These are notes on Structure and Interpretation of Computer Programs.
Building Abstractions with Procedures
Lisp combinations are written using prefix form:
(operator operand1 operand2 ...)
The operator and operands above may themselves be combinations or perhaps atoms (e.g. numbers, symbols, procedures). Every combination "reduces" to an atom.
For example, the mathematical expression
may be represented as follows:
;; Evals to -37 / 150 (/ (+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5)))))) ;; numerator (* 3 (* (- 6 2) (- 2 7)))) ;; denominator
Defining symbols is done using the
(define <sym> <expr>)
Whenever a combination involving
sym is evaluated,
sym is replaced by
expr may itself involve symbols, this process continues until
only primitives exists. This is the "expansion phase".
The application of operators on evaluated operands will also result in a lisp expression. This is the "reduction phase".
Normal-order evaluation fully expands (but not evaluates) all expressions before reduction.
Applicative-order evaluation fully evaluates each expression before reduction.
Lisp/Scheme provides two branching operators,
(if <boolexpr> <branch1> <branch2>)
The above combination evaluates to
boolexpr evaluates to
Else, it evaluates to
cond works similarly:
(cond (<boolexpr1> <branch1>) (<boolexpr2> <branch2>) ...)
If nonte of the above boolean expressions (or predicates are defined), then
cond combination is undefined.
Procedures are connstructed using the
(lambda (<sym1> <sym2> ...) <expr>)
Lambda expressions themselves produce operators. When applied to operands and
evaluated, those operands are substituted for the above symbol list (the arguments)
are substituted in
expr (the body).
Lambdas may have any number of arguments, including zero.
Lambdas are first-class objects in Lisp. This means:
- They can be named
- They can be used as arguments to procedures
- They can be returned from procedures
- They can be members of data structures
Naming lambdas can be done using
define in two ways
;; using define in the typical manner (define <name> (lambda (<arg1> <arg2> ...) <body>)) ;; syntax sugar for above (define (<name> <arg1> <arg2> ...) <body>)
For example, the following
sos-largest-numbers procedure takes three numerical
arguments and returns the sum of the square of the largest two:
(define (sos-largest-numbers x y z) (- (+ (sq x) (+ (sq y) (sq z))) (sq (min3 x y z)))) (define (sq x) (* x x)) (define (min3 x y z) (min2 (min2 x y) z)) (define (min2 x y) (if (> x y) y x)) (sos-largest-numbers 3 8 7) ;; => 113
This example exhibits the black box principle of software design. The
sos-largest-numbers function was written before
min3. It didn't
matter how these functions were implemented, provided that they were
implemented correctly with regards to their expected behavior. If this
so, then these procedures could even be delegated to different programmers.
Procedures can reference themselves. This is known as recursion.
Consider the following two procedures, one to calculate the factorial of a positive integer, the other to calculate a term in the fibonacci sequence:
(define (factorial1 n) (if (= n 1) 1 (* n (factorial1 (- n 1))))) (define (factorial2 n) (define (iter prod cnt max-cnt) (if (> cnt max-cnt) prod (iter (* cnt prod) (+ cnt 1) max-cnt))) (iter 1 1 n)) (- (factorial1 6) (factorial2 6)) ;; => 0
factorial1 requires expansions. And thus the interpreter must account for variables. In contrast,
factorial2 only needs variables to evaluate. This is called
an iterative process. Note the difference between process and
procedures. Both procedures are recursive.
Not all recursive procedures can be easily translated to iterative processes. For example, the following inefficiently calculates fibonacci numbers:
(define (fib n) (if (< n 2) n (+ (fib (- n 1)) (fib (- n 2)))))
This takes exponential time (rather, time).
Lambdas may be supplied input arguments or returned from other lambdas. When a lambda does both, it is called a higher-order procedure.
For example, the following defines a
integrate procedure that calculates the
via simpson's rule. It used layers of higher-ordered functions.
(define (integrate fn a b) (simpsons-rule fn a b 1000)) (define (simpsons-rule fn a b n) (define (incr n) (+ n 1)) (define (term n) ;; 1,4,2,1,4,2,... (define m (modulo n 3)) (cond ((= m 1) 1) ((= m 2) 4) ((= m 3) 2))) (define h (/ (- b a) n)) (* (/ h 3) (sum term 1 incr n))) ;; sums up term(n) for n ranging from a, next(a), next(next(a)), ... up to b. (define (sum term a next b) (accumulate + 0 term a next b)) ;; iterative function fo accumulating a "combiner" function (define (accumulate combiner null-value term a next b) (define (iter a result) (if (> a b) result (iter (next a) (combiner result (term a))))) (iter a null-value)) ;; test (define (cube x) (* x (* x x))) ;; anti-derivative = 1/4 x^4 (integrate cube 0 2) ;; => ~ 81/4
(Exercise 1.32 and Exercise 1.29)