;;;; 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)