Лекция 10 (Лекции (2009) (Саша Федорова)), страница 2

Modula-2. Абстрактный тип данных соответствует скрытому типу данных в Modula-2. Что это?

Показывать структуру очень плохо. А ели плохо – то мы ее и не будем показывать

DEFINITION MODULA Stacks;

TYPE Stack; //вот так определяется скрытый тип данных

Далее повторяем все заголовки, к примеру:

PROCEDURE PUSH(VAR S: STACK, X: T);

И на Modula-2, и на Оберон пример не совсем полон. Для полноты в начале определения надо импортировать тип Т. Вот так:

DEFINITION MODULA Stacks;

FROM MyTypes IMPORT T; //возможность получить доступ к типу, который описан в другом модуле

TYPE Stack; //вот так определяется скрытый тип данных

Далее повторяем все заголовки, к примеру:

PROCEDURE PUSH(VAR S: STACK, X: T);

……………..

Добавим еще и процедуру разрушения стека:

PROCEDURE Destroy(VAR S: Stack);

END STACKS

В Аде все гибче, а, следовательно, сложнее. В качестве типа Т мы там будем писать родовой модуль стеков (настраиваемый модуль).

Продемонстрировали возможность инкапсуляции. Однако все не так хорошо, как кажется:

• недоступно определение соответствующего типа. Никому

Пусть у нас есть главный модуль:

MODULE Main;

IMPROT stacks;

………..

VAR S: stacks. Stack;

C точки зрения языка Оберон все будет очень просто:

DEFINITION Stacks;

TYPE Stack

RECORD

……….

END;

PROCEDURE PUSH(………..)

END stacks;

В Turbo Pascal:

unit

interface

implementation

//сначала описываем все заголовки, а потом – реализацию.

Замечание (о минимизации затрат на трансляцию – не знаю, надо ли было записывать это)

stdafx.h – модуль проекта, в который рекомендуется помещать все include-ы, которые мы менять не будем.

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

А минимизация затрат на трансляцию очень важна (тут многое, конечно, зависит от скорости трансляции – но в проектах с миллионами строк кода она может занимать несколько суток).

50-100 тысяч строк кода транслируется несколько часов.

Можно как угодно менять реализацию, и перетранслировать проект не надо – нужно только все пересобрать (перекомпоновать).

Как сделать язык программирования так, чтобы такие конструкции были возможны? Для этого надо выбрать стандартный размер и стандартный набор операций. Ограничение: предполагается, что он реализован либо типом INTEGER, либо типом POINTER(и если мы хотим, например, завести стек, то можно использовать для реализации только INTEGER и POINTER:

TYPE STACK = POINTER

To Srack_Rec;

Stack_Rec= RECORD

………………

END

Является ли это нарушением? Нас заставляют работать в пределах АТД (абстрактного типа данных), а он заставляет работать с объектами из динамической памяти (а все объекты у нас и без того в динамической памяти  наверное, несильное ограничение.)

В современных языках программирования разделять таблицу символов и объектный код не стали.

А вот в Аде это разделение присутствует.

В Аде присутствуют:

• приватный тип данных (тип, у которого структура данных скрыта от пользователя)

• ограниченный приватный тип данных

Идея Ады: за счет увеличения расходов на перетрансляцию компилятор знает все.

Общая схема:

package M

………………….

private

………….//компилятор сразу видит всю информацию необходимую для реализации – важно для компилятора и для разработчика

end M;

package stacks is

type Stack is private;

//……повторяем все заголовки

private: //приватная часть

описание всех приватных структур данных

type Stack is record top: integer:=0;

………

end record;

end stacks

Использование:

Use stacks;

: Stack;

push(S, a);

pop(S, b);

Как только мы меняем интерфейс, все надо перекомпилировать заново (ведь в любом модуле могла быть функция из этого интерфейса, которая поменялась) полный rebuild проектаснижается эффективность.

Для приватного типа данных, если он допустим соответствующим определением, допустимы операции:

• присваивания

• сравнения на равенство и неравенство

Язык Ада, таким образом, заставляет пользователя инкапсулировать все типы данных.

Приватный тип данных в Аде – не совсем абстрактный тип данных, т. к. Есть спецификации:

Modula-2:

type T is limited private;

…………………………………

private:

type T;

70-80-е годы – Барбара Лисков разработала теорию абстрактных типов данных.

По виду структуры нельзя сказать, как с ней работать. Для Абстрактного Типа Данных набор операций

• не должен зависеть от реализации

• должен полностью описывать семантику

Абстрактный тип данных – это тип данных, который вводился как набор операций, связанных некоторыми отношениями.

Аксиоматическая теория абстрактного типа данных – теория абстрактного типа данных в смысле математической логики.

Данная теория, к примеру, изучала, как лучше ввести описание сигнатур и соответствующих операций, чтобы по ним было понятно, что это стек.

Доказательное программирование

Началось в 60-е годы Эдсгером Дейкстрой, активно развивалось в 70-80-е годы. В 90-х годах, в связи с появлением объектно-ориентированных языков программирования, было забыто. Однако программирование сверхсложных систем без элементов доказательного программирования, как показала практика, невозможно.