;;;; FUNCTIONS THAT GENERATE FUNCTIONS

;;; we can ask what are the conditions that allow us to find a
;;; tail recursive representation of a recursive function

;;; it is possible to prove that any primitive-recursive function
;;; has a tail recursive form

;;; in SCHEME we can construct the best possible proof of them all
;;; we can implement a function which does the transformation of
;;; a primitive-recursive function into a tail recursive form
;;; (we shall restrict ourselves to functions of one variable)

;;; first, we shall make a function that makes a primitive recursive
;;; function given a transformation and an initial value

(define (make-primitive-recursive transformation initial-value)
  (named-lambda (function n)
    (if (= n 0)
        initial-value
        (transformation n (function (- n 1))))))

;;; PROBLEM:

;;; define FACTORIAL with the help of MAKE-PRIMITIVE-RECURSIVE

;;; we can produce an equivalent iterative function with:

(define ((make-primitive-iterative transformation initial-value) n)
  (define (loop variable result)
    (if (= n variable)
        result
        (loop (+ variable 1) (transformation (+ variable 1) result))))
  (loop 0 initial-value))

;;; in TI SCHEME not just functions, but environments are first class objects
;;; and we can extract transformation and initial value out of a functional
;;; object created with the help of make-primitive-recursive.
;;; That allows us to define a function:

(define (recursive->iterative function)
  ((lambda (environment)
    (make-primitive-iterative
      (access transformation environment)
      (access initial-value environment)))
   (procedure-environment function)))

;;; PROBLEM:

;;; with the help of MAKE-PRIMITIVE-RECURSIVE and MAKE-PRIMITIVE-ITERATIVE
;;; implement functions MAKE-ADD-SELECT(PREDICATE) and
;;; MAKE-ADD-SELECT-ITERATIVE(PREDICATE) so that they return a function
;;; defined on non-negative integers such that for any integer N it returns
;;; the sum of those integers less-or-equal to N that satisfy PREDICATE
;;; define ADD-ODD as (make-add-select odd?) and ADD-ODD-ITERATIVE
;;; as (make-add-select-iterative odd?);
;;; what is the smallest integer i on your system such that
;;; (add-odd i) bombs and (add-odd-iterative i) does not?

;;; Now, what if the value of a function on N depends not just on the value on
;;; F(N-1), but on F(N-1) and F(N-2)?

(define (make-two-recursive transformation value-0 value-1)
  (named-lambda (function n)
    (cond ((= n 0) value-0)
          ((= n 1) value-1)
          (else
            (transformation n (function (- n 1)) (function (- n 2)))))))

;;; and the equivalent iterative function can be obtained with:

(define ((make-two-iterative transformation value-0 value-1) n)
  (define (loop variable first second)
    (if (= n variable)
        first
        (loop (1+ variable)
              (transformation (1+ variable) first second)
              first)))
  (if (= n 0) value-0
      (loop 1 value-1 value-0)))

(define (two-recursive->iterative function)
  ((lambda (environment)
    (make-two-iterative
      (access transformation environment)
      (access value-0 environment)
      (access value-1 environment)))
   (procedure-environment function)))

;;; PROBLEM:

;;; define a function FIB(n) which returns n-th fibonacci number
;;; with the help of TWO-RECURSIVE.
;;; time (fib 20)
;;; transform fib into an iterative function with the help of
;;; TWO-RECURSIVE->ITERATIVE
;;; time (fib 20)