bmstu-iu9 / bmstu-iu9/refal-5-lambda

Переписывание языка сборки

Open
#204 3 comments 0 reactions 1 assignee Claimed by @Mazdaywik View on GitHub
task
Dominant language
C++
Stars
97
Forks
40
PR merge metrics
No merged PRs in 30d

Description

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

Мотивация
========
Как описано в #169, текущий язык сборки сформировался стихийно. Сначала я придумал кодогенерацию в Си++ для первой версии Простого Рефала. Она основана была на диапазонах вида `[first, last]`, от которых откусываются сопоставляемые объекты:

https://github.com/bmstu-iu9/refal-5-lambda/blob/ab2c5c1d9b10a2c73843619c32bb29c2443fc35d/doc/historical/note000.txt#L909-L921

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

Сейчас мне этот подход не нравится. Гораздо разумнее реализован вариант в диссертации Романенко. У него диапазоны открытые `(left, right)`, при этом границами служат сами сопоставленные элементы. При сопоставлении проверяется, что граница не пустая, сохраняется на вершине стека под очередным номером новый элемент, никакие другие указатели не изменяются.

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

Недостатком кода Романенко является наличие команды `SETB` — установки диапазона. Анализируемый диапазон в командах явным образом не передаётся, вместо этого есть некоторый «текущий». И при сопоставлении текущий модифицируется. А это значит, что компилятор должен соблюдать локальность при трансляции образцов — минимизировать количество команд `SETB`. Если в текущем диапазоне сопоставляется повторная t-переменная, а в соседнем — константная литера, то по умолчанию выгоднее сопоставить повторную переменную, поскольку иначе придётся вставить `SETB`.

Что предлагается
============
Предлагается воплотить подход Романенко, но с модификациями. Предлагается использовать те же 4-байтовые команды, но в них передавать не один номер диапазона, а пару номеров граничных элементов. Соответственно, команда `SETB` становится не нужна. Остаётся один байт на номер инструкции и один байт на значение инструкции. Точно также, как и у Романенко, для t-переменных тоже хранить пару указателей, это удобно.

Предлагается также хранить e-переменные как закрытые диапазоны `[begin, end]`, на этапе сопоставления пустые переменные хранить «нахлёстом» — `end->next == begin`. Перед построением правой части переменные будут нормализоваться, т.е. пустые вновь будут изображаться парой нулевых указателей. Прежде всего, это упростит сопоставление с повторными переменными — не придётся особым образом рассматривать пустой диапазон. Скорее всего упростятся циклы удлинения открытых переменных, по той же причине. В оптимизации построения результатных выражений можно будет разрешить плиткам начинаться и кончаться на e-переменную — для плиток, целиком состоящих из одних e-переменных, потребуется нормализация, остальное будет работать нормально.

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

Из других дополнений. Команды `icPushStack` всегда идут парами — помещается на стек закрывающая, потом открывающая скобка. Имеет смысл ввести команду, которая кладёт на стек сразу обе скобки. Получим экономию на одной команде.

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

Contributor guide

No contributing guide indexed for this repository

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.