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
^{n}) 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
_{2}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!