Topics to know:

• Types of evaluation
• Applicative order evaluation (all arguments must be fully evaluated before being plugged into parameters
• Normal order evaluation (arguments evaluated as needed within body of procedure
• Special Forms: Do not have to adhere to any particular form of evaluation (define, for example)
• Types of processes in recursion
• Recursive processes: eat up memory as deferred operations (such as * in the factorial example) must wait for recursive calls to complete.
• Iterative processes: save on memory by having state variables keep track of what is being computed.
• Orders of growth: How do we characterize the amount of time or space needed to run an algorithm?
• Exponential growth (such as the bad Fibonacci function): O(xⁿ) where x > 1
• Linear growth (such as a generic factorial function): O(n)
• Logarithmic growth (such as searching for a name in a phone book or fast-expt): O(log₂n)
• Polynomial growth: O(n^k)
• Constant growth (such as with arrays): O(n)
• Procedural abstraction (going from sum to accumulate)
• Procedures that return procedures (such as double, compose, and repeated)

Below is code from review during class

(require (lib "trace.ss"))  ; for testing only
(define (square x) (* x x))
(define (1+ x) (+ x 1))
(define (2+ x) (+ x 2))
(define (identity x) x)


(define (acc2 combiner id term a next b)
  (acc-iter combiner id term a next b))
(define (acc-iter combiner result term a next b)
  (cond ((> a b) result)
        (else (acc-iter combiner 
                        (combiner (term a) result)
                        term
                        (next a)
                        next 
                        b))))

; (trace acc-iter)
; (trace accumulate)

(define (double f)
  (lambda (x) (f (f x))))

;(double 1+) --> (lambda (x) (1+ (1+ x)))
;(double double) --> (lambda (x) (double (double x)))
;(double (double double)) -->
  ; (lambda (x) ((double double) ((double double) x)))   
;(define (f g)  
;  (g 2))

; f(g(x))
(define (compose f g)
  (lambda (x) (f (g x))))
; repeated (two different ways)
(define (repeated f n)
  (lambda (x)
    (cond ((= n 0) x)
          (else ((compose f (repeated f (- n 1))) x)))))

(define (repeated f n)
  (lambda (x)
    (cond ((= n 0) x)
          (else ((repeated f (- n 1)) (f x))))))


; pi/4: product, pi-term
(define (accumulate combiner id term a next b)
  (cond ((> a b) id)
        (else (combiner (term a)
                        (accumulate combiner id term (next a) next b)))))

(define (product term a next b) 
  (accumulate * 1 term a next b))

(define (pi-term n)
  (cond ((odd? n) (/ (+ n 1) (+ n 2)))
        (else (/ (+ n 2) (+ n 1)))))

(define (pi/4 terms)
  (product pi-term 1 1+ terms))

(define (pi terms)   ; Floating point nice for display purposes
  (* 4. (pi/4 terms)))

; An interval abstraction
(define make-interval cons)
(define lower car)
(define upper cdr)

; Another interval abstraction
(define (make-interval lower upper)
  (lambda (msg)
    (cond ((eq? msg 0) lower)
          ((eq? msg 1) upper))))
(define (lower interval) (interval 0))
(define (upper interval) (interval 1))

; Bottom line: Use lower and upper.  They work.  No guarantees about
;   how they are written though!