Смена (уточнение) концепции

[Mazdaywik]

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

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

Недавно я задумался: в Рефал-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, 5dc0c8e65b79c476dcc9bd2fb5c29c94b6c8d0a2 — в коммите не менялись объявления функций, см. также и Library.sref в bmstu-iu9/refal-5-lambda@6f1a36670f903443577f37e9c27262e76cf1341b. Но того же эффекта можно было достичь и аккуратным использованием макросов.

Нативные вставки позволяют смешивать в исходном файле код на Рефале и код на целевом языке, но это преимущество немного сомнительно. Оно было актуально раньше в Простом Рефале/Рефале-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 — подзадачи

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

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

[Mazdaywik]

Согласно Mazdaywik/refal-5-framework#5, библиотечные файлы фреймворка должны находиться в переменной среды REF5RSL. Соответственно, Рефал-05 должен поддерживать поиск в этой переменной

[Mazdaywik]

Помимо неявно декларируемой цели

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

была и другая неявная цель:

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

Отсюда, кстати, и минимализм — чем меньше объём, тем проще изучить и понять, и хорошая подробная документация.

Т.е. это должен быть как Minix, но компилятор Рефала.

Среди целей, описанных в документации, понятность и прозрачность исходников (следствие «учебного пособия») обозначены как второстепенная цель и граничное условие:

https://github.com/Mazdaywik/Refal-05/blob/035ffcdcdebb7fd06ff8fb27e99b035892a94bf5/docs/1-intro.md?plain=1#L28-L34

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

[Mazdaywik]

Критикуя, предлагай

Старая концепция раскритикована, поставлены новые задачи, они, по большей части, выполнены, но новая цель (на которую направлены эти задачи) явно не артикулирована.

