Непейвода Н.Н., Скопин И.Н. Основания программирования

Подождите немного. Документ загружается.

13.1. КОНКРЕТИЗАЦИЯ

735

ния, элементов и узлов образца P на элементы и узлы объектного выраже-

ния E. Графическое представление успешного сопоставления приведено на

рис. 13.2. Здесь узлы представлены знаками

Рис. 13.2. Сопоставление E : P является отображением P на E. Здесь объ-

ектным выражением E является

’A’((2’B’))’B’

, а образцом P является

’A’(e.1

t.2)s.3

Следующие требования являются инвариантом алгоритма сопоставления

и их выполнение обеспечивается на каждой его стадии:

Общие требования к отображению P на E

(сопоставлению E : P )

1. Если узел N2 расположен в P правее узла N 1, то проекция N2 в E

может либо совпадать с проекцией N1, либо располагаться справа от

нее (линии проектирования не могут пересекаться).

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

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

ваниям их значений; т. е., быть в соответствии с типом переменной ато-

мами, термами или произвольными выражениями. Различные вхожде-

ния одной переменной должны иметь одинаковые проекции.

Предполагается, что в начале сопоставления граничные узлы P отобра-

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

736

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

следующих шести правил. На каждом шаге отображения правила 1–4 опре-

деляют следующий элемент, подлежащий отображению; таким образом, ка-

ждый элемент из P получает при отображении уникальный номер.

Правила отображения

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

нию парная ей скобка.

2. Если в результате предыдущих шагов оба конца вхождения некоторой

переменной для выражений уже отображены, но эта переменная еще

не имеет значения (ни одно другое ее вхождение не было отображено),

то эта переменная отображается следующей. Такие вхождения назы-

ваются закрытыми

-переменными. Две закрытые

-переменные мо-

гут появиться одновременно; в этом случае та, что слева, отображается

первой.

3. Вхождение переменной, которая уже получила значение, является по-

вторным. Скобки, атомы, символьные и термовые переменные и по-

вторные вхождения переменных для выражений в P являются жест-

кими элементами. Если один из концов жесткого элемента отображен,

проекция второго конца определена однозначно. Если Правила 1 и 2

неприменимы, и имеется несколько жестких элементов с одним спро-

ектированным концом, то из них выбирается самый левый. Если воз-

можно отобразить этот элемент, не вступая в противоречие с общими

требованиями 1–3, приведенными выше, тогда он отображается, и про-

цесс продолжается дальше.В противном случае объявляется тупиковая

ситуация.

4. Если Правила 1–3 неприменимы и имеются несколько переменных для

выражений с отображенным левым концом, то выбирается самая левая

из них. Она называется открытой

-переменной. Первоначально она

получает пустое значение, т. е. ее правый конец проектируется на тот

же узел, что и левый. Другие значения могут присваиваться открытым

переменным через удлинение (см. Правило 6).

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

ния успешно завершен.

13.1. КОНКРЕТИЗАЦИЯ

737

6. В тупиковой ситуации процесс возвращается назад к последней откры-

той

-переменной (т. е. к той, что имеет максимальный номер проек-

ции), и ее значение удлиняется; т. е., проекция ее правого конца в 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

завершает сопо-

ставление. Расположение отображающих номеров над элементами образца

дает наглядное представление описанного алгоритма:

1 2 5 4 3 6

’A’ ( e.1 t.2 ) s.3

Конец алгоритма

Этот сложный алгоритм упрятан для программиста в простые программ-

ные конструкции.Программа на

Рефале

состоит из последовательности опре-

делений функций. Относительное расположение членов этой последователь-

ности никакой роли не играет, и функции можно группировать из логических

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

Рефале

имеет вид

Имя функции {Последовательность сопоставлений}

Каждое сопоставление имеет вид

Образец = Метавыражение;

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

738

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

Программа 13.1.1 Программа вычисления предиката предшествования од-

ного символа другому в заданном алфавите

Pre_alph {

*1. Отношение рефлексивно

s.1 s.1 = T;

*2. Если буквы различны, проверить, входит ли

* первая из них в алфавит до второй

s.1 s.2 = <Before s.1 s.2 In <Alphabet>>; }

