search

bmstu-iu9 / refal-5-lambda

Компилятор Рефала-5λ
https://bmstu-iu9.github.io/refal-5-lambda
Other
78 stars 35 forks source link

Оптимизация условий-сужений #257

Open Mazdaywik opened 5 years ago

Mazdaywik commented 5 years ago

Мотивация

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

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

Рефал-машине нужно построить вспомогательное поле зрения для вычисления R′, чтобы сопоставить его с образцом P′. Если сопоставление неуспешно, аргумент функции нужно будет сопоставить с P2. Переменные из R′ могут в процессе вычисления могут сколько угодно раз разрушаться, но для перехода на следующее предложение аргумент F должен оставаться неизменным.

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

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

Условия-сужения — мощное выразительное средство

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

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 много подобных условий сужений.

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

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

Реализация

Задача имеет два аспекта. Первый — это сопоставление переменной с образцом, второй — построение правой части.

Выполнить сопоставление переменной с образцом сравнительно несложно — к командам сопоставления с «главным» образцом добавляется (конкатенируется) последовательность команд сопоставления значения некоторой переменной с образцом условия.

А вот более интересный нюанс — построение правой части. Ведь в ней могут присутствовать как сами сужаемые переменные, так и переменные из самих суженных выражений. Т.е. на один участок поля зрения может быть несколько ссылок.

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

А ещё есть оптимизация построения результатных выражений…

Связь с задачей #248 (прогонка условий)

Задача #248 предлагает решение более общей проблемы — устранить необходимость в построении и сопоставлении условия путём инкорпорирования проверок в сам образец предложения. В частности, метод прогонки условий может упрощать и условия-сужения.

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

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 в образец нельзя, поскольку нарушится порядок сопоставления открытых переменных. Но оптимизация условий-сужений отработает блестяще.

Другой аспект в производительности. Прогонка требует нетривиального алгоритма обобщённого сопоставления с образцом. А компиляция условий-сужений столько же времени, сколько и компиляция обычных условий. В ней тоже есть нетривиальный анализ — анализ переноса/копирования переменных, но он, мне кажется, будет проще обобщённого сопоставления с образцом и выполнения подстановок.

Mazdaywik commented 5 years ago

Задача сложная для курсовой работы. К тому же, язык сборки всё равно надо переделывать (#204). Оставляю себе.

Mazdaywik commented 4 years ago

Несколько соображений.