Кіріспе
Деректер түрлерінің математикалық моделі
Компьютерлік ғылымда абстрактілік дерек түрі (АДТ) – деректердің пайдаланушысының көзқарасы бойынша оның мінез-құлқы (семантикасы) арқылы анықталатын, атап айтқанда, мүмкін мәндер, осы типтегі деректер бойынша мүмкін операциялар және осы операциялардың мінез-құлқы. Бұл математикалық модель деректердің нақты бейнелемелері болып табылатын және пайдаланушының емес, іске асырушының көзқарасы болып табылатын дерек құрылымдарымен қарама-қайшы келеді. Мысалы, стекте соңғы кірген, бірінші шығады (LIFO) ережесіне сәйкес келетін push/pop операциялары бар, және оларды тізім немесе массивті пайдалану арқылы нақты іске асыруға болады. Тағы бір мысал – мәндерді қандай да бір ретсіз және қайталанбайтын мәндерді сақтайтын жиын. Жиыннан мәндер алынбайды, керісінше, мәндік мүшелікке тексеру арқылы «бар» немесе «жоқ» деген Бульдік мәлімдеме алуға болады. АДТ – бұл теориялық ұғым, ол формалды семантикада және бағдарламаны тексеруде, сондай-ақ алгоритмдерді, дерек құрылымдарын және бағдарламалық жүйелерді жобалау мен талдауда қолданылады (кем қатаңдықпен). Көптеген негізгі компьютерлік тілдер АДТ-ны формалды түрде анықтауды тікелей қолдамайды. Дегенмен, әртүрлі тілдік мүмкіндіктер АДТ-ны іске асырудың белгілі бір аспектілеріне сәйкес келеді және оларды АДТ-мен шатастыру оңай; мұндайларға абстрактілік типтер, түсініксіз дерек түрлері, протоколдар және келісімшарт бойынша жобалау кіреді. Мысалы, модульдік бағдарламалауда модуль АДТ операцияларына сәйкес келетін процедураларды, көбінесе шектеулерді сипаттайтын түсініктемелермен жариялайды. Бұл ақпаратты жасыру стратегиясы клиенттік бағдарламаларды бұзбай модульді іске асыруды өзгертуге мүмкіндік береді, бірақ модуль АДТ-ны тек бейресми түрде анықтайды. Абстрактілік дерек түрлерінің түсінігі деректерді абстракциялау тұжырымдамасымен байланысты, ол объектіге бағытталған бағдарламалауда және бағдарламалық жасақтаманы жасаудағы келісімшарт әдістемелерінде маңызды болып табылады.
Тарих
ADT-ны алғаш рет Барбара Лисков және Стивен Н. Зильс 1974 жылы CLU тілін жасау барысында ұсынған. 1980 жылдар шамасында алгебралық спецификация компьютер ғылымындағы маңызды зерттеу тақырыбы болды және сол кезде абстрактілі деректер типтерімен шамалас ұғым еді. Оның математикалық негізі – универсалды алгебра.
Анықтама
Формальды түрде, АДТ математикадағы алгебралық құрылымға ұқсас, доменнен, операциялар жиынтығынан және операциялардың орындалуын шектейтін талаптар жиынтығынан тұрады. Домен көбінесе аталмайды, мысалы, АДТ операциялары жиынтығы бойынша еркін объекті ретінде беріледі. АДТ интерфейсі әдетте тек домен мен операцияларды, сондай-ақ операцияларға қатысты кейбір талаптарды, мысалы, бастапқы және соңғы шарттарды қамтиды; бірақ операциялар арасындағы қатынастар сияқты басқа талаптарды емес, олар мінез-құлық деп есептеледі. Мінез-құлықты формалды түрде сипаттаудың екі негізгі тәсілі бар: аксиоматикалық және операциялық семантика. Интерфейстің құрамына кірмесе де, талаптар АДТ анықтамасы үшін маңызды болып табылады; мысалы, стек пен кезек элемент қосу/алып тастау интерфейсі жағынан ұқсас, бірақ соңғы кірген, бірінші шығатын (LIFO) және бірінші кірген, бірінші шығатын (FIFO) мінез-құлықты ажырататын талаптар болып табылады. Талаптар тек теңдеулерден ғана емес, сонымен қатар логикалық формулалардан тұрады.
Аксиомалық семантика
Функционалдық бағдарламалау қағидаларына сәйкес, абстрактілі деректер құрылымының әрбір күйі жеке бірлік немесе мән болып табылады. Осы көзқарас бойынша, әрбір операция жасайтын әрекет қандай да бір қосымша әсерлерге жол бермейтін математикалық функция ретінде бейнеленеді. Абстрактілі деректер құрылымын өзгертетін операциялар ескі күйді аргумент ретінде қабылдап, нәтижесінің бір бөлігі ретінде жаңа күйді қайтаратын функциялар түрінде модельделеді. Операциялардың орындалу реті маңызды емес, және бірдей аргументтерге (соның ішінде бірдей кіріс күйлеріне) қолданылған бірдей операция әрқашан бірдей нәтижелерді (және шығыс күйлерін) береді. Бұл талаптар аксиомалар немесе алгебралық заңдар түрінде көрсетіледі, оларды операциялар орындауы тиіс.
Операциялық семантика
Императивті бағдарламалау қағидаларына сәйкес, абстрактілі деректер құрылымы өзгертілетін нысан ретінде қарастырылады, яғни уақыт ұғымы бар және АДТ әртүрлі уақыттарда әртүрлі күйде болуы мүмкін. Операциялар уақыт өте келе АДТ-ның күйін өзгертеді; демек, операциялардың орындалу реті маңызды, және бір операция бірдей нысандарға әртүрлі уақытта орындалса, әртүрлі әсер ете алады. Бұл компьютер нұсқауларына немесе императивті тілдің командалары мен процедураларына ұқсас. Бұл көзқарасты нақтылау үшін, операциялар бағаланатын емес, орындалатын немесе қолданылатын болады деу қалыпты, бұл абстрактілі алгоритмдерді сипаттағанда жиі қолданылатын императивті стильге ұқсас. Шешімдер әдетте мәтін түрінде беріледі.
Шектелген түрлері
ADT анықтамасы көбінесе оның мысалдары үшін сақталатын мәндерді, осы айнымалылардың диапазоны деп аталатын белгілі бір X жиынының мүшелерімен шектейді. Мысалы, абстракт айнымалы тек қана бүтін сандарды сақтауға шектелуі мүмкін. Бағдарламалау тілдеріндегідей, мұндай шектеулер алгоритмдерді сипаттау және талдауды жеңілдетіп, олардың түсінікті болуын жақсартады.
Аталық атауы
Операциялық стильде бірнеше инстанцияны қалай өңдеуге болатыны және бір инстанцияны өзгерту басқаларына әсер ете алатыны көбінесе белгісіз болады. ADT-ны анықтаудың әдеттегі стилі операцияларды алгоритм орындалу кезінде тек бір ғана инстанция бар сияқты жазады, ал барлық операциялар сол инстанцияға қолданылады. Мысалы, стекте (x) және () операциялары болуы мүмкін, олар қолданыстағы жалғыз стекте жұмыс істейді. Бұл стильдегі ADT анықтамаларын, жасырын инстанцияны пайдаланатын немесе өзгертетін әрбір операцияға (мысалы, төмендегі стек мысалында S сияқты) нақты инстанция параметрін қосу арқылы ADT-ның бірнеше бірдей инстанцияларын қабылдауға оңай қайта жазуға болады. Кейбір ADT-лар бірнеше инстанцияларға рұқсат берілмесе, мағыналы түрде анықталмайды, мысалы, бір операция ADT-ның екі түрлі инстанциясын параметрлер ретінде қабылдағанда, жиынтардағы немесе тізімдердегі операция сияқты. Көп инстанциялы стиль кейде псевдоаксиомамен біріктіріледі, атап айтқанда, нәтижесі алгоритм қолданып жүрген кез келген инстанциядан өзгеше болады. ADT-ның іске асырылымдары әлі де жадты қайта пайдалана алады және бұрын жасалған инстанцияны беруге мүмкіндік береді; алайда, мұндай инстанцияның тіпті «қайта пайдаланылғанын» анықтау ADT формализмінде қиын. Жалпы алғанда, бұл аксиома басқа инстанциялармен ішінара сәйкестікті жою үшін күшейтілуі мүмкін, сондықтан күрделі ADT-лар (мысалы, ағаштар немесе жазбалар) және сілтемелі стильдегі ADT-лар (мысалы, көрсеткіштер) толыққанды бөлек деп есептелуі мүмкін. Мысалы, абстрактілі өзгермелінің анықтамасын абстрактілі жазбаларды қоса алғанда кеңейткенде, жазба өзгермелінің F өрісіне жасалған операциялар, әрине, R-ден ерекшеленетін, бірақ сонымен бірге оның бір бөлігі болып табылатын F-ді қамтиды. Ішінара сәйкестік аксиомасы бір жазба өзгермелісінің өрісін өзгертудің басқа жазбаларға әсер етпейтінін көрсетеді.
Күрделілік талдауы
Кейбір авторлар алгоритмдерді талдауға көмектесу үшін әр операцияның есептеулік күрделілігін ("құнын") уақыт (компьютерлік операцияларды есептеу үшін) және кеңістік (мәндерді көрсету үшін) тұрғысынан қосады. Мысалы, әр операцияға бірдей уақыт жұмсалады және әр мән АДТ-ның күйіне қарамастан бірдей орын алады, немесе АДТ-ның "өлшемі" болады және операциялар АДТ-ның өлшемі бойынша сызықтық, квадраттық сияқты болады. C++ Стандартты Үлгілер кітапханасының авторы Александр Степанов STL спецификациясына күрделік кепілдіктерін енгізді: «Абстрактілі деректер типтері ұғымын енгізудің себебі – алмастырылатын бағдарламалық модульдерге мүмкіндік беру еді. Егер модульдердің күрделілігі ұқсас болмаса, оларды алмастыру мүмкін емес. Егер мен бір модульді функционалдық тұрғыдан ұқсас, бірақ күрделілік тұрғысынан өзгеше модульмен алмастырсам, осы кодты пайдаланушы көңілі толмайды. Мен оған деректерді абстракциялау туралы қандай болса да айтсам да, ол бұл кодты пайдаланғысы келмейді. Күрделік туралы мәлімдемелер интерфейстің бөлігі болуы керек». – Александр Степанов.
The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with the same functional behavior but with different complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface.|Alexander Stepanov
Other authors disagree, arguing that a stack ADT is the same whether it is implemented with a linked list or an array, despite the difference in operation costs, and that an ADT specification should be independent of implementation.
Басқа авторлар келіспейді, олар ADT стегі байланысты тізім немесе массив арқылы іске асырылса да, операциялардың құнына қарамастан бірдей болады және ADT спецификациясы іске асырудан тәуелсіз болуы керек деп санайды.
The reason for introducing the notion of abstract data types was to allow interchangeable software modules. You cannot have interchangeable modules unless these modules share similar complexity behavior. If I replace one module with another module with the same functional behavior but with different complexity tradeoffs, the user of this code will be unpleasantly surprised. I could tell him anything I like about data abstraction, and he still would not want to use the code. Complexity assertions have to be part of the interface.|Alexander Stepanov
Other authors disagree, arguing that a stack ADT is the same whether it is implemented with a linked list or an array, despite the difference in operation costs, and that an ADT specification should be independent of implementation.
Абстрактілдік айнымалы
Абстрактіл өзгермеліні ең қарапайым тривиальді емес ADT ретінде қарастыруға болады, императивті өзгермелінің семантикасымен. Ол екі операцияны қабылдайды, ал операциялық анықтамалар көбінесе абстрактіл айнымалылар арқылы жазылады. Аксиомалық семантикада, абстрактіл өзгермелінің түрі және оның мазмұнының түрі болсын, онда – бұл функция, ал – функция болып табылады. Негізгі шектеу – әрқашан сол айнымалыға жасалған соңғы операцияда қолданылған x мәнін қайтару, яғни біз сондай-ақ мәнді толыққанды жаңартуды талап ете аламыз. Операциялық семантикада (V) – V орнындағы ағымдағы мәнді қайтаратын процедура, ал (V, x) – V орнына x мәнін сақтайтын процедура, қайтарым түрімен. Шектеулер оқу операцияларының жазу операцияларымен сәйкес келуі ретінде бейресми түрде сипатталады. Көптеген бағдарламалау тілдеріндегідей, (V, x) операциясы көбінесе V ← x (немесе осыған ұқсас жазба) түрінде жазылады, ал (V) айнымалы V мән талап ететін контексте қолданылғанда түсініледі. Мысалы, V ← V + 1 жиі (V,(V) + 1) дегеннің қысқартылған түрі ретінде түсініледі. Бұл анықтамада атаулар әрқашан ерекше деп ескеріледі: U айнымалысына мән сақтау V айнымалының күйіне әсер етпейді. Бұл ескертуді нақтылау үшін, егер U және V ерекше айнымалылар болса, { (U, x); (V, y) } тізбегі { (V, y); (U, x) } тізбегіне тең деуге болады. Бұл анықтама V инициализацияланбаған кезде (V) бағалау нәтижесі туралы ештеңе айтпайды, яғни V-ге кез келген операция жасаудан бұрын. Сақтаудан бұрын алуға тыйым салуға болады, белгілі бір нәтиже беруге немесе анықталмаған қалдыруға болады. Мұндай операцияның заңды екені және айнымалының диапазонында кездейсоқ мәнді қайтаратыны туралы болжамға тиімділігі байланысты алгоритмдер бар.
In the operational semantics, (V) is a procedure that returns the current value in the location V, and (V, x) is a procedure with return type that stores the value x in the location V. The constraints are described informally as that reads are consistent with writes. As in many programming languages, the operation (V, x) is often written V ← x (or some similar notation), and (V) is implied whenever a variable V is used in a context where a value is required. Thus, for example, V ← V + 1 is commonly understood to be a shorthand for (V,(V) + 1). In this definition, it is implicitly assumed that names are always distinct: storing a value into a variable U has no effect on the state of a distinct variable V. To make this assumption explicit, one could add the constraint that:
if U and V are distinct variables, the sequence { (U, x); (V, y) } is equivalent to { (V, y); (U, x) }. This definition does not say anything about the result of evaluating (V) when V is un initialized, that is, before performing any operation on V. Fetching before storing can be disallowed, defined to have a certain result, or left unspecified. There are some algorithms whose efficiency depends on the assumption that such a is legal, and returns some arbitrary value in the variable's range.
Іске асыру
Абстрактілі деректер түрлері – (басқа нәрселермен қатар) абстрактілі алгоритмдердің сипаттамасын жеңілдету, дерек құрылымдарын жіктеу және бағалау, сондай-ақ бағдарламалау тілдерінің типтік жүйелерін ресми түрде сипаттау үшін қолданылатын теориялық ұғымдар. Дегенмен, ADT-ны іске асыруға болады. Бұл, әрбір ADT мысалы немесе күйі нақты дерек типі немесе дерек құрылымымен ұсынылады, ал әрбір абстрактілі операцияға сәйкес процедура немесе функция болады. Бұл іске асырылған процедуралар ADT-ның ерекшеліктері мен аксиомаларын белгілі бір деңгейде сақтайды. Іс жүзінде, іске асыру толық емес, сондықтан пайдаланушылар өкілдік пен іске асырылған процедуралардың шектеулерінен туындайтын мәселелерге назар аударуы керек. Мысалы, бүтін сандар 0 және 1 ерекшеленген мәндерімен, қосу, алу, көбейту, бөлу (нөлге бөлуге қатысты сақтықпен), салыстыру және т.б. операцияларымен анықталуы мүмкін, олар абстрактілі алгебрадағы ассоциативтілік, коммутативтілік сияқты таныс математикалық аксиомаларға сәйкес келеді. Алайда, компьютерде бүтін сандар көбінесе 32 немесе 64 биттік бинарлық сандар түрінде ұсынылады. Пайдаланушылар осы ұсынысқа байланысты мәселелерге, мысалы, арифметикалық ағып кетуге назар аударуы керек, онда ADT жарамды нәтижені көрсетеді, бірақ ұсыныс бұл мәнді қабылдай алмайды. Дегенмен, көптеген жағдайларда пайдаланушы осы қателіктерді елемеуге және іске асырылғанды абстрактілі дерек типі ретінде қарастыруға болады. Көбінесе, бір ADT-ны әртүрлі нақты дерек құрылымдарын пайдалана отырып, іске асырудың көптеген жолдары бар. Мысалы, абстрактілі стек байланысты тізім немесе массив арқылы іске асырылуы мүмкін. ADT-ның әртүрлі іске асырылулары, барлық қасиеттері мен мүмкіндіктері бірдей болса, семантикалық түрде эквивалентті деп есептелуі мүмкін және ADT-ны пайдаланатын кодта бірін-бірі алмастырып қолдануға болады. Бұл абстракция немесе капсулация түрін қамтамасыз етеді және ADT объектілерін әртүрлі жағдайларда пайдалану кезінде үлкен икемділік береді. Мысалы, ADT-ның әртүрлі іске асырылулары әртүрлі жағдайларда тиімдірек болуы мүмкін; оларды тиімдірек жағдайларда пайдалану арқылы жалпы тиімділікті арттыруға болады. ADT интерфейсіне сәйкес іске асырылуды пайдаланатын код, ADT іске асырылуы өзгерсе де жұмыс істеуін жалғастырады. Клиенттердің іске асырылуға тәуелді болуын болдырмау үшін ADT көбінесе бір немесе бірнеше модульдерде мөлдір емес дерек типі немесе қандай да бір дескриптор ретінде жинақталады, оның интерфейсі операциялардың қолтаңбасын (параметрлер мен нәтижелердің саны мен түрлері) ғана қамтиды. Модульдің іске асырылуы – атап айтқанда, процедуралардың денесі мен қолданылатын нақты дерек құрылымы – модульдің көптеген клиенттерінен жасырылуы мүмкін. Бұл іске асырылуды клиенттерге әсер етпей өзгертуге мүмкіндік береді. Егер іске асырылу ашық болса, ол мөлдір дерек типі ретінде белгілі. C++ және Java сияқты қазіргі заманғы объектіге бағытталған тілдер абстрактілі деректер түрлерінің бір түрін қолдайды. Класс тип ретінде пайдаланылғанда, ол жасырын ұсынысқа сілтеме жасайтын абстрактілі тип болып табылады. Бұл модельде ADT әдетте класс ретінде іске асырылады, ал ADT-ның әрбір мысалы әдетте сол кластың объекісі болады. Модульдің интерфейсі конструкторларды әдеттегі процедуралар ретінде, ал ADT операцияларының көпшілігін осы кластың әдістері ретінде жариялайды. Көптеген қазіргі заманғы бағдарламалау тілдері, мысалы C++ және Java, осы стильде көптеген ADT-ны іске асыратын стандартты кітапханалармен бірге келеді. Алайда, бұл тәсіл ADT-да кездесетін бірнеше ұсыныс нұсқаларын оңай қамтамасыз етпейді. Ол сондай-ақ объектіге бағытталған бағдарламалардың кеңейтілуін шектеуі мүмкін. Интерфейстерді типтер ретінде пайдаланатын таза объектіге бағытталған бағдарламада типтер ұсыныс емес, мінез-құлыққа қатысты. Кейбір бағдарламалау тілдерінің спецификациясы белгілі бір енгізілген деректер түрлерінің ұсынысы туралы қасақана бұлыңғыр, олармен жасалатын операцияларды ғана анықтайды. Сондықтан, бұл типтерді "енгізілген ADT" деп қарастыруға болады. Мысалы, Awk, Lua және Perl сияқты көптеген сценарий тілдеріндегі массивтер абстрактілі тізімнің іске асырылуы ретінде қарастырылуы мүмкін. Ресми спецификация тілінде ADT-лар аксиоматикалық түрде анықталуы мүмкін, содан кейін тіл осы ADT-лардың мәндерін өңдеуге мүмкіндік береді, осылайша қарапайым және тікелей іске асыруды қамтамасыз етеді. Мысалы, OBJ тілдері отбасы спецификация мен қайта жазу үшін теңдеулерді анықтауға және оларды орындауға мүмкіндік береді. Мұндай автоматты іске асырылулар көбінесе арнайы іске асырылуларға қарағанда тиімді болмайды.
Мысал: абстрактілі стекті іске асыру
Мысал ретінде, C бағдарламалау тілінде жоғарыда сипатталған абстрактілік стектің іске асырылуы келтірілген.