#lang scheme

#| Computation is on the way out/back, on the return values.
   Post-order computation.

Waiting computation must be kept around,
 typically on the "run time stack".

(list-length '(a b c))
  (+ 1 (list-length '(b c)))
     (+ 1 (list-length '(c)))
       (+ 1 (list-length '())) |#

#;(define list-length
    (lambda (l)
      (if (empty? l) 0
          (+ 1 (list-length (rest l))))))

#| Computation is on the way in, via an "accumulator" argument.
   Pre-order computation.

Scheme will not keep the functions around on the stack,
 since they don't do anything on the way back.

Tail recursion: recursions are the *last* thing done.

(list-length '(a b c))
  (list-length-accumulator '(a b c) 0)
    (list-length-accumulator '(b c) 1)
      (list-length-accumulator '(c) 2)
        (list-length-accumulator '() 3) |#

(define list-length
    (local [#| Length of l + length-so-far. |#
            (define list-length-accumulator
              (lambda (l length-so-far)
                (if (empty? l) length-so-far
                    (list-length-accumulator (rest l) (+ 1 length-so-far)))))]
      (lambda (l) (list-length-accumulator l 0))))

(define reverse
  (local [(define reverse-accumulator
            (lambda (l reverse-so-far)
              (if (empty? l) reverse-so-far
                  (reverse-accumulator (rest l)
                                       (cons (first l) reverse-so-far)))))]
    (lambda (l) (reverse-accumulator l '()))))

#| 1 1 2 3 5 8 13 21 ...
  f_0 = 1
  f_1 = 1
  f_n = f_(n-2) + f_(n-1)

Return f_n for n an integer >= 0. |#

#|
  Direct translation has exponential (~2^n) calls.

  (fib 32):
    (+ (fib 30) (fib 31))
      (fib 30):
        (+ (fib 28) (fib 29))
        (fib 28):
          ...
        (fib 29):
          ...
      (fib 31):
        (+ (fib 29) (fib 30))
        (fib 29): - even though already did it above for (fib 30)
          ... |#

#;(define fib
    (lambda (n)
      (if (<= n 1) 1
          (+ (fib (- n 2)) (fib (- n 1))))))

(define fib
  (lambda (n)
    (local [#| Return f_n given f_k-1 f_k for some k <= n. |#
            (define fib-accumulator
              (lambda (k f_k-1 f_k)
                (if (= k n) f_k
                    (fib-accumulator (+ k 1) f_k (+ f_k-1 f_k)))))]
      (fib-accumulator 0 0 1))))