bmstu-iu9 / bmstu-iu9/refal-5-lambda
Оптимизация условий-сужений
- Dominant language
- C++
- Stars
- 97
- Forks
- 40
- PR merge metrics
- No merged PRs in 30d
Description
Мотивация
=======
В Рефале-5 и в Рефале-5λ семантика условий требует копирования переменных в выражение условия. Действительно, пусть имеется функция вида:
```Refal5
F {
P1, R′ : P′ = R1;
P2 = R2;
}
```
Рефал-машине нужно построить вспомогательное поле зрения для вычисления `R′`, чтобы сопоставить его с образцом `P′`. Если сопоставление неуспешно, аргумент функции нужно будет сопоставить с `P2`. _Переменные из `R′` могут_ в процессе вычисления могут сколько угодно раз _разрушаться,_ но для перехода на следующее предложение аргумент `F` должен оставаться неизменным.
Если предложение с условием последнее, то переменные в него можно перемещать, а не копировать (что делает оптимизирующий компилятор [`crefal`](http://www.botik.ru/pub/local/scp/refal5/)). В терминах Рефала-5λ условие рассматривается как присваивание. Конечно, такую оптимизацию тоже интересно сделать, причём даже на уровне рассахаривателя, но речь здесь о другом.
* _Примечание._ Есть заявка на такую оптимизацию: #286.
Есть особый случай условий, когда копирование переменных избыточно. Если левая часть условия является переменной, то можно её значение сразу сопоставить с образцом, не создавая её копию. Такие условия будем называть _условиями-сужениями._
Условия-сужения — мощное выразительное средство
--------------------------------------------------------------
Иногда требуется выполнять предложение, когда значение некоторой переменной имеет некоторый вид, но при этом с переменной удобно обращаться как с единым целым:
https://github.com/bmstu-iu9/refal-5-lambda/blob/80c891fb890089de33a6d0e6b1cbd87d1a5cdc5b/src/compiler/OptTree-Drive.ref#L77-L85
Здесь первое условие проверяет, что `e.OptNames` содержит имя `e.Name` с некоторой меткой. Второе условие проверяет, что тело функции `e.Body` является набором предложений (не нативной вставкой). При этом в правой части `e.OptNames` используется целиком, а также наравне используются `e.Body` и `e.Sentences`.
Вообще в коммите 80c891fb890089de33a6d0e6b1cbd87d1a5cdc5b в файле [`OptTree-Drive.ref`](https://github.com/bmstu-iu9/refal-5-lambda/blob/80c891fb890089de33a6d0e6b1cbd87d1a5cdc5b/src/compiler/OptTree-Drive.ref) много подобных условий сужений.
Но их непосредственное использование пагубно сказывается на быстродействии. Для оптимизации прогонки мне пришлось практически везде их вычистить (поэтому ссылаюсь на старый коммит).
Так что оптимизация актуальна: она позволит писать естественный выразительный код без потери производительности.
Реализация
========
Задача имеет два аспекта. Первый — это сопоставление переменной с образцом, второй — построение правой части.
Выполнить сопоставление переменной с образцом сравнительно несложно — к командам сопоставления с «главным» образцом добавляется (конкатенируется) последовательность команд сопоставления значения некоторой переменной с образцом условия.
А вот более интересный нюанс — построение правой части. Ведь в ней могут присутствовать как сами сужаемые переменные, так и переменные из самих суженных выражений. Т.е. на один участок поля зрения может быть несколько ссылок.
И потребуется принимать решение — какие же значения следует перемещать, а какие — копировать. Более того, в предложении может быть несколько условий-сужений, и некоторые из них могут сужать переменные из предыдущего условия-сужения. В образцах условий-сужений могут быть повторные переменные — одна и та же переменная может быть и частью аргумента, и частью сужения другой переменной.
А ещё есть оптимизация построения результатных выражений…
Связь с задачей #248 (прогонка условий)
============================
Задача #248 предлагает решение более общей проблемы — устранить необходимость в построении и сопоставлении условия путём инкорпорирования проверок в сам образец предложения. В частности, метод прогонки условий может упрощать и условия-сужения.
Но предлагаемый метод и прогонка условий хоть и существенно пересекаются, но не исключают друг друга. В частности, есть предложения, где прогонка условий бессильна, а оптимизация условий-сужений даёт результат. Например:
```Refal5
F {
(e.X) (e.Y-B s.1 e.Y-E), e.X : e.X-B s.1 e.X-E = (e.X-B) s.1 (e.Y-E);
(e.X) (e.Y) = '*';
}
```
Здесь даже при ad hoc-расширениях (#249) встроить сужение для `e.X` в образец нельзя, поскольку нарушится порядок сопоставления открытых переменных. Но оптимизация условий-сужений отработает блестяще.
Другой аспект в производительности. Прогонка требует нетривиального алгоритма обобщённого сопоставления с образцом. А компиляция условий-сужений столько же времени, сколько и компиляция обычных условий. В ней тоже есть нетривиальный анализ — анализ переноса/копирования переменных, но он, мне кажется, будет проще обобщённого сопоставления с образцом и выполнения подстановок.
Contributor guide
No contributing guide indexed for this repository
Assessment
This issue has not been assessed yet.