В этом приложении рассмотрены два важных и связанных между собой приёма программирования на Рефале: форматы функций и неформальная нотация для записи типов данных. Рассмотренная неформальная нотация активно используется в самих исходных текстах в комментариях, поэтому при доработке компилятора её нужно понимать и эти комментарии грамотно сопровождать.
Формально все функции Рефала принимают один аргумент и возвращают одно значение, и то и другое является объектным выражением. Но на практике существует потребность передавать в функцию и возвращать из неё несколько самостоятельных значений. Способ упаковки нескольких значений в одно объектное выражение мы будем называть форматом. Таким образом, для функции описываются формат аргумента и формат результата — пару этих форматов мы будем называть форматом функции.
В Рефале существует единственный способ анализа (др.-греч. ἀνάλυσις «разложение, расчленение, разборка») объектного выражения — сопоставление с образцом. Поэтому, чтобы извлечь из одного объектного выражения его составные части (отдельные значения), его нужно сопоставить с образцом. Поэтому формат мы будем записывать в виде некоторого образцового выражения. Для записи формата функции будем использовать следующую форму:
<ИмяФункции ФорматАгрумента> == ФорматРезультата
Здесь ФорматАргумента и ФорматРезультата — некоторые образцовые выражения.
Двойной знак равенства == символизирует, что замена вызова функции на конечное
пассивное выражение может выполняться на некоторое количество шагов
рефал-машины.
Переменные в форматах аргумента и результата соответствуют тем самым отдельным значениям, которые мы упаковываем в одно выражение. О переменных в формате аргумента мы будем говорить как об аргументах функции, по умолчанию подразумевая, что эти аргументы упакованы в некоторый формат. Аналогично о переменных в формате результата будем говорить как об отдельных возвращаемых значениях.
Формат аргумента также часто называют входным форматом, формат результата — выходным форматом.
Если функция возвращает пустое выражение, то формат результата будем обозначать
словом пусто. Иногда вместо слова пусто используют [] — пару квадратных
скобок.
Иногда функция может возвращать разные значения в зависимости от результата работы (например, успешно/неуспешно), в этом случае формат функции мы будем описывать так:
<ИмяФункции ФорматАргумента>
== ФорматРезультата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).
С точки зрения хорошего стиля обязательными являются форматы для entry-функций
(кроме функции Go по очевидным причинам), либо там, где функция работает
с типом данных, который нужно задокументировать (см. далее).
На начальном периоде обучения желательно писать форматы для всех функций.
При этом, чтобы комментарий с форматом был правильным, нужно, чтобы тело самой функции и все точки её вызова согласовывались с заявленным форматом. Что это значит?
Если среди фактических аргументов вызова функции имеются вызовы арифметических функций с небольшими аргументами, причём их результат тоже небольшой и неотрицательный, то допустимо рассматривать результаты работы этих функций не как длинные числа (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λ)
даст чуть ли не кубическую сложность, более хитрые алгоритмы — линейную.
Но зачем всё это, если можно передать две переменные за малое константное
время?
К сожалению, плохой формат демонстрируют несколько встроенных функций — функции
работы с копилкой. В них (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
> == …
Это может привести к крошечному снижению быстродействия (время на построение дополнительных символов и сопоставление с ними), но при этом несколько проясняет программу и может предотвращать ошибки в форматах. Я (А.К.) так не пишу, но некоторые так пишут. Это тоже вопрос личных предпочтений.
Рефал — динамически типизированный язык, единственный тип данных — объектное выражение. Но объектное выражение — очень аморфная вещь, и редко когда областью определения функции является произвольное объектное выражение.
Как правило, функции работают со структурированными данными. Т.е. понятия, с которыми работает программа, определённым образом кодируются объектными выражениями и могут работать только с такими кодированными данными.
Например, мы хотим работать с арифметическими выражениями (вычислять их значения, преобразовывать их разными способами: упрощать, дифференцировать), поэтому нам нужен способ их представления в виде объектных выражений.
Для простоты положим, что наши арифметические выражения могут состоять из двухместных арифметических действий: сложения, вычитания, умножения и деления, длинных целых чисел и переменных. Примем такие правила:
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-переменные. Для того,
чтобы записать ей правильный формат, достаточно было бы завернуть в скобки
только один из аргументов. Здесь для симметрии и красоты мы завернули в скобки
оба аргумента.
Выше мы описали типы данных «арифметическое выражение» и «таблица значений переменных» словами на русском языке. Получилось длинно и не наглядно даже для таких простых типов. Более сложные типы потребовали более громоздкого описания.
Чтобы описывать типы данных компактно и наглядно, программисты на Рефале прибегают к формализованным нотациям, похожим на форму Бэкуса-Наура или расширенную форму Бэкуса-Наура — нотации для описания синтаксиса языков программирования (рекомендую прочитать две предыдущие ссылки). Вариантов этой нотации столько же, сколько программистов на Рефале, здесь будет даваться нотация, принятая при документировании исходных текстов Рефала-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*)*> == пусто
Формально тип функции записан правильно, но только зачем? Типы и форматы пишутся для программиста, чтобы проще было понимать программу. А в записи выше типы функций записаны труднопонимаемым образом. В общем, пишите понятно, особенно комментарии. Иначе зачем их писать?