8463-1 (О возможности универсального кода внутреннего представления программы), страница 2

Алгоритмические формулы (АФ; табл.1, рис.1) представляют собой формальную систему, являющуюся развитием ЯЛС посредством включения в него конструкций, адекватных упомянутому языковому ядру. Главным фактом, лежащим в основе этого формализма, является возможность рассматривать основные элиминаторы оператора перехода – условные операторы, операторы выбора и операторы организации цикла, – как особые (операторные) скобки, в принципе аналогичные обычным по своим свойствам и функциям. В соответствии с этим «программа» рассматривается как скобочное выражение (строка), структура которого оформляется тремя видами скобок: алгебраическими (круглыми), условными (прямыми) и цикловыми (фигурными).

Рис. 1. Алгоритм Евклида нахождения наибольшего общего делителя в представлении различными языками программирования: I – на языке логических схем (Ляпунов, Янов, 1958), II – на одном из наиболее распространенных языков программирования (BASIC) в «старой» (A) и «новой» (B) нотации, III – в виде алгоритмической формулы, адекватной коду формульного процессора

Элементом алгоритмической формулы является оператор, состоящий из имени оператора и списка аргументов, заключенного в алгебраические скобки. Алгоритмическая формула (см. рис.1) является последовательностью операторов, отделяемых друг от друга знаком-разделителем (точка с запятой). Основу формализма составляют оператор сохранения значения (присваивание) и операторы-скобки, именами которых служат символы фигурных (цикловых) либо квадратных (операторы условий и выбора) скобок. Условные и цикловые скобки аналогичны соответствующим операторам большинства распространенных языков (табл.1 и рис.1). Например, открывающая прямая скобка в качестве имени оператора, с логическим условием в качестве единственного аргумента, и парный ей оператор закрывающей скобки, не имеющий аргументов, ограничивают подпоследовательность операторов, выполняющуюся, если выполнено данное логическое условие. Подобные парные операторы, именами которых являются символы скобок, ограничивают подстроку, выполняющуюся кратное число раз, заданное значением параметра цикла, либо в зависимости от выполнения соответствующего логического условия. Оператор присваивания является безымянным, традиционная запись x:=F(y₁,..., y_n) отвечает оператору (x, F(y₁,..., y_n)). Множество всех остальных («именованных») операторов, наборы функций и отношений, как и допустимые классы переменных или иные ограничительные символы, могут быть в той или иной степени специфичными.

Таким образом, алгоритмическая формула отличается от ЯЛС главным образом в том отношении, что, с одной стороны, наиболее последовательно проводится принцип линеаризации записи алгоритма с полностью унифицированным операторным представлением его элементов, с другой – в соответствии со сложившейся практикой в формализм введены наиболее распространённые средства элиминации операторов перехода (операторы-скобки).

В алгоритмических формулах легко усматривается естественное развитие обычной функционально-алгебраической символики. Уже при вычислении простейших выражений возникает необходимость сохранять промежуточные результаты. В обычных (алгебраических или арифметических) формулах этот процесс однозначен. Более общая ситуация требует явного введения ячеек-переменных. Подобным образом, операторы-скобки являются лишь обобщением алгебраических, определяющих последовательность действий с входящими в выражение объектами. В связи с этим мы считаем возможным рассматривать АФ как расширение общематематической семиотики, а не как язык программирования или его математическую модель. Поэтому мы полагаем также допустимыми любые возможные расширения (клоны) этого языка, сколь угодно своеобразные в зависимости от контекста различных сфер его применения. В частности, в соответствующих ситуациях, легко представить применение в составе АФ любой известной общематематической символики – кванторов, производных, интегралов, – и т.п., лишь бы при этом формула оставалась «понятной» в той же, например, степени, в какой понятно доказательство какого-либо математического утверждения, как правило не доводимое до уровня совершенной формально-логической строгости. В этом ракурсе и сам ЯЛС можно трактовать как частный случай или клон АФ.

