У меня есть следующее математическое выражение:
; f(n) = f(n - 1) + f(n - 2) where n >= 2
; f(n) = n where n < 2`
Который я перевел в обычный рекурсивный вызов LISP:
(define (f n)
(cond ((< n 2) n)
(else (+ (f (- n 1))
(f (- n 2))))))
Как бы я перевел вышеизложенное в процедуру хвостовой рекурсии? Я не привык к функциональному программированию, поэтому немного борюсь.
Вы говорите об установленном примере хвостового рекурсивного преобразования для вычисления чисел Фибоначчи. Вы можете найти отличное описание с примерами кода по адресу эта глава SICP.
(Следующий код написан и протестирован в Racket.)
Начните с наивной версии:
;; fib : nat -> nat
(define (fib n)
(cond [(= n 0) 0]
[(= n 1) 1]
[else (+ (fib (- n 1)) (fib (- n 2)))]))
Когда мы разрабатываем новые версии, мы можем использовать test, чтобы увидеть, согласуются ли они с исходным fib (по крайней мере, для чисел от 0 до 9).
;; test : (nat -> nat) -> boolean
;; Check that the given function agrees with fib on 0 through 9
(define (test f)
(for/and ([i (in-range 10)])
(= (f i) (fib i))))
Во-первых, важное наблюдение, которое делает возможным все остальное, заключается в том, что когда мы вычисляем (fib N), мы вычисляем (fib (- N 1))... но мы отбрасываем его, и поэтому позже нам приходится вычислять его снова. Вот почему наивное fib имеет экспоненциальное время! Мы можем добиться большего успеха, сохранив его, скажем, с помощью вспомогательной функции, которая возвращает список:
;; fib2list : nat -> (list nat nat)
;; (fib2list N) = (list (fib (- N 1)) (fib N))
(define (fib2list n)
(cond [(= n 1) (list 0 1)]
[else (let ([resultN-1 (fib2list (- n 1))])
(let ([fibN-2 (first resultN-1)]
[fibN-1 (second resultN-1)])
(list fibN-1
(+ fibN-2 fibN-1))))]))
;; fib2 : nat -> nat
(define (fib2 n)
(cond [(= n 0) 0]
[else (second (fib2list n))]))
(test fib2) ;; => #t
Функция fib2list останавливается на 1, поэтому fib2 обрабатывает 0 как особый (но неинтересный) случай.
Мы можем переписать это в стиле передачи продолжения (CPS), чтобы сделать его рекурсивным:
;; fib3k : nat ((list nat nat) -> nat) -> nat
(define (fib3k n k)
(cond [(= n 1) (k (list 0 1))]
[else (fib3k (- n 1)
(lambda (resultN-1)
(let ([fibN-2 (first resultN-1)]
[fibN-1 (second resultN-1)])
(k (list fibN-1
(+ fibN-2 fibN-1))))))]))
;; fib3 : nat -> nat
(define (fib3 n)
(cond [(= n 0) 0]
[else (fib3k n (lambda (resultN)
(let ([fibN-1 (first resultN)]
[fibN (second resultN)])
fibN)))]))
(test fib3) ;; => #t
Теперь вместо рекурсивного вызова без хвостовой части fib3k вызывает себя с расширенным продолжением, которое принимает результат списка. Продолжение k из (fib3k N k) вызывается со списком, эквивалентным (list (fib (- N 1)) (fib N)). (Таким образом, если первый аргумент равен (- n 1), аргумент продолжения называется resultN-1 и т. д.)
Для начала мы предоставляем начальное продолжение, которое принимает результат resultN; второй элемент равен (fib N), поэтому мы возвращаем его.
Конечно, нет причин продолжать упаковывать вещи в список; мы можем просто заставить продолжение принимать два аргумента:
;; fib4k : nat (nat nat -> nat) -> nat
(define (fib4k n k)
(cond [(= n 1) (k 0 1)]
[else (fib4k (- n 1)
(lambda (fibN-2 fibN-1)
(k fibN-1
(+ fibN-2 fibN-1))))]))
;; fib4 : nat -> nat
(define (fib4 n)
(cond [(= n 0) 0]
[else (fib4k n (lambda (fibN-1 fibN) fibN))]))
(test fib4) ;; => #t
Обратите внимание, что в программе есть только два варианта продолжения --- они соответствуют двум вхождениям lambda в коде. Есть начальное продолжение, и есть единственный способ расширить существующее продолжение. Используя это наблюдение, мы можем преобразовать функции продолжения в структуру данных контекста:
;; A context5 is either
;; - (initial-context)
;; - (extend-context context5)
(struct initial-context ())
(struct extend-context (inner))
Теперь мы заменяем выражения, создающие функции продолжения (т. е. lambdas), на использование конструкторов контекста, а также заменяем (единственный) сайт, применяющий функцию продолжения, на новая явная функция apply-context5, выполняющая работу, ранее выполнявшуюся двумя выражениями lambda:
;; fib5ctx : nat context5 -> nat
(define (fib5ctx n ctx)
(cond [(= n 1) (apply-context5 ctx 0 1)]
[else (fib5ctx (- n 1)
(extend-context ctx))]))
;; apply-context5 : context5 nat nat -> nat
(define (apply-context5 ctx a b)
(match ctx
[(initial-context)
b]
[(extend-context inner-ctx)
(apply-context5 inner-ctx b (+ a b))]))
;; fib5 : nat -> nat
(define (fib5 n)
(cond [(= n 0) 0]
[else (fib5ctx n (initial-context))]))
(test fib5) ;; => #t
(Когда компиляторы делают это, они называют это дефункционализацией или преобразованием закрытия, и они делают это, чтобы превратить непрямые переходы в прямые переходы.)
На данный момент совершенно очевидно, что тип данных context совершенно скучен. На самом деле, это алгебраически эквивалентно натуральным числам! (Натуральное число равно нулю или является преемником натурального числа.) Итак, давайте просто изменим тип данных контекста, чтобы использовать натуральные числа, а не какую-либо структуру, распределенную в куче.
;; A context6 is just a natural number.
;; fib6ctx : nat context6 -> nat
(define (fib6ctx n ctx)
(cond [(= n 1) (apply-context6 ctx 0 1)]
[else (fib6ctx (- n 1)
(+ ctx 1))]))
;; apply-context6 : context6 nat nat -> nat
(define (apply-context6 ctx a b)
(cond [(= ctx 0)
b]
[else
(apply-context6 (- ctx 1) b (+ a b))]))
;; fib6 : nat -> nat
(define (fib6 n)
(cond [(= n 0) 0]
[else (fib6ctx n 0)]))
(test fib6) ;; => #t
Но теперь очевидно, что fib6ctx просто считает ctx в большую сторону, поскольку считает n в меньшую сторону до 1. В частности:
(fib6ctx N M) = (fib6ctx 1 (+ N M -1))
= (apply-context6 (+ N M -1) 0 1)
и так
(fib6ctx N 0) = (apply-context6 (+ N -1) 0 1)
Таким образом, мы можем полностью избавиться от fib6ctx.
;; apply-context7 : nat nat nat -> nat
(define (apply-context7 ctx a b)
(cond [(= ctx 0)
b]
[else
(apply-context7 (- ctx 1) b (+ a b))]))
;; fib7 : nat -> nat
(define (fib7 n)
(cond [(= n 0) 0]
[else (apply-context7 (- n 1) 0 1)]))
(test fib7) ;; => #t
И это традиционная итеративная версия Фибоначчи, за исключением того, что apply-context7 обычно называют fib-iter или что-то в этом роде, и большинство версий считают вверх, а не вниз, и надеются, что они получают правильное сравнение, поэтому они не получают ошибку «не на единицу».
