Во всех рассмотренных выше программах порядок вынесения пе-
ременных как экстрапараметров был произвольным. Например, рас-
смотрим программу
.. . . . . . . . . . . . . . . . . . ..
(. . .
([x].[z].+ y(×x z))
. . .),
где “. . . ” указывает на объемлющий [x].-абстракцию контекст. На-
чнем выполнять алгоритм ламбда-подъема.
(1) Выберем самую внутреннюю абстракцию [z].+ y(×x z). Эта
абстракция не является суперкомбинатором, так как содержит две
свободные переменные x и y. На следующем шаге алгоритма сле-
дует вынести свободные переменные в качестве экстрапараметров.
Возникает вопрос, в каком порядке располагать переменные: можно
сначала поместить x, а затем y, а можно - сначала y, затем - x. Вы-
полним оба варианта.
Вариант 1.
(2) Вынесем переменные, расположив их в порядке x, y:
([x].[y].[z].+ y(×x z))x y.
(3) Присвоим полученному суперкомбинатору имя
$S = ([x].[y].[z].+ y(×x z)).
(4) Подставим $S в исходную программу:
$S x y z = + y(×x z)
____________
(. . .
([x].$S x y)
. . .)
Выражение [x].$S x y не является суперкомбинатором, поэтому к
нему, в свою очередь, следует применить алгоритм ламбда-подъема.
(2) Вынесем свободную переменную y:
([y].[x].$S x y)y.
(3) Присвоим суперкомбинатору имя $T y x = $S x y.
(4) Подставим комбинатор в программу:
$T y x = $S x y
____________
$T y.
Вернемся к основному алгоритму, в котором теперь получаем:
$S x y z = + y(×x z)
$T y x = $S x y
(. . .$T y . . .).
Вариант 2.
(2) Вынесем переменные, расположив их в порядке y, x:
([y].[x].[z].+ y(×x z))y x.
(3) Присвоим полученному суперкомбинатору имя
$S = ([y].[x].[z].+ y(×x z)).
(4) Подставим $S в исходную программу:
$S y x z = + y(×x z)
(. . .
([x].$S y x)
. . .).
Выражение [x].$S y x не является суперкомбинатором, поскольку
содержит свободную переменнуюy. Применим к [x].$S y xалгоритм
подъема.
(1) Самая внутренняя абстракция совпадает с программой.
(2) Вынесем переменную y : ([y].[x].$S y x)y.
(3) Присвоим суперкомбинатору имя $T = [y].[x].$S y x.
(4) Подставим комбинатор в программу:
$T y x = $S y x
_______________
$T y
Вернемся к основному алгоритму. Получим:
$S x y z = + y(×x z)
$T y x = $S y x
___________
(. . .$T y . . .)
В соответствии с правилом устранения избыточных параметров (см.
подраздел 16.4) получаем: $T = $S, поэтому $T можно устранить.
Тогда скомпилированный код примет вид:
$S y x z = + y(×x z)
____________
$S y
В первом варианте такая оптимизация невозможна. В исходной про-
грамме (. . .([x].[z]. + y(×x z)). . .) имеются две связанные пере-
менные: x и z. Во втором варианте произведено упорядочивание
свободных переменных на шаге (2) так, что в полученном супер-
комбинаторе связанные в программе переменные xи z стоят послед-
ними: $S y x z. Только в этом случае код можно оптимизировать.
Таким образом, свободные переменные необходимо упорядочивать
так, чтобы связанные переменные оказались последними в списке
параметров суперкомбинатора.
С каждой абстракцией связывается лексический номер уровня, кото-
рый определяется числом объемлющих ее символов абстракции.
Пример 16.7 В выражении ([x].[y].+ x(×y y)) оператор [x].-абст-
ракции находится на уровне 1, а [y].-абстракция -- на уровне 2.
Сформулируем правила, позволяющие устанавливать лексический
номер уровня:
1) лексический номер абстракции на единицу больше числа объ-
емлющих ее абстракций; если таких абстракций нет, то номер равен
1,
2) лексический номер переменной - это номер абстракции, свя-
зывающей данную переменную; если номер x меньше номера y, то
говорят, что x свободнее y,
3) лексический номер константы равен 0.
Для того, чтобы повысить возможность оптимизаций, экстрапараме-
тры следует отсортировать по возрастанию их лексических номеров. |
Главная
Каталог файлов
