0не имеет свободных переменных (1) и символов абстракции (3);[x].+x1
имеет переменную x, которая является связанной (1); + x 1 не содер-
жит абстракций (2);[f].f([x].+ x x) не имеет свободных переменных (1),
[x].+ x x является суперкомбинатором (2).
16.2
[x].x y z содержит свободные переменные y и z, нарушается пункт (1)
определения 16.1; [x].[y].+ (+ x y)z имеет свободную переменную z.
16.3
Например, [x].[y].x y([z].z x).
16.4
Выражение $XY 5 вычислить нельзя, так как оно не является редексом;
$XY 5 7 вычислимо, $XY 3 4 7 вычислимо.
16.5
1)([x].([y].− y x)x)5:
(1) самой внутренней абстракцией является [y].− y x;
(2) вынесем x как экстрапараметр ([x].[y].− y x)x и подставим его в
исходную программу ([x].([v].[y].− y v)x x)5;
(3) присвоим суперкомбинатору имя $Y :
$Y v y = − y v
([x].$Y x x)5
(4) [x].-абстракция также является суперкомбинатором, которому
можно дать имя и который можно сопоставить скомпилированному коду:
$Y v y = − y v
$X x = $Y x x
$X 5
Полученная программа выполняется следующим образом:
$X 5 = $Y 5 5 = − 5 5 = 0.
2)([z].+ z (([x].([y].× y x)x)4)2 :
(1) внутренняя абстракция: [y].× y x;
(2) вынесем x как экстрапараметр:
([x].[y].× y x)x
([z].+ z(([x].([w].[y].× y w)x x)4))2;
(3)
$Y w y = × y w
([z].+ z([x].$Y x x)4)2
(4) [x].-абстракция является суперкомбинатором:
$Y w y = × y w
$X x = $Y x x
([z].+ z($X 4))2
Теперь видно, что [z].-абстракция является суперкомбинатором:
$Y w y = × y w
$X x = $Y x x
$Z z = + z ($X 4)
$Z 2
Выполнение программы:
$Z 2 = + 2 ($X 4) = + 2 ($Y 4 4) = + 2 (× 4 4) = + 2 16 = 18.
16.6
inf находится на уровне и не содержит внутренних абстракций. Поэтому
inf уже является суперкомбинатором:
$inf v = letrec vs = cons 0 vs in vs
$P rog = $inf 4
$P rog
16.7
Запишем эту программу в терминах абстракций:
letrec apply = [m].letrec constr = [n].(IF > n m)NIL
(cons n (constr (+ n 1)))
in fold КВАДРАТ (constr 1)
fold = [f].[ns].IF(= ns NIL)NIL(cons(f(head ns))
(fold(f(tail ns))))
in apply 5
(1) внутренняя абстракция имеет вид:
([n].IF(> n m)NIL(cons n(constr(+ n 1)));
(2) вынесем переменные constr и m в указанном порядке:
([constr].[m].[n].IF(> n m)NIL(cons n(constr(+ n 1)))constr m;
(3) присвоим полученному суперкомбинатору имя $constr:
$constr constr m n = IF(> n m)NIL(cons n(constr(+ n 1)));
(4) заменим вхождение [n].-абстракции в программу на
($constr constr m n);
$constr constr m n = IF(> n m)NIL(cons n(constr(+ n 1)))
letrec
apply = [m].letrec
constr = $constr constr m
in fold КВАДРАТ (constr 1)
fold = [f].[ns].IF(= ns NIL)NIL
(cons(f(head ns))(fold f(tail ns)))
in apply 5
(5) выражения apply и fold являются суперкомбинаторами:
$constr constr m n = IF(> n m)NIL(cons m(constr(+ n 1)))
$fold f ns = IF(= ns NIL)NIL(cons(f(head ns))
(fold(f (tail ns))))
$apply m = letrec constr = $constr constr m
in $fold КВАДРАТ (constr 1)
$P rog = $apply 5
$P rog
16.8
Поднимем [n].-абстракцию, абстрагируя переменную m, но не constr, и
заменим все вхождения constr на ($constr m):
$constr m n = IF(> n m)NIL(cons n($constr m(+ n 1)))
letrec
apply = [m].fold(КВАДРАТ)($constr m 1)
fold = [f].[ns].IF(= ns NIL)NIL(cons(f(head ns))
(fold(f(tail ns))))
in apply 5
В данном случае и apply, и fold являются суперкомбинаторами:
$constr m n = IF(> n m)NIL(cons n($constr m(+ n 1)))
$fold f ns = IF(= ns NIL)NIL(cons(f(head ns))
($fold f(tail ns)))
$apply m = $fold КВАДРАТ ($constr m 1)
$P rog = $apply 5
$P rog
16.9
а) Запись в виде абстракции:
letrec f = g 2
g = [x].[y].× y (КВАДРАТ x)
in × (f 3)(f 1)
Вычисление выражения:
× (f 3)(f 1) → (. 3)(. 1)
−→ ([x].[y].× y (КВАДРАТ x))2
→ × (. 3)(. 1)
−→ ([y].× y (КВАДРАТ 2))
→ × (. 3)(× 1 (КВАДРАТ 2))
−→ ([y].× y (КВАДРАТ 2))
→ × (. 3) 4
−→ ([y].× y (КВАДРАТ 2))
→ × (× 3 (КВАДРАТ 2)) 4
→ × 12 4
→ 48.
б) Данное выражение компилируется в:
$g x y = × y (КВАДРАТ x)
$f = $g 2
$P rog = × ($f 3)($f 1)
$P rog
Последовательность редукций:
$P rog → (× (. 3)(. 1))
−→ ($g 2)
→ × (. 3)(× 1 (КВАДРАТ 2))
−→ ($g 2)
→ × (. 3) 4
−→ ($g 2)
→ × (× 3 (КВАДРАТ 2)) 4
→ × (× 3 4) 4
→ × 12 4
→ 48.
16.10
× (f 3)(f 1) → × (. 3)(. 1)
−→ (([x].[y].× y (КВАДРАТ x))2)
→ × (. 3)(× 1 .)
−→ ([y].× y (КВАДРАТ 2))
→ × (. 3) 4 (× 1 .)
−→ ([y].× y 4)
→ × (. 3) 4
−→ ([y].× y 4)
→ × (× 3 .) 4
−→ 4
→ × 12 4
→ 48
Выражение (КВАДРАТ 2) вычисляется единственный раз.
16.11
Функция g содержит абстракцию: [x].[y].× y (КВАДРАТ x):
(1) самой внутренней абстракцией является
[y].× y (КВАДРАТ x);
(2) (КВАДРАТ x) представляет собой МСВ, которую вынесем в каче-
стве экстрапараметра:
[КВАДРАТx].[y].× y (КВАДРАТx)КВАДРАТx.
Подставим полученное выражение в абстракцию:
[x].[КВАДРАТx].[y].× y (КВАДРАТx)КВАДРАТx ;
(3) присвоим полученному суперкомбинатору имя:
$g1 = [КВАДРАТx].[y].× y КВАДРАТx
[x].$g1 (КВАДРАТ x)
(4) [x].-абстракция также является суперкомбинатором, которому
дадим имя $g и который сопоставим скомпилированному коду:
$g1 КВАДРАТx y = × y КВАДРАТx
$g x = $g1 (КВАДРАТ x)
$f = $g 2
$P rog = × ($f 3)($f 1)
$P rog
16.12
Данная программа компилируется в:
$el el n s = (IF(= n 1)(head s)(el(− n 1)(tail s)))
$g x = letrec el = $el el
in (cons x (el 3 (A, B, C)))
(cons ($g R)($g L))
Поскольку определение el не зависит от x, можно вынести letrec для el:
letrec el = [n].[s].(IF(= n 1)(head s)
(el(−n1)(tails)))
in let g = [x].cons x (el 3 (A, B, C))
in (cons (g R)(g L))
В результате применения ламбда-подъема получим:
$el n s = (IF(= n 1)(head s)(el(− n 1)(tail s)))
$el3(A, B, C) = $el 3 (A, B, C)
$g x = cons x $el3(A, B, C)
$P rog = cons ($g R)($g L)
$P rog
В ходе компилирования программы порождаются новые комби-
наторы, параметрами которых являются конкретные МСВ. Другими
словами, компилятор выполняет соотнесение с заложенным в нем
способом вычленения из исходного кода программы объектов и по-
рождает объекты-индивиды. Поскольку порожденные объекты явля-
ются комбинаторами, то вполне безопасно добавить их к системе-
оболочке в качестве новых инструкций. Все порожденные комбина-
торы дают вполне индивидуализированное представление исходной
программы: это система объектов.
Возможно, лучше объяснять в терминах соотнесения системы-
оболочки (λ-исчисления) с совокупностью МСВ. Тогдаλ-исчисление
как концептдает систему индивидов (скомпилированных программ):
они образуют класс эквивалентности (конвертируются друг к другу)
относительно критериев оптимальности. |
Главная
Каталог файлов
