represent the simplest entities the language is concerned with
by which compound elements are built from simpler ones
by which compound elements can be named and manipulated as units
evaluate operator and operands when expanding
Substitute operand expression for parameters until it obtained an expression involving only primitive operators
Could cause redundant computations
Exercise 1.5
(define (p) (p))
(define (test x y)
(if (= x 0) 0 y))
(test 0 (p))
Applicative Order
(test 0 (p)) ->
(test 0 (p)) ->
(test 0 (p)) ->
...
Normal Order
(test 0 (p)) ->
(if (= 0 0) 0 (p)) -> ; only has primitive operator, start evaluating
(if #t 0 (p)) ->
0
successive approximations: whenever we have a guess 𝑦 for the value of the square root of a number 𝑥 , we can perform a simple manipulation to get a better guess by averaging 𝑦 with 𝑥/𝑦.
Real computers have limited precision on arithmetic operations, which makes them inadequate for very large and small numbers.
(define (sqrt-iter guess x)
(if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
(define (improve guess x)
(average guess (/ x guess)))
(define (average x y)
(/ (+ x y) 2))
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (square x) (* x x))
(define (sqrt x)
(sqrt-iter 1.0 x))
(sqrt 0.0001)
;(sqrt 10000000000000) never ends, (improve guess x) keeps on yielding one number whose square subtracts x larger than 0.001
Improved good-enough?:
; iterates until guess and next guess are equal
(define (good-enough? guess x)
(= (improve guess x) guess))
; or look at difference between iterations
(define (good-enough? guess x)
(<= (abs (- (improve guess x) guess))
(* guess .001)))
Because Scheme uses Applicative order.
(define (new-if predicate then-clause else-clause)
(cond (predicate then-clause)
(else else-clause)))
(define (sqrt-iter guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
; what happens
Because Scheme interpreter uses applicative order, when coming to new-if function, it will evaluate its parameters first, which means the newly if will always evaluate then-clause and else-clause. It is different from if, which evaluate then-clause first, and if false, then evaluate else-clause.
Back to this case, when interpreter tries to evaluate new-if, it will loop forever because of sqrt-iter parameter.
The meaning of a procedure definition isn’t related to the naming of bound variables. The set of expressions where a binding defines a variable is called the scope of that variable. E.g., procedure parameters: procedure difinition binds its formal paraters, whose body is scope of parameters.
Opposite of Bound Variable
Lexical scoping allows free variables being looked up in the enviroment where the procedures used them are defined.
Program variables provide a complete description of the state of the process at any point.
The length of chain and the amount of information needed grows linearly with n
Number of steps grows linearly with n
When describing a procedure as recursive, it means the procedure definition refers to the procedure itself. When describing a process as recursive, we focus on the way it’s evolving.
A linear iterative process can be generated by a recursive procedure.
Exercise 1.9
(define (+ a b)
(if (= a 0) b (inc (+ (dec a) b))))
(define (+ a b)
(if (= a 0) b (+ (dec a) (inc b))))
first one is a recursive process, second is iterative process.
Execute an iterative process in constant space, even if the iterative process is described by a recursive procedure. With a tail-recursive implementation, iteration can be expressed using the procedure call mechanism instead of loop structures.
Computation steps grows exponentially with the input. Space required grows linearly with the input. One use case: List interpreter using Applicative Order
Define an invariant quantity that remains unchanged from state to state.
Example
Exercise 1.16
keep ab^n unchanged.
(define (fast-expt b n)
(define (fast-expt-iter a b n)
(cond ((= n 0) 1)
((= n 1) (* a b))
((even? n) (fast-expt-iter a (* b b) (/ n 2)))
(else (fast-expt-iter (* a b) b (- n 1)))))
(fast-expt-iter 1 b n))
Factorial
; Recursive
(define (fact n)
(if (= n 0)
1
(* n (fact (- n 1)))))
; Iterative
(define (fact n)
(define (fact-iter acc n)
(if (= n 0)
acc
(fact-iter (* n acc) ( - n 1))))
(fact-iter 1 n))
; Algorithms + Threading
; from https://www.youtube.com/watch?v=b1aAjlNnxT8&list=PLVFrD1dmDdvdvWFK8brOVNL7bKHpE-9w0&index=2
(require threading)
(define (fact n)
(~> (range 1 (+ n 1))
(foldl * 1 _)))
Fibonacci
; Recursive
(define (fib n)
(cond ((= n 0) 0)
((= n 1) 1)
(else (+ (fib (- n 1))
(fib (- n 2))))))
; Iterative
(define (fib n)
(fib-iter 1 0 n))
(define (fib-iter a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))
If r is the remainder when a is divided by b, then the common divisors of a and b are precisely the same as the common divisors of b and r.
; GCD(a, b) = GCD(b, r)
(define (gcd a b)
(if (= b 0)
a
(gcd b (remainder a b))))
Lamé’s Theorem
If Euclid’s Algorithm requires k steps to the gcd of some pair, then the smaller number in the pair must be greater than or equal to the k th Fibonacci number.
So, O(lgn).
(define (smallest-divisor n) (find-divisor n 2))
(define (find-divisor n test-divisor)
(cond ((> (square test-divisor) n) n)
((divides? test-divisor n) test-divisor)
(else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b) (= (remainder b a) 0))
(define (prime? n)
(= n (smallest-divisor n)))
Fermat’s Little Theorem
If 𝑛 is a prime number and 𝑎 is any positive integer, then 𝑎 raised to the 𝑛 th power is congruent to 𝑎 modulo 𝑛 .
a^n % n = a % n
Carmichael numbers.
Numbers that fool the Fermat test. Little is known about them other than that they are extremely rare. There are 255 Carmichael numbers below 100,000,000. The smallest few are 561, 1105, 1729, 2465, 2821, and 6601
Implementation
(x * y) % m = ((x % m) * (y % m)) % m
(define (expmod base exp m)
(cond ((= exp 0) 1)
((even? exp)
(remainder
(square (expmod base (/ exp 2) m))
m))
(else
(remainder
(* base (expmod base (- exp 1) m))
m))))
(define (fermat-test n)
(define (try-it a)
(= (expmod a n n) a))
(try-it (+ 1 (random (- n 1)))))
(define (fast-prime? n times)
(cond ((= times 0) true)
((fermat-test n) (fast-prime? n (- times 1)))
(else false)))
Summation
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
; Iterative Form, exercise 1.30
(define (sum-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (+ result (term a)))))
(iter a 0))
; sum a range of integers
(define (inc x) (+ x 1))
(define (identity x) x)
(define (sum-integers a b)
(sum identity a inc b))
Simpson’s Rule to compute integral
; exercise 1.29
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
(define (simpson f a b n)
(define h (/ (- b a) n))
(define (y k) (f (+ a (* k h))))
(define (term k)
(* (cond ((or (= k 0) (= k n)) 1)
((even? k) 2)
(else 4))
(y k)))
(define (next k) (+ k 1))
(* (/ h 3) (sum term 0 next n)))
(define (cube x) (* x x x))
Product
; exercise 1.31
(define (next x) (+ x 1))
(define (product term a next b)
(if (> a b)
1
(* (term a) (product term (next a) next b))))
(define (product-iter term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (* result (term a)))))
(iter a 1))
(define (pi n)
(define (pi-term n)
(if (even? n)
(/ (+ n 2) (+ n 1))
(/ (+ n 1) (+ n 2))))
(* (product pi-term 1 next n) 4))
Accumulate
Summation and product can be further abstracted into a more general form, which is accumulate.
; exercise 1.32
(define (accumulate combiner null-value term a next b)
(if (> a b)
null-value
(combiner (term a) (accumulate combiner null-value term (next a) next b))))
(define (accumulate-iter combiner null-value term a next b)
(define (iter a result)
(if (> a b)
result
(iter (next a) (combiner (term a) result))))
(iter a null-value))
Add a filter:
; exercise 1.33
(define (filtered-accumulate filter combiner null-value term a next b)
(if (> a b)
null-value
(if (filter a)
(combiner (term a)
(filtered-accumulate filter combiner null-value term (next a) next b))
(filtered-accumulate filter combiner null-value term (next a) next b))))
(lambda ( ⟨ formal-parameters ⟩ ) ⟨ body ⟩ )
;e.g.
(define (plus4 x) (+ x 4))
;is equal to
(define plus4 (lambda (x) (+ x 4)))
; lambda can be used as an operator
((lambda (x y z) (+ x y (square z)))
1 2 3)
let
A syntactic sugar for the underlying lambda application.
((lambda (<var1> ... <varn>)
<body>)
<exp1>
...
<expn>)
; -->
(let ((<var1> <exp1>)
(<var2> <exp2>)
...
(<varn> <expn>))
<body>)
(define x 2)
(let ((x 3)
(y (+ x 2)))
(* x y))
; y -> 4
; output: 12
(define (f g) (g 2))
(f f)
(f 2)
(2 2)
Finding fixed points of functions
f(x) = x, can be found through applying f repeatedly(define tolerance 0.00001)
(define (fixed-point f first-guess)
(define (close-enough? v1 v2)
(< (abs (- v1 v2))
tolerance))
(define (try guess)
(let ((next (f guess)))
(if (close-enough? guess next)
next
(try next))))
(try first-guess))
Average damping
Square root can be found using fixed-point, f(y) = x / y.
However, fixed-point can not converge, because 𝑦3 = 𝑥/𝑦2 = 𝑥/(𝑥/𝑦1 ) = 𝑦1.
To prevent this happening, new guess should not changed so much.
Change to f(y) = (y + x / y) / 2.
When converge is impossible: the function f(x) is a curve symmetric about the y=x axis. How to avoid: average-damping
Example: generate average dumping functions
(define (average-damp f) (lambda (x) (average x (f x))))
Exercise 1.41
Run a function twice.
(define (double p) (lambda (x) (p (p x))))
(((double (double double)) inc) 5)
; output: 21
Exercise 1.42
Compose two functions together.
(define (compose f g) (lambda (x) (f (g x))))
((compose square inc) 6)
; output: 49
Exercise 1.43
Compute the nth repeated application of a function.
(define (repeated f k)
(define (compose f g) (lambda (x) (f (g x))))
(define (iter rf k)
(if (= k 1)
rf
(iter (compose rf f) (- k 1))))
(iter f k))
Exercise 1.44
(define dx 0.00001)
(define (average x y z) (/ (+ x y z) 3.0))
(define (smooth f)
(lambda (x) (average (f (- x dx)) (f x) (f (+ x dx)))))
(define (n-fold-smooth f n) ((repeated smooth n) f))
Exercise 1.45
see DEVONThink
If 𝑥 ↦ 𝑔(𝑥) is a differentiable function, then a solution of the equation 𝑔(𝑥) = 0 is a fixed point of the function 𝑥 ↦→ 𝑓 (𝑥) , where 𝑓 (𝑥) = 𝑥 − 𝑔(𝑥) / 𝐷𝑔(𝑥).
(define dx 0.00001)
(define (deriv g)
(lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))
(define (newton-transform g)
(lambda (x) (- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))
; square root by average dump
(define (sqrt x)
(fixed-point-of-transform
(lambda (y) (/ x y)) average-damp 1.0))
; square root by newton method
(define (sqrt x)
(fixed-point-of-transform
(lambda (y) (/ x y)) newton-transform 1.0))
Elements with first class status:
To compute something, start with an initial guess for the answer, test if the guess is good enough, otherwise improve the guess and continue the process.
(define (iterative-improve test-good improve)
(define (iter guess)
(if (test-good guess)
guess
(iter (improve guess))))
(lambda (x) (iter x)))
; Better Solution
(define (iterative-improve good-enough? improve)
(lambda (guess)
(if (good-enough? guess)
guess
((iterative-improve good-enough? improve) (improve guess)))))