Эта задача — подзадача для #1.

Глобальные переменные не нужны. Практика показывает, что можно написать самоприменимый компилятор Рефала без глобальных переменных. Простой Рефал, плавно мутировавший в Рефал-5λ, не использовал никакие глобальные переменные (LexGen — исключение).

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

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

В Простом Рефале статические ящики появились для совместимости с Модульным Рефалом. Для Рефала-05 такой цели не ставится, а значит, это избыточная возможность.

Согласно инструкции установке в README.md

https://github.com/Mazdaywik/Refal-05/blob/98004229b456c8fb623c8757794a42242f28ff05/README.md#Установка-иконфигурирование

в пути поиска нужно указывать каталоги lib и src. lib нужна для файлов рантайма (refalrts) и встроенных функций (Library.ref). src нужна только для LibraryEx. В то время, как там лежит не только расширение библиотеки, но и все исходники самого компилятора:

• Error.ref
• Escape.ref
• FindFile.ref
• Generator.ref
• Lexer.ref
• Parser.ref
• refal05c.ref
• Sentence.ref
• SymTable.ref

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

Escape содержит единственную функцию EscapeChar, которая записывает в экранированном виде разные нехорошие знаки. Для числовых кодов использует сишное представление — восьмеричные числа. Отдельно может быть использована по назначению, только назначение весьма узкое.

FindFile ищет исходники на Рефале-05 или на Си в заданных папках поиска. Отдельно может быть использована.

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

Lexer отдельно использовать можно, входная точка LexFolding возвращает поток лексем для заданного файла. Сфера применения узка — вход для парсеров или каких-нибудь препроцессоров, зависит от Escape.

Parser — единственная входная точка CompileFile принимает имя исходного и целевого файла и выполняет компиляцию. Компиляцию Рефала-05 в Си. Смысл использовать отдельно не очевиден. Зависит от Lexer, Error, SymTable, Generator, Sentence.

refal05c — это сам компилятор со входной точкой Go. Зависит от всего прямо или косвенно. Смысла использовать отдельно как библиотеку нет.

Sentence — компилятор предложения в последовательность элементарных императивных команд, зависит от Escape. Нет смысла использовать как библиотеку.

SymTable — решает узкую задачу, контроль области видимости функций Рефала-05. Зависит от Error и Generator. Использовать отдельно бессмысленно.

Частично осмысленно использовать как отдельные компоненты только Error, Escape, FindFile и Lexer, да и то основания для большинства из них зыбкие.

Предлагается

Предлагается сделать два повторно используемых компонента: Parser, который принимает имя исходного файла и возвращает либо Success и синтаксическое дерево, либо Fails и список ошибок, и Generator, который принимает имя целевого файла и синтаксическое дерево, и сохраняет в указанном файле сишный код.

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

Документация к проекту устарела:

1. Цели и задачи изменились и уточнились — #33, а значит, вся первая глава подлежит полному переписыванию.
2. Синтаксически входной язык на данный момент является Рефалом-5 с псевдокомментариями, а, согласно, #38, псевдокомментариев уже не будет. Так что описание синтаксиса устарело. Кроме того, в ходе решения #28, в библиотеку добавлено несколько встроенных функций, которые не задокументированы.
3. Два следующих раздела — Установка и использование, конфигурирование, отладка и Библиотека компонентов компилятора нуждаются во внимательном чтении и устранении косяков.
4. Согласно #40, изменится генерация сопоставления с образцом, а значит, нужно будет обновлять и последний раздел.

Таким образом, документацию надо обновлять:

