БАЗИСНЫЙ РЕФАЛ

• Объектное выражение
• Образец
• Результатное выражение, предложение, функция
• Комментарий
• Выбор варианта сопоставления
• Рефал-машина
• Модуль

  ОБЪЕКТНОЕ ВЫРАЖЕНИЕ

Программа на языке Рефал представляет собой набор определений функций. Аргументы и результаты функций - символьные выражения, образованные из символов при помощи скобок "(" и ")". Скобки в выражении должны быть "правильно расставлены". Более строго эту мысль можно выразить в форме следующего рекурсивного определения:

• пустой текст есть выражение;
• всякий символ есть выражение;
• если E1 и E2 - выражения, то (E1) - выражение и E1 E2 - выражение.

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

Символы бывают следующих видов:

Символы-литеры. Это знаки, которые можно ввести с клавиатуры. В программе они записываются цепочками между апострофами. Если в цепочку входит литера апостроф (а также двойная кавычка или обратный слеш), то она изображается этой литерой со знаком "\" (обратный слеш) впереди.

Примеры символов-литер:

'+' '1' 'A'

литеры "плюс", "один", "А заглавная"

'+1A'

то же, записанное одной цепочкой/

' '

литера "пробел"

'\''

литера апостроф/

'He\'s got ill'

цепочка из 12 литер

')('

две объектные скобки

Символы-слова - это символы, которые имеют изображением последовательность литер. Если слово состоит из букв (латинских), цифр, знаков "-" и "_" и начинается с заглавной буквы, то в программе оно записывается непосредственно своим изображением. В общем случае слово записывается по правилам записи одной цепочки литер, но вместо апострофа используется двойная кавычка. Вот примеры символов-слов:

      A
      A_17
      Del-Dups
      "18:30"
      " \" is expected "

Два слова равны, если они имеют изображением одну и ту же текстовую строку. Например, символы-слова A и "A" равны, но слова "abc" и "abc " различны (последнее имеет пробел на конце).

Символы-числа изображаются последовательностями десятичных цифр, возможно со знаком "+" или "-" впереди. Размер числа не ограничен. Примеры символов-чисел:

     0   +17   -19999999999999999 

Два символа-числа равны тогда и только тогда, когда они выражают одно и то же целое число. Так, символы 0, +0 и -0 равны между собой и выражают число нуль.

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

Скобки "(" и ")" являются особыми знаками языка Рефал. Они служат для придания структуры выражениям, поэтому их называют структурными. Они записываются непосредственно как скобки, без какого-либо обрамления. Не следует путать их с объектными символами, имеющими вид круглых скобок: последние записываются между апострофами.

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

Пример объектного выражения:

       (A '+-' 10) (Expr1 (0 -223)) '()'

Для самопроверки замените в этом выражении каждый объектный символ словом S. Должно получиться:

       (S S S S) (S (S S)) S S

Термом (объектным) будем называть символ или объектное выражение в скобках. Каждое выражение является последовательностью термов, возможно пустой. Эти термы называют нуль-термами данного выражения. Предыдущее выражение содержит четыре нуль-терма:

      (A '+-' 10)
      (Expr1 (0 -223))
      '('
      ')'

ОБРАЗЕЦ

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

Образец - это выражение, в которое наряду с символами и скобками могут входить также переменные. Запись переменной начинается с указателя типа - маленькой буквы s, t или e - за которой следует индекс. Индекс есть цепочка букв,цифр, а также знаков "-" и "_". Он может отделяться от указателя типа точкой. Примеры записи переменных:

         sA   e1   t.const   e.17   s.ind-var

Образец обозначает класс объектных выражений, которые можно из него получить, подставляя некоторые объектные значения вместо переменных. При этом s-переменные могут заменяться только на символы, t-переменные - только на термы, а e-переменные - на произвольные выражения. Одинаковые переменные должны заменяться на одинаковые значения.

Вот некоторые примеры образцов с описанием соответствующего класса объектных выражений:

А е1 (e2)

начинающиеся со слова А и оканчивающиеся структурной скобкой

e1 sX e2 sX e3

содержащие два одинаковых символа на верхнем скобочном уровне