Before {

s.1 s.2 In e.A s.1 e.B s.2 e.C = T;

e.Z = F; }

Alphabet {

= ’abcdefghijklmnopqrstuvwxyz’; }

Строки, начинающиеся с

, служат комментариями. Последняя из функций

Alphabet

введена для технологичности, чтобы определение алфавита было в

одном месте и его легко было изменять. Так что функция с пустым образцом

может пониматься как константное выражение.

является атомом-раздели-

телем, заведомо не встречающимся в алфавите.

Последнее из правил сопоставления в

Before

применимо всегда. Это га-

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

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

Если взаимное расположение функций никакой роли не играет, то внутри

функции расположение сопоставлений важно. Сначала применяется первое

из сопоставлений, при неудаче переходят ко второму и так далее до послед-

него.

Заметим, что в языке

Рефал

отсутствие сопоставления, конкретизацией

которого является текущая область зрения, означает аварийный останов про-

граммы с выдачей текущего поля памяти и закопанных данных. Пожалуй,это

достаточно технологичное решение, поскольку для тех, кто сам желает обра-

батывать ошибки,всегда имеется возможность поместить последней строкой

в определение функции правило вида

e.A=Обработка ошибки;

Имеются также встроенные функции, в частности, функции работы с чи-

слами

<’+’ s.Number1 s.Number2>

и подобные ей.

13.1. КОНКРЕТИЗАЦИЯ

739

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

Для запуска

Рефал

-программы необходимо инициализировать поле па-

мяти. Принято, что в начале выполнения программы поле памяти имеет вид

<Go >

Таким образом, вначале применяется функция

к пустому полю зрения.

Эта функция должна быть определена в программе одним сопоставлением

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

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

ходные данные, в типичном случае описание функции

выглядит пример-

но следующим образом:

$ENTRY Go { =<Prog <Open ’r’ 1 ’data.txt’><Get 1> >}

13.1.3. Дополнительные возможности

В нашей программе 13.1.4 алфавит определен статически. Но из смысла

алфавита видно, что эту глобальную информацию хорошо было бы иметь

возможность заменять. Для хранения динамической глобальной информации

(чаще всего числовых характеристик либо словарей) в языке Рефал имеются

стандартные функции работы со стеками закопанных данных. Функция

рассматривает свой первый аргумент, который должен быть строкой симво-

лов, не включающей

’=’

, как имя стека, и помещает свой второй аргумент на

вершину этого стека. Если стек был пуст, то он создается. Соответственно,

функция

выкапывает верхушку стека. Если стек пуст, то ошибки нет, просто выдает-

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

работы с глобальной информацией.

копирует верхушку стека без ее уда-

ления,

замещает верхушку стека на свой аргумент,

DgAll

выкапывает сразу

весь стек

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

740

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

Ввод-вывод организован в

Рефале

достаточно аскетически.Имеется функ-

ция открытия канала ввода, которая открывает файл либо для ввода, либо для

вывода (в этом случае первым аргументом служит

’r’

) и присваивает ему но-

мер. Одна строка символов из файла читается с помощью функции

Get

, за-

меняющей свой вызов на прочитанную строку, одна строка пишется в файл

путем функций

либо

Вторая функция стирает свое поле зрения, а первая оставляет в качестве ре-

зультата напечатанное выражение.

Следует заметить, что эти функции читают и пишут именно последова-

тельности символов. При их использовании программист должен сам пре-

образовать последовательности цифр в числа, а скобки-символы в структур-

ные скобки. Более того, при выводе часть информации теряется: невозможно

различить последовательность букв и идентификатор, последовательность

цифр и число, структурные скобки и скобки-символы. Поэтому имеется еще

одна совокупность функций, автоматизирующих преобразование. Каждая из

этих функций обрабатывает сбалансированное по скобкам выражение. При

вводе это выражение заканчивается пустой строкой.

или

или

Первая из функций предназначена для ввода подготовленных вручную фай-

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

Только что перечисленные функции вместе с функцией

требуют объ-

яснения инструментов модульности в

Рефале

Рефал

-модуль — просто

Ре-

фал

-программа, не обязательно включающая

. Функции, предоставляе-

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

цификатором

$ENTRY

