Программирование с использованием абстрактных типов данных.
Вступление
В данной статье описывается подход компьютерного представления абстракции. Подход, разработанный при разработке языка для поддержки структурного программирования, также имеет отношение к работе на языках высокого уровня. Цель структурного программирования заключается в повышении надежности и понятности программ.
Высокоуровневый язык пытается представить пользователю абстракции (операции, структуры данных и управляющие структуры), полезные для его области применения. Пользователь может использовать эти абстракции, не беспокоясь о том, как они реализуются — он озабочен только тем, что они делают. Таким образом, пользователь в состоянии игнорировать детали, не имеющие отношение к его области применения, и сосредоточиться на решении проблемы.
Структурное программирование пытается сделать программу «хорошо структурированной». Проблема решается с помощью последовательного разложения. Первый шаг — это написать программу, работающую на абстрактной машине, которая представляет только те объекты и операции, которые идеально подходят для решения проблемы. Некоторые или все данные являются действительно абстрактными (не существуют в качестве примитивов в языке программирования). Мы сгруппируем их в термин «абстракция».
Программист изначально озабочен тем, чтобы его программа корректно решала проблему. В данном анализе он обеспокоен тем, как его программа использует абстракции, но не как эти абстракции могут быть реализованы. После создания программы, он обращает внимание на абстракции, которые он использует. Каждая абстракция представляет собой новую проблему, которая требует дополнительных программ для ее решения. Новая программа также может быть написана для работы на абстрактной машине. Проблема считаются полностью решенной, когда все абстракции реализованы с помощью дополнительных программ.
Теперь ясно, что подходы языков высокого уровня и структурного программирования связаны друг с другом: каждый из них основан на идее использования абстракций, которые являются правильными для решаемой задачи. Кроме того, цель использования абстракций одинакова в обоих подходах — освобождение программиста от беспокойства о деталях, не имеющих отношения к проблеме.
Далее будет описан подход к абстракции, который допускает множество встроенных абстракций, число которых увеличивается, когда потребность в новых абстракциях появляется.
Что такое «абстракция»?
Что мы хотим от абстракции? Мы хотим механизм, позволяющий выделить нужные детали и скрыть незначащие. Обычные языки программирования предоставляют помощь в абстракции — функции и процедуры. Когда программист использует функции или процедуры он не озабочен тем, как они реализованы, ему важно, что они делают.
Но к сожалению, процедуры не предоставляют большие возможности для абстракций. И эта мысль приводит нас к понятию абстрактного типа данных, которое занимает центральное место в конструкции языка. Абстрактный тип данных определяет класс абстрактных объектов, которые полностью характеризуются операциями, доступными для этих объектов. Это означает, что абстрактный тип данных может быть определен путем определения, операций для этого типа.
Абстрактные типы предназначены для того, чтобы быть очень похожими на встроенные типов, предоставляемые на языком программирования. В случае встроенного типа данных, программист использует абстракции, которые реализуются на более низком уровне детализации - самого языка программирования и компилятора. Точно так же, абстрактный тип данных используется на одном уровне и реализуется на более низком уровне. Язык программирования позволяет использование абстрактного типа данных, не требуя его определения на рабочем месте. Процессор языка поддерживает абстрактные типы данных путем создания связей между использованием типа и его определением (которое может быть предусмотрено раньше или позже).
Заметим, что следствием концепции абстрактных типов данных является то, что большинство абстрактных операций в программе будет принадлежать к наборам операций, характеризующими абстрактные типы. Мы будем использовать термин функциональная абстракция для обозначения этих абстрактных операций, которые не принадлежат к какому-либо набору типов. Функциональная абстракция будет реализована в виде композиции операций одного или нескольких типов данных и будет поддерживаться обычным способом с помощью процедуры.
Язык программирования
Теперь дадим неформальное определение языка программирования, который позволяет использовать определение абстрактного типа данных. Язык программирования — упрощенная версия структурного языка программирования.
Язык представляет 2 формы абстракций: процедуры, которые поддерживают функциональные абстракции и операционные кластеры, которые поддерживают абстрактные типы. Каждый модуль компилируется сам по себе. Язык имеет только структурированный контроль. Структурный механизм обработки ошибок находится в стадии разработки. В данной работе, он представлен только наличием зарезервированной ошибки слова.
Проиллюстрируем использование абстрактных типов данных на следующей задаче: нужно написать программу Polish_gen, которая будет переводить инфиксную запись в польскую (постфиксную запись). Сделаем следующие предположения о нашем языке:
- Язык имеет приоритеты операторов. - Символ есть некая строка из букв и цифр либо отдельный алфавитно-цифровой символ. Символы разделены пробелом.
Пример: входная строка — a + b * (c + d), выходная строка — a b c d + * + .
Использование абстрактных типов данных
Процедура Polish_gen, описанная выше, принимает на вход три аргумента — входные данные, объект абстрактного типа данных infile, представляющий предложение в инфиксной записи; выходные данные — объект абстрактного типа данных outfile, представляющий предложение в постфиксной записи и абстрактный тип g, представляющий собой грамматику для распознования символов. Также используются вспомогательные абстрактные типы stack и token. Объявление переменных абстрактного типа использует следующий синтаксис: t : token.
Polish_Gen: procedure(input: infile, output: outfile, g: grammar); t : token; mustscan: boolean; s : stack(token) ; mustscan := true; stack$push (s, token (g, grammar$eof (g)) ) ; while-stack$empty (s) do if mustscan then t := scan(input, g) else mustscan := true; if token$is__op(t) then case tokenSprec_rel(stackStop(s), t) of '<":: stackSpush(s, t); "=":: stackSerasetop(s); '>":: begin outfile$out_str(output,tokenSymbol(stackSpop(s))); mustscan := false; end otherwise error; else outfile$out_str(output, tokenSymbol(t)); end outfile$close(output); return; end Polish_gen
scan: procedure(input: infile, g: grammar) returns token; newsymb: string; ch: char; ch := infile$get(input) while ch=" " do ch := infile$get(input); end if infileSeof(input) then return token(g, granmmrSeof(g)); newsymb :=unit string(ch); if alphanumeric(ch) then while alphanumeri¢(infile$peek(input)) do newsymb := newsymb concat infile$get(input); end return token(g, newsymb); end scan
*Вызов операции использует синтаксис, в котором сначала определяется абстрактный тип, а только потом, через специальный символ $, перечисляется операция : infile$get(input) (Таким образом, мы видим с каким абстрактным типом данная операция выполняется). Язык является строго типизованным, есть только 3 варианта, в которых абстрактный тип данных может быть использован: 1) объект может использоваться только операциями, которые определяют его абстрактный тип; 2) абстрактный объект может быть передан в качестве параметра процедуре; 3) абстрактный объект может быть назначен переменной, но только если переменная определена для хранения объектов этого типа.
Также возможно создавать объекты независимо от объявления переменной: token(g, newsymb)
Исходная функция использует 5 абстракций: infile, outfile, grammar, stack, token и функциональную абстракцию scan. Мощность абстракций данных иллюстрируется типами infile и outfile, которые используются, чтобы оградить Polish__gen от каких-либо физических фактов, относящихся к вводу и выводу, соответственно. Функция не знает ни как infile и outfile будут использоваться, ни о их представлении в виде 0 и 1 на устройстве. Все, что polish_gen знает, достаточно для его нужд. Для вывода параметров он знает, как добавить строку символов (outfile$out_str) и как означает, что выход завершен (outfile$close). Для ввода параметров, он знает, как получить следующий символ (infile$get), как смотреть на следующий символ, не удаляя его из входного сигнала (infile$peek), и как распознать конец ввода (infile$eof).
Определение абстрактных типов данных Теперь пришло время поговорить об операционном кластере, чья трансляция обеспечивает реализацию типа. Кластер содержит код, реализующий характеризующие операции и таким образом, воплощает в себе идею о том, что тип данных определяется набором операций.
В качестве примера рассмотрим абстрактный тип данных stack, используемый в Polish_gen. Кластер, описанный ниже, реализует общий набор объектов стека, которые не известны заранее.
Первая часть кластера представляет очень краткое описание интерфейса. Остальная часть определения кластера состоит из трех частей: объект представления, код для создания объектов и определение операций.
stack: cluster(element_type: type) is push, pop, top, erasetop, empty ; rep(type_param: type) = (tp: integer; e type: type; stk: array[l..] of type_param; create s: rep(element_type); s.tp := O; s.e_type := element_type; return s; end push: operation(s: rep, v: s.e_type); s.tp := s.tp+l; s.stk[s.tp] := v; return; end pop: operation(s: rep) returns s.e type; if s.tp=0 then error; s.tp := s.tp-l; return s.stk[s.tp+l]; end top: operation(s: rep) returns s.e_type; if s.tp = 0 then error; return s.stk[s.tp]; end erasetop: operation(s: rep); if s.tp = 0 then error; s.tp := s.tp-l; return; end empty: operatlon(s: rep) returns boolean; return s.tp = O; end end stack
Пользователи абстрактного типа данных смотрят на данные этого типа как неделимых сущностей. Внутри кластера объекты раскладываются на более примитивные сущности.
Зарезервированное слово create используется, когда объект данного типа создается (пользователь указывает на то, что объект абстрактного типа данных должен быть создан). Код, представленный выше, использует типичный «код создания».
Остальная часть кластера состоит из группы определений операций, которые обеспечивают реализацию допустимых операций по типу данных. Определение операции - обычные определения процедуры, за исключением того, что они имеют доступ к кластеру, что позволяет им разложить объекты кластерного типа. Операции - не сами модули; они будут приняты компилятором только в составе кластера.
Поскольку язык является строго типизированным, тип объектов, вставляемых в данный стек должен быть проверен на предмет соответствия с типом элементов стека. Это требование согласованности указано синтаксически — тип второго объекта, который будет добавлен в стек должна быть такой же, как и тип первого.
Контроль и использование информации
Абстрактные типы данных были введены как способ освобождения программиста от беспокойства по поводу неуместных деталей в его использовании абстракций данных. Но мы зашли дальше. Поскольку язык является строго типизированным, пользователь не может использовать какие-либо детали реализации. Token является хорошим примером типа, созданного для контроля доступа к деталям реализации.Новый тип вводится для ограничения распространения информации о том, как представлена грамматика. Теперь на переопределение грамматики может повлиять только token кластера - который не делает никаких предположений об индексе, который он получает от грамматики. Если ошибка возникает при поиске очередной зависимости (например, индекс вне границ), то ошибка может только быть вызвана чем-то в token или в грамматическом кластере.
На самом деле, выбор реализации лексем — например, является ли token целым числом или строкой — проектное решение. Это решение может быть отложено до тех пор, пока кластер для токенов не определен. Таким образом, программирование Polish_gen может быть сделано в соответствии с одним из принципов Дейкстры: одно решение программы в один момент времени. Следование этому принципу приводит к упрощенной логики для Polish_gen, что делает ее легче для понимания и поддержки.