Рефакторинг синтаксического дерева

[Mazdaywik]

Мотивация

Предлагается упростить синтаксическое дерево на выходе рассахаривания. Упрощение позволит писать более простой и лаконичный код. Писать (Symbol Identifier e.Name) или (TkVariable s.Mode e.Index s.Depth) слишком громоздко, тем более префикс Tk в слове TkVariable уже не имеет смысла на проходах после синтаксического анализа.

Многие из этих имён уже являют собой древнее легаси. Например, тот же префикс Tk в TkVariable и (Symbol Name e.Name) и (Symbol Identifier e.Name). Последнее сохранилось со времён Простого Рефала, когда исходно в нём не было идентификаторов, а были имена функций и для них было удобно писать TkName. Позже добавились идентификаторы, для которых был введён новый тип TkIdentifier. В ходе решения задачи #198 узлы (TkName e.Name) и (TkIdentifier e.Name) были механически переименованы в (Symbol Name …) и (Symbol Identifier …), я тогда даже не задумался дать им более подходящие имена.

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

Реализация

Изменения будут двух видов:

• переименования, сокращающие размер текста,
• изменения структуры.

Переименования узлов

• Symbol → Sym,
  • Symbol Identifier → Sym Word,
  • Symbol Name → Sym Func или Sym Ptr,
  • Symbol Number → Sym Num или Sym Number,
• Brackets → Parens,
• CallBrackets → Call,
• ADT-Brackets → ADT,
• ClosureBrackets → Closure,
• TkVariable → Var.

Изменения структуры

Узлы (Extern e.Names), (Entry e.Names), (Drive e.Names)…

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

Точно также удобно будет собрать все entry-функции в одну кучу. В этом случае можно отказаться от метки s.ScopeClass в дереве для самых разных элементов.

С метками Drive и Inline аналогично.

Удалить глубину у переменных

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

Новые имена можно назначать и более консервативным способом — функцией NewVarName. В этом случае поле s.Depth исчезнет изо всех образцов и результатов, что существенно упростит работу с деревом.

Удалить $SCOPEID

Про это отдельная задача #284. Сюда написал для полноты картины.

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

Образцы нужно будет представлять не как (e.Pattern), а как (L e.Pattern) или (R e.Pattern). Это изменение потребуется для задачи #175. Раз уж большой рефакторинг делается, то почему бы и не сделать это сейчас.

Координаты для предложений (?)

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

Во время рефакторинга можно добавить координаты в дерево до рассахаривания, чтобы сообщать о них при проверке. Но надо ли?

Представлять имена и индексы переменных как слова (?)

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

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

Дополнительные замечания

• Задача, хоть и ремесленная, не выносится на практику. Я планирую летом заняться задачами, связанными с древесными оптимизациями. Задача рефакторинга с ними не параллелится в принципе, а ждать, когда студент сделает рефакторинг и отладит, слишком долго.
• Задача #198 в некотором смысле является подзадачей настоящей задачи.

[Mazdaywik]

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

Решение: переименовывать сокрывающие переменные иначе. Например, добавлять им суффикс вида $〈буква〉. Знак $ в исходном коде недопустим, но DisplayName умеет его экранировать (для поддержки $table). s.Foo → s.Foo$a, s.Foo$b, …, e.1 → e.1$a. Стандартное поведение NewVarName переименовало бы e.1 → e.2, s.007 → s.008 и т.д.

Поскольку суффикс $〈буква〉 будут получать только скрывающие переменные, отлаживать программу даже станет проще. Вместо номера области видимости (пронумеруй все образцы по пути вычислений) будет номер переменной с тем же индексом и знаком ^. Первая переменная с ^ будет иметь суффикс $a, вторая — $b и т.д.

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

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

[Mazdaywik]

Дополнительные соображения:

• Для удобства миграции вместо (Extern e.Names), (Entry e.Names), (Drive e.Names)… лучше использовать множественное число: Externs, Entries, Drives…

• Абстрактные скобки можно хранить как (ADT-Brackets t.Term*), подразумевая, что термов больше одного и первый из них всегда имя. Такая структура во многих местах упростит обход дерева: ADT-Brackets будет обрабатываться единообразно с Brackets, CallBrackets и ClosureBrackets, исчезнет один частный случай. Если переписывать генерацию кода в рамках #204, то можно квадратные скобки обрабатывать аналогично круглым: не выделять особую операцию, которая сопоставляет и квадратные скобки, и имя функции внутри.

  Преобразование формата квадратных скобок можно объединить с переименованием ADT-Brackets → ADT.

[Mazdaywik]

$SWAP как функция

Статический ящик в дереве имеет смысл представлять как функцию с телом Swap:

(Function s.ScopeClass (e.Name) Swap /* пусто */)

Цель: единообразие. В компиляторе уже есть функции типа Sentences, NativeBody и Metatable. Нет смысла выделять функцию в особый узел.

[Mazdaywik]

$EXTERN’ы нужны только Checker’у (upd: на самом деле нет)

В актуальной реализации объявления функций нужны только на стадии проверки на ошибки. Машинно-зависимая стадия синтеза ими не пользуется: все функции, к которым происходит обращение и которые не определены, считаются внешними. Поэтому узел (Declaration s.ScopeClass e.Name) можно удалять на стадии рассахаривания.

UPD: внешние объявления также нужны специализатору. В аварийных предложениях обращения к функциям заменяются на обращения к пустым функциям Func@0. Поскольку замениться также может обращение ко внешней функции, для каждой внешней функции генерируется пустая функция с суффиксом @0. Так что пока удалять объявления преждевременно. При использовании алгоритма вроде https://github.com/bmstu-iu9/refal-5-lambda/issues/228#issuecomment-883563904 недостающие пустые функции можно будет генерировать на лету, а значит, объявления после семантической проверки станут не нужны.

[Mazdaywik]

Коммит выше будет перезапушен с изменением сообщения.