Покажем действие полностью ленивого ламбда-подъема на более де-
тализированном примере1:
SumInts n = foldl(+) 0 (count 1 n)
count n m = [], n > m
count n m = n : count(n + 1) m
fold op base [] = base
foldl op base (x : xs) = foldl op (op base x) xs
1
Дополнительную разработку техники ленивых вычислений с суперкомбинато-
рами см. в [86]. В этой же работе можно познакомиться с реализацией абстрактной
машины, обеспечивающей поддержку всего спектра возможностей.
Приведенная программа в терминах абстракций записывается сле-
дующим образом:
letrec
SumInts = [n].foldl + 0 (count 1 n)
count = [n].[m].IF(> n m)NIL
(cons n (count(+ n 1)m))
foldl = [op].[base].[xs].IF(= xs NIL)base
(foldl op (op base (head xs))(tail xs))
in SumInts 100
В этой программе:
(1) внутренней абстракцией является ([xs]. . . .),
(2) максимально свободными выражениями являются (fold op),
(op base) и base.
Вынесем их в качестве экстрапараметров p, q и base соответственно:
$R1 p q base xs = IF (= xs NIL) base
(p(q(head xs))(tail xs))
letrec
SumInts = [n].foldl + 0 (count 1 0)
count = [n].[m].IF(> n m)NIL
(cons n (count(+ n 1)m))
foldl = [op].[base].$R1(foldl op)
(op base)base
in
SumInts 100
В этой программе внутренней абстракцией является “[base].”. Мак-
симально свободными выражениями служат ($R1(foldl op)) и op,
которые вынесем как r и op соответственно:
$R1 p q base xs = IF(= xs NIL)base
(p(q(head xs))(tail xs))
$R2 r op base = r (op base)base
letrec
SumInts = [n].foldl + 0(count 1 n)
count = [n].[m].IF(> n m)NIL(cons n
(count(+ n 1)m))
foldl = [op].$R2($R1 op)op
in
SumInts 100
(3) все определения letrec являются суперкомбинаторами, поскольку
выполнен подъем всех внутренних абстракций. С учетом всех заме-
чаний получаем окончательный результат:
$SumInts n = $foldlPlus0 ($count1 n)
$foldlPlus0 = $foldl + 0
$count1 = $count 1
$count n m = IF(> n m)NIL(cons n($count(+ n 1)m))
$foldl op = $R2($R1($foldl op))op
$P rog = $SumInts 100
$R1 p q base xs =
IF(= xs NIL)base(p(q(head xs))(tail xs))
$R2 r op base = r (op base)base
$P rog
Завершая рассмотрение, отметим, сто в данном случае нельзя устра-
нить параметр op из $foldl, поскольку он используется дважды в
правой части. |
Главная
Каталог файлов
