Разрешить аргументам прогоняемых функций быть активными

[Mazdaywik]

В текущей реализации прогонки аргументы встраиваемых и прогоняемых функций могут быть только пассивными:

https://github.com/bmstu-iu9/refal-5-lambda/blob/4ed95a0af96abfda5654ba8e4c7bf9ad680c4427/src/compiler/OptTree-Drive.ref#L284-L286

https://github.com/bmstu-iu9/refal-5-lambda/blob/4ed95a0af96abfda5654ba8e4c7bf9ad680c4427/src/compiler/OptTree-Drive.ref#L364-L366

Это было намеренным ограничением на ВКР @InfiniteDisorder‘а, поскольку содержательной частью работы был алгоритм обобщённого сопоставления и собственно прогонка.

Однако, можно прогонять и вызовы, аргументы которых содержат другие вызовы. Причём это описано даже в классических статьях Турчина (Турчин, 1972 и Турчин, 1974). Вызовы функций заменяются новыми e-переменными (т.н. «неразменными» переменными), которые запрещено сужать. Если решение уравнения содержит сужение «неразменной» переменной — то этот вызов просто оптимизировать нельзя.

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

[Mazdaywik]

Задача #231 предлагается на курсовую работу, а это её естественная подзадача, часть #231.

[Mazdaywik]

Задача не была выбрана в качестве курсовой.

[Mazdaywik]

Задача не была выбрана в качестве ВКР.

[Mazdaywik]

Соображения о связи с неразменными переменными

Интересна эволюция связи между активными аргументами и неразменными переменными.

1. Турчин описывает алгоритм обобщённого сопоставления — решения уравнения вида E : Le, где E — произвольное пассивное выражение. Для того, чтобы разрешить прогонку вызовов с активными аргументами, Турчин ввёл понятие неразменных переменных.
2. Понятие оказалось удобным для описания оптимизации прогонки в компиляторе. Можно расширить сферу применения прогонки и встраивания, если тонко управлять ограничениями на сужения переменных. Подробности: #231.
3. А вот прогонку с активным аргументом вполне можно реализовать без неразменных переменных. Просто сопоставляем аргумент с образцом, а функция Solve нам возвращает Undefined, когда пытается сузить скобки вызова.

Так что связи с задачей #231 нет, обновляю пост.

[Mazdaywik]

Соображения о реализации

Рассмотрим сопоставление E : Le, причём E — активно. Пусть сопоставление выполнилось успешно (чисто или с сужениями), переменные из Le получили свои значения. Будем называть переменные, содержащие активные подвыражения, активными переменными.

Рассмотрим ограничения на активные переменные.

1. Они не могут быть повторными. Пояснение:

   F { = <Eq (<Card>) (<Card>)> }
   
   $INLINE Eq {
     t.X t.X = True;
     t.Y t.Z = False;
   }
   

   По общему правилу подстановка для обоих вхождений текстуально совпадает, поэтому вызов должен прогнаться в True. Но тогда исчезнут два вызова <Card>! Следовательно, для повторных переменных нужно обязательно выполнять сравнение на равенство.
2. Они могут иметь только одно вхождение в правую часть. Действительно, если переменная в правую часть не входит, вызов пропадёт. Если входит несколько раз, вызов размножится.
3. Они должны входить в правую часть в том же порядке, что и в левую. Иначе возможно нарушение порядка их вызова.
4. Они должны находиться в правой части текстуально до первого вхождения закрывающей угловой скобки. Аргумент функции вычисляется раньше, чем правая часть самой функции — этот побочный эффект должен сохраняться.

Ограничение 3 зависит от вызова. Пример:

$INLINE F { (e.X) (e.Y) = e.Y e.X }

Test1 { = <F (<Print A>) (<Print B>)> }
Test2 { = <F (<Print A>) (B)> }
Test3 { = <F (A) (<Print B>)> }

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

Нюанс с замыканиями

Рассмотрим код

$INLINE F {
  (e.X) (e.Y) e.Z
    = <Print e.Z> : e.Z^
    = e.X '+' e.Y '+' e.Z;
}

Test { = <F (<Print A>) (<Print B>) <Print C>> }

Прогонится ли этот пример? Всё зависит от того, как рассахариватель перепишет замыкание. Он может сделать это так:

$INLINE F, F=1;
F {
  (e.X#1) (e.Y#1) e.Z#1
    = <{{ &F=1 (e.X#1) (e.Y#1) }} <Print e.Z#1>>;
}

F=1 {
  (e.X#1) (e.Y#1) e.Z#2 = e.X#1 '+' e.Y#1 '+' e.Z#2;
}

Test { = <F (<Print A>) (<Print B>) <Print C>> }

Тогда прогонятся оба вызова: и F, и присваивание F=1. А может построить так:

$INLINE F, F=1;
F {
  (e.X#1) (e.Y#1) e.Z#1
    = <{{ &F=1 (e.Y#1) (e.X#1) }} <Print e.Z#1>>;
}

F=1 {
  (e.Y#1) (e.X#1) e.Z#2 = e.X#1 '+' e.Y#1 '+' e.Z#2;
}

Test { = <F (<Print A>) (<Print B>) <Print C>> }

В этом случае прогонки не произойдёт, т.к. активные переменные переупорядочатся.

Какой из двух вариантов реализуется на практике — не очевидно (я проверил — первый).

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

Вывод

Реализовать поддержку активных вызовов сравнительно несложно. Сложнее, правда, чем в специализаторе (#245). Но я этого делать пока не буду, поскольку с файлом OptTree-Drive.ref будет работать @Cstyler в рамках задачи #260. Чтобы избежать боли при слиянии правок я лучше подожду.

[Mazdaywik]

Задача приемлема для курсовой работы.

[Mazdaywik]

Алгоритм решения задачи:

1. Заменяем все скобки активации в аргументе на особые k-переменные (TkVariable 'k' s.N), где s.N — число. Номера k-переменных последовательные, это важно.
2. Поправляем алгоритм обобщённого сопоставления с образцом, чтобы он не пугался k-переменных. Они для него как e-переменные, только при попытке их сузить возвращается Undefined.
3. Проверяем каждый результат прогонки. Для этого рекурсивно обходим его и выбираем только k-переменные и закрывающие угловые скобки. В полученной строке k-переменных должно быть столько же, они должны располагаться в возрастающем порядке и ни одна закрывающая угловая скобка не должна предшествовать k-терму. Это гарантирует, что порядок вызовов функций не изменится, вызовы не продублируются и не сотрутся, вызовы аргумента выполнятся раньше, чем вызовы правой части прогнанной функции.
4. Если все варианты осмысленны, то переходим к прогонке следующего предложения. Если хотя бы в одном из решений порядок нарушился, то заменяем вызов вызовом остаточной функции <Func*n …>.

ВСЁ!

А я ещё хотел её дать на ВКР и курсовую.

Так что исключаю её из списка для курсовых, как несерьёзную.