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

[Mazdaywik]

Мотивация

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

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

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

Если предложение с условием последнее, то переменные в него можно перемещать, а не копировать (что делает оптимизирующий компилятор crefal). В терминах Рефала-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 много подобных условий сужений.

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

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

Реализация

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

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

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

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

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

Связь с задачей #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]

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

[Mazdaywik]

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

• Условия требуют одного шага рефал-машины. Поэтому даже если условие является сужением и выполняется как часть сопоставления с образцом, фиктивный шаг рефал-машины должен эмулироваться.

  Возможно, стоит перенести учёт виртуальных шагов рефал-машины из Library в рантайм, туда же перенести функции __Step-Start, __Step-End и __Step-Drop.

• Совместить сужения с режимом -OR+ довольно просто, если переменная сужается один раз. Просто подставляем в образец, откуда берётся сужаемая переменная, правую часть сужения. В результатном выражении заменяем на правую часть сужения одно из вхождений этой переменной. Если сужаемая переменная в образце была повторной, то заменяем то вхождение, которое сужалось.

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

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

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

• Как компилировать без режима -OR-, пока непонятно. Подход с подстановкой сужения в образец и результат тут будет неэффективен, т.к. в результате получим вместо одной переменной кучу переменных и литералов (символов и скобок). Если переменная могла переместиться, то кучу литералов придётся аллоцировать. Если переменная копировалась, то выполнить кучу команд аллокации будет дольше, чем скопировать переменную целиком.

• Если переменная повторная и имеет два сужения, то сужать (анализировать) нужно разные её экземпляры. Тогда можно будет оба сужения подставить в образец для режима -OR+, для режима -OR- тоже возможен свой профит.