Представленная в предыдущих подразделах методика не является
единственным способом ламбда-подъема рекурсивных функций. Су-
ществует алгоритм, который строит суперкомбинаторы для структур
данных, а не для функций. Этот алгоритм работает следующим обра-
зом. Пусть имеется программа, содержащая рекурсивную функцию
f со свободной переменной v:
(. . .
letrec f = [x].(. . . f . . . v
. . .)
in (. . . f . . .)
. . .)
По f строится рекурсивный суперкомбинатор $f, однако при этом
абстрагируется не сама функция f, а переменная v: все вхождения v
замещаются на $f v. В результате замещения получаем:
$f v x = . . .($f v). . . v . . .
(. . .
(. . .($f v). . .)
. . .)
Посмотрим, как работает данный алгоритм на примере из подраздела
16.6. Исходная программа имеет вид:
letrec
SumInts
[m].letrec
count = [n].IF(> n m)NIL
(cons n (count(+ n 1)))
in sum (count 1)
sum
= [ns].IF(= ns NIL) 0 (+(head ns)
(sum(tail ns)))
in SumInts 100
Поднимем [n].абстракцию, абстрагируя свободную переменную m,
но не count, и заменим все вхождения count на ($count m):
$count m n = IF(> n m)NIL(cons n($count m (+ n 1)))
letrec
SumInts = [m].sum($count m 1)
sum = [ns].IF(= ns NIL)0(+(head ns)
(sum(tail ns)))
in
SumInts 100
В исходной программе имеется два обращения к count: в [n].- аб-
стракции и в определении SumInts; оба эти обращения заменены
на ($count m). Теперь видно, что и SumInts, и sum являются су-
перкомбинаторами, поэтому можно выполнить их ламбда-подъем:
$count m n = IF(> n m)NIL(cons n($count m (+ n 1)))
$sum ns = IF(= ns NIL)0(+(head ns)($sum(tail ns)))
$SumInts m = sum ($count m 1)
$P rog = $SumInts 100
______________
$P rog
Основное преимущество этого метода по отношению к предыдуще-
му заключается в следующем. В примере из подраздела 16.6 рекур-
сивное обращение к $count в суперкомбинаторе $count осуществля-
лось через его параметр, названный count. В новом методе выполня-
ется вызов самого суперкомбинатора $count непосредственно. По-
строенный на этом методе компилятор работает более эффективно.
Упражнение 16.8 Выполнить предложенным методом компиляцию
программы из упражнения 16.7. |
Главная
Каталог файлов
