2.1 Building Abstractions with Procedures
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.
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.
(define square (lambda (x) (* x x))) (square 3) 9
(define (cube x) (* x x x)) (cube 3) 27
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.
syntax
(cond (<p1> <e1>) (<p2> <e2>) .. (<pn> <en>))
syntax
(if <predicate> <consequent> <alternative>)
There are three frequently used logical composition operators:
syntax
(and <e1> .. <en>)
syntax
(or <e1> .. <en>)
syntax
(not <e>)
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
(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.
(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.
(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.
(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.
syntax
(lambda (<parameters>) <body>)
syntax
(let ((<var1> <exp1>) (<var2> <exp2>) .. (<varn> <expn>)) <body>)
An interesting pattern is the algorithm to find fixed points of a function by repeatedly applying that function starting from some point.