Задача 17.1 Для примера определения
el n s = if n = 1 then (hd s) else el(n−1)(tl s) f i
выбрать суперкомбинаторы, дающие полностью ленивую реализа-
цию, и рассмотреть частный случай применения el 2.
Решение. Введем некоторые определения. Оказывается, что те выра-
жения, которые подвергаются повторным означиваниям, легко иден-
тифицируются. Это относится и ко всякому подвыражению λ-выра-
жения, которое не зависит от связанной переменной. Такие выраже-
ния называют свободными выражениями λ-выражения (по аналогии
с введением понятия свободной переменной). Свободные выраже-
ния, которые не являются частью никакого другого большего сво-
бодного выражения, называют максимальными свободными выра-
жениями λ-выражения (МСВ).
lazy--1. Рассмотрим схему трансляции. Минимальные свободные
выражения каждого λ-выражения преобразуются в параме-
тры соответствующего комбинатора. Остановимся на схе-
ме преобразования максимальных свободных выражений в па-
раметры соответствующего комбинатора.
lazy--2. Сначала установим, что такая схема трансляции значи-
ма, то есть получены настоящие комбинаторы и каждое λ-
выражение заменено на аппликативную форму. Рассмотрим
применимость новой схемы к отдельномуλ-выражению, тело
которого является аппликативной формой. Тот комбинатор,
который при этом возникает, должен удовлетворять опреде-
лению, так как его тело должно быть аппликативной формой
и не должно содержать свободных переменных. Тело комби-
натора заведомо будет аппликативной формой, поскольку оно
в свою очередь возникло из аппликативной формы (тела исход-
ного λ-выражения) путем подстановки вместо некоторых
выражений новых имен параметров. В нем не может быть
свободных переменных, поскольку любая свободная перемен-
ная должна быть частью некоторого максимального свобод-
ного выражения и поэтому подлежит удалению как часть па-
раметра. Все это подтверждает, что построен настоящий
комбинатор. Окончательный результат,который замещает
исходное λ-выражение, представляет собой новый комбина-
тор, приложенный к максимальным свободным выражениям,
каждое из которых - уже аппликативная форма. Вернемся к
исходной задаче.
lazy--3. Пусть максимальные свободные выражения для исходно-
го выражения
λs.if(= n 1)(hd s)(el(− n 1)(tl s))
представляют собой
(if(= n 1)) и (el(− n 1)).
Следовательно, новый комбинатор alpha определяется по-
средством
alpha p q s → p(hd s)(q(tl s)),
а определением el служит выражение
el = Y (λel.λn.alpha(if(= n 1))(el(− n 1))).
Продолжая этот процесс, получаем комбинаторыbetaиgamma,
задаваемые определениями:
beta el n → alpha(if(= n 1))(el(− n 1)),
gamma el → beta el,
откуда заключаем, что выражениеel эквивалентно(Y gamma),
то есть el = Y gamma, что совпадает с прежним результа-
том.
lazy--4. Рассмотрим частный случай, когда применяется (el 2):
el 2 → (Y gamma)2
→ gamma el 2
→ beta el 2
→ alpha(if(= 2 1))(el(− 2 1)).
Всегда при использовании (el 2) употребляются одни и те
же копии свободных выражений, следовательно, они означи-
ваются только один раз. Фактически получается редукция:
el 2 → alpha if −F ALSE(alpha if −T RUE(el(− 1 1))).
Более подробно:
el 2 → alpha(if(= 2 1))(el(− 2 1))
→ alpha(if −F ALSE)(el 1)
→ alpha(if −F ALSE)(alpha(if(= 1 1))(el(− 1 1)))
→ alpha(if −F ALSE)(alpha(if −T RUE)(el(− 1 1)))
Рассмотренная схема приводит к субоптимальным комбинаторам.
Контрольные вопросы.
1. Определите понятия “ленивое означивание в λ -исчислении” и
“полная ленивость” в языке КАФ и укажите связь между ними.
2. Что означает термин “МСВ λ -выражения”?
3. Что представляет собой окончательный результат замещения
исходного λ -выражения при полностью ленивой реализации
суперкомбинаторов?
Упражнение. Для выражения
f ac n = if n = 0 then 1 else n×(f ac(n−1))
осуществить полностью ленивую реализацию с помощью суперком-
бинаторов и вычислить f ac 3. |
Главная
Каталог файлов
