# Основы программирования на Рефале, Базисный Рефал

<div id="toc"></div>
<script src="toc.js"></script>
<script>
makeTOC.localizedHeader = "Содержание"
makeTOC.localizedShow = "Показать";
makeTOC.localizedHide = "Скрыть";
</script>

Этот раздел представляет собой неформальное введение в Рефал-5λ, учебник,
доступный для новичка, даже для новичка в программировании. Более строго
и формально язык будет рассмотрен в следующем разделе (справочник).

## Синтаксис Базисного Рефала

Термином _Базисный Рефал_ принято называть семантическое подмножество
Рефала, в котором предложения функций состоят только из двух частей,
переменные могут иметь тип s-, t- или e- (нет, например, спецификаторов
РЕФАЛа-2 \[7]) и типы символов (symbol) включают в себя только литеральные
символы (characters), числа и слова.

Подмножество Базисного Рефала семантическое. Это значит, что конкретная
синтаксическая форма рассмотренных конструкций может сильно отличаться
в разных диалектах и реализациях (например, синтаксис РЕФАЛа-2 \[7]
совсем не похож на синтаксис Рефала-5λ), но перечисленные выразительные
средства в языке существуют.

### Программа Hello, World!

В [предыдущей части](2-intro.md) нам удалось откомпилировать и запустить
программу [`hello.ref`](hello.ref), которая распечатала строчку «Hello, World!».
Давайте теперь научимся читать и понимать её исходный код.

    $ENTRY Go {                                 /* 1 */
      /* empty */ = <Prout 'Hello, World!'>;    /* 2 */
    }                                           /* 3 */

Внимательные читатели заметили отличия от программы в предыдущей главе:
добавились строчки, начинающиеся на `/*` и заканчивающиеся на `*/`.
Это _комментарии_ — любой текст между `/*` и `*/` компилятором игнорируется
и используется для пояснения смысла программы читающему её программисту.

В эту программу были добавлены комментарии, просто нумерующие строки
(для удобства ссылки на них из текста руководства) и слово `/* empty */`,
обращающее внимание читателя на то, что в этом месте программы ничего нет.
Да, звучит на первый взгляд странно, но вскоре всё станет понятнее.

Комментарии, ограниченные знаками `/*` и `*/`, являются _многострочными,_
т.е. `*/` не обязана находиться в той же строке, что и предшествующая ей `/*`.
Помимо многострочных комментариев также допустимы _однострочные_ — любая
строка, начинающаяся со знака (в первой колонке) `*`, игнорируется
компилятором.

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

    /*
      Ньютонометр безусловно не зависит от скорости вращения внутреннего
      кольца подвеса, что не кажется странным, если вспомнить о том,
      что мы не исключили из рассмотрения периодический кожух.
    */
    $ENTRY Go {                                 /* 1 */
    * Проекция на подвижные оси, несмотря на некоторую погрешность,
    * относительно не зависит от скорости вращения внутреннего кольца
    * подвеса, что не кажется странным, если вспомнить о том, что мы
    * не исключили из рассмотрения штопор.
      /* empty */ = <Prout 'Hello, World!'>;    /* 2 */
    }                                           /* 3 */
    * Источник текста комментариев:
    /* https://yandex.ru/referats/?t=gyroscope&s=34928 */

Но вернёмся к нашей функции.

    $ENTRY Go {                                 /* 1 */
      /* empty */ = <Prout 'Hello, World!'>;    /* 2 */
    }                                           /* 3 */

Любая программа на Рефале-5λ представляет собой набор функций (язык ведь
функционального программирования всё-таки). И эта программа не исключение.
Здесь определена функция `Go`. Определение функции записывается как имя
функции, за которым следует _блок_ — тело функции, ограниченное фигурными
скобками (в строках 1 и 3 соответственно). Имя `Go` неслучайно: любая
программа на Рефале должна содержать единственное определение функции с именем
`Go` либо `GO` — процесс выполнения программы есть вычисление функции `Go`
(или `GO`) с пустым аргументом.

Непонятное `$ENTRY` перед именем функции будет прояснено в следующих разделах,
сейчас нам достаточно знать, что ключевое слово `$ENTRY` обязано предварять
точку входа (entry point) `Go` или `GO` в программу.

В строке 2 находится единственное _предложение_ функции `Go`. Предложение —
это правило, определяющее, как построить значение функции на некотором
подмножестве её аргументов. Функция в общем случае может состоять из нескольких
предложений, каждое из которых завершается знаком `;` (точкой с запятой). Точка
с запятой в конце последнего предложения может не ставиться.

Любое предложение состоит из двух частей — _левой части, образца,_ описывающей
подмножество значений аргумента функции, на котором это предложение применимо,
и _правой части, результата,_ описывающей значение функции на этом подмножестве.
Левая и правая части разделяются знаком `=` (равенства).

Примечание. _В дальнейшем будет рассматриваться расширенный синтаксис Рефала,
в котором синтаксис предложения будет уже сложнее._

В программе `hello.ref` единственное предложение говорит о том, что оно
применимо только для пустого аргумента функции (перед равенством ничего
не записано), комментарий `/* empty */` подчёркивает этот факт. Правая часть
описывает значение функции `Go` с пустым аргументом как результат вычисления
функции `Prout`, которому в качестве аргумента передаётся последовательность
знаков `Hello, World!`. Вызовы функций на Рефале, в отличие от математической
нотации, оформляются при помощи угловых скобок `<` и `>` (знаков «меньше»
и «больше»), при этом имя функции пишется не перед открывающей скобкой, а после
неё.

Функция `Prout` при любом своём аргументе вычисляет «пустоту», однако её
выполнение имеет побочный эффект — она распечатывает свой аргумент на экране.
Очевидно, ради этого побочного эффекта её и вызывают.

На самом деле, практически все программы на Рефале пишутся ради побочных
эффектов. После завершения вычисления функции `Go` (или `GO`), её результат
отбрасывается, и программа завершается. Пользователю достаётся лишь то, что
было выведено на экран функциями типа `Prout`, записано в файлы, либо передано
«наружу» из процесса вычислений иным путём.

Примечание. _Есть исключения из этого правила. Во-первых, это автоматизированные
тесты (автотесты) — программы, которые запускают тестируемую функцию, проверяют
её результат и завершаются. При успешной проверке программа молча завершается,
при неуспешной — аварийно вылетает с ошибкой. Среда запуска тестов умеет
различать эти два случая и сообщает пользователю о подобных неуспешных запусках.
Другой пример — исследования в области автоматического преобразования
и верификации программ, например, при помощи суперкомпиляции. В этом случае
пишется какая-нибудь математически интересная функция на Рефале, скармливается
инструментальному средству, например, суперкомпилятору РЕФАЛа-5 SCP4 (\[1],
\[2], \[3]), после чего изучается результат преобразования или анализа этой
функции. Собственно, исследования в области разработки подобных инструментальных
средств — это одно из основных применений Рефала на сегодня._

Функция `Prout` — это одна из функций, входящих в стандартную библиотеку языка,
и по умолчанию неявно доступна к использованию в любой программе. В классическом
РЕФАЛе-5 она является встроенной, т.е. определённой неявно всегда в любой
программе. Рефал-5λ, однако, позволяет писать программы, в которых
не используется стандартная библиотека.

#### Промежуточные выводы — что мы увидели в `hello.ref`

Давайте подытожим, что мы к этому моменту узнали.

* В программах можно писать комментарии, которые никак не влияют на выполнение
  программы и служат лишь для пояснения.
* Комментарии бывают двух видов: однострочные и многострочные.
* Однострочный комментарий представляет собой строку, первым символом которой
  является знак `*`, а остальные могут быть любыми.
* Многострочный комментарий может располагаться в любом месте программы, где
  допустим незначащий пробельный символ. Комментарий начинается знаками `/*`
  и заканчивается знаками `*/`.
* Программа на Рефале есть набор функций.
* Выполнение программы начинается с вызова «стартовой» функции `Go` или `GO`
  с пустым аргументом.
* Перед именем стартовой функции должно располагаться ключевое слово `$ENTRY`.
* Функция на Рефале записывается как имя функции, за которым в фигурных скобках
  следует одно или несколько предложений.
* Предложение состоит из двух частей: левой части — «образца» и правой части —
  «результата».
* Левая часть определяет подмножество значений аргумента, на котором применимо
  данное предложение.
* Правая часть определяет, каким способом будет строиться результат вычисления
  функции на этом подмножестве аргумента.
* «Пустое значение» записывается пустым местом, обычно в этом месте ставят
  комментарий `/* empty */` или `/* пусто */`.
* Последовательность печатных знаков (characters) записывается в одинарных
  кавычках: `'Hello, World!'`.
* Вызов функции `F` с некоторым аргументом `arg` записывается как `<F arg>`.

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

### Другие примеры программ

#### Программы из нескольких предложений

Прежде чем перейти к рассмотрению других примеров, нужно дать пояснения
по синтаксису, не отражённые в листинге `hello.ref`.

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

Во-вторых, каждый из знаков внутри одинарных кавычек является самостоятельным,
следующие записи эквивалентны: `'Hello'`, `'Hel' 'lo'`, `'H' 'e' 'l' 'l' 'o'`.

В-третьих, именем функции может быть любая последовательность букв, цифр,
знаков `_` («прочерк») и `-` («дефис»), начинающаяся с прочерка или буквы.
Например, `Go`, `Hello`, `A-plus-B`, `_remove_file`, `ANSWER_42`. Строчные
и прописные буквы различаются, т.е. имена `hello`, `Hello` и `HELLO` различные.

Примечание. _Классическая реализация РЕФАЛа-5 не поддерживает имена, которые
начинаются на прочерк._

**Пример 1.** Напишем функцию, которая складывает две двоичные цифры.

    BinAdd {
      '0' '0' = '0';
      '0' '1' = '1';
      '1' '0' = <BinAdd '0' '1'>;
      '1' '1' = '10';
    }

Левые части предложений можно было записать и слитно, например `'00'`,
на работу программы это бы никак не повлияло — они написаны раздельно для
удобочитаемости.

Нетрудно понять, что первое предложение применимо, когда аргумент функции —
`'00'`, т.е. результатом вызова `<BinAdd '00'>` будет `'0'`, со вторым
и четвёртым предложением тоже всё понятно.

Третье предложение говорит о том, что результат вызова функции
`<BinAdd '10'>` точно такой же, как и `<BinAdd '01'>`, от перемены мест
слагаемых сумма не меняется. Можно было написать в правой части сразу `'1'`,
вызов функции был добавлен в правую часть ради демонстрации самого вызова.

