(λ SICP)

These are notes on Structure and Interpretation of Computer Programs.

Building Abstractions with Procedures

Combinations

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

5 + 3 + ( 2 ( 3 ( 6 + 4 5 ) ) ) 3 ( 6 2 ) ( 2 7 ) \frac{5+3+(2-(3-(6+\frac{4}{5})))}{3(6-2)(2-7)}

may be represented as follows:

;; Evals to -37 / 150
(/
 (+ 5 (+ 4 (- 2 (- 3 (+ 6 (/ 4 5)))))) ;; numerator
 (* 3 (* (- 6 2) (- 2 7)))) ;; denominator

(Exercise 1.2)

Symbols, Evaluations

Defining symbols is done using the define operator

(define <sym> <expr>)

Whenever a combination involving sym is evaluated, sym is replaced by expr. Since 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.

Branching

Lisp/Scheme provides two branching operators, if and cond

(if <boolexpr> <branch1> <branch2>)

The above combination evaluates to branch1 if boolexpr evaluates to #t ("true"). Else, it evaluates to branch2.

cond works similarly:

(cond
    (<boolexpr1> <branch1>)
    (<boolexpr2> <branch2>)
    ...)

If nonte of the above boolean expressions (or predicates are defined), then the cond combination is undefined.

Procedures

Procedures are connstructed using the lamdba operator.

(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:

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

(Exercise 1.3)

This example exhibits the black box principle of software design. The sos-largest-numbers function was written before sq and 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.

Recursion, Iteration

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

Evaluating factorial1 requires O ( n ) O(n) expansions. And thus the interpreter must account for O ( n ) O(n) variables. In contrast, factorial2 only needs O ( 1 ) O(1) 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, O ( fib ( n ) ) O(\text{fib}(n)) time).

Higher-Order Procedures

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)

let construct

TODO

f ( x + h ) f ( x h ) 2 h \frac{f(x+h)-f(x-h)}{2h}