Задача 18.1 Для исходного определения:
el = Y (λel.λnλs.IF(= n1)(hd s)(el(− n 1)(tl s)))
получить выражение с оптимальным (по двум критериям) упорядо-
чением параметров комбинатора.
Решение. Напомним, что двумя основными критериями оптимально-
сти порядка параметров комбинатора являются минимальное число
МСВ и максимальное устранение избыточных параметров. Оптими-
зируем наше определение последовательно по обоим критериям.
opt--1. Для максимизации размера и минимизации числа МСВ сле-
дующего вложенного λ -выражения все МСВ подвергаемого
компиляции λ -выражения, которые в то же самое время
являются свободными выражениями следующего вложенного
λ -выражения, должны появиться прежде МСВ, не обладаю-
щих указанным свойством. Оптимальное упорядочение пара-
метров по этому критерию можно сформулировать следую-
щим образом. Все Ei являются свободными выражениями λ
-выражения, которое подлежит компилированию, однако оно
может быть свободным выражением одного или большего
числа вложенных λ -выражений. Назовем самое внутреннее
λ -выражение, в котором выражение Ei не является свобод-
ным, порождающим λ -выражением. Если порождающее λ -
выражение Ei включает порождающее λ-выражение Ej, то
в оптимальном упорядочении Ei предшествет Ej. Отсюда
не следует, что с необходимостью однозначно определяется
оптимальное упорядочение, поскольку выражения с одним и
тем же порждающимλ-выражением могут входить в любом
порядке. Тем не менее всякое упорядочение, удовлетворяющее
этому условию, является оптимальным, как и всякое другое.
opt--2. Рассмотрим аппликативную форму (alpha(hd s)n(tl s)),
в которой параметры alpha можно расположить в любом
порядке. Если непосредственно вложенное λ -выражение свя-
зывает n , то максимальные свободные выражения (МСВ)
из формы представляют собой (alpha(hd s)) и (tl s). Если же
выполнить переупорядочение формы вида(alpha(hd s)(tl s)n),
то МСВ единственно:
(alpha(hd s)(tl s)).
opt--3. Если, с другой стороны, непосредственно вложенное λ -
выражение связывает s, то оптимальным упорядочением па-
раметров служит
(alpha n (hd s)(tl s)),
откуда единственное МСВ представляет собой (alpha n).
opt--4. Получив оптимальное упорядочение по одному критерию,
обратимся к другому. В качестве “естественных” параме-
тров можно принять
alpha beta el hd tl.
Компилятор должен так расположить параметры, чтобы
происходило максимальное устранение избыточных параме-
тров. У компилятора только тогда есть выбор, когда один
комбинатор прямо определяется как вызов другого. В каче-
стве примера рассмотрим редукцию:
beta p q r s → alpha . . . s . . . .
Кроме последнего параметра, других избыточных параметров
нет, но последний параметр комбинатора всегда должен быть
связанной переменной того λ -выражения, из которого был
осуществлен вывод. В данном случае параметр s является
связанной переменнойλ-выражения, непосредственно включа-
ющего alpha. Если параметры уже упорядочены оптимально
по рассмотренным правилам, то все параметры, в которых
участвует s, перемещаются в конец его списка параметров.
Если имеется только один такой параметр, и это s, то s
оказывается избыточным параметром beta и может быть
устранен. На этом основании вызов alpha следует задавать
в виде (alpha E1 . . . En s), где s не имеет вхождений ни в
одно из выражений Ei. Это означает, что все Ei свободны в
beta, что распространяется и на (alpha E1 . . . En s). Следо-
вательно, фактически, если имеются какие-либо Ei, то beta
надо определить посредством редукции
beta p s → p s,
где p соответствует (alpha E1 . . . En s). Если у alpha един-
ственный параметр s, то beta следует определять посред-
ством beta s → s.
В первом случае beta эквивалентен комбинатору I. Порожда-
ющее beta λ -выражение замещается на аппликацию
(beta(alpha E1 . . . En s)),
то есть на (I(alpha E1 . . . En s)). Кроме того, beta мож-
но целиком опустить, и λ -выражение замещается непосред-
ственно на (alpha E1 . . . En s).
Во втором случае beta эквивалентно alpha. Можно видеть,
что оптимальное упорядочение, получаемое по второму кри-
терию, удовлетворяет также первому и, кроме того, суще-
ственно упрощает работу по нахождению избыточных па-
раметров.
opt--5. Рассматриваемое выражениеelопределяется равенством:
el = Y (λel.λn.λs.IF(= n 1)(hd s)(el(− n 1)(tl s))).
У самого внутреннего λ -выражения имеются два МСВ:
(IF(= n 1)) и (el(− n 1)).
Примем их за параметры p и q. Оба этих МСВ имеют одно
и то же порождающее λ -выражение, поэтому их порядок
несущественен, и alpha можно определить редукцией:
alpha p q s → p(hd s)(q(tl s)),
поэтому
el = Y (λel.λn.alpha(IF(= n 1))(el(− n 1))).
Теперь оказывается, что у следующего λ-выражения только
одно МСВ и это el. Следовательно, beta определяется редук-
цией
beta el n → alpha (IF(= n 1))(el(− n 1)),
по которой
el = Y (λel.beta el).
Далее следует применять редукцию
gamma el → beta el,
и поскольку комбинатор gamma эквивалентен комбинатору
beta, то gamma порождать не следует.
Окончательно получаем, что gamma эквивалентен (Y beta).
Контрольные вопросы.
1. Какие преимущества дает использование правил оптимизации?
2. Назовите два основных критерия оптимизации.
3. На что влияет порядок параметров суперкомбинаторов?
Упражнение. Получить выражение с оптимальным порядком супер-
комбинаторов для определения:
f ac n = IF n = 0 then 1 else n×(f ac(n−1)).
|
Главная
Каталог файлов
