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

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

Жанры

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

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

Шрифт:

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

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

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

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

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

Метатель. Книга 7

Тарасов Ник
7. Метатель
Фантастика:
боевая фантастика
попаданцы
постапокалипсис
рпг
фэнтези
фантастика: прочее
5.00
рейтинг книги
Метатель. Книга 7

Вернуть Боярство 3

Мамаев Максим
3. Пепел
Фантастика:
фэнтези
попаданцы
аниме
5.00
рейтинг книги
Вернуть Боярство 3

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

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

Студиозус

Шмаков Алексей Семенович
3. Светлая Тьма
Фантастика:
юмористическое фэнтези
городское фэнтези
аниме
5.00
рейтинг книги
Студиозус

Неправильный лекарь. Том 1

Измайлов Сергей
1. Неправильный лекарь
Фантастика:
городское фэнтези
попаданцы
аниме
фэнтези
5.00
рейтинг книги
Неправильный лекарь. Том 1

Черный дембель. Часть 2

Федин Андрей Анатольевич
2. Черный дембель
Фантастика:
попаданцы
альтернативная история
4.25
рейтинг книги
Черный дембель. Часть 2

Развод с генералом драконов

Солт Елена
Фантастика:
фэнтези
5.00
рейтинг книги
Развод с генералом драконов

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

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

Око василиска

Кас Маркус
2. Артефактор
Фантастика:
городское фэнтези
попаданцы
аниме
5.00
рейтинг книги
Око василиска

Возвышение Меркурия. Книга 15

Кронос Александр
15. Меркурий
Фантастика:
боевая фантастика
попаданцы
аниме
5.00
рейтинг книги
Возвышение Меркурия. Книга 15

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

Винокуров Юрий
23. Кодекс Охотника
Фантастика:
боевая фантастика
попаданцы
5.00
рейтинг книги
Кодекс Охотника. Книга XXIII

Бастард Императора. Том 4

Орлов Андрей Юрьевич
4. Бастард Императора
Фантастика:
попаданцы
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Бастард Императора. Том 4

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

Сапфир Олег
16. Лекарь
Фантастика:
боевая фантастика
юмористическая фантастика
аниме
5.00
рейтинг книги
Идеальный мир для Лекаря 16

Своя правда

Шебалин Дмитрий Васильевич
2. Чужие интересы
Фантастика:
фэнтези
попаданцы
5.00
рейтинг книги
Своя правда