• Переписать первую главу в соответствии с новой концепцией (#33).
• Обновить описание синтаксиса.
  Т.к. синтаксис совпадает с синтаксисом Рефала-5, то само описание синтаксиса (включая приложение с БНФ) нужно выкинуть, нужно оставить лишь подробное описание отличий в семантике Mu Рефала-5 и Рефала-05 (#38)
  Удалённое описание синтаксиса можно воскресить (с соответствующими дополнениями) или в документации по Рефалу-5λ, или в документации по фреймворку.
• Просмотреть другие главы на предмет наличия неактуальных сведений.
• Задокументировать добавленные встроенные функции.
• В случае переписывания сопоставления с образцом, переписать соответствующую главу документации (#40).

Эта задача — подзадача для #1 и #2.

Пустые функции и идентификаторы дублируют друг друга. Поэтому что-то из них нужно удалить.

В текущей реализации Простого Рефала пустые функции записываются своими именами, идентификаторы предваряются знаком #. Скобки вызова на уровне синтаксиса трактуются также, как и круглые — внутри них может быть что угодно. И это даёт дополнительную гибкость — можно косвенно вызывать функцию синтаксисом <s.Func e.Arg>, можно даже возвращать функцию из функции <<MakeFn …> …> (хотя последним не помню, чтобы пользовался). Ну, и, конечно, упрощается синтаксический анализ ценой проверки на уровне рантайма.

Понятно, что в синтаксисе Рефала-05 останется что-то одно, а значит, знак # больше не потребуется.

Если оставить идентификаторы, то синтаксис угловых скобок усложнится. Можно будет, как в Рефале-5, хитрым образом сохранять указатель на функцию в самой скобке активации, но это усложнит внутреннее представление (минималистичность нужна и на уровне понимания). Для сравнения идентификаторов на равенство потребуется или использовать strcmp, или поддерживать хеш-таблицу для обеспечения единственности указателей. Возникнет соблазн реализовать Implode со всеми её недостатками. Поскольку в перспективе предполагается Си89, а значит, фокус с шаблонами не перенесётся. Но при этом не потребуются $ENUM’ы. Единственным способом косвенного вызова останется функция Mu, но обеспечить её межмодульную работу будет гораздо сложнее, если вообще возможно. Можно поступить в духе Рефала-7, навешивая на идентификаторы указатели на функции, но он тоже плох.

Если оставить указатели на функции, скобки вызова останутся простыми, но потребуется сложный синтаксис $ENUM/$EENUM. На самом деле несложный, ведь в языке уже есть $EXTERN. Сохранится возня с парами $EENUM/$EXTERN — где определить, а где экспортировать символ. Сохранится простое сравнение на равенство по указателю. Сохранится вся мощь косвенных вызовов.

Почему плох подход Рефала-7 (и, вроде, Рефала-2). Если идентификаторы одновременно являются указателями на функции, то сам указатель становится невидимым. Пример.

* файл 1.ref

$ENTRY MakeA { = A }

A { = <Prout 1> }

* файл 2.ref
$EXTERN MakeA;

A { = <Prout 2> }

$ENTRY Go {
  = <Call <MakeA> A>;
}

Call {
  e.1 s.X s.X = <s.X>;
}

Какой экземпляр будет вызван в Call — из 1.ref или 2.ref? С явными указателями или простыми идентификаторами и Mu неоднозначности бы не было.

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

Эта задача — подзадача #12, косвенно относится также к #1.

Цель — совместимость с Рефалом-5 (#2), исходники компилятора должны собираться при помощи Рефала-5. Кроме того, минималистичность (#1).

Сортировка предобъявлений в алфавитном порядке — чисто декоративная возможность, которая снаружи никому не видна. Вернее, видна только мне, когда я обновляю папку bootstrap. И ради своего чувства прекрасного я делал эту сортировку. Из соображений минимализма функция избыточна и подлежит устранению.

Функция Sort использует функцию Compare для определения отношения между термами. Функция Compare использует нативную функцию SymbCompare, которая умеет сравнивать символы. Аналога функции SymbCompare в Рефале-5 нету.

Функции Compare и SymbCompare сравнивают два терма (символа) и возвращают отношение между ними: '<', '=', '>'.

Реализовывать SymbCompare средствами Рефала-5 громоздко, что противоречит #1.

В Рефале-5 есть встроенная функция Compare, которая сравнивает два числа и возвращает знак разности между ними: '−', '0', '+'. Очевидный конфликт, который разрешается согласно #12 — заменить унаследованную из Простого Рефала функцию на функцию Рефала-5.

На данный момент функция Compare используется в Escape.ref, где её несложно заменить на Compare Рефала-5.

Таким образом:

• не сортируем предобъявления,
• удаляем универсальную функцию Sort, а также Compare-T,
• переделываем функцию Compare во встроенную функцию Рефала-5 (пока как обёртку над SymbCompare),
• реализуем Compare как нативную, SymbCompare выбрасываем.

Эта задача — подзадача #33.

В противоположность задаче #11 предлагается удалить нативные вставки. Обоснование — в задаче #33.

Что надо сделать:

• создать в рантайме макросы DEFINE_LOCAL_ENUM(name), DEFINE_ENTRY_ENUM(name) для определения пустых функций,
• создать макросы DECLARE_LOCAL_FUNCTION(name), DECLARE_ENTRY_FUNCTION(name) для объявления внешних функций и ссылок вперёд для локальных,
• создать макросы DEFINE_LOCAL_FUNCTION(name), DEFINE_ENTRY_FUNCTION(name) для определения заголовка функции,
• использовать каждый из этих макросов в кодогенераторе,
• переделать Library.ref в Library.c,
• удалить поддержку нативных вставок в компиляторе.

Замечание по макросам DEFINE_…_FUNCTION(name). Их использование:

DEFINE_LOCAL_FUNCTION(Foo) {
  ...
}

DEFINE_ENTRY_FUNCTION(Bar) {
  ...
}

Они раскрываются в

static r05c_Foo(struct r05_node *arg_begin, struct r05_node *arg_end);
static r05_function r05f_Foo = { r05c_Foo, "Foo" };
static r05c_Foo(struct r05_node *arg_begin, struct r05_node *arg_end) {
  ...
}

static r05c_Bar(struct r05_node *arg_begin, struct r05_node *arg_end);
r05_function r05f_Bar = { r05c_Bar, "Bar" };
static r05c_Bar(struct r05_node *arg_begin, struct r05_node *arg_end) {
  ...
}

Очевидно, их легко использовать и в самописном коде.

Для файла, который во вложении, неправильно выводится результат профилирования.

C:\…>echo 5|lambda.exe
Enter a number:
120

Total program time: 220.528 seconds (100.0 %).
(Total refal time): 220.308 seconds (99.9 %).
Linear result time: 219.789 seconds (99.7 %).
t- and e-var copy time: 219.203 seconds (99.4 %).
Linear pattern time: 0.519 seconds (0.2 %).
Builtin time: 0.220 seconds (0.1 %).
Step count 1903576
Memory used 1969848 nodes, 1969848 * 16 = 31517568 bytes

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

C:\…>echo 5|lambda.exe
Enter a number:
120

Total program time: 327.484 seconds (100.0 %).
(Total refal time): 326.922 seconds (99.8 %).
t- and e-var copy time: 324.539 seconds (99.1 %).
Linear result time: 1.462 seconds (0.4 %).
Linear pattern time: 0.921 seconds (0.3 %).
Native time: 0.282 seconds (0.1 %).
Runtime time overhead: 0.280 seconds (0.1 %).
Identifiers allocated: 101
Step count 3197998
Memory used 1969846 nodes, 1969846 * 16 = 31517536 bytes

Приложенный файл

• lambda.ref

Преамбула

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

Если в программу добавить псевдокомментарии *$ENUM/*$EENUM и дополнительные $EXTERN’ы, то класс допустимых программ можно расширить практически до базисного подмножества Рефала-5 (с исключениями для несовместимого использования Mu). И это всё.

Но у нас есть препроцессор, которым можно преобразовывать программы на полном Рефале-05 к его базисному подмножеству: 5-to-basis. И он умеет сохранять псевдокомментарии. С его помощью можно расширить класс программ, к которым применим Рефал-05.

Задача

Задача состоит в том, чтобы при помощи 5-to-basis и дополнительной разметки псевдокомментариями собрать некоторые сторонние программы, при необходимости расширить набор встроенных функций. Некоторые встроенные функции добавить не получится в принципе, прежде всего, это Implode.

Предлагается перенести следующие программы:

• Собственно, 5-to-basis. С ней не должно быть больших трудностей. В её репозитории уже создана заявка Mazdaywik/refal-5-framework#3 (#37).

• Модульный Рефал, скомпилированный в Рефал-5.

  Модульный Рефал поддерживает только базисное подмножество, соответственно, компилируется в базисное подмножество Рефала-5 (в том числе).

  Проблемы могут возникнуть с функциями, описанными при помощи нативных вставок, в них могут быть условия и блоки. Тут два решения проблемы: либо сконвертировать при помощи 5-to-basis, либо переписать нативные вставки в исходниках.

  Возникнет проблема с идентификаторами, которые потребуется объявить как *$ENUM. Их можно добавить либо вручную (что дофига), либо автоматически, модифицировав back-end. Автоматический вариант проще.

  Другая проблема будет в том, что Модульный Рефал использует статические ящики → скомпилированный код использует копилку. Что с этим делать — пока не очевидно, придумаю в процессе. Может быть, добавлю копилку. (См. обновление #27)

• RMCC Скоробогатова. Тут без 5-to-basis не обойтись.

• Генератор случайных программ на Рефале А. П. Немытых. Опять, конвертируем при помощи 5-to-basis.

• Попробовать откомпилировать и запустить основной проход SCP4.

  На сколько я понял из исходников, функция Implode, которую невозможно добавить в Рефал-05, в SCP4 используется преимущественно во front-end’е (inref4 и mst), основная фаза преобразований её почти не использует. Однако, основная фаза использует Xxin (или Sysfun) для загрузки сериализованных объектных выражений, где неявно создаются новые идентификаторы. Что можно сделать?

  • Посмотреть, где используется Implode и как её можно обойти.
  • Для Xxin/Sysfun просто захардкодить некий константный граф для запуска тестового примера.

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

  Здесь, кстати, аналогичная проблема с копилкой. (См. обновление #27)

• Какие-нибудь ещё программы, которые мне попадутся.

Эта задача — подзадача для #2.

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

• Написанный вручную код меньше зависит от способа кодогенерации. Можно, например, изменять заголовки функций, заменять функции на дескрипторы и т.д., меняя только кодогенератор. Без нативных вставок придётся делать тупую однообразную замену по всему полотну Library.cpp.
• Повышается наглядность исходников.

Недостатки:

• Некоторое усложнение синтаксиса.
• Противоречие с минималистичностью.

Преимущества существенно перевешивают недостатки, поэтому надо реализовывать. Успешный опыт нативных вставок в Простом Рефале (Рефале-5λ) вынудил меня добавить их и в Модульный Рефал.

Максимально упростить и язык, и компилятор.

• Удалить интерпретируемый код. (#3)
• Удалить идентификаторы. (#4)
• Удалить статические ящики. (#5)
• Удалить вложенные функции. (#6)
• Удалить квадратные скобки. (#7)
• Переписать на C89. (#8)
• Переписать лексический анализ вручную, удалить lexgen. (#9)
• Читать конфигурацию из переменных окружения (#19)
• Удалить код переименования файлов (#20)
• Почистить библиотеку встроенных функций (#21)

Эта задача — подзадача #8.

Предлагается сделать также, как и в bmstu-iu9/refal-5-lambda#46. А именно, функцию представлять не в виде двух полей (указатель и строка) внутри структуры узла, а в виде глобальной переменной, хранящей те же указатель на функцию и её имя в виде строки.

Мотивация: устраняем костыль с return’ом и пустыми функциями (коммит: 86cde16).

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

// Automatically generated file. Don't edit!
#include "refalrts.h"


extern refalrts::FnResult Foo(refalrts::Iter arg_begin, refalrts::Iter arg_end);
static refalrts::FnResult Bar(refalrts::Iter arg_begin, refalrts::Iter arg_end);
static refalrts::FnResult Baz(refalrts::Iter arg_begin, refalrts::Iter arg_end);

refalrts::FnResult Foo(refalrts::Iter arg_begin, refalrts::Iter arg_end) {
  …
}

static refalrts::FnResult Bar(refalrts::Iter arg_begin, refalrts::Iter arg_end) {
  …
}

static refalrts::FnResult Baz(refalrts::Iter arg_begin, refalrts::Iter arg_end) {
  …
}


//End of file

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

Эта задача — подзадача #33.

Мотивация

С условиями и блоками проще программировать. Добавить их в back-end и рантайм технически не сложно.

Реализация

Компиляция условий

Рассмотрим компиляцию условия:

P, R1 : P1 = R;

В этом случае псевдокод предложения будет иметь вид:

do {
  〈объявления переменных〉
  〈сопоставление с <F P>〉
  〈построение <F$1 R1> перед закрывающей угловой скобкой〉
  〈рекурсивный вызов рефал-машины〉
  do {
    〈сопоставление с <F$1 P1>〉
    〈построение R〉
    return;
  } while (0);
  〈удаление <F$1 …>〉
} while (0);

Здесь я намеренно написал не 〈сопоставление с P〉, а 〈сопоставление с <F P>〉, дабы подчеркнуть, что первой операцией выделяется аргумент из диапазона [arg_begin, arg_end]. Аналогичное действие применяется к сопоставлению с образцом условия.

Функция F$1, будучи вызванной, прерывает цикл работы рефал-машины.

Компиляция блоков

Рассмотрим блок:

P
  , R
  : {
      P1 = R1;
      P2 = R2;
    };

Псевдокод предложения:

do {
  〈объявления переменных〉
  〈сопоставление с <F P>)
  〈построение <F$1 R> перед закрывающей угловой скобкой〉
  〈рекурсивный вызов рефал-машины〉
  do {
    〈сопоставление с <F$1 P1>〉
    〈построение R1〉
    return;
  } while (0);

  do {
    〈сопоставление с <F$1 P2>〉
    〈построение R2〉
    return;
  } while (0);
  r05_recognition_impossible();
} while (0);

Выводы

Изменения рантайма минимальные — нужна функция для рекурсивного вызова рефал-машины и тело для функций F$1. На этапе кодогенерации потребуется некоторое количество работы. На этапе синтаксического анализа делать ничего не надо — см. #34.

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

• Чем этот язык отличается от Рефала-5.
• Каково его общее подмножество с Рефалом-5.
• Какие поддерживаются встроенные функции.
• Как пользоваться компилятором.
• Как устроен этот компилятор.
• Как писать нативные функции: внутренние структуры данных, интерфейс с языком Си.
• Приблизительное устройство рантайма.

Эта задача — подзадача для #2.

В рамках данной задачи необходимо реализовать встроенные функции Рефала-5 в том объёме, которого достаточно для самоприменения. Дублирующие старые функции Простого Рефала следует безжалостно удалять. И скорее всего, под нож бритву Оккама пойдёт вся библиотека Простого Рефала кроме функций арифметики.

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

Должны быть доступны все встроенные функции, поддерживаемые версией PZ Oct 29 2004, большинство из них допустимо реализовать как $EENUM.

Полный список и тонкости семантики встроенных функций описаны в bmstu-iu9/refal-5-lambda#102.

Эта задача — подзадача для #1.

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

Это немного упростит загрузку конфигурации.

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

Строки в R05PATH будут разделяться знаком ; независимо от платформы. Потому что организовывать платформенно-зависимый код громоздко, идёт в разрез с требованием минималистичности.

Эта задача — подзадача для #33 и #28, блокирует #34.

Тонкое отличие от задачи Mazdaywik/refal-5-framework#3: задача в том репозитории посвящена адаптации того репозитория к Рефалу-05, задача в этом репозитории — адаптация Рефала-05 к проекту 5-to-basis.

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

Эта задача — подзадача для #1.

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

• Интерпретируемый код (работа Сухарева/Дрогунова) на рассматриваемом этапе развития Простого Рефала представляет собой константный массив внутри функции на Си++.
• Код прямой кодогенерации — просто код на Си++.

Если отказываться от кода прямой кодогенерации, то генерация Си++ всё равно останется (с константными массивами). Придётся переходить к файлам байткода и к отдельному интерпретатору (как это сделано, например, в Рефале-5 или Рефале-5λ). Это снизит гибкость: чтобы добавить новую функцию, нужно будет менять кодогенератор, парсер байткода и интпретатор вместо кодогенератора и рантайма. Это лишит удобного интерфейса с языком Си/Си++ (подход Рефала-5λ совсем не минималистичен).

Поэтому предлагается отказаться от интерпретации. Простой Рефал, генерирующий код на Си++, концептуально закончен, а интерпретация «прицеплена сбоку».

Более того, частично код интерпретации уже удалён — история проекта была переписана, коммиты Игоря Дрогунова и связанные с ними мои коммиты просто туда не попали. Значит, достаточно удалить код Вадима Сухарева, которого сравнительно немного.

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

Эта задача — подзадача #8.

Предлагается по возможности не использовать typedef’ы. Например, struct r05_Node* вместо refalrts::Iter. Исключение — типы указателей на функции.

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

• r05_ — для всех сущностей рантайма: r05_Node, r05_alloc_char, r05_cDataNumber. Заменяет refalrts::.
• r05f_ — для дескрипторов функций. Дескрипторы функций могут быть как статическими, так и со внешней компоновкой.
• r05c_ — для самих функций (кода). Эти функции могут быть только статическими.

Пример:

static r05_FnResult r05c_Foo(struct r05_Node *arg_begin, struct r05_Node *arg_end);
r05_Function r05f_Foo = { r05c_Foo, "Foo" };

static r05_FnResult r05c_Foo(struct r05_Node *arg_begin, struct r05_Node *arg_end) {
  . . .
}

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

$ENTRY Go { = }

Bar { = Bar }

C:\…\Refal-05\src\cfiles>..\..\bin\refal05c.exe test.ref refal05rts Library
*Compiling test.ref:
+Linking C:\…\Refal-05\lib/refal05rts.c
*Compiling C:\…\Refal-05\lib/Library.ref:
Borland C++ 5.5.1 for Win32 Copyright (c) 1993, 2000 Borland
test.c:
c:\…\refal-05\lib/refal05rts.c:
c:\…\refal-05\lib/library.c:
Turbo Incremental Link 5.00 Copyright (c) 1997, 2000 Borland
*** Compilation successed ***

Total program time: 0.640 seconds (100.0 %).
Builtin time: 0.624 seconds (97.5 %).
Linear pattern time: 0.016 seconds (2.5 %).
(Total refal time): 0.016 seconds (2.5 %).
Step count 67876
Memory used 33634 nodes, 33634 * 16 = 538144 bytes

К слову, на рекурсивные статические функции не ругается и BCC 5.5.

Надо выдавать ошибку.

Эта задача — подзадача #33.

После того, как 5-to-basis станет фреймворком (Mazdaywik/refal-5-framework#5), нужно будет заменить front-end Рефала-05 на front-end из фреймворка.

Поскольку back-end не поддерживает условий и блоков, то на первое время будет использоваться проход трансформации к базисному подмножеству из фреймворка. Проблем с раскруткой не будет, поскольку раскручивается он классическим Рефалом-5.

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

Если многострочный комментарий содержит внутри /*, то следует выдавать ошибку. Поскольку это, скорее всего, ошибка пользователя — он закомментировал кусок, уже содержащий комментарий.

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

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

Эта задача — подзадача для #1 и #2.

Во-первых, лексику придётся менять — однострочные комментарии будут как в Рефале-5, появятся псевдокомментарии (см. #2).

Во-вторых, используемый генератор лексических анализаторов был экспериментом — мне было интересно попробовать написать генератор из некоторого высокоуровневого описания.

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

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

После переписывания лексического анализатора исходники LexGen можно удалить. Генератор LexGen лежит и развивается в репозитории Рефала-5λ, здесь его более старый дубль не нужен. (Кстати, та же судьба ждёт и SRMake.)

Эта задача предваряет #4, #6, #7, косвенно #1.

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

Эта задача — подзадача для #8.

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

Преимущества:

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

Недостатков явных не видно.

Как и раньше, выполнение предложения состоит из трёх фаз:

1. сопоставление с образцом,
2. распределение памяти,
3. построение результата.

Фазы и их инварианты сохраняются.

Эта задача — подзадача для #2.

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

Компилятор написан на подмножестве Рефала-5, а значит, может быть собран как официальной реализацией Рефала-5 (PZ Oct 29 2004), так и любой совместимой, например, Рефалом-5λ.

Но скрипты раскрутки (bootstrap.*) и самоприменения (src/makeself.*) поддерживают раскрутку только классической реализацией.

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

Вынесено из комментария #33 (comment).

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

Костыли в ней, например, в необходимости запоминать диапазоны при сопоставлениях с открытыми переменными.

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

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

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

Тоже самое предполагается в дальнейшем сделать и в Рефале-5λ — bmstu-iu9/refal-5-lambda#204.

Этапы

• Реализовать новую кодогенерацию сопоставления с образцом.
• Задокументировать (#39).

Эта задача — подзадача для #1.

Простой Рефал, особенно его ранние версии, компилируется в C++, однако C++ почти не использует. Поэтому из соображений минимализма следует перейти на подмножество — на C.

Язык Си более переносим: скорее всего придётся обходить меньше ошибок в Watcom, существуют компиляторы C, которые не поддерживают C++ (например, Tiny C, PCC).

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

В Простом Рефале C++ был необходим для простой реализации идентификаторов. Благодаря трюку с шаблонами компоновщик C++ устранял дубликаты, обеспечивая тем самым глобальность указателей. В Рефале-5λ C++ обеспечивает инициализацию глобальных переменных в нативных файлах и упрощает написание рантайма (без STL и RAII написать динамическую загрузку было бы сложнее). На чистый C переписать можно, но пока такой цели не стоит.

В Рефале-05 идентификаторов не будет (#4), для глобальных переменных будет достаточно только статической инициализации. Поэтому технически C++ не нужен. Идеологическое обоснование ненужности дано выше.

Подзадачи:

• Дескрипторы функций (#14)
• Стилевые особенности рантайма и генерируемого кода (#15)
• Функции Рефала — безотказные (#16)
• Генерация результатного выражения (#17)

Цель

Должна быть возможность писать программы, которые будут корректны и с точки зрения Рефала-05, и классического Рефала-5, т.е. у обоих языков должно быть общее подмножество. И это подмножество должно быть достаточно выразительно для того, чтобы на нём написать компилятор.

Эскиз языка Рефал-05

Язык в первом приближении выглядит так:

• Синтаксис как у Рефала-5 или Простого Рефала — фигурные скобки, имена переменных через точку. Т.е. не как у Рефала-2.
• Базисный Рефал — предложения состоят только из образца и результата.
• Типы символов как в раннем Простом Рефале — литеры, числа и имена глобальных функций.
• Пустые функции задаются псевдокомментариями *$ENUM/*$EENUM, что обеспечит совместимость с Рефалом-5.
• Поддерживается подмножество встроенных функций Рефала-5, достаточное для самоприменения.
• Есть нативные вставки. Они идут в разрез с минималистичностью, но упрощают разработку библиотеки.

Общее подмножество

• Имена enum’ов будем называть именами-идентификаторами. Имя-идентификатор должно либо создаваться и потребляться только в одной единице трансляции (и тогда объявлено как *$ENUM), или объявлено как *$EENUM и во всех остальных единицах объявлено как $EXTERN.
• Косвенный вызов функций осуществляется только через Mu.
• Для передачи функции для косвенного вызова из другой единицы трансляции её надо определить как entry. Поскольку функция Mu Рефала-5 умеет вызывать entry-функции из других единиц трансляции.

Подзадачи

• Разработка и уточнение синтаксиса языка. (в комментариях)
• Реализация нового лексического анализатора. (#9)
• Реализация нативных вставок. (#11)
• Реализация библиотеки встроенных функций Рефала-5. (#12)

(Дамп потока сознания.)

Декларированные цели

Недавно я задумался: в Рефал-05 сравнительно несложно внедрить условия и блоки (upd: #35). Для этого потребуются совсем минимальные изменения рантайма (рекурсивный вызов рефал-машины и псевдофункции FuncName$n) плюс некоторое количество кода на Рефале (парсер, дерево, генератор). Т.е. технически проблем никаких нет. Но есть идеологические проблемы — противоречие целям, заявленным в README и документации.

Я затрудняюсь сказать, останется ли в этом случае Рефал-05 минималистичным. Возможно, останется, возможно, нет, нужно смотреть, на сколько объём кода увеличится.

Но в любом случае пришлось задуматься над целями и пересмотреть их. Исходно цели декларировались так:

Рефал-05 — минималистичный самоприменимый компилятор минималистичного
диалекта Рефала, имеющий общее подмножество с классическим Рефалом-5.
На этом подмножестве он и написан.

Но получился язык, в котором в отличие от Рефала-5, идентификаторы являются именами функций (отсюда костыль с псевдокомментариями и $ENUM) и есть синтаксис для нативных вставок. Обе вещи несколько противоречат минималистичности…

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

Критика концепции

Получился язык, не полностью минималистичный, но частично совместимый с Рефалом-5. Важнейшие отличия от Рефала-5

• Вместо символов-слов символы-функции (что лишает пользователя составных символов в двойных кавычках).
• Объявления пустых функций в псевдокомментариях *$ENUM и *$EENUM. Без псевдокомментариев исходники невозможно было бы собрать Рефалом-5.
• Нативные вставки.

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

Можно было бы генерировать интерпретируемый код по диссертации Романенко, код прозрачен, компактен и эффективен. Тогда бы «встроенные функции» пришлось бы делать встроенными. Расширяемости не было. Но при этом получилось бы подмножество Рефала-5. Точное подмножество без геморроя с объявлением пустых функций.

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

Можно было бы оставить C++ и трюк с генерацией идентификаторов.

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

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

...
struct Ident **idents_table = NULL;
const char *ident_names = "True\0False\0Success\0Fails\0\0";

...
void r05f_funcname(…) {
  if (idents_table == 0) {
    idents_table = r05_init_idents_table(ident_names);
  }
  ...
  /* ссылка на Success */
  ... idents_table[2] ...
  ...
}
...

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

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

Сделать Простой Рефал совместимым с Рефалом-5, эффективным и компилирующимся в Си.

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

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

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

Чтобы программу на Рефале-5 можно было откомпилировать Рефалом-05, нужно, чтобы в ней не было копилки (она выкинута), не было символов-слов в двойных кавычках, остальные символы-слова были именами функций в текущей области видимости, в ней не использовались условия и блоки (для этого её можно пропустить через 5-to-basis). Слишком много возни.

Отсюда следует и ненужность фреймворка-компилятора. Инструментальные средства, разрабатываемые на нём, будут столь же бесполезны.

Кроме того, наличие нативных вставок затрудняет реализацию инструментальных средств. Один из подпунктов в #27 гласит:

• Альтернативный компилятор — объединяет все файлы без нативных вставок в один файл с необходимым переименованием локальных функций.

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

Нативные вставки безусловно удобны при изменениях представления данных, например, при описаниях функций через дескрипторы. Пример такого изменения — #14, 5dc0c8e — в коммите не менялись объявления функций, см. также и Library.sref в bmstu-iu9/refal-5-lambda@6f1a366. Но того же эффекта можно было достичь и аккуратным использованием макросов.

Нативные вставки позволяют смешивать в исходном файле код на Рефале и код на целевом языке, но это преимущество немного сомнительно. Оно было актуально раньше в Простом Рефале/Рефале-5λ, поскольку позволяло смешивать оба языка в Library.sref, сохраняя при этом единый файл. Сейчас это не так актуально и там (поскольку если уж рантайм рассыпался на кучу файлов, можно рассыпать и Library), и здесь (встроенные функции Рефала-05 несложно описать и на Си).

Что же делать?

Менять концепцию.

Хороший фреймворк для Рефала-5, безусловно, нужен (по моему мнению, prefal — плохой фреймворк). Фреймворк для странного языка Рефала-05 не нужен. Компилятор странного Рефала в Си пускай будет.

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

(Либо, вообще можно подумать о фреймворке на базе Рефала-5λ.)

Задачу #27 перенести в 5-to-basis и решить её там.

В Рефал-05 можно добавить условия и блоки, фронт-энд сделать общим с 5-to-basis. Соответственно, здесь останется только рантайм, кодогенератор и расширения парсера (разбор псевдокомментариев *$ENUM, проверка имён-идентификаторов).

Как унифицировать фронт-энд между обоими проектами — отдельный вопрос.

Из Рефала-05 выкинуть нативные вставки, Library.ref переписать на Си. В ней на Рефале написаны только Mu и ListOfBuiltin, их переписать на Си несложно. Можно добавить дополнительные встроенные функции для большей совместимости с классическим Рефалом-5.

5-to-basis видоизменить так, чтобы он мог компилироваться Рефалом-05.

Ревизия 2019-03-31 — подзадачи

• Удалить нативные вставки из языка (#36).
• Перенести задачу #27 в 5-to-basis (перенесена: Mazdaywik/refal-5-framework#4).
• Сделать 5-to-basis фреймворком (Mazdaywik/refal-5-framework#5).
• Заменить front-end на front-end фреймворка (#34).
• Реализовать в Рефале-05 условия и блоки (#35).
• Собрать 5-to-basis Рефалом-05. Сначала собрать после собственного самоприменения (на базисном подмножестве),… (#37, Mazdaywik/refal-5-framework#3)
• …а потом, реализовав условия и блоки, собрать напрямую.
• Подумать о нативной реализации копилки в Рефале-05 — это сделает его более совместимым с Рефалом-5.
• Переписать документацию (первую главу целиком, остальные актуализировать).
• Изменить семантику идентификаторов согласно #38.

В комментарий этот список выносить нельзя, поскольку тогда интерфейс GitHub его не увидит.

Эта задача — подзадача #8.

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

Обоснование: сложно представить себе ситуацию, когда эти ошибки корректно обрабатываются и продолжается выполнение. Функции, написанные на Рефале, могут только упасть.

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

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

• Подзадача для #33.

Проблема

На актуальной реализации Рефала-05 программировать неудобно и часто непросто переносить другие программы (см. #28). Причина — объявления *$ENUM’ов и *$EENUM’ов.

Причина появления пустых функций — (подразумеваемая) цель разработки, как она была описана в #33:

Сделать Простой Рефал совместимым с Рефалом-5, эффективным и компилирующимся в Си.

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

Как и в Простом Рефале и в Рефале-5λ, такая реализация допускала библиотечные функции высшего порядка (например, Map в LibraryEx), это тоже важный для меня критерий. Если функции Map не будет, то мне программировать на Рефале будет грустно.

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

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

Требуется лишь определить. На практике оказалось, что для MSCP-A потребовалось определить несколько десятков идентификаторов, я замучался их определять и так и не довёл дело до конца. SCP4 собирать Рефалом-05 я даже не пробовал. Кроме того, в программах на Рефале-5 часто используются функции Implode/Implode_Ext, мне эти функции не нравятся, но факт остаётся фактом. Чтобы запустить некоторые программы, их использующие, в #28 мне пришлось сооружать костыли.

Ради совместимости с Рефалом-05 мне пришлось фреймворк refal-5-framework засорить всеми этими *$EENUM’ами, что, в свете вышеизложенного, уродливо.

Предлагаемое решение

Предлагается вместо функций в роли имён использовать идентификаторы, сравниваемые по текстовому представлению. Их объявлять явным образом не надо (псевдокомментарии *$(E)NUM становятся комментариями и уходят в прошлое), одинаковые имена, записанные в разных единицах трансляции, являются равными.

Примитивнейший способ проверки на равенство — strcmp(), но тут возможны оптимизации (хотя интересно сделать замер и с одним strcmp() тоже).

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

$EXTERN Extern;

$ENTRY Entry {
  /* пусто */
    = Extern /* полезная нагрузка — ссылка на внешнюю функцию */
      Entry /* полезная нагрузка — ссылка на entry-функцию */
      Local /* полезная нагрузка — ссылка на локальную функцию */
      NoPayload /* нет функции NoPayload в области видимости, нет полезной нагрузки */
}

Local { … }

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

Функция Mu смотрит на полезную нагрузку и вызывает соответствующую функцию. В ненагруженные идентификаторы можно класть либо NULL, либо функцию, которая для любого аргумента выдаёт ошибку невозможности отождествления.

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

Историческое замечание

Подобная идея была предложена Скоробогатовым, он мне сообщил об этом в личной беседе много лет назад, когда он сам ещё разрабатывал Рефал-7 (в конце 2000-х — в начале 2010-х). В Рефале-7 предлагались именованные вложенные функции. Я спросил:

— А как сравниваются на равенство вложенные функции?
— По именам.
— А безымянные?
— Они вообще ничему не равны, даже сами себе.

Диалог не дословный, но суть передал насколько помню. Данный подход мне не понравился — в те годы Скоробогатов также планировал реализовать специализатор для Рефала-7, а тут с аксиоматикой равенства возникали существенные проблемы (например, что копия значения не равна себе). Вообще, с функциями высшего порядка, их равенством и глубокими трансформациями программ есть много сложностей — см., например, bmstu-iu9/refal-5-lambda#276.

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

Возможные оптимизации

Постоянно дёргать strcmp() для проверки на равенство может быть неэффективно (но надо померять!). Поэтому можно предложить следующие оптимизации.

• Тупо сначала проверять на равенство сами дескрипторы. Такая эвристика будет срабатывать, если они порождены в одном файле или сопоставляется с константой в образце порождённый в том же файле символ. Можно также хранить указатель на статическую переменную — в разных файлах переменные будут разными и адреса, соответственно, тоже. Если этот указатель равен, а сами дескрипторы разные, то заведомо не равны. Если не равен — надо уже сравнивать строковое представление.
• Лес не пересекающихся множеств. В эту эвристику слабо верится, т.к. не равны идентификаторы могут быть чаще, чем равны.
• Хранить в дескрипторе хэш имени. Хэш можно вычислять и во время компиляции, и во время выполнения. В первом случае придётся дублировать логику (т.к. хэш нужно считать будет, например, в Implode), во втором — потеря быстродействия. К тому же не все хэш-функции удобно описывать на Рефале. Если два хэша не равны, значит, заведомо не равны и сами символы. Если равны — надо сравнивать на точное равенство.
• Хэш имени и лес непересекающихся множеств можно сочетать, они нивелируют недостатки друг друга. Когда хэши равны, то с вероятностью 1 − 1/2¹⁶ будут равны и сами символы (см. «парадокс дней рождения»), лес непересекающихся множеств сразу выявит равенство. Равенство на strcpy() регулярно будет проверяться только если в программе более 2¹⁶ идентификаторов.
• Строить во время выполнения в библиотеке рантайма хэш-таблицу имён. Недостаток — накладные расходы во время выполнения.

Расширение семантики Mu

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

UPD: не нужно, #38 (comment).

Пример на несовместимость с Рефалом-5

Не смотря на то, что предложенная семантика стала ещё ближе к Рефалу-5, несовместимость остаётся всё равно. Пусть s.Func содержит имя некоторой entry-функции программы. Тогда <Mu s.Func …> в Рефале-5 вызовет эту функцию, если одноимённого имени не было в точке вызова, а в Рефале-05 — если при создании этого имени в области видимости было либо определение этой функции с $ENTRY, либо объявление с $EXTERN.

* file1.ref
$ENTRY A { = <Prout 'Aaaa!'> }
$EXTERN B;
$EXTERN C;

$ENTRY Get1 { = A B C }

* file2.ref
$EXTERN A;
$ENTRY B { = <Prout 'Bbbb!'> }

$ENTRY Get2 { = A B C }

Обе функции Get1 и Get2 вернут нагруженные идентификаторы A и B, однако только Get1 вернёт C как нагруженный. Get2 вернёт пустой.

* file3.ref

$ENTRY Go { = <Run <Get1>> <Run <Get2>> }

Run {
  s.F e.Fs = <Mu s.F> <Run e.Fs>;
  /* пусто */ = /* пусто */;
}

B { = <Prout 'BbBbB???'> }

$ENTRY C { = <Prout 'Ccccc!'> }

Эта программа на Рефале-5 напечатает

Aaaaa!
BbBbB???
Ccccc!
Aaaaa!
BbBbB???
Ccccc!

В Рефале-05 напечатает

Aaaaa!
Bbbbb!
Cccccc!
Aaaaa!
Bbbbb!

и аварийно упадёт из-за вызова ненагруженного идентификатора. Если же расширить Mu, как предложено выше, то получим

Aaaaa!
BbBbB???
Ccccc!
Aaaaa!
BbBbB???
‹RECOGNITION IMPOSSIBLE›

Преимущества

• ✔ Упрощается ввод типичной программы — не требуется вручную объявлять пустые функции, не надо заботиться о том, где они определены (там *$EENUM, тут *$EXTERN).
• ✔ Минимальные правки текущей реализации (до возможных оптимизаций, впрочем и они небольшие).
• ✔ Сохраняется раздельная трансляция.
• ✔ Сохраняется минималистичный дизайн.
• ✔ Естественная реализация Implode/Implode_Ext — просто создаются идентификаторы без нагрузки. Кроме, возможно, имён, совпадающих со встроенными функциями.
• ✔ На практике по моему мнению имеющаяся несовместимость не существенна.
• ✔ Из refal-5-framework можно будет удалить ненужные псевдокомментарии.

Недостатки

• ❌ Чувствительность к опечаткам — если ошибёмся в вводе имени, то молча будет создан ненагруженный идентификатор. Впрочем, та же проблема есть в Рефале-5.
• ❌ Равные символы могут быть семантически не эквивалентны:

  $ENTRY Test {
    s.A s.B, s.A s.B : s.Eq s.Eq = <Mu s.A> <Mu s.B>;
    s.A s.B = Neq;
  }
  

  Здесь в первом предложении могут быть вызваны разные одноимённые функции. На сколько это может привести к проблемам, мне не очевидно.
• ❌ Снижение быстродействия. Умозрительно оценить я не могу, надо мерять. Скорее всего, оно будет приемлемым на практике, особенно с предложенными оптимизациями.

Альтернативный путь

Чтобы обеспечить семантику Mu Рефала-5 с идентификаторами, можно пожертвовать раздельной трансляцией, как это предложено в bmstu-iu9/refal-5-lambda#324 и bmstu-iu9/refal-5-lambda#197. Однако, это выглядит слишком громоздким для Рефала-05.

Этапы

• Сделать наивное сравнение имён по strcmp(), оценить быстродействие.
• Оптимизировать его, если это необходимо.
• Изменить семантику имён — не требовать наличия определённой функции, вместо этого доопределять пустые функции.
• Удалить избыточные $EXTERN’ы для имён.
• Удалить поддержку псевдокомментариев (всех).
• Удалить псевдокомментарии из фреймворка (за ненадобностью).
• Задокументировать новый синтаксис (#39).

Эта задача — подзадача #1.

Когда компилятор замечает среди выходных файлов файлы с одинаковыми именами (без учёта регистра), он к ним добавляет суффиксы @1, @2 и т.д. Т.е., например, если компилируются файлы BE-CppSR/MLinker.ref** и BE-SimRef/MLinker.ref, то будут построены целевые файлы BE-CppSR/MLinker.c и BE-SimRef/[email protected] — ко второму имени будет добавлена собака с номером.

Зачем? Некоторые компиляторы для Windows (BCC, MS VC) создают объектные файлы в текущей папке. Поэтому, если компилировать предыдущий набор файлов без переименования, получатся два файла MLinker.c в разных папках, каждый из них откомпилируется в файл MLinker.obj в текущей папке и один перезатрёт другой. Для обхода этой проблемы и был добавлен код переименования.

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

Откуда взялся этот код? Проблема всплыла, когда компилятор Простого Рефала стал использоваться как back-end Модульного Рефала, а в исходниках последнего были одноимённые файлы. Например, те же BE-CppSR/MLinker.mref и BE-SimRef/MLinker.mref. Решением оказалось добавить костыль в Простой Рефал (хотя тот же костыль есть и в Модульном Рефале для компиляции непосредственно в C++).

Почему предлагается это удалить.

• Это избыточная по смыслу логика — не имеет прямого отношения к решаемой задаче — компиляции Рефала в императивный код.
• Рефал-05 не предназначается как back-end Модульного Рефала. Даже если я его и сделаю back-end’ом, то это уже будет проблемой Модульного Рефала то есть.
• Даже компилятор Microsoft Visual C++ позволяет себе закрыть глаза на этот нюанс, почему я с этим должен бороться?
• Функция Lower стандартной библиотеки используется только здесь. После удаления кода переименования её можно выкинуть (и функцию Upper, добавленную для симметрии — тоже). Эти функции при желании можно написать и на Рефале (так когда-то и было), поэтому как примитивы избыточны.

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

От рекурсивного спуска остаётся принцип «одно правило — одна функция», от переноса-свёртки — накопление на стеке символов до ближайшей свёртки.

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

Грамматика должна описываться в духе ПС-парсеров, в частности, с левой рекурсией. Например,

E → T | E + T | E − T

Каждая функция, соответствующая нетерминалу, имеет формат

<NTerm e.Stack t.Token* e.Context>
  == e.Stack t.Token* e.Context
e.Stack ::= t.Token | t.NTerm
t.Token ::= (s.TokType t.SrcPos e.Info)
t.NTerm ::= (s.NTermType e.Info)

Здесь e.Stack — часть уже распознанного правила, t.Token* — нераспознанная последовательность токенов, e.Context — глобальная информация — таблица символов, список ошибок и т.д.

Для каждого правила NTerm → X1 X2 … Xn строятся n предложений, где e.Stack соответствует уже распознанным частям правила, перечисляются они в порядке убывания длины. Если в некотором правиле следующим предполагается нетерминал NTerm′, то рекурсивно вызывается <NTerm′ e.Tokens…> для остатка. Т.е. выглядит это примерно так:

/* Expr → Term | Expr + Term | Expr − Term */
Expr {
  /* Expr → Expr BinOp Term */
  (Expr s.EVal) (BinOp s.BinOp) (Term s.TVal) e.Tokens t.SymTable t.ErrorList =
     /* свёртка */
    <Expr (Expr <Mu s.BinOp s.EVal s.TVal>) e.Tokens t.SymTable t.ErrorList>;

  /* Expr → Expr BinOp … */
  (Expr s.EVal) (BinOp s.BinOp) e.Tokens t.SymTable t.ErrorList =
     /* рекурсивный разбор терма */
     <Expr (Expr s.EVal) (BinOp s.BinOp) <Term e.Tokens t.SymTable t.ErrorList>>;

  /* Expr → Expr + … */
  (Expr s.EVal) ('+' t.SrcPos) e.Tokens t.SymTable t.ErrorList =
    <Expr (Expr s.EVal) (BinOp Add) e.Tokens t.SymTable t.ErrorList>;

  /* Expr → Expr − … */
  (Expr s.EVal) ('-' t.SrcPos) e.Tokens t.SymTable t.ErrorList =
    <Expr (Expr s.EVal) (BinOp Sub) e.Tokens t.SymTable t.ErrorList>;

  /* Expr → Expr … */
  (Expr e.Expr) e.Tokens t.SymTable t.ErrorList =
     /* возврат, дальше не знак операции */
     (Expr e.Expr) e.Tokens t.SymTable t.ErrorList;

  /* Expr → Term … */
  (Term s.Val) e.Tokens t.SymTable t.ErrorList =
    <Expr (Expr s.Val) e.Tokens t.SymTable t.ErrorList>;

  /* Expr → … */
  e.Tokens t.SymTable t.ErrorList =
    <Expr <Term e.Tokens t.SymTable t.ErrorList>>;
}

/* Term → Prim | Term * Prim | Term / Prim | Term % Prim */
Term { … }

/* Prim → NUMBER | VAR | (AssignExpr) */
Prim {
  (NUMBER t.SrcPos s.Value) e.Tokens t.SymTable t.ErrorList =
    (Prim s.Value) e.Tokens t.SymTable t.ErrorList;

  (VAR t.SrcPos e.Name) e.Tokens (e.Vars-B (e.Name s.Value) e.Vars-E) t.ErrorList =
    (Prim s.Value) e.Tokens (e.Vars-B (e.Name s.Value) e.Vars-E) t.ErrorList;

  (VAR t.SrcPos e.Name) e.Tokens t.SymTable t.ErrorList =
    (Prim 0) e.Tokens t.SymTable
    <AddError t.ErrorList t.SrcPos 'Undefined variable ' e.Name>;

  ('(' t.OpenSrcPos) (AssignExpr s.Value) (')' t.CloseSrcPos) e.Tokens t.SymTable t.ErrorList =
    (Prim s.Value) e.Tokens t.SymTable t.ErrorList;

  ('(' t.OpenSrcPos) (AssignExpr s.Value) t.Unexpected e.Tokens t.SymTable t.ErrorList =
    (Prim s.Value) t.Unexpected e.Tokens t.SymTable
    <AddUnexpected t.ErrorList t.Unexpected '")"'>;

  ('(' t.SrcPos) e.Tokens t.SymTable t.ErrorList =
    <Prim ('(' t.SrcPos) <AssignExpr e.Tokens t.SymTable t.ErrorList>>;

  t.Unexpected e.Tokens t.SymTable t.ErrorList =
    (Prim 0) t.Unexpected e.Tokens t.SymTable
    <AddUnexpected t.ErrorList t.Unexpected 'Primary expression'>;
}

/* AssignExpr → Expr | VAR = AssignExpr */
AssignExpr {
  (VAR t.VarSrcPos e.Name) ('=' t.EqSrcPos) (AssignExpr s.Value) e.Tokens
  t.SymTable t.ErrorList =
    <AssignExpr
      (AssignExpr s.Value) e.Tokens <UpdateTable t.SymTable e.Name s.Value> t.ErrorList
    >;

  (VAR t.VarSrcPos e.Name) ('=' t.EqSrcPos) e.Tokens t.SymTable t.ErrorList =
    <AssignExpr
      (VAR t.VarSrcPos e.Name) ('=' t.EqSrcPos) <AssignExpr e.Tokens t.SymTable t.ErrorList>
    >;

  (Expr s.Value) e.Tokens t.SymTable t.ErrorList =
    (AssignExpr s.Value) e.Tokens t.SymTable t.ErrorList;

  e.Tokens t.SymTable t.ErrorList =
    <AssignExpr <Expr e.Tokens t.SymTable t.ErrorList>>;
}

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

В таком стиле нужно переписать парсер, дабы понять, на сколько на практике такой стиль действительно удобен.

Если исходный код станет после этого яснее и прозрачнее, то изменения следует влить в master. Иначе, коммиты нужно подвесить под меткой shift-reduce-29.

Эта задача — подзадача для #1 и #2.

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

Рефал-05 не предполагается в роли back-end’а Модульного Рефала, не предполагается быть языком для больших программных систем. Поэтому они не нужны.

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

Эта задача — подзадача для #1, связана с задачей #12.

Предлагается сделать две вещи:

• Удалить нереализованные функции (их объявления как $EENUM и строки в ListOfBuiltin).
• Рассмотреть удаление функций, не используемых в самом компиляторе.

Удалить нереализованные функции

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

Поэтому из соображений минимализма от них следует отказаться.

Рассмотреть удаление неиспользуемых функций

Именно рассмотреть. В компиляторе, например, не используется функция Card, поскольку программа не интерактивная. Но Рефал без чтения перфокарт — не Рефал, нельзя так.

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

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

Эта задача — подзадача #1 и #2.

Вложенные функции в Простом Рефале — это эксперимент, навеянный Рефалом-7. Я узнал об этом диалекте и добавил их ради процесса добавления. Тогда я мыслил Простой Рефал исключительно тестовым полигоном (не полигоном предполагался Модульный Рефал), поэтому решил потренироваться «на кошках». Но они прижились, с ними оказалось программировать удобнее, чем на чистом базисном Рефале.

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