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

  Соглашение о терминологии.
  Под лямбда-функцией здесь и далее будем подразумевать функциональный блок,
объявленнный в результатном выражении. Понятие функции является статическим,
т.е. существует только во время написания кода и компиляции программы. Под гло-
бальной функцией будет подразумеваться обычная функция Простого Рефала в том ви-
де, в каком она присутствовала в предыдущих версиях языка.
  Под замыканием будет подразумеваться экземпляр функции (как лямбда-функции,
так и  глобальной), существующий во время выполнения программы и присутствующий
в поле зрения абстрактной рефал-машины. Замыкание может быть выполнено (активи-
ровано), если оно находится после открывающей угловой скобки. Замыкание является
обобщением понятия "указатель на функцию" предыдущих версий Простого Рефала.
  Отношение между функцией (глобальной или локальной) и замыканием такое же, как
и отношение между классом и объектом в ООП.
  Поскольку (в данной версии) не существует образца, который мог бы разбить за-
мыкание на более мелкие элементы (мельче чем имя функции в случае экземпляра
глобальной функции), замыкание является атомом и может быть сопоставлено с s-пе-
ременной.
  Изначально для лямбда-функций я собирался использовать термин "локальная функ-
ция", т.к. такой же термин использовал Скоробогатов в статье "Язык Refal с функ-
циями высшего порядка", однако существует уже сложившаяся (во внутренней доку-
ментации к Простому и Модульному Рефалам) терминология, согласно которой гло-
бальные функции делятся на entry-функции (доступные извне модуля) и локальные
функции (недоступные извне модуля). Чтобы не возникало терминологической путани-
цы, я решил использовать термин "лямбда-функция".

  Одним из способов реализации замыканий, который будет реализован в данной ла-
бе, представление замыкания в виде пары (указатель функцию, контекст), где ука-
затель на функцию -- это указатель на некоторую глобальную функцию с уникальным
именем, которая в качестве аргумента принимает аргумент-замыкания+контекст, кон-
текст -- это список свободных переменных лямбда-функции в терминологии лямбда-
исчисления. Т.е. пусть у нас следующая функция порождает замыкание:
  CreateClosure {
    s.1 e.2 = { e.3 = e.2 s.1 e.3; };
  }
Замыкание, порождённое вызовом <CreateClosure 'Hello'> будет представляться па-
рой (CreateClosure#1, 'H' 'ello'), где функция CreateClusure#1 является автома-
тически сгенерированной и имеет вид:
  CreateClosure#1 {
    s.1 (e.2) e.3 = e.2 s.1 e.3;
  }
  Вызов замыкания (s.Function e.Context) с некоторым аргументом e.Arg сводится
к вызову s.Function с аргументом e.Context e.Arg, для приведённого примера:
  <<CreateClosure 'Hello'> ' World'>
эквивалентен
  <CreateClosure#1 'H' ('ello') ' World'>
результатом которого будет 'elloH World'.
  Поскольку в случае функций высших порядков функции являются полноправными объ-
ектами данных, замыканиям необходимо обеспечить возможность копирования. Копиро-
вать весь контекст при копировании объектного выражения (если в результатное вы-
ражение входит больше переменных с заданным именем, чем в образцовое) нежелате-
льно, т.к. это не только снижение эффективности программы, но и неожиданность
для программиста: копирование атомов должно выполняться за постоянное время в
списковой реализации.
  Поскольку циклических связей при данном способе задания лямбда-функций быть не
может (контекст данного замыкания создаётся до создания самого замыкания и затем
он не может быть изменён -- прямые циклические ссылки исключены; если контекст
содержит другие замыкания, то они должны быть созданы до создания текущего замы-
кания и далее по индукции -- косвенные циклические ссылки запрещены), можно при-
менить схему подсчёта ссылок. При копировании объектного выражения счётчик ссы-
лок на контекст увеличивается на 1, при удалении в список свободных блоков счёт-
чики ссылок никак не меняются. Счётчик ссылок уменьшается на 1 только в тот мо-
мент, когда узел, содержащий замыкание, повторно используется для создания ново-
го узла. При уменьшении счётчика ссылок до нуля содержимое контекста сбрасывает-
ся в список свободных блоков.
  При активации замыкания, содержащего контекст, контекст копируется в поле зре-
