Рефал-5λ

Приложение B. Краткий справочник

В этом приложении содержатся краткие сведения о расширениях языка Рефала-5λ и инструментах командной строки для разработки.

Установка и настройка

Последнюю версию дистрибутива всегда можно скачать со страницы репозитория:

https://github.com/bmstu-iu9/refal-5-lambda/releases/latest

Поддерживаются платформы Windows, Linux и macOS, а также имитаторы POSIX-окружения на Windows (Cygwin, MinGW)

Возможна установка в трёх вариантах:

Установка на Windows

Автоматическая установка

  1. Скачайте по ссылке выше инсталлятор, его имя имеет вид setup-refal-5-lambda-***.exe.
  2. Запустите его.

Компилятор готов к использованию.

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

Конфигурирование Рефала-5λ для использования компилятора C++

  1. Установите компилятор C++, узнайте, как им пользоваться из командной строки
  2. Запустите в командной строке rlc --scratch. На экране высветится предложение отредактировать файл, по умолчанию %APPDATA%\Refal-5-lambda\c-plus-plus.conf.bat.
  3. В указанном файле раскомментируйте строчки для для соответствующего компилятора C++. Поддерживаются MS Visual C++, BCC 5.5.1, MinGW GCC C++, Watcom, Clang. Можно использовать и другие компиляторы (однако, на них не тестировалось), для этого нужно правильно настроить соответствующие переменные среды (%CPPLINEE% и %CPPLINEL% должны заканчиваться на опцию указания имени целевого файла, обычно это опция -o).

Сборка из полускомпилированных исходников

Полускомпилированные исходники — это оттранслированные исходники Рефала-5λ в C++, которые затем можно развернуть на поддерживаемых платформах (Windows, Linux, macOS), используя компилятор C++

  1. Скачайте архив исходников (bootstrap-refal-5-lambda-***.zip или bootstrap-refal-5-lambda-***.tar.gz) по ссылке выше, распакуйте в любую папку.
  2. Запустите bootstrap.bat. Он создаст файл c-plus-plus.conf.bat и попросит его отредактировать. Как это сделать, описано в предыдущем параграфе.
  3. Снова запустите bootstrap.bat
  4. Добавьте путь к папке bin в %PATH%, к папке lib — в %RL_MODULE_PATH%.

Сборка из исходников

  1. Склонируйте репозиторий командой 
    git clone https://github.com/bmstu-iu9/refal-5-lambda

    Внимание! Скачивать архив с исходниками нельзя, не соберётся. Сборка рассчитана на использование Git.

  2. Запустите bootstrap.bat. Он создаст файл c-plus-plus.conf.bat и попросит его отредактировать. Отредактируйте его, как описано на два параграфа выше.
  3. Снова запустите bootstrap.bat или bootstrap.bat --no-tests. Скрипт bootstrap.bat по умолчанию запускает автоматизированные тесты, выполнение которых может потребовать полчаса-час работы. Ключ --no-tests предотвращает запуск тестов.
  4. Добавьте путь к папке bin в %PATH%, к папке lib — в %RL_MODULE_PATH%.

Установка на Linux и macOS

На компьютере должен быть установлен компилятор GCC C++ или Clang в режиме имитации GCC. В любом случае должна работать команда g++ в командной строке.

Автоматическая установка

Для установки выполните в командной строке команду

curl -L https://bmstu-iu9.github.io/refal-5-lambda/setup.bash | bash

Компилятор готов к использованию.

Рефал-5λ будет по умолчанию сконфигурирован на работу с компилятором GCC C++. Если желаете изменить, отредактируйте файл ~/.local/share/refal-5-lambda/c-plus-plus.conf.sh, указав в нём другой компилятор или другие опции командной строки (например, уровень оптимизации).

Сборка из полускомпилированных исходников

  1. Скачайте архив исходников (bootstrap-refal-5-lambda-***.zip или bootstrap-refal-5-lambda-***.tar.gz) по ссылке выше, распакуйте в любую папку.
  2. Установите флаг исполнимости у файла bootstrap.sh: 
    chmod +x bootstrap.sh
  3. Запустите ./bootstrap.sh. Он скомпилирует исходники, используя g++ в качестве компилятора C++. Если хотите использовать другой компилятор, отредактируйте файл c-plus-plus.conf.sh и заново запустите сборку. Файл c-plus-plus.conf.sh по умолчанию отсутствует, появляется только после первого запуска ./bootstrap.sh.
  4. Добавьте путь к папке bin в $PATH, к папке lib — в $RL_MODULE_PATH.

Сборка из исходников

  1. Склонируйте репозиторий командой 
    git clone https://github.com/bmstu-iu9/refal-5-lambda

    Внимание! Скачивать архив с исходниками нельзя, не соберётся. Сборка рассчитана на использование Git.

  2. Запустите ./bootstrap.sh или ./bootstrap.sh --no-tests. Он скомпилирует исходники, используя g++ в качестве компилятора C++. Если хотите использовать другой компилятор, отредактируйте файл c-plus-plus.conf.sh и заново запустите сборку.

    Файл c-plus-plus.conf.sh по умолчанию отсутствует, появляется только после первого запуска ./bootstrap.sh.

    Скрипт bootstrap.sh по умолчанию запускает автоматизированные тесты, выполнение которых может потребовать полчаса-час работы. Ключ --no-tests предотвращает запуск тестов.

  3. Добавьте путь к папке bin в $PATH, к папке lib — в $RL_MODULE_PATH.

Использование компилятора Рефала-5λ

В поставку компилятора входят две основные утилиты командной строки: rlc и rlmake, которыми вы и будете пользоваться. Есть ряд и других утилит (rl-lexgen, rl-rsl-decompiler), мы их рассматривать не будем.

Утилита rlc выполняет компиляцию, утилита rlmake — поиск зависимых файлов и запуск компилятора. Каждая из этих утилит «двухслойная» — состоит из «ядра» rlc-core и rlmake-core, которое вызывается из скрипта (bat-файлы на Windows, Bash-скрипты на Linux). Сами ядра ничего не знают о своём окружении (расположении стандартных библиотек, расширениях исполнимых файлов и динамических библиотек, имени файла стандартного вступления, имена префиксов и некоторые другие). Настройкой окружения занимаются скрипты.

Внимание! На Windows утилиты rlc и rlmake являются bat-файлами (соответственно, rlc.bat и rlmake.bat), поэтому из файлов сценариев их нужно вызывать командой call: call rlc.bat ….

Скрипты rlc и rlmake понимают ограниченное количество опций командной строки (причём их опции должны быть самыми первыми), остальные аргументы они как есть передают в rlc-core и rlmake-core.

Компиляция программ

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

rlc file1.ref file2.ref file3.ref …

Компилятор создаст исполнимый файл, имя которого совпадает с именем первого исходника: file1.exe на Windows или file1 на Linux.

