Контрольные вопросы

1) Какие алгебры называются подобными?

2) Что такое  - равенство и в чем его назначение?

3) Какая алгебра называется моделью множества равенств?

4) Что является замыканием множества равенств?

5) Что называется представлением?

6) Сформулируйте понятие «теория».

7) Что называется моделью теории?

4.5. Абстрактные типы данных

Обсуждая алгебры и теории, мы постоянно соприкасались с двумя уровнями рассмотрения: конкретным и абстрактным. Конкретный уровень представляется конкретной алгеброй с конкретными носителями основ и конкретными функциями, задающими реализации знаков операций. Абстрактный уровень представляется сигнатурой и аксиомами теории.

По отношению к типам данных также можно выделять конкретный и абстрактный аспекты их рассмотрения. Типы данных, предоставляемые конкретным компьютером и конкретной системой программирования, конкретны: для каждого из них транслятор обеспечивает конкретный способ представления значений (в виде последовательностей битов памяти) и конкретные алгоритмы реализации операций. В то же время типы данных, предлагаемые языком программирования, абстракты. Для каждого из них описание языка задает только синтаксис (имена основ, имена и типы операций) и семантику (смысл операций). В разных трансляторах одному и тому же абстрактному типу данных сопоставляются различные конкретные типы. Программы, полученные разными трансляторами, будут исполняться по-разному, но предъявляемый человеку результат должен быть семантически одинаков.

В самой развитой форме в определение абстрактного типа данных входят следующие четыре части:

1. внешность, содержащая имя определяемого типа, имена операций с указанием типов их аргументов и значений;

2. абстрактное описание операций и объектов, с которыми они работают, средствами некоторого языка спецификации;

3. конкретное описание этих же операций и объектов средствами «обычного» или «известного» языка программирования;

4. описание связи между пунктами (2), (3), объясняющее: в каком смысле часть (3) корректно представляет часть (2).

Сопоставляя данное определение с уже знакомыми понятиями теории и алгебры, нетрудно видеть, что части (1) и (2) задают некоторую теорию, а части (3) и (4) – конкретную алгебру этой теории. Таким образом, поскольку имеет место задание конкретной алгебры с конкретными носителями, здесь идет речь о вполне конкретном типе данной теории.

Основное пожелание к абстрактному типу – независимость от реализации. Абстракция в программировании определяется как «отдельная программная конструкция, использование которой связано с отвлечением от деталей ее реализации». Принцип абстракции дает программисту возможность работать с программной конструкцией, зная только синтаксис и семантику ее операций и не вдаваясь в детали реализации. Это в свою очередь позволяет определить структуру программного модуля таким образом, что конкретная реализация модуля скрывается от пользователя и может быть изменена, если статистика работы с модулем покажет недостаточную эффективность его реализации. При этом программист не должен ощущать какие-либо изменения в логическом построении типа данных. Рассмотренное различие между абстрактными и конкретными типами данных побуждает связать понятия абстрактного типа данных с понятиями теории, а конкретного типа данных – с понятиями алгебры. Алгебры данной теории, выбираемые для построения конкретных типов данных, будем называть моделями абстрактного типа данных.