s.1 s.2 s.3

состоящие из трех символов

Образец можно рассматривать как условие, которому должно удовлетворять объектное выражение. Если выражение относится к классу, определяемому образцом, то можно подобрать значения переменных, которые превращают образец в данное выражение. Такая операция называется сопоставлением выражения с образцом. В случае успеха результатом сопоставления является список значений для всех переменных, встречающихся в образце.

РЕЗУЛЬТАТНОЕ ВЫРАЖЕНИЕ, ПРЕДЛОЖЕНИЕ, ФУНКЦИЯ

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

Записывая слева образец, затем знак "=", а за ним произвольное результатное выражение мы получаем предложение - элементарное правило преобразования языка Рефал. Результатное предложение в правой части предложения может содержать лишь такие переменные, которые имеются в образце в левой части. Предложение завершается знаком ";".

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

Fab1 {               
    A e1 = B e1;    
    e1 = e1;        
    };

Здесь два предложения. Первое гласит: если аргумент начинается с символа А, то результат получается приписыванием символа B к остатку, иными словами - заменой первого символа A на символ B. Согласно второму предложению результат тождествен аргументу.

Предложение применимо к аргументу (объектному выражению), если тот удовлетворяет образцу. Из нескольких применимых предложений одной функции всегда работает то, которое написано раньше. Таким образом второе предложение функции Fab1 будет работать только тогда, когда аргумент не начинается с символа А. (Это значит, что аргумент либо пуст, либо начинается со скобки, либо с символа, отличного от А.). В целом смысл функции Fab1 можно выразить словами: "если аргумент начинается на A, замени этот символ на B, иначе оставь весь аргумент без изменения".

Теперь усложним пример. Мы хотим описать функцию Fab, которая заменяет все вхождения символа А в ее аргумент на символ В. Тогда нам необходимо в первом предложении указать, что в полученном результате надо продолжить применять функцию замены к остатку e1. Это записывается так: <Fab e1>. Необходимо также рассмотреть случай когда первый символ - не A и должен быть пропущен. Если же выражение начинается со скобки "(", то придется в результатном выражении применять функцию Fab дважды: к содержимому скобок и к остатку после правой скобки ")". Получаем такое описание функции Fab:

Fab {
    A e1 = B <Fab e1> ;					  
    sX e1 = sX <Fab e1> ;					
    (e1) e2 = (<Fab e1>) <Fab e2> ;
    = ;
    };

