Абстрактний тип даних

У філософії імперативних мов програмування, абстрактна структура даних задумана як сутність, яка є змінним-це означає, що він може перебувати в різних станах в різний час. Деякі операції можуть змінити стан АТД; таким чином, порядок, в якому оцінюються операції має важливе значення, і та ж сама операція на одних і тих же суб'єктах, можуть мати різні ефекти, якщо виконуються в різний час, так само, як інструкції комп'ютера, або команди і процедури імперативної мови. Щоб підкреслити цю точку зору, прийнято казати, що операції виконуються або застосовуються, не стільки, скільки оцінюються. Імперативний стиль часто використовується при описі абстрактних алгоритмів. (Дивіться Мистецтво програмування Дональда Кнута для отримання більш докладної інформації)

Визначення імперативного стилю АТД часто залежать від поняття абстрактної змінної, яку можна розглядати, як найпростіший нетривіальний АТД. Абстрактна змінна V є змінний об'єкт, який допускає дві операції:

• store(V, х), де х є значення невизначеного характеру;
• fetch(V), що дає значення, з тим обмеженням, що
• fetch(V) завжди повертає значення х, котре використовуються в самий останній операції store(V, х) на тій же самій змінної V.

Як і в багатьох мовах програмування, операція store(V, x) часто пишеться V ← x (або деякі аналогічні позначення) і fetch(V) мається на увазі кожен раз, коли змінна V використовується в контексті, де потрібно значення. Так, наприклад, V ← V + 1 зазвичай розуміється, як скорочення для store(V,fetch(V) + 1).

У цьому визначенні неявно передбачається, що збереження значення в змінну U не робить ніякого впливу на стан окремої змінної V. Для того, щоб зробити це припущення явним, можна було б додати, що обмеження

• якщо U і V є різні змінні, то послідовність { store(U, x); store(V, y) } еквівалентна послідовності  store(V, y); store(U, x) }.

У більш загальному плані, при визначенні АТД часто припускають, що будь-яка операція, яка змінює стан одного екземпляра АТД не робить ніякого впливу на стан будь-якого іншого екземпляру (в тому числі інших екземплярів одного і того ж АТД), хіба тільки аксіоми АТД не означають, що два екземпляри пов'язані (псевдонімами) в цьому сенсі. Наприклад, при розширенні визначення абстрактної змінної, щоб включити абстрактні структури, операція, яка вибирає поле з структурою змінної R повинен дати змінну V, яка є псевдонімом до тієї частини R.

Означення абстрактної змінної V може також обмежити записані значення x членів певної множини X, називається діапазон, або тип V. Як і в мовах програмування, такі обмеження можуть спростити опис і аналіз алгоритмів, а також поліпшити їх читаність.

Зверніть увагу, що це визначення нічого не говорить про результат оцінки fetch(V), коли V є не-ініціалізована, тобто, перед виконанням будь-якої операції збереження на V. Алгоритм, який робить це, як правило, вважається недійсним, оскільки його ефект не визначений. (Проте, є деякі важливі алгоритми, ефективність яких значною мірою залежить від припущення, що така вибірка є законною, і повертає деяке довільне значення в діапазоні змінної.)

Деяким алгоритмам необхідно створювати нові екземпляри деякого АТД (наприклад, нові змінні, або нові стеки). Для опису таких алгоритмів, він, як правило, включає в АТД визначення операції Create(), який дає екземпляр АТД, як правило, з аксіом, еквівалентних

• результат операції Create() відрізняється від будь-якого екземпляру, які використовується алгоритмом.

Ця аксіома може бути посилена, щоб виключити також часткове накладення спектрів з іншими екземплярами. З іншого боку, ця аксіома досі дозволяє реалізації операції Create() отримати раніше створений екземпляр, який став недоступним для програми.

Як інший приклад, визначення абстрактного стека імперативним стилем може вказати, що стан стека S може бути змінений тільки за допомогою операцій

• push(S, x), де х деяке значення невизначеного характеру;
• pop(S), що надає значення як результат, з тим обмеженням, що
• Для будь-якого значення х і будь-якої абстрактної змінної V, послідовність операцій { push(S,x); V ← pop(S)} еквівалентна операції V ← x.

Так як привласнення V ← x, за визначенням, не може змінити стан S, ця умова означає, що V ← pop(S) відновлює S в стан він мав до операції push(S,x). З цієї умови і з властивостей абстрактних змінних, то це означає, наприклад, що послідовність

{ push(S, x); push(S, y); U ← pop(S); push(S, z); V ← pop(S); W ← pop(S) }

де х, у та z є будь-які значення, а U, V, W попарно різні змінні, еквівалентно

{ U ← y; V ← z; W ← x }

При цьому неявно передбачається, що операції на екземплярі стека не змінюють стан будь-якого іншого екземпляру АТД, в тому числі інших стеків; а саме

• Для будь-яких значень x, y, а також будь-яких різних стеків S і T, послідовність { push(S,x); push(T,y)} еквівалентна послідовності { push(T,y); push(S,x)}.

