Теоретические сведения. Имеется два подхода к применению суперкомби-
наторов для реализации аппликативных языков программирования. При
первом их них программа компилируется посредством фиксированного на-
бора суперкомбинаторов (в неоптимизированном варианте - S, K, I) с за-
ранее известными определениями. Сначала остановимся на втором под-
ходе, при котором определения суперкомбинаторов генерируются самой
программой в процессе компиляции.
16.1 Понятие о суперкомбинаторе
Определение 16.1 Суперкомбинатор $S арности n представляет
собой ламбда-выражение (абстракцию) вида:
[x1].[x2]....[xn].E,
где E не является абстракцией. Таким образом, все “ведущие” сим-
волы абстракции [·]. относятся только к x1, x2, . . . , xn, при этом
выполняются условия:
(1) $S не содержит свободных переменных;
(2) каждая абстракция в E является суперкомбинатором;
(3) n ≥ 0, то есть наличие символов “[·].” не обязательно.
Суперкомбинаторный редекс это аппликация суперкомбинатора к n
аргументам, где n - его арность. Подстановка аргументов в тело су-
перкомбинатора вместо свободных вхождений соответсвующих фор-
мальных параметров называется редукцией суперкомбинатора. Мож-
но вспомнить обычное определение комбинатора и произвести срав-
нение. Другими словами, можно сказать, что комбинатор - это такая
ламбда-абстракция, которая не содержит вхождений свободных пе-
ременных. Некоторые ламбда-выражения являются комбинаторами,
а некоторые комбинаторы являются суперкомбинаторами.
Пример 16.1 Выражения
3, + 2 5, [x].x, [x].+ x x, [x].[y].xy
представляют собой суперкомбинаторы.
Пример 16.2 Приводимые термы не являются суперкомбинатора-
ми:
[x].y (переменная y входит свободно),
[y].− y x (переменная x входит свободно).
Пример 16.3 Терм [f].f([x].f x 2) является комбинатором, так как
все переменные (f и x) связаны, но не являются суперкомбинато-
ром, поскольку во внутренней абстракции переменная f свободна
и нарушается пункт (2) определения 16.1. В соответствии с этим
определением комбинаторы S, K, I, B, C являются суперкомбина-
торами. Следовательно, представленная в теории категориальных
вычислений SK-машина реализует один из методов использования
суперкомбинаторов.
Суперкомбинаторы арности 0 считаются константными апплика-
тивными формами (КАФ).
Пример 16.4 Выражения:
а) 3,
б) + 4 6,
в) + 2
являются КАФ.
Пункт в) показывает, что КАФ может быть функцией, хотя и не со-
держит абстракций. Поскольку в КАФ нет символа абстракции, для
них код не компилируется.
Упражнение 16.1 Показать, что следующие выражения являются
суперкомбинаторами: 1 0, [x].+ x 1, [f].([x].+ x x).
Упражнение 16.2 Объясните, почему следующие выражения не явля-
ются суперкомбинаторами: [x].x y z, [x].[y].+ (+ x y)z.
Упражнение 16.3 Привести пример комбинатора, не являющегося
суперкомбинатором. |
Главная
Каталог файлов
