"Адское" программирование Ada-95 -Компилятор GNAT



              

Абстракция стека



Абстракция стека

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

package Stacks is Max : constant := 10; subtype Count is Integer range .Max; subtype Index is range .Max; type List is array(Index) of Integer; type Stack is record Values : List; Top : Count; end record; Overflow : exception; Underflow : exception; procedure Push(Item : in out Stack; Value : in Integer); procedure Pop(Item : in out Stack; Value : out Integer); function Full(Item : Stack) return Boolean; function Empty(Item : Stack) return Boolean; -- возвращает пустой проинициализированный стек function Init return Stack;end Stacks;

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

package Stacks is type Stack is private; -- неполное описание типа Stack. -- это делает информацию о деталях реализации недоступной. Overflow : exception; Underflow : exception; procedure Push(Item : in out Stack; Value : in Integer); procedure Pop(Item : in out Stack; Value : out Integer); function Full(Item : Stack) return Boolean; function Empty(Item : Stack) return Boolean; -- возвращает пустой проинициализированный стек function Init return Stack;private -- полное описание типа, вместе с другими приватными деталями. Max : constant := 10; subtype Count is Integer range .Max; subtype Index is range .Max; type List is array(Index) of Integer; type Stack is record Values : List; Top : Count; end record; end Stacks;

Следует заметить, что хотя программист использующий такую абстракцию, имеет возможность увидеть все детали реализации (при наличии исходных текстов кода), он не может написать свою собственную программу, которая будет использовать эту информацию.Также очевидно, что такое разделение вынуждает лучше понять, что для абстракции важно, а что нет.

В качестве альтернативы, можно изменить приватную секцию в соответствии с реализацией стека на связанном списке:

package Stacks is type Stack is private; -- неполное описание типа Stack. -- это делает информацию о деталях реализации недоступной. Overflow : exception; Underflow : exception; procedure Push(Item : in out Stack; Value : in Integer); procedure Pop(Item : in out Stack; Value : out Integer); function Full(Item : Stack) return Boolean; function Empty(Item : Stack) return Boolean; -- возвращает пустой проинициализированный стек function Init return Stack;private type Stack; type Ptr is access Stack; type Stack is record Value : Integer; Next : Ptr; end record; end Stacks;

Программа-клиент может использовать оба варианта пакета следующим образом:

with Stacks; use Stacks;procedure Demo is A : Stack := Init; B : Stack := Init; Temp : Integer;begin for I in 0 loop Push(A, I); end loop; while not Empty(A) loop Pop(A, Temp); Push(B, Temp); end loop; end Demo;

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

Рассмотрим еще один пример использования рассмотренной абстракции стека:

with Stacks; use Stacks;procedure Not_Quite_Right is A, B : Stackbegin Push(A, 1); Push(A, 2); B := A; end Not_Quite_Right;

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









Содержание  Назад  Вперед