Абстрактне визначення стека зазвичай включає в себе також булеву функцію empty(S) і операцію create(), яка повертає екземпляр стека, з аксіом, еквівалентних

• create() ≠ S для будь-якого стека S (новостворений стек відрізняється від усіх попередніх стеків);
• empty(create()) (новостворений стек порожній);
• not empty(push(S, x)) (заштовхуючи щось в стек робить його непустим);

Іноді АТД визначається так, якби тільки один його екземпляр існував під час виконання алгоритму, і всі операції були застосовані до цього екземпляру, який явно не записаний. Наприклад, абстрактний стек, який вказано вище, може бути визначений з операціями push(x) та pop(), які працюють на єдиному існуючому стеку. Визначення АТД в цьому стилі можна легко переписати, щоб визнати, що кілька екземплярів АТД співіснують, шляхом додавання явного параметра екземпляру (наприклад, S в попередньому прикладі) для кожної операції, яка використовує або змінює неявне екземпляр.

З іншого боку, деякі АТД не можуть бути визначені за значенням, не припускаючи декількох екземплярів. Це той випадок, коли одна операція приймає два різних екземпляра АДТ як параметри. Для прикладу, розглянемо доповнюючи визначення абстрактного стека з операцією compare(S, T), яка перевіряє, чи стеки S і Т містять одні й ті ж елементи в тому ж порядку.

Інший спосіб визначення АТД, ближче до духу функціонального програмування, це розглядати кожен стан структури, як окрему сутність. З цієї точки зору, будь-яка операція, яка змінює АТД моделюється як математична функція, яка приймає старий стан як аргумент, і повертає новий стан як частину результату. На відміну від імперативних операцій, ці функції не мають побічних ефектів. Таким чином, порядок, в якому вони оцінюються — несуттєвий, і та ж операція застосовується до тих же аргументів (в тому числі і тих же вхідних станів) завжди буде повертати ті ж результати (і вихідні стани).

У функціональному поданні, зокрема, не існує ніякого способу (або необхідності), щоб визначити «абстрактне змінну» з семантикою імперативних змінних (а саме, з операціями fetch і store). Замість того щоб зберігати значення в змінних, він передає їх як аргументи функції.

Наприклад, повне визначення абстрактного стека у функціональному стилі може використовувати три операції:

• push: приймає стан стека і довільне значення, повертає стан стека;
• top: приймає стан стека, повертає значення;
• pop: приймає стан стека, повертає стан стека.

У визначенні функціонального стилю немає необхідності в операції створення. Справді, не існує поняття «екземпляр стеку». Стек станів можна розглядати, як потенційні стани єдиної структури стека, а два стану стека, які містять одні і ті ж значення в тому ж порядку, вважаються однаковими станами. Ця точка зору фактично відображає поведінку деяких конкретних реалізацій, таких як зв'язані списки з хеш-мінусами.

Замість операції create(), визначення абстрактного стека у функціональному стилі може припустити існування особливого стану стека, порожнього стека, який позначається спеціальним символом, як Λ або «()»; або визначити операцію bottom(), яка не приймає аргументів і повертає цей особливий стан стека. Зауважимо, що аксіоми мають на увазі, що

• push(Λ, x) ≠ Λ.

У визначенні стека у функціональному стилі, немає потреби у предикаті empty: замість нього, можна перевірити, чи є стек порожній шляхом тестування, чи дорівнює стек Λ.

Зверніть увагу, що ці аксіоми не визначають дію top(s) або pop(s), якщо s не є станом стека повертається операцією push. Так як операція push залишає стек не порожнім, тоді ці дві операції не визначені (і, отже неспроможні) при s = Λ. З іншого боку, аксіоми (і відсутність побічних ефектів) слід, що push(s, x) = push(t, y) тоді й лише тоді, коли x = y та s = t.

Як і в деяких інших областях математики, прийнято вважати також, що стек станів тільки ті, чиє існування може бути доведено з аксіом в кінцеве число кроків. В прикладі абстрактного стеку, зазначений вище, це правило означає, що кожен стек — це кінцева послідовність значень, яка стає порожнім стеком (Λ) після кінцевого числа викликів операції pop(). Самі по собі, аксіоми, не виключають існування нескінченних стеків (на котрих операцію pop() можна викликати нескінчену кількість раз, щоразу отримуючи інший стан) або кругові стеки (які повертаються в той же стан після кінцевого числа викликів операції pop()). Зокрема, вони не виключають стани S такі, що pop(s) = s або push(s, x) = s для деякого х. Однак, так як ніхто не може отримати такий стек станів із заданими операціями, вони вважаються «не існуючими».

Крім поведінки з точки зору аксіом, можна також включити, в визначенні операції АТД, їх алгоритмічної складності. Олександр Степанов, дизайнер стандартної бібліотеки шаблонів C++, включені гарантії складності в специфікації STL, аргументуючи:

Причина введення поняття абстрактних типів даних було дозволити взаємозамінність програмних модулів. Ви не можете мати змінні модулі, якщо ці модулі не поділяють подібну поведінку складності. Якщо замінити один модуль іншим модулем з тією же функціональною поведінкою, але з різними компромісами складності, користувач цього коду буде неприємно здивований. Я міг би сказати йому що-небудь, що мені подобається абстракції даних, і він до цих пір не хотів би використовувати код. Складність твердження мають бути частиною інтерфейсу.

