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

Заключение

В работе рассматривается понятие абстрактного типа данных – одного из ключевых понятий в программировании. Абстрактные типы данных используются как метод абстракции данных в программном коде, а также как метод выделения объектов в программной модели.
Для описания абстрактных типов данных используется т.н. поведенческая абстракция. Объекты рассматриваются как черные ящики, доступ к которым обеспечивается посредством т.н. кластера операций. Это позволяет подменять реализации абстрактного типа данных без необходимости что-то менять в коде взаимодействия.
Для абстрактных типов данных имеется строгое математическое описание – теория сигнатур многосортных алгебраических систем. Абстрактный тип данных описывается как сигнатура Σ-алгебры с конечным набором аксиом в виде равенств.
Для каждого класса Σ-алгебр имеется т.н. инициальная Σ-алгебра, из которой имеется в каждую алгебру этого класса единственный гомоморфизм. Инициальную Σ-алгебру можно построить как множество термов, построенных из операций сигнатуры. При этом роль атомарных термов играют нульарные операции, называемые также константами. Инициальные алгебры позволяют производить вычисления на сигнатуре Σ-алгебры: получать ответы на вопросы, проверять корректность задания АТД и т.д. В статье даются примеры алгебраических спецификаций, записанные на специально созданных для этих целей языках OBJ и CASL.
Автор надеется, что данная работа послужит внесению некоторой ясности в вопросы, связанные с понятием абстрактного типа данных. Математическая теория абстрактных типов данных вообще мало известна в программистском сообществе. Донести информацию об этом именно разработчикам представляется автору в высшей степени полезным делом.

Список литературы

1. 
   Liskov B., Zilles S.Programming with abstract data types // SIGPlan Notices, vol. 9, no. 4, 1974.
   
2. 
   Мальцев А.И. Алгебраические системы: М.: Наука, 1970. 392 с.
   
3. 
   Кнут Д. Искусство программирования. Том 1. Основные алгоритмы. Вильямс, 2010.
   
4. 
   Zilles S. Procedure encapsulation: a linguistic protection technoque // SIGPlan Notices, vol. 8, no. 9, 1973.
   
5. 
   Parnas D. On the criteria to be used in decomposing systems into modules // Communications of the ACM, 15, 1972.
   
6. 
   Cock W.R. Object-Oriented Programming Versus Abstract Data Types. ed. by de Bakker J.W., de Roever W.P. and Rozenberg G., in Foundations of Object Oriented Languages, Lecture Notes in Computer Science #489, 1990. pp. 151-178.
   
7. 
   http://ru.wikipedia.org/wiki/Принцип_подстановки_Лисков.
   
8. 
   http://en.wikipedia.org/wiki/Curiously_recurring_template_pattern
   
9. 
   http://gcc.gnu.org/wiki/LinkTimeOptimization.
   
10. 
    Goguen J. Memories of ADJ // Bulletin of the European Association. for Theoretical Computer Science, 36:96–102, October 1989.
    
11. 
    Чень Ч., Ли Р. Математическая логика и автоматическое доказательство теорем. Пер. с англ. М.: Наука, 1983.
    
12. 
    http://cseweb.ucsd.edu/~goguen/sys/obj.html.
    
13. 
    http://www.informatik.uni-bremen.de/cofi/wiki/index.php/CASL.
    
14. 
    http://www.informatik.uni-bremen.de/cofi/wiki/index.php/About_CoFI.