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

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

Жанры

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

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

Шрифт:

square_plus_one: R R

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

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

Спецификации абстрактных типов данных используют именно это понятие. Например, операция put определяется как

put: STACK [G] × G STACK [G]

и означает, что put

будет брать два аргумента: STACK экземпляров типа G и экземпляр типа G и возвращать в качестве результата новый STACK [G]. (Более формально, множеством определения функции put является множество STACK [G] _ G, являющееся декартовым произведением множеств STACK [G] и G, т.е. множеством пар <s, x>, в которых первый элемент s принадлежит STACK [G] , а второй элемент x принадлежит G.) Вот рисунок, иллюстрирующий это:

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

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

Из нашего обсуждения следуют роли операций, моделируемых каждой из функций спецификации STACK:

[x]. Функция put возвращает новое состояние стека с одним новым элементом, помещенным на его вершину. Рисунок на предыдущей странице иллюстрирует операцию put(s, x), выполняемую над стеком s и элементом x.

[x]. Функция remove возвращает новое состояние стека с вытолкнутым верхним элементом, если таковой был. Как и put, эта функция при проектировании и реализации должна превращаться в команду (операцию, изменяющую объект, обычно реализуемую как процедура). Мы увидим далее, как учесть возможность пустого стека, с вершины которого нечего удалять.

[x]. Функция item возвращает верхний элемент стека, если таковой имеется.

[x]. Функция empty выявляет пустоту стека, ее результатом является логическое значение (истина или ложь). Предполагается, что АТД BOOLEAN, задающий логические значения, определен отдельно.

[x]. Функция new создает пустой стек.

В разделе ФУНКЦИИ эти функции определяются не полностью, вводятся только их сигнатуры– списки типов их аргументов и результата. Сигнатура функции put

STACK [G] × G STACK [G]

показывает, что put берет в качестве аргумента пару вида <s,x>, в которой s– экземпляр типа STACK [G],

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

В сигнатуре функций remove и item вместо обычной стрелки используется перечеркнутая стрелка . Это означает, что эти функции применимы не ко всем элементам множества входов. Описание функции new выглядит просто как

new: STACK

без всякой стрелки в сигнатуре. Фактически, это сокращение для записи

new: STACK,

определяющей функцию без аргументов. Здесь аргументы не нужны, поскольку new должна всегда возвращать один и тот же результат - пустой стек. Поэтому для простоты мы убрали здесь стрелку. Результат применения этой функции (т. е. пустой стек) будет записываться new, как сокращение для new, обозначающего результат применения new к пустому списку аргументов.

Категории функций

В начале этой лекции операции над типами были разделены на конструкторы, запросы и команды. В спецификации АТД для нового типа T, например для STACK [G] в нашем примере можно определить эту классификацию более строго. Эта классификация просто проверяет, где по отношению к стрелке расположен в сигнатуре каждой функции тип T:

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

[x]. Функция, в сигнатуре которой T появляется лишь справа от стрелки, например new, является функцией-конструктором. Она моделирует операцию, создающую экземпляры T из экземпляров других типов или вообще не использующую аргументов, например как в случае константного конструктора new.

[x]. Такие функции как item и empty, у которых T появляется только слева от стрелки, являются функциями-запросами. Они моделируют операции, которые устанавливают свойства T, выраженные в терминах экземпляров других типов (в наших примерах - это BOOLEAN и параметр типа G).

[x]. Такие функции как put и remove, у которых T появляется с обеих сторон стрелки, являются функциями-командами. Они моделируют операции, которые по существующим экземплярам T и, возможно, экземплярам других типов выдают новые экземпляры типа T.

Раздел АКСИОМЫ

Мы уже видели, как типы данных (например, STACK) описываются посредством задания списка функций, применимых к их экземплярам. Все, что известно об этих функциях, - это их сигнатуры.

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

Доктор. Заново

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

Неправильный диверсант Забабашкин

Арх Максим
4. Неправильный солдат Забабашкин
Фантастика:
боевая фантастика
попаданцы
альтернативная история
5.00
рейтинг книги
Неправильный диверсант Забабашкин

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

Сапфир Олег
8. Лекарь
Фантастика:
юмористическое фэнтези
аниме
7.00
рейтинг книги
Идеальный мир для Лекаря 8

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

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

Дочь моего друга

Тоцка Тала
2. Айдаровы
Любовные романы:
современные любовные романы
эро литература
5.00
рейтинг книги
Дочь моего друга

Сильнейший ученик. Том 1

Ткачев Андрей Юрьевич
1. Пробуждение крови
Фантастика:
фэнтези
боевая фантастика
аниме
5.00
рейтинг книги
Сильнейший ученик. Том 1

Черный Маг Императора 17

Герда Александр
17. Черный маг императора
Фантастика:
юмористическое фэнтези
попаданцы
аниме
фэнтези
фантастика: прочее
5.00
рейтинг книги
Черный Маг Императора 17

Элита элит

Злотников Роман Валерьевич
1. Элита элит
Фантастика:
боевая фантастика
8.93
рейтинг книги
Элита элит

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

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

Наследник и новый Новосиб

Тарс Элиан
7. Десять Принцев Российской Империи
Фантастика:
городское фэнтези
попаданцы
аниме
5.00
рейтинг книги
Наследник и новый Новосиб

Пробуждение. Пятый пояс

Игнатов Михаил Павлович
15. Путь
Фантастика:
фэнтези
уся
5.00
рейтинг книги
Пробуждение. Пятый пояс

Личник

Валериев Игорь
3. Ермак
Фантастика:
альтернативная история
6.33
рейтинг книги
Личник

В семье не без подвоха

Жукова Юлия Борисовна
3. Замуж с осложнениями
Фантастика:
социально-философская фантастика
космическая фантастика
юмористическое фэнтези
9.36
рейтинг книги
В семье не без подвоха

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

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