About the method of projecting abstract data type at the algebra of algorithmic
A method of development of extended abstract data type and algebraic class is proposed. This abstract data type is an essential component of the phases of specification and projecting. The problem of completeness of the extended abstract data type is studied and the decision of sufficient completene...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | rus |
| Veröffentlicht: |
Інститут програмних систем НАН України
2018
|
| Schlagworte: | |
| Online Zugang: | https://pp.isofts.kiev.ua/index.php/ojs1/article/view/34 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Problems in programming |
Institution
Problems in programming| id |
pp_isofts_kiev_ua-article-34 |
|---|---|
| record_format |
ojs |
| resource_txt_mv |
ppisoftskievua/d1/c3d1601481da97b0cfc519e1425834d1.pdf |
| spelling |
pp_isofts_kiev_ua-article-342018-07-25T14:00:23Z About the method of projecting abstract data type at the algebra of algorithmic О методе проектирования абстрактного типа данных в алгебре алгоритмики Про метод проектування абстрактного типу даних в алгебрі алгоритміки Doroshenko, A.Yu. Iovchev, V.O. Abstract data types; Algorithmic Algebra Software and its engineering~Abstract data types Абстрактные типы данных: Алгебра алгоритмики Абстрактні типи данних, алгебра алгоритміки A method of development of extended abstract data type and algebraic class is proposed. This abstract data type is an essential component of the phases of specification and projecting. The problem of completeness of the extended abstract data type is studied and the decision of sufficient completeness is proposed. Предлагается метод проектирования расширенного абстрактного типа данных и алгебраического класса. Данный абстрактный тип данных является необходимым ключевым звеном между этапами спецификации и проектирования. Рассмотрена проблема полноты расширенного абстрактного типа данных и предложено для этого решение достаточной полноты. Пропонується метод проектування розширеного абстрактного типу даних та алгебраїчного класу. Даний абстрактний тип даних є необхідною ланкою між етапами специфікації та проектування. Розглянута проблема повноти розширеного абстрактного типу даних та запропоновано для цього рішення достатньої повноти. Інститут програмних систем НАН України 2018-07-23 Article Article application/pdf https://pp.isofts.kiev.ua/index.php/ojs1/article/view/34 PROBLEMS IN PROGRAMMING; No 1 (2012) ПРОБЛЕМЫ ПРОГРАММИРОВАНИЯ; No 1 (2012) ПРОБЛЕМИ ПРОГРАМУВАННЯ; No 1 (2012) 1727-4907 rus https://pp.isofts.kiev.ua/index.php/ojs1/article/view/34/37 Copyright (c) 2015 ПРОБЛЕМИ ПРОГРАМУВАННЯ |
| institution |
Problems in programming |
| baseUrl_str |
https://pp.isofts.kiev.ua/index.php/ojs1/oai |
| datestamp_date |
2018-07-25T14:00:23Z |
| collection |
OJS |
| language |
rus |
| topic |
Abstract data types Algorithmic Algebra Software and its engineering~Abstract data types |
| spellingShingle |
Abstract data types Algorithmic Algebra Software and its engineering~Abstract data types Doroshenko, A.Yu. Iovchev, V.O. About the method of projecting abstract data type at the algebra of algorithmic |
| topic_facet |
Abstract data types Algorithmic Algebra Software and its engineering~Abstract data types Абстрактные типы данных: Алгебра алгоритмики Абстрактні типи данних алгебра алгоритміки |
| format |
Article |
| author |
Doroshenko, A.Yu. Iovchev, V.O. |
| author_facet |
Doroshenko, A.Yu. Iovchev, V.O. |
| author_sort |
Doroshenko, A.Yu. |
| title |
About the method of projecting abstract data type at the algebra of algorithmic |
| title_short |
About the method of projecting abstract data type at the algebra of algorithmic |
| title_full |
About the method of projecting abstract data type at the algebra of algorithmic |
| title_fullStr |
About the method of projecting abstract data type at the algebra of algorithmic |
| title_full_unstemmed |
About the method of projecting abstract data type at the algebra of algorithmic |
| title_sort |
about the method of projecting abstract data type at the algebra of algorithmic |
| title_alt |
О методе проектирования абстрактного типа данных в алгебре алгоритмики Про метод проектування абстрактного типу даних в алгебрі алгоритміки |
| description |
A method of development of extended abstract data type and algebraic class is proposed. This abstract data type is an essential component of the phases of specification and projecting. The problem of completeness of the extended abstract data type is studied and the decision of sufficient completeness is proposed. |
| publisher |
Інститут програмних систем НАН України |
| publishDate |
2018 |
| url |
https://pp.isofts.kiev.ua/index.php/ojs1/article/view/34 |
| work_keys_str_mv |
AT doroshenkoayu aboutthemethodofprojectingabstractdatatypeatthealgebraofalgorithmic AT iovchevvo aboutthemethodofprojectingabstractdatatypeatthealgebraofalgorithmic AT doroshenkoayu ometodeproektirovaniâabstraktnogotipadannyhvalgebrealgoritmiki AT iovchevvo ometodeproektirovaniâabstraktnogotipadannyhvalgebrealgoritmiki AT doroshenkoayu prometodproektuvannâabstraktnogotipudanihvalgebríalgoritmíki AT iovchevvo prometodproektuvannâabstraktnogotipudanihvalgebríalgoritmíki |
| first_indexed |
2025-07-17T10:05:43Z |
| last_indexed |
2025-07-17T10:05:43Z |
| _version_ |
1838410551377526784 |
| 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. Построение АТД Сорт
Заключение
|