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

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

Жанры

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

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

Шрифт:

Неявность также предполагает открытость определений: всегда можно добавить новые свойства АТД или класса. Основным механизмом для выполнения таких расширений без разрушения уже существующего первоначального определения является наследование.

Этот "неявный" подход имеет далеко идущие последствия. В пункте "дополнительные темы" в конце этой лекции помещены еще некоторые комментарии о неявности.

Частичные функции

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

это имеет место для функций remove и item: нельзя удалить элемент из пустого стека, и у пустого стека нет верхнего элемента.

Решение этой проблемы, использованное в приведенной выше спецификации, состоит в том, чтобы определить эти функции как частичные. Функция из исходного множества X в результирующее множество Y является частичной, если она определена не для всех элементов X. Функция, не являющаяся частичной, называется полной. Простым примером частичной функции в обычной математике является функция обращения действительных чисел inv, значение которой на действительном числе x равно

inv(x)= 1/x.

Поскольку inv не определена при x = 0, мы можем определить ее как частичную функцию на множестве R всех действительных чисел:

Inv: R R

Чтобы указать, что функция частичная, используется перечеркнутая стрелка , а обычная стрелка будет означать, что функция заведомо полная.

Областью (определения) частичной функции типа X Y является подмножество тех элементов X, для которых эта функция имеет некоторое значение. В нашем примере областью функции inv является R - {0}, т.е. множество действительных чисел, отличных от 0.

В спецификации АТД STACK эти идеи использованы для стеков при объявлении remove и item как частичных функций в разделе ФУНКЦИИ - это указано с помощью перечеркнутых стрелок в их сигнатуре. При этом возникает новая проблема, обсуждаемая в следующем пункте: как задавать области таких функций?

В некоторых случаях функцию put тоже желательно описывать как частичную, например, это требуется в таких реализациях как МАССИВ_ВВЕРХ и МАССИВ_ВНИЗ, которые поддерживают выполнение лишь конечного числа подряд идущих операций put для каждого заданного стека. Это на самом деле полезное упражнение - приспособить спецификацию STACK к тому, чтобы она описывала ограниченные стеки конечного объема, поскольку в приведенном выше виде она не содержит никаких ограничений на размеры стеков.

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

Предусловия

Частичные функции являются неустранимым фактом процесса проектирования ПО, отражающим очевидное

наблюдение: не каждая операция применима ко всем объектам. Но они также являются и потенциальным источником ошибок: если функция f из X в Y является частичной, то нельзя быть уверенным в том, что выражение f(e) имеет смысл, даже если e принадлежит X– требуется гарантировать, что это значение принадлежит области f.

Для этого всякая спецификация АТД, содержащая частичные функции, должна задавать их области. В этом и состоит роль раздела ПРЕДУСЛОВИЯ (PRECONDITIONS). Для АТД STACK этот раздел выглядит так:

Предусловия (preconditions)

[x]. remove (s: STACK [G]) require not empty (s)

[x]. item (s: STACK [G]) require not empty (s)

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

Булевское выражение, которое определяет область функции, называется предусловием соответствующей частичной функции. В нашем случае предусловия обеих функций remove и item утверждают, что стек должен быть непустым. Перед "требует" помещается имя функции с именами ее аргументов (в примере для аргумента-стека использовано s), так что предусловие может ссылаться на эти аргументы.

BOOLEAN такая, что ch(x) истинна, если x принадлежит A, и ложна в противном случае.

С точки зрения математики предусловие функции f - это характеристическая функция области f. Характеристической функцией подмножества Aмножества X называется полная функция ch: X

Полная спецификация

Раздел ПРЕДУСЛОВИЯ (PRECONDITIONS) завершает простую спецификацию абстрактного типа данных STACK. Для удобства ссылок полезно собрать вместе разные компоненты спецификации, приведенные выше. Вот полная спецификация.

Спецификация стеков как АТД

ТИПЫ (TYPES)

[x]. STACK [G]

ФУНКЦИИ (FUNCTIONS)

[x]. put: STACK [G] × G STACK [G]

[x]. remove: STACK [G] STACK [G]

[x]. item: STACK [G] G

[x]. empty: STACK [G] BOOLEAN

[x]. new: STACK [G]

АКСИОМЫ (AXIOMS)

Для всех 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))

ПРЕДУСЛОВИЯ (PRECONDITIONS)

[x]. remove (s: STACK [G]) require not empty (s)

[x]. item (s: STACK [G]) require not empty (s)

Ничего кроме правды

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

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

Минин Станислав
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
рейтинг книги
Ведунские хлопоты