Можно было бы отдельно рассмотреть вопрос о минимальности набора собственных символов АФ: в сущности достаточна лишь одна разновидность операторных скобок – цикловые, с блокировкой тела цикла при нулевом значении числа повторений. Даже логико-алгебраические формулы для АФ-термов в каком-то смысле являются расширением языка, можно было бы обойтись и чисто функциональной записью выражений. Однако очевидно, что в соответствие с общими тенденциями развития минимальность набора непосредственно выполняемых процессором операций ни в каком отношении не является целью, фактически в качестве таковой выступают достаточно трудно и медленно вырабатываемые иные критерии оптимальности этого набора. Представляемый подход состоит в том, что сущностью АФ объявляется общематематический смысл некоторых специфически программистских по происхождению символов – присваиваний и операторных скобок. Их использование может быть уподоблено практике применения формально-логических по происхождению знаков кванторов или функциональных символов интегрирования и дифференцирования. Конкретизация («локализация») соответствующего формализма в строго определенное исчисление или алгоритмический код так или иначе должна быть привязана к контексту ситуации и в общем виде не производится, как она не производится и для приведенных аналогичных объектов.

В алгебраической интерпретации [6, 10] нормальная (без полускобок Янова) алгоритмическая формула – это свободная конструкция над алгеброй функций внутренних состояний (ВС) некоего автоматического устройства (АУ) и тем или иным множеством именованных операторов, выделенное подмножество которых характеризуется как «действия» АУ, а остальные выступают в роли вызовов подпрограмм (т.е., в конечном счете, как сокращения). При этом, при «выполнении» АФ, из нее удаляются все внутренние переменные и операторы преобразования внутреннего состояния (элиминация ВС), а аргументы остающихся в результирующей строке именованных операторов-действий получают определяемое значение. Таким образом, АФ как формальный объект играет роль шаблона, по которому, при заданном векторе условий, по определенным правилам, вычисляется выходная строка действий АУ.

Синтаксическая правильность АФ складывается из правильности строения термов и операторов, соблюдения парности входящих в неё скобочных операторов и правильности чередования условных и цикловых скобок. Семантическая правильность весьма естественно определяется как элиминируемость ВС на элементах обусловленного подмножества допустимых вариантов входного файла. Семантически тождественные на данном множестве входных условий формулы порождают на нем идентичные последовательности действий, выбор подмножества действий среди операторов, таким образом, предопределяет это отношение.

Операторно-формульная запись алгоритма, в отличие от языкового или командного, наиболее удобна как для исследования, так и машинного анализа, генерации и оптимизации программного кода. Она также наиболее естественно («исчислительно») представляет объекты алгоритмической природы, подобные программам, что существенно, коль скоро речь идет о возможности формирования нового стандарта внутреннего представления программ. Более того, мы полагаем, что формульная запись, наряду с общепринятыми рекурсивными функциями, автоматом Тьюринга или алгорифмами Маркова, наиболее пригодна выступать в роли «программной» версии определения алгоритма вообще. Язык программирования как технический объект в АФ редуцируется практически полностью, сводясь лишь к нескольким символам и правилам общематематического характера, причем это не сопровождается введением каких-либо специфических объектов или знаков, таких, как метки передачи управления.

Формульный процессор

Главной характеристикой АФ, как мы считаем, является возможность построения для них исполняющего устройства – процессора с формульной архитектурой ([11], рис.2), – по уровню сложности и быстродействию сопоставимого с существующими командными процессорами. Это существенно отличает данный процессор от любой известной системы схемной реализации, для которых характерно многоуровневое усложнение логики исполняющей системы с включением в нее множества дополнительных регистров (иногда столь специфичных, как, например, счетчики скобок), связей, логических схем, прошитых в ПЗУ программных модулей, фактически интерпретирующих в конечном счете операторы входного языка и т.д. и т.п. В отличие от этого, базовая идея формульной архитектуры может быть отражена в одной фразе: для организации прямого выполнения операторно-формульного кода программы в код исполняемой команды включаются флаги декларируемого состояния загрузки ряда регистров местной (внутрипроцессорной) памяти. Такой упрощающий подход к исполнительной системе соответствует более адекватному распределению функций между ней и системами транслирующими либо интерпретирующими. Более сильная подгонка схемы под тот или иной язык или инструментальное средство на сегодняшний день выглядит нецелесообразной. В случае формульного процессора все программные средства остаются в равном положении по отношению к исполняющей системе, а транслирующая фаза хотя и заметно упрощается, всё же сохраняется как таковая, сохраняя вместе с собой и естественную возможность использования самых причудливых приёмов программирования и управляющих протоколов.