«ОСНОВАНИЯ ПРОГРАММИРОВАНИЯ УДК 519.682 Непейвода Н. Н., Скопин И. Н. Основания программирования Книга представляет собой первое издание в серии, предназначенной для студентов, готовящихся к работе по современным ...»

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

Пример 13.1.2. Рассмотрим пример памяти Рефал-машины в ходе вычислений.

Поле памяти:

’aaxzACDE’ ’XZ начиная с реализации, описанной в [69]. Однако он не является обязательным.2 Преобразование выражений в формат для обработки проделывается один раз, при их вводе, либо даже заранее, при трансляции программы.

Рассмотрим конкретный синтаксис выражений. Идентификатор — любая последовательность цифр и букв, начинающаяся с большой буквы. Идентификатор является символьным литералом и представляет составной символ.

Символы, заключенные в одинарные ’ ’ или двойные " " кавычки, являются символьными литералами, представляют сами себя. Дважды повторенная кавычка представляет себя. Если вне кавычек встречается символ, не являющийся скобкой, частью идентификатора или числа, это трактуется как ошибка.

Определение 13.1.3. Метавыражение Рефала может содержать переменные, чье обозначение включает тип и символ переменной, записываемые в конкретном синтаксисе как тип.атом. Переменные не могут быть детерминативами. В стандартном Рефале имеются переменные трех типов: символьПри реализации языка Рефал В. Ф. Турчин задумался, как избежать слишком частых обращений к каким-то суррогатам возможностей традиционных языков. Поэтому он решил заранее описать алгоритм преобразования выражений и подобрать для него подходящую структуру данных. Описанный им алгоритм оказался хорошо работающим для целого класса случаев, включая те, которые заранее не предусматривались — характеристический признак хорошего решения. В качестве того, что происходит, если это хорошо не продумать на ранних, см. параграф, относящийся к языку PROLOG.

Более того, описанные Турчиным алгоритм и структуры данных являются хорошей базой для точного определения семантики на базе абстрактного синтаксиса языка Рефал.

ные (s.First), термовые (t.Inner) и общие (e.Last). Метавыражение называется образцом, если оно не содержит функциональных скобок.

Конец определения 13.1.3.

Значением символьной переменной служит атом, термовой — неделимое объектное выражение (терм, в терминах Рефала), то есть символ или выражение в скобках, общей — произвольное (может быть, пустое) объектное выражение. Идентификаторы переменных вводить не понадобилось, поскольку каждый идентификатор является атомом.

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

13.1.2. Модель вычислений и Рефал-программа Основными двумя шагами при Рефал-вычислениях являются конкретизация переменных в образце в соответствии с областью зрения и подстановка полученных значений в другое метавыражение. В языке рассматривается лишь частный случай конкретизации.

Конкретизацией образца M e в объектное выражение E называется такая подстановка значений вместо переменных M e, что после применения данной подстановки M e совпадет с E.

Заметим, что одно и то же метавыражение может иметь много конкретизаций в одно и то же объектное выражение. Например, рассмотрим метавыражение К этой концептуальной конфетке еще бы красивую обертку!

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