ния и выполняется вызов указателя на функцию. Однако, если контекст используется
только этим экземпляром замыкания, то контекст можно не копировать, а переносить
в поле зрения.

  Предполагается следующий способ реализации. Поскольку в Простом Рефале синтак-
сический анализ делается достаточно нерегулярно (сначала автомат выделяет декла-
рации верхнего уровня, а также образецы и результаты каждого предложения без
учёта парности скобок и правильности объявления переменных; затем выполняется
проверка парности скобок отдельно для каждого действия предложения, затем прове-
ряется правильность использования переменных; только после этого генерится резу-
льтатный код на Си++), то у нас есть два пути:
  1. Реализовать регулярный синтаксический анализатор (по аналогии с Модульным
Рефалом), т.е. написать синтаксический анализатор методом рекурсивного спуска с
параллельным анализом правильности использований переменных (что принципиально
важно для работы с контекстом). Часть подобного регулярного анализатора написа-
на: это автомат, обрабатывающий декларации и черновую обработку функций. Необ-
ходимо будет лишь переписать обработку предложений и изменить порядок генерации
конечного кода на Си++.
  2. Нерегулярно добавить поддержку лямбда-функций. Один из способов -- добавить
ещё один проход по лексической свёртке с проверкой сбаллансированности фигурных
скобок, при этом содержимое фигурных скобок сворачивается в псевдолексему. В
этом случае автомат по разбору конструкций верхнего уровня и чернового анализа
тела функции практически не изменится. В таком случае работу можно разбить на
два этапа, первый простой, второй сложнее:
  2.1. При обнаружении в результатном выражении лямбда-лексемы создавать уника-
льное имя для глобальной функции; на место лямбда-лексемы помещать операцию свя-
зывания глобальной функции с этим уникальным именем с контекстом (который на
этом этапе будет содержать ВСЕ переменные из образцового предложения); уникаль-
ное имя, содержимое лямбда-лексемы (содержимое фигурных скобок) и связываемый
контекст сохранить (в виде передачи очередного терма из функции в функцию); за-
тем по завершении генерации конкретной функции приступить к обработке лямбда-
функции, рассматривая её как обычную функцию, все образцы которой начинаются с
аргументов, соответствующих контексту.
  2.2. В основе идея примерно такая же, только в контекст должны посылаться ре-
ально используемые в лямбда-функции переменные.
  Преимущество разбиения процесса на два этапа в том, что на втором этапе уже
будет готова (хоть и кривая) поддержка функций высших порядков, что резко повы-
сит выразительность Простого Рефала и реализовывать второй этап будет проще. Как
реализовывать второй этап -- я пока до конца не продумал, но подозреваю, что при
любой реализации второго этапа мы не сможем сразу же отправлять генератору от-
дельные предложения, а потребуется хранить в памяти функции целиком (на первом
этапе сохранённые лямбда-функции представляют собой ещё не разобранный поток ле-
ксем внутри фигурных скобок). Возможна реализация второго этапа как написание
регулярного анализатора (см. п. 1).

  Результаты.

  [1] Изменения, внесённые в компилятор

  Простой Рефал пополнен лямбда-функциями в соответствии целью лабы. Кроме того,
