Рассмотрим простую оптимизацию алгоритма ламбда-подъема. Пусть
имеется выражение: [x].[y].− y x. Хотя оно и является суперкомби-
натором, применим к нему алгоритм ламбда-подъема.
(1) Выберем самую внутреннюю абстракцию[y].−y x. Перемен-
наяxвходит в нее свободно. Вынесем ее в качестве экстрапараметра:
([x].[y].− y x)x. Положим: $Y = [x].[y].− y x. Таким образом:
$Y x y = − y x
____________
[x].$Y x
(2) Пусть $X = [x].$Y x. Тогда имеем:
$Y x y = − y x
$X x = $Y x
____________
$X
(3) В данном случае определение $X упрощается до $X = $Y
(в силу η-редукции). Таким образом, суперкомбинатор $X является
избыточным и может быть заменен на $Y :
$Y x y = − y x
____________
$Y
В результате оказывается, что имеется две оптимизации:
1) устранение избыточных параметров из определений с помо-
щью η-редукции,
2) удаление избыточных определений. |
Главная
Каталог файлов
