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

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

Жанры

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

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

Шрифт:

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

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

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]. Сами функции также определяются неявно. Вместо явных определений используются аксиомы, задающие свойства этих функций. Здесь тоже ничего не утверждается о полноте: когда вы, в конце концов, дойдете до реализации этих функций, они приобретут дополнительные свойства.

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

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

Сумеречный Стрелок 10

Карелин Сергей Витальевич
10. Сумеречный стрелок
Фантастика:
рпг
аниме
фэнтези
5.00
рейтинг книги
Сумеречный Стрелок 10

Газлайтер. Том 15

Володин Григорий Григорьевич
15. История Телепата
Фантастика:
боевая фантастика
попаданцы
5.00
рейтинг книги
Газлайтер. Том 15

70 Рублей

Кожевников Павел
1. 70 Рублей
Фантастика:
фэнтези
боевая фантастика
попаданцы
постапокалипсис
6.00
рейтинг книги
70 Рублей

Как я строил магическую империю 2

Зубов Константин
2. Как я строил магическую империю
Фантастика:
попаданцы
аниме
5.00
рейтинг книги
Как я строил магическую империю 2

Лэрн. На улицах

Кронос Александр
1. Лэрн
Фантастика:
фэнтези
5.40
рейтинг книги
Лэрн. На улицах

Долг

Кораблев Родион
7. Другая сторона
Фантастика:
боевая фантастика
5.56
рейтинг книги
Долг

Истребители. Трилогия

Поселягин Владимир Геннадьевич
Фантастика:
альтернативная история
7.30
рейтинг книги
Истребители. Трилогия

Младший сын князя. Том 2

Ткачев Андрей Юрьевич
2. Аналитик
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Младший сын князя. Том 2

Боярышня Евдокия 4

Меллер Юлия Викторовна
4. Боярышня
Фантастика:
альтернативная история
фэнтези
5.00
рейтинг книги
Боярышня Евдокия 4

Отверженный. Дилогия

Опсокополос Алексис
Отверженный
Фантастика:
фэнтези
7.51
рейтинг книги
Отверженный. Дилогия

Жена на четверых

Кожина Ксения
Любовные романы:
любовно-фантастические романы
эро литература
5.60
рейтинг книги
Жена на четверых

Лидер с планеты Земля

Тимофеев Владимир
2. Потерявшийся
Фантастика:
боевая фантастика
космическая фантастика
6.00
рейтинг книги
Лидер с планеты Земля

Дракон с подарком

Суббота Светлана
3. Королевская академия Драко
Любовные романы:
любовно-фантастические романы
6.62
рейтинг книги
Дракон с подарком

Вперед в прошлое 3

Ратманов Денис
3. Вперёд в прошлое
Фантастика:
попаданцы
альтернативная история
5.00
рейтинг книги
Вперед в прошлое 3