Язык блок-схемы
| Парадигма | императив |
|---|---|
| Разработано | Карстен К. Гомар, Нил Д. Джонс, Джон Хэтклифф |
| Впервые появился | 1989, 1993, 1998 |
Язык блок-схем (FCL) — простой императивный язык программирования, предназначенный для объяснения фундаментальных концепций анализа и специализации программ, в частности, частичной оценки . Язык был впервые представлен в 1989 году Карстеном К. Гомаром и Нилом Д. Джонсом. [1] Позже это снова всплыло в их книге с Питером Сестофтом. [2] в 1993 году и в конспектах лекций Джона Хэтклиффа. [3] в 1998 году. Ниже описывается FCL в том виде, в каком он появился в конспектах лекций Джона Хэтклиффа.
FCL — это императивный язык программирования, близкий к тому, как компьютер фон Неймана выполняет программу. Программа выполняется последовательно, следуя последовательности команд, сохраняя при этом неявное состояние, то есть глобальную память. В FCL нет понятия процедур, но предусмотрены условные и безусловные переходы. FCL оправдывает свое название, поскольку абстрактный граф вызовов программы FCL представляет собой простую блок-схему.
Программа FCL принимает в качестве входных данных конечный ряд именованных значений в качестве параметров и в результате выдает значение.
Синтаксис
[ редактировать ]Мы указываем синтаксис FCL, используя форму Бэкуса-Наура .
Программа FCL представляет собой список объявлений формальных параметров, метку записи и последовательность базовых блоков :
<p> ::= "(" <x>* ")" "(" <l> ")" <b>+Изначально язык допускает только неотрицательные целочисленные переменные.
Базовый блок состоит из метки, списка назначений и перехода.
<b> ::= <l> ":" <a>* <j>Присвоение присваивает переменную выражению. Выражение представляет собой либо константу, либо переменную, либо применение встроенного n-арного оператора:
<a> := <x> ":=" <e><e> := <c> | <x> | <o> "(" <e>* ")"Обратите внимание, что имена переменных, встречающиеся в программе, не обязательно объявляются в верхней части программы. Переменные, объявленные в верхней части программы, обозначают аргументы программы.
Поскольку значения могут быть только неотрицательными целыми числами, то же самое можно сказать и о константах. Список операций в целом не имеет значения, если они не имеют побочных эффектов , включая исключения, например, деление на 0:
<c> ::= "0" | "1" | "2" | ...<o> ::= "+" | "-" | "*" | "=" | "<" | ">" | ...Где = , < , ... имеют семантику, как в C. Семантика - таков, что если xy<0, то xy=0.
Пример
[ редактировать ]Мы пишем программу, которая вычисляет n й Число Фибоначчи для n>2:
(n)(init)init: x1 = 1 x2 = 1fib: x1 = x1 + x2 t = x1 x1 = x2 x2 = t n = -(n 1) if >(n 2) then fib else exitexit: return x2
Где инвариант цикла Фиб заключается в том, что x1 — это (i+2-1) й и x2 - это (i+2) й Число Фибоначчи, где i — количество раз fib был переключен.
Проверить корректность метода для n=4 можно, представив трассировку выполнения программы:
![{\displaystyle {\begin{aligned}&\left({\mathtt {init}},\\left[n\mapsto 4,\x1\mapsto 0,\x2\mapsto 0,\t\mapsto 0\right] \right)\\\rightarrow &\left({\mathtt {fib}},\\left[n\mapsto 4,\x1\mapsto 1,\x2\mapsto 1,\t\mapsto 0\right]\right )\\\rightarrow &\left({\mathtt {fib}},\ \left[n\mapsto 3,\ x1\mapsto 1,\ x2\mapsto 2,\ t\mapsto 0\right]\right)\ \\rightarrow &\left(\left\angle {\mathtt {halt}},\3\right\angle,\\left[n\mapsto 2,\x1\mapsto 2,\x2\mapsto 3,\t\ mapsto 0\right]\right)\end{aligned}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/59d43f26233ae3f742f2ff382a7f8f5fca87f119)
Где отмечает конечное состояние программы с возвращаемым значением .
Варианты
[ редактировать ]Реверсивный язык блок-схемы
[ редактировать ]Язык обратимых блок-схем (RL) — это простой обратимый императивный язык программирования, предназначенный для обратимых вычислений, где каждый вычислительный процесс обратим. [4] RL сочетает в себе этапы, тесты и утверждения таким образом, чтобы обеспечить обратимость программ.
RL делает упор на создание обратимых программ, которые позволяют детерминированные обратные вычисления, гарантируя, что никакая информация не будет потеряна во время обработки. Эта характеристика отличает его от традиционных языков блок-схем, которые обычно включают необратимые операции. Синтаксис и примеры программ для RL очень похожи на традиционные языки блок-схем, но с дополнительными ограничениями для обеспечения обратимости. К ним относятся обратимые циклы, обратимые условия и обратимость шагов атомарных вычислений.
Из-за ограничения обратимости RL имеет меньшую вычислительную мощность, чем обычные машины Тьюринга , но эквивалентен обратимым машинам Тьюринга (RTM) , что закладывает основу для обратимого программирования. обратимый вариант теоремы о структурированной программе Например, можно эффективно анализировать с помощью RL, демонстрируя его значение в теоретических основах обратимых вычислений .Существует также структурированный вариант RL (SRL: язык структурированных обратимых блок-схем). [4] который сочетает в себе последовательность, выбор и итерацию таким образом, чтобы обеспечить обратимость программ.
Ссылки
[ редактировать ]- ^ Карстен К. Гомар и Нил Д. Джонс. Генерация компилятора путем частичной оценки. В GX Ritter, редакторе журнала Information Processing '89. Материалы 11-го Всемирного компьютерного конгресса ИФИП , страницы 1139–1144. ИФИП, Северная Голландия, 1989 г.
- ^ Нил Д. Джонс, Карстен К. Гомард и Питер Сестофт. Частичная оценка и автоматическая генерация программы. С главами Л.О. Андерсена и Т. Могенсена. Prentice Hall International, июнь 1993 г. xii + 415 страниц. ISBN 0-13-020249-5 . Доступно бесплатно по адресу http://www.itu.dk/~sestoft/pebook/pebook.html.
- ^ Джон Хэтклифф. Введение в онлайн- и офлайн-частичную оценку с использованием простого языка блок-схем. Частичная оценка - практика и теория, Международная летняя школа DIKU 1998 г., Джон Хэтклифф, Торбен Э. Могенсен и Питер Тиманн (ред.). 1998. Спрингер-Верлаг, Лондон, Великобритания, 20–82.
- ^ Перейти обратно: а б Ёкояма, Тецуо; Аксельсен, Хольгер Бок; Глюк, Роберт (январь 2016 г.). «Основы обратимых языков блок-схем» . Теоретическая информатика . 611 : 87–115. дои : 10.1016/j.tcs.2015.07.046 .