Областью определения этой функции будут пары символов `'00'`, `'01'`, `'10'`,
`'11'`. При попытке вызвать эту функцию с аргументом вне области определения
программа аварийно завершится (т.н. ошибка невозможности отождествления,
«recognition impossible»).

**Пример 2.** Напишем функцию, которая вычитает две двоичные цифры.

    BinSub {
      '0' '0' = '0';
      '1' '1' = '0';
      '1' '0' = '1';
      '0' '1' = '-' <BinSub '1' '0'>;
    }

Здесь всё аналогично, кроме последнего предложения. В правой части четвёртого
предложения записан символ минуса, вслед за которым находится вызов функции
`BinSub`. Что это значит? Это значит, что результатом вызова функции
`<BinSub '0' '1'>` будет знак `'-'`, за которым следует результат вычисления
`<BinSub '1' '0'>` — `'1'`. Т.е. результат `<BinSub '0' '1'>` будет равен
`'-' '1'` или `'-1'`.

**Пример 3.** Напишем функцию, которая проверяет равенство двух двоичных
чисел, не больших 2 (т.е. 10 в двоичной записи) и не меньших -1. Будем считать,
что оба числа в аргументе функции разделяются знаком `'='`.

    IsEqual {
      '-1=-1' = 'True'; '-1=0' = 'False'; '-1=1' = 'False'; '-1=10' = 'False';

      '0=-1' = 'False'; '0=0' = 'True'; '0=1' = 'False'; '0=10' = 'True';

      '1=-1' = 'False'; '1=0' = 'False'; '1=1' = 'True'; '1=10' = 'False';

      '10=-1' = 'False'; '10=0' = 'False'; '10=1' = 'True'; '10=10' = 'True';
    }

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

**Пример 4.** Напишем функцию `Go`, демонстрирующую коммутативность сложения
и некоммутативность вычитания.

    $ENTRY Go {
      = <Prout '1+0=0+1? ' <IsEqual <BinAdd '1' '0'> '=' <BinAdd '0' '1'>>>
        <Prout '1-0=0-1? ' <IsEqual <BinSub '1' '0'> '=' <BinSub '0' '1'>>>;
    }

Функции `BinAdd`, `BinSub`, `IsEqual` и `Go` можно положить в один файл
(назовём его [`binmath-1.ref`](binmath-1.ref)) и откомпилировать следующей
командой:

    rlc binmath-1.ref

то получится исполнимый файл `binmath-1.exe` (или `binmath-1` на unix-like),
который при запуске напечатает

    1+0=0+1? True
    1-0=0-1? False

В этом разделе мы рассмотрели функции, у которых в левых частях предложений
записаны различные, но _фиксированные_ значения. И очевидно, областями
определения таких функций являются все явно перечисленные значения
образцов. Понятно, что для написания нетривиальных программ этого чертовски
мало: можно задать только функции с конечной областью определения и для каждого
из значений аргумента придётся написать предложение. Это привело к тому,
что даже такая простая функция, как `IsEqual` потребовала целых 16 предложений.

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

У внимательного читателя наверняка возник вопрос: а что будет, если несколько
предложений будут иметь одинаковые левые части? Не будет ли это синтаксической
ошибкой? Ответ: не будет. Если аргумент функции таков, что становятся
применимыми несколько предложений, то приоритет имеет то, которое написано выше.
Например, результатом вызова `<F 'A'>` будет `'1'`, а не `'3'`:

    F {
      'A' = '1';
      'B' = '2';
      'A' = '3';
    }

Первое предложение имеет приоритет над третьим.

### Переменные

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

Рефал позволяет записывать в левых частях выражения (точное определение
понятия «выражение» будет дано позже), которые, помимо явно заданных символов,
содержат неизвестные произвольные фрагменты — _переменные_.

Множества значений, которые могут принимать переменные, определяются _типом_
переменной. В Рефале есть три типа переменных: s-, t- и e-переменные.
t-переменные мы рассмотрим позже, когда будем изучать структурные скобки.

Значением _s-переменной_ или _переменной символа_ может быть любой одиночный
символ (symbol). Значением _e-переменной_ или _переменной выражения_ может быть
любой фрагмент аргумента функции, в том числе пустой (не совсем любой, на самом
деле, но об этом позже).

Переменная записывается как признак типа (`s`, `t`, `e`), за которой следует
знак `.` («точка») и имя переменной — некоторая последовательность букв и цифр.
Имя переменной часто называют индексом переменной.

Если в выражении переменная встречается несколько раз, то она называется
_повторной,_ все её вхождения должны иметь одинаковое значение.

Рассмотрим некоторые выражения с переменными:

* `s.1 s.2 s.3` — три любых символа, например `'ABC'`, `'999'`, `'@#$'`.
* `s.A s.A s.A` — три любых _одинаковых,_ символа, например `'666'`, `'www'`.
* `s.Edge s.Middle s.Edge` — три любых символа, причём первый и последний
  должны совпадать. Например: `'@$@'`, `'kek'`, `'^_^'`.
* `s.first e.middle s.last` — любое выражение, содержащее как минимум два
  символа. Например: `'Hello'`, `'10'`, `'0_o'`.
* `s.EDGE e.CENTER s.EDGE` — любое выражение как минимум из двух символов,
  начинающееся и заканчивающееся на одинаковый символ. Например: `'++'`,
  `'LOOOL'`, `'revolver'`.
* `'(' e.Inner ')'` — выражение, начинающееся и заканчивающееся на скобку.
  Примеры: `'()'`, `'()()'`, `'(ok)'`.
* `e.Key '=' e.Value` — выражение, содержащее хотя бы один знак равенства.
  Например: `'='`, `'x=1'`, `'-1=10'`, `'A=B==C=D'`.
* `e.Eq e.Eq` — выражение чётной длины, которое можно разбить на две
  одинаковые половинки: `'ABCABC'`, `'8888'`, пустое выражение (да, его
  тоже можно разбить на два пустых).

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

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

1. Выбирается предложение, из левой части которого можно получить аргумент
   функции путём замены переменных в ней на некоторые значения. Если таких
   предложений несколько, выбирается с наименьшим номером. Если такого
   предложения не нашлось, то программа завершается с ошибкой отождествления
   (recognition impossible).
2. Фиксируются значения переменных, при подстановке которых в левую часть
   выбранного предложения, та обращается в аргумент функции. Если таких
   наборов значений переменных (подстановок) несколько, то фиксируется
   та из них, при которой самая левая e-переменная принимает кратчайшее
   значение, если это не разрешает неоднозначности, то рассматривается
   следующая e-переменная и т.д. (в следующем разделе мы рассмотрим этот
   процесс подробнее).
3. В правой части выбранного предложения заменяются переменные на их
   значения. После чего вычисляются функции в правой части.

В следующем разделе этот процесс будет рассмотрен более детально и формально.


**Пример 5.** Теперь, вооружённые новым знанием, мы можем упростить функцию
`IsEqual`:

    IsEqual {
      e.Equal '=' e.Equal = 'True';
      e.Left '=' e.Right = 'False';
    }

Видно, что, во-первых, функция сократилась с 16 предложений до двух, во-вторых,
её область определения существенно расширилась — она принимает не только
пары двоичных чисел, но и вообще любые выражения, содержащие знак `'='`.

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

Второе предложение применимо к любому аргументу, содержащему знак равенства.

Очевидно, что для аргументов вида `'ab=ab'` применимы оба предложения, первое,
поскольку до и после знака `'='` находятся одинаковые выражения, второе,
потому что просто содержит знак равенства. Но, как было сказано выше,
предшествующие предложения имеют приоритет над последующими, поэтому первое
предложение будет обрабатывать только случаи равных «половинок», а второму
будут доставаться все остальные (неравные).

Если оба предложения поменять местами, то результатом функции (на своей области
определения) всегда будет `'False'`.

**Пример 6.** Функция `IsPalindrome`, проверяющая, является ли аргумент функции
палиндромом.

    IsPalindrome {
      s.OneSymbol = 'True';
      /* empty */ = 'True';
      s.Equal e.Middle s.Equal = <IsPalindrome e.Middle>;
      e.Other = 'False';
    }

Определение этой функции можно прочитать так. Строка из одного символа является
палиндромом. Пустая строка тоже является палиндромом. Строка, которая начинается
и заканчивается на один и тот же символ, является палиндромом, если «средняя»
часть строки тоже является палиндромом. Любая другая строка палиндромом
не является.

Вообще, определения функций на ФЯ часто могут читаться как математические
определения.

**Пример 7.** Напишем функцию сложения двух двоичных чисел произвольной длины.
Функции на Рефале принимают один аргумент, а здесь мы хотим передать два.
В первом варианте функции сложения мы избежали этого затруднения, передавая
в функцию два _символа._ Теперь нам надо передать два выражения произвольной
длины. Каждый из аргументов может состоять только из знаков `'0'` и `'1'`,
поэтому можно между ними поместить любой символ, кроме нуля и единицы — по нему
можно будет понять, где кончается один аргумент и начинается другой. Будем
использовать символ `'+'` для наглядности.

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

    BinAdd {
      e.Num1 '0' '+' e.Num2 '0' = <BinAdd e.Num1 '+' e.Num2> '0';
      e.Num1 '0' '+' e.Num2 '1' = <BinAdd e.Num1 '+' e.Num2> '1';
      e.Num1 '1' '+' e.Num2 '0' = <BinAdd e.Num1 '+' e.Num2> '1';
      e.Num1 '1' '+' e.Num2 '1'
        = <BinAdd <BinAdd e.Num1 '+' '1'> '+' e.Num2> '0';
      /* empty */ '+' e.Num2 = e.Num2;
      e.Num1 '+' /* empty */ = e.Num1;
    }

Нетрудно заметить, что функция реализует сложение двух двоичных чисел в столбик.
Если последние цифры обоих чисел — `'1'` и `'1'`, то происходит перенос
в следующий разряд — эта дополнительная единица прибавляется к первому
аргументу.

#### Промежуточные выводы

Давайте подытожим:

* В левых и правых частях предложения могут находиться переменные — фрагменты
  выражений, которые могут заменяться на произвольные значения в соответствии
  с их типом.
* S-переменные могут заменяться на любой символ.
* E-переменные могут заменяться на произвольное выражение.
* Синтаксис имён переменных: `s.varname`, `e.ab123`, `s.123ab`.
* Выполняется то предложение в функции, для левой части которого можно
  подобрать такую подстановку значений переменных, которая преобразует левую
  часть в аргумент функции.
