Задача 16.1 Записать следующее определение исходного языка с по-
мощью суперкомбинаторов:
el n s = if n = 1 then hd s
else el(n−1)(tl s).
Функция el выбирает n-й элемент из последовательности s.
Решение. В терминах λ-исчисления определение функции принима-
ет вид:
el = Y (λel.λn.λs.if(= n 1)(hd s)(el(− n 1)(tl s))). (el)
Напомним алгоритм перевода λ -выражения в аппликативную фор-
му. Возьмем произвольное λ -выражение λV.E.
SK--1. Тело выражения преобразуется в аппликативную форму
рекурсивным вызовом компилятора. Результатом является:
λV.E0
.
SK--2. Свободные переменные в λ-выражении идентифицируют-
ся литерами P, Q, . . . , R , затем λ-выражение снабжается
префиксом λ , связывающим все эти переменные. Результа-
том служит:
λP.λQ....λR.λV.E0
.
Результирующее выражение заведомо является комбинато-
ром, поскольку E0 - аппликативная форма, все свободные пе-
ременные P, Q, . . . , R которой связаны.
SK--3. Назовем возникающий комбинаторalphaи сопоставим ему
определение (определяющее равенство) :
alpha P Q . . . RV → E0
.
Исходноеλ-выражение заменяется формой(alpha P R . . . R).
Применительно к выражению аппликацию a можно сокра-
тить. Выражение связано с V , а каждая свободная перемен-
ная принимает свое собственное значение в 0
. Следователь-
но, аппликативная форма действительно полностью эквива-
лентна исходному λ -выражению. Теперь определим пошаго-
вую трансляцию.
1. Рассмотрим самое внутреннее λ -выражение:
λs.if(= n 1)(hd s)(el(− n 1)(tl s)).
его свободными переменными являются n и el, поэтому
комбинатор alpha вводится определением:
alpha n el s → if(= n1)(hd s)(el(−n1)(tl s)). (alpha)
2. Все λ - выражения заменим на (alpha n el), следова-
тельно,
el = Y (λel.λn.alpha n el).
3. Повторим шаги (1.) и (2.) дляλn.alpha n el. Введем ком-
бинатор beta определением:
beta el n → alpha n el, (beta)
откуда получаем, что
el = Y (λel.beta el).
4. Повторим шаги (1.) и (2.) для (λel.beta el). Введем ком-
бинатор gamma определением:
gamma el → beta el, (gamma)
откуда получаем, что
el = Y gamma.
Ответ. el = Y gamma.
Контрольные вопросы.
1. Чем вызвано использование суперкомбинаторов для реализа-
ции редукции?
2. Что представляет собой язык константных аппликативных форм
(КАФ)?
3. Какие специфические свойства комбинаторов S, K, I допус-
кают их непосредственное использование в РГ-машине?
Упражнение. Записать с помощью суперкомбинаторов выражение:
f ac n = if n = 0 then 1 else n × (f ac(n−1)).
|
Главная
Каталог файлов
