Приложение A. Форматы функций и типы данных в Рефале-5λ
=======================================================

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

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


Форматы функций в Рефале
------------------------

### Что такое «формат функции»

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

В Рефале существует единственный способ анализа (др.-греч. ἀνάλυσις «разложение,
расчленение, разборка») объектного выражения — сопоставление с образцом.
Поэтому, чтобы извлечь из одного объектного выражения его составные части
(отдельные значения), его нужно сопоставить с образцом. Поэтому формат мы будем
записывать в виде некоторого образцового выражения. Для записи формата функции
будем использовать следующую форму:

    <ИмяФункции ФорматАгрумента> == ФорматРезультата

Здесь `ФорматАргумента` и `ФорматРезультата` — некоторые образцовые выражения.
Двойной знак равенства `==` символизирует, что замена вызова функции на конечное
пассивное выражение может выполняться на некоторое количество шагов
рефал-машины.

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

_Формат аргумента_ также часто называют _входным форматом,_ _формат
результата_ — _выходным форматом._

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

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

    <ИмяФункции ФорматАргумента>
      == ФорматРезультата1
      == ФорматРезультата2
      …
      == ФорматРезультатаN

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

#### Примеры форматов функций

Встроенная функция `Open`, которая открывает файл и связывает его с некоторым
номером:

    <Open s.Mode s.FileNo e.FileName> == пусто

Функция получает три аргумента: `s.Mode` — режим, в котором следует открыть
файл, `s.FileNo` — номер файла для открытия и `e.FileName` — имя файла.

Встроенная функция `First` отделяет от выражения префикс указанной длины:

    <First s.Length e.Expr> == (e.Prefix) e.Suffix

Функция принимает два аргумента: `s.Length` — длину префикса и `e.Expr` —
исходное выражение, и возвращает два значения `e.Prefix` — начальная часть
выражения длиной `s.Length` и `e.Suffix` — оставшаяся часть выражения (если
`s.Length` больше длины выражения, то `e.Prefix` совпадает с `e.Expr`,
а `e.Suffix` пустой).

Функция `LowLevelRASL`, выполняющая один из проходов компиляции в Рефале-5λ:

    <LowLevelRASL s.GenMode e.RASLAST>
      == t.RASLModule
      == t.RASLModule t.NativeModule

Функция принимает режим генерации кода `s.GenMode` и императивное синтаксическое
дерево `e.RASLAST`, возвращает либо только модуль с интерпретируемым кодом
`t.RASLModule`, либо модуль с интерпретируемым кодом `t.RASLModule` и модуль
с нативным кодом `t.NativeModule`. Её возвращаемое значение зависит от режима
генерации кода и содержимого `e.RASLAST`.


### Использование форматов функций

Форматы функций, как правило, записываются в комментариях перед функциями, либо
в сопроводительной документации (например, [src/compiler/README.md][readme]).
С точки зрения хорошего стиля обязательными являются форматы для entry-функций
(кроме функции `Go` по очевидным причинам), либо там, где функция работает
с типом данных, который нужно задокументировать (см. далее).
На начальном периоде обучения желательно писать форматы для всех функций.

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

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

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

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

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

Иногда бывает допустимо иметь несколько форматов как «синтаксический сахар» —
некоторым аргументам можно дать значения по умолчанию, либо более простую
запись. В этом случае предложение «простого формата» повторно вызывает себя,
его усложняя — добавляя недостающие параметры или усложняя формат. Хорошим
примером являются встроенные функции арифметики — они предназначены для
работы с длинными числами, но разрешают первый аргумент писать без скобок,
если он является макроцифрой. Примером на аргумент по умолчанию можно считать
функцию `Open` — если имя файла не задано (вызывается в виде `<Open 'w' 7>`),
по умолчанию открывается файл `REFALn.DAT`, где вместо `n` подставляется номер
файла (в примере — `<Open 'w' 7 'REFAL7.DAT'>`).


### Как выбирать форматы

**Хороший формат должен разбираться однозначно и эффективно.** А это значит,
что в нём не должно быть открытых и повторных переменных. Во-первых, они
сопоставляются неэффективно (время их сопоставления зависит от объёма входных
данных), во-вторых, использование открытых переменных в формате может привести
к неоднозначности.

S-переменные, t-переменные, закрытые e-переменные, скобки и символы
сопоставляются эффективно — за малое константное время. Поэтому их можно
использовать в форматах.

Рассмотрим примеры некоторых **плохих форматов** и разберём, чем же они плохи.

    <F e.1 ',' e.2 ',' e.3> == …

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

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

    <F e.X 'A' e.Y e.X 'B' e.Y> == …