Заметим, что для создания исполнимого файла не требуется компилятор C++, rlc по умолчанию компилирует файлы в байткод и формирует исполнимый файл путём конкатенации готового интерпретатора с байткодом. Интерпретатор при запуске открывает свой исполнимый файл для чтения, находит в нём байткод и его выполняет.

Замечание. Аналогичным образом устроены самораспаковывающиеся (SFX) архивы — в них к распаковщику приписывается файл архива.

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

Перечислять исходники в явном виде не всегда удобно, поэтому для облегчения сборки программ из нескольких исходных файлов предусмотрена утилита rlmake. Она получает из командной строки единственный файл и сканирует его в поисках меток *$FROM ИмяФайла. Эта метка означает, что также нужно подключить к сборке файл с указанным именем и его тоже рекурсивно просканировать.

Получив набор всех зависимых файлов, утилита rlmake вызывает rlc-core для компиляции программы.

Метки *$FROM рекомендуется размещать перед директивами $EXTERN, в которых перечисляются импортируемые имена функций из соответствующего исходного файла. Пример:

*$FROM DisplayName
$EXTERN DisplayCName, CName;

*$FROM Escape
$EXTERN EscapeChar, EscapeString;

Скрипты rlc и rlmake распознают только несколько ключей командной строки, причём эти ключи должны располагаться в начале. Остальные аргументы как есть передаются rlc-core и rlmake-core.

Ключи, понимаемые скриптами:

Все три сорта опций можно комбинировать произвольным образом + все они допустимы и при компиляции в исполнимые файлы, и при компиляции в динамически загружаемые библиотеки (.dll, .so, .rasl-module).

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

Поэтому не рекомендуется использовать --scratch вместе с rlc.

Скрипты rlc и rlmake поддерживают переменные среды RLC_FLAGS и RLMAKE_FLAGS соответственно. Значения этих переменных автоматически добавляются к командным строкам запуска rlc-core и rlmake-core. Их можно использовать или если одни и те же параметры приходится задавать часто, или если rlc или rlmake вызываются из какого-то другого скрипта и задать там дополнительные опции невозможно.

Дальнейшее описание в равной степени относится и к rlc, и к rlmake. Там, где упоминается опция компилятора -Od, подразумевается что эта опция «пробрасывается» от rlmake до rlc-core при помощи ключа -X: -X-Od.

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

По умолчанию компилятор создаёт исполнимый файл — файл, который можно запустить непосредственно. На Windows он будет иметь расширение .exe, на unix-like — без расширения, но с флагом исполнимости. Этот режим используется по умолчанию, хотя для него можно явно задать опцию -x или --makeexe.

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

В режиме--scratch компилятор вызывает C++ для сборки префикса из файлов C++ (как библиотечных, в том числе рантайма), так и построенных из пользовательских исходных текстов (если в них использовались нативные вставки или использовался режим -Od).

Для сборки библиотеки используется опция -l или --makelib. В этом случае, если в исходных файлах не было нативных вставок и не использовался режим -Od, строится файл, целиком состоящий из байткода и имеющий расширение .rasl-module. В случае использования нативных вставок или режима -Od вызывается компилятор C++ (т.е. необходимо использовать опцию --scratch) и строится целевой файл с расширениями .dll (на Windows) или .so (на unix-like).

Опция -R предписывает создавать только .rasl-module и не совместима с ключами -Od или нативными вставками в исходных файлах.

Опция -C включает режим «только компиляция». Целевой файл не создаётся, вместо этого для каждого файла исходного текста создаётся объектный файл с байткодом с расширением .rasl. Для файлов с нативными вставками также создаётся файл .cpp с текстом из нативных вставок. В режиме -Od для каждого исходного файла создаётся пара файлов .rasl + .cpp.

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

Среди исходных файлов могут быть не только исходные тексты, но и уже скомпилированные файлы .rasl или пары .rasl + .cpp. В этом случае они «прилинковываются» к готовой программе.

