►Documentation
▼2 SICP
8.1
    ← prev  up  next → 

2.1 Building Abstractions with Procedures

Every powerful language has three mechanisms:

  • primitive expressions

  • means of combination

  • means of abstraction.

Expressions formed by delimiting a list of expressions within parentheses in order to denote procedure application are called combinations. The leftmost element in the list is called the operator, and the other elements are called operands. So for example

(+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))

57

In Scheme, it’s possible to name things with define.

The most simple model to interpret a combination is by substitution:

  • evaluate the subexpression of the combination,

  • apply the procedure to the values of the operands.

This doesn’t apply to definitions, which are special forms and not combinations.

A procedure can be defined with a lambda function or a special form:
(define square
  (lambda (x) (* x x)))
(square 3)

9

(define (cube x)
  (* x x x))
(cube 3)

27

The general form of a procedure definition is

syntax

(define (<name> <formal parameters>) <body>)

The substitution interpretation is as follows: to apply a compound procedure to arguments, evaluate the body of the procedure with each formal parameter replaced by the corresponding argument.

This models breaks down when working with mutable data, as we will see.

Lisp has a special form for conditionals

syntax

(cond (<p1> <e1>)
      (<p2> <e2>)
      ..
      (<pn> <en>))
where each clause consists of a predicate and an expression. The last predicate is allowed to be the special symbol else, which always evaluates to true.

Another conditional form is

syntax

(if <predicate>
  <consequent>
  <alternative>)

There are three frequently used logical composition operators:

syntax

(and <e1> .. <en>)

which evaluates the expression one at a time, and if any one evaluates to false then its value is false,

syntax

(or <e1> .. <en>)

which evaluates to true if any expression evaluates to true,

syntax

(not <e>)

which evaluates to true if and only if the value of the expression is false.

It’s possible to nest definitions as in the following example:

(define (abs x)
  (if (< x 0) (- x) x))
(define (distance x y)
  (abs (- x y)))
(define (average x y)
  (/ (+ x y) 2))
(define (sqrt x)
  (define tolerance 0.001)
  (define (good-enough? guess)
    (< (distance (square guess) x) tolerance))
  (define (step guess)
    (average guess (/ x guess)))
  (define (iter guess)
    (if (good-enough? guess)
      guess
      (iter (step guess))))
  (define initial-guess 1.0)
  (iter initial-guess))
(sqrt 2)

1.4142156862745097

 

The difference between recursion and iteration can be illustrated with the factorial function:

(define (factorial n)
  (if (= n 1)
    1
    (* n (factorial (- n 1)))))
(define (factorial-iter n)
  (define (iter i n accumulator)
    (if (> i n)
      accumulator
      (iter (+ 1 i) n (* accumulator i))))
  (iter 1 n 1))

The first implementation can be interpreted as follows:

(factorial 4)
(* 4 (factorial 3))
(* 4 (* 3 (factorial 2)))
(* 4 (* 3 (* 2 (factorial 1))))
(* 4 (* 3 (* 2 1)))
(* 4 (* 3 2))
(* 4 6)
24

while the seconds as follows:
(factorial-iter 4)
(iter 1 4 1)
(iter 2 4 1)
(iter 3 4 2)
(iter 4 4 6)
(iter 5 4 24)
24

Tail call elimination is assumed.

Another common pattern is tree recursion, illustrated in the bad implementation of Fibonacci function:
(define (fibonacci n)
  (cond ((= 0 n) 0)
        ((= 1 n) 1)
        (else (+ (fibonacci (- n 1))
                 (fibonacci (- n 2))))))

The number of times this procedure calls (fib 1) and (fib 0) is exactly (fib (+ n 1)), and (fib n) is the closest integer to φⁿ/√5.

An iterative implementation can be given as follows:
(define (fibonacci-iter n)
  (define (iter i x y)
    (if (> i n)
      y
      (iter (+ i 1) y (+ x y))))
  (iter 2 0 1))

One should not conclude from this that tree-recursive processes are useless. When we consider processes that operate on hierarchically structured data rather than numbers, we will find that tree recursion is a natural and powerful tool.

Another funky thing is the Fermat primality test. Recall that for prime fields the Frobenius endomorfism is the identity. One can use this as a test:
(require math/number-theory)
(define (fermat-prime? n)
  (define (test x)
    (= (modular-expt x n n) x))
  (test (+ 1 (random (- n 1)))))

Yet this test is fooled by Carmichael numbers: 561, 1105, 1729 and so on. Fast probabilistic algorithms are useful.

 

High order functions allows us to abstract many patterns, and provide a syntactical closure.

The lambda form is:

syntax

(lambda (<parameters>) <body>)

It’s possible to use a let form to specify local parameters:

syntax

(let ((<var1> <exp1>)
      (<var2> <exp2>)
      ..
      (<varn> <expn>))
     <body>)
which is syntactic sugar for a corresponding lambda.

An interesting pattern is the algorithm to find fixed points of a function by repeatedly applying that function starting from some point.

    ← prev  up  next →