была исправлена ошибка, связанная с проблемами компиляции компилятором g++ в ре-
жиме интерпретации. Ошибка заключалась в том, что указатели на функцию и указа-
тели на строковые литералы не могут автоматически приводиться в (void*) (первые
не могут в принципе, вторые могут приводиться только к (const void*)). Было до-
бавлено явное приведение типов в стиле Си. Кроме того, массив команд стал стати-
ческим константным, вместо указателей alloc_ptr1/alloc_ptr2 введён массив allocs
[2*sizeof(raa)/sizeof(raa[0])). Размер массива выделяется с запасом (т.к. на
каждую команду требуется не больше двух распределений, а на некоторые не требу-
ются распределения вообще). Т.к. массив автоматический и не инициализируемый,
дополнительных затрат быстродействия на запас не требуется, затраты памяти нич-
тожны по сравнению с затратами памяти на поле зрения. Это позволило сравнить
размер исполнимого файла, сгенерированного в обоих режимах с помощью компилято-
ра g++. Компиляция выполнялась с параметрами оптимизации по умолчанию (не испо-
льзовались дополнительные ключи командной строки). Размер файла, сгенерированно-
го в обоих режимах, превосходит размер исполнимого файла, сгенерированного при
помощи BCC 5.5 в том же режиме.

  [2] Идеи по использованию лямбда-функций

  Можно предположить, что добавление лямбда-функций в диалект Рефала, управляю-
щие конструкции которого во многом совпадают с подмножеством Базисного Рефала
(текущая версия Модульного Рефала -- 0.1.959, Простой Рефал предыдущих версий),
приведёт к резкому повышению выразительности языка и развитию новых идиом.
  Одна из основных проблем подмножества Базисного Рефала в том, что приходится
писать целую уйму промежуточных функций (вторая проблема -- отсутствие откатов).
Промежуточные функции используются для того, чтобы проанализировать результат
вызова функции и в зависимости от этого выполнить те или иные действия (такие
функции я пишу с префиксом Sw); чтобы преобразовать результат вызова одной фун-
кции в одном формате в другой формат с целью возврата или передачи в другую
функцию (такие функции я пишу с суффиксом -Aux); выполнения остаточно-рекурсив-
ного цикла (такие функции я пишу с префиксом Do). Если функция имеет и тот или
иной смысловой префикс, и суффикс -Aux, то приоритет определяется как правило
по смыслу.
  Кроме того, использование библиотечных функций высших порядков, применяемых
для сокрытия цикла (Map, Reduce, MapReduce) требует указания функции-преобразо-
вателя, которую приходится объявлять глобальной.
  Во всех перечисленных случаях могут помочь лямбда-функции.
  1. Ветвление в зависимости от результата функции.

вместо

  Func {
    аргумент = <SwFunc (какой-то контекст) <OtherFunc какой-то аргумент>>;
  }

  SwFunc {
    (контекст) результат-1 = действие-1;
    (контекст) результат-2 = действие-2;
    ....
  }

пишем

  Func {
    аргумент =
      <
        {
          результат-1 = действие-1;
          результат-2 = действие-2;
          ....
        }
        <OtherFunc какой-то аргумент>
      >;
  }

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

  Во многих диалектах Рефала для этой цели существует такая конструкция как дей-
ствие-блок (with-конструкция Рефала 5, образцовый блок в Рефале 6 и Рефале Плюс
(относительно последнего не уверен в терминологии), операция "стрелка" (fetch)
в Рефале 7). Синтаксис подобной конструкции в Рефале 7 выглядела бы как

  Func {
    аргумент =
      <OtherFunc какой-то аргумент> => {
        результат-1 = действие-1;
        результат-2 = действие-2;
        ....
      };
  }

  В Рефале 5, 6 и Плюс вместо стрелки следует использовать двоеточие (в Рефале
6 можно использовать и квадроточие).
  Подобный синтаксис можно имитировать следующим образом -- вводим функцию
Fetch, определённую (в некотором модуле библиотеки) так:

  Fetch {
    e.Argument s.Function = <s.Function e.Argument>;
  }

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

  Func {
    аргумент =
      <Fetch
        <OtherFunc какой-то аргумент>
        {
          результат-1 = действие-1;
          результат-2 = действие-2;
        }
      >;
  }

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