Утилита srmake для файлов .rasl без исходников (.ref, .sref) ищет одномённый файл с расширением .froms и ищет там метки зависимостей (в файлах .froms они должны иметь вид //FROM ИмяФайла). Кроме того, на метки зависимостей сканируются .cpp-файлы (тоже //FROM).

Компилятор rlc рассматривает в качестве исходных файлов файлы байткода для классического Рефала-5 (файлы с расширением .rsl). Если среди исходных файлов таковой обнаружится, то компилятор сначала вызовет утилиту rl-rsl-decompiler, а затем будет компилировать полученный файл. Утилита rlmake для .rsl-файлов также ищет файлы .froms.

Опции -d и -D определяют папки поиска исходных файлов. Компилятор и утилита rlmake, когда встречают имя файла, сначала проверяют его наличие в текущей папке (так, как записано, с расширениями .ref, .sref, .rsl и .rasl), затем по очереди в каждой из папок поиска. Опция -D, в отличие от -d, сообщает компилятору, что данная папка также является хранилищем заголовочных файлов рантайма и должна быть передана компилятору C++ опцией -I (путь поиска #include-файлов).

Опции -d и -D имеют длинные синонимы --dir/--directory и --runtime-dir/--runtime-directory соответственно.

В этих же путях поиска ищутся заголовочные файлы для директивы $INCLUDE.

Ключ --ref5rsl предписывает добавить к путям поиска пути из переменной окружения REF5RSL. Эту переменную использует интерпретатор классического Рефала-5 для поиска .rsl-файлов.

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

Опция -o файл (--target-file=файл) задаёт имя целевого файла. Целевой файл создаётся в точности с тем именем, которое указано — расширение .exe, .dll, .so не добавляется. Если эта опция не указана, то создаётся файл с именем, совпадающим с именем первого входного файла в командной строке (единственного для rlmake) и расширением по умолчанию.

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

Компилятор rlc (rlc-core)

В этом разделе мы рассмотрим опции, специфичные для компилятора. Утилита rlmake их не поддерживает, но позволяет «прокинуть», используя -Xопция (или --thru=опция, или --through=опция).

Интерпретатор rlgo

Программа rlgo загружает библиотеку (.rasl-module, .dll или .so) и запускает функцию Go или GO в ней (GO имеет приоритет).

Командная строка:

rlgo [отладочные ключи...] библиотека [аргументы...]

Список отладочных ключей тот же самый, какой допустим для файлов @refal-5-lambda-diagnostics.ini, список ключей выводится по команде --help.

Синтаксис Рефала-5λ

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

http://refal.botik.ru/book/html/

и при чтении этого справочника сосредоточиться на отличиях.

Грамматика

В грамматике ниже фигурные скобки означают повторение ноль или более раз, квадратные скобки — необязательный элемент. Строки в двойных кавычках ($ENTRY, "=" …) и имена сплошными заглавными (IDENT) соответствуют терминальным символам, имена в CamelCase (LeftPart) — нетерминальным.

Program ::= Unit
Unit ::=
    Declaration
  | Definition
  | "$INCLUDE" COMPOUND ";"
  | NATIVE-CODE
  | ";"

Declaration ::=
    "$EXTERN" NameList
  | "$ENTRY" NameList
  | "$DRIVE" NameList
  | "$INLINE" NameList
  | "$SPEC" Name Pattern ";"
  | "$LABEL" NameList

Name ::= IDENT
NameList ::= Name { "," Name } ";"

Definition ::=
    ["$ENTRY"] Name Body
  | "$ENUM" NameList
  | "$EENUM" NameList
  | "$META" NameList
  | "$SWAP" NameList
  | "$ESWAP" NameList

Body ::=
    "{" [Sentences] "}"
  | "{" NATIVE-BODY "}"

Sentences ::= Sentence { ";" Sentence } [";"]
Sentence ::= LeftPart RightPart

LeftPart ::= Pattern { Condition }
Condition ::= "," ResultEx ":" Pattern

RightPart ::=
    { Assignment } "=" ResultEx
  | { Assignment } "," ClassicBlock
Assignment ::= "=" ResultEx ":" LeftPart

ResultEx ::= Result { ":" Body }
ClassicBlock ::= Result ":" Body

Pattern ::= { PatternTerm }
PatternTerm ::=
    Symbol
  | VARIABLE ["^"]
  | "(" Pattern ")"
  | "[" Name Pattern "]"

Symbol ::= IDENT | COMPOUND | "&" Name | CHAR | NUMBER

Result ::= { ResultTerm }
ResultTerm ::=
    Symbol
  | VARIABLE
  | "(" Result ")"
  | OpenCall Result ">"
  | "[" Name Result "]"
  | "{" Body "}"
OpenCall ::= "<" [Name] | "<+" | "<-" | "<*" | "</" | "<%" | "<?"

Пробелы, табуляции и переводы строк считаются символами пустого пространства. Комментарии бывают однострочными и многострочными.

Однострочный комментарий представляет собой строку, в первой колонке которой находится знак *.

* Это комментарий

Многострочный комментарий такой же, как и в Си — /* … */, допусти́м в любом месте, где допусти́м пробельный символ.

Псевдокомментарий *$CLASSIC переключает синтаксический анализ в режим совместимости с классическим Рефалом-5, расширения Рефала-5λ будут трактоваться как синтаксические ошибки. Псевдокомментарий *$EXTENDED обратен предыдущему, разрешает в последующем тексте расширенные возможности Рефала-5λ. Стартовый режим устанавливается опциями --classic и --extended (по умолчанию).

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

Рассмотрим подробнее основные элементы грамматики.

Программа

Program ::= Unit
Unit ::=
    Declaration
  | Definition
  | "$INCLUDE" COMPOUND ";"
  | NATIVE-CODE
  | ";"

Программа — это последовательность объявлений, определений, директив включения заголовка, вставок нативного кода и точек с запятой.

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

Директива $INCLUDE предписывает включить в исходный файл текст из данного заголовочного файла. Заголовочные файлы имеют расширение .refi (синтаксис Рефала-5λ) или .srefi (синтаксис Простого Рефала, deprecated). При этом расширение можно не писать, расширение будет добавлено автоматически (.refi имеет приоритет). Поиск осуществляется в каталогах поиска, задаваемых опциями -d или -D командной строки. Рекурсивная зависимость включаемых файлов не является ошибкой.

Исходный файл после вставки всех заголовочных файлов становится единицей трансляции. Единица трансляции компилируется в файл интерпретируемого кода с расширением .rasl. Интерпретируемый код для Рефала традиционно называется RASL — Refal ASsembly Language.

В каждый исходный файл Рефала-5λ компилятор неявно добавляет директиву $INCLUDE, подключающую стандартное вступление, содержащее объявления и определения встроенных функций Рефала-5.

Вставка нативного кода — фрагмент текста, между строчками %% и %%. Пример:

%%
#include <stdio.h>
%%

Если файл содержит вставки нативного кода (в данной реализации — C++), то вместе с файлом RASL’а компилятор создаст исходник на C++, куда поместит текст всех нативных вставок. О компиляции в нативный код будет написано подробнее в соответствующей главе.

Точки с запятой игнорируются. Программа слева эквивалентна программе справа:

;;;;;;;                          |
                                 |
$EXTERN Map;;;;;;                |  $EXTERN Map;
                                 |
$ENTRY Go {                      |  $ENTRY Go {                     
  = <Map &Prout Hello World>     |    = <Map &Prout Hello World>
};;;;;;;;                        |  }
                                 |
;;;;;;;                          |

Расширения Рефала-5

Объявления

Declaration ::=
    "$EXTERN" NameList
  | "$ENTRY" NameList
  | "$DRIVE" NameList
  | "$INLINE" NameList
  | "$SPEC" Name Pattern ";"
  | "$LABEL" NameList

Name ::= IDENT
NameList ::= Name { "," Name } ";"

Объявление не создаёт нового объекта, а только задаёт свойства имеющимся, либо пополняет область видимости.

Имя функции является идентификатором. Идентификатор в Рефале-5λ начинается на заглавную или строчную латинскую букву или прочерк, состоит из латинских букв, цифр, прочерков и дефисов:

Go, Hello, __Step-Drop, cRaZy-_-nAmE

Директива $EXTERN добавляет в область видимости текущего файла перечисленные имена. Как правило, это имена entry-функций (см. далее), описанные в других единицах трансляции. Но объявление $EXTERN для имени в текущей области видимости ошибкой не является. Вместо $EXTERN можно писать $EXTERNAL или $EXTRN.

Директива $ENTRY говорит о том, что функции с данными именами являются entry-функциями. Т.е. код слева эквивалентен коду справа

Foo { … }                        | $ENTRY Foo { … }
                                 |
$ENTRY Foo, Bar;                 |
                                 |
Bar { … }                        | $ENTRY Bar { … }

Директивы $INLINE и $DRIVE описывают функции, которые компилятор может встроить или прогнать соответственно. Директива $SPEC описывает шаблон специализации для функции. Мы не будем их рассматривать в этом документе.

Функции, имена которых указываются в $ENTRY, $DRIVE, $INLINE, $SPEC, должны быть определены в той же единице трансляции.

Директива $LABEL описывает имена идентификаторов, которые можно использовать в нативных вставках.

Расширения Рефала-5

Определения функций

Definition ::=
    ["$ENTRY"] Name Body
  | "$ENUM" NameList
  | "$EENUM" NameList
  | "$META" NameList
  | "$SWAP" NameList
  | "$ESWAP" NameList

Определение определяет функцию.

Конструкция ["$ENTRY"] Name Body является основным способом определения функции. Если указано ключевое слово $ENTRY, определяемая функция становится entry-функцией — она становится доступной для вызова из других единиц трансляции. Если ключевое слово $ENTRY перед определением остутствует и имя функции не указано в списках $ENTRY, то функция является локальной.

Директивы $ENUM и $EENUM определяют пустые функции — функции без предложений. Директива $ENUM определяет локальные пустые функции, $EENUM (entry enum) — пустые entry-функции.

Программа

$ENUM Foo, Bar;
$EENUM Baz;

эквивалентна следующей:

Foo {}
Bar {}
$ENTRY Baz {}

Пустые функции в текущей реализации используются только для объявления меток квадратных скобок (см. далее).

Директива $META определяет метафункцию — функцию, которая работает с текущей областью видимости. Например, метафункция Mu вызывает функцию из текущей области видимости по указанному имени. Метафункция определяется как локальная. В теле метафункции вызывается внешняя функция с именем вида __Meta_NAME (где NAME — имя метафункции), которой передаётся исходный аргумент и описатель области видимости.

Директивы $SWAP и $ESWAP описывают статические ящики — функции, способные хранить некоторое значение между вызовами. Эти функции могут принимать любой аргумент и при вызове возвращают предыдущий аргумент вызова. Самый первый вызов всегда возвращает пустоту. По аналогии с $ENUM и $EENUM, директивы $SWAP и $ESWAP определяют локальные и entry статические ящики.

Пример.

$SWAP S;

$ENTRY Go {
  /* пусто */
    = <Prout '1: [' <S 'one'> ']'>
      <Prout '2: [' <S 'two'> ']'>
      <Prout '3: [' <S 'three'> ']'>
}

Эта программа напечатает

1: []
2: [one]
3: [two]

Расширения Рефала-5

Тело функции

Body ::=
    "{" [Sentences] "}"
  | "{" NATIVE-BODY "}"

Sentences ::= Sentence { ";" Sentence } [";"]

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

Если функция описана как последовательность предложений, то выбирается первое предложение, сопоставимое с аргументом, и это предложение выполняется. Если такового предложения не нашлось, программа аварийно останавливается.

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

Если функция описана с пустым телом (явно с пустыми фигурными скобками или при помощи директив $ENUM и $EENUM), то в ней по определению нет подходящего предложения, а значит, её вызове программа аварийно останавливается всегда.

Если тело функции описано вставкой нативного кода, то компилятор создаст функцию на целевом языке (в данной реализации — C++), куда поместит содержимое нативной вставки. Эта функция будет выполняться при активизации тела функции на Рефале.

Расширения Рефала-5

Предложения

Sentence ::= LeftPart RightPart

LeftPart ::= Pattern { Condition }
Condition ::= "," ResultEx ":" Pattern

RightPart ::=
    { Assignment } "=" ResultEx
  | { Assignment } "," ClassicBlock
Assignment ::= "=" ResultEx ":" LeftPart

ResultEx ::= Result { ":" Body }
ClassicBlock ::= Result ":" Body

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

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

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

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

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

Во время проверки условия вычисляется значение её левой части и затем оно сопоставляется с образцом. Условие выполняется, если удалось сопоставить значение левой части с образцом.

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

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

Пример. Функция Abracadabra вернёт Abra, если аргумент начинается на 'A' и файл config.ini существует. Иначе вернёт Cadabra.

Abracadabra {
  'A' e._, <ExistFile 'config.ini'> : True = Abra;

  e._ = Cadabara;
}

Левая часть первого предложения 'A' e._, <ExistFile 'config.ini'> : True говорит о том, что аргумент должен начинаться на 'A' (образец 'A' e._) и выражение <ExistFile 'config.ini'> сопоставимо с образцом True.

Левая часть второго предложения описывается образцом e._ без условий. Образец e._ успешно сопоставляется с любым предложением.

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

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

Присваивание начинается на знак =, за которым следуют расширенное результатное выражение и левая часть, разделённые знаком :. Расширенное результатное выражение вычисляется и его значение сопоставляется с левой частью. Сопоставление должно быть успешным. При неуспешном сопоставлении с левой частью программа аварийно завершается.

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

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

Расширенное результатное выражение вида

…res… : { …f1… } : { …f2… } … : { …fn−1… } : { …fn… }

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

…res… : e.1
= <{ …f1… } e.1> : e.2
= <{ …f2… } e.2> : e.3
…
= <{ …fn−1… } e.n−1> : e.n
= <{ …fn… } e.n>

или следущему результатному выражению:

<{ …fn… } <{ …fn−1… } … <{ …f2… } <{ …f1… } …res…>>…>>

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

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

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

Расширения Рефала-5

Выражения

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

Объектное выражение можно описать так:

ObjectExpr ::= { ObjectTerm }
ObjectTerm ::=
    RuntimeSymbol
  | "(" ObjectExpr ")"
  | "[" Name ObjectExpr "]"

RuntimeSymbol ::= CHAR | WORD | NUMBER | FUN-PTR | CLOSURE

Объектные выражения — это данные языка Рефал. Объектные выражения состоят из нуля или более объектных термов.

Объектный терм может быть либо символом — неделимым элементом данных (литерой, словом, числом…), либо составным термом — выражением в круглых или квадратных скобках.

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

Скобочные термы образуются скобками двух видов — круглые структурные скобки и квадратные АТД-скобки (АТД — абстрактный тип данных).

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

Для создания «запечатанного» терма можно использовать имя любой локальной функции. Обычно для этой цели специально определяют пустую локальную функцию при помощи директивы $ENUM.

Pattern ::= { PatternTerm }
PatternTerm ::=
    Symbol
  | VARIABLE ["^"]
  | "(" Pattern ")"
  | "[" Name Pattern "]"

Symbol ::= COMPOUND | IDENT | "&" Name | CHAR | NUMBER

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

Символ (symbol) в образцовом выражении может быть записан как идентификатор, составной символ, имя функции, предварённое знаком &, литера или число.

Идентификатор и составной символ являются способами записи символов-слов — некоторых строчек знаков, записываемых как единое целое. Составной символ записывается как строка в двойных кавычках, которая может содержать escape-последовательности:

Если символ-слово удовлетворяет синтаксическим требованиям для идентификаторов (состоит только из латинских букв, цифр, прочерков и дефисов и при этом не начинается на дефис), то он может быть записан и идентификатором, и составным символом. Иначе — только составным символом.

Примеры: Hello — слово Hello, "Hello" — тоже самое, "\x48\x65\x6C\x6c\x6F" — тоже слово Hello, "Hello, World!" — может быть записано только в кавычках, "" — пустое слово.

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

Литера (character) — печатный знак и некоторого символьного набора (в текущей реализации — ASCII). Записывается в одинарных кавычках. В литерах допустимы те же escape-последовательности, что и в составных символах. Несколько литер подряд могут быть записаны слитно, под одними кавычками, например, 'ABC' означает три символа, то же, что и 'A' 'B' 'C'.

Классический Рефал-5 поддерживает недокументированную возможность — escape-последовательность без кавычек. Т.е. запись \n в тексте программы означает то же, что и '\n'. Рефал-5λ поддерживает и эту возможность.

Число или макроцифра — целое число в диапазоне от 0 до 4 294 967 296 (2³²−1).

Переменная записывается как 〈тип〉.〈индекс〉, где 〈тип〉 — один из знаков s, t или e, 〈индекс〉 — последовательность латинских букв, цифр, знаков прочерка и дефиса, не может начинаться на дефис. В зависимости от типа различают s-переменные, t-переменные и e-переменные. Переменная описывает некоторый участок объектного выражения. S-переменные соответствуют символам, t-переменные — термам и e-переменые — произвольным выражениям (в том числе, пустым).

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

Пример.

Eq {
  (e.X) (e.Y)
    = e.Y
    : {
        e.X = True;
        e.X^ = False;
      }
}

В первом предложении вложенной функции переменная e.X повторная, во втором — переопределённая.

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

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

Пример. Условие , A B : s._ s._ и цепочка условий , A : s_, B : s_ всегда выполняются.

Знак ^ после безымянных переменных запрещён, т.к. бессмысленный.

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

Пусть даны объектное выражение E и образцовое выражение P. Поиск такой подстановки, которая переводит P в E называется сопоставлением выражения E с образцом P и обозначается E : P.

Сопоставление с образцом может быть неоднозначным. Например, сопоставление

(A B C) (C A A B) : (e.1 s.2 e.3) (e.4 s.2 e.5)

даст следующие подстановки (зна́ком ε обозначено пустое выражение):

  A ← e.1,  B ← s.2,    C ← e.3,  C A A ← e.4,      ε ← e.5    (1)
  ε ← e.1,  A ← s.2,  B C ← e.3,    C A ← e.4,      B ← e.5    (2)
  ε ← e.1,  A ← s.2,  B C ← e.3,      C ← e.4,    A B ← e.5    (3)
A B ← e.1,  C ← s.2,    ε ← e.3,      ε ← e.4,  A A B ← e.5    (4)

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

(3) < (2) < (1) < (4)

У подстановок (3) и (2) равная длина переменной e.1, но переменная e.4 у (3) короче.

Result ::= { ResultTerm }
ResultTerm ::=
    Symbol
  | VARIABLE
  | "(" Result ")"
  | OpenCall Result ">"
  | "[" Name Result "]"
  | "{" Body "}"
OpenCall ::= "<" [Name] | "<+" | "<-" | "<*" | "</" | "<%" | "<?"

Symbol ::= IDENT | "&" Name | COMPOUND | CHAR | NUMBER

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

В результатных выражениях безымянные переменные запрещены.

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

После открывающей угловой скобки может находиться один из следующих знаков: +, -, *, /, %, ?. Это синтаксический сахар для вызова функций, соответственно, Add, Sub, Mul, Div, Mod, Residue.

Вложенная функция, записываемая как тело функции в фигурных скобках, при выполнении превращается в объект-замыкание. Этот объект в образце может быть сопоставлен только с s-переменной. Замыкание можно вызвать, поместив его после безымянной открывающей угловой скобки.

Сравнение на равенство

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

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

Пример:

F { e.X = <Eq (e.X) (e.X)> }

Eq {
  (e.Eq) (e.Eq) = True;
  (e.L) (e.R) = False;
}

В соответствии с инвариантом функция F всегда возвращает True.

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

Пример.

F { e.X = { = e.X } }
G { e.X = { = e.X } }
H { = { e.X = e.X } }

$ENTRY Go {
  = <Eq &F &F>                /* 1 */
    <Eq &F &G>                /* 2 */
    <Eq <F 'ab'> <G 'ab'>>    /* 3 */
    <Eq <F 'ab'> <F 'cd'>>    /* 4 */
    <Eq <F 'ab'> <F 'ab'>>    /* 5 */
    <Eq <H> <H>>              /* 6 */
}

Eq {
  s.Eq s.Eq = <Prout s.Eq ' = ' s.Eq>;
  s.L s.R = <Prout s.L ' # ' s.R>;
}
  1. Два указателя на одну функцию равны.
  2. Два указателя на разные функции не равны.
  3. Два замыкания, построенные из разных вложенных функций (одна в первой строчке, другая во второй), не равны.
  4. Два замыкания с разным контекстом не равны.
  5. Замыкания построены из одной и той же вложенной функции, захватывают равный контекст. Правила нет, не определено. В актуальной реализации при компиляции без оптимизаций будут не равны.
  6. Замыкания построены из одной и той же вложенной функции, захватывают равный (пустой) контекст. Правила нет, не определено. В актуальной реализации при компиляции без оптимизаций будут равны.

ВНИМАНИЕ!!! В актуальной реализации в древесных оптимизациях есть ошибка — нарушается инвариант равенства копий для замыканий. Про неё уже есть issue в багтрекере:

https://github.com/bmstu-iu9/refal-5-lambda/issues/276

Расширения Рефала-5

Рассахаривание

Многие из конструкций Рефала-5λ являются синтаксическим сахаром — во время компиляции преобразуются в комбинации более примитивных конструкций.

Понимать, во что преобразуется программа, нужно по двум причинам:

Следующие конструкции языка являются синтаксическим сахаром и преобразуются в более примитивные:

В результате преобразований получается программа на промежуточном языке — базисном Рефале, расширенном условиями и операциями создания замыканий. Присваивания, блоки и вложенные функции преобразуются в обычные именованные функции Рефала, с именами вида 〈ИМЯ〉〈СУФФИКСЫ〉, где 〈ИМЯ〉 — имя функции, в которой они были определены, а 〈СУФФИКСЫ〉 — последовательности вида 〈ЗНАК〉〈ЧИСЛО〉〈ЗНАК〉〈ЧИСЛО〉…, которые описывают «путь» к соответствующей конструкции языка.

Можно выделить следующие проходы:

  1. Переименования переменных
  2. Рассахаривание присваиваний
  3. Рассахаривание блоков
  4. Рассахаривание вложенных функций
  5. (Рассахаривание условий)

Примечание. В файле Desugaring.ref перечислены другие проходы преобразований. В частности, там есть технические проходы, упрощающие дерево, например, удаление координат некоторых объектов. А проходы устранения присваиваний и блоков объединены в один.

Просмотреть результат рассахаривания можно в логе компиляции. Для этого нужно запустить компилятор rlc с опцией --log=имяфайла.log (а rlmake — с пробросом опции компилятору: -X--log=имяфайла.log). В логе будет выписан результат преобразований в виде псевдокода на Рефале.

1. Переименование переменных

В промежуточном языке нет ни безымянных переменных (e._…), ни переопределения переменных (e.…^). Первый проход рассахаривания таким переменным даёт новые имена.

Безымянные переменные получают имена путём приписывания некоторого уникального номера, который не совпадает ни с одной из ранее используемых переменных. Например, s._ s._ s._ переименуются в s._ s._1 s._2, а s._1 s._1 s._2 — в s._1 s._2 s._3 (любопытные читатели могут убедиться, включив лог компиляции).

Переменные, чьи индексы не начинаются с прочерка и не переопределялись ранее, свои индексы сохраняют. Каждая переопределённая переменная получает суффикс вида $‹строка›, где ‹строка› представляет собой порядковый номер, закодрованный при помощи латинских букв. Цифры 01…9 записываются при помощи букв oa…i.

Таким образом, первая переменная, помеченная ^, получит суффикс $a, вторая — $b, девятая — $i, десятая — $ao.

Пример. Функция Eq будет преобразована так:

Eq {                       →          Eq {
  (e.X) (e.Y)              →            (e.X) (e.Y)
    = e.Y                  →              = e.Y
    : {                    →              : {
        e.X = True;        →                  e.X = True;
        e.X^ = False;      →                  e.X$a = False;
      }                    →                }
}                          →          }

Переопределённая переменная во втором предложении просто получила другое имя.

О переименовании знать полезно, поскольку при использовании отладочной опции --markup-context имена добавляются в дамп.

2. Преобразование присваиваний в блоки

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

= …расш. результат… : …левая часть… = …остаток предложения…;

Становится:

= …расш. результат… : { …левая часть… = …остаток предложения… };

Нетрудно убедиться, что это преобразование сохраняет семантику.

Действительно, в исходном варианте, если сопоставление с левой частью успешно, то результат остатка предложения становится результатом всего предложения. Если сопоставление неуспешно, то программа аварийно завершается.

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

3. Преобразование блоков в вызовы вложенных функций

Блок — это просто сокращённая запись для вызова функции по определению. Следующие две конструкции по определению эквивалентны:

…результат… : { …тело функции… }

<{ …тело функции… } …результат…>

Если блоков несколько, то они «наматываются» на результатное выражение последовательно:

…результат… : { …блок 1… } : { …блок 2… } : { …блок 3… }

<{ …блок 3… } <{ …блок 2… } <{ …блок 1… } …результат…>>>

Продолжая предыдущий пример, получим:

Eq {                       →          Eq {
  (e.X) (e.Y)              →            (e.X) (e.Y)
    = e.Y                  →              = <
    : {                    →                  {
        e.X = True;        →                    e.X = True;
        e.X$a = False;     →                    e.X$a = False;
      }                    →                  }
}                          →                  e.Y
                           →                >
                           →          }

4. Преобразование вложенных функций

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

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

Хранятся они в объекте замыкания. Вообще, объект замыкания хранит две вещи: указатель на функцию, реализующую логику замыкания и связанные переменные контекста.

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

Пример:

F {
  e.X = { e.Y = e.X '*' e.Y }
}

G {
  e.X '+' e.Y
    = {
        X = e.X;
        Y = e.Y;
      }
}

↓  ↓  ↓  ↓  ↓  ↓

F {
  e.X = {{ &F\1 (e.X) }};
}

F\1 {
  (e.X) e.Y = e.X '*' e.Y;
}

G {
  e.X '+' e.Y = {{ &G\1 (e.X) (e.Y) }};
}

G\1 {
  (e.X) (e.Y) X = e.X;
  (e.X) (e.Y) Y = e.Y;
}

Пример с функцией F\1 демонстрирует, зачем нужно заключать в скобки e-переменные, взятые из окружения.

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

Eq {
  (e.X) (e.Y) = <{{ &Eq:1 (e.X) }} e.Y>;
}

Eq:1 {
  (e.X) e.X = True;
  (e.X) e.X$a = False;
}

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

Семантику замыкания можно условно описать так:

<{{ &Func e.X }} e.Y>   →   <Func e.X e.Y>

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

Почему у функций F\1 и G\1 суффикс \1, а у функции Eq:1 — :1, мы обсудим позже. Кратко: потому что в первом случае это просто вложенные функции в результатном выражении, во-втором вложенная функция построена из блока.

Для упрощения отладки компилятор поддерживает режим разметки замыканий. Он включается опцией --markup-context. В этом случае захваченные переменные в замыканиях предваряются идентификаторами с именами переменных. Пример функции G (см. выше) с такой разметкой:

G {
  e.X '+' e.Y = {{ &G\1 "e.X:" (e.X) "e.Y:" (e.Y) }};
}

G\1 {
  "e.X:" (e.X) "e.Y:" (e.Y) X = e.X;
  "e.X:" (e.X) "e.Y:" (e.Y) Y = e.Y;
}

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

5. (Преобразование условий)

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

https://github.com/bmstu-iu9/refal-5-lambda/blob/master/doc/Презентация_Козлова_Условия_2018.pdf https://github.com/bmstu-iu9/refal-5-lambda/blob/master/doc/РПЗ_Козлова_Условия_2018.pdf

Полноценная реализация условий оформлена как режим оптимизации -OC и эта оптимизация по умолчанию включается в rlc и rlmake. Режим работы без -OC считается устаревшим и не рекомендуется к использованию, т.к. он более медленный.

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

Включить режим рассахаривания условий можно ключом -OC- для rlc или -X-OC- для rlmake. В этом случае будут создаваться вспомогательные функции с суффиксами ?n?m, где ?n — порядковый номер условия в предложении (см. следующий параграф), ?m — номер вспомогательной функции для этого условия. Вспомогательных функций как минимум два, для условий при образцах с открытыми e-переменными их может быть больше.

Суффиксы присваиваний, условий, блоков и вложенных функций

Вернёмся к суффиксам. У функций F\1 и G\1 суффикс \1, а у функции Eq:1 суффикс :1. Почему и что они обозначают?

Доступны следующие суффиксы:

Суффиксы *n и @n мы здесь не будем рассматривать. Заметим, лишь, что если упала функция с суффиксом Func*n или Func@0 (только ноль!), то на суффикс можно не обращать внимания, а просто считать, что упала Func. В случае Func@n, где n ≠ 0 всё сложнее — реальный аргумент функции будет существенно перетасован. Нужно по логу компиляции разбираться во что компилятор переписал исходную функцию Func и её вызов. Но непосредственно на вызове Func@n, где n ≠ 0, программа падать не должна.

Пример. В функциях ниже в комментариях указаны имена неявных функций:

/* одно предложение */
F {
  …pattern…
    = …result… : …pattern…  /* F=1 */
    = {  /* F=2\1 */
        …pattern… = { /* F=2\1$1\1 */ }
        …pattern… = { /* F=2\1$2\1 */ }
      }
      {  /* F=2\2 */
        …pattern…
          = …result… : …pattern…  /* F=2\2=1 */
          = …result…;
      }
    : …pattern…  /* F=2 */
    = { /* F\1 */ }
}

/* два предложения */
G {
  …pattern…
    , …result… : …pattern…  /* G$1?1 */
    = …result… : …pattern…  /* G$1=2 */
    , …result… : …pattern…  /* G$1?3 */
    , …result…
    : {
        /* G$1?4:1 */
      }
    : {
        /* G$1?4:2 */
      }
    : …pattern…  /* G$1?4 */
    = …result…;

  …pattern…
    = …result…
    : {
        /* G$2:1 */
      }
    : {
        /* G$2:2 */
      };

  …pattern…
    , …result…
    {
      /* G$3:1 */
    };
}

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

Средства отладки и диагностики программ на Рефале-5λ

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

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

Аварийный отладочный дамп

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

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

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

Использование отладочного рантайма

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

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

Программа, собранная с отладочным рантаймом, читает конфигурацию диагностики по умолчанию из файлов @refal-5-lambda-diagnostics.ini и progname@refal-5-lambda-diagnostics.ini, где progname — имя исполнимого файла программы. При запуске на Windows имя программы должно содержать расширение .exe: myprogram.exe@refal-5-lambda-diagnostics.ini. Файлы должны располагаться в текущем каталоге. Любой из них может отсутствовать. Если присутствуют оба файла, то читаются оба, установки из файла с именем программы имеют приоритет.

Если в командной строке программы имеются опции вида ++diagnostic+config=filename.ini, то файлы *@refal-5-lambda-diagnostics.ini читаться не будут — вместо них конфигурация диагностики будет загружаться из ++diagnostic+config=…. Если таких опций несколько, то параметры из последующих имеют более высокий приоритет. Опции ++diagnostic+config=… невидимы для выполняемой программы: среди аргументов, возвращаемых функцией Arg, они отсутствуют.

Формат конфигурационного файла диагностики следующий:

# Строки, которые начинаются на # — комментарии

# Ниже перечислены опции с их значениями по умолчанию
print-statistics = false
start-step-trace = 0
idents-limit = 0
memory-limit = 0
step-limit = 0
dump-free-list = false
show-cookies = true
show-hidden-steps = false
enable-debugger = false
enable-profiler = false
dump-file = ""

Регистр имён опций не имеет значения, знаки _ и - в них взаимозаменяемы (т.е. IDENTS_LIMIT и Idents-Limit означают одну и ту же опцию). Логические значения могут записываться словами true и false (без учёта регистра) или числами 1 или 0. Строковые значения записываются в двойных кавычках, однако их можно опускать.

Рассмотрим каждую из опций отдельно.

Параметр print-statistics = BOOL — общий профиль работы программы

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

Total program time: 35.32800 seconds (100.0 %).
(Total refal time): 29.41900 seconds (83.3 %).
Linear pattern time: 12.81800 seconds (36.3 %).
Linear result time: 11.58300 seconds (32.8 %).
Native time: 3.69600 seconds (10.5 %).
t- and e-var copy time: 2.48500 seconds (7.0 %).
Open e-loop time (clear): 2.25100 seconds (6.4 %).
Runtime time overhead: 1.71500 seconds (4.9 %).
Context copy time: 0.49800 seconds (1.4 %).
Repeated e-var match time (inside e-loops): 0.25100 seconds (0.7 %).
Repeated t-var match time (inside e-loops): 0.03100 seconds (0.1 %).
Step count 26657583
Identifiers allocated: 1868
Memory used 549000 nodes, 549000 * 16 = 8784000 bytes

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

Рассмотрим каждую из строчек подробнее:

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

Число шагов, отображаемое в Step count, отличается от значения, возвращаемого функцией <Step> в бо́льшую сторону. Функция Step подсчитывает число шагов, которые сделал классический Рефал-5 при выполнении данной программы. При этом предполагается, что встроенные функции Рефала-5 выполняются за один шаг. Однако, в Рефале-5λ некоторые «встроенные» функции Рефала-5 написаны на Рефале и фактически выполняются за несколько шагов.

Параметры start-step-trace и step-limit используют реальное количество шагов.

Параметр start-step-trace = n

Иногда по состоянию поля зрения на момент ошибки трудно понять, откуда же эта ошибка взялась, как сформировался некорректный аргумент для функции. Параметр start-step-trace позволяет увидеть временной контекст ошибки — некоторое количество шагов, предшествующее падению. Если макрос установлен и равен неотрицательному числу n, то начиная с n-го шага на stderr (по умолчанию) будет на каждом шаге выводиться дамп поля зрения (в том же формате, что и при ошибке).

Поэтому, если непонятен контекст ошибки, установите параметр start-step-trace равным числу, немного меньшему, чем номер шага, который привёл к ошибке. На сколько меньшему — определяется опытным путём.

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

Параметр idents-limit = n

Eсли эта опция установлена в ненулевое значение, то программа аварийно остановится при создании указанного количества идентификаторов (см. Identifiers allocated выше).

Дело в том, что память для идентификаторов, созданных функциями Implode и Implode_Ext, никогда не освобождается. Поэтому, если, например, создавать всё новые и новые идентификаторы в цикле, то память будет утекать. Опция позволяет отлаживать такие утечки памяти.

Параметр memory-limit = n

Макрос должен принимать целочисленное значение. Если значение ненулевое, то при превышении объёма распределённой памяти (в узлах, см. выше про Memory used) программа будет останавливатся с ошибкой недостатка памяти, даже если в системе памяти достаточно.

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

Параметр step-limit = n

Параметр позволяет прервать программу при достижении указанного количества шагов. Нулевое значение означает отсутствие ограничения.

Параметр помогает отлаживать зависающие программы — если программа выполняется аномально долго, то прерывание по step-limit, скорее всего, окажется внутри бесконечного цикла.

Параметр dump-free-list = BOOL

Если этот параметр установлен, то в отладочном дампе выводится не только первичное активное подвыражение и поле зрения, но и содержимое списка свободных узлов — области памяти, где распределяется новое значение результатного выражения (см. первую главу раздела). Параметр влияет на дамп, выводимый как при ошибке, так и при установленном макросе start-step-trace.

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

Параметр show-cookies = BOOL

Параметр включает отображение маркеров области видимости в отладочном дампе. Маркеры записываются после имён функций как FuncName#MMM:NNN, где MMM и NNN — десятичные числа. Каждая такая пара чисел уникальна для единицы трансляции программы.

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

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

Параметр show-hidden-steps = BOOL

Если этот параметр установлен, то в дампе по start-step-trace будут отображаться шаги реализации встроенных функций, а также функций __INIT и __FINAL. Если не установлен — встроенные функции будут изображаться как «одношаговые».

Параметр enable-debugger = BOOL

Если этот параметр установлен, при запуске программы будет включаться консольный пошаговый отладчик (типа gdb или reftr). Отладчик на данный момент работает нестабильно, поэтому мы не рекомендуем им пользоваться и не будем описывать в этом справочнике.

Параметр enable-profiler = BOOL

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

Параметр dump-file = STRING

Если этот параметр установлен, то отладочный дамп, выводимый при аварийном остановке или при включённой опции start-step-trace, будет выводиться не на stderr, а в указанный файл. Пустая строка означает, что дамп выводится на stderr.

Использование отладчика языка C++

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

Однако, отладчик полезен при отладке функций, которые сами пишутся на C++, или рантайма. В частности, автор использовал GDB для просмотра точки падения и трассировки стека при ошибках доступа к памяти (SEGFAULT’ах).

Отладка на уровне исходного кода — отладочная печать

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

Поскольку открывать файлы в Рефале-5λ (как и в Рефале-5) необязательно, простота вывода в файл сравнима с простотой вывода на консоль — вместо Prout пишем Putout с неиспользуемым в программе номером. А дальше просто смотрим текстовый файл REFAL*.DAT.

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

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

Fibonacci {
  1 = 1;
  s.N = <DoFib 2 s.N 1 1>;
}

DoFib {
  s.N s.N s.Prev s.Cur = s.Cur;

  s.K s.N s.Prev s.Cur =
    <DoFib <Add 1 s.K> s.N s.Cur <Add s.Prev s.Cur>>;
}

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

Для этого сначала переименуем DoFib, например, в DoFib-DEBUG.

DoFib-DEBUG {
  s.N s.N s.Prev s.Cur = s.Cur;

  s.K s.N s.Prev s.Cur =
    <DoFib <Add 1 s.K> s.N s.Cur <Add s.Prev s.Cur>>;
}

Отлаживаемая функция имеет формат <DoFib s.K s.N s.Prev s.Cur>. Добавим новую функцию с именем DoFib, левая часть которой совпадает с форматом исходной. В правой части запишем вызов переименованной функции.

Важно. В общем случае, если отлаживаемая функция имела модификатор $ENTRY, функция-оболочка с отладочной печатью тоже должна быть entry.

Удобно это делать перед исследуемой функцией:

DoFib {
  s.K s.N s.Prev s.Cur =
    <DoFib-DEBUG s.K s.N s.Prev s.Cur>;
}

DoFib-DEBUG {
  s.N s.N s.Prev s.Cur = s.Cur;

  s.K s.N s.Prev s.Cur =
    <DoFib <Add 1 s.K> s.N s.Cur <Add s.Prev s.Cur>>;
}

Теперь в функцию DoFib можно добавить вывод любой отладочной печати, например, всех переменных.

DoFib {
  s.K s.N s.Prev s.Cur =
    <Putout 13 '<DoFib>'>
    <Putout 13 '  s.K = ' s.K>
    <Putout 13 '  s.N = ' s.N>
    <Putout 13 '  s.Prev = ' s.Prev>
    <Putout 13 '  s.Cur = ' s.Cur>
    <Putout 13>
    <DoFib-DEBUG s.K s.N s.Prev s.Cur>;
}

DoFib-DEBUG {
  s.N s.N s.Prev s.Cur = s.Cur;

  s.K s.N s.Prev s.Cur =
    <DoFib <Add 1 s.K> s.N s.Cur <Add s.Prev s.Cur>>;
}

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

Если отладочная функция располагалась перед исходной, то её довольно легко удалить — нужно стереть строки от DoFib (не включая) до DoFib-DEBUG (включая), удаляемые строки помечены крестиком:

  DoFib {
×   s.K s.N s.Prev s.Cur =
×     <Putout 13 '<DoFib>'>
×     <Putout 13 '  s.K = ' s.K>
×     <Putout 13 '  s.N = ' s.N>
×     <Putout 13 '  s.Prev = ' s.Prev>
×     <Putout 13 '  s.Cur = ' s.Cur>
×     <Putout 13>
×     <DoFib-DEBUG s.K s.N s.Prev s.Cur>;
× }
×
× DoFib-DEBUG {
    s.N s.N s.Prev s.Cur = s.Cur;

    s.K s.N s.Prev s.Cur =
      <DoFib <Add 1 s.K> s.N s.Cur <Add s.Prev s.Cur>>;
  }

Как упростить отладку — соблюдать форматы функций

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

Одной плохих практик при программировании на Рефале является смешивание основной («интерфейсной») и вспомогательной функций в одном определении. Например, функцию Fibonacci из примера выше можно было бы написать так:

* ЭТО ПЛОХОЙ ПРИМЕР, НЕ ПИШИТЕ ТАК!!!

Fibonacci {
  1 = 1;

  s.N = <Fibonacci 2 s.N 1 1>;

  s.N s.N s.Prev s.Cur = s.Cur;

  s.K s.N s.Prev s.Cur =
    <Fibonacci <Add 1 s.K> s.N s.Cur <Add s.Prev s.Cur>>;
}

Здесь мы объединили функции Fibonacci и DoFib, пользуясь тем, что они имеют разные форматы.

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

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

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

* Это хороший пример

$ENTRY refal05c_PrintNotFound {
  (NotFound e.FileName) =
    <Prout 'COMMAND LINE ERROR: file ' e.FileName ' not found'>;

  (Output e.FileName) = ;

  (Source (e.Source) e.Output) = ;
}

можно «сократить» так:

* А ЭТО ПЛОХОЙ ПРИМЕР, НЕ ПИШИТЕ ТАК!!!

$ENTRY refal05c_PrintNotFound {
  (NotFound e.FileName) =
    <Prout 'COMMAND LINE ERROR: file ' e.FileName ' not found'>;

  e.Other = ;
}

Функцию

* Это хороший пример

DoParseBlock {
  t.ErrorList (e.References) (e.Sentences) (TkCloseBlock t.SrcPos) e.Tail =
    (Sentences e.Sentences) t.ErrorList (e.References) e.Tail;

  t.ErrorList (e.References) (e.Sentences) (TkEOF t.SrcPos) e.Tail =
    (Sentences e.Sentences)
    <EL-AddErrorAt
      t.ErrorList t.SrcPos 'Unexpected EOF, expected "}"'
    >
    (e.References)
    (TkEOF t.SrcPos) e.Tail;

  t.ErrorList (e.References) (e.Sentences) e.Tokens =
    <ParseSentence t.ErrorList (e.References) (e.Sentences) e.Tokens>;
}

«упростить» так (см. последнее предложение):

* А ЭТО ПЛОХОЙ ПРИМЕР, НЕ ПИШИТЕ ТАК!!!

DoParseBlock {
  t.ErrorList (e.References) (e.Sentences) (TkCloseBlock t.SrcPos) e.Tail =
    (Sentences e.Sentences) t.ErrorList (e.References) e.Tail;

  t.ErrorList (e.References) (e.Sentences) (TkEOF t.SrcPos) e.Tail =
    (Sentences e.Sentences)
    <EL-AddErrorAt
      t.ErrorList t.SrcPos 'Unexpected EOF, expected "}"'
    >
    (e.References)
    (TkEOF t.SrcPos) e.Tail;

  e.Args = <ParseSentence e.Args>;
}

Обе функции (конечно, в хороших примерах) взяты из исходников компилятора Рефала-05.

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

Коды возврата скомпилированных программ

При корректном завершении (когда поле зрения становится пассивным — не содержит вызовов функций) программа завершается с кодом возврата 0.

Если программа завершилась вызовом функции Exit, то её кодом возврата будет указанное значение с точностью до особенностей платформы. Например, на Linux будут учитываться только младшие 8 бит кода возврата.

В случае аварийного останова код возврата будет следующим:

This site is open source. Improve this page.