Попробуем её выявить, рассмотрев особенности актуального и предполагаемого (#35, #38) Рефала-05.

• Цели минималистичность, эффективность и компиляция в Си они константы, они не обсуждаются.
• Синтаксически Рефал-05 является подмножеством Рефала-5 — как неоднократно в этом репозитории написано, «любая синтаксически корректная программа на Рефале-05 является синтаксически корректной программой на Рефале-5». Исходно это было не так (были, например, «голые» $ENUM’ы вне псевдокомментариев), но теперь это так из-за использования refal-5-framework.
• Синтаксически Рефал-05 строже Рефала-5:
  • неиспользуемые функции и $EXTERN’ы являются синтаксической ошибкой,
  • избыточные $EXTERN’ы являются синтаксической ошибкой,
  • когда у Рефала-05 был свой лексер, комментарии вида /* … /* … */ тоже были синтаксической ошибкой.
• Процесс сближения с Рефалом-5:
  • Простой Рефал, взятый за основу, не был совместим с Рефалом-5. Единственная совместимая программа — $ENTRY Go { = ; }, т.к. библиотечные/встроенные функции ввода-вывода в обеих реализациях не пересекались.
  • Версии 1.0, 2.0, 3.0 обеспечивала лишь ту совместимость с Рефалом-5, которая требовалась для раскрутки самоприменимого компилятора Рефалом-5.
  • Разрабатываемая сейчас версия 4.0 уже использует front-end из refal-5-framework.
  • В рамках задачи #28 расширяется библиотека встроенных функций.
  • Задача #38 предполагает ещё большую близость с Рефалом-5 — уже не будут требоваться псевдокомментарии для имён, почти любая программа Рефала-5 будет без внесения изменений нормально работать с Рефалом-05 (где нет длинной арифметики и ограниченно используется Mu).
• Предлагается условия и блоки сделать нативными (#35).
• В описании вехи (https://github.com/Mazdaywik/Refal-05/milestone/4) говорится (на момент написания этого комментария):

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

• Высокие требования к генерируемому коду.
  • Текст генерируется хорошо отформатированный с отступами, хотя отступы несколько противоречат заявленной цели минимализма.
  • Компилятор Си не должен выдавать на сгенерированный код предупреждения. Отчасти ради этого парсер выдаёт ошибки на неиспользуемые функции. (Хотя, отсутствие предупреждений можно было бы обеспечить стиранием неиспользуемых функций.)
  • Не используются goto.
  • Код должен быть эффективным.
• Исходно, Рефал-05 должен быть прозрачен и хорошо документирован. Сейчас документация устарела, её надо переписывать. Исходники, по большей части, написаны на базисном Рефале, ради большей выразительности в них стоит использовать условия и блоки.

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

Таким образом, высока вероятность (после #38), что программа, написанная для Рефала-5, будет компилироваться Рефалом-05 и выполняться с тем же поведением без дополнительных правок, вроде добавления всяких '*$EENUM`’ов. Так что, можно говорить, что Рефал-05 — не только «совместим с Рефалом-5», но и является его альтернативной реализацией!

Неполностью совместимой альтернативной реализацией. А почему не полностью совместимой?

• На неиспользуемые объявления и определения компилятор ругается исключительно по моей прихоти. Можно переделать так, чтобы компилятор выдавал предупреждения или вообще молча удалял их из дерева.
• Аналогично и про избыточные $EXTERN’ы. Исторически нужна была проверка на избыточные *$E(E)NUM’ы, а $EXTERN’ы добавились заодно. Однако, crefal также ругается на избыточные $EXTERN’ы. refc ругается на избыточные $EXTERN’ы только в объявлениях вида $EXTERN F, F;. Так что это, скорее, не прихоть, а, наоборот, недоработка refc.
• Длинная арифметика, некоторые форматы встроенных функций (например, <Add (e.X) e.Y>) не реализованы из соображений минимализма.
• Другое поведение функции Mu (#38) объяснимо целевым языком Си и раздельной компиляцией. Раздельная компиляция реализована из соображений минимализма.

Отдельно остановлюсь на ошибках о неиспользуемых объявлениях и определениях. Конечно, можно их сделать и предупреждениями, и вообще убрать (заменив на молчаливое удаление таких узлов из синтаксического дерева). Но они полезны — и как воспитательная мера, и для упрощения рефакторинга (переписал код, компилятор напоминает удалить неиспользуемые). Кроме того, имена считаются используемыми (и будут считаться после #38!), если в тексте программы есть идентификатор с данным именем:

$ENTRY Go { = A С }

A { = } /* ✔ нет ошибки, используется в Go */
B { = } /* ❌ ошибка «Unused local function B» */
$EXTERN С; /* ✔ нет ошибки, используется в Go */
$EXTERD D; /* ❌ ошибка «Unused external declaration D» */

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

Например:

* файл main.ref

$EXTERN CallMu;

$ENTRY Go {
  = <CallMu F> <CallMu G>
}

$ENTRY F { = <Prout 'F in main.ref'> }

* файл callmu.ref

$ENTRY CallMu {
  s.F = <Mu s.F>
}

F { = <Prout 'F in callmu.ref'> }
G { = <Prout 'G in callmu.ref'> }

Эта программа, будучи откомпилированной и запущенной Рефалом-5, выдаст

F in callmu.ref
G in callmu.ref

Компилятор Рефала-05 выдаст ошибки на функции F и G в файле callmu.ref. Удалим их и снова откомпилируем и запустим Рефалом-5 (да, опять им):

F in main.ref
‹ошибка RECOGNITION IMPOSSIBLE›

Таким образом, в одном месте поведение изменилось (программа стала работать иначе), в другом и вовсе упала.

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

F in main.ref
‹ошибка RECOGNITION IMPOSSIBLE›

но это совпадение. Данная программа опирается на поведение функции Mu, разное в обоих реализациях.

Вообще, можно показать, что если

• программа на Рефале-5 работает правильно,
• компилятор Рефала-05 сообщает о неиспользуемых локальных функциях,
• при удалении этих локальных функций программа на Рефале-5 перестаёт работать правильно,

то эта программа не работала бы правильно на Рефале-05, если бы он такую программу компилировал бы молча.

Так что данное предупреждение я оставлю.

Предлагаю

Предлагаю определить Рефал-05 так:

Рефал-05 — альтернативная реализация Рефала-5, минималистичная, эффективная, прозрачная и компилируемая в Си. Реализация имеет отличия в семантике некоторых встроенных функций, сделанные ради минимализма и компиляции в Си.

[Mazdaywik]

Переписать сопоставления с образцом

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

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

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

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

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

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

---

P.S. Перенесено в отдельную заявку: #40.

[Mazdaywik]

Поведение на избыточные $EXTERN’ы

Планируемые изменения фреймворка

В рамках задачи Mazdaywik/refal-5-framework#9 предлагается реализовать проверку на избыточные $EXTERN’ы в самом фреймворке.

Предлагается сообщать об ошибке в случаях вида

$EXTERN F;

F { … } /* может быть и $ENTRY, не важно */

и выдавать предупреждения в случаях вида

$EXTERN F;

$EXTERN F;

$EXTERN Prout;

Однако, поддержка предупреждений пока не реализована (Mazdaywik/refal-5-framework#11), поэтому вместо предупреждений фреймворк будет выдавать ошибки (но позже — предупреждения).

Что делать в Рефале-05

Оставить как есть — избыточные $EXTERN’ы все ошибочны. Однако, в дальнейшем можно будет ожидать, что в корректном дереве от фреймворка не будут одновременно присутствовать и объявление, и определение некоторой функции, а значит, логику проверки соответствующей ошибки можно будет убрать. В случае же реализации предупреждений будет выдаваться и предупреждение на $EXTERN F, F; от фреймворка, и ошибка от Рефала-05.

[Mazdaywik]

• Синтаксически Рефал-05 строже Рефала-5:
  • неиспользуемые функции и $EXTERN’ы являются синтаксической ошибкой,
  • избыточные $EXTERN’ы являются синтаксической ошибкой,
  • когда у Рефала-05 был свой лексер, комментарии вида /* … /* … */ тоже были синтаксической ошибкой.

Это не следует из других явно заявленных целей, но при этом соблюдается. Значит, это самостоятельная цель. Назовём её педантичность. Рефал-05 педантичный — в нём некоторые стилистические ошибки считаются ошибками синтаксиса. Имеет смысл это направление расширить и углубить.

[STrusov]

была и другая неявная цель:

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

Спасибо. Именно благодаря Рефал-05 написал интерпретатор Рефала. При этом для меня, привыкшего к императивным языкам, наибольшую ценность представляли исходники на Си, как генерируемые, так и refal05rts.*.

[Mazdaywik]

Спасибо, @STrusov! Значит, Рефал-05 написан не зря!