вместо

  Func {
    аргумент =
      <Func-Aux
        (какой-то контекст) <OtherFunc какой-то аргумент>;
      >;
  }

  Func-Aux {
    (контекст) данные в формате 1 =
      <OtherFunc2 части контекста и данные в формате 2>;
  }

пишем

  Func {
    аргумент =
      <
        {
          данные в формате 1 =
            <OtherFunc2 части контекста и данные в формате 2>;
        }
        <OtherFunc какой-то аргумент>
      >;
  }

  В развитых диалектах Рефала (те же Рефал 5, 6, 7, Плюс) для этой цели также
существует специальный синтаксис (использование where-конструкции в Рефале 5 для
перестройки (основное её предназначение -- проверка условий), собственно пере-
стройка в Рефале Плюс, квадроточие или двоеточие в Рефалах 6 и 7 (в Рефале 7
следует осторожнее обращаться с квадроточием -- оно запрещает неуспехи во всём
окончании предложения, следующем после него, в отличие от Рефала 6, где оно за-
прещает неуспех только в следующем за ним образцовом действии, но является про-
зрачным для оставшейся части предложения)). Пример на Рефале Плюс:
  Func
    аргумент,
      <OtherFunc какой-то аргумент> :: формат 1 =
      <OtherFunc2 части контекста и данные в формате 2>;

  Здесь намеренно написано "формат 1", а не "данные в формате 1", т.к. после
квадроточия может находиться только т.н. "жёсткое выражение", т.е. выражение без
литералов, повторных переменных и открытых e-переменных. Т.е. фактически формат.
  Подобный синтаксис можно эмулировать с помощью той же функции Fetch:

  Func {
    аргумент =
      <Fetch
        <OtherFunc какой-то аргумент> {
          данные в формате 1 =
            <OtherFunc2 части контекста и данные в формате 2>
        }
      >;
  }

  3. Выполнение остаточно-рекурсивных циклов.
  Здесь будет рассмотрен как абстрактный, так и реальный пример. Рассмотрем аб-
страктный пример

  Func {
    аргумент = <DoFunc (контекст) начальный инвариант цикла>;
  }

  DoFunc {
    (контекст) разновидность инварианта 1 =
      <DoFunc (контекст) изменение инварианта 1>;

    (контекст) разновидность инварианта 2 =
      возвращаемый результат 2;

    ....
  }

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

  Factorial {
    0 = 1;
    s.N = <DoFact s.N 1 1>; // контекст, аккумулятор, счётчик цикла
  }

  DoFact {
    s.N s.Prod s.N = <Mul s.Prod s.N>;
    s.N s.Prod s.K =
      <DoFact s.N <Mul s.Prod s.K> <Inc s.K>>;
  }

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

  Тут возникает интересная проблема: для рекурсивного вызова нам требуется осу-
ществить вызов функции с тем же именем, что и имя функции, в рамках которой
осуществляется вызов (т.е. внутри функции с именем DoFact нужно вызвать функцию
DoFact). До сих пор мы рассматривали случаи, в которых безымянные лямбда-функции
подставлялись вместо имени глобальной промежуточной (Sw... или ...-Aux) функции
и всё оказывалось довольно гладко. А теперь нам надо умудриться совершить рекур-
сивный вызов безымянной лямбда-функции.
  Прежде чем приходить к разгадке, рассмотрим те же примеры на Рефале 7, в кото-
