Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов
На прикладі продемонстрована можливість формалізованого переходу від алгоритму до програми за рахунок розвитку і використання засобів розширеної системи алгоритмічних ал-гебр. Показано можливості перетворення отриманої програми й автоматичного переходу на необхідну мову програмування....
Saved in:
| Date: | 2008 |
|---|---|
| Main Author: | |
| Format: | Article |
| Language: | Ukrainian |
| Published: |
Інститут програмних систем НАН України
2008
|
| Subjects: | |
| Online Access: | https://nasplib.isofts.kiev.ua/handle/123456789/323 |
| 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: | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2008. — N 1. — С. 51-59. — Бібліогр.: 7 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1859895013140332544 |
|---|---|
| author | Акуловский, В.Г. |
| author_facet | Акуловский, В.Г. |
| citation_txt | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2008. — N 1. — С. 51-59. — Бібліогр.: 7 назв. — рос. |
| collection | DSpace DC |
| description | На прикладі продемонстрована можливість формалізованого переходу від алгоритму до програми за рахунок розвитку і використання засобів розширеної системи алгоритмічних ал-гебр. Показано можливості перетворення отриманої програми й автоматичного переходу на необхідну мову програмування.
|
| first_indexed | 2025-12-07T15:54:20Z |
| format | Article |
| fulltext |
Формальні методи розробки програмного забезпечення
© В.Г. Акуловский, 2008
ISSN 1727-4907. Проблеми програмування. 2008. № 1 51
УДК 519.681
В.Г. Акуловский
РЕАЛИЗАЦИЯ ФОРМАЛИЗОВАННОГО ПЕРЕХОДА ОТ
АЛГОРИТМА К ПРОГРАММЕ СРЕДСТВАМИ РАСШИРЕННОЙ
АЛГЕБРЫ АЛГОРИТМОВ
На примере продемонстрирована возможность формализованного перехода от алгоритма к программе
за счет развития и использования средств расширенной системы алгоритмических алгебр. Показаны
возможности преобразования полученной программы и автоматического перехода на требуемый язык
программирования.
Введение
В процессе разработки любого ал-
горитма в некоторый момент времени дос-
тигается такой уровень детализации, после
которого осуществляется переход от алго-
ритма к программе. При этом алгоритм, в
каком бы виде он не был записан, необхо-
димо переписать на выбранном языке про-
граммирования. Отметим, что выбор мо-
мента такого перехода не формализован и
определяется главным образом двумя при-
чинами: квалификацией (предпочтениями)
разработчика и уровнем целевого языка
программирования. На этом этапе разра-
ботки возникают в больших количествах
трудно выявляемые ошибки, вызванные
неадекватностью полученной программы
исходному алгоритму. Наличие таких
ошибок подтверждает тот факт, что сте-
пень детализации алгоритма в существен-
ной мере определяет качество получаемой
программы (т.е., чем детальнее проработан
алгоритм, тем выше качество программы).
Таким образом, очевидно, что для
минимизации числа ошибок подобного
рода необходимо, во-первых, обеспечить
возможность детализации алгоритма до
максимально низкого уровня, во-вторых,
автоматизировать процесс перехода от ал-
горитма к программе.
Для решения этой задачи формали-
зуем процесс перехода от алгоритма к про-
грамме, для чего воспользуемся расши-
ренной системой алгоритмических алгебр
(САА-Р), предложенной в [1], которая вос-
ходит к системе алгоритмических алгебр
(САА) В. Глушкова [2, 3]. При этом
применим простой прием. Будем
осуществлять детализацию алгоритма до
тех пор, пока каждый оператор алгебры не
будет описывать одну операцию, опре-
деленную на элементарных данных и
доступную в некотором (целевом) языке
программирования. Заметим, что эле-
ментарными будем считать данные, допус-
кающие обработку с помощью одного
оператора (одной операции целевого
языка).
Поскольку данные являются важ-
нейшей и неотъемлемой составляющей
любой программы, то для “плавного” пе-
рехода от алгоритма к программе необхо-
димо включить в рассмотрение данные на
этапе разработки алгоритма. С этой целью
модифицируем САА-Р таким образом,
чтобы формализовать взаимосвязь опера-
торов и данных.
Формализация данных в расширенной
алгебре алгоритмов
Для включения в рассмотрение
данных, воспользуемся абстрактной
моделью ЭВМ [2, 3] в трактовке,
предложенной в [4]. В данной трактовке в
качестве управляющего автомата УА рас-
сматривается произвольный алгоритм, в
качестве автомата операционного ОА –
обрабатываемая этим алгоритмом инфор-
мация (множество данных ∆). Выходные
сигналы А управляющего автомата УА
отождествляются с операторами, которые
изменяют данные, т.е. состояние опе-
рационного устройства ОА. Выходные
сигналы операционного автомата, пред-
ставляют собой значения различных эле-
ментарных логических условий α, харак-
Формальні методи розробки програмного забезпечення
52
теризующих значения данных и/или соот-
ношения между ними.
Разобъем множество ∆ на два непе-
ресекающихся подмножества ∆=DS∪DD,
где
DS – статические данные, которые
можно интерпретировать как данные, рас-
положенные в оперативной памяти;
DD – динамические данные, кото-
рые можно интерпретировать как данные,
расположенные в регистровой памяти, т.е.
динамически изменяемые данные,
нефиксируемые в памяти.
Известные основные понятия (опе-
ратор, операция, логическое условие),
введенные в САА [2, 3] и расширенные в
САА-Р [1] будем интерпретировать в соот-
ветствии с рассматриваемой трактовкой
абстрактной модели ЭВМ. Отметим, что в
данной работе будут рассмотрены только
те основные алгоритмические конструк-
ции, которые найдут применение при ре-
шении поставленной задачи.
Пусть < U, W, Ω > – САА-Р, где
U – множество операторов; W – множество
логических условий; Ω – сигнатура опера-
ций, состоящая из логических операций –
Ω1, принимающих значения на множестве
W и операций – Ω2, принимающих значе-
ния на множестве операторов U.
Выделим на множестве операторов
два подмножества UUU ′′∪′= , где опе-
раторы из множества U ′ изменяют стати-
ческие (из множества DS), операторы из
множества U ′′ динамические (из множе-
ства DD) данные.
Операторы из множества U ′ опре-
делим таким образом:
DDA ′′=′)( UA ′∈∀ , SDD D∈, ′′′∀ .
Множество данных D′– область определе-
ния, а множество данных D ′′ – область зна-
чений операторов из U ′и для множеств D′
и D ′′ может выполняться любое из
следующих соотношений:
DD ′′⊆′ , DD ′⊆′′ , ∅≠′′∩′ DD ,
∅=′′∩′ DD , DD ′′=′ .
Такой оператор будем называть би-
нарным. Запишем его в виде )DA(D ′′′ )( .
В частном случае, когда DD ′′=′ ,
оператор запишем в виде )(DA ′ и назовем
унарным.
Операторы из множества U ′′
определим так:
D)D(A ′′=′′ U ′′′∈A∀ , DSD ∈′∀ ,
DDD ∈′′∀ (1)
и только после выполнения данных
операторов множество DD определено,
т.е. эти данные доступны для анализа.
Множество D′– область определения,
множество D ′′ – область значений
операторов из U ′′ . Для множеств D′ и D ′′
естественно выполняется соотношение
∅=′′∩′ DD . Оператор будем записывать
в виде )(DA ′′ .
Можно сказать, что оператор
U)DA(D ′∈′′′ )( отличается от оператора
UDA ′′∈′′ )( тем, что первый изменяет дан-
ные множества DS , т.е. изменяет данные в
оперативной памяти, а второй на данные
не влияет.
Множество операторов U включают
тождественный оператор, не изменяющий
множества данных ∆, который определим
таким образом:
DDE =)( ∆∈∀D (2)
и будем записывать в виде Е.
Определим операции на множестве
W.
Множество предикатов P, опреде-
ленных на множестве ∆, введем следую-
щим образом:
DDDp =α= )()( , Pp ∈∀ ,
∆∈∀D , ∅≠D . (3)
Результатом вычисления предиката явля-
ется логическое условие α(D), характери-
зующее текущее состояние множества
данных ∆∈D , состояние операционного
автомата (ОА), которое при вычислении
предиката p не изменяется.
Элементы множества P принимают
истинные значения трехзначной логики
Е3 = {0, 1, µ}, где 0 – ложь, 1 – истина,
µ – промежуточное значение. На множес-
тве Е3 введено отношение порядка < так,
что 0 < µ < 1 и известны обобщенные ло-
гические операции (дизъюнкция, конъюн-
Формальні методи розробки програмного забезпечення
53
кция, отрицание, циклическое отрицание)
со своими таблицами истинности [1, 5–7].
Кроме этих операций определим
операцию (введенную В.М. Глушковым
[2, 3]), позволяющую осуществлять про-
гнозирование вычислительного процесса.
В предлагаемой работе реализуем
данную возможность так. Операцию
левого умножения предиката на оператор
в общем случае с учетом определений
(1), (3) запишем таким образом:
)Dα()Dp())D(Ap()pD(A ′′=′′=′′=′′
DSD ∈∀ ′ , DDD ∈∀ ′′ , UDA ′′∈′′∀ )( .
(4)
Результатом выполнения данной
операции является условие )(D ′′α ,
характеризующее изменение состояния
множества данных DS, соответствующее
тому, которое было бы получено после
выполнения оператора UDAD ′∈′′′ )()( .
Однако, статические данные множества DS
при этом остаются неизменными, так как
при UDA ′′∈′′ )( DDD ∈′′ .
Смысл данного оператора состоит в
прогнозировании вычислительного про-
цесса, а результат выполнения такого
оператора – логическое условие )(D ′′α ,
которое является прогнозом выполнения
оператора UDAD ′∈′′′ )()( .
Операции, определенные на мно-
жестве операторов U, введем таким
образом.
Композиция (последовательное
выполнение). Композиция операторов
)D)B(D)*(D)A(D(
~~ˆˆ ′′ ,
U)∈D)B(D()D)A(D∀( ′′′ ~~
,ˆˆ , ∆D,D,D,D ∈∀ ′′ ~~ˆˆ
означает, что последовательно выполня-
ются сначала оператор )D)A(D( ˆˆ ′ , затем
)
~
()
~
( DBD′ .
Рассмотрим два возможных вари-
анта данной операции.
Первый – когда ,ˆˆ )D)A(D( ′
U)D)B(D( ′∈′ ~~
. При этом некоторое
состояние множества DS, полученное
после выполнения оператора )D)A(D( ˆˆ ′ ,
поступает (передается) оператору
)D)B(D(
~~′ .
Второй – когда U)DA( ′′∈ˆ ,
а U)D)B(D( ′∈′ ~~
тогда операция записыва-
ется в виде
)D
~
)B(D
~
)*(D̂A( ′ . (5)
В данном случае оператору )D)B(D(
~~′
передается состояние множества
∆ = DS ∪ DD.
Отметим, что операцию компози-
ции операторов “*” в очевидных случаях
будем опускать.
αααα −−−− итерация )}D)A(D{(α(D)
′′′ (со-
ответствует программной конструкции
WHILE). Операция α-итерации оператора
)()( DAD ′′′ состоит сначала в проверке ус-
ловия )(Dα , затем, если условие истинно,
выполняется оператор )()( DAD ′′′ и вновь
проверяется условие )(Dα . Данный
циклический процесс осуществляется до
тех пор, пока условие )(Dα не станет
ложным. Для завершения операции α–
итерация необходимо выполнение такого
соотношения: ∅≠′′∩ DD .
Операция αααα3 – дизъюнкция
))()()
~
()
~
()ˆ()ˆ(()( DCDDBDDADD ′′′∨′′′∨′′′α
((
.
Данная операция, об удобстве и
эффективности изложена в [5, 6]. Она
ориентирована на использование трех-
значных логических условий, которую
запишем в виде
µ=α′′′
=α′′′
=α′′′
=
=′′′∨′′′∨′′′α
;(D) если ),()(
;0(D) если ),
~
()
~
(
1;(D) если ),ˆ()ˆ(
))()()
~
()
~
()ˆ()ˆ(()(
DCD
DBD
DAD
DCDDBDDADD
((
((
где DSDDDDDD ∈′′′′′′′′′
((
,,
~
,
~
,ˆ,ˆ , DDD ∈ ,
∅≠D .
Результат выполнения данной кон-
струкции – выполнение одного из трех
возможных операторов, выбирающегося в
соответствии со значением логического
условия )(Dα , и принимающего истинные
значения трехзначной логики Е3.
Формальні методи розробки програмного забезпечення
54
αααα–дизъюнкция, которая вводится
как частный случай α3 – дизъюнкции (с
учетом (2)), записывается в виде
[ ]
=α′′′
=α′′′
=
=∨′′′∨′′′α=
=′′′∨′′′α
;0(D) если ),
~
()
~
(
1;(D) если ),ˆ()ˆ(
))
~
()
~
()ˆ()ˆ(()]([
))
~
()
~
()ˆ()ˆ(()(
DBD
DAD
EDBDDADD
DBDDADD
и обеспечивает выбор одного из двух опе-
раторов в зависимости от значения логиче-
ского условия (D)α .
αααα-фильтрация (последовательная
фильтрация), – частный случай α–
дизъюнкции
E))DA(DD)]([αDADD)][α ∨′′′=′′′ ˆ)ˆ(())ˆ()ˆ(((
и обеспечивает выполнение оператора
)DA(D ′′′ ˆ)ˆ( только при истинном значении
(D)α .
Отметим, что в качестве логиче-
ского условия в операциях α3 – дизъюнк-
ция, α – дизъюнкция, α – фильтрация и
α − итерация могут выступать предикат и
операции левого умножения предиката на
оператор и, что данные операции
записываются аналогично в случае
унарных операторов.
Предлагаемый подход позволил в
рамках САА-Р включить в рассмотрение
данные, т.е. специфицировать взаимосвязи
между операторами и данными. При этом
сохраняются все возможности по по-
строению производных алгоритмических
конструкций и преобразованию регуляр-
ных схем (РС), которые являются средст-
вом описания алгоритма рассматриваемого
формального аппарата.
Разработка алгоритмов на требуемом
уровне детализации
Наиболее наглядным способом
продемонстрировать возможности предла-
гаемого подхода является решение кон-
кретной задачи, что мы и сделаем, выбрав
некоторую элементарную задачу. Данная
задача, иллюстративная, по мнению
автора, не носит, отвлеченного от
практических задач характера. Будем
полагать, что в процессе декомпозиции
некоторого алгоритма, возникла
следующая подзадача.
Имеется два массива:
X = x1,x2,…,xk ,
Y = y1,y2,…,yn, .
Необходимо вычислить сумму элементов
массива Х, если k < n, сумму элементов
массива Y, если k > n. В том случае, когда
k = n необходимо, если k четное переста-
вить элементы массива X на место одно-
именных элементов массива Y, а в против-
ном случае – переставить элементы мас-
сива Y на место одноименных элементов
массива X.
Запишем требуемый алгоритм в
виде следующей регулярной схемы:
,))),()(),()]((([
)()()()((
),(),,(
YXперестXXYперестY
YсумSXсумS
YXAYXS
∨β∨
∨∨α=
=
где α – условие k < n ;
β–условие k-четное;
(S)сум(Х) – оператор, суммирую-
щий элементы массива Х;
(S)сум(Y) – оператор, суммирую-
щий элементы массива Y;
(Y)перест(Y,Х) – оператор, пере-
ставляющий элементы массива Х на место
одноименных элементов в массив Y;
(X)перест(X,Y) – оператор, пере-
ставляющий элементы массива Y на место
одноименных элементов в массив X.
В данном алгоритме мы воспользо-
вались операцией α3 – дизъюнкции,
поэтому остановимся на работе данной
операции.
Известно, что предикат – это функ-
ция, вычисляющая некоторое отношение,
определенное на множестве данных. В
большинстве языков программирования
используются (и поддерживаются аппа-
ратно) следующие отношения: “<”, ”>”,
≠=≥≤ ,"","","" . Будем считать, что в
операторе α3 – дизъюнкции используются
только отношения “<”, “>”. В результате
вычисления которых логическое условие
принимает значение 1(истина), в случае
если отношение выполняется, 0 (ложь) –
Формальні методи розробки програмного забезпечення
55
противоположного значения и µ
(промежуточное значение) – равенства
сравниваемых величин.
Очевидно уровень детализации
приведенного алгоритма можно переписы-
вать в виде программы на некотором языке
программирования. В данном случае реа-
лизацию всех алгоритмических конструк-
ций необходимо переписать в терминах
языка программирования. Затем принять
решения о программной реализации
операции суммирования и перемещения
массивов. Мы не будем проходить этот
традиционный путь, а осуществим более
глубокую детализацию РС.
Для построения алгоритмов тре-
буемого уровня детализации необходимо
строить алгоритмические конструкции,
адекватные языковым конструкциям.
САА-Р предоставляет достаточно богатые
возможности построения таких конструк-
ций. В частности, в данном случае опера-
цию суммирования и перестановки эле-
ментов массива естественно (для боль-
шинства языков программирования) реа-
лизовать с помощью конструкции типа
оператора for.
Построим в общем виде данную
широко применяемую алгоритмическую
конструкцию, которой воспользуемся для
решения рассматриваемой задачи.
Известно, что она легко реализуется как
частный случай α-итерации, т.е.
циклической конструкции типа WHILE:
)S(D)}DA(D{
p(D)
I(D) ˆ)ˆ( ′ , (6)
где I(D) – оператор инициализации
переменных цикла;
(D)Dp α=)( – условие
завершения цикла;
)DA(D ˆ)ˆ( ′ – тело цикла;
S(D) – оператор, изменяющий
переменные цикла.
Построенную конструкцию запи-
шем в виде
{ }.ˆ)ˆ())();();(( )DA(DDSDPDI ′ .
Далее будем полагать (как вышеот-
меченно), что на данном этапе де-
композиции алгоритма любой оператор
алгебры реализуют одну элементарную
операцию над данными, а предикат вычис-
ляет элементарное бинарное отношение.
Введем и традиционно обозначим такие
элементарные операторы, выполняющие
соответствующие элементарные операции:
“:=” – присваивание; “+” – сложение; “++”
– инкремент; “%” – остаток от деления и
отношения “<” – меньше; “=” – равно.
Будем полагать, что элементы мно-
жества обрабатываемых данных ∆ – это
объекты, обладающие именем и зна-
чением, которые мы будем называть пе-
ременными и указывать в РС. Кроме того,
множество данных содержит константы.
Будем полагать, что элементы массивов
нумеруются с нуля.
С помощью введенного оператора
типа for, запишем РС для случая суммиро-
вания элементов массива X в виде:
}.:{);;0:*0:(
)(сум)(
i
xSSikiSi
XS
+=++<===
=
Отметим, что в данном случае для по-
вышения читабельности мы опустили
скобки при записи операторов, т.е.,
записали бинарный оператор )0(:)( =i в
виде 0:=i , унарный оператор )(i++ в
виде i++ . В последующем изложении
будем придерживаться таких обозначений.
Кроме того, отметим, что оператор S:=S+xi
реализуется композицией операторов
U ′′∈+ и U ′=∈: в соответствии с (5).
Для случая перестановки элементов
массива Y на место элементов массива X
РС запишем в виде:
{ }.:);;0(
),()(
ii yxikii:
YXперестX
=++<==
=
Операторы (S)сум(Y) и (Y)перест(Y,X)
реализуются аналогично, а РС будет вы-
глядеть таким образом:
})).:){;;0(
}:){;;0(02(
}:){;;0:*0:(
}:){;;0:*0:(
),i,,,,(),,,(
i
x
i
yikii:
i
y
i
xikii:k%
i
ySSikiSi
i
xSSikiSink
nkSYXAiSYX
=++<=∨
∨=++<==∨
∨+=++<==∨
∨+=++<==<=
=
][
Заметим, что при вычислении
условия ]02%[ =k использована операция
левого умножения бинарного оператора
Формальні методи розробки програмного забезпечення
56
Uk ′′∈2% на предикат (см. определение
(4)).
Приведенный алгоритм внешне
напоминает программу, при этом всем
алгоритмическим конструкциям соответ-
ствуют языковые конструкции. Таким
образом алгоритм, очевидно, может быть
не только легко переписан на требуемый
язык программирования, но и
автоматически преобразован в программу
на этом языке. Для этого необходимо
заменить алгоритмические конструкции
соответствующими конструкциями языка
программирования. Учитывая, что
программа – это форма записи алгоритма в
терминах конкретного языка программи-
рования, введем следующее определение.
В рамках применяемого формаль-
ного аппарата программой на языке РС бу-
дем называть алгоритм, степень декомпо-
зиции и набор используемых алгоритми-
ческих конструкций которого таковы, что
каждой операции и каждому оператору
алгоритма можно поставить в соответствие
адекватные оператор и операцию неко-
торого языка программирования.
Важно заметить, несмотря, что в
соответствии с приведенным оп-
ределением, мы получили программу на
языке РС, которая остается под
“юрисдикцией” формального аппарата.
Таким образом, можно воспользоваться
возможностями для преобразования
программы. Предварительно заметим, что
в процессе преобразований используем как
общие свойства РС, так и специфические
особенности рассматриваемой программы.
Обратив внимание на наличие в
программе вложенной α-дизъюнкции,
рассмотрим её отдельно и постараемся
исключить из программы.
{ }
{ }.:);;0:(
:);;0:](02%[
i
x
i
yikii
i
y
i
xikiik
=++<=∨
∨=++<==
Для этого, воспользуемся тем, что исполь-
зуемые циклы однотипны и просто органи-
зованы, перейдем от цикла for к циклу
WHILE (α−итерация).
В качестве первого шага, учитывая
тождественное соотношение вида
{ }
{ }
{ })D)A(D();S(D))I(D)*(;P(D
)D)A(D(D);S(D))I(D)*(E;P(
)D)A(D(;S(D))(I(D);P(D)
ˆˆ
ˆˆ
ˆˆ
′=
=′=
=′
(7)
вынесем оператор i:=0 из цикла, в резуль-
тате чего цикл, например, перестановки
элементов массива Y на место элементов
массива X может быть записан в виде
}.:){;(;*0:
}:){;;0:(
i
y
i
xikii
i
y
i
xikii
=++<==
==++≤=
Преобразуем в соответствии с (6) данный
цикл в цикл типа while: { }
.}*:{*0:
:);(;*0:
i
i
y
i
x
ki
i
i
y
i
xikii
++=<==
==++≤=
Удобным, в полученном варианте цикла,
представляется применение операции ле-
вого умножения оператора на предикат
(см. определение (4)). Однако, в этом
случае следует учитывать, что инкремент
переменной i будет осуществляться до
входа в цикл, а не после выполнения
цикла. Для исключения нежелательного
эффекта следует предварительно умень-
шить эту переменную цикла на единицу и
записать следующий его вариант в виде:
}
i
y:
i
x{
ki
*1:i =<++−= .
Цикл, переставляющий элементы массива
X на место элементов массива Y, работает
и записывается аналогично. В результате
проведенных преобразований вложенная
α-дизъюнкция может быть записана в виде
.}):{*1:
}:{*1:](02%[
i
x
i
y
ki
i
i
y
i
x
ki
ik
=<++−=∨
∨=<++−==
Далее, воспользовавшись тождест-
венным соотношением вида
))()()
~
()
~
](()[ˆ()ˆ(
)()(*)ˆ()ˆ(
)
~
()
~
(*)ˆ()ˆ](([
DCDDBDαDAD
DCDDAD
DBDDADα
′′′∨′′′′′=
=′′′′′∨
∨′′′′′
((
((
вынесем оператор i:=-1 за оператор
α-дизъюнкции. Кроме того, применив
тождественным соотношением вида:
)8())}ˆ()ˆ()())]((
~
({[
)(
)}ˆ()ˆ{(
)(
)}(){(
)(
](
~
[[
DBDDADDβ
Dα
DBD
DαDAD
DαDβ
′∨′′′=
=′∨′′′
можно внести оператор α – дизъюнкций
Формальні методи розробки програмного забезпечення
57
внутрь цикла. Однако на применение
данного соотношения накладываются оче-
видные ограничения вида:
∅=∪′∅=∪′′ DDDD
~ˆ,
~
, обусловленные
тем, что в исходном операторе условие
)Dβ(
~
проверяется однократно, а в
результирующем в процессе всего времени
работы цикла. В нашем случае эти ограни-
чения удовлетворяются и, таким образом,
искомая конструкция может быть записана
в виде
}::](02%{[*1:(
i
x
i
y
i
y
i
xk
ki
i =∨==<++−=
Перепишем всю программу с
учетом полученного результата:
})).:
:](02%{[*1:(
}:){;;0:*0:(
}:){;;0:*0:(
),i,,,,(),,,(
i
x
i
y
i
y
i
xk
ki
i
i
ySSikiSi
i
xSSikiSink
nkSYXAiSYX
=∨
∨==<++−=∨
∨+=++<==∨
∨+=++<==<=
=
Полученная программа теперь не
содержит вложенной α-дизъюнкции, но
представляет собой оператор α3–дизъюнк-
ция, которая в настоящее время не под-
держивается языками программирования.
Учитывая это, приведем α3 – дизъюнкцию
к последовательности α – дизъюнкций:
})).:
:](02%{[*1:(
}:){;;0:*0:]([
}:){;;0:*0:]([
),i,,,,(),,,(
i
x
i
y
i
y
i
xk
ki
i
i
ySSikiSink
i
xSSikiSink
nkSYXAiSYX
=∨
∨==≤++−=∨
∨+=++<==>∨
∨+=++<==<=
=
Заметим, что операция α3 –
дизъюнкция в данном случае пре-
образована “вручную” для дальнейшего
преобразования программы. Однако, эта
операция может быть представлена в виде
α – дизъюнкций автоматически, т.е. в ре-
зультате трансляции.
После последнего преобразования
мы снова получили вложенность α–дизъ-
юнкций, т.е. проблему, решенную на
предыдущем шаге преобразований. С уче-
том некоторых несущественных отличий
выполним те же преобразования для уст-
ранения вложенности. В частности, выне-
сем за операцию цикла операторы S:= 0 и
i:= –1 (в соответствии с (7)) а цикл, сумми-
рующий элементы массива Y, преобразуем
к циклу типа while (в соответствии с (6)) .
В результате получаем выражение вида
})).:
:](02%{[*1:
}:{*0:*1:]([
}:){;;0:*0:]([
),i,,,,(),,,(
i
x
i
y
i
y
i
xk
ki
i
i
ySS
ki
Sink
i
xSSikiSink
nkSYXAiSYX
=∨
∨==<++−=∨
∨+=<++=−=>∨
∨+=++<==<=
=
Далее аналогично предыдущему случаю
внесем оператор α – дизъюнкций внутрь
цикла в соответствии с (8) и получим вы-
ражение:
.}))::](02%[
:]({[*0:*1:(
}:){;;0:*0:]([
),i,,,,(),,,(
i
x
i
y
i
y
i
xk
i
ySSnk
ki
Si
i
xSSikiSink
nkSYXAiSYX
=∨==∨
∨+=><++=−=∨
∨+=++<==<=
=
Выполнив точно такие же преобразования
над последним сохранившимся неиз-
менным фрагментом программы, получаем
программу в окончательном виде:
.)))}:
:](02%[:]([
:]({[*
*0:*1:
),i,,,,(),,,(
i
x
i
y
i
y
i
xk
i
ySSnk
i
xSSnk
ki
Si
nkSYXAiSYX
=∨
∨==∨+=>∨
∨+=<<++
=−=
=
Полученный в результате преобра-
зований алгоритм существенно лучше
(компактнее) исходного, однако, при этом
следует сделать такие замечания.
Формальні методи розробки програмного забезпечення
58
Во-первых, для программы с более
сложной структурой такую степень преоб-
разования реализовать, вероятно, не уда-
лось бы.
Во-вторых, преобразования на
более высоком уровне декомпозиции
алгоритма более эффективны, однако нет
оснований пренебрегать такой воз-
можностью на рассматриваемом уровне.
Для реализации трансляции полу-
ченной на языке РС программы на требуе-
мый язык программирования необходимо
дополнить её указаниями типов перемен-
ных. Это можно сделать как в ручном ре-
жиме (непосредственно перед трансля-
цией), так и в процессе разработки РС,
записав её, например, в виде
.)))}::](02%[
:]([
:]({[*
*0:*1:)int_,int_
,int_,_,_,_(
)int_,_,_,_(
i
x
i
y
i
y
i
xk
i
ySSnk
i
xSSnk
ki
Sink
iSfloatYfloatXfloatA
iSfloatYfloatXfloat
=∨==∨
∨+=>∨
∨+=<<++
=−==
Отметим, что данного этапа можно
избежать, если целевой язык программи-
рования допускает умолчания (как,
например, FORTRAN) или если подобную
систему умолчаний принять при
разработке транслятора. Так же отметим,
что контроль совместимости типов данных
и возможные их преобразования мы
оставляем “на совести” компилятора с
целевого языка программирования.
Заключение
Полученные в работе результаты
демонстрируют возможность построить
алгоритм, степень детализации которого
соответствует уровню языка программи-
рования, т.е., осуществить формализо-
ванный переход от алгоритма к программе.
При этом сохраняются все возможности
формализованного преобразования про-
граммы, предоставляемые формальным
аппаратом. Достигнутый уровень детали-
зации позволяет осуществить автоматиче-
ский переход от алгоритма к программе на
требуемом языке программирования.
Практическое использование полу-
ченных результатов возможно по трем на-
правлениям.
Во-первых, можно за счет разра-
ботки и включения в алгоритм специали-
зированных операторов строить язык, ори-
ентированный на решение некоторого
класса задач. Например, при регулярном
решении класса задач, аналогичных при-
веденной в качестве примера, следует
включить в язык в качестве элементарных
операции суммирования и перемещения
массивов.
В этом случае, естественно, возни-
кает непростая проблема трансляции соз-
данного языка. Если указанная проблема
будет решена, то это явится средством,
позволяющим реализовать призыв извест-
ного специалиста в области программиро-
вания К. Хоар к тому, чтобы отказаться от
языков-монстров, а использовать
небольшие специализированные языки.
Более того, уровень специализации языка
может быть достигнут сколь угодно
глубокий, т.е. класс решаемых задач может
быть сколь угодно узким. Такая
специализация может в существенной мере
положительно повлиять на качество
программных продуктов.
Во-вторых, можно разработать
транслятор, осуществляющий перевод не-
посредственно из РС (с языка регулярных
схем) в машинный код. Однако, это весьма
затруднительно в силу нетривиальности
задачи разработки компилятора.
В-третьих, можно в процессе разра-
ботки ориентироваться на конкретный
язык программирования и осуществлять
трансляцию путем разработки и после-
дующей замены конструкций РС, адекват-
ными языковыми конструкциями. При
этом можно повысить читабельность РС,
за счет подбора системы обозначений
наиболее соответствующих синтаксису
целевого языка. В данной работе мы не
ориентировались на какой-либо конкрет-
ный язык программирования, хотя влияние
языка Си, заметно.
Формальні методи розробки програмного забезпечення
59
Так как последнее направление
наиболее просто в реализации, в качестве
ближайшей перспективы в дальнейшей
работе назовем реализацию рассмотрен-
ных возможностей для конкретных при-
ложений и для конкретного языка про-
граммирования.
1. Акуловский В.Г. Расширенная алгебра алго-
ритмов // Проблеми програмування. –
2007. – № 3. – С. 3 – 15.
2. Глушков В.М., Цейтлин Г.Е., Ющенко
Е.Л. Алгебра. Языки. Программирование. –
Киев: Наук. думка, 1978. – 319 с.
3. Андон Ф.И., Дорошенко А.Е., Цейтлин
Г.Е., Яценко Е.А.. Алгеброалгоритмические
модели и методы параллельного про-
граммирования. – Киев: Академпериодика,
2007. – 634 с.
4. Ющенко Е.Л., Цейтлин Г.Е., Грицай В.П.,
Терзян Т.К. Многоуровневое структурное
проектирование программ: Теоретические
основы, инструментарий. – М.: Финансы и
статистика, 1989. – 208 с.
5. Брусенцов Н.П., Владимирова Ю. С. Ком-
пьютеризация булевой алгебры // Доклады
Академии наук, 2004. – Т. 395. – № 1.
6. Брусенцов Н.П. Кибернетика – ожидания и
результаты. Политехнические чтения. –
М.: Знание, 2002. – Вып. 2. – С. 104 – 105.
7. Поспелов Д.А. Логические методы анализа
и синтеза схем. Изд. 3-е, перераб. и доп. –
М.: Энергия, 1974. – 368 с.
Получено 01.11.2007
Об авторе:
Акуловский Валерий Григорьевич,
кандидат технических наук, доцент
кафедры информационных систем и
технологий.
Место работы автора:
Академия таможенной службы Украины,
49000, Днепропетровск, ул. Дзержинского
2\4.
Тел/факс.: (0562) 45 5596;
тел.: (0562) 67 5004;
моб.: тел. 8050–9410566.
e-mail: akulovski@rambler.ru
e-mail: academy@amsu.dnp.ukrpack.net
|
| id | nasplib_isofts_kiev_ua-123456789-323 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1727-4907 |
| language | Ukrainian |
| last_indexed | 2025-12-07T15:54:20Z |
| publishDate | 2008 |
| publisher | Інститут програмних систем НАН України |
| record_format | dspace |
| spelling | Акуловский, В.Г. 2008-03-31T13:17:25Z 2008-03-31T13:17:25Z 2008 Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов / В.Г. Акуловский // Пробл. програмув. — 2008. — N 1. — С. 51-59. — Бібліогр.: 7 назв. — рос. 1727-4907 https://nasplib.isofts.kiev.ua/handle/123456789/323 519.681 On an example of the opportunity of the formalized transition from algorithm to the program showed due to development and use of means of the expanded system of algorithmic algebras. There are showed the opportunities of transformation of the received program and auto-matic transition to the required programming lan-guage. На прикладі продемонстрована можливість формалізованого переходу від алгоритму до програми за рахунок розвитку і використання засобів розширеної системи алгоритмічних ал-гебр. Показано можливості перетворення отриманої програми й автоматичного переходу на необхідну мову програмування. uk Інститут програмних систем НАН України Формальні методи розробки програмного забезпечення Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов Realization of the formalized transition from algorithm to program, using means of the expanded algebra of algorithms Article published earlier |
| spellingShingle | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов Акуловский, В.Г. Формальні методи розробки програмного забезпечення |
| title | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов |
| title_alt | Realization of the formalized transition from algorithm to program, using means of the expanded algebra of algorithms |
| title_full | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов |
| title_fullStr | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов |
| title_full_unstemmed | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов |
| title_short | Реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов |
| title_sort | реализация формализованного перехода от алгоритма к программе средствами расширенной алгебры алгоритмов |
| topic | Формальні методи розробки програмного забезпечення |
| topic_facet | Формальні методи розробки програмного забезпечення |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/323 |
| work_keys_str_mv | AT akulovskiivg realizaciâformalizovannogoperehodaotalgoritmakprogrammesredstvamirasširennoialgebryalgoritmov AT akulovskiivg realizationoftheformalizedtransitionfromalgorithmtoprogramusingmeansoftheexpandedalgebraofalgorithms |