. В свою очередь. использующий модуль должен опи-

сать внешние функции:

$EXTRN F1,F2,F3;

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

тором примерно следующего вида:

refgo prog1+functions+reﬂib

13.1. КОНКРЕТИЗАЦИЯ

741

Модуль основной программы должен идти первым.Никаких средств включить

требование вызова модуля в текст другого модуля нет, модули сопрягаются

внешним образом. При конфликтах имен берется определение функции из

первого в порядке подключения модуля.

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

определяются в стандартном модуле

reﬂib

Важнейшими средствами современного

Рефала

является работа с мета-

выражениями. Базовое ее средство — встроенная функция

, которая за-

ключает свой аргумент в функциональные скобки и тем самым дает возмож-

ность вычислить динамически построенное выражение. По словам Турчина,

работает так, как работало бы определение

Mu { s.F e.X = <s.F e.X> }

если бы оно было синтаксически допустимо.

В частности,через

работает стандартный модуль Рефала

(Evaluation),

дающий возможность вычислить динамически введенное выражение. Он об-

рабатывает это выражение через функцию

Upd

, которая должна быть доба-

влена к модулю, желающему осуществлять динамическое вычисление выра-

жений. Например, если добавить описание

$ENTRY Upd {e.X = <Mu e.X>;}

то командная строка

refgo e+prog1

приведет к требованию написать выраже-

ние. Это выражение будет сделано полем памяти программы

prog1

и вычи-

слено, а результат выведен. Например, написав для программы 13.1.4

мы получим в качестве результата

’abcdefghijklmnopqrstuvwxyz’

Естественно возникает вопрос об обработке внутри языка произвольных,

а не только объектных, выражений. Для этого имеются стандартные функ-

ции

. Первая из них превращает объектное выражение в выражение

произвольного вида, вторая кодирует свою область зрения (ей, по семантике

языка, может быть лишь объектное выражение) в форме, годящейся для об-

щих выражений и даже метавыражений. В стандартном комплекте

Рефала

есть даже модуль прогонки, который позволяет подать на вход программе ме-

тавыражение и вычислить его настолько, насколько это возможно без знания

значений переменных.

742

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

При решении сложных задач на

Рефале

естественно возникла задача пред-

ставления мультииерархической структуры. Для частного случая двух неза-

висимых иерархий, одна из которых считается главной, а вторая начнет рабо-

тать после исчерпания первой, в

Рефале

разработано мультискобочное пред-

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

дирования и декодирования выражений и программ, переводящих мультис-

кобочное выражение в его стандартный код и наоборот. Для частного случая,

когда вторичная иерархия — наши обычные скобки, а первичная иерархия —

ссылка глубоко внутрь скобочного выражения, неявно задающая одноуров-

невую скобочную структуру, независимую от стандартной, алгоритм кодиро-

вания исключительно прост.Выражение разбито на две несбалансированных

по скобкам части: левую и правую. В обеих частях непарные скобки заменя-

ем на пары

)(

. Открывающую скобку высшего уровня представляем как

((

место, куда ведет ссылка — как

))(

, закрывающую скобку высшего уровня

как

))

И в заключение рассмотрим достаточно сложный алгоритм на

Рефале

иллюстрирующий многие приемы программирования. Пусть у нас дано вы-

ражение с различными парными скобками (в конкретном случае мы исполь-

зуем пары

’()[]{}<>’

, но программа составлена так, чтобы эти пары можно бы-

ло заменить в любой момент). Для эффективной работы на Рефале это вы-

ражение нужно закодировать, используя структурные скобки. Кодом пары

скобок

Левая Правая

будут скобки

(Левая

Правая)

. Ниже дан алгоритм

кодировки.

При записи данного алгоритма используется еще одна возможность

Ре-

фала-5

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

включающее свободные переменные образца, а затем другой образец. Во вто-

ром образце мы отождествляем вспомогательное выражение, не изменяя зна-

чений переменных, унаследованных из предыдущего образца. Если после

второго образца идут фигурные скобки, то мы задаем безымянную функцию

внутри функции. Если же их нет, то это отождествление рассматривается как

дополнительное условие успешности первого отождествления. Эта иерархия

вложенности может продолжаться на несколько уровней, причем перемен-

