Рекурсивные функции

Поскольку в l-исчислении все функции анонимны, то для представления рекурсивных функций с помощью ламбда-термов необходимо придумать метод, позволяющий функциям вызывать себя не по имени, а каким-то другим образом.

Представим рекурсивную функцию как функцию, имеющую себя в качестве аргумента. В этом случае функция может оказаться связанной с одной из её собственных переменных и будет, таким образом, содержать в своем теле ссылки на самое себя.

Рассмотрим, например, рекурсивную функцию sum(x), определенную для сложения все целых чисел от 1 до n

sum(n) = (IF (= n 0) 0 (+ n (sum (1- n)))).

В этой записи мы используем пять констант: число 0, булевские функцию для равенства (=), функции для условного выражения (IF), для суммы (+) и для вычитания 1 (1-).

Это выражение может быть представлено в виде l-абстракции, имеющей дополнительный параметр, который при применении этой абстракции связывается с самой функцией. Мы запишем эту промежуточную версию функции sum:

sum = ls. ln. IF (= 0 n) 0 (+ n (s (1- n)))

Все, что нам осталось сделать теперь, - это связать переменную s со значением функции sum, которую пытаемся определить. Это можно сделать, использовав специальную функцию, называемую Y-комбинатором, которая удовлетворяет следующему уравнению:

Y f = f (Y f)

Y также известен как комбинатор неподвижной точки. “Неподвижная точка” функции f - это выражение, которое не изменяется при применении к нему функции f. (Заметим, что функция может иметь несколько неподвижных точек. Например, функция тождества lx. x, имеет бесконечное их число.) Выражение Y f дает наименьшую неподвижную точку функции f.

Y sum

= Y(ls. ln. IF (= 0 n) 0 (+ n (s (1- n))))

® (ls. ln. IF (= 0 n) 0 (+ n (s (1- n)))) (Y sum)

® ln. IF (= 0 n) 0 (+ n ((Y sum) (1- n)))

® ln. IF (= 0 n) 0

(+ n ((lm. IF (= 0 m) 0 (+ m ((Y sum) (1- m))))

(1- n))))

Данное выражение ведет себя точно так же, как исходное рекурсивное определение sum. Внутреннее вхождение Y sum конструирует копию исходной функции sum, помещая само себя (т. е. Y sum) вместо s в тело копии.

Таким образом, функция sum выражается в l-исчислении в виде

Y(ls. ln. IF (= 0 n) 0 (+ n (s (1- n))))

Проверим:

(Y(ls. ln. IF (= 0 n) 0 (+ n (s (1- n))))) 1

® ln. IF (= 0 n) 0 (+ n ((Y(ls. ln. IF (= 0 n) 0 (+ n (s (1- n)))))

(1- n))) 1

® IF (= 0 1) 0 (+ 1 ((Y(ls. ln. IF (= 0 n) 0 (+ n (s (1- n)))))

(1- 1)))

® (+ 1 ((Y(ls. ln. IF (= 0 n) 0 (+ n (s (1- n))))) 0))

® (+ 1 (ln. IF (= 0 n) 0

(+ n ((Y(ls. ln....))))) 0)

® (+ 1 (IF (= 0 0) 0 (+ 0 ((Y (ls. ln....))))))

® (+ 1 0)

® 1

В общем случае рекурсивная функция f с телом, задаваемым выражением E, записывается в l-исчислении в виде Y (lf. E).

Определим комбинатор неподвижной точки Y следующим образом:

Y = lh. (lx. h (x x)) (lx. h (x x))

Проверим:

Yf=

(lh. (lx. h (x x)) (lx. h (x x))) f

® (lx. f (x x)) (lx. f (x x))

® f ((lx. f (x x)) (lx. f (x x)))

® f (Y f)