* Та же подстановка производится и в правую часть предложения.

### Структурные скобки

Чисто математически изученного подмножества Рефала достаточно для записи любого
сколь угодно сложного алгоритма (см. \[4, лекция № 6]). Но на практике этого
мало: изученные средства позволяют работать только с «плоскими» строками
символов, тогда как многие нетривиальные алгоритмы требуют уже иерархически
организованных данных.

Что такое иерархия данных? Это возможность работать с некоторым фрагментом
данных, как с одним объектом, абстрагируясь от его внутренней сложной структуры.
Например, мы можем работать с текстовым документом как с файлом: перемещать
его из папки в папку, копировать, стирать, и при этом не заботиться о том,
что внутри него может находиться текст, таблицы, картинки и т.д. На определённом
уровне иерархии нас это не интересует.

Для того, чтобы в Рефале с выражением работать как с единым объектом, его
заключают в круглые скобки, которые называют _структурными скобками._ Такой
объект, его называют _скобочный терм,_ сам может быть частью другого выражения,
которое, в свою очередь, тоже может быть заключено в круглые скобки. Так в Рефале
строятся иерархические вложенные данные. Символы (symbols), которые мы
рассматривали до этого, тоже являются термами. Таким образом, выражение
на Рефале состоит из термов, каждый из которых может быть либо символом, либо
скобочным термом, который внутри содержит другое выражение на Рефале.

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

**Пример 8.** Выражение

    ('abc') 'def' (('ghi') 'j' ('klm') ()) 'nop' ((('rst')))

состоит из 9 термов. Первый терм — скобочный, содержит в себе выражение из трёх
термов-символов, следующие три — печатные знаки `'def'`, следующий — опять
скобочный, состоящий из трёх скобочных термов и одного символа, при этом
его последний скобочный терм содержит пустое выражение.

В выражении на Рефале скобки должны обязательно образовывать правильную
скобочную структуру как в левой, так и в правой части предложений. При этом
в правой части предложений круглые и угловые скобки не могут накладываться
(overlap) друг на друга.

Уточним наше понимание переменных в свете нового знания.

* E-переменные могут принимать произвольную последовательность _термов,_
  т.е. значением e-переменной может быть только выражение с правильной
  скобочной структурой.
* Значением _t-переменных_ (записываются как `t.varname`) может быть любой
  одиночный терм — как символ (symbol), так и выражение в скобках.

**Пример 9.** Изобразим родословную Пушкина в виде выражения на Рефале.
Каждого персонажа родословной мы будем изображать в виде скобочного терма,
который содержит имя персонажа и два терма: отец и мать. Причём, если
предок известен, он изображается в виде такого же персонажа, если нет —
на его месте будет располагаться символ `'?'`. Таким образом, каждый
из персонажей может быть сопоставлен с образцом вида

    (e.Name t.Father t.Mother)

Собственно, родословная \[5, 6]:

    (
      'Александр Сергеевич Пушкин'
      (
        'Сергей Львович Пушкин'
        (
          'Лев Александрович Пушкин'
          '?'   /* не известен отец */
          (
            'Евдокия Ивановна Головина'
            '?' /* не известен отец */
            '?' /* не известна мать */
          )
        )
        (
          'Ольга Васильевна Чичерина'
          ('Василий Иванович Чичерин??')
          '?'   /* не известна мать */
        )
      )
      (
        'Надежда Осиповна Пушкина (Ганнибал)'
        (
          'Осип Абрамович Ганнибал'
          ('Абрам Петрович Ганнибал (арап Петра Великого)??')
          ('Христина-Регина фон-Шеберг??')
        )
        ('Мария Алексеевна Пушкина??')
      )
    )

Примечание. _На самом деле родословная А. С. Пушкина известна гораздо глубже,
здесь просто для наглядности были пропущены некоторые предки на разных уровнях
иерархии._

**Пример 10.** Давайте напишем функцию, которая принимает генеалогическое
древо и ветвь предка в виде цепочки знаков вида `'MFFM…'` — где `'M'`
означает мать, `'F'` — отец и находит соответствующего предка.

Например, `'F'` — отец, `'FF'` — дед по отцу, `'MM'` — бабка по матери,
`'FM'` — бабка по отцу, `'FMM'` — прабабка по бабке по отцу, пустое выражение —
сам персонаж.

    FindAncestor {
      /* продвигаемся по отцу */
      (e.Name t.Father t.Mother) 'F' e.Branch
        = <FindAncestor t.Father e.Branch>;

      /* продвигаемся по матери */
      (e.Name t.Father t.Mother) 'M' e.Branch
        = <FindAncestor t.Mother e.Branch>;

      /* у неизвестного персонажа неизвестны и предки */
      '?' e.Branch = '?';

      /* Ветвь закончилась — искомый человек текущий */
      (e.Name t.Father t.Mother) /* empty branch */ = e.Name;
    }

Иначе говоря, чтобы по родословной найти какого-то предка по отцу (ветвь
начинается с `'F…'`), нужно взять родословную отца (поле `t.Father`)
и поискать предка в ней (отбросив от начала ветви `'F'`) — именно это
делает первое предложение. Второе предложение аналогично.

Если родословная на некотором этапе неизвестна, то и любой предок будет
неизвестен — этот случай обрабатывает третье предложение. Если ветвь
пустая (явно указана пустая ветвь или опустошилась за несколько итераций),
то корень текущей родословной и есть искомый человек — последнее четвёртое
предложение.

**Пример 11.** Давайте напишем программу, которая распечатывает некоторых
предков Пушкина ([`pushkin.ref`](pushkin.ref)).

    $ENTRY Go {
      = <Prout <FindAncestor <Pushkin> 'FF'>>
        <Prout <FindAncestor <Pushkin> 'FFF'>>
        <Prout <FindAncestor <Pushkin> 'MFF'>>
        <Prout <FindAncestor <Pushkin> 'MFM'>>
        <Prout <FindAncestor <Pushkin> 'F'>>
        <Prout <FindAncestor <Pushkin> 'FM'>>
        <Prout <FindAncestor <Pushkin> 'FMF'>>
        <Prout <FindAncestor <Pushkin> 'FMFM'>>
    }

    FindAncestor {
      …см. выше…
    }

    Pushkin {
      = (
          'Alexander Sergeyevich Pushkin'
          (
            'Sergey Lvovich Pushkin'
            (
              'Lev Aleksandrovich Pushkin'
              '?'   /* unknown father */
              (
                'Evdokia Ivanovna Golovin'
                '?' /* unknown father */
                '?' /* unknown mother */
              )
            )
            (
              'Olga Vasilievna Chicherina'
              ('Vasily Ivanovich Chicherin??')
              '?'   /* unknown mother */
            )
          )
          (
            'Nadezhda Ossipovna Pushkina (Gannibal)'
            (
              'Ossip Abramovich Gannibal'
              ('Abram Petrovich Gannibal (The Moor of Peter the Great)??')
              ('Christina Regina von Sioberg??')
            )
            ('Maria Alekseevna Pushkina??')
          )
        )
    }

Функция `Pushkin` состоит из одного предложения — при любом аргументе возвращает
константу. Т.е. фактически она и является определением константы. Остальное всё
должно быть понятно.

Примечание. _Имена предков записаны транслитом — на некоторых операционных
системах вывод кириллицы на экран не работает или работает криво. В будущих
версиях это будет исправлено._

Для компиляции и запуска программы под Windows введите:

    rlc pushkin.ref
    pushkin.exe

Под Linux:

    rlc pushkin.ref
    ./pushkin

Программа должна распечатать следующее:

    Lev Aleksandrovich Pushkin
    ?
    Abram Petrovich Gannibal (The Moor of Peter the Great)
    Christina Regina von Sioberg
    Sergey Lvovich Pushkin
    Olga Vasilievna Chicherina
    Vasily Ivanovich Chicherin
    ?

Выше мы, когда хотели вызвать функцию с несколькими аргументами, передавали их,
разделяя каким-нибудь знаком, который не может встречаться внутри самих
аргументов (например, `'='` в функции `IsEqual` или `'+'` в функции `BinAdd`).
Более грамотной практикой при передаче нескольких аргументов является их
«заворачивание» в скобочные термы. Например, если функция принимает 3 аргумента
произвольной длины — обозначим их как `e.1`, `e.2`, `e.3`, — то их можно
передать как `(e.1) e.2 (e.3)`, `e.1 (e.2) (e.3)`, `(e.1) (e.2) e.3`
и `(e.1) (e.2) (e.3)`. Последний вариант, помещение каждого аргумента
в скобочный терм, избыточен, но иногда делает программы более понятными. Вообще,
если передаётся в функцию N аргументов, то достаточно завернуть в скобки
только N−1 аргументов.

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

Функции `IsEqual` и `BinAdd` мы можем теперь переписать так:

    IsEqual {
      (e.X) (e.X) = 'True';
      (e.X) (e.Y) = 'False';
    }

    BinAdd {
      (e.Num1 '0') e.Num2 '0' = <BinAdd (e.Num1) e.Num2> '0';
      (e.Num1 '0') e.Num2 '1' = <BinAdd (e.Num1) e.Num2> '1';
      (e.Num1 '1') e.Num2 '0' = <BinAdd (e.Num1) e.Num2> '1';
      (e.Num1 '1') e.Num2 '1' = <BinAdd (<BinAdd (e.Num1) '1'>) e.Num2> '0';
      (/* empty */) e.Num2 = e.Num2;
      (e.Num1) /* empty */ = e.Num1;
    }

### Другие типы символов: числа

Выше по тексту мы использовали понятия символы (symbols) и печатные знаки
(characters) как синонимы. Но это не так. Помимо печатных знаков (characters),
которые далее по тексту мы будем называть _символами-литерами_ (characters),
Рефал поддерживает и другие виды символов.

Вообще в Рефале _символ_ (symbol) — это объект, который невозможно разложить
при помощи образца на более мелкие фрагменты. Помимо символов-литер, в Рефале
есть ещё символы-числа и символы-слова. Символы-слова мы рассмотрим в следующем
параграфе.

_Символ-число_ или _макроцифра_ (macrodigit) — это число в диапазоне от 0
до 2³²−1, записанное в десятичном виде. Примеры: `1`, `10`, `65536`,
`4294967295` (самая большая макроцифра).

Для работы с макроцифрами в Рефале есть встроенные арифметические функции:

