(следующий код написан и протестирован в 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))
Теперь мы заменим выражения, которые создали функции продолжения (т. Е. lambda s), на использование контекстных конструкторов , и заменим (единственный) сайт, который применял функция продолжения с новой явной 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 или что-то в этом роде, и большинство версий считают, а не убирают, и надеются, что получат правильное сравнение, чтобы не получить ошибка "один на один".