и объектное выражение AhAhAh ’OhOhOh’ (Ugu’,’Udgu) ’(((’ Basta’!’ Имеется 11 вариантов конкретизации (13.4) в (13.5) (проверьте!).

Если у метавыражения Me есть много вариантов конкретизации в E, то они упорядочиваются по предпочтительности в следующем порядке.

Пусть Env1 и Env2 — два варианта конкретизации Me в P. Рассмотрим все вхождения переменных в Me. Если Env1 и Env2 не совпадают, они приписывают некоторым переменным различные значения. Найдем в P самое первое слева вхождение переменной которому Env1 и Env2 приписывают разные значения и сравним длину этих значений. Та из конкретизаций, в которой значение, приписываемое данному вхождению переменной, короче, предшествует другой и имеет приоритет перед ней.

Например, сопоставим объектное выражение (A1 A2 A3)(B1 B2) с образцом e.1 (e.X s.A e.Y) e.2. В результате получится следующее множество вариантов сопоставления:

где варианты сопоставления перечислены в соответствии с их приоритетами, т. е. самый первый вариант находится на первом месте и т. д. Описанный способ упорядочения вариантов сопоставления называется сопоставлением слева направо.

Тот алгоритм конкретизации, который используется в Рефале, называется проецированием и согласован с введенным нами отношением порядка.

Опишем его (описание взято из учебника Турчина [90]). Обратите внимание, как в данном случае общая и не всегда эффективно реализуемая операция ‘проецируется’ на свою частную реализацию, одновременно повышающую эффективность, сохраняющую общность и навязывающую методику программирования.

';

Алгоритм для сопоставления объектного выражения E с образцом P в РЕФАЛ-5.

Вхождения атомов, скобок и переменных будут называться элементами выражений. Пропуски между элементами будут называться узлами. Сопоставление E : P определяется как процесс отображения, или проектироваКОНКРЕТИЗАЦИЯ ния, элементов и узлов образца P на элементы и узлы объектного выражения E. Графическое представление успешного сопоставления приведено на рис. 13.2. Здесь узлы представлены знаками o.

Рис. 13.2. Сопоставление E : P является отображением P на E. Здесь объектным выражением E является ’A’((2’B’))’B’, а образцом P является ’A’(e. t.2)s.3.

Следующие требования являются инвариантом алгоритма сопоставления и их выполнение обеспечивается на каждой его стадии:

1. Если узел N 2 расположен в P правее узла N 1, то проекция N 2 в E может либо совпадать с проекцией N 1, либо располагаться справа от нее (линии проектирования не могут пересекаться).

2. Скобки и атомы должны совпадать со своими проекциями.

3. Проекции переменных должны удовлетворять синтаксическим требованиям их значений; т. е., быть в соответствии с типом переменной атомами, термами или произвольными выражениями. Различные вхождения одной переменной должны иметь одинаковые проекции.

Предполагается, что в начале сопоставления граничные узлы P отображаются в граничные узлы E. Процесс отображения описывается при помощи

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

следующих шести правил. На каждом шаге отображения правила 1–4 определяют следующий элемент, подлежащий отображению; таким образом, каждый элемент из P получает при отображении уникальный номер.

1. После того, как отображена скобка, следующей подлежит отображению парная ей скобка.

2. Если в результате предыдущих шагов оба конца вхождения некоторой переменной для выражений уже отображены, но эта переменная еще не имеет значения (ни одно другое ее вхождение не было отображено), то эта переменная отображается следующей. Такие вхождения называются закрытыми e-переменными. Две закрытые e-переменные могут появиться одновременно; в этом случае та, что слева, отображается 3. Вхождение переменной, которая уже получила значение, является повторным. Скобки, атомы, символьные и термовые переменные и повторные вхождения переменных для выражений в P являются жесткими элементами. Если один из концов жесткого элемента отображен, проекция второго конца определена однозначно. Если Правила 1 и неприменимы, и имеется несколько жестких элементов с одним спроектированным концом, то из них выбирается самый левый. Если возможно отобразить этот элемент, не вступая в противоречие с общими требованиями 1–3, приведенными выше, тогда он отображается, и процесс продолжается дальше. В противном случае объявляется тупиковая ситуация.

4. Если Правила 1–3 неприменимы и имеются несколько переменных для выражений с отображенным левым концом, то выбирается самая левая из них. Она называется открытой e-переменной. Первоначально она получает пустое значение, т. е. ее правый конец проектируется на тот же узел, что и левый. Другие значения могут присваиваться открытым переменным через удлинение (см. Правило 6).

5. Если все элементы P отображены, это значит, что процесс сопоставления успешно завершен.

6. В тупиковой ситуации процесс возвращается назад к последней открытой e-переменной (т. е. к той, что имеет максимальный номер проекции), и ее значение удлиняется; т. е., проекция ее правого конца в E продвигается на один терм вправо. После этого процесс возобновляется. Если переменную нельзя удлинить (из-за Общих требований 1–3), удлиняется предшествующая открытая переменная, и т. д. Если не имеется подлежащих удлинению открытых переменных, процесс сопоставления не удался.

На рис. 13.2 сопоставление производится следующим образом. Вначале имеется два жестких элемента с одним отображенным концом: ’A’ и s.3. В соответствии с Правилом 3, отображается ’A’ и этот элемент получает при отображении номер 1. Номера 2 и 3 будут назначены левой и правой скобкам, согласно Правилам 3 и 1. Внутри скобок начинается перемещение справа налево, так как t.2 является жестким элементом, который может быть отображен, в то время как значение e.1 еще не может быть определено. На следующем шаге обнаруживается, что e.1 является закрытой переменной, чью проекцию не требуется обозревать для того, чтобы присвоить ей значение;

что бы ни было между двумя узлами, это годится для присвоения (на самом деле, значение e.1 оказывается пустым). Отображение s.3 завершает сопоставление. Расположение отображающих номеров над элементами образца дает наглядное представление описанного алгоритма:

Конец алгоритма Этот сложный алгоритм упрятан для программиста в простые программные конструкции. Программа на Рефале состоит из последовательности определений функций. Относительное расположение членов этой последовательности никакой роли не играет, и функции можно группировать из логических или технологических соображений. Каждое описание функции в базисном Рефале имеет вид Имя функции {Последовательность сопоставлений} Каждое сопоставление имеет вид Образец = Метавыражение;

Пример 13.1.4. Рассмотрим пример Рефал-программы.

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

Программа 13.1.1 Программа вычисления предиката предшествования одного символа другому в заданном алфавите *1. Отношение рефлексивно Pre_alph { *2. Если буквы различны, проверить, входит ли * первая из них в алфавит до второй Before { s.1 s.2 In e.A s.1 e.B s.2 e.C = T;

Alphabet { = ’abcdefghijklmnopqrstuvwxyz’; } Строки, начинающиеся с *, служат комментариями. Последняя из функций Alphabet введена для технологичности, чтобы определение алфавита было в одном месте и его легко было изменять. Так что функция с пустым образцом может пониматься как константное выражение. In является атомом-разделителем, заведомо не встречающимся в алфавите.

Последнее из правил сопоставления в Before применимо всегда. Это гарантирует, что предикат никогда не заканчивается неудачей.

Конец примера 13.1.4.

Если взаимное расположение функций никакой роли не играет, то внутри функции расположение сопоставлений важно. Сначала применяется первое из сопоставлений, при неудаче переходят ко второму и так далее до последнего.

Заметим, что в языке Рефал отсутствие сопоставления, конкретизацией которого является текущая область зрения, означает аварийный останов программы с выдачей текущего поля памяти и закопанных данных. Пожалуй, это достаточно технологичное решение, поскольку для тех, кто сам желает обрабатывать ошибки, всегда имеется возможность поместить последней строкой в определение функции правило вида e.A=Обработка ошибки;

Имеются также встроенные функции, в частности, функции работы с числами и подобные ей.

Рассмотрим связь между языком и программным окружением.

Для запуска Рефал-программы необходимо инициализировать поле памяти. Принято, что в начале выполнения программы поле памяти имеет вид Таким образом, вначале применяется функция Go к пустому полю зрения.

Эта функция должна быть определена в программе одним сопоставлением с пустым образцом, и не может вызываться никакой другой функцией. Поскольку чаще всего программа должна обрабатывать имеющиеся в файле исходные данные, в типичном случае описание функции Go выглядит примерно следующим образом:

13.1.3. Дополнительные возможности В нашей программе 13.1.4 алфавит определен статически. Но из смысла алфавита видно, что эту глобальную информацию хорошо было бы иметь возможность заменять. Для хранения динамической глобальной информации (чаще всего числовых характеристик либо словарей) в языке Рефал имеются стандартные функции работы со стеками закопанных данных. Функция рассматривает свой первый аргумент, который должен быть строкой символов, не включающей ’=’, как имя стека, и помещает свой второй аргумент на вершину этого стека. Если стек был пуст, то он создается. Соответственно, функция выкапывает верхушку стека. Если стек пуст, то ошибки нет, просто выдается пустое выражение. Несколько других функций дополняют возможности работы с глобальной информацией. Cp копирует верхушку стека без ее удаления, Rp замещает верхушку стека на свой аргумент, DgAll выкапывает сразу весь стек4.

(И.Н. Скопин) Милая штучка! Сразу видно, что она для тех случаев, когда запутываешься!

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

Ввод-вывод организован в Рефале достаточно аскетически. Имеется функция открытия канала ввода, которая открывает файл либо для ввода, либо для вывода (в этом случае первым аргументом служит ’r’) и присваивает ему номер. Одна строка символов из файла читается с помощью функции Get, заменяющей свой вызов на прочитанную строку, одна строка пишется в файл путем функций либо Вторая функция стирает свое поле зрения, а первая оставляет в качестве результата напечатанное выражение.

Следует заметить, что эти функции читают и пишут именно последовательности символов. При их использовании программист должен сам преобразовать последовательности цифр в числа, а скобки-символы в структурные скобки. Более того, при выводе часть информации теряется: невозможно различить последовательность букв и идентификатор, последовательность цифр и число, структурные скобки и скобки-символы. Поэтому имеется еще одна совокупность функций, автоматизирующих преобразование. Каждая из этих функций обрабатывает сбалансированное по скобкам выражение. При вводе это выражение заканчивается пустой строкой.

Первая из функций предназначена для ввода подготовленных вручную файлов, вторая и третья — для обмена с диском промежуточной информацией.

Только что перечисленные функции вместе с функцией Go требуют объяснения инструментов модульности в Рефале. Рефал-модуль — просто Рефал-программа, не обязательно включающая Go. Функции, предоставляемые в пользование другим модулям, описываются как входы, описанные спецификатором $ENTRY. В свою очередь. использующий модуль должен описать внешние функции:

Вызов программы, состоящей из нескольких модулей, производится оператором примерно следующего вида:

refgo prog1+functions+reib Модуль основной программы должен идти первым. Никаких средств включить требование вызова модуля в текст другого модуля нет, модули сопрягаются внешним образом. При конфликтах имен берется определение функции из первого в порядке подключения модуля.

В частности, только что описанные расширенные функции ввода-вывода определяются в стандартном модуле reib.

Важнейшими средствами современного Рефала является работа с метавыражениями. Базовое ее средство — встроенная функция Mu, которая заключает свой аргумент в функциональные скобки и тем самым дает возможность вычислить динамически построенное выражение. По словам Турчина, Mu работает так, как работало бы определение если бы оно было синтаксически допустимо.

В частности, через Mu работает стандартный модуль Рефала e (Evaluation), дающий возможность вычислить динамически введенное выражение. Он обрабатывает это выражение через функцию Upd, которая должна быть добавлена к модулю, желающему осуществлять динамическое вычисление выражений. Например, если добавить описание то командная строка refgo e+prog1 приведет к требованию написать выражение. Это выражение будет сделано полем памяти программы prog1 и вычислено, а результат выведен. Например, написав для программы 13.1. мы получим в качестве результата Естественно возникает вопрос об обработке внутри языка произвольных, ’abcdefghijklmnopqrstuvwxyz’ а не только объектных, выражений. Для этого имеются стандартные функции Up и Dn. Первая из них превращает объектное выражение в выражение произвольного вида, вторая кодирует свою область зрения (ей, по семантике языка, может быть лишь объектное выражение) в форме, годящейся для общих выражений и даже метавыражений. В стандартном комплекте Рефала есть даже модуль прогонки, который позволяет подать на вход программе метавыражение и вычислить его настолько, насколько это возможно без знания значений переменных.

ГЛАВА 13. СЕНТЕНЦИАЛЬНЫЕ МЕТОДЫ

При решении сложных задач на Рефале естественно возникла задача представления мультииерархической структуры. Для частного случая двух независимых иерархий, одна из которых считается главной, а вторая начнет работать после исчерпания первой, в Рефале разработано мультискобочное представление выражений. Оно поддерживается библиотечными функциями кодирования и декодирования выражений и программ, переводящих мультискобочное выражение в его стандартный код и наоборот. Для частного случая, когда вторичная иерархия — наши обычные скобки, а первичная иерархия — ссылка глубоко внутрь скобочного выражения, неявно задающая одноуровневую скобочную структуру, независимую от стандартной, алгоритм кодирования исключительно прост. Выражение разбито на две несбалансированных по скобкам части: левую и правую. В обеих частях непарные скобки заменяем на пары )(. Открывающую скобку высшего уровня представляем как ((, место, куда ведет ссылка — как ))(, закрывающую скобку высшего уровня как )).

И в заключение рассмотрим достаточно сложный алгоритм на Рефале, иллюстрирующий многие приемы программирования. Пусть у нас дано выражение с различными парными скобками (в конкретном случае мы используем пары ’()[]{}’, но программа составлена так, чтобы эти пары можно было заменить в любой момент). Для эффективной работы на Рефале это выражение нужно закодировать, используя структурные скобки. Кодом пары скобок Левая Правая будут скобки (Левая и Правая). Ниже дан алгоритм кодировки.

При записи данного алгоритма используется еще одна возможность Рефала-5. После образца через запятую может идти произвольное выражение, включающее свободные переменные образца, а затем другой образец. Во втором образце мы отождествляем вспомогательное выражение, не изменяя значений переменных, унаследованных из предыдущего образца. Если после второго образца идут фигурные скобки, то мы задаем безымянную функцию внутри функции. Если же их нет, то это отождествление рассматривается как дополнительное условие успешности первого отождествления. Эта иерархия вложенности может продолжаться на несколько уровней, причем переменные внешних уровней на внутренних уровнях остаются связанными, уже не изменяя значений.

Иерархически вложенные функции и условия в принципе не нужны для Рефала, но их использование позволяет сократить и, главное, лучше структурировать текст программы.

Программа 13.1.2 Мультискобочное выражение: Рефал $ENTRY Go{=;} * Инициализация поля зрения и констант $EXTRN Xxout;