ные внешних уровней на внутренних уровнях остаются связанными, уже не

изменяя значений.

Иерархически вложенные функции и условия в принципе не нужны для

Рефала

, но их использование позволяет сократить и, главное, лучше струк-

турировать текст программы.

Программа 13.1.2 Мультискобочное выражение: Рефал

13.1. КОНКРЕТИЗАЦИЯ

743

$ENTRY Go{=<Init>;}

$EXTRN Xxout;

Инициализация поля зрения и констант

Init{=<Open ’r’ 1 ’Input.txt’><Trans <Acquire(<Get 1>)»;}

Acquire {

e.Got ()= e.Got;

* Конец ввода - пустая строка

e.Got (e.New)=<Acquire e.Got e.New (<Get 1>)>;

}

Brackets {=(’()’)(’[]’)(’’)(’<>’);}

Trans {

e.A =<Result <Pairing () e.A > >;

}

Pairing {

В первой скобке содержится последовательность всех незакрытых

скобок вместе с сегментами данных, подлежащими помещению

в данную пару скобок;

каждый сегмент данных также заключен в скобки

(e.Unclosed (e.LastUn)(s.Lbrack e.Middle)) s.Rbrack e.Last,

<Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =

Встретилась правая скобка, парная последней незакрытой;

выбрасываем отработанный сегмент из поля зрения

<Pairing (e.Unclosed (e.LastUn (s.Lbrack e.Middle s.Rbrack))) e.Last>;

((s.Lbrack e.Middle)) s.Rbrack e.Last,

<Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =

Парная незакрытой, находящейся внутри другой незакрытой

(s.Lbrack e.Middle s.Rbrack) <Pairing () e.Last>;

(e.Unclosed (e.LastUn)(s.Lbrack e.Middle)) s.Rbrack e.Last,

<Brackets>: e.A(s.Lbrack1 s.Rbrack ) e.B =

Непарные скобки

<Prout "Brackets Mismatch!"> Error;

(e.Unclosed ) s.Lbrack1 e.Last,

<Brackets>: e.A(s.Lbrack1 s.Rbrack ) e.B =

Еще одна открывающая скобка; создаем новую группу данных

<Pairing (e.Unclosed (s.Lbrack1)) e.Last>;

() s.Lbrack e.Last,

<Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =

Первая открывающая скобка

744

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

<Pairing ((s.Lbrack)) e.Last>;

() s.Rbrack e.Last,

<Brackets>: e.A(s.Lbrack s.Rbrack ) e.B =

Первая скобка - закрывающая

<Prout "Extra right bracket"> Error;

Нейтральный символ вне скобок

() s.Other e.Last = s.Other <Pairing () e.Last>;

Выражение и скобки исчерпаны - успех

() =;

Выражение исчерпано, а скобки - нет

(e.Unclosed (e.Lastun))=<Prout "Not all brackets are closed» Error;

Нейтральный символ в очередной скобке

(e.Unclosed (e.Lastun))s.Other e.Last=

<Pairing (e.Unclosed(e.Lastun s.Other)) e.Last>;

}

Result {

Если была ошибка, выйти

e.A Error=;

Иначе вывести результат для дальнейшего использования

e.A =<Xxout (’output.rdt’) e.A>;

}

Чтобы нагляднее увидеть влияние стиля на программные решения, сравните

эту программку с развитием программы в традиционном стиле, приведен-

ным в § 11.5. Данная программа намного выразительнее, короче. легче мо-

дифицируема и не менее эффективна, чем программа 11.5.3.

13.1.4. Развитие языка и его диалекты

Созданный в теоретической работе Турчина язык сразу же поменял свою

конкретно-синтаксическую форму для удобства представления и работы.Язык

Рефал-2

длительное время был практическим стандартом

Рефал

-систем. В

нем появились ввод-вывод и стеки закопанных данных.

В языке

Рефал-4

было сделано две попытки. Одной из них была попыт-

ка достаточно механически совместить Рефал с нарождавшимися объектно-

ориентированными средствами, которая быстро завела в тупик и была оста-

влена. Другой было определение метаопераций, которое доказало свою жиз-

неспособность. В языке

Рефал-5

[90], который сейчас является фактическим