Рассмотрим программу, суммирующую первые 100 целых чисел:
SumInts m = sum(count 1)
where
count n = [], n > m
= n : count(n+ 1)
sum [] = 0
sum (n : ns) = n + sum ns
___________________
SumInts 100
SumInts представляет собой композицию функций sum и count:
сначала функция count применяется к 1, а затем ее результат посту-
пает на вход функции sum. Функция count работает следующим
образом:
count 1 = 1 : count 2 (так как n = 1, m = 100,
и условие n > m не выполняется)
= 1 : 2 : (count 3) (вычисляется count 2)
. . .
= 1 : 2 : . . . : 100 : (count 101)
= 1 : 2 : . . . : 100 : [] (поскольку
n = 101, m = 100, то n > m, и (count 101 = []))
Теперь список 1 : 2 : 3 : . . . : 100 : [] передается функции sum.
Во втором определяющем равенстве для sum аргумент (n : ns) обо-
значает список, в котором первым элементом является число n, а
“хвостом” - список чисел ns :
sum 1 : 2 : 3 : . . . : 100 : [] = 1 + sum 2 : 3 : . . . : 100 : []
. . .
= 1 + 2 + 3 +. . .+ 100 +sum[]
= 1 + 2 + 3 +. . .+ 100 + 0 (так как sum [] = 0)
Запишем эту функцию в терминах абстракций с использованием
letrec:
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
В данном случае: NIL - пустой список [], head - функция, воз-
вращающая первый элемент списка, tail - функция, возвращающая
хвост списка (список без первого элемента). Переменные SumInts
и sum имеют номер 0, однако SumInts содержит внутреннюю [n].-
абстракцию со свободными переменными m и count. Необходимо
выполнить алгоритм ламбда-подъема и “поднять” эти переменные.
(1) Внутренняя абстракция имеет вид:
[n].IF(> n m)NIL(cons n(count(+ n 1))).
(2) Вынесем переменные countиmв указанном порядке (так как
связанная в исходной программе переменная m должна находиться
на последнем месте):
([count].[m].[n].IF(> n m)NIL
(cons n (count(+ n 1))))count m
(3) Полученному суперкомбинатору присвоим имя $count
$count count m n = IF(> n m)NIL
(cons n(count(+ n 1))).
(4) Заменим вхождение [n].-абстракции в программу на$count count m n :
$count count m n = IF(> n m) NIL
(cons n (count(+ n 1)))
letrec
SumInts
= [m].letrec
count = $count count m
in sum (count 1)
sum = [ns].IF(= ns NIL)0
(+(head ns)(sum(tail ns)))
in SumInts 100
(5) В выражениях SumInts и sum нет внутренних абстракций, их
уровень равен 0, поэтому они являются суперкомбинаторами. Непо-
средственно применяя к ним подъем и добавляя суперкомбинатор
$P rog, получим окончательный результат:
$count count m n = IF(> n m)NIL
(cons n(count(+ n 1)))
$sum ns = IF (= ns NIL)0(+(head ns)
($sum(tail ns)))
$SumInts m = letrec count = $count count m
in $sum (count 1)
$P rog = $SumInts 100
______________
$P rog
Упражнение 16.7 Скомпилировать программу, которая приклады-
вает функцию f = КВАДРАТ к каждому элементу списка целых
чисел от 1 до 5:
apply m = fold КВАДРАТ (constr 1)
where constr n = [], n > m
= n : constr(n+ 1)
fold f[] = []
fold f(n : ns) = fn : fold f ns
|
Главная
Каталог файлов
