Чтение онлайн

на главную - закладки

Жанры

Основы объектно-ориентированного программирования

Мейер Бертран

Шрифт:

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

Это, конечно, не должно удивлять, поскольку в разделе ФУНКЦИИ сами функции только объявляются (так же, как в программе объявляются переменные), но полностью не определяются. В ранее рассмотренном примере математического определения:

square_plus_one: R R

square_plus_one (x)= x2 + 1 (для
каждого x из R)

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

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

Только чтобы убедиться в том, что мы понимаем, как может выглядеть явное определение, давайте напишем одно такое определение для приведенного ранее представления стека МАССИВ_ВВЕРХ. С точки зрения математики выбор этого представления означает, что экземпляр типа STACK– это пара <count, representation> , где representation– это массив, а count– это число помещенных в стек элементов. Тогда явное определение функции put (для любого экземпляра x типа G) выглядит так:

put (<count, representation>, x)= <count + 1, representation [count+1: x]>

где a [n: v] обозначает массив, полученный из a путем изменения значения элемента с индексом n на v (все остальные элементы не изменяются).

Это определение функции put является просто математической версией реализации операции put, набросок которой в стиле Паскаля приведен вслед за представлением МАССИВ_ВВЕРХ на рисунке с возможными представлениями стеков в начале этой лекции.

Но это не то определение, которое бы нас устроило. "Освободите нас от рабства представлений!" - этот лозунг Фронта Освобождения Объектов и его военного крыла (бригады АТД) является также и нашим. (Отметим, что его политическая ветвь специализируется на тяжбах: класс - действие).

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

Они формулируются в разделе АКСИОМЫ (AXIOMS). Для типа STACK он выглядит следующим образом.

Аксиомы

Для всех x: G, s: STACK [G],

[x]. (A1) item (put (s, x)) = x

[x]. (A2) remove (put (s, x)) = s

[x]. (A3) empty (new)

[x]. (A4) not empty (put (s, x))

Первые

две аксиомы выражают основные свойства стеков (последним пришел - первым ушел) LIFO. Чтобы понять их, предположим, что у нас есть стек s и экземпляр x, и определим s' как результат put(s, x) , т. е. как результат вталкивания x в s. Приспособим один из предыдущих рисунков:

Рис. 6.4. Применение функции put

Здесь аксиома A1, говорит о том, что вершиной s' является x– последний элемент, который мы втолкнули, а аксиома A2 объясняет, что при удалении верхнего элемента s' мы снова получаем тот же стек s, который был до вталкивания x. Эти две аксиомы дают лаконичное описание главного свойства стеков в чисто математических терминах без всякой помощи императивных рассуждений или ссылок на свойства представлений.

Аксиомы A3 и A4 говорят о том, когда стек пуст, а когда - нет: стек, полученный в результате работы конструктора new пустой, а всякий стек, полученный после вталкивания элемента в уже существующий стек (пустой или непустой) не является пустым.

Эти аксиомы, как и остальные, являются предикатами (в смысле логики), выражающими истинность некоторых свойств для всех возможных значений s и x. Некоторые предпочитают рассматривать A3 и A4 в другой эквивалентной форме как определение функции empty индукцией по размеру стеков:

Для всех x: G, s: STACK [G]

A3' · empty (new) = true

A4' · empty (put (s, x)) = false

Две или три вещи, которые мы знаем о стеках

Спецификации АТД являются неявными. Имеются два вида "неявности":

[x]. Метод АТД определяет неявно некоторое множество объектов, задавая применимые к ним функции. Из этого определения никогда не следует, что в нем перечислены все операции; часто, на пути к представлению, будут добавлены и другие.

[x]. Сами функции также определяются неявно. Вместо явных определений используются аксиомы, задающие свойства этих функций. Здесь тоже ничего не утверждается о полноте: когда вы, в конце концов, дойдете до реализации этих функций, они приобретут дополнительные свойства.

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

Поделиться:
Популярные книги

Камень. Книга восьмая

Минин Станислав
8. Камень
Фантастика:
фэнтези
боевая фантастика
7.00
рейтинг книги
Камень. Книга восьмая

Очкарик 2

Афанасьев Семен
2. Очкарик
Фантастика:
фэнтези
альтернативная история
5.00
рейтинг книги
Очкарик 2

Убивать чтобы жить 8

Бор Жорж
8. УЧЖ
Фантастика:
боевая фантастика
космическая фантастика
рпг
5.00
рейтинг книги
Убивать чтобы жить 8

Барон Дубов 6

Карелин Сергей Витальевич
6. Его Дубейшество
Фантастика:
юмористическое фэнтези
аниме
сказочная фантастика
фэнтези
5.00
рейтинг книги
Барон Дубов 6

Отверженный IX: Большой проигрыш

Опсокополос Алексис
9. Отверженный
Фантастика:
попаданцы
альтернативная история
аниме
5.00
рейтинг книги
Отверженный IX: Большой проигрыш

На границе империй. Том 8. Часть 2

INDIGO
13. Фортуна дама переменчивая
Фантастика:
космическая фантастика
попаданцы
5.00
рейтинг книги
На границе империй. Том 8. Часть 2

Тринадцатый XI

NikL
11. Видящий смерть
Фантастика:
попаданцы
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Тринадцатый XI

Доктор 5

Афанасьев Семён
5. Доктор
Фантастика:
фэнтези
альтернативная история
5.00
рейтинг книги
Доктор 5

Законы Рода. Том 10

Андрей Мельник
10. Граф Берестьев
Фантастика:
юмористическая фантастика
аниме
фэнтези
5.00
рейтинг книги
Законы Рода. Том 10

Эволюционер из трущоб. Том 6

Панарин Антон
6. Эволюционер из трущоб
Фантастика:
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Эволюционер из трущоб. Том 6

Барон Дубов 3

Карелин Сергей Витальевич
3. Его Дубейшество
Фантастика:
юмористическое фэнтези
аниме
сказочная фантастика
фэнтези
5.00
рейтинг книги
Барон Дубов 3

Кодекс Охотника. Книга XV

Винокуров Юрий
15. Кодекс Охотника
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Кодекс Охотника. Книга XV

Идеальный мир для Лекаря 27

Сапфир Олег
27. Лекарь
Фантастика:
аниме
фэнтези
5.00
рейтинг книги
Идеальный мир для Лекаря 27

Ведунские хлопоты

Билик Дмитрий Александрович
5. Бедовый
Фантастика:
юмористическое фэнтези
городское фэнтези
мистика
5.00
рейтинг книги
Ведунские хлопоты