Суперкомбинаторы легко компилируются. Опишем алгоритм пре-
образования абстракций в комбинаторы. Рассмотрим программу, не
содержащую ни одного суперкомбинатора:([x].([y].+ y x)x)4. Вы-
берем самую внутреннюю абстракцию, то есть такую абстракцию,
которая не содержит других абстракций: ([y]. + y x). В нее входит
свободная переменная x, поэтому эта абстракция не является супер-
комбинатором.
(1) С помощью простого преобразования (обычной β-редукции)
получим суперкомбинатор ([x].[y].+ y x)x.
(2) Подставим его в исходную программу:([x].([w].[y].+y w)x x)4.
(3) Присвоим суперкомбинатору имя $Y .
(4) Теперь видно, что [x].-абстракция тоже является суперкомби-
натором. Дадим ему имя $X (скомпилируем абстракцию) и сопоста-
вим его скомпилированному коду:
$Y w y = + y w
$X x = $Y x x
________________
$X 4
Можно выполнить полученную программу, осуществляя редукцию
суперкомбинаторов: $X 4 ⇒ $Y 4 4 = + 4 4 = 8. Таким образом,
алгоритм преобразования абстракций в суперкомбинаторы приобре-
тает следующий вид:
ЦИКЛ while:
есть абстракции,
(1) выбрать любую абстракцию, не содержащую других абстрак-
ций,
(2) вынести все свободные в этой абстракции переменные в ка-
честве экстрапараметров,
(3) абстракции приписать некоторое имя (например, $X34),
(4) заменить вхождение абстракции в программу на имя супер-
комбинатора, которое приложено к свободным переменным,
(5) произвести компиляцию абстракции и скомпилированному
коду сопоставить имя,
ВСЕ-while
В ходе преобразования объем программы возрос. Это является свое-
образной платой за простоту правил редукции. Заметим, что проце-
дура преобразования приводит исходную программу к виду:
. . . . определения суперкомбинаторов . . . .
___________________
E
Поскольку выражениеE является вычисляемым выражением самого
высокого уровня, то оно не содержит свободных переменных. Его
можно считать суперкомбинатором арности 0, то есть КАФ:
. . . . определения суперкомбинаторов . . . .
$P rog = E
______________
$P rog
Процесс преобразования абстракций в суперкомбинаторы называ-
ется ламбда-подъемом, поскольку все абстракции поднимаются на
верхний уровень.
Упражнение 16.5 Преобразовать и выполнить программы:
1)([x].([y].− y x)x)5,
2)([z].+ z(([x].([y].×y x)x)4))2.
|
Главная
Каталог файлов