Этот формат, как ни странно, однозначен. Его длина всегда чётная, первая
половина — `e.X 'A' e.Y`, вторая — `e.X 'B' e.Y`. Начинаются обе половины
с `e.X`, поэтому если их последовательно просматривать — первое и единственное
отличие будет в термах `'A'` и `'B'` соответственно. Одинаковые термы до `'A'`
и `'B'` будут соответствовать значению `e.X`, после — `e.Y`. Да, сопоставление
с ним однозначно, хотя не очевидно на первый взгляд.

Но вот сам процесс сопоставления потребует удлинений двух открытых переменных
`e.X` и `e.Y` и дальнейшего сопоставления с их же повторными вхождениями.
Наивная реализация сопоставления с образцом (которая реализована в Рефале-5λ)
даст чуть ли не кубическую сложность, более [хитрые алгоритмы][orl] — линейную.
Но зачем всё это, если можно передать две переменные за малое константное
время?

К сожалению, плохой формат демонстрируют несколько встроенных функций — функции
работы с копилкой. В них (`Br` и `Rp`) ключ от значения отделяется знаком `'='`,
что в их реализации приводит к поиску по открытой переменной. Но они таковы
по историческим причинам — Рефал-5 их поддерживает по давней традиции (так же,
как называет функцию чтения из `stdin` функцией чтения перфокарт — `Card`),
а Рефал-5λ вынужден поддерживать с ним полную совместимость.

**Хорошие форматы** строятся по такому принципу: все значения, представляемые
e-переменными, должны быть закрытыми e-переменными. Т.е. повторных переменных
в формате быть не должно, на каждом скобочном уровне может быть не более одной
e-переменной. Простейший способ получить хороший формат — выписать подряд все
передаваемые значения, если среди них есть e-переменные, все кроме одной
завернуть в скобки. Допустим, нам надо передать в функцию значения `t.1`, `s.2`,
`e.3`, `e.4`, `t.5`, `s.6`, `e.7`. Записываем их последовательно:

    t.1 s.2 e.3 e.4 t.5 s.6 e.7

Здесь у нас 3 e-переменные. Ставим вокруг двух из трёх на свой вкус круглые
скобки:

    t.1 s.2 (e.3) e.4 t.5 s.6 (e.7)

Формат готов. При желании можно заключать в скобки все e-переменные, это уже
вопрос личных предпочтений:

    t.1 s.2 (e.3) (e.4) t.5 s.6 (e.7)

Можно «декорировать» формат дополнительными константными символами, например,
вместо

    <Parse e.Tokens t.SymTable t.ErrorList> == …

писать

    <Parse
      Tokens '=' e.Tokens SymTable '=' t.SymTable ErrorList '=' t.ErrorList
    > == …

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


Типы данных в Рефале, неформальная нотация для их записи
--------------------------------------------------------

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

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

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

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

* Выражение записывается одиночным термом (t-переменной).
* Арифметическое действие записывается с помощью скобочного терма, внутри
  которого последовательно записываются: левый операнд, знак действия
  в виде литеры, правый операнд.
* Длинное число записывается с помощью скобочного терма, содержимое которого
  начинается с символа `Num`, за которым следует значение числа.
* Переменная записывается как скобочный терм, содержимое которого начинается
  с символа `Var`, за которым следует имя переменной — слово.

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

Запишем теперь функцию вычисления значения выражения:

    /*
      <Eval t.Expr e.VarTable> == e.LongNumber
    */
    Eval {
      (Num e.Val) e.VarTable = e.Val;

      (Var s.VarName) e.VarTable-B (s.VarName e.Val) e.VarTable-E = e.Val;

      (t.Left s.Op t.Right) e.VarTable =
        <Eval-Op (<Eval t.Left e.VarTable>) s.Op (<Eval t.Right e.VarTable>)>;
    }

    /*
      <Eval-Op (e.Left) s.Op (e.Right)> == e.LongNumber
    */
    Eval-Op {
      (e.X) '+' (e.Y) = <Add (e.X) e.Y>;
      (e.X) '-' (e.Y) = <Sub (e.X) e.Y>;
      (e.X) '*' (e.Y) = <Mul (e.X) e.Y>;
      (e.X) '/' (e.Y) = <Div (e.X) e.Y>;
    }

Функция `Eval-Op` принимает два длинных числа — две e-переменные. Для того,
чтобы записать ей правильный формат, достаточно было бы завернуть в скобки
только один из аргументов. Здесь для симметрии и красоты мы завернули в скобки
оба аргумента.

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