рых нет подобных проблем, т.к. лямбда-функции могут быть именованными. Другие
диалекты Рефала (5, 6, Плюс) здесь не рассматриваются, т.к. в них нет лямбда-
функций, и уж тем более именованных, и в них остаточно рекурсивные циклы прихо-
дится реализовывать так, как показано выше.

  Абстрактный пример

  Func {
    аргумент =
      начальный инвариант цикла =>
      $func Loop {
        разновидность инварианта 1 = <Loop изменение инварианта 1>;
        разновидность инварианта 2 = возвращаемый результат 2;
        ....
      };
  }

  Конкретный пример

  Factorial {
    0 = 1;

    s.N = 1 1 =>
      $func Loop {
        s.Prod s.N = <Mul s.Prod s.N>;
        s.Prod s.K = <Loop <Mul s.Prod s.K> <Inc s.K>>;
      };
  }

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

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

  // функция библиотеки
  Loop {
    s.Function e.Argument =
      <s.Function s.Function e.Argument>;
  }

  Func {
    аргумент =
      <Loop
        {
          s.Me разновидность инварианта 1 = <Loop s.Me измерение инварианта 1>;
          s.Me разновидность инварианта 2 = возвращаемый результат 2;
          ....
        }
        начальный инвариант цикла
      >;
  }

  Тут вспомогательная лямбда-функция первым аргументом терма всегда должна при-
нимать атом s.Me, рекурсивный вызов осуществлять вызовом функции библиотеки
Loop с первым аргументом s.Me. В параметр s.Me помещается само замыкание, соот-
ветствующее лямбда-функции. Можно написать комбинированную функцию Fetch-L,
сочетающую в себе действие Fetch и Loop, а именно, указание сначала аргумента,
а затем функции и запуск цикла соответственно.

  Fetch-L {
    e.Argument s.Function = <Loop s.Function e.Argument>;
  }

  Пример с факториалом будет выглядеть так:

  Fact {
    0 = 1;

    s.N =
      <Fetch-L
        1 1
        {
          s.Me s.Prod s.N = <Mul s.Prod s.N>;
          s.Me s.Prod s.K = <Loop s.Me <Mul s.Prod s.K> <Inc s.K>>;
        }
      >;
  }

  Недостатки этого решения состоят в том, что (а) нельзя забывать об аргументе
s.Me, (б) нельзя забывать вызывать функцию Loop с аргументом s.Me.
  Недостаток (а) в принципе несущественнен, но его можно устранить следующим
тяжеловесным способом: введением дополнительного уровня косвенности. Например,
так:

  Fact {
    0 = 1;

    s.N =
      <Fetch-L
        1 1
        {
          s.Me =
            <{
              s.Prod s.N = <Mul s.Prod s.N>;
              s.Prod s.K = <Loop s.Me <Mul s.Prod s.K> <Inc s.K>>;
            }>;
        }
      >;
  }

или даже так
  Loop-i { // improved
    s.Function e.Argument = <<s.Func s.Func> e.Argument>;
  }

  Fetch-Li {
    e.Argument s.Function = <<Loop-i s.Function> e.Argument>;
  }

  Fact {
    0 = 1;

    s.N =
      <Fetch-Li
        1 1 {
          s.Me = {
            s.Prod s.N = <Mul s.Prod s.N>;
            s.Prod s.K = <Loop-i s.Me <Mul s.Prod s.K> <Inc s.K>>;
          };
        }
      >;
  }

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

  Y {
    s.Func = { e.Arg = <s.Func <Y s.Func> e.Arg; };
  }

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

  Fact {
    0 = 1;

    s.N =
      <Y {
        s.Loop s.Prod s.N = <Mul s.Prod s.N>;
        s.Loop s.Prod s.K = <s.Loop <Mul s.Prod s.K> <Inc s.K>>;
      }
        1 1
      >;
  }

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

  Y-i {
    s.Func = { e.Arg = <<s.Func <Y-i s.Func>> e.Arg>; };
  }

  Fetch-Y {
    e.Argument s.Function = <<Y-i s.Function> e.Argument>;
  }

  Fact {
    0 = 1;

    s.N =
      <Fetch-Y
        1 1 {
          s.Loop = {
            s.Prod s.N = <Mul s.Prod s.N>;
            s.Prod s.K = <s.Loop <s.Prod s.K> <Inc s.K>>;
          };
        }
      >;
  }

  Сравним последний пример с примером кода на Рефале 7:

  Factorial {
    0 = 1;

    s.N = 1 1 =>
      $func Loop {
        s.Prod s.N = <Mul s.Prod s.N>;
        s.Prod s.K = <Loop <Mul s.Prod s.K> <Inc s.K>>;
      };
  }

  Конструкцию с Fetch-Y можно считать запуском цикла, предложение s.Loop = {...}
