Абстрактные типы данных (АТД)



         

Альтернативы частичным функциям


Один из технических приемов, используемый в этой лекции, мог вызвать удивление, - применение частичных функций. Он связан с неустранимой проблемой применения в некоторой спецификации не всюду определенных операций. Но являются ли частичные функции лучшим решением этой проблемы?

Конечно, это не единственно возможное решение. Другим способом, который приходит на ум и действительно используется в некоторых работах по АТД, является превращение частичной функции во всюду определенную за счет введения специального значения "ошибка" для случаев применения функции к неподходящим аргументам.

Каждый тип T дополняется значением "ошибка". Обозначим его через wT . Тогда для всякой функции

f сигнатура

f: ... Типы входов ... → T

определяет, что всякое применение f к объекту, для которого соответствующее вычисление не может быть выполнено, выдаст значение

wT.

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

Предположим, например, что рассматриваются стеки целых чисел - экземпляры типа STACK [INTEGER], где INTEGER - это АТД, экземпляры которого - целые числа. Хотя для нашего примера не требуется полностью выписывать спецификацию INTEGER, этот АТД должен моделировать основные операции (сложение, вычитание, "меньше чем" и т. п.), определенные на математическом множестве целых чисел. Аксиомы этого АТД должны выражать обычные свойства целых чисел. Вот одно из таких типичных свойств: для всякого целого n:

[Z1] n + 1 ≠ n

Пусть теперь n будет результатом запроса верхнего элемента пустого стека, т. е. значением выражения item (new), где new - это пустой стек целых чисел. При этом запросе n должно получить специальное значение wINTEGER . Что же тогда должно быть значением выражения

n+1? Если у нас в распоряжении имеются в качестве значений только обычные целые числа и wINTEGER , то в качестве ответа мы вынуждены выбрать wINTEGER:




Содержание  Назад  Вперед