Добавить в Простой Рефал условия РЕФАЛа-5

[Mazdaywik]

Введение

На текущий момент синтаксис и частично семантика Простого Рефала представляет собой подмножество Базисного РЕФАЛа диалекта РЕФАЛ-5, пополненное, однако, функциями высших порядков (косвенный вызов функции, указатели на глобальные функции, вложенные безымянные функции).

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

РЕФАЛ-5 поддерживает два синтаксических расширения Базисного Рефала: условия и блоки. Блоки — те же безымянные функции, которые, однако, можно только вызвать одновременно с созданием. Предложение с блоком РЕФАЛа-5 эквивалентно предложению Простого Рефала, результатная часть которого состоит из вызова функции Fetch со вложенной функцией. Поэтому синтаксис блоков в Простом Рефале избыточен.

Условия, синтаксис и семантика

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

Функция {
  …
  Образец, Результат1 : Образец1, Результат2 : Образец2, … РезультатN : ОбразецN = Результат;
  …
}

Здесь на каждый из образцов (кроме ОбразецN) наложено условие.

• Образец имеет условие , Результат1 : Образец1, Результат2 : Образец2, … РезультатN : ОбразецN.
• Образец1 имеет условие , Результат2 : Образец2, … РезультатN : ОбразецN.
• …
• ОбразецN−1 имеет условие , … РезультатN : ОбразецN.

Условие выполняется, когда значение, сформированное результатом (после знака , и перед знаком :), успешно сопоставилось с последующим образцом (после знака : и перед знаком , или =). В противном случае не выполняется.

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

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

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

В рамках настоящей задачи предлагается пополнить Простой Рефал следующим синтаксисом (используется нотация Вирта):

Sentence = Pattern { Condition | Assignment } "=" Result.
Condition = "," Result ":" Pattern.
Assignment = "=" Result ":" Pattern.

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

Присваивания

Мотивация

Практика программирования на РЕФАЛе-5 показывает, что условия часто удобно использовать в роли присваиваний: в предложение добавляется условие, которое всегда выполняется, результатная часть которого вычисляет некоторое новое значение, а образцовая связывает его с одной или несколькими переменными. После чего эти переменные можно использовать в результатной части самого предложения.

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

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

Недостаток обоих подходов — громоздкость. Но есть и недостаток у условия в РЕФАЛе-5. Дело в том, что в силу их семантики, при возможной неудаче сопоставления, аргумент функции должен быть передан на анализ в левую часть следующего предложения. Таким образом, при вычислении результатных выражений в условии, переменные, передаваемые в них, копируются (а это может быть дорого на списковой реализации). Но часто так бывает, что некоторое крупное значение передаётся в условие-присваивание для преобразования и исходное значение в правой части предложения не используется. Компилятор не способен догадаться, что условие выполняется всегда и вместо копирования это значение можно перемещать за постоянное время.

Синтаксис и семантика

Поэтому в предлагаемом синтаксисе наряду с классическими условиями предлагается конструкция «присваивание» имеющая вид = Результат : Образец. Её отличие от условия в том, что требуется, чтобы Образец (возможно, с наложенными на него условиями) всегда сопоставлялся успешно (то есть, при неуспешном сопоставлении будет происходить аварийный останов программы).

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

Фактически, присваивания являются синтаксическим сахаром. Запись

  Образец = Результат1 : Образец1 = Результат

эквивалентна записи

  Образец =
    <
      {
        Образец1 = Результат;
      }
      Результат1
    >;

или, если использовать библиотечную функцию Fetch:

  Образец =
    <Fetch
      Результат1
      {
        Образец1 = Результат;
      }
    >;

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

Реализация

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

Рекурсивная реализация

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

Достоинство:
(+) Простота реализации.

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

Итеративная реализация

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

Достоинство:
(+) Глубина рекурсии ограничена не системным стеком, а объёмом кучи.

Недостаток:
(−) Сложность реализации.

Что требуется сделать

Программа минимум. Синтаксис условий и присваиваний, семантика присваиваний, рекурсивная реализация условий.

Программа максимум. Программа минимум + итеративная реализация условий + сравнение производительности обоих реализаций.

[Mazdaywik]

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

Задача перенесена в веху refal-5-lambda, поскольку требует реализации синтаксиса, поддерживаемого РЕФАЛом-5.

[Mazdaywik]

Задача вновь стала учебной — это тема курсового на эту осень.

[Mazdaywik]

Эта задача — подзадача #112 в некотором смысле.

[Mazdaywik]

Два раза запушил кривые коммиты. Не верьте им, они не войдут никуда.

[Mazdaywik]

Всё по задаче выполнено, задача закроется автоматически, когда код окажется в ветке master.