Алгоритм, использующий МСВ, отличается от приведенного ранее
алгоритма ламбда-подъема тем, что абстрагирует не переменные, а
МСВ. Вернемся к разбираемому примеру. Функция g содержит аб-
стракцию:
x].[y].+ y(sqrt x).
Проиллюстрируем в этой ситуации работу алгоритма.
(1) Самой внутренней абстракцией является [y].+ y(sqrt x).
(2) Выражение (sqrt x) является МСВ. Вынесем МСВ в качестве
экстрапараметра: ([sqrtx].[y]. + y(sqrtx))sqrtx, где sqrtx является
именем экстрапараметра. Подставим полученное выражение в ис-
ходную абстракцию: [x].([sqrtx].[y].+ y sqrtx)sqrtx.
(3) Присвоим полученному суперкомбинатору имя:
$g1 = [sqrtx].[y].+ y sqrtx
[x].$g1 (sqrt x)
(4) Имеющаяся [x].-абстракция также является суперкомбинато-
ром, которому дадим имя и который сопоставим скомпилированному
коду:
$g1 sqrtx y = + y sqrtx
$g x = $g1 (sqrt x)
$f = $g 4
$P rog = + ($f 1)($f 2)
$P rog
Дополнительный суперкомбинатор получен потому, что потеряна воз-
можность использованияη-редукции из-за абстрагирования по(sqrtx)
вместо абстрагирования по x. Однако этот эффект компенсируется
наличием полной ленивости. Следовательно, для обеспечения пол-
ной ленивости необходимо абстрагировать МСВ, а не свободные пе-
ременные, используя возникающие абстракции в качестве экстра-
параметров. Приведенный алгоритм считается полностью ленивым
ламбда-подъемом.
Упражнение 16.11 Выполнить полностью ленивый ламбда-подъем
программы, рассмотренной в упражнении 16.9. |
Главная
Каталог файлов
