1.4. Исключительные ситуации
|
|
Процедурная абстракция есть отображение аргументов в результаты с возможной модификацией некоторых аргументов. Аргументы принадлежат области определения процедуры, а результаты - области изменения..
Часто процедура имеет смысл только для аргументов, принадлежащих подмножеству ее области определения. Например, операция choose для наборов целых чисел имеет смысл, только если ее аргумент - не пустой набор. В приведенной выше спецификации типа данных intset (рис.1.9) эта ситуация учитывалась использованием процедуры choose, заданной на некоторой области определения.
------------------------------------------------------¬
¦ = proc (s: intset) returns (int) ¦
¦ requires набор s не пуст ¦
¦ effects Возвращает произвольный элемент s ¦
L------------------------------------------------------
Но в этом случае, реализуя операцию choose, игнорируется случай пустого множества. Такие процедуры приводят к неустойчивым программам.
Устойчивая программа - это такая программа, которая ведет себя корректно даже в случае ошибки. То есть, она должна вести себя определенным, предсказуемым образом.
Метод, который гарантирует устойчивость, заключается в использовании процедур, заданных на всей области определения. Если процедура неспособна осуществить свою функцию для некоторых аргументов, она должна оповестить обратившегося к ней о возникшем затруднении. Таким образом, разрешение ситуации передается обратившемуся к процедуре, который может быть в состоянии что-то предпринять или избежать последствий ошибки.
Проверка входных аргументов на принадлежность допустимому подмножеству области определения требует затрат времени и очень часто ее используют только при отладке ПО и отключают в сдаваемом программном продукте. Однако это не самое лучшее решение. Лучшим является использование защитного программирования, когда программы сами защищают себя от ошибок. Защитное программирование облегчает отладку программ.
При эксплуатации ПО оно еще более ценно, так как исключает возможность того, что незначительная ошибка приведет к серьезной проблеме.
Проверка на нелегальные аргументы может быть отключена только при абсолютной уверенности в невозможности ошибки или если проверка приводит к крайней неэффективности.
Чтобы специфицировать процедуры, которые вызывают исключительные ситуации, добавим в спецификацию предложение signals. Это предложение - часть заголовка. Оно следует за предложением returns. Если исключительных ситуаций не имеется, оно может быть опущено.
Как и раньше, секция effects должна определять поведение процедуры для всех фактических аргументов, отвечающих предложению requires.
Так как это поведение включает в себя исключительные ситуации, секция effects должна определять, что приводит к вызову каждой исключительной ситуации и что делает процедура в каждом таком случае. Завершение процедуры оповещением об исключительной ситуации - это один из нормальных режимов работы этой процедуры.
С учетом всего вышесказанного, спецификация процедуры choose будет иметь вид:
-------------------------------------------------------------------¬
¦ hoose = proc (s: intset) returns (int) signals (empty) ¦
¦ effects Если size(s)=0, то сигнализировать об исключитель-¦
¦ ной ситуации empty, иначе возвратить произвольный ¦
¦ элемент s. ¦
L-------------------------------------------------------------------
При реализации процедуры с исключительными ситуациями работа программиста заключается в том, чтобы обеспечить соответствующую спецификации работу процедуры.
Если спецификация включает в себя исключительные ситуации, программа должна в нужное время сигнализировать о соответствующих исключительных ситуациях и передавать определенные в спецификации значения. Для выполнения этой задачи, программа, возможно, должна будет обрабатывать исключительные ситуации, возникающие в процедурах, к которым она обращается.
Исключительные ситуации могут обрабатываться двумя различными способами. Иногда исключительная ситуация распространяется до другого уровня, то есть вызывающая процедура также завершает работу сигнализацией об исключительной ситуации с тем же самым или другим значением.
Перед распространением исключительной ситуации вызывающая процедура может осуществить некоторую локальную обработку. Такая обработка иногда необходима для достижения соответствия со спецификацией вызывающей процедуры. Например, операция типа данных должна гарантировать, что объекты перед ее завершением будут удовлетворять инварианту представления.
Другой способ заключается в том, что вызывающая процедура маскирует исключительную ситуацию, то есть обрабатывает ее сама.
Рассмотрим в качестве примера спецификацию упорядоченных списков, в операциях которой удалены предложения requires и добавлены исключительные ситуации в операциях addel, remel и least. Полученная в результате спецификация (рис.1.14) будет обладать большей устойчивостью по сравнению с исходной (рис.1.13).
-------------------------------------------------------------------¬
¦olist = data type [t:type] is create,addel,remel,is_in,empty,least¦
¦ ¦
¦Requires - t имеет операции ¦
¦ equal,lt:proctype(t,t) returns (bool), ¦
¦ которые определяют упорядочение t ¦
¦ ¦
¦Описание ¦
¦ ¦
¦Упорядоченные списки olist - изменяемые списки элементов. Операции¦
¦addel и remel модифицируют списки. Каждый элемент упорядоченного ¦
¦списка отличается от остальных (как определяется t.equal). Опера- ¦
¦ция least возвращает наименьший элемент olist (как определяется ¦
¦t.lt) ¦
¦ ¦
¦Операции ¦
¦ ¦
¦ create = proc () returns (olist [t]) ¦
¦ effects возвращает новый, пустой список ¦
¦ ¦
¦ addel = proc (s: olist[t], x:t) signals(dupl) ¦
¦ modifies s ¦
¦ effects если x принадлежит s, сигнализирует об исключи- ¦
¦ тельной ситуации dupl, иначе вставляет x в s ¦
¦ ¦
¦ remel = proc (s: olist[t], x:t) signals(not_in) ¦
¦ modifies s ¦
¦ effects если x не принадлежит s, сигнализирует об исключи¦
¦ тельной ситуации not_in,иначе удаляет x из s ¦
¦ ¦
¦ is_in = proc (s: olist[t], x:t) returns (bool) ¦
¦ effects возвращает значение true, если s содержит элемент ¦
¦ равный x (используется t.equal), в противном слу- ¦
¦ чае возвращает значение false ¦
¦ ¦
¦ empty = proc (s: olist[t]) returns (bool) ¦
¦ effects возвращает значение true, если s не содержит эле- ¦
¦ ментов, и значение false - в противном случае ¦
¦ ¦
¦ least = proc (s: olist[t]) returns(t) signals(empty) ¦
¦ effects если s пуст, сигнализирует об исключительной ситуа¦
¦ ции empty, иначе возвращает элемент e из s, такой,¦
¦ что в s не существует элемента, меньшего e(как оп-¦
¦ ределяется t.lt) ¦
¦ ¦
¦end olist ¦
L-------------------------------------------------------------------
Рис.1.14.Спецификация параметризованной абстракции данных для упорядоченных списков.
Исключительные ситуации следует использовать для устранения большинства ограничений, перечисленных в предложениях requires. Эти предложения следует оставлять только из соображений эффективности или если контекст использования настолько ограничен, что можно быть уверенным, что ограничения удовлетворяются.
Cледует остановиться на взаимосвязи модификаций аргументов с завершением работы процедуры выходом на исключительную ситуацию. Секция modifies спецификации указывает, что аргумент может модифицироваться, но не говорит о том, когда это происходит. Если имеются исключительные ситуации, то обычно модификации происходят только для каких-нибудь из них. Точное описание происходящего должно быть приведено в секции effects. Модификации должны быть описаны явно в каждом случае, в котором они совершаются; если не описано никаких модификаций, это означает, что они не совершаются вообще. Например, рассмотрим процедуру
-------------------------------------------------------------------¬
¦ ¦
¦ addel = proc (s: olist[t], x:t) signals(dupl) ¦
¦ modifies s ¦
¦ effects если x принадлежит s, сигнализирует об исключи- ¦
¦ тельной ситуации dupl, иначе вставляет x в s ¦
¦ ¦
L-------------------------------------------------------------------
Так как для случая, когда процедура addel сигнализирует об исключительной ситуации dupl, не описано никаких модификаций, s модифицируется только при обычном возврате из процедуры addel.
Исключительная ситуация failure является неявной исключительной ситуацией каждой процедуры, однако она не упоминается ни в каких спецификациях. Спецификация описывает поведение процедуры при ее работе и для случая, когда аргументы удовлетворяют предложению requires. Исключительная ситуация failure возникает тогда, когда в работе процедуры происходит сбой и она больше не отвечает своей спецификации или когда заданы неверные аргументы.
Обычно исключительная ситуация failure не может быть обработана программой. Эта ситуация означает либо ошибку в математическом обеспечении, либо сбой в аппаратной части.
1.5. Абстракции итерации
Для работы с набором данных требуется некоторый общий метод итерации, который удобен и эффективен и который сохраняет абстракцию через спецификацию. Итератор обеспечивает эти требования. Он вызывается как процедура, но вместо окончания с выдачей всех результатов имеет много результатов, которые каждый раз выдает по одному. Полученные элементы могут использоваться в других модулях, которые задают действия, выполняемые для каждого такого элемента. Использующий итератор модуль будет содержать некоторую структуру организации цикла. Каждый раз, когда итератор выдает некоторый элемент, над этим элементом выполняется тело цикла. Затем управление возвращается в итератор, так что он может выдавать следующий элемент. Следует отметить разделение обязанностей в такой форме взаимодействия. Итератор ответственен за получение элемента, а модуль, содержащий цикл, определяет то действие, которое будет над ним выполняться. Итераторы являются некоторой обобщенной формой методов итерации, имеющихся в большинстве языков программирования.
Как и другие абстракции, итераторы должны быть определены через спецификации. Форма спецификации итерации аналогична форме для процедуры. Заголовок имеет вид:
iname = iter(список входных данных) yields(список выходных данных)
signals (сообщение об исключительной ситуации)
Ключевое слово iter используется для обозначения абстракции итератора. Итератор может совсем не выдавать объектов на каждой итерации или выдать несколько объектов. Число и тип этих объектов описываются в предложении yields. Итератор может не выдавать никаких результатов, когда он заканчивается нормально, но он может заканчиваться по исключительной ситуации с именем и результатами, указанными в предложении
signals. Например,
-------------------------------------------------------------------¬
¦ elements = iter (s: intset) yields (int) ¦
¦ requires s не модифицируется в теле цикла ¦
¦ effects Выдает элементы s в некотором произвольном по- ¦
¦ рядке, причем каждый элемент только один раз. ¦
L-------------------------------------------------------------------
Эта операция вполне правдоподобна для набора intset. Операция elements не имеет исключительных ситуаций. Если ей будет задан в качестве аргумента пустой набор intset, она просто заканчивается, не выдавая ни одного элемента. Характерно, что использование итераторов исключает проблемы, связанные с заданием некоторых аргументов (таких, как пустой набор intset) для соответствующих процедур (таких, как процедура choose).
Требование о том, чтобы набор s не модифицировался при использовании цикла, является ограничением, типичным для итераторов.
Таким образом, рассмотрена проблема полноты типов данных, которые являются совокупностью объектов. Поскольку совокупность используется для выполнения некоторого действия над ее элементами, необходим некоторый способ доступа ко всем элементам. Этот способ должен быть эффективным в смысле времени и пространства, удобным для использования и не должен разрушать данную совокупность. Кроме того, он должен обеспечивать абстракцию через спецификацию.
Итераторы являются механизмом, решающим эту задачу. Поскольку они выдают объекты по одному, не требуется дополнительного пространства для хранения объектов, и процедура может быть остановлена, когда нужный объект будет найден. Метод выдачи объектов зависит от знания представления этих объектов, но использующие его программы защищены от этого знания.
Итераторы полезны сами по себе, однако их основным применением являются операции над типами данных.
1.6. Использование абстракций в языке Паскаль
В языке Паскаль непосредственно не обеспечиваются ни абстракции данных или итераций, ни абстракция через параметризацию. Тем не менее при проектировании программ, которые будут реализовываться на языке Паскаль, все же можно с успехом применять эти абстракции. Для этого при проектировании надо использовать приемущества тех методов построения программ, которые хорошо обеспечивает язык Паскаль, и избежать таких методов, которые черезмерно трудно реализовывать.
Рассмотрим по очереди абстракции процедур, данных и итераций, а затем приведем пример их использования.
1.6.1. Абстракции процедур и функций
1. В общем случае нецелесообразно проектировать абстракции, которые зависят от глобальных переменных, поскольку тогда знание такой абстракции бкдет зависеть от того контекста, в котором она находится.
2. Для обработки исключительных ситуаций в программах на языке Паскаль зададим некоторую процедуру failure. Эта процедура помещается в начало программы, и к ней может обращаться любая операция в этой программе.
--------------------------------------------------------------------¬
¦ procedure failure (s:error_msg) ¦
¦ modifies выходной поток на основном устройстве вывода ¦
¦ effects печатает следующую строку на основном устройстве ¦
¦ вывода: "Сбой. Программа окончилась из-за: +S", ¦
¦ а затем выполнение программы останавливается ¦
L--------------------------------------------------------------------
1.6.2. Абстракции данных
В общем случае эти абстракции могут быть основаны на объектах, запоминаемых в стеке, и на объектах, хранящихся в неупорядоченном массиве. Рассмотрим второй случай, который дает большую гибкость за счет некоторой неэффективности.
Зададим спецификацию абстракции данных для очереди целых чисел.
--------------------------------------------------------------------¬
¦ ntqueue = data type is q_new, q_isempty, q_append, q_remfirst ¦
¦ ¦
¦ Описание ¦
¦ Типы данных intqueue используются для хранения значений типа ¦
¦ целого числа. Элементы могут извлекаться из очереди или удалять- ¦
¦ ся из нее только по методу FIFO (First Input-First Output) ¦
¦ Операции ¦
¦ function q_new:intqueue ¦
¦ effects Возвращает новую очередь без элементов в ней ¦
¦ function q_isempty (q:intqueue): boolean ¦
¦ effects Возвращает значение true, если в очереди q нет ¦
¦ элементов, в противном случае возвращает значе- ¦
¦ ние false ¦
¦ procedure q_append (q:intqueue; e:integer) ¦
¦ modifies q ¦
¦ effects Добавляет элемент e в конец очереди q ¦
¦ function q_remfirst (q:intqueue): integer ¦
¦ requires чтобы очередь q не была пустой ¦
¦ modifies q ¦
¦ effects Возвращает элемент из начала очереди q и ¦
¦ удаляет этот элемент из очереди q ¦
¦ end intqueue ¦
L--------------------------------------------------------------------
Рис.1.15.Спецификация абстракции данных для очереди целых чисел.
Решение хранить абстрактные объекты в неупорядоченном массиве продиктовано тем, что надо реализовать типы, чьи объеты изменяют свой размер по мере работы программы. Реализация такого абстрактного типа данных использует указатель на неупорядоченный массив. То есть при передаче в процедуру некоторого абстрактного объекта всегда передается только ссылка. При модификации абстрактного объекта, модифицируется тот объект, на который указывает ссылка, а не сама ссылка. Таким образом, абстрактные объекты введенного типа никогда не передаются, как параметры типа var. Кроме того, представление объекта некоторой ссылкой гарантирует то, что абстрактные объекты могут быть возвращены при помощи функций.
В результате тип intqueue будет иметь следующее представление
type
intqueue = ^intqueue_rep;
intqueue_rep = ^intqueue_elem;
intqueue_elem = record
var : integer;
next : intqueue_rep;
end;
Теперь для объявления переменных некоторого абстрактного типа достаточно указать
var q:intqueue;
Смысл этого объявления состоит в том, что в стеке отводится пространство для некоторой неинициализированной переменной q. Когда очередь q объявлена, выделяется только указатель, а при выходе из процедуры, освобождается только этот указатель.
Чтобы гарантировать правильное освобождение пространства, для каждого типа должна существовать некоторая дополнительная операция, называемая destroy.
--------------------------------------------------------------------¬
¦ procedure q_desstroy (q:intqueue) ¦
¦ modifies q ¦
¦ effects В неупорядоченном массиве освобождается вся ¦
¦ память, занимаемая очередью q ¦
L--------------------------------------------------------------------
По соглашению нельзя освобождать абстрактные объекты непосредственно. Вместо этого необходимо обращение к операции destroy для типа данного объекта. На рис.1.16 приведена реализация типа данных intqueue, включая и операцию destroy.
--------------------------------------------------------------------¬
¦ Type IntQueue = ^IntQueue_Rep; ¦
¦ IntQueue_Rep = ^IntQueue_Elem; ¦
¦ IntQueue_Elem = Record ¦
¦ i : Word; ¦
¦ Next : IntQueue_Rep; ¦
¦ End; ¦
¦ ¦
¦ Function q_new:IntQueue; ¦
¦ Function q_isempty(q:IntQueue):Bollean; ¦
¦ Procedure q_append(q:IntQueue; e:Word); ¦
¦ Function q_remfirst(q:Intqueue):Word; ¦
¦ Procedure failure(s:String); ¦
¦ ¦
¦ Function q_new:IntQueue; ¦
¦ Var q:IntQueue; ¦
¦ Begin ¦
¦ new(q); ¦
¦ q^:=nil; ¦
¦ q_new:=q; ¦
¦ End; ¦
¦ ¦
¦ Function q_isempty(q:IntQueue):Bollean; ¦
¦ Var buf:bollean; ¦
¦ Begin ¦
¦ buf:=(q^=nil); ¦
¦ q_isempty:=buf; ¦
¦ End; ¦
¦ ¦
¦ Procedure q_append(q:IntQueue; e:Word); ¦
¦ Var last,elem:IntQueue_Rep; ¦
¦ Begin ¦
¦ new(elem); ¦
¦ elem^.i:=e; ¦
¦ elem^.next:=nil; ¦
¦ if q_isempty(q) then q^:=elem ¦
¦ else begin ¦
¦ last:=q^; ¦
¦ while last^.next <> nil do ¦
¦ last:=last^.next; ¦
¦ last^.next:=elem; ¦
¦ end; ¦
¦ End; ¦
¦ ¦
¦ Function q_remfirst(q:IntQueue):Word; ¦
¦ Var oldq:IntQueue_Rep; ¦
¦ Begin ¦
¦ if q_isempty(q) then failure (' DC=:F88 q_remfirst ¦
¦ >1@0B8;8AL A ?CAB>9 >G5@54LN') ¦
¦ else begin ¦
¦ q_remfirst:=q^^.i; ¦
¦ oldq:=q^; ¦
¦ q^:=q^^.next; ¦
¦ dispose(oldq); ¦
¦ end; ¦
¦ End; L--------------------------------------------------------------------
Рис.1.16.Реализация операций типа данных intquaeue.
1.6.3. Абстракция итерации
Для реализации итератора создадим тип некоторого специального вида, называемый генератором. Генераторы имитируют работу итераторов. У каждого генератора есть три функции и одна процедура. Эти три функции создают объект генератора, получают следующий элемент и проверяют, все ли элементы были выданы. Процедура уничтожает объект генератора.
Например, для очереди целых чисел создадим генератор qelems (рис.1.17). Функция qelems_create выполняет некоторую работу по инициализации, то есть возвращает некоторый объект с типом qelems. Вторая функция qelems_next выдает каждый раз один элемент при обращении к ней и модифицирует объект генератора qelems, чтобы указать, что этот элемент уже был выдан. Последняя функция qelems_done используется для определения того, были ли выданы все элементы. Процедура qelems_destroy освобождает пространство, которое было выделено при работе функцией qelems_create и qelems_next.
--------------------------------------------------------------------¬
¦ qelems = generator type is qelems_create, qelems_done, ¦
¦ qelems_next, qelems_destroy ¦
¦ Описание ¦
¦ Генераторы qelems используются для выполнения итераций по ¦
¦ элементам очередей целых чисел IntQueue. ¦
¦ Операции ¦
¦ function qelems_create (q:IntQueue): qelems ¦
¦ effects Возвращается некоторый объект qelems, который ¦
¦ может быть использован для выдачи всех элементов ¦
¦ в очереди q ¦
¦ function qelems_done (qi:qelems): boolean ¦
¦ requires Чтобы очередь целых чисел intqueue, используемуя ¦
¦ для создания элементов qi, не модифицировалась ¦
¦ после того, как создан элемент qi ¦
¦ effects Возвращается значение true, если все элементы в ¦
¦ очереди целых чисел intqueue, используемой для ¦
¦ создания элементов qi, были "выданы" после того, ¦
¦ как был создан элемент qi. В противном случае ¦
¦ возвращается значение false ¦
¦ function qelems_next (qi:qelems): word ¦
¦ requires Чтобы очередь целых чисел intqueue, используемуя ¦
¦ для создания элементов qi, не модифицировалась ¦
¦ после того, как создан элемент qi, и чтобы сущест-¦
¦ вовал некоторый элемент в очереди целых чисел ¦
¦ intqueue, который еще не был выдан ¦
¦ modifies qi ¦
¦ effects Возвращается некоторый элемент в очереди чисел ¦
¦ intqueue, используемой для создания элемента qi. ¦
¦ Этот элемент очереди не был выдан после того, как ¦
¦ был создан элемент qi. Элемент qi модифицируется ¦
¦ для того, чтобы отметить тот факт, что данный ¦
¦ элемент был "выдан" ¦
¦ procedure qelems_destroy (qi:qelems) ¦
¦ modifies qi ¦
¦ effects Освобождается вся память из неупорядоченного ¦
¦ массива, занимаемая элементом qi ¦
¦ end qelems ¦
L--------------------------------------------------------------------
Рис.1.17.Спецификация типа данных генератор для очередей.
Реализация операций над типом данных qelems, совместная с реализа цией очереди целых чисел intqueue, имеет вид:--------------------------------------------------------------------¬
¦ type ¦
¦ qelems = ^qelems_rep; ¦
¦ qelems_rep = ^intqueue_elem; ¦
¦ function qelems_create (q:intqueue): qelems; ¦
¦ var qi:qelems; ¦
¦ begin ¦
¦ new(qi); ¦
¦ qi^:=q^; ¦
¦ qelems_create:=qi; ¦
¦ end; ¦
¦ function qelems_done (qi:qelems): bollean; ¦
¦ begin ¦
¦ qelems_done:=(qi^=nil); ¦
¦ end; ¦
¦ function qelems_next (qi:qelems): word; ¦
¦ begin ¦
¦ if qi^=nil ¦
¦ then failure('К функции qelems_next обратились ¦
¦ с пустой очередью генератора') ¦
¦ else begin ¦
¦ qelems_next:=qi^^.i; ¦
¦ qi^:=qi^^.next; ¦
¦ end; ¦
¦ end; ¦
¦ procedure qelems_destroy (qi:qelems); ¦
¦ begin ¦
¦ dispose(qi); ¦
¦ end; ¦
L--------------------------------------------------------------------
Рис.1.18.Реализация генератора для типа данных очередь целых чисел intqueue.
В результате этой реализации осуществляется доступ к представлению очереди целых чисел intqueue. Следует отметить, что представление имеет дополнительный уровень косвенности для того, чтобы гарантировать правильность совместимого использования.
Пример суммирования всех членов очереди примет вид:
sum:=0;
qi:=qelems_create(q);
while not (qelems_done(qi)) do
sum:=sum+qelems_next(qi);
qelems_destroy(qi);