-- записью именованной функции $func Loop {...}, а устойчивую комбинацию записи
всего этого безобразия как идиоматический способ записи именованной лямбда-функ-
ции, точно также, как цикл for(i = 0; i < N; ++i) совершенно естественно воспри-
нимают как цикл со счётчиком for i = 0 to N-1 do, хотя формально цикл for языка
Си им не является.

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

  4. Использование библиотечных функций высших порядков.
  Тут всё просто -- в вызове подобной функции вместо имени глобальной функции
записываем непосредственно тело функции-преобразователя. Если последний является
рекурсивным, то используем идиоматическую конструкцию <Y-i {s.Loop = {тело};}>.

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

  Circle {
    s.Radius s.X s.Y =
      {
        Move = {
          s.OffX, s.OffY =
            <Circle s.Radius <Add s.X s.OffX> <Add s.Y s.OffY>>;
        };

        Area = <Mul <Pi> s.Radius s.Radius>;
        Center = s.X s.Y;
        Size = <Mul 2 s.Radius> <Mul 2 s.Radius>;
      };
  }

  Rectangle {
    s.Width s.Height s.Left s.Top =
       {
         Move = {
           s.OffX s.OffY =
             <Rectangle
               s.Width s.Height <Add s.Left s.OffX> <Add s.Top s.OffY>
             >;
         };

         Area = <Mul s.Width s.Height>;
         Center =
           <Map
             { s.X = <Div s.X 2>; } <Add s.Width s.Left> <Add s.Height s.Top>
           >;
         Size = s.Width s.Height;
       };
  }

  Вызов модификатора фигуры выглядит так <<s.Shape Move> 320 240>, вызов селек-
тора -- как <s.Shape Area>. Преимуществом подобной реализации абстрактных типов
данных является тот факт, что они как замыкания эффективно копируются, в отличие
от штатных средств использования абстрактных типов данных (квадратные скобки).
Недостаток в том, что при встраивании статической типизации для штатных АТД
контролировать корректность типов проще, чем для подобных замыканий.

  [3] Реализация рантайма

  1. Вызов замыканий в виртуальной машине
  Как уже было сказано в цели лабы, замыкание представляет собой пару (глобаль-
ная функция, связанный контекст). Поскольку контекст представляет собой просто
перечисление свободных переменных функционального блока (при этом e-переменные
заключены в скобки) и он располагается слева от аргумента замыкания, то замыка-
ние можно просто хранить как объектное выражение s.Function e.Context. При обна-
ружении виртуальной машиной замыкания после открывающей скобки вызова функции,
виртуальная машина может извлечь это выражение s.Function e.Context и подставить
его на место узла замыкания. В данной реализации это именно так и сделано, при
этом на раскрытие замыкания требуется один шаг рефал-машины. Таким образом, вы-
зов замыкания выполняется за два шага.

  2. Представление замыканий в списковой реализации
  Для представления замыканий в представление добавлены 3 новых типа узла: узел-
