О методе проектирования абстрактного типа данных в алгебре алгоритмики
Предлагается метод проектирования расширенного абстрактного типа данных и алгебраического класса. Данный абстрактный тип данных является необходимым ключевым звеном между этапами спецификации и проектирования. Рассмотрена проблема полноты расширенного абстрактного типа данных и предложено решение в...
Saved in:
| Date: | 2012 |
|---|---|
| Main Authors: | , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут програмних систем НАН України
2012
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/69614 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | n- исчисление – реалистичная формализация класса переписывающих систем / А.Е. Дорошенко, В.А. Иовчев // Пробл. програмув. — 2012. — № 1. — С. 3-16. — Бібліогр.: 29 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-69614 |
|---|---|
| record_format |
dspace |
| spelling |
Дорошенко, А.Е. Иовчев, В.А. 2014-10-17T14:44:45Z 2014-10-17T14:44:45Z 2012 n- исчисление – реалистичная формализация класса переписывающих систем / А.Е. Дорошенко, В.А. Иовчев // Пробл. програмув. — 2012. — № 1. — С. 3-16. — Бібліогр.: 29 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/69614 681.3 Предлагается метод проектирования расширенного абстрактного типа данных и алгебраического класса. Данный абстрактный тип данных является необходимым ключевым звеном между этапами спецификации и проектирования. Рассмотрена проблема полноты расширенного абстрактного типа данных и предложено решение в качестве достаточной полноты. ru Інститут програмних систем НАН України Теоретичні та методологічні основи програмування О методе проектирования абстрактного типа данных в алгебре алгоритмики Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
О методе проектирования абстрактного типа данных в алгебре алгоритмики |
| spellingShingle |
О методе проектирования абстрактного типа данных в алгебре алгоритмики Дорошенко, А.Е. Иовчев, В.А. Теоретичні та методологічні основи програмування |
| title_short |
О методе проектирования абстрактного типа данных в алгебре алгоритмики |
| title_full |
О методе проектирования абстрактного типа данных в алгебре алгоритмики |
| title_fullStr |
О методе проектирования абстрактного типа данных в алгебре алгоритмики |
| title_full_unstemmed |
О методе проектирования абстрактного типа данных в алгебре алгоритмики |
| title_sort |
о методе проектирования абстрактного типа данных в алгебре алгоритмики |
| author |
Дорошенко, А.Е. Иовчев, В.А. |
| author_facet |
Дорошенко, А.Е. Иовчев, В.А. |
| topic |
Теоретичні та методологічні основи програмування |
| topic_facet |
Теоретичні та методологічні основи програмування |
| publishDate |
2012 |
| language |
Russian |
| publisher |
Інститут програмних систем НАН України |
| format |
Article |
| description |
Предлагается метод проектирования расширенного абстрактного типа данных и алгебраического класса. Данный абстрактный тип данных является необходимым ключевым звеном между этапами спецификации и проектирования. Рассмотрена проблема полноты расширенного абстрактного типа данных и предложено решение в качестве достаточной полноты.
|
| issn |
1727-4907 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/69614 |
| citation_txt |
n- исчисление – реалистичная формализация класса переписывающих систем / А.Е. Дорошенко, В.А. Иовчев // Пробл. програмув. — 2012. — № 1. — С. 3-16. — Бібліогр.: 29 назв. — рос. |
| work_keys_str_mv |
AT dorošenkoae ometodeproektirovaniâabstraktnogotipadannyhvalgebrealgoritmiki AT iovčevva ometodeproektirovaniâabstraktnogotipadannyhvalgebrealgoritmiki |
| first_indexed |
2025-11-27T02:08:24Z |
| last_indexed |
2025-11-27T02:08:24Z |
| _version_ |
1850792845411090432 |
| fulltext |
Теоретичні та методологічні основи програмування
УДК 681.3
А.Е. Дорошенко, В.А. Иовчев
О МЕТОДЕ ПРОЕКТИРОВАНИЯ АБСТРАКТНОГО ТИПА
ДАННЫХ В АЛГЕБРЕ АЛГОРИТМИКИ
Предлагается метод проектирования расширенного абстрактного типа данных и алгебраического клас-
са. Данный абстрактный тип данных является необходимым ключевым звеном между этапами специ-
фикации и проектирования. Рассмотрена проблема полноты расширенного абстрактного типа данных
и предложено решение в качестве достаточной полноты.
Введение
К числу актуальных проблем алгебры
алгоритмики (АА) [1 – 3] относятся средства
описания и реализации рекурсии и паралле-
лизма, а также формализация концепции
абстрактного типа данных (АТД). Решение
этих задач тесно связано с важными при-
ложениями в современных объектно-
ориентированных вычислительных средах.
В Украине исследования в данной области
восходят к фундаментальным работам
В.М. Глушкова по теории систем алгорит-
мических алгебр (САА) [2, 3].
Современное состояние исследова-
ний по применению алгебры алгоритмики
связано с решением ряда важных теорети-
ческих и практических задач построения
сверхвысокого уровня языков проектиро-
вания, а также средств автоматизации про-
цесса синтеза (сборки, трансформации)
программ в объектно-ориентированных
вычислительных средах [4 – 6]. Следует
отметить, что множественность указанных
языков определяется концепцией алгорит-
мического клона, системы образующих
(СО) которого соответствуют подходящей
парадигме программирования (структур-
ной, неструктурной, объектно-ориенти-
рованной и др.) [6 – 8].
Цель данной работы – показать воз-
можность развития концепции абстрактно-
го типа данных [2 – 5] в направлении объ-
ектно-ориентированной парадигмы в рам-
ках алгебры алгоритмики. В статье показа-
но, как с помощью алгоритмических опи-
саний АА можно провести проектирование
объекта менее затратным способом с по-
следующим погружением в произвольно
выбранную вычислительную среду с реа-
лизацией на объектно-ориентированном
языке (Delphi, C++, Java и др.) [6 – 8].
Материал данной статьи подчинён
следующей структуре. В разделе 1 дается
краткая характеристика алгебры алгорит-
мики. Раздел 2 посвящен обзору зарубеж-
ных публикаций по направлению АТД и
технике алгебраического проектирования
классов. Раздел 3 описывает стили специ-
фикаций, необходимые для описания ме-
тода проектирования. Концепция актуаль-
ного АТД в АА приведена в разделе 4.
Раздел 5 содержит описание метода по-
строения расширенного АТД. Проблема
полноты расширенного АТД описывается
в разделе 6. Иллюстративный пример про-
цесса построения АТД Стек содержится в
разделе 7. Раздел 8 характеризирует объ-
ектно-ориентированное решение в АА.
Раздел 9 содержит описание Класса на ос-
нове расширенного АТД. Раздел 10 содер-
жит иллюстративную спецификацию АТД
Сорт и эффективного Класса Сорт. В за-
ключении приведены выводы и дальней-
шие перспективы.
1. Алгебра алгоритмики
АА положена в основу алгебраиче-
ской теории алгоритмов, в рамках которой
осуществляется разработка средств пред-
ставления, накопления, конструирования и
классификации алгоритмических знаний,
относящихся к различным предметным
областям, в частности, к задачам символь-
ной мультиобработки (сортировка, поиск,
процессирование языков)[1, 4, 5].
Алгебра алгоритмики – это двух-
уровневая система:
3
© А.Е. Дорошенко, В.А. Иовчев, 2012
ISSN 1727-4907. Проблеми програмування. 2012. № 1
Теоретичні та методологічні основи програмування
• верхний уровень, ориентирован на
проектирование неинтерпретированных
схем, здесь используется аппарат теории
клонов в связи с построением подходящей
алгебры алгоритмов и формированием её
алгебраических основ;
• на втором уровне осуществляется
конкретизация неинтерпретированных
схем и построение прикладных алгебр ал-
горитмов, ориентированных на выбранные
предметные области.
На всех уровнях алгебры алгорит-
мики применяются метаправила проекти-
рования схем: свёртка (укрупнение), раз-
вёртка (детализация), переинтерпретация
(сочетание свёртки и развёртки) и транс-
формация, состоящая в совершенствова-
нии схем на основе применения аппарата
тождеств, квазитождеств и соотношений,
характеризующих свойства операций ал-
гебры алгоритмов и выбранной предмет-
ной области [3 – 5].
С АА связаны три формы представ-
ления (спецификации или алгебро-алго-
ритмические модели) алгоритмов [3]:
• аналитическая – представление ал-
горитма в виде формулы в выбранной ал-
гебре алгоритмов, удобна для трансформа-
ции, в частности для улучшения по вы-
бранным критериям (память, быстродейст-
вие и др.);
• текстовая (естественно-лингвисти-
ческая) – представление алгоритма на ес-
тественном (понятном пользователю) язы-
ке в терминах выбранной предметной об-
ласти, удобна для диалогового проектиро-
вания правильных алгоритмов и программ
на разных входных языках;
• визуальная (графовая, граф-схем-
ная) – представление алгоритма в виде
граф-схем Калужнина, характеризуется в
первую очередь наглядностью в процессе
диалогового проектирования и, кроме то-
го, является промежуточным звеном при
переходе к UML-диаграммам.
Высокоуровневость и взаимодопол-
няемость формализмов предлагаемых АА
по сравнению с традиционными языками
программирования (ЯП), вместе с теорией
клонов и использованием метаправил
обеспечивает надежный фундамент для
проектирования и синтеза программ в объ-
ектно-ориентированных и распределенных
(Grid) средах [9].
2. Техника алгебраического про-
ектирования классов
Первые труды по абстрактным ти-
пам данных появились в начале 1970-х.
Среди них наиболее известны работа Хоа-
ра о доказательстве корректности пред-
ставлений данных [10], в которой было
введено понятие абстракции функций, и
работа Парнаса по сокрытию информации
[11]. Конечно, абстрактные типы данных
не ограничиваются вопросами сокрытия
информации, хотя многие их элементар-
ные изложения дальше этого не идут.
Собственно АТД были введены
Лисков и Зиллес [12]; более глубокие ал-
гебраические представления были приве-
дены в [13 – 14]. Группа ADJ (Гоген, Тэт-
чер, Вагнер) исследовала алгебраические
основания абстрактных типов данных, ис-
пользуя теорию категорий [15].
На основе абстрактных типов дан-
ных базируются несколько языков специ-
фикаций. Двумя результатами группы ADJ
являются CLEAR [16] и OBJ-2 [17], а так-
же Larch, предложенный Гуттаг, Хорнинг
и Винг [18].
Идея "разделения интересов" явля-
ется центральной в работах Э. Дейкстры, в
частности, в его книге "Дисциплина про-
граммирования" [19]. Суть ее состоит в
разделении программного решения на от-
дельные функции, которые минимально
перекрываются в функциональности.
Можно также сказать, что "Интерес" явля-
ется синонимом "функции" или "поведе-
ния". Данная идея предполагает достиже-
ние прогресса за счет модульности и ин-
капсуляции. Как пример, проектирование
информационных систем базируется на
разделении "интересов", а конкретнее на
уровень представления, уровень бизнес-
логики, уровня доступа к данным, уровень
базы данных и т. д.
Понятие достаточной полноты впер-
вые опубликовано исследователями Гуттаг
и Хорнинг [20].
Поскольку под классом можно по-
нимать пару «тип данных + функции», а в
рассматриваемой технике помимо проек-
4
Теоретичні та методологічні основи програмування
5
тирования собственно АТД выполняется
проектирование функций работы с ним, то
это эту технику можно считать техникой
алгебраического проектирования классов
(АПК) [20 – 28].
Чтобы получить надлежащие опи-
сания объектов, разрабатываемый метод
АПК должен удовлетворять трем услови-
ям:
1) описания должны быть точными и
недвусмысленными;
2) они должны быть полными - или,
по крайней мере, иметь в каждом конкрет-
ном случае нужную нам полноту (некото-
рые детали можно намеренно опускать);
3) они не должны быть «излишне спе-
цифицированы».
Основой для третьего условия яв-
ляются результаты изучения Лиенц и
Свонсон стоимости сопровождения [26].
Было установлено, что более 17 % стоимо-
сти программного обеспечения (ПО) при-
ходится на изменения в форматах данных.
Ясно, что метод, который ставит анализ и
проектирование в зависимость от физиче-
ского представления структур данных, не
обеспечит разработку достаточно гибкого
ПО [21]. Поэтому при использовании объ-
ектов или типов объектов в качестве осно-
вы для архитектуры системы требуется
найти лучший способ описания, чем кон-
кретное представление.
3. Стиль спецификаций
Выбор конкретного стиля специфи-
каций несет как ряд преимуществ, так и
ряд ограничений. В рамках данной про-
блемы существует как минимум четыре
альтернативы [22, 28]:
• аппликативный последовательный –
функциональное программирование без
переменных и параллельных вычислений;
• императивный последовательный –
программирование с переменными, при-
сваиванием, циклами и т. д., но без парал-
лельных вычислений;
• аппликативный конкурентный – функ-
циональное программирование с парал-
лельными вычислениями;
• императивный конкурентный – про-
граммирование с переменными, присваи-
ванием, циклами и т. д. и параллельными
вычислениями.
Конкурентные стили больше зави-
сят от дальнейшего представления и реа-
лизации проектируемого решения, и ап-
пликативный конкурентный стиль счита-
ется неподходящим как базис [22, 28].
Разница между аппликативным и
императивным стилями такая же, как и
разница между абстрактными и конкрет-
ными стилями. Под абстрактностью пони-
мается свойство спецификаций иметь
множество открытых альтернативных ва-
риантов формализации. Другими словами,
чем меньше проектных решений принима-
ется в схеме, тем больше в ней вариантов и
соответственно тем более она абстрактна.
Понятие проектного решения вклю-
чает в себя такие решения [22, 28]:
• как определить модуль;
• «конкретизация» структур данных;
• «конкретизация» алгоритмов;
• использование переменных;
• используемые образцы данных для
обмена информации;
• использование каналов обмена дан-
ных.
Таким образом, можно выделить
общие категории:
• абстрактно аппликативная – описа-
ние, содержащее абстрактные типы и сиг-
натуры функций с аксиомами, но не явные
определения;
• конкретно аппликативная – описа-
ние, содержащее конкретные типы и явные
определения;
• абстрактно императивная – в опи-
сании нет явного определения перемен-
ных, вместо их используется абстрактное
ключевое слово, присутствуют описания
аксиом;
• конкретно императивная – описа-
ние, содержащее определения переменных
и явные определения функций;
• абстрактно конкурентная – описа-
ние, не содержащее явных определений
каналов, вместо их используется абстракт-
Теоретичні та методологічні основи програмування
ное ключевое слово, присутствуют описа-
ния аксиом;
• конкретно конкурентная – описа-
ние, содержащее явные определения пере-
менных, каналов и функций.
Отметим, что эти различия более
относительные, чем абсолютные. Описа-
ние может быть в одном смысле абстракт-
ным и конкретным в другом. Данная неоп-
ределенность имеет сходство с вышеупо-
мянутой (раздел 2) идеей "разделения ин-
тересов" Э. Дейкстры [19].
В итоге, спецификации могут со-
держать как комбинации разных стилей,
так и разные степени абстракций.
4. Концепция абстрактного типа
данных в АА
Все языки программирования по-
строены на абстракции [29]. Сложность
решения задачи напрямую зависит от типа
и качества абстракции.
Концепция абстрактного типа дан-
ных (АТД) состоит в фиксации типов (сор-
тов) обрабатываемых данных и средств
доступа к ним (логических условий и опе-
раторов), допустимых при конструирова-
нии алгоритмов и программ обработки
данных указанных типов. Для АТД харак-
терен принцип инкапсуляции, в соответст-
вии с которым обработка данных допусти-
ма лишь определенными для них средст-
вами доступа [3, 4]. Также данный принцип
идентичен инкапсуляции в объектно-
ориентированном программировании (ООП).
Различают два уровня представле-
ния АТД. На верхнем (абстрактном) уров-
не перечисляются типы данных и сигнату-
ра АТД, в рамках которой обозначаются
средства доступа данных. На нижнем
уровне (реализации) разрабатываются
представления типов для выбранного (це-
левого) языка программирования и сово-
купность оформленных в данном языке
процедур, реализующих доступ к обраба-
тываемым данным соответствии с сигна-
турой АТД. Можно сказать, что "видимая"
часть абстрактного типа данных – наиме-
нования зафиксированных средств досту-
па, тогда как их реализации "невидимы",
недоступны для программиста [3, 4].
Для формализации понятия абст-
рактного типа данных в АА используются
многоосновные (многосортные) алгебраи-
ческие системы (МАС). Определение МАС
представляет собой обобщение понятий
модели и алгебры. Следует отметить, что
математический фундамент алгоритмики –
алгебры алгоритмов – это двухосновные
алгебраические системы, ориентированные
на формализованное описание и преобра-
зования алгоритмов. А также, основы раз-
личных алгебр алгоритмов – множества
операторов и предикатов (логических ус-
ловий), порожденных функциями, входя-
щими в сигнатуру АТД, связанного с вы-
бранным классом задач [3 – 6].
Многоосновная алгебраическая сис-
тема имеет вид:
><= СигнатураБазисМАС ;
где,
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
∈
∈
−
nnxnx
xx
Qqq
Qqq
Базис
|
| 111
K – совокупность
сортов (основ) ( )niQi ≤≤1 ,
Сигнатура – это объединение пре-
дикатов (логических условий) и операций
(операторов), определенных на совокупно-
сти основ [3, 4].
Операции и предикаты, входящие в
сигнатуру рассмотренного АТД, опреде-
ленные на совокупностях основ, могут
рассматриваться в качестве базисных
(элементарных) при построении различ-
ных алгоритмов обработки последователь-
ностей данных из основ, в частности, алго-
ритмов сортировки.
5. Расширение абстрактного типа
данных
Процесс разработки программного
обеспечения проходит этапы известные
как анализ или спецификация, проектиро-
вание и реализация [20]. Переход от про-
ектирования к реализации – это просто
движение от одного явного вида к друго-
му: форма при проектировании более аб-
страктна и ближе к математическим поня-
тиям, а при реализации более конкретна и
ближе к компьютеру, но обе они являются
явными. В общих случаях объектная тех-
6
Теоретичні та методологічні основи програмування
нология почти стирает различия между
проектированием и реализацией [20, 29].
Чего нельзя сказать о переходе от специ-
фикации к проектированию. Главная про-
блема данного перехода состоит в отсутст-
вии промежуточного звена обладающего
рядом свойств:
• спецификация должна быть фор-
мальным математическим описанием;
• иметь математическую модель для
описания не всюду определенных опера-
ций;
• отсутствие императивных состоя-
ний присущих программам;
• иметь общий вид для многоразово-
го использования, как для решения кон-
кретной задачи, так и для других, имею-
щих разные пути решения;
• являть четкий переход от неявного
к явному.
Как решение данной проблемы
предлагается метод построения расширен-
ного абстрактного типа данных.
Пусть некая МАС описывает
АТД(T). Текущего описания АТД(T) недос-
таточно для полной спецификации АТД.
Возникает проблема полного понимания
типа (сорта) данного АТД. Для конкрети-
зации предлагается дополнительная фор-
мализация спецификаций, а именно:
• тип;
• функции;
• аксиомы;
• предусловия.
5.1. Тип. Для указания специфици-
руемых типов следует дать определение
типа. Тип – это некое множество, характе-
ризуемое МАС, функциями, аксиомами и
предусловиями. Как пример, тип Стек –
это множество всех возможных стеков, тип
Числовые массивы – это множество всех
числовых массивов и т.д.
Указывая:
[ ]GADT
Тип :
подразумевается, что спецификация отно-
сится к одному абстрактному типу данных
ADT задающему объекты G. Другими сло-
вами [ ]GADT – это не один конкретный
объект, а совокупность объектов.
Пусть ADT(T) и ADT’(T) произволь-
ные абстрактные типы данных тогда:
• любой описанный АТД может вхо-
дить в базис другого АТД:
{ }
{ }
);1(,
)(|
|
:
:)(
niQ
TTADqq
Qqq
Базис
TADT
i
jj
iii
≤≤
′∈
∈
M
• вхождение в базис АТД позволяет
применяться рекурсивно:
ADT(T):
{ }
{ }
).1(,
)(|
|
: niQ
TADTqq
Qqq
Базис i
jj
iii
≤≤
∈
∈
M
Определение. Экземпляром абст-
рактного типа данных АТД(T) называется
объект, принадлежащий множеству опи-
сываемому спецификацией АТД(T).
5.2. Функции – это понятие, содер-
жащее определение полной, частной функ-
ций, а также категорий функций.
Под полной функцией понимается
, где переменные x прини-
мают значение из множества D, а функция
принимает значение из множества V, реа-
лизует отображение из D в V. Множество
D – область определения (исходное мно-
жество), а V – область значения функции
(результирующее множество).
),...,,( 21 nxxxf
Другими словами, функция – это
механизм для получения значения, при-
надлежащего результирующему множест-
ву, по допустимому входу, принадлежа-
щему исходному множеству.
При описании АТД функции опре-
деляются не полностью, вводятся только
их сигнатуры. Т. е. списки типов их аргу-
ментов и результата. Соответственно,
множества D и V входят в описанные типы
АТД.
7
Теоретичні та методологічні основи програмування
.,
,,...,,: 21
VyDx
yxxxf n
∈∈
→><
Функция ) , из области
определения D, в результирующее множе-
ство V называется частной, если она опре-
делена не для всех элементов D. Отсюда,
функция, не являющаяся частной, называ-
ется полной. Соответственно, областью
определения D произвольной частной
функции ) , является под-
множество таких элементов D, для кото-
рых эта функция имеет элементы в резуль-
тирующем множестве V.
,...,,( 21 nxxxf
,...,,( 21 nxxxf
>< nxxxf ,...,,: 21 y,
.
,
,,
VV
DD
VyDx
⊂′
⊂′
′∈′∈
Примером частной функции являет-
ся функция обращения действительных
чисел inv, значение которой на действи-
тельной оси x равно . Пусть N
– множество всех действительных чисел, а
функция inv не определена на x = 0, тогда
она определяется как частная функция на
N. Область определения ее является под-
множество R от N, т. е. множество всех
действительных чисел, кроме нуля.
xxinv /1)( =
Функции предлагается разделить на
три категории: создающие объекты (кон-
структоры), возвращающие информацию
об объектах (запросы) и изменяющие объ-
екты (команды). В современном ООП эти
три категории называются "конструктор",
"аксессор" и "модификатор". Конкретиза-
ция данных категорий такова:
• функция-конструктор моделирует
операцию, использующую аргументы, ли-
бо не использующую, которая создает эк-
земпляры Т из экземпляров других типов;
• функция-запрос моделирует опера-
цию, которая устанавливает свойство Т,
описанное в терминах экземпляров других
типов;
• функция-команда моделирует опе-
рацию, которая по существующему экзем-
пляру Т и, возможно экземплярам других
типов выдает новые экземпляры типа Т.
5.3. Аксиомы. Вышерассмотренные
данные описываются посредством задания
списка функций, применимых к экземпля-
рам АТД. Но описание метода алгебраиче-
ского проектирования классов подразуме-
вает, что выбор конкретного представле-
ния уступает способу описания, т. е., что
всякое явное определение обязывает вы-
брать некоторое представление, а для опи-
сания АТД это недопустимо. Допустимы
только неявные определения, но вышеопи-
санных деклараций функций явно недоста-
точно и требуется еще дополнительные
определения в виде аксиом. Отметим так-
же, что данные определения не содержат
конкретные значения функций в специфи-
кации АТД. По сути, аксиомы являются
предикатами (в смысле логики), выра-
жающими истинность некоторых свойств,
для всех возможных значений из АТД.
Отметим, что имеются два вида
«неявности»:
• метод определяет неявно некоторое
множество объектов, задавая применимые
к ним функции. Но, из этого определения
не следует, что перечислены все операции.
Т.е. в процессе построения и/или исполь-
зования могут быть добавлены и другие;
• сами функции также определены
неявно. Свойства данных функций задают
аксиомы. Т. е. утверждения о полноте нет,
и в процессе проектирования они могут
приобрести дополнительные свойства.
Эта неявность и является важным
ключевым аспектом АТД и, как следствие,
их воплощения в классы ООП. Такая неяв-
ность предполагает открытость определе-
ний. Т.е. всегда можно добавить новые
свойства АТД или класса. В ООП подоб-
ным механизмом расширения является
наследование.
5.4. Предусловия. Процесс расши-
ренной формализации спецификаций АТД
неизбежно сталкивается с проблемой не-
обходимости частных функций. В п. 5.2, в
функциях при их объявлении используют-
ся перечеркнутые стрелки, таким образом,
указывая, что эти функции являются част-
ными. В процессе проектирования ПО
8
Теоретичні та методологічні основи програмування
очевидно, что не каждая операция приме-
нима ко всем объектам (т. е. является част-
ной) и что они часто являются источником
ошибок. Даже если описание частной
функции f(x) корректно, и если x принад-
лежит D, это не дает гарантии что на x из
D функция f(x) определена. Для этого спе-
цификация АТД должна содержать задан-
ные области для частных функций. В этом
заключен смысл предусловий.
Предусловие p функции f – это ха-
рактеристическая функция области f. Ха-
рактеристической функцией подмножества
A′ множества A называется полная функ-
ция p(x) истинная, если , и ложная в
противном случае.
Ax ′∈
Каждая функция имеет условия,
которым должны удовлетворять аргумен-
ты функции, чтобы входить в ее область.
Булевское выражение, которое оп-
ределяет область функции, называется
предусловием соответствующей частичной
функции.
В итоге, расширенным АТД являет-
ся система , где >< PAFSBT ,,,,,
T – описываемый тип;
B – совокупность основ (сортов);
S – объединение базисных предикатов и
операций, определенных на совокупности
основ;
F – функции для обработки основ;
A – аксиомы;
P – предусловия.
6. Полнота АТД
Формализация спецификаций АТД
является неявной и неполной [20 – 28]. Так
вышеприведенная спецификация выражает
все, что нужно знать об объекте, но и не
включает ничего, что бы относилось к
конкретным реализациям. Методом по-
строения определяется некое множество
элементов (объектов) со свойствами и
функциями. Так же, нет как формального,
так и неформального эталонного докумен-
та для определения полноты специфика-
ции АТД. Отметим, что в логических сис-
темах, идея полноты относится к возмож-
ности доказать все истинные утверждения
[20]. Применение этой идеи для специфи-
каций АТД позволяет определить только
достаточную полноту. Достаточная полнота
позволяет охватить АТД и не оставить вне
спецификации никакое важное свойство.
Определение. Пусть С – схема со-
держащая одну или более функций некого
АТД. Эта схема является корректной тогда
и только тогда, когда все функции (по ре-
курсии) имеют правильное число аргумен-
тов соответствующих типов и их значения
удовлетворяют предусловиям, если они
имеются.
Определение. Спецификация АТД(T)
>< PAFSBT ,,,,, является непротиворе-
чивой тогда и только тогда, когда для кор-
ректно простроенной схемы ее аксиомы
позволяют вывести не более одного значе-
ния.
Определение. Спецификация АТД(T)
>< PAFSBT ,,,,, является достаточно
полной тогда и только тогда, когда:
• на каждой основе { } )1(,,...,1 niBBB in ≤≤
определена совокупность операций
{ })()( пСигноСигнS ∪= , и нет операций из
S не определенных на этих основах;
• аксиомы { } )1(@,@,...,@1 niA in ≤≤= и
предусловия { } )1(,,...,1 nipppP in ≤≤=
позволяют определить корректность схемы
С использующей АТД(T);
• спецификация АТД является непроти-
воречивой.
Отметим, что по аналогии, такое
решение проблемы полноты используется
в разных методах построения алгебраиче-
ского класса [12, 13, 15, 16, 20, 21].
При дальнейших описаниях воз-
никнет потребность в конкретизации ти-
пов, и могут добавиться другие, в зависи-
мости от пути представления (например,
разные языки программирования или раз-
ные среды выполнения). Функции из неяв-
ных определений и аксиом приобретут
дополнительные свойства.
Описанные спецификации форми-
руют общую модель на соответствующих
структурах данных. Определенные функ-
ции дают возможность строить посредст-
вом операции суперпозиции [3] более
9
Теоретичні та методологічні основи програмування
сложные выражения, а аксиомы в свою
очередь упрощают понимание сложных
выражений и позволяют получать более
простые результаты.
Также следует отметить, что спе-
цификация АТД является формальным
математическим описанием и не описыва-
ет явных изменений, т. е. является аппли-
кативной. Все свойства АТД моделируют-
ся как математические функции, включая
конструкторы, запросы и команды.
7. Построение АТД Стек
Проиллюстрируем описанную кон-
цепцию. Одним из хорошо изученных
примеров является описание типа стек.
Стек служит для того, чтобы накапливать
и извлекать другие элементы в режиме
"последним пришел – первым ушел"
(LIFO). Элемент, помещенный в стек по-
следним, будет извлечен из него первым.
Стеки присутствуют в дидактических
представлениях абстрактных типов данных
настолько часто, что Э. Дейкстра как-то
заметил, что "абстрактные типы данных
являются прекрасной теорией, целью ко-
торой является описание стеков" [19, 21].
Далее будет рассматриваться в ка-
честве примера физическое представление
стека МАССИВ_ВВЕРХ [21].
Данный стек представляется по-
средством массива Представление и цело-
го числа Счет, с диапазоном значений от 0
(для пустого стека) до Емкость – размера
массива Представление, элементы стека
хранятся в массиве и индексируются от 1
до Счет.
7.1. Базис. Пусть Базис – это мно-
жество основ Базис(q), где q = 1,...,n, а
множество –
основа q, состоящая из элементов типа
(сорта) X. Следовательно, определим базис
стека:
}|),({)( XxxqAqБазис ∈=
{ }
.
}|{
}},{2|{
}|{
Элементvv
ЛожноИстинноEee
ЧисланиеПредставлениеПредставле
ЧислаСчетСчет
∈
=∈
∈
∈
Отметим, что в качестве элементов
стека может выступать сам стек. В этом
случае необходимо добавить:
.}|{ Стекvv ∈′′
7.2. Сигнатура. На множествах
Базис определим сигнатуру предикатов и
операций, входящих в качестве элементар-
ных логических условий и операторов в
схему Стек.
Сигн(р):
ЕмкостьСчет < – предикат, истинный,
если Счет не достиг Емкость;
0==Счет – предикат, истинный, если
Счет равен 0;
Сигн(о):
),,( ниеПредставлеСчетvЗаписать – за-
писать элемент в массиве Представление с
позицией Счет;
),( ниеПредставлеСчетЧитать – прочи-
тать элемент в массиве Представление с
позицией Счет;
),( ниеПредставлеСчетУдалить – удалить
элемент в массиве Представление с пози-
цией Счет;
)(СчетУвеличить – увеличить Счет на
единицу типа;
)(СчетУменьшить – уменьшить Счет на
единицу типа.
Таким образом, спецификация от-
носится к одному абстрактному типу дан-
ных – стек, задающему стеки объектов
произвольного типа S.
7.3. Функции.
• Поместить – функция-команда, воз-
вращает новое состояние стека с новым
элементом, помещенным в его вершину.
.: SvSПоместить →×
• Извлечь – функция-команда, возвра-
щает новое состояние стека с вытолкну-
тым верхним элементом, если таковой
был. Объяснение, как учесть возможность
пустого стека, из вершины которого нече-
го удалять, последует далее.
SИзвлечь : .S
• Элемент – функция-запрос, возвра-
щает верхний элемент стека, если таковой
имеется.
10
Теоретичні та методологічні основи програмування
SЭлемент : .v
• Пустой – функция-запрос, выявляет
пустоту стека, ее результатом является
логическое значение из множества E2 (ис-
тина или ложь).
.: eSПустой →
• Новый – функция-конструктор, соз-
дает пустой стек.
.][: SSСтекНовый →
Функция Поместить в качестве
аргумента принимает пары вида (S,v), в
которой S – экземпляр типа Стек[S], а v –
экземпляр типа Элемент и возвращает в
качестве результата экземпляр типа
Стек[S]. В сигнатуре таких функций как
Извлечь и Элемент под перечеркнутой
стрелкой понимается, что эти функции
применимы не ко всем элементам множе-
ства входов. Описание функции Новый
сокращенно в виду того, что результат
один, а аргументов нет.
7.4. Аксиомы. Формализация их
для АТД Стек такова:
;)),((:4@
;)(:3@
;)),((:2@
;)),((:1@
1
0
evSПоместитьПустой
eНовыйПустой
SvSПоместитьИзвлечь
vvSПоместитьЭлемент
=
=
=
=
где
.
,
,2,
1
0
10
Ложноe
Истинноe
Eee
=
=
∈
Аксиомы @1 и @2 выражают ос-
новные свойства стеков LIFO, первая –
вершина содержит последний помещен-
ный элемент m, вторая, – после удаления
элемента m из s получаем s который был
до помещения в него m. Аксиома @3, лю-
бой стек, полученный в результате выпол-
нения Новый пустой. И аксиома @4, лю-
бой стек, полученный после выполнения
Поместить, другими словами, получен-
ный после помещения элемента в сущест-
вующий стек, не является пустым.
7.5. Предусловия. Для всякого вы-
ражения, содержащего частичные функ-
ции, необходимо проверять, что их аргу-
менты удовлетворяют соответствующим
предусловиям. В данном случае, сущест-
вуют две, не полностью определенные
функции:
• Элемент – у пустого стека нет
верхнего элемента;
• Извлечь – нельзя удалить элемент
из пустого стека.
В разделе функции при их объявле-
нии использованы перечеркнутые стрелки,
таким образом, указывая, что эти функции
являются частными.
p1: Элемент(S) если НЕ Пустой(S)
p2: Извлечь(S) если НЕ Пустой(S).
7.6. Полная спецификация АТД
Стек.
АТД Стек:
1. Тип:
Стек[S].
2. Базис:
{ }
.
}|{
}},{2|{
}|{
Элементvv
ЛожноИстинноEee
ЧисланиеПредставлениеПредставле
ЧислаСчетСчет
∈
=∈
∈
∈
3. Сигнатура:
⎭
⎬
⎫
⎩
⎨
⎧
<
==
=
⎪
⎪
⎪
⎭
⎪⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
=
)(
),0(
)(
,
)(
),(
),,(
),,(
),,,(
)(
ЕмкостьСчет
Счет
рСигн
СчетУменьшить
СчетУвеличить
ниеПредставлеСчетУдалить
ниеПредставлеСчетЧитать
ниеПредставлеСчетvЗаписать
оСигн
4. Функции:
,:
,][:
SvSПоместить
SSСтекНовый
→×
→
SИзвлечь : ,S
SЭлемент : ,v
11
Теоретичні та методологічні основи програмування
.: eSПустой →
5. Аксиомы:
,)),((:4@
,)(:3@
,)),((:2@
,)),((:1@
1
0
evSПоместитьПустой
eНовыйПустой
SvSПоместитьИзвлечь
vvSПоместитьЭлемент
=
=
=
=
где
.
,
,2,
1
0
10
Ложноe
Истинноe
Eee
=
=
∈
6. Предусловия:
p1: Элемент(S) если НЕ Пустой(S)
p2: Извлечь(S) если НЕ Пустой(S)
8. Объектно-ориентированное
решение в АА
При возникновении проблемы по-
строения модульной структуры, основан-
ной на типах объектов, АТД представляет
гибкое решение содержащее механизм
описания высокого уровня, при этом не
связанный с особенностями реализации.
Что в свою очередь является подходящим
фундаментом для развития объектно-
ориентированного направления в рамках АА.
Таким образом, новое объектно-
ориентированное решение строится (на
уровне анализа, проектирования и реализа-
ции) как совокупность взаимодействую-
щих, с разной степенью описания, АТД.
Конструирование объектно-
ориентированного решения в АА – это
описание решения как структурированной
совокупности полной и/или частичной
реализации абстрактных типов данных со
следующей структурой:
• в основе лежит понятие АТД;
• для конструирования программ
нужны классы – реализации АТД;
• реализации не обязаны быть пол-
ными;
• в основе структурирования лежат
отношения между классами и наследова-
ние.
Отсюда следует, что переход от
спецификации к проектированию – это
идентификация каждой абстракции. На
рисунке показано переходы, в процессе кон-
струирования объектно-ориентированного
решения, между формами и их экземпляра-
ми.
9. Класс
Определение. Класс – это абст-
рактный тип данных, с описанной частич-
ной или полной реализацией.
Под классом понимается система
( )IFBТКласс ,,,= , где:
• T – тип, характеризуемый абстракт-
ным типом данных, либо (в случае множе-
ственной реализации) множеством абст-
рактных типов данных.
{ }
).1(
,,...,: 1
njАТД
АТДАТДТ
j
n
≤≤
• B – множество, полученное в ре-
зультате объединения базиса из и
конкретизации (привязки к целевой плат-
форме, или «реализации») базиса.
iАТД
.БазисБазисB АТД ∪=
• F – описание алгоритмов функций
посредством Сигнатуры из АТД в строгих
рамках аксиом и предусловий. Как пример,
в статье в качестве описания выбрана Ал-
гебра Дейкстры [3,19].
,:: Sf =
где S – структурная схема
• I – множество, характеризующее
интерфейс класса с точки зрения ООП.
Содержит декларации функций, представ-
ляемые открыто классом. Отметим, что
функции описанные в АТД, но не содер-
жащиеся в I, следует рассматривать как
внутренние или «приватные».
.:
0
⎪
⎭
⎪
⎬
⎫
⎪
⎩
⎪
⎨
⎧
⇒∈
⇒∈
TФункцииf
TФункцииf
I
n
K
АТД может иметь разную степень
описания, а класс – разную степень реали-
зации. По сути, реализация это уже сфор-
мированная, конкретная привязка к некой
платформе. Полностью реализованный
класс называется эффективным. Частич-
но реализованный – называется отложен-
ным. Любой класс является либо отложен-
ным, либо эффективным [21].
12
Теоретичні та методологічні основи програмування
Для получения эффективного клас-
са необходимо описать:
• спецификации АТД;
• выбор представления (View);
• отображение из АТД в View в виде
множества компонентов (features), каждый
из которых реализует одну из функций в
рамках представления, и при этом строго
удовлетворяет аксиомам и предусловиям.
Следует отметить, что данные ком-
поненты в процессе реализации могут
сформироваться как в процедуры и/или
функции, так и в качестве полей данных
или атрибутов.
Часто при разработке программного
обеспечения объектно-ориентированная
система в завершенном виде не содержит
данных о проектировании, разработке и
реализации. Тем, кто будет обслуживать
такую систему (расширять, переносить,
отлаживать), придется полностью изучить
ее, потратив на это время и ресурсы. В ка-
честве решения предлагается обеспечить
систему описанными АТД и/или классами.
Отложенные классы служат для
классификации групп связанных типов
объектов, описывают важные многократно
используемые модули высокого уровня,
фиксируют общие свойства поведения.
Именно они играют ключевую роль в по-
лиморфизме, а также обеспечении децен-
трализации и расширяемости программной
архитектуры.
Если спецификации АТД являются
аппликативными, то в классах апплика-
тивная точка зрения на функции отбрасы-
вается, и команды переопределяются как
операции, которые могут изменять объек-
ты. Такое изменение четко отражает импе-
ративную парадигму, преобладающую при
разработке ПО. Это в свою очередь влечет
изменение в аксиомах АТД.
10. Построение АТД Сорт
Проиллюстрируем абстрактный тип
данных Сорт с описанием эффективного
класса Сорт. В качестве примера в часть
функции взяты алгоритмы сортировки
Раствор, Пузырек и Шейкер [3 – 5].
Первым этапом является построе-
ние абстрактного типа данных Сорт:
АТД Сорт:
1. Тип:
Сорт[C].
Рисунок. Формы и их экземпляры
13
Теоретичні та методологічні основи програмування
2. Базис:
{
{
{
{
{ }
{ }
}
}
}
}
.
_|
_|
,|,
|
|
|
|
_
__
массиваУказателиУУ
массиваМаркерыММ
массивмассивмассивrlrl
Массивымассивмассив
Массивымассивмассив
Массивы
МассивыМассивы
МассивыМассивыМассивы
неот
отсортненене
отсортотот
отсортнеотсортне
отсортотсорт
∈
∈
∩=∈
∈
∈
⎭
⎬
⎫
⎩
⎨
⎧
∈
∈
3. Сигнатура:
( )
( )
( )
( )
( )
,
,_
,_
,,__
,,__
,|,
)(
⎪
⎪
⎪
⎪
⎭
⎪⎪
⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎪
⎨
⎧
=
Е
УвлевоСдвиг
УвправоСдвиг
УУуказательнаУст
МУмаркернаУст
УrlТрансп
оСигн
( )
( )
( )
( )
,
,_
,
,|
),,(_
,,_
)(
⎪
⎪
⎪
⎭
⎪⎪
⎪
⎬
⎫
⎪
⎪
⎪
⎩
⎪⎪
⎪
⎨
⎧
>=
УУотрезокУпорядочен
массивУпорядочен
Уrl
УУуказателяДостиг
МУмаркераДостиг
рСигн
где Е – пустой оператор.
4. Функции:
.:
;:
;:
;][:
отне
отне
отне
массивмассивШейкер
массивмассивПузырек
массивмассивРаствор
СССортНовый
→
→
→
→
5. Аксиомы:
.)(:3@
;)(:2@
;)(:1@
отне
отне
отне
массивмассивШейкер
массивмассивПузырек
массивмассивРаствор
→
→
→
Таким образом, описанный абст-
рактный тип данных ориентирован на об-
работку массивов. В базисном разделе
описываются необходимые для обработки
данные. Сигнатура содержит необходимый
набор операторов и предикатов, информа-
ционным множеством которых выступает
базис. Далее перечисляются функции, мо-
делирующие соответствующие операции
абстрактного типа данных Сорт. И завер-
шает описание раздел аксиом. Следует
отметить, что данный пример не содержит
раздел предусловий в виду отсутствия час-
тично определенных функций.
Следующим и завершающим этапом
является построение эффективного Класса
Сорт на основе вышепостроенного АТД
Сорт:
Эффективный Класс Сорт:
1. Тип:
АТД Сорт.
2. Базис:
{ }
{ }
{ }
.
,,1_
|_
,_
|_
_
|
}_{
|
⎭
⎬
⎫
⎩
⎨
⎧
=
⎭
⎬
⎫
⎩
⎨
⎧
=
⎭
⎬
⎫
⎩
⎨
⎧
=
⎭
⎬
⎫
⎩
⎨
⎧
=
∪
УNУмассиваУказатели
массиваУказатели
КНмассиваМаркеры
массиваМаркеры
цепочкиСимвольныеМассивы
Массивы
массивыЧисловыеМассивы
Массивы
Базис
K
3. Функции:
Раствор ::= {[ Достиг_маркера(У, К) ]
([ l>r | У ] Трансп( l,r | У )*
Уст_на_маркер(У, Н), Сдвиг_вправо(У))}
Пузырек ::= {[ Упорядочен(массив) ]
{[ Достиг_маркера(У1, К) ]([ l>r | У1]
Трансп(l,r | У1), Е)* Сдвиг_вправо(У1)}*
Уст_на_маркер(У1, Н)}
Шейкер ::=
{[Упорядочен_отрезок[У4,У2]]
{[ Достиг_указатель(У1,У2)]
( [l>r | У1] Трансп(l,r | У1)*
Уст_на_указатель(У3, У1), Е )*
Сдвиг_вправо(У1) }*
Уст_на_указатель(У2, У3)*
Уст_на_указатель(У1, У2)*
( [Упорядочен_отрезок(У4, У2) ] Е,
14
Теоретичні та методологічні основи програмування
{ [Достиг_указатель[У1,У4]
( [ l>r | У1] Трансп(l,r | У1)*
Уст_на_указатель(У3,У1), Е )*
Сдвиг_влево(У1) }*
Уст_на_указатель(У4,У3)*
Уст_на_указатель(У1,У4) )}
4. Интерфейс:
( )
( )
( )
.
,
,
,
⎪
⎪
⎭
⎪
⎪
⎬
⎫
⎪
⎪
⎩
⎪
⎪
⎨
⎧
=
массивШейкер
массивПузырек
массивРаствор
Новый
Интерфейс
Заключение
Таким образом, авторами предло-
жен метод построения расширенного АТД
и алгебраического класса. Преимущества-
ми данного метода являются:
• полученная спецификация АТД яв-
ляется формальным математическим опи-
санием, а не текстом программы;
• модель не несет императивных со-
стояний;
• математическая модель для описа-
ния не всюду определенных операций;
• аксиомы и предусловия выражают
семантику АТД;
• гибким механизмом перехода от
анализа и спецификации к проектирова-
нию и реализации;
• разработка класса происходит в
наиболее общем виде, что необходимо для
повторного использования;
• сокращение времени анализа и раз-
бора программного решения для сторонне-
го программиста.
Сформулирована достаточная пол-
нота расширенного АТД как решение про-
блемы полноты.
В дальнейшем авторы намеревают-
ся провести апробацию данного метода на
разработке WEB-сервиса и реализацию в
виде инструментария АА.
1. Ноден П., Китте К. Алгебраическая алго-
ритмика (с упражнениями и решениями). –
М.: Мир, 1999. – 720 с.
2. Глушков В.М., Цейтлин Г.Е., Ющенко Е.Л.
Алгебра. Языки. Программирование. 3-е
изд., перераб. и доп. – Киев: Наук. думка,
1989. – 376 с.
3. Цейтлин Г. Е. Введение в алгоритмику. –
К.: Сфера, 1999. – 720 с.
4. Андон Ф.И., Дорошенко А.Е., Цейтлин Г.Е.,
Яценко Е.А. Алгеброалгоритмические мо-
дели и методы параллельного программи-
рования. – Киев: Академпериодика, 2007. –
634 с.
5. Цейтлин Г.Е. Алгебраическая алгоритмика: тео-
рия и приложения // Кибернетика и системный
анализ. – 2003. – № 1. – С. 8 – 18.
6. Цейтлин Г.Е., Иовчев В.А., Мусихин А.А.
Ментальные аспекты методов символьной
мультиобработки // Проблеми програму-
вання. – 2008. – № 1. – С. 60 – 67.
7. Иовчев В.А., Мохница А.С. Инструмен-
тальные средства алгебры алгоритмики на
платформе WEB 2.0 // Проблеми програ-
мування. (матеріали конф. УкрПрог-2010).
– 2010. – № 2 – 3. – С. 547 – 556.
8. Иовчев В.А., Мохница А.С. Формальный
метод генерации программ в инструмен-
тальных средствах алгебры алгоритмики //
матеріали конф. TAAPSD’2010.
9. Дорошенко А.Е., Алистратов О.В., Тырчак
Ю.М., Розенблат А.П., Рухлис К.А. Систе-
мы Grid-вычислений – перспектива для на-
учных исследований // Проблеми програ-
мування. – 2005. – № 1. – С. 14 – 38.
10. Dahl O.-J., Dijkstra E. W. and Hoare C.A.R..
Structured Programming. Academic Press.
1972.
11. Parnas D.L. On the Criteria To Be Used in
Decomposing Systems into Modules. Decem-
ber 1972. http://www.cs.umd.edu/class/spring
2003/cmsc838p/Design/criteria.pdf
12. Barbara Liskov, Programming with Abstract
Data Types, in Proceedings of the ACM
SIGPLAN Symposium on Very High Level
Languages, Santa Monica, California. – 1974.
– Р. 50 – 59.
13. Robert T. Johnson, James B. Morris: Abstract
Data Types in the Model Programming
Language. Conference on Data: Abstraction, Defini-
tion and Structure. – 1976. – Р. 36 – 46.
14. John Guttag. Abstract Data Types and the
Development of Data Structures. – 1977.Bern,
June 1997, 2001.
15
Теоретичні та методологічні основи програмування
15. Gougen J.A., Thatcher J.W., Wagner E.G.:
An initial algebra approach to the specifica-
tion, correctness, and implementation of ab-
stract data types. In: Current Trends in Pro-
gramming Methodology, Prentice-Hall,
Englewood Cliffs. – 1978. – Р. 80 – 149.
16. Rod M. Burstall, Joseph A. Goguen: The
Semantics of CLEAR, A Specification
Language. Abstract Software Specifications. –
1979. – Р. 292 – 332.
17. Futatsugi K. et al., Principles of OBJ2, 12th
POPL, ACM. – 1985. – Р. 52 – 66.
18. J. Guttag et al, The Larch Family of Specifi-
cation Languages, IEEE Trans Soft Eng 2(5).
– Sep 1985. – Р. 24 – 365.
19. Dijkstra E.W. A Discipline of Programming,
Prentice-Hall Series in Automatic Computa-
tion. – 1976.
20. Guttag J. V. and Horning J. J. The algebraic
specification of abstract data types., Acta
Informatica. – 1978. – Vol. 10. – 27 p.
21. Bertrand Meyer. Object-Oriented Software
Construction, Second Edition, Prentice Hall. –
1997.
22. The RAISE Method Group. The RAISE De-
velopment Method, – 1999. http://users.iptele
com.net.ua/~agp1/arts/book.pdf.
23. Birrell N.D., Martyn A.Ould. A Practical
Handbook for Software Development. –
February 1988. – 272 p.
24. Erich Gamma, Richard Helm, Ralph Johnson,
and John Vlissides. Design Patterns: Elements
of Reusable Object-Oriented Software, Addi-
son-Wesley. – 1995.
25. Jamie Shield. Towards an Object-Oriented
Refinement Calculus. – 2001. Thesis.
26. Bennet P., Lientz E., Burton Swanson. Problems
in Application Software Maintenance.
Commun. ACM. – 1981. – Р. 763 – 769.
27. Пискунов А.Г. Формализация парадигмы
обьектно-ориентированного программиро-
вания: критика определения Гради Буча, –
2007. http://i.com.ua/~agp1/ru/oopFormalizm
.html
28. Пискунов А.Г. The RAISE Method Group:
Алгебраическое проектирование класса,
2007, http://www.realcoding.net/article/view/
4538
29. Bruce Eckel. Thinking in Java, 4th edition,
2006.
Получено 14.07.2011
Об авторах:
Дорошенко Анатолий Ефимович,
доктор физико-математических наук,
профессор, заведующий отделом теории
компьютерных вычислений,
Иовчев Владимир Александрович,
младший научный сотрудник.
Место работы авторов:
Институт программных систем
НАН Украины,
проспект Академика Глушкова, 40.
03680, Киев-187.
Тел. (044) 526 1538
е-mail: dor@isofts.kiev.ua,
iovchev.v@gmail.com
16
mailto:dor@isofts.kiev.ua
mailto:iovchev.v@gmail.com
Введение
1. Алгебра алгоритмики
2. Техника алгебраического проектирования классов
3. Стиль спецификаций
4. Концепция абстрактного типа данных в АА
5. Расширение абстрактного типа данных
6. Полнота АТД
7. Построение АТД Стек
8. Объектно-ориентированное решение в АА
9. Класс
10. Построение АТД Сорт
Заключение
|