Можно задать наивный вопрос: почему бы третье предложение не написать в виде:

    (e1 = (<Fab e1> ;

Простейший ответ таков: потому что здесь ни левая ни правая части не являются правильными выражениями синтаксически.

Функция Fab рекурсивна: она вызывает сама себя в трех предложениях. Последнее предложение - выход из рекурсии. Оно работает в случае, когда аргумент пуст (т.к. образец пуст), и выдает пустое же выражение в качестве результата.

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

Формально в Рефале все функции имеют один аргумент и один результат. Когда нужно задать несколько аргументов, будем склеивать их в один посредством скобок: (E1) (E2) ... (En). Если аргумент - символ или терм, скобки могут быть опущены. Аналогично можно представить тот факт, что функция вырабатывает несколько результатов.

Упражнения:

1. Опишите функцию Rev, которая обращает входную цепочку символов, так что например:

<Rev 'abc'> == 'cab'

2. Обобщите функцию Rev на случай любых выражений (в т.ч. со скобками), так что например:

<Rev A (B C)> == (C B) A

3. Опишите предикат Pal, допускающий палиндромы, т.е. цепочки, читающиеся одинаково в обе стороны. Выдавайте символ T в случае палиндрома, и символ F во всех остальных случаях, например:

<Pal 'eye' > == T

<Pal 'edge'> == F

4. Обобщите функцию Pal на случай любых выражений, так что например:

<Pal ('moor') ('a') ('room')> == T

<Pal ('name') ('man')> == F

5. Определите функцию, которая сравнивает две строки по длине, результат - один из трех символов: L, E или G.

6. Напишите функцию Maxcomm, определяющую наибольшую общую часть двух строк. Это должна быть самая длинная строкa, которую можно получить из обоих исходных строк путем вычеркивания некоторых символов, например:

<Maxcomm ('program') ('algorithm')> == 'orm'

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

КОММЕНТАРИЙ

Комментарии в программе записываются в форме:

• одной строки, начинающейся со знака "*";
• текста, начинающегося с "/*" и оканчивающегося на "*/";
• окончания строки после знаков "//".

Комментарий в программе может стоять всюду, где допускается незначащий пробел (табуляция, перевод строки). Это позиции между последовательностями знаков в апострофах, словами, переменными, скобками (всех видов), знаками "=", ";" и другими разделителями.

ВЫБОР ВАРИАНТА СОПОСТАВЛЕНИЯ

Некоторые образцы допускают несколько вариантов сопоставления для одного и того же объектного выражения. Рассмотрим, например, образец e1 '+' e2 и объектное выражение 'A+B+C'. Возможны такие варианты сопоставления:

1. e1 = 'A' ; e2 = 'B+C'
2. e1 = 'A+B' ; e2 = 'C'

Когда нужно выбрать из нескольких вариантов один, будем поступать так. Выпишем каждый вариант, располагая переменные в порядке их первого слева вхождения в образец. Варианты упорядочим в порядке возрастания. Для сравнения двух вариантов последовательно сравниваем значения переменных в порядке их написания. Как только встречается первое отличие, смотрим: где значение короче, тот вариант и меньше. Можно доказать утверждение, что одно из двух значений обязательно будет короче; более того, оно непременно будет началом другого, причем это будут значения e-переменной. В нашем примере это переменная e1, а ее значения: 'A' и 'A+B'.

Для доказательства утверждения рассмотрим переменные, стоящие в образце левее данной. В силу правила упорядочения переменных образца их значения одинаковы в обоих вариантах. Следовательно, левый конец данной переменной в обоих вариантах приходится на одно и то же место объектного выражения, а значит, оба значения данной переменной являются разными началами одного и того же подвыражения. Отсюда с очевидностью вытекает доказываемое утверждение. Данная переменная яляется е-переменной, поскольку два ее допустимых значения имеют разное число нуль-термов; следовательно, она не может быть ни s- ни t-переменной.

Чтобы результат сопоставления был всегда однозначным, потребуем, чтобы из нескольких возможных вариантов выбирался всегда наименьший. Данное правило носит название "сопоставление слева", поскольку мы упорядочили переменные образца согласно их первым вхождениям при просмотре образца слева направо. Можно выбрать другой порядок переменных: например согласно их первым вхождениям при просмотре справа налево. Он приводит к другому упорядочению вариантов сопоставления и, следовательно, к другому правилу выбора окончательного варианта, которое называется правилом "сопоставления справа". Некоторые реализации Рефала поддерживают возможность выбора для каждого образца своего порядка сопоставления: слева или справа.

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

<Cross (e1) (e2)>

где e1 и e2 - представления исходных множеств.

 Cross {
    (e1 sA e2) (e3 sA e4) = sA <Cross (e2) (e3 e4)>; 
    (e1) (e2) = ;
 };

Первое предложение срабатывает всегда, когда две входные строки имеют хотя бы один общий символ. Таким образом, второе предложение сработает и выдаст пустой результат только если входные множества не пересекаются, что вполне согласуется с постановкой. Первое предложение выдаст результат, в который войдут, во-первых, найденный общий символ sA (что бесспорно), и, во-вторых, результат рекурсивного применения той же функции к части первого аргумента (e2) и части второго аргумента (e3 e4). Возникает вопрос: почему левый аргумент рекурсивного вызова не есть (e1 e2), что было бы естественно и гарантировало бы правильность результата. Для обоснования нашего варианта, посмотрим, может ли подстрока e1 содержать элементы пересечения двух исходных строк. Нет, так как иначе был бы выбран другой вариант сопоставления образца с аргументом, с более коротким значением для e1 (по умолчанию всегда подразумевается сопоставление слева). Но раз этого не произошло, то можно утверждать, что строка e1 не содержит общих символов со вторым аргументом, и потому может быть благополучно опущена.

Мы разобрали функцию Cross с точки зрения того, что она выдает в результат, и убедились, что этот результат правильный. Теперь посмотрим, как она это делает. Наша цель - понять, как именно происходит поиск требуемого варианта сопоставления, и, в частности, как долго это делается.

В первом предложении мы видим две переменные, которые допускают множественность сопоставления: e1 и e3 . Такие переменные называются открытыми. В общем случае контекст открытой переменной eX имеет вид:

EL eX EC eY ER

где EL, EC, ER - метапеременные, обозначающие некоторые подвыражения, а X и Y - произвольные индексы. Строго говоря, EL и ER здесь не обязательно правильные выражения: EL может содержать несколько "лишних" левых скобок, а ER - столько же "лишних" правых.

Заметим, что процесс сопоставления не только устанавливает значения переменных, входящих в образец, но также всем элементам образца, включая символы и скобки, сопоставляет определенные элементы объектного выражения. При этом если какие-то два элемента образца стоят рядом, то и сопоставленные им элементы примыкают друг к другу.

Каждая открытая переменная образца требует того, чтобы в процессе сопоставления с объектным выражением происходил перебор всех способов сопоставления данной переменной с частями объектного выражения. Перебор начинается с момента, когда уже получили значения все переменные из EL и, возможно, некоторые из ER. Тем самым уже зафиксирован левый конец переменной eX, но еще свободен ("открыт") правый. Однако для правого конца уже известна некоторая позиция, правее которой он не может быть. Это самая левая из позиций, которые уже сопоставлены позициям из ER. (Без ограничения общности можно считать, что это позиция, сопоставленная левому концу ER).

Теперь рассмотрим, как происходит перебор. Сначала переменной еX сопоставляется пустое значение. Затем начинается основной цикл. В начале каждой итерации переменной еX сопоставлено некоторое подвыражение исходного объектного выражения. Левый конец подвыражения фиксирован в точке, соответствующей правому концу EL. Внутри цикла происходит поиск варианта сопоставления еще не сопоставленных переменных в предположении, что значение переменной eX фиксировано. В случае успеха найденный вариант вместе с текущим значением данной переменной объявляется окончательным. В случае неуспеха делается попытка удлинить значение переменной eX на один терм вправо и вновь войти в цикл. Если удлинение не удается (по той причине, что достигнут ограничитель справа), то объявляется неуспех (в результате которого либо происходит удлинение предыдущей открытой переменной, либо сопоставление данного образца завершается полным неуспехом).

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

T [ OE:PE ] < C x**n

где

x - длина объектного выражения OE;

n - число открытах переменных образца PE;

С - величина, пропорциональная длине образца, от объектного выражения не зависящая;

** - операция возведения в степень.

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

Посмотрим, как работает функция пересечения множеств Cross. В первом предложении образец содержит две открытые переменные: e1 и e3. В цикле удлинения переменной e1 переменная символа sA последовательно сопоставляется с каждым "элементом" левого "множества". Для каждого элемента исполняется вложенный цикл удлинения переменной e3, в котором второму вхождению переменной sA последовательно сопоставляется каждый элемент второго множества, который тут же сравнивается с символом, сопоставленным ранее первому вхождению переменной sA. Если символы окажутся равны, то сопоставление успешно оканчивается, иначе цикл продолжается. В худшем случае, когда одинаковых символов нет, каждый символ левой строки будет сравниваться с каждым символом правой. Это займет время, пропорциональное произведению длин двух строк.

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

О переменной e3 можно сказать лишь то, что в ней нет символа, равного sA, но еще могут быть символы, такие же как в e2, поэтому ее опускать не следует.

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

Упражнения.

1. Путем небольших переделок функции Cross напишите функции Union, Diff и Sdiff, которые вычисляют, соответственно, объединение, разность и симметрическую разность двух множеств.

2. Используя открытую переменную, напишите функцию Fab0, которая заменяет каждый символ А в исходной строке (без скобок) на символ В.

3. Напишите функцию-предикат, которая проверяет, является ли строка E1 подстрокой строки E2.

4. Используя образец: e1 sA e2 sA e3 , напишите функцию Del-Dups, удаляющую все повторные символы строки. Проанализируйте ее работу.

5. Напишите функцию перекодировки, имеющую формат вызова:

<Subst (e.Tab) e.Arg>

где

e.Tab - таблица перекодировки: список термов вида (S D), где S и D - соответственно, исходный и заменяющий символы;

e.Arg - выражение, символы которого подлежат перекодировке. Символы, отсутствующие в таблице, оставлять без изменения.

РЕФАЛ-МАШИНА

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

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

<Sfunc0 Earg0>

где Sfunc0 - символ: имя функции, а Earg0 - объектное выражение: ее аргумент.

Работа Рефал-машины состоит из шагов. Перед началом каждого шага в поле зрения в общем случае находится так называемое рабочее выражение. Наряду с объектными символами и скобками оно может содержать функциональные термы вида <Sfunc Earg>, где Sfunc - опять-таки имя функции, а Earg - рабочее выражение. Но: в рабочем выражении не может быть переменных. Отсюда следует, что содержимое самого внутреннего функционального терма заведомо является объектным выражение.

Шаг рефал-машины начинается с поиска самого левого самого внутреннего функционального терма, называемого активным термом. Он имеет вид <Sfunc Eobj>, где Eobj - объектное выражение. Затем из поля программы извлекается определение функции Sfunc, а если его там нет, фиксируется ошибка (как правило, эта ошибка ловится еще на стадии компиляции). Определение функции содержит набор предложений. Выбирается первое предложение, образец которого можно сопоставить с выражением Eobj (Если подходящего предложения нет, происходит аварийный останов рефал-машины с диагностикой "СОПОСТАВЛЕНИЕ НЕВОЗМОЖНО"). Затем выполняется сопоставление, в результате которого определяется список значений переменных образца. В правой части выбранного предложения (результатном выражении) все переменные заменяются на их значения. Поскольку все переменные правой части предложения должны входить в левую (образец), то результатом является рабочее выражение (т.е. выражение без переменных, но, возможно, с вызовами функций). Теперь исходный активный терм удаляется из поля зрения и на его место ставится полученное рабочее выражение. На этом шаг заканчивается, и начинается следующий шаг. Когда в поле зрения не остается ни одного функционального терма, работа рефал-машины прекращается, и содержимое поля зрения - объектное выражение - объявляется результатом ее работы. Этот результат считается значением начальной функции Sfunc0 от начального аргумента Earg0.

На практике реальная Рефал-машина начинает исполнение любой программы с фиксированного поля зрения:

<GO>

Таким образом, всякая законченная программа должна содержать определение функции GO, допускающей пустой аргумент. Реальные входные данные программа должна брать из окружения (клавиатуры или файловой системы) при помощи встроенных функций ввода, а результат - отдавать (на экран или в файл) посредством функций вывода.

 МОДУЛЬ

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

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

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

Функции, которые используются в данном модуле, но определены в других модулях, должны быть заявлены в данном модуле в специальном служебном предложении. Оно начинается с ключа $EXTERNAL (или $EXTERN, или $EXTRN), за которым следует список имен функций через запятую. Предложение оканчивается знаком ";". Пример:

      $EXTERN  Rev, Merge, Sort;

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

Функция, имя которой используется в других модулях, должна иметь определение, начинающееся с ключа $ENTRY, например:

$ENTRY Rev {
       sA eX = <Rev eX> sA;
       =;
       };

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

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

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

Файл M1.REF:

* Функция Fact вычисляет произведение чисел от 1 до sN
*        Здесь используются краткие обозначения для
*        встроенных арифметических функций
$ENTRY Fact {
     0 = 1;
     sN = <* sN <Fact <- sN 1>>>;
     };

Файл M2.REF:

* Головной модуль для вызова функции Fact
*      Здесь используются расширения рефала,
*      а также встроенные функции ввода-вывода
*      и преобразований символов
$EXTERN Fact;
$ENTRY GO { ,
     <PRINTLN 'Введи число:'> ,
     <READ_LINE> : {
          = ;
          e1 = <PRINTLN 'Fact(' e1 ') = ' <Fact <NUMB e1>>> <GO>;
          };
     };