замыкание, узел головы замыкания и узел развёрнутого замыкания (о назначении
последнего будет рассказано ниже в подразделе "Свёртывание и развёртывание замы-
каний"). Непосредственно в поле зрения присутствует узел замыкания, в поле link\
_info которого располагается указатель на узел-голову замыкания. Собственно, са-
мо замыкание: объектное выражение, состоящее из указателя на глобальную функцию
и контекста, привязано к узлу головы, поля которого next и prev указывают соот-
ветственно на начало и конец данного выражения, образуя таким образом цикличес-
кий двусвязанный список. Поле информации узла головы замыкания содержит счётчик
ссылок на данное замыкание.
  При копировании объектного выражения копируется только узел замыкания, в поле
link_info помещается адрес имеющейся головы, при этом увеличивается счётчик ссы-
лок внутри последней. Таким образом копирование атома замыкания выполняется за
постоянное время.
  Счётчик ссылок уменьшается в двух случаях: когда объектное выражение, содержа-
щее замыкание и помещённое в список свободных блоков, используется повторно и
узел замыкания следует возвратить для переиспользования или когда данное замыка-
ние выполняется. При обнулении счётчика ссылок содержимое замыкания (указатель
на функцию и контекст) помещается в список свободных блоков. При вызове замыка-
ния при значении счётчика, большим единицы, содержимое замыкания копируется в
поле зрения, при значении, равном единице, содержимое замыкания перемещается в
поле зрения.
  Таким образом, даже если замыкание встречается в поле зрения единожды, счётчик
ссылок этого замыкания может быть больше единицы, т.к. могут существовать неуни-
чтоженные экземпляры в списке свободных блоков.
  Сравнение двух замыканий как одноимённых s-переменных выполняется по полю
link_info, что обеспечивает ожидаемую семантику для сопоставления s.X s.X: s.Y
s.Y, которое всегда завершается успешно. Абстрагируясь от реализации, семантику
сравнения замыканий можно сформулировать как-то так: "все копии данного замыка-
ния (полученные как превышением числа вхождений переменной в результатное выра-
жения числа вхождений в образцовое выражения, так и копированием при передаче
через контекст лямбда-функции) считаются идентичными с точки зрения сравнения
при помощи одноимённых переменных". При этом обратное неверно (см. ниже).
  В данной реализации существует оптимизация: если лямбда-функция не задейству-
ет контекст окружения (т.е. не имеет свободных переменных), то вместо порожде-
ния замыкания происходит на место замыкания помещается указатель на глобальную
функцию с уникальным именем, что позволяет экономить шаги рефал-машины как на
создание (см. ниже), так и на выполнение (см. выше) замыкания. Поэтому два замы-
кания, порождённые в разные моменты времени, могут считаться идентичными с точ-
ки зрения сопоставления одноимённых переменных.
  В Рефале 7 безымянные лямбда-функции априори считаются неравными, поэтому
конструкция вида
  ... , s.X s.X : s.Y s.Y, ...
может порождать неуспех (если я правильно понял Скоробогатова).

  3. Свёртывание и развёртывание замыканий
  Хранение содержимого замыканий в самостоятельных циклических двусвязанных спи-
сках отдельно от основных двусвязанных списков (поле зрения и список свободных
блоков) обеспечивает возможность эффективного копирования и сравнения на иден-
тичность, но в то же время обладает и одним недостатком -- невозможностью без
рекурсивных вызовов последовательно проглядеть всё поле зрения (или весь список
свободных блоков. Классическая реализация абстрактной рефал-машины на списках
является итеративной и не использует рекурсивных вызовов (рекурсивные вызовы
функций обеспечивает структура поля зрения), что является преимуществом -- иск-
лючаются ошибки переполнения стека (но в то же время возможны ошибки переполне-
ния памяти).
  Однако, последовательный просмотр необходим, прежде всего это вывод дампа па-
мяти, а также вывод выражений средствами библиотеки (WriteLile/FWriteLine библи-
отеки Library). Кроме того, последовательный просмотр упрощает освобождение па-
мяти при завершении программы.
  Проблему решает введение средств свёртывания/развёртывания замыканий. Развёр-
тывание заключается во включении содержимого замыкания в основной список, свёр-
тывание -- в востановлении свёрнутого замыкания из развёрнутого. В данной реа-
лизации операции свёртывания/развёртывания ориентированы на просмотр поля зре-
ния слева направо (в направлении ссылки next).
  При развёртывании головной узел и следующий за ним список содержимого замыка-
ния разрывается и помещается перед узлом замыкания. При этом замыкание меняет
свой тип с обычного на развёрнутое (из cDataClosure в cDataUnwrappedClosure),
сохраняя ссылку на голову в link_info. Функция развёртывания (unwrap_closure)
принимает итератор (указатель на узел) замыкания и возвращает итератор головы.
  При свёртывании выполняются обратные действия: восстанавливается кольцевой
список и возвращается тип замыкания узлу развёрнутого замыкания. Аналогично фун-
кция свёртывания (wrap_closure) принимает итератор развёрнутого замыкание и
возвращает итератор следующего за замыканием узла.
  Применяются эти функции следующим образом. В тот момент, когда при последова-
тельном просмотре слева направо мы встречаем замыкание, мы его разворачиваем и
продолжаем просмотр начиная с головы. В результате мы просмотрим сначала голову,
затем содержимое замыкания и наткнёмся на узел развёрнутого замыкания, которое
и свернём. В данной реализации дампа памяти и вывода выражений средствами биб-
лиотеки при обнаружении замыкания выводится '{' и замыкание разворачивается,
голова отображается как [X], где X -- значение счётчика ссылок, при обнаружении
развёрнутого замыкания выводится '}' и замыкание сворачивается.
  Кроме того, в данной реализации Простого и Модульного Рефала объём памяти,
потребляемый программой, может только расти, что нежелательно. В дальнейшем
предполагается распределять память из пула и периодически с целью освободить
ненужную память копировать поле зрения, распределяя его из нового пула, а ста-
рый после копирования освобождать. Возможность линеаризации подобных разделяемых
конструкций, (подобным путём может разделяться не только содержимое замыканий,
но и содержимое структурных (и АТД-) скобок) позволит при помощи линейного прос-
мотра скопировать поле зрения. Подобные очистки могут выполняться по счётчику
(при выполнении N шагов машины) или по объёмам поля зрения и списка свободных
блоков (для этого нужно уметь отслеживать размеры выражений).

  4. Порождение замыканий
  При генерации результатного выражения лямбда-функции заменяются на операции
порождения замыканий, создающие из указателя на глобальную функцию и контекста
замыкание. Имя глобальным функциям, реализующим замыкание создаётся по следую-
щему правилу:
  (1) Закрывающие фигурные скобки блоков внутри функции получают последователь-
ные номера начиная с нуля.
  (2) Имя глобальной функции, соответствующее данному блоку, создаётся в виде
lambda_FuncName_N, где FuncName -- имя функции, в которой находится замыкание,
N -- номер закрывающей скобки блока.
  Поскольку по правилам синтаксиса все имена (функций и идентификаторов) должны
начинаться с заглавной буквы, функции, начинающиеся на lambda_ гарантированно
не совпадут с именами функций, определённых пользователем. Функции объявляются
с модификатором static, поэтому они не вызовут коллизий с именами функций в дру-
гих модулях.
  Поскольку объекты, из которых строится замыкание, являются обычными объектны-
ми выражениями (указатель на глобальную функцию и фактический контекст), было
решено не создавать дополнительной операции по порождению замыканий, а восполь-
зоваться для этой цели вызовом "встроенной" функции, создающей из содержимого
замыкания собственно замыкание. Данная функция входит в рантайм и имеет имя
refalrts::create_closure и обладает сигнатурой (совокупность аргументов и воз-
вращаемого значения) такой же, как и у любых других рефал-функций. Функция при-
нимает содержимое замыкания и возвращает построенное замыкание. Т.к. имеет осо-
бое имя (с маленькой буквы, да и ещё в пространстве имён), то она недоступна из
пользовательского кода на Рефале.
  Таким образом, если функция порождает замыкания, то на каждое замыкание потре-
буется по одному дополнительному шагу рефал-машины.
  Как уже было сказано выше, в компилятор включена оптимизация, позволяющая
вместо замыканий без контекста возвращать непосредственно указатель на глобаль-
ную функцию, соответствующую блоку. На такой возврат не требуется дополнительно-
го шага рефал-машины.

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