;;;
;;; memoize.scm
;;;
;;; An Example on Memoization.
;;;
;;; pz, aDu, October 2000.
    
;;; Exercise 3.27 from SICP 2nd Edition, page 272.
;;;
;;; Memoization (also called tabulation) is a technique that enables a
;;; procedure to record, in a local table, values that have
;;; previously been computed.  This technique can make a vast
;;; difference in the performance of a program.  A memoized procedure
;;; maintains a table in which values of previous calls are stored
;;; using as keys the arguments that produced the values.  When the
;;; memoized procedure is asked to compute a value, it first checks
;;; the table to see if the value is already there and, if so, just
;;; returns that value.  Otherwise, it computes the new value in the
;;; ordinary way and stores this in the table.  As an example of
;;; memoization, recall from Section 1.2.2 the exponential process for
;;; computing Fibonacci numbers:


(define (fib n)
  (cond ((= n 0) 0)
	((= n 1) 1)
	(else (+ (fib (- n 1))
		 (fib (- n 2))))))


;;; The memoized version of the same procedure is:


(define memo-fib (memoize (lambda (n)
			    (cond ((= n 0) 0)
				  ((= n 1) 1)
				  (else (+ (memo-fib (- n 1))
					   (memo-fib (- n 2))))))))


;;; where the memoizer is defined as


(define (memoize f)
  (let ((table (make-table)))
    (lambda (x)
      (let ((previously-computed-result (lookup x table)))
	(or previously-computed-result
	    (let ((result (f x)))
	      (insert! x result table)
	      result))))))


;;; Draw an environment diagram to analyze the computation of
;;; (MEMO-FIB 3).  Explain why MEMO-FIB computes the Nth Fibonacci
;;; number is a number of steps proportional to N.  Would the scheme
;;; still work if we had simply defined MEMO-FIB to be (MEMOIZE FIB)?


;;; TABLE ABSTRACTION
;;;
;;; Here are the definitions for the table data abstraction.
;;; Notice that this uses mutation!


;;; make-table
;;;
;;; Our constructor.  Returns an empty table

(define (make-table) (list '*table*))


;;; lookup
;;;
;;; Sees if there is a record for a given key.

(define (lookup key table)
  (let ((record (assoc key (cdr table))))
    (if record
	(cdr record)
	false)))


;;; assoc
;;;
;;; Does the hard work for lookup.

(define (assoc key records)
  (cond ((null? records)
	 false)
	((equal? key (caar records))
	 (car records))
	(else
	 (assoc key (cdr records)))))


;;; insert!
;;;
;;; Inserts a new entry or modifies an old entry in the table.
;;; Uses mutation to make changes in place.
;;;
;;; Note that the ASSOC call cannot be replaced with a LOOKUP call as
;;; the mutating statements would not work (in any form), because the
;;; pointer to the ASSOC record would have been lost.
;;;
;;; Also notice that (SET-CDR! RECORD VALUE) could not be changed (in
;;; the case above) to (SET! RECORD VALUE) to compensate for using
;;; LOOKUP, as that would merely change the local value of RECORD (as
;;; defined in the LET), rather than mutating the contents of the
;;; table. 

(define (insert! key value table)
  (let ((record (assoc key (cdr table))))
    (if record
	(set-cdr! record value)
	(set-cdr! table
		  (cons (cons key value)
			(cdr table))))
    'ok))