* `Add` — сложение,
* `Sub` — вычитание,
* `Mul` — умножение,
* `Div` — деление (вычисление частного),
* `Mod` — вычисление остатка от деления,
* `Divmod` — возвращает и частное, и остаток,
* `Compare` — сравнивает два числа,
* `Numb` — преобразует цепочку литер в число (в десятичной записи),
* `Symb` — преобразует число в цепочку литер (тоже в десятичной записи).

Читателя должно заинтересовать такое странное слово, как «макроцифра». Объясняем:
арифметические функции реализуют арифметику произвольной точности (длинную
арифметику, arbitrary-precision arithmetic) — работу с числами произвольной
длины. И для представления таких чисел используются цепочки макроцифр.

Точно так же, как в обычной десятичной записи, число 1864 означает

    1864 = 1×10³ + 8×10² + 6×10 + 4

в Рефале длинное число, например, 10000000000000000000000 представляется как
`542 434162106 2990538752`, что обозначает

    10000000000000000000000 = 542×(2³²)² + 434162106×2³² + 2990538752

т.е. основанием системы счисления является не 10, а 2³². Для записи
отрицательных чисел в начале цепочки макроцифр следует поставить литеру `'-'`,
в начало положительных чисел можно записывать необязательный знак `'+'`.

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

Функции `Add`, `Sub`, `Mul`, `Div`, `Mod`, `Divmod` и `Compare` принимают
два числа. Если первое число — небольшое положительное (макроцифра), то оно
макроцифрой и записывается. Иначе первый аргумент записывается в виде скобочного
терма. Второй аргумент пишется вслед за первым.

Функция `Divmod` возвращает частное в скобках и остаток. Функция `Compare`
возвращает знак разности первого и второго числа, соответственно `'+'`, `'0'`
или `'-'`, когда первое больше, равно или меньше второго.

Функция `Numb` принимает строку. Если строка начинается с необязательного
знака и десятичных цифр, то функция возвращает число, представимое этими
цифрами. Иначе (если аргумент не начинается с десятичной записи числа) функция
возвращает `0`.

Функция `Symb` обратна функции `Numb` — преобразует число в десятичную запись

**Пример 12.** Некоторые вызовы функций и их результаты рядом:

    <Add 1 2>                          3
    <Sub 1 2>                          '-' 1
    <Add 1 2 3>                        2 4
    <Add (1) 2 3>                      2 4
    <Add (2 3) 1>                      2 4
    <Add ('-' 7) 17>                   10
    <Mul (1 1) 1 1>                    1 2 1
    <Div (1 2 3) 1 1>                  1 1
    <Mod (1 2 3) 1 1                   2
    <Divmod (1 2 3) 1 1>               (1 1) 2
    <Compare 10 13>                    '-'
    <Compare (0 0 100) 0 100>          '0'
    <Compare (1 2) 1 0 0>              '-'
    <Numb '10abcdef'>                  10
    <Numb '-11113'>                    '-' 11113
    <Numb 'not a number>               0
    <Numb '10000000000000000000000'>   542 434162106 2990538752
    <Symb 123456>                      '123456'
    <Symb '-' 1 1>                     '-4294967297'
    <Symb 542 434162106 2990538752>    '10000000000000000000000'

**Пример 13.** Функция вычисления факториала. Напомним, что факториал числа N
(обозначается N!, читается «эн факториал») — это произведение всех чисел от 0
до N включительно. Т.е. N! = 1×2×…×(N−1)×N. Считается, что 0! = 1.

Можно заметить, что N! = 1×2×…×(N−1)×N = (1×2×…×(N−1))×N = (N−1)!×N. При этом
1! = (1−1)!×1 = 0!×1 = 1×1 = 1. Воспользуемся этим, чтобы написать функцию.

    Fact {
      0 = 1;
      s.N = <Mul (<Fact <Sub s.N 1>>) s.N>;
    }

    $ENTRY Go {
      = <Prout '1!   = ' <Symb <Fact 1>>>
        <Prout '10!  = ' <Symb <Fact 10>>>
        <Prout '100! = ' <Symb <Fact 100>>>
    }

Заметим, что первый аргумент функции `Mul` мы завернули в скобки, а первый
аргумент `Sub` — нет. Почему? Потому что уже

    13! = 6227020800 > 4294967296 = 2³².

Т.е. для аргументов, больших 12, факториал уже перестанет влезать в одну
макроцифру. У функции `Sub` первый аргумент всегда влезает в макроцифру,
поскольку он изначально задаётся макроцифрой и на каждом шаге рекурсии он
только уменьшается. Приведённая выше программа [`fact.ref`](fact.ref)
напечатает на экране следующее (последняя строка слишком длинная, для
удобства чтения разбита на части)

    1!   = 1
    10!  = 3628800
    100! = 9332621544394415268169923885626670049071596826438162146859↓
    29638952175999932299156089414639761565182862536979208272237582511↓
    85210916864000000000000000000000000

### Другие типы символов: слова

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

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

    <ReadConfig e.FileName>

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

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

Можно эти случаи просто пронумеровать. В первом случае функция вернёт
макроцифру `1` и данные, во втором — только макроцифру `2` и в третьем —
число `3` и сообщение об ошибке. Да, результаты функции можно будет различить,
но главный недостаток такого решения — числа сами за себя не говорят.
Программист будет вынужден помнить, что, например, для этой функции цифра
`3` означает синтаксическую ошибку, а `2` — отсутствие файла, и не наоборот.
А если таких разных функций много? Придётся учить, что каждое число значит
применительно к каждой функции.

Можно возвращать последовательность литер. Например, в первом случае
выводить `'Success' (e.Configuration)`, во втором — `'File not found'`,
в третьем — `'Syntax error' (e.ErrorMessage)`. Текстовые строки уже говорят
сами за себя, понимать программу становится легко. Но у этого решения тоже
есть свой недостаток — текстовые строки — выражения произвольной длины,
и когда функция возвращает другие данные произвольной длины, например,
конфигурацию или сообщение об ошибке, их приходится отделять круглыми скобками.
Более того, избыточно передавать пару десятков символов (symbols), когда
для различия достаточно одного.

Для различия достаточно одного. Может нам сократить по первой букве? Тогда
вместо `'Success' (e.Configuration)` мы запишем `'S' e.Configuration`,
вместо `'File not found'` запишем `'F'`, вместо `'Syntax error (e.ErrorMessage)`
запишем `'S' e.ErrorMessage`. Стоп, стоп, стоп. Чем у нас тогда будет
отличаться первый и последний случай? Они оба начинаются на знак `'S'`,
после которого может следовать выражение произвольной длины. Сократить
по первой букве не получилось — придётся выбирать какие-то другие буквы.
Но тогда всплывёт та же проблема, что и с числами — одиночные буквы плохо
сами за себя говорят.

Вот для решения этой проблемы в Рефале существуют _символы-слова
(символы-идентификаторы, составные символы)._ Это символы (symbols),
сопоставляются с обычной s-переменной, но имеют вид слова без кавычек.
Внешний вид идентификатора точно такой же, как у имени функции: он состоит
из букв, цифр, прочерков и дефисов, но при этом обязан начинаться с буквы
или прочерка. Примеры идентификаторов: `Success`, `FILE_NOT_FOUND`,
`syntax-error`, `True`, `False`, `Error-404-Not-found`, `o_0` и т.д.

Теперь уже очевидно, что для нашей функции `ReadConfig` в возвращаемом значении
нужно использовать идентификаторы. Например, `Success e.Config`, `FileNotFound`
и `SyntaxError e.Message`.

Рефал-5λ, как и классический РЕФАЛ-5, допускает использование произвольных
строк символов в качестве идентификаторов. Для этого строку нужно заключить
в _двойные_ кавычки: `"This is one symbol:-)"`. На практике они используются
довольно редко, но могут быть полезны, когда хочется использовать в качестве
признака-идентификатора комбинацию знаков, которую без кавычек записать нельзя.
Например, `"*="`, `"C++"`, `"=0?"` и т.д. Можно записывать в кавычках слова,
которые пишутся и без кавычек тоже — `"Success"`, `"SyntaxError"` — они будут
идентичны этим же словам без кавычек.

#### Escape-последовательности

На первый взгляд может показаться, что невозможно записать литеру, представляющую
одинарную кавычку, либо составной символ, содержащий внутри двойную кавычку.
Но это не так. И в цепочке литер, и в составном символе можно использовать
так называемые _escape-последовательности_ — специальные обозначения для
некоторых символов.

Escape-последовательность выглядит как знак `\`, за которым следует один или
несколько других знаков. Все они вместе образуют одну литеру (если записаны
внутри одинарных кавычек), либо один из знаков составного символа. В Рефале-5λ
допустимы следующие escape-последовательности:

* `\'` — одинарная кавычка, `'`,
* `\"` — двойная кавычка, `"`,
* `\\` — обратная косая черта, `\`,
* `\n` — перевод строки, LF,
* `\r` — возврат каретки, CR,
* `\t` — знак табуляции,
* `\xHH` — символ с кодом `HH` в шестнадцатеричной записи, например,
  `\x07` — звуковой сигнал, `\x0A` — перевод строки (то же, что и `\n`),
  поскольку имеет код 10, `\x3F` — знак вопроса `?`,
* `\<`, `\>`, `\(`, `\)` — то же, что и `<`, `>`, `(`, `)` —
  escape-последовательности, поддерживаемые классическим РЕФАЛом-5,
  поддерживаются и в Рефале-5λ.

Понятно, что внутри одинарных кавычек можно использовать двойную без
экранирования (знака `\`), и наоборот. Но для единообразия язык разрешает
писать `\"` внутри апострофов и наоборот.

**Пример 13.**

* Запись `'Abc\ndef\'ghi\\jkl\x6D\x6e'` обозначает последовательность
  из 17 литер: `'A'`, `'b'`, `'c'`, знак перевода строки, `'d'`, `'e'`, `'f'`,
  одинарная кавычка, `'g'`, `'h'`, `'i'`, знак обратной косой черты, `'j'`,
  `'k'`, `'l'`, `'m'`, `'n'` (последние два записаны в шестнадцатеричной
  форме).
* Запись `"Hello, \"World\'!"` — это слово, состоящее из 15 знаков. Знак `\`
  перед одинарной кавычкой здесь избыточен, это же слово можно записать как
  `"Hello, \"World'!"` или `"Hello, \x22World'"`.

### Абстрактная рефал-машина. Семантика поля зрения

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

Говорят, что программу на Рефале выполняет _абстрактная рефал-машина,_ —
воображаемая вычислительная машина, понимающая синтаксис программ на Рефале.
У этой машины есть две области памяти: поле программ (program field), хранящее
все определения функций программы, и поле зрения (view field), хранящее текущее
состояние вычислений. Состояние вычислений описывается в виде _активного
выражения_ — выражения языка Рефал, которое содержит скобки активации, но при
этом не может содержать переменных.

Рефал-машина выполняет программу по шагам. Каждый шаг — это выполнение следующей
последовательности действий.

1. Рефал-машина находит в поле зрения самую левую пару скобок активации, такой
   что внутри этого вызова не находится других угловых скобок. Этот участок поля
   зрения называется первичным активным подвыражением (primary active
   sub-expression).
2. Рефал-машина смотрит, что находится справа от левой скобки активации: там
   должно располагаться имя функции. Если его там нет (язык позволяет написать
   такую программу), то рефал-машина останавливается с ошибкой «отождествление
   невозможно» (recognition impossible).
3. Рефал-машина находит имя функции в поле программ. Функция может быть как
   написанной на Рефале, так и встроенной. Если функция встроенная,
   рефал-машина передаёт управление на процедуру в машинном коде, реализующую
   логику этой функции. Если эта функция написана на Рефале, машина выбирает
   первое предложение функции.
4. Если можно подобрать такие значения переменных в левой части текущего
   предложения, что та обратится в аргумент функции, то выполняется пункт 5.
   В противном случае выбирается следующее предложение и повторяется пункт 4.
   Если предложений больше нет, то рефал-машина останавливается с ошибкой
   «отождествление невозможно».
5. Найденные значения переменных подставляются в правую часть текущего
   предложения. Полученное выражение Рефал-машина вставляет в поле зрения
   на место первичного активного подвыражения.
6. Если в поле зрения остались скобки активации, то рефал-машина выполняет
   следующий шаг — возвращается к пункту 1. В противном случае рефал-машина
   корректно завершается.

Начальным содержимым поля зрения является вызов функции `GO` с пустым
аргументом:

    <GO>

если в программе определена функция `GO`, либо вызов `Go`:

    <Go>

если определена функция `Go`. Если ни той, ни другой функции нет, то программа
не запустится.

Примечания.

1. _Классический РЕФАЛ-5 не поддерживает пустые функции, в любой
   функции должно быть хотя бы одно предложение. Рефал-5λ поддерживает — вызов
   такой функции приводит к ошибке невозможности отождествления._
2. _Текущая реализация на момент создания программы не может проверить, что
   функция `GO` или `Go` в программе отсутствует. В этом случае будет создана
   программа, которая при запуске выводит сообщение об ошибке и завершается.
   Возможно, это будет исправлено в следующих версиях._

Из этого алгоритма можно сделать два важных вывода.

Во-первых, первичным активным подвыражением выбирается самая левая пара скобок
активации, не содержащая внутри себя других скобок активации. Из этого следует,
что Рефал — _аппликативный язык,_ причём порядок вычисления функций чётко
определён: слева-направо. Т.е. если записано несколько вызовов функций в правой
части предложения, то они будут вычисляться слева-направо, от самых внутренних
к самым внешним. Поэтому мы можем использовать функции с побочным эффектом,
(например, `Prout`) чётко зная, когда этот побочный эффект будет выполняться.

Во-вторых, из семантики поля зрения непосредственно следует, что Рефал реализует
так называемую _оптимизацию хвостовой рекурсии._

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

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

**Пример 14.** Проиллюстрируем это простейшим примером — рассмотрим процесс
вычисления функции `Fab`, заменяющей все литеры `'a'` на литеры `'b'`
(программа [`fab-1.ref`](fab-1.ref)):

    $ENTRY Go {
      = <Prout <Fab 'abracadabra'>>;
    }

    Fab {
      'a' e.Rest = 'b' <Fab e.Rest>;
      s.Other e.Rest = s.Other <Fab e.Rest>;
      /* empty */ = /* empty */;
    }

Начальным содержимым поля зрения будет вызов функции `Go`:

    <Go>

Рефал-машина на первом шаге найдёт этот вызов (он будет первичным активным
подвыражением), увидит имя `Go` после `<` и найдёт в поле программ функцию `Go`.
Функция вызывается с пустым аргументом, первое предложение имеет пустую левую
часть. Переменных в левой и правой части нет, поэтому рефал-машина просто
заменит вызов `<Go>` на правую часть предложения:

    <Prout <Fab 'abracadabra'>>
           ^^^^^^^^^^^^^^^^^^^

Первичным активным подвыражением здесь будет вызов функции `Fab`, поскольку
он не содержит вложенных скобок активации (вызов `Prout` содержит внутри себя
скобки активации вызова `Fab`).

Рефал-машина увидит `Fab` после `<` и попробует отождествить (match) аргумент
`'abracadabra'` с левой частью первого предложения `'a' e.Rest`. Отождествление
возможно: если вместо `e.Rest` подставить `'bracadabra'`, то левая часть
превратится в аргумент. Указанную подстановку (`e.Rest → 'bracadabra'`)
рефал-машина применяет к правой части предложения — получается выражение
`'b' <Fab 'bracadabra'>` и заменяет вызов функции на это выражение:

    <Prout 'b' <Fab 'bracadabra'>>
               ^^^^^^^^^^^^^^^^^^

На третьем шаге первичным активным подвыражением опять будет вызов функции
`Fab`. Но левую часть первого предложения отождествить с аргументом невозможно:
образец начинается с `'a'`, но аргумент — с `'b'`. Выбирается второе
предложение. Отождествление возможно: существует подстановка переменных
`s.Other → 'b', e.Rest → 'racadabra'`. Подстановка применяется к правой части,
результат подстановки (`'b' <Fab 'racadabra'>`) подставляется в поле зрения
на место первичного активного подвыражения:

    <Prout 'bb' <Fab 'racadabra'>>
                ^^^^^^^^^^^^^^^^^

Несколько следующих шагов выполняются в том же духе:

    <Prout 'bbr' <Fab 'acadabra'>>
                 ^^^^^^^^^^^^^^^^
    <Prout 'bbrb' <Fab 'cadabra'>>
                  ^^^^^^^^^^^^^^^
    <Prout 'bbrbc' <Fab 'adabra'>>
                   ^^^^^^^^^^^^^^
    <Prout 'bbrbcb' <Fab 'dabra'>>
                    ^^^^^^^^^^^^^
    <Prout 'bbrbcbd' <Fab 'abra'>>
                     ^^^^^^^^^^^^
    <Prout 'bbrbcbdb' <Fab 'bra'>>
                      ^^^^^^^^^^^
    <Prout 'bbrbcbdbb' <Fab 'ra'>>
                       ^^^^^^^^^^
    <Prout 'bbrbcbdbbr' <Fab 'a'>>
                        ^^^^^^^^^

На этом этапе рефал-машина выполнит первое предложение функции `Fab`,
подстановка будет интересна тем, что `e.Rest` получит значение пустого
выражения.

    <Prout 'bbrbcbdbbrb' <Fab>>
                         ^^^^^

Тут тоже рефал-машина будет выполнять функцию `Fab`, но первое предложение
не подходит (невозможно отождествить выражение, которое начинается на `'a'`,
с пустым выражением), второе — тоже (невозможно отождествить выражение,
которое начинается на символ с пустым). А вот третье подойдёт — пустая левая
часть успешно отождествляется с пустым аргументом. И рефал-машина заменит
вызов функции `<Fab>` на пустую правую часть третьего предложения:

    <Prout 'bbrbcbdbbrb'>
    ^^^^^^^^^^^^^^^^^^^^^

Теперь уже первичным активным подвыражением будет вызов функции `Prout`.
Рефал-машина заметит, что это встроенная функция и вызовет соответствующую
машинную процедуру для вычисления её результата. Машинная процедура напечатает
на экране `bbrbcbdbbrb` и возвратит пустое выражение. На пустое выражение
заменится вызов `Prout` в поле зрения.

Поле зрения станет пустым — рефал-машина корректно остановится.

#### Хвостовая и нехвостовая рекурсия

При _хвостовой рекурсии,_ как сказано выше, рекурсивный вызов в правой части
выполняется последним. Продемонстрируем наглядно, почему это так. Рассмотрим
функцию `Rec1`, которая осуществляет вызов функции `F` в правой части и самой
себя:

    Rec1 {
      продолжение = <F ...> <Rec1 ...>;
      окончание = rec1-res;
    }

Развитие поля зрения будет выглядеть примерно так:

    <Rec1 ...>
    ^^^^^^^^^%
    <F ...> <Rec1 ...>
    ^^^^^^^
    f-res <Rec1 ...>
          ^^^^^^^^^^
    f-res <F ...> <Rec1 ...>
          ^^^^^^^
    f-res f-res <Rec1 ...>
                ^^^^^^^^^^
    . . . . .
    f-res f-res .... f-res rec1-res

Видно, что невычисленные вызовы функций нигде не накапливаются. На каждом шаге
перед вызовом `Rec1` размещается вызов `F`, который завершается до вызова
`Rec1`.

Рассмотрим функцию `Rec2`, которая незначительно отличается от функции `Rec1`:

    Rec2 {
      продолжение = <Rec2 ...> <F ...>;
      окончание = rec2-res
    }

Здесь наоборот — сначала вызывается `Rec2`, потом `F`. И поле зрения будет
развиваться совсем иначе:

    <Rec2 ...>
    ^^^^^^^^^^
    <Rec2 ...> <F ...>
    ^^^^^^^^^^
    <Rec2 ...> <F ...> <F ...>
    . . . . . .
    <Rec2 ...> <F ...> <F ...> ... <F ...>
    ^^^^^^^^^^
    rec2-res <F ...> <F ...> ... <F ...>
             ^^^^^^^
    rec2-res f-res <F ...> ... <F ...>
                   ^^^^^^^
    . . . . . .
    rec2-res f-res ... f-res <F ...>
                             ^^^^^^^
    rec2-res f-res ... f-res f-res

Здесь уже накапливаются невычисленные вызовы `F`, и они накапливаются до тех
пор, пока функция `Rec2` не перестанет вызывать себя рекурсивно.

Аналогично получается со вложенными вызовами функций. Рекурсия в функции `Rec3`
хвостовая:

    Rec3 {
      продолжение = <Rec3 ... <F ...> ...>;
      окончание = rec3-res;
    }

    <Rec3 ...>
    ^^^^^^^^^^
    <Rec3 ... <F ...> ...>
              ^^^^^^^
    <Rec3 ... f-res ...>
    ^^^^^^^^^^^^^^^^^^^^
    <Rec3 ... <F ...> ...>
              ^^^^^^^
    . . . . .
    <Rec3 ... f-res ...>
    ^^^^^^^^^^^^^^^^^^^^
    rec3-res

Рекурсия в функции `Rec4` не хвостовая:

    Rec4 {
      продолжение = <F ... <Rec4 ...> ...>;
      окончание = rec4-res;
    }

    <Rec4 ...>
    ^^^^^^^^^^
    <F ... <Rec4 ...> ...>
           ^^^^^^^^^^
    <F ... <F ... <Rec4 ...> ...> ...>
                  ^^^^^^^^^^
    . . . . . .
    <F ... <F ... ... <F ... rec4-res ...> ... ...> ...>
                      ^^^^^^^^^^^^^^^^^^^^
    . . . . . .
    <F ... <F ... f-res ...> ...>
           ^^^^^^^^^^^^^^^^^
    <F ... f-res ...>
    ^^^^^^^^^^^^^^^^^
    f-res

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

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

### Объектные, образцовые, активные и результатные выражения

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

* _Объектным выражением_ (object expression) называется выражение языка Рефал,
  которое может содержать только символы и круглые скобки. Соответственно,
  термы, из которых составлено объектное выражение, называются _объектными
  термами_ (object terms). Аргументом функции может быть только объектное
  выражение.
* _Активным выражением_ (active expression) или _определённым выражением_
  (ground expression) называется выражение, которое содержит символы, круглые
  и угловые скобки. Содержимым поля зрения может быть только активное
  выражение.
* _Образцовым выражением_ (pattern expression) или _образцом_ (pattern)
  называется выражение, составленное из символов, структурных скобок
  и переменных. Левая часть предложения является образцовым выражением.
* _Результатным выражением_ (result expression) или _результатом_ (result)
  называется выражение, содержащее символы, круглые и угловые скобки
  и переменные. Правые части предложений являются результатными выражениями.

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

Все четыре типа выражений можно изобразить в виде вот такой диаграммы:

     Объектное выражение:        переменные        Образцовое выражение:
           символы           → → → → → → → → →       символы, круглые
       и круглые скобки                             скобки, переменные
              ↓                                             ↓
              ↓ скобки вызова                               ↓ скобки вызова
              ↓                                             ↓
     Активное выражение:         переменные        Результатное выражение:
      символы, круглые       → → → → → → → → →   символы, круглые и угловые
      и угловые скобки                               скобки, переменные

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

### Алгоритм сопоставления с образцом и открытые e-переменные

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

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

1. Подстановка переменных в левую часть должна превращать образец в аргумент
   функции.
2. Значения, подставляемые вместо переменных, должны соответствовать типам
   этих переменных. S-, t- и e-переменные могут заменяться только
   на, соответственно, символы, термы и произвольные выражения.
3. Если в образце несколько раз встречается переменная с одним и тем же
   именем, то все её вхождения должны заменяться на одно и то же значение.
4. Если существует несколько подстановок переменных, соответствующих
   требованиям 1-3, то выбирается из них та, у которой длина самого левого
   вхождения e-переменной является кратчайшей. Если это не разрешает
   неоднозначности, то рассматривается следующая e-переменная и т.д.

Самым интересным требованием тут является последний. Поясним его на примере.

**Пример 15.** Рассмотрим сопоставление объектного выражения
`('abra') ('cadabra')` с образцом `(e.L1 s.D e.E1) (e.L2 s.D e.R2)`.

Сопоставление возможно, причём можно построить следующие 8 подстановок
(пустое выражение будем обозначать как `[]`):

    e.L1 → [],     s.D → 'a',  e.R1 → 'bra',  e.L2 → 'c',       e.R2 → 'dabra'
    e.L1 → [],     s.D → 'a',  e.R1 → 'bra',  e.L2 → 'cad',     e.R2 → 'bra'
    e.L1 → [],     s.D → 'a',  e.R1 → 'bra',  e.L2 → 'cadabr',  e.R2 → []
    e.L1 → 'a',    s.D → 'b',  e.R1 → 'ra',   e.L2 → 'cada',    e.R2 → 'ra'
    e.L1 → 'ab',   s.D → 'r',  e.R1 → 'a',    e.L2 → 'cadab',   e.R2 → 'a'
    e.L1 → 'abr',  s.D → 'a',  e.R1 → [],     e.L2 → 'c',       e.R2 → 'dabra'
    e.L1 → 'abr',  s.D → 'a',  e.R1 → [],     e.L2 → 'cad',     e.R2 → 'bra'
    e.L1 → 'abr',  s.D → 'a',  e.R1 → [],     e.L2 → 'cadabr',  e.R2 → []

Согласно четвёртому пункту будут выбраны те подстановки, у которых самое
левое вхождение e-переменной будет кратчайшим. Самая левая e-переменная здесь
это `e.L1`, кратчайшему её вхождению (пустому выражению) соответствуют
первые три подстановки:

    e.L1 → [],  s.D → 'a',  e.R1 → 'bra',  e.L2 → 'c',       e.R2 → 'dabra'
    e.L1 → [],  s.D → 'a',  e.R1 → 'bra',  e.L2 → 'cad',     e.R2 → 'bra'
    e.L1 → [],  s.D → 'a',  e.R1 → 'bra',  e.L2 → 'cadabr',  e.R2 → []

Опять неоднозначность. Смотрим на следующую e-переменную. `e.R1` во всех
трёх случаях имеет одинаковую длину. Смотрим на следующую — `e.L2`.
Кратчайшей подстановке переменной `e.L2` среди этих трёх отвечает первая,
где `e.L2 → 'c'`. Таким образом, будет выбрана подстановка

    e.L1 → [], s.D → 'a', e.R1 → 'bra', e.L2 → 'c', e.R2 → 'dabra'

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

Но декларативное описание никак не определяет, _каким_ образом будет выбрана
подходящая подстановка. И, что ещё хуже, каковы будут временны́е затраты
на сопоставление с таким образцом.

Рассмотрим, как в Рефале-5λ осуществляется сопоставление с образцом.

Примечание. _В \[9, раздел 2.5] описывается алгоритм сопоставления с образцом
немножко с другой точки зрения, и, возможно, кому-то он покажется более
понятным. При написании руководства я не хотел его дублировать или дословно
пересказывать, поэтому дальнейшее изложение построено в терминах трансляции
образца в последовательность элементарных команд._

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

#### Алгоритм порождения императивного кода сопоставления с образцом

Рефал-5λ — это компилятор, который преобразует исходный текст на Рефале
в форму, удобную для выполнения машиной — в последовательность интерпретируемых
команд, либо в код на C++. В обоих случаях модель вычислений _императивная,_
т.е. описываются не свойства конечного результата, а элементарные шаги, к этому
результату приводящие. В данном случае, последовательно выполняя эти шаги,
можно вычислить результат сопоставления: найти подстановку значений переменных,
удовлетворяющие четырём требованиям выше, либо доказать, что такой подстановки
не существует.

Алгоритм, описанный ниже, формирует по заданному образцу последовательность
команд сопоставления для некоторого абстрактного исполнителя. Исполнитель
рассматривает s- и t-переменные образца как одиночные указатели, e-переменные —
как пары указателей, либо указывающих на первый и последний терм выражения,
либо одновременно хранящих особое, «нулевое» значение. Помимо переменных,
присутствующих в образце, исполнитель пользуется диапазонами — промежуточными
рабочими переменными, которые устроены так же, как и e-переменные — в виде
пары указателей. Диапазоны мы будем просто нумеровать и обозначать как
`BN`, где `N` — целое число.

Алгоритм построения при работе будет использовать объекты-указатели, которые
будут обозначаться квадратными скобками с индексами: `[`<sub>N</sub>,
`]`<sub>N</sub>. Эти указатели могут перемещаться по образцу, перескакивая
через его элементы, причём `[`<sub>N</sub> может двигаться только вправо,
а `]`<sub>N</sub> — только влево. Два указателя с одинаковым индексом могут
аннигилировать — исчезать из образца. Аннигилируют они в двух случаях — когда
они непосредственно встречаются, и когда они окружают ещё не сопоставленную
e-переменную, такая переменная называется _закрытой._

_Жёстким элементом_ называется часть образца, которая имеет известную длину
в термах: литеральный символ, любая s- или t-переменная и e-переменная,
которая уже получила своё значение, скобочный терм. Жёсткий элемент мы
будем обозначать как `He`.

**Входные данные** алгоритма: образцовое выражение `P`.

**Выходные данные** алгоритма: последовательность команд сопоставления.

**Шаг 1.** Поместить слева от образца `P` указатель `[`<sub>0</sub>, справа —
`]`<sub>0</sub>:

`[`<sub>0</sub>`P ]`<sub>0</sub>

**Сгенерировать:** `B0 ← аргумент функции`.

Установить переменную `NextK ← 1`.

**Шаг 2.** Если в образце есть указатель `[`<sub>N</sub>, справа от которого
есть жёсткий элемент (за исключением скобочного терма), передвинуть указатель
за жёсткий элемент:

`... [`<sub>N</sub>`He ...` → `... He [`<sub>N</sub>` ...`

**Сгенерировать:** `BN → He BN`.

Вернуться к шагу 2.

**Шаг 3.** (Симметричен шагу 2.) Если в образце есть указатель `]`<sub>N</sub>,
слева от которого есть жёсткий элемент (за исключением скобочного терма),
передвинуть указатель перед жёстким элементом:

`... He ]`<sub>N</sub>` ...` → `... ]`<sub>N</sub>` He ...`

**Сгенерировать:** `BN → BN He`.

Вернуться к шагу 2.

**Шаг 4.** Если в образце есть указатель `[`<sub>N</sub>, справа от которого
располагается круглая скобка `(`, создать пару новых указателей `[`<sub>K</sub>
и `[`<sub>K</sub>, где K равно `NextK`, переместить исходный указатель вправо
за соответствующую `)`, поместить новые указатели справа от `(` и слева от `)`
соответственно:

`... [`<sub>N</sub>` (...) ...` → `... ([`<sub>K</sub>`...]`<sub>K</sub>`) [`<sub>N</sub>`...`

**Сгенерировать:** `BN → (BK) BN`.

`NextK = NextK + 1`

Вернуться к шагу 2.

**Шаг 5.** (Симметричен шагу 4.) Если в образце есть указатель `]`<sub>N</sub>,
слева от которого располагается круглая скобка `)`, создать пару новых
указателей `[`<sub>K</sub> и `]`<sub>K</sub>, где K равно `NextK`, переместить
исходный указатель влево за соответствующую `(`, поместить новые указатели
справа от `(` и слева от `)` соответственно

`... (...) ]`<sub>N</sub>` ...` → `... ]`<sub>N</sub>` ([`<sub>K</sub>`...]`<sub>K</sub>`)...`

**Сгенерировать:** `BN → BN (BK)`.

`NextK = NextK + 1`

Вернуться к шагу 2.

**Шаг 6.** Если в образце есть пара указателей, находящихся рядом друг с другом,
удалить их (первый случай аннигиляции):

`... [`<sub>N</sub>` ]`<sub>N</sub>` ...` → `... ...`

**Сгенерировать:** `BN → []`.

Вернуться к шагу 2.

**Шаг 7.** Если в образце есть пара указателей, окружающих несвязанную
ранее e-переменную, удалить их (второй случай аннигиляции):

`... [`<sub>N</sub>` e.X ]`<sub>N</sub>` ...` → `... e.X ...`

**Сгенерировать:** `e.X ← BN`.

Повторимся, такая переменная называется _закрытой._ При выполнении операции
`BN → e.X` переменная получает значение соответствующего диапазона.

Вернуться к шагу 2.

**Шаг 8.** Найти самый левый указатель `[`<sub>N</sub>, справа от которого
располагается несвязанная ранее e-переменная, передвинуть указатель за эту
переменную:

`... [`<sub>N</sub>` e.X ...` → `... e.X [`<sub>N</sub>`...`

**Сгенерировать:** `Loop BN → e.X BN`

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

Для каждой пары указателей повторять:

* Заменить номер N на K, где K — значение переменной `NextK`.
* **Сгенерировать:** `BK ← BN`.
* **Выполнить:** `NextK ← NextK + 1`.

Вернуться к шагу 2.

**Шаг 9.** На данном этапе указатели уже должны закончиться. Завершение работы
алгоритма.


Стрелки влево (`→`) в рассмотренном алгоритме являются элементарными командами
отождествления (recognition), они либо могут выполниться успешно (если значение
слева может быть разбито на части, указанные справа), либо завершиться неудачей.

В случае неудачи управление передаётся на предыдущую команду `Loop`. Если ранее
по тексту нет команды `Loop` (т.е. если в образце нет открытых e-переменных),
то считается, что попытка сопоставления оказалась неудачной.

Команда `Loop BN → e.X BN` при первом проходе присваивает переменной `e.X`
пустое значение и не меняет `BN`. При перехвате неудачи сопоставления команда
`Loop` удаляет первый терм из `BN` и приписывает его в конец `e.X` — происходит
удлинение переменной `e.X` за счёт `BN`. Если к тому моменту `BN` оказался
пустым, то операция удлинения оказалась неуспешной — неудача обрабатывается
как описано выше.

Стрелки вправо (`←`) — это присваивания. Они всегда выполняются успешно.


**Пример 16.** Составим последовательность элементарных команд для образца
`(e.L1 s.D e.R1) (e.L2 s.D e.R2)`.

Инициализируем нулевую пару указателей и переменную `NextK`:

`[`<sub>0</sub>`(e.L1 s.D e.R1) (e.L2 s.D e.R2)]`<sub>0</sub>

`NextK ← 1`

**Генерируем:** `B0 ← аргумент функции`.

Шаги 2 и 3 выполнить не можем. Но можем выполнить шаг 4:

`([`<sub>1</sub>`e.L1 s.D e.R1]`<sub>1</sub>`) [`<sub>0</sub>`(e.L2 s.D e.R2)]`<sub>0</sub>

`NextK ← 2`

**Генерируем:** `B0 → (B1) B0`

Опять не можем выполнить шаги 2 и 3 и можем выполнить шаг 4:

`([`<sub>1</sub>`e.L1 s.D e.R1]`<sub>1</sub>`) ([`<sub>2</sub>`e.L2 s.D e.R2]`<sub>2</sub>`)[`<sub>0</sub>`]`<sub>0</sub>

`NextK ← 3`

**Генерируем:** `B0 → (B2) B0`

Шаги 2, 3, 4 и 5 неприменимы. Выполняем шаг 6 — аннигиляцию пары указателей.


`([`<sub>1</sub>`e.L1 s.D e.R1]`<sub>1</sub>`) ([`<sub>2</sub>`e.L2 s.D e.R2]`<sub>2</sub>`)`

**Генерируем:** `B0 → []`

Шаги 2–7 неприменимы. Шаг 8 предписывает передвинуть указатель `[`<sub>1</sub>
и перенумеровать указатели:

`(e.L1 [`<sub>1</sub>`s.D e.R1]`<sub>1</sub>`) ([`<sub>2</sub>`e.L2 s.D e.R2]`<sub>2</sub>`)`

**Генерируем:** `Loop B1 → e.L1 B1`

**Меняем** указатель 1 на 3:

`(e.L1 [`<sub>3</sub>`s.D e.R1]`<sub>3</sub>`) ([`<sub>2</sub>`e.L2 s.D e.R2]`<sub>2</sub>`)`

**Генерируем:** `B3 ← B1`.

`NextK` ← 4.

**Меняем** указатель 2 на 4:

`(e.L1 [`<sub>3</sub>`s.D e.R1]`<sub>3</sub>`) ([`<sub>4</sub>`e.L2 s.D e.R2]`<sub>4</sub>`)`

**Генерируем:** `B4 ← B2`.

`NextK` ← 5.

Примени́м шаг 2, поскольку `s.D` — жёсткий элемент.

`(e.L1 s.D [`<sub>3</sub>`e.R1]`<sub>3</sub>`) ([`<sub>4</sub>`e.L2 s.D e.R2]`<sub>4</sub>`)`

**Генерируем:** `B3 → s.D B3`. Заметим, что переменная `s.D` здесь новая.

Шаги 2–6 неприменимы, шаг 7 (аннигиляция указателей вокруг закрытой
e-переменной) применим. Выполняем:

`(e.L1 s.D e.R1) ([`<sub>4</sub>`e.L2 s.D e.R2]`<sub>4</sub>`)`

**Генерируем:** `e.R1 ← B3`.

Шаги 2–7 недоступны, доступен шаг 8 — цикл удлинения открытой переменной `e.L2`.
Двигаем указатель и перенумеровываем диапазон:

`(e.L1 s.D e.R1) (e.L2 [`<sub>4</sub>`s.D e.R2]`<sub>4</sub>`)`

**Генерируем:** `Loop B4 → e.L2 B4`

**Меняем** указатель 4 на 5:

`(e.L1 s.D e.R1) (e.L2 [`<sub>5</sub>`s.D e.R2]`<sub>5</sub>`)`

**Генерируем:** `B5 ← B4`.

`NextK` ← 6.

Примени́м шаг 2:

`(e.L1 s.D e.R1) (e.L2 s.D [`<sub>5</sub>`e.R2]`<sub>5</sub>`)`

**Генерируем:** `B5 → s.D B5`. Переменная `s.D` здесь повторная, поскольку
ранее по тексту она уже отождествлялась.

Аннигилируем указатели вокруг `e.R2` (шаг 7):

`(e.L1 s.D e.R1) (e.L2 s.D e.R2)`

**Генерируем:** `e.R2 ← B5`.

В образце указателей больше не осталось, генерация кода закончена. Получилось:

     1. B0 ← аргумент функции
     2. B0 → (B1) B0
     3. B0 → (B2) B0
     4. B0 → []
     5. Loop B1 → e.L1 B1
     6. B3 ← B1
     7. B4 ← B2
     8. B3 → s.D B3, s.D — новая
     9. e.R1 ← B3
    10. Loop B4 → e.L2 B4
    11. B5 ← B4
    12. B5 → s.D B5, s.D — повторная
    13. e.R2 ← B5

Выполним сопоставление `('abra') ('cadabra') : (e.L1 s.D e.R1) (e.L2 s.D e.R2)`
пользуясь описанным алгоритмом.

     1. B0 ← аргумент функции
        B0 = ('abra') ('cadabra')

     2. B0 → (B1) B0, успешно
        B0 = ('cadabra')
        B1 = 'abra'

     3. B0 → (B2) B0, успешно
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'

     4. B0 → [], успешно
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'

     5. Loop B1 → e.L1 B1, выполняется первый раз
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []

     6. B3 ← B1
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'abra'

     7. B4 ← B2
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'abra'
        B4 = 'cadabra'

     8. B3 → s.D B3, s.D — новая, успешно
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'cadabra'
        s.D = 'a'

     9. e.R1 ← B3
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'cadabra'
        s.D = 'a'
        e.R1 = 'bra'

    10. Loop B4 → e.L2 B4, выполняется первый раз
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'cadabra'
        s.D = 'a'
        e.R1 = 'bra'
        e.L2 = []

    11. B5 ← B4
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'cadabra'
        s.D = 'a'
        e.R1 = 'bra'
        e.L2 = []
        B5 = 'cadabra'

    12. B5 → s.D B5, s.D — повторная, неуспешно
        Потому что B5 начинается 'c…', а s.D == 'a'.
        Откатываемся к последней команде Loop

    10. Loop B4 → e.L2 B4, возврат при неудаче, успешно.
        e.L2 удлиняется на один терм, B4 укорачивается.
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'adabra'
        s.D = 'a'
        e.R1 = 'bra'
        e.L2 = 'c'
        B5 = 'cadabra'

    11. B5 ← B4
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'adabra'
        s.D = 'a'
        e.R1 = 'bra'
        e.L2 = 'c'
        B5 = 'adabra'

    12. B5 → s.D B5, s.D — повторная, успешно.
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'adabra'
        s.D = 'a'
        e.R1 = 'bra'
        e.L2 = 'c'
        B5 = 'dabra'

    13. e.R2 ← B5
        B0 = []
        B1 = 'abra'
        B2 = 'cadabra'
        e.L1 = []
        B3 = 'bra'
        B4 = 'adabra'
        s.D = 'a'
        e.R1 = 'bra'
        e.L2 = 'c'
        B5 = 'dabra'
        e.R2 = 'dabra'

Алгоритм успешно отработал. Получили подстановку:

        e.L1 = [], s.D = 'a', e.R1 = 'bra', e.L2 = 'c', e.R2 = 'dabra'

Заметим, ту же самую, что и при декларативном описании.

**Пример 17.** Будет ли переменная `e.X` в образце `e.X e.Y (e.X)` открытой?
Построим последовательность команд отождествления.

Шаг 1. Инициализация.

**Генерируем:** `B0 ← аргумент функции`.

`NextK ← 1`

Окружаем указателями `[`<sub>0</sub>, `]`<sub>0</sub> образец:

`[`<sub>0</sub>`e.X e.Y (e.X)]`<sub>0</sub>

Шаги 2–4 неприменимы. Но можем выполнить шаг 5 (отщепление скобочного терма
справа):

`[`<sub>0</sub>`e.X e.Y]`<sub>0</sub>` ([`<sub>1</sub>`e.X]`<sub>1</sub>`)`

**Генерируем:** `B0 → B0 (B1)`

`NextK ← 2`

Шаги 2–5 неприменимы, примени́м шаг 6 (аннигиляция через закрытую переменную):

`[`<sub>0</sub>`e.X e.Y]`<sub>0</sub>` (e.X)`

**Генерируем:** `e.X ← B1`.

Теперь, внимание, срабатывает шаг 2. Потому что переменная `e.X` стала
повторной, имеет фиксированное значение. Т.е. стала жёстким элементом:

`e.X [`<sub>0</sub>`e.Y]`<sub>0</sub>` (e.X)`

**Генерируем:** `B0 → e.X B0, e.X — повторная`

Переменная `e.Y` закрытая (шаг 6):

`e.X e.Y (e.X)`

**Генерируем:** `e.Y ← B0`.

Указателей не осталось, генерация кода завершена. Получилось:

    B0 ← аргумент функции
    B0 → B0 (B1)
    e.X ← B1
    B0 → e.X B0, e.X — повторная
    e.Y ← B0

Переменная `e.X` не открытая. Она сначала закрытая (в скобках), потом —
повторная (в начале).

#### Простое правило поиска открытых переменных

Чтобы увидеть в образце открытые переменные, можно воспользоваться следующим
приёмом. Записываем образец, приписываем в начале и конце знаки `@`,
подчёркиваем их.

Жёсткими элементами будем считать символы, скобки, s- и t-переменные
и повторные e-переменные, одно из вхождений которых уже подчёркнуто.

Затем, пока весь образец не подчёркнут, повторяем:

* Если подчёркнута одна из круглых скобок, подчёркиваем парную скобку.
* Если есть неподчёркнутый жёсткий элемент, соседствующий с подчёркнутым
  текстом, его подчёркиваем.
* Если есть неподчёркнутая e-переменная, окружённая подчёркнутым текстом,
  подчёркиваем её — это закрытая переменная.
* Если есть несколько неподчёркнутых e-переменных, смотрим на самую левую.
  Эта переменная будет открытой, подчёркиваем её. Всё, что будет подчёркнуто
  позже, будет сопоставляться в цикле для каждого удлинения этой открытой
  переменной.

Знаки `@` очевидно нужны, чтобы не выделять в особый случай элементы
в самом начале и в самом конце образца.

**Пример 18.** Найдём открытые переменные в образце
`(e.L1 s.D e.R1) (e.L2 s.D e.R2)`.

    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^                                 ^
    С подчёркнутыми собачками соседствуют скобки:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^                             ^^^
    Подчёркиваем парные скобки:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^             ^^^             ^^^
    Жёстких элементов нет. Есть несколько неподчёркнутых e-переменных.
    Самая левая — e.L1. Она открытая, подчёркиваем её:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^^^^^         ^^^             ^^^
    s.D — жёсткий элемент:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^^^^^^^^^     ^^^             ^^^
    e.R1 — закрытая переменная:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^^^^^^^^^^^^^^^^^             ^^^
    e.L2 — открытая:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^^^^^^^^^^^^^^^^^^^^^         ^^^
    s.D — жёсткий элемент:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^     ^^^
    e.R2 — закрытая переменная:
    @ (e.L1 s.D e.R1) (e.L2 s.D e.R2) @
    ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    Весь образец подчёкнут.

Открытые переменные — `e.L1` и `e.L2`.

**Пример 19.** Найдём открытые переменные в образце `e.X e.Y (e.X)`:

    @ e.X e.Y (e.X) @
    ^               ^
    @ e.X e.Y (e.X) @
    ^             ^^^
    @ e.X e.Y (e.X) @
    ^         ^   ^^^
    @ e.X e.Y (e.X) @
    ^         ^^^^^^^
    e.X — повторная переменная, уже есть подчёркнутое вхождение,
    значит e.X — жёсткий элемент
    @ e.X e.Y (e.X) @
    ^^^^^     ^^^^^^^
    @ e.X e.Y (e.X) @
    ^^^^^^^^^^^^^^^^^

Открытых переменных нет.

#### Почему нужно заворачивать аргументы функции в скобки

Вернёмся к примеру с функцией `IsEqual`. Первоначальный вариант у нас выглядел
так:

    IsEqual {
      e.X '=' e.X = True;
      e.X '=' e.Y = False;
    }

Во-первых, функция плоха тем, что если `e.X` или `e.Y` содержит знак `'='`,
то она будет работать некорректно. Сравним к примеру `'a=b=a'` и `'b'`:

    <IsEqual 'a=b=a=b'>
    True

Но, допустим, мы точно знаем, что её аргументы никогда не содержат знака `'='`.
Запишем императивный код для первого образца:

    1. B0 ← аргумент функции
    2. Loop B0 → e.X B0
    3. B1 ← B0
    4. B1 → '=' B1
    5. B1 → e.X B1, e.X — повторная
    6. B1 → []

Операции 4 и 5 будут выполняться последовательно для каждого возможного удлинения
открытой переменной `e.X`. Представьте себе такой вызов:

    <IsEqual 'aaa…1000 раз…aaa=bcd'>

Переменную `e.X` придётся удлинить 1000 раз, пока сопоставление в строке 4
не выполнится успешно.

Второй образец также содержит открытую e-переменную и для этого вызова снова
будет делать 1000 удлинений `e.X`.

Если разделять аргументы скобками, то избыточных циклов не возникает.

    IsEqual {
      (e.X) (e.X) = True;
      (e.X) (e.Y) = False;
    }

Код для первого предложения:

    1. B0 → (B1) B0
    2. B0 → (B2) B0
    3. B0 → []
    4. e.X ← B1
    5. B2 → e.X B2, e.X — повторная
    6. B2 → []

Код для второго предложения

    1. B0 → (B1) B0
    2. B0 → (B2) B0
    3. B0 → []
    4. e.X ← B1
    5. e.Y ← B2

Открытых переменных нет.

Можно заметить, что в функции `IsEqual` одна пара скобок избыточна — аргумент
будет правильно разделён на подаргументы, если одну из них стереть:

    IsEqual {
      e.X (e.X) = True;
      e.X (e.Y) = False;
    }

или так:

    IsEqual {
      (e.X) e.X = True;
      (e.X) e.Y = False;
    }

В этом случае мы сэкономим одну команду отождествления пары скобок (а эта
команда дешёвая) и несколько нажатий на клавиши. Но вариант с двумя парами
скобок в этом случае выразительнее — сравниваются два _одинаковых_
аргумента, и поэтому мы их одинаково заворачиваем.

#### Стоимость различных элементарных операций

Открытые e-переменные — не единственный источник неэффективности. Элементарные
операции сопоставления имеют различную стоимость.

Быстро выполняются операции сопоставления с символами, s-переменными, круглыми
скобками и _новыми_ t-переменными. Хотелось в этот ряд включить
и «сопоставление» с закрытой e-переменной, но она, как мы выяснили, является
не сопоставлением, а присваиванием. И она тоже выполняется эффективно.

Медленно выполняются операции сопоставления с повторными e- и t-переменными.
Ведь для их сопоставления необходимо проверить равенство их значений, а сами
значения могут быть достаточно «тяжёлыми». Допустим, у нас есть функция

    IsEqual {
      (e.X) (e.X) = True;
      (e.X) (e.Y) = False;
    }

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

    1. B0 → (B1) B0
    2. B0 → (B2) B0
    3. B0 → []
    4. e.X ← B1
    5. B2 → e.X B2, e.X — повторная
    6. B2 → []

Циклов по открытым переменным нет, в строке 5 имеем элементарную команду
отождествления повторной e-переменной.

Пусть функция `IsEqual` вызывается как

    <IsEqual ('aaa…1000 раз…aaa') ('aaa…999 раз…aab')>

Команда в строке 5 будет сканировать диапазон `B2` слева направо. И прежде
чем она увидит отличие в 1000-м символе, она убедится в равенстве предыдущих
999 букв `'a'`.

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


## Ссылки
1. А. П. Немытых, Суперкомпилятор SCP4: общая структура, ISBN 978-5-382-00365-8,
   Издательство УРСС, Москва, 2007.
2. А. П. Немытых, В. Ф. Турчин, Суперкомпилятор SCP4: исходные тексты,
   on-line демонстрация, ([online]: <http://www.botik.ru/pub/local/scp/refal5/>),
   2000.
3. А. П. Немытых, В. Ф. Турчин, Суперкомпилятор SCP4: on-line демонстрация,
   ([online]: <http://refal.botik.ru/scp_demo/>), 2000.
4. А. П. Немытых, Лекции по языку программирования Рефал.
   Сборник трудов по функциональному языку программирования Рефал, том I
   // Под редакцией А. П. Немытых. — Переславль-Залесский: Издательство
   «СБОРНИК», 2014, 194 с. — ISBN 978-5-9905410-1-6 — стр. 120.
   Доступно в Интернете: <http://refal.botik.ru/library/refal2014_issue-I.pdf>
5. Родословная Пушкина. Предки великого поэта :: SYL.ru,
   режим доступа:
   <https://www.syl.ru/article/183012/new_rodoslovnaya-pushkina-predki-velikogo-poeta>
   (дата обращения: 07.01.2018).
6. Пушкин, Александр Сергеевич // Википедия. [2003—2018]. Дата обновления: 05.01.2018.
   URL: <http://ru.wikipedia.org/?oldid=90075965> (дата обращения: 07.01.2018).
8. А. Ю. Алешин, А. Г. Красовский, С. А. Романенко, В. Ю. Шерстнев, Система
   программирования РЕФАЛ-2 для IBM PC, PDP-11 и VAX-11. Руководство пользователя,
   Москва, 1991, URL: <http://refal.net/~belous/download/refal2/refal2-doc.zip>,
   (дата обращения: 08.01.2018)
9. V. F. Turchin, REFAL-5 programming guide and reference manual, New England
   Publishing Co., Holyoke, 1989
   В интернете доступен перевод на русский язык (описывается устаревший
   синтаксис): <http://refal.ru/rf5_frm.htm>, также доступно переработанное
   и расширенное издание 1999 года: <http://refal.botik.ru/book/html>.