Чтобы описывать типы данных компактно и наглядно, программисты на Рефале
прибегают к формализованным нотациям, похожим на [форму Бэкуса-Наура][bnf]
или [расширенную форму Бэкуса-Наура][rbnf] — нотации для описания синтаксиса
языков программирования (рекомендую прочитать две предыдущие ссылки). Вариантов
этой нотации столько же, сколько программистов на Рефале, здесь будет даваться
нотация, принятая при документировании исходных текстов Рефала-5λ.

Нотацию будем называть _неформальной,_ поскольку она, во-первых, как и псевдокод,
допускает ad hoc расширения, и, во-вторых, не контролируется компилятором, т.к.
пишется только в комментариях.

Типы данных будем именовать переменными Рефала соответствующего вида. Например,
арифметическое выражение у нас является термом, поэтому будем обозначать его
как `t.Expr`, таблица переменных — последовательность термов, e-переменная,
обозначим как `e.VarTable`.

После имени переменной ставится знак `::=`, за которым следует набор альтернатив,
вариантов того, чем может являться этот тип. Альтернативы разделяются знаком `|`.
В альтернативах могут присутствовать символы и структурные скобки с тем же
смыслом, как и в Рефале. Переменная в альтернативе означает вхождение значения
соответствующего типа. После символа, скобочного терма или переменной может
следовать один из знаков `*`, `+` или `?` со следующим смыслом:

* `*` означает, что предшествующий элемент может повторяться ноль или более раз,
* `+` — один или более раз (т.е. как минимум один раз встречается),
* `?` — ноль или один раз (или есть, или нет).

Есть также и «встроенные» типы:

* любая макроцифра обозначается `s.NUMBER`,
* любая литера — `s.CHAR`,
* любое слово — `s.WORD`,
* любой символ, терм и выражение — соответственно, `s.ANY`, `t.ANY`, `e.ANY`
  или `s.ANY-SYMBOL`, `t.ANY-TERM`, `e.ANY-EXPR`.

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

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

    e.LongNumber ::= s.Sign? s.NUMBER+
    s.Sign ::= '+' | '-'

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

Таким образом, типы `t.Exrp` и `e.VarTable` могут быть описаны как

    t.Expr ::= (t.Expr s.Op t.Expr) | (Num e.LongNumber) | (Var s.VarName)
    s.Op ::= '+' | '-' | '*' | '/'
    s.VarName ::= s.WORD

    e.VarTable ::= (s.VarName e.LongNumber)*

Возникли вспомогательные типы — `s.Op` — обозначение двухместной операции,
`s.VarName` — имя переменной.

Описания типов `t.Exrp` и `e.VarTable` можно поместить в исходную программу или
отдельным комментарием, или добавить в комментарий перед функцией `Eval` после
описания её формата.

В библиотеке `LibraryEx` есть две удобные функции — `LoadFile` и `SaveFile`,
которые, соответственно, загружают и сохраняют текстовые файлы. Содержимое
текстовых файлов представлено как последовательности строчек, строчка
представляется скобочным термом, содержащим последовательность литер. Типы этих
функций можно описать так:

    <LoadFile e.FileName> == e.Lines
    <SaveFile (e.FileName) e.Lines> == пусто

    e.FileName ::= s.CHAR+
    e.Lines ::= (e.Line)*
    e.Line ::= s.CHAR*

Как видно, описания типов данных прекрасно сочетаются с описаниями форматов
функции — достаточно после формата для каждого аргумента описать его тип.
Можно при записи формата функции сразу записывать её тип, если это не усложняет
понимание. Например, в исходных текстах упомянутая выше функция `LowLevelRASL`
описана как

    <LowLevelRASL s.GenMode e.RASLAST>
      == t.RASLModule t.NativeModule?

Вместо двух выходных форматов записан один, но с использованием знака `?`.

Функции `LoadFile` и `SaveFile` технически можно (но стилистически ни в коем
случае!) описать так:

    <LoadFile s.CHAR+> == (s.CHAR*)*
    <SaveFile (s.CHAR+) (s.CHAR*)*> == пусто

Формально тип функции записан правильно, но только зачем? Типы и форматы
пишутся для программиста, чтобы проще было понимать программу. А в записи выше
типы функций записаны труднопонимаемым образом. В общем, пишите понятно,
особенно комментарии. Иначе зачем их писать?


[readme]: https://github.com/bmstu-iu9/refal-5-lambda/blob/master/src/compiler/README.md
[orl]: https://pat.keldysh.ru/~orlov/publications/2004.05-AbramovOrlov-Kompiljacija_sintaksicheskogo_otozhdestvlenija_jazyka_Refal.pdf
[bnf]: https://ru.wikipedia.org/wiki/Форма_Бэкуса_—_Наура
[rbnf]: https://ru.wikipedia.org/wiki/Расширенная_форма_Бэкуса_—_Наура