— Олександр Степанов[3]

Абстракція зобов'язується, що будь-яка реалізація АТД має певні властивості і здібності; знати їх — це все, що потрібно, щоб використовувати об'єкт АТД. Користувач не потребує будь-яких технічних знань про те, як здійснюється робота над АТД, щоб їх використовувати.

Код, який використовує об'єкт АТД не потрібно буде редагувати, якщо реалізація АТД змінилася. Оскільки будь-які зміни в реалізації як і раніше повинні відповідати інтерфейсу, а так як код з використанням об'єкту АТД може відноситися тільки до властивостей і здібностей, зазначених в інтерфейсі, можуть бути зроблені зміни в реалізації, при цьому не вимагаючи будь-яких змін в коді, де використовується АТД.

Різні варіанти реалізації АТД, мають всі ті ж властивості і здібності, котрі еквівалентні і можуть бути використані як взаємозамінні в коді, який використовує АТД. Це дає велику гнучкість при використанні об'єктів АТД в різних ситуаціях. Наприклад, різні реалізації АТД можуть бути більш ефективним в різних ситуаціях; можна використовувати кожен з них в ситуації, коли він є кращим, збільшуючи таким чином загальну ефективність.

Розширення АТД для комп'ютерної графіки було запропоновано в 1979 році:[4] абстрактний тип графічних даних (AGDT). Воно було введено Надією Магненат Тельманн і Даніелем Тельманн. AGDT забезпечує переваги АТД зі зручностями для побудови графічних об'єктів в структурованому вигляді.

Як приклад, ось реалізація абстрактного стека в мові програмування C.

Інтерфейс в імперативному стилі може бути:

typedef struct stack_Rep stack_Rep;       // тип: уявлення екземпляру стека(непрозорий запис)
typedef stack_Rep* stack_T;               // тип: дескриптор до екземпляру стека (непрозорий вказівник)
typedef void* stack_Item;                 // тип: значення, збережене в екземплярі стека(довільний адрес)

stack_T stack_create(void);               // створює новий порожній екземпляр стека
void stack_push(stack_T s, stack_Item x); // додає елемент на вершину стека
stack_Item stack_pop(stack_T s);          // видаляє верхній елемент зі стека і повертає його
bool stack_empty(stack_T s);              // перевіряє, порожній чи стек

Цей інтерфейс може бути використаний в такий спосіб:

#include <stack.h>          // підключає інтерфейс стека

stack_T s = stack_create(); // створює новий порожній екземпляр стека
int x = 17;
stack_push(s, &x);          // додає адресу x на вершину стека
void* y = stack_pop(s);     // видаляє адресу х зі стека і повертає його
if(stack_empty(s)) { }      // робить щось, якщо стек порожній

Цей інтерфейс може бути реалізований різними способами. Реалізація може бути як завгодно неефективна, так як формального визначення АТД, вище, не визначає, скільки простору стека може використовуватися, і як довго кожна операція повинна зайняти. Він також не уточнює, чи продовжує стек стану s існувати після виклику x ← pop(s).

На практиці формальне визначення повинно бути зазначено, що простір пропорційно кількості елементів заштовханих і ще не видалених; і що кожна з операцій вище, повинна закінчитися за постійну кількість часу, незалежно від цієї кількості. Для виконання цих додаткових специфікацій, реалізація може використовувати зв'язаний список або масив (з динамічною зміною розмірів) разом з двома цілими числами (кількість елементів і розмір масиву).

Функціональний стиль визначення АТД є більш придатними для функціональних мов програмування, і навпаки. Проте, можна забезпечити інтерфейс функціональним стилем навіть в імперативній мові програмування, як C. Наприклад:

typedef struct stack_Rep stack_Rep;          // тип: уявлення стану стека (непрозорий запис)
typedef stack_Rep* stack_T;                  // тип: дескриптор до стану стека (непрозорий вказівник)
typedef void* stack_Item;                    // тип: значення стану стека (довільний адрес)

stack_T stack_empty(void);                   // повертає порожнє стан стека
stack_T stack_push(stack_T s, stack_Item x); // додає елемент на вершину стану стека і повертає отриманий стан стека
stack_T stack_pop(stack_T s);                // видаляє верхній елемент зі стану стека і повертає отриманий стан стека
stack_Item stack_top(stack_T s);             // повертає верхній елемент стану стека

Багато сучасних мов програмування, такі як C ++ і Java, поставляються зі стандартними бібліотеками, які реалізують кілька загальних АТД, таких як ті, які перераховані вище.

Специфікація деяких мов програмування навмисно розпливчаста про подання деяких вбудованих типів даних, визначаючи тільки ті операції, які можуть бути зроблені на них. Таким чином, ці типи можна розглядати як «вбудовані АТД». Прикладами є масиви в багатьох сценарних мовах, таких як Awk, Lua, і Perl, які можна розглядати як реалізацію абстрактного списку.