notes.org 9.3 KB
- 1.3 Formulating Abstractions with Higher-Order Procedures
1.3 Formulating Abstractions with Higher-Order Procedures
procedures are abstractions that describe compound operations
(define (cube x) (* x x x))
is not about any number in particular, but how to cube any number
it describes 'how to'
one thing we should demand from a language is the ability to build abstractions by assigning names to common patterns.
operating only on numbers is limiting. let's operate on procedures!
- higher-order procedure
-
a procedure that manipulates procedures
1.3.1 Procedures as Arguments
consider these three procedures:
one that computes the sum of ints between a and b
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))
one that computes the sum of cubes between a and b
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b))))
one that computes the sum of the following series
1 1 1 —– + —– + —— 1*3 5*7 9*11
which converges to π/8 slowly (thanks leibniz)
(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))
how can we abstract this?
(define (⟨name⟩ a b)
(if (> a b)
0
(+ (⟨term⟩ a)
(⟨name⟩ (⟨next⟩ a) b))))
this is the summation of series ie sigma notation
b 𝚺 f(n) = f(a) + … + f(b) n=a
the value of sigma notation is to allow mathematicians to deal with the concept of summation itself
so for the abstraction,
(define (sum term a next b)
(if (> a b)
0
(+ (term a)
(sum term (next a) next b))))
back to sum-cubes
(define (inc n) (+ n 1))
(define (cube x) (* x x x))
(define (sum-cubes a b)
(sum cube a inc b))
(sum-cubes 1 10)
3025
(define (identity x) x)
(define (sum-integers a b)
(sum identity a inc b))
(sum-integers 1 10)
55
(define (pi-sum a b)
(define (pi-term x)
(/ 1.0 (* x (+ x 2))))
(define (pi-next x)
(+ x 4))
(sum pi-term a pi-next b))
(* 8 (pi-sum 1 1000))
3.139592655589783
you can approx an integral with the sum b ∫ f = [ f(a + dx/2) + f(a + dx + dx/2) + f(a + 2dx + dx/2) + … ]dx a
(define (integral f a b dx)
(define (add-dx x) (+ x dx))
(* (sum f (+ a (/ dx 2.0)) add-dx b)
dx))
(integral cube 0 1 0.01)
0.24998750000000042
(integral cube 0 1 0.001)
0.249999875000001
1.3.2 Constructing Procedures Using Lambda
kinda clumsy to have to define a function for even small operations, such as the pi-term and pi-next in pi-sum
can define a function in place:
(lambda (x) (+ x 4))
so, pi-sum can be expressed
(define (pi-sum a b)
(sum (lambda (x) (/ 1.0 (* x (+ x 2))))
a
(lambda (x) (+ x 4))
b))
and integral
(define (integral f a b dx)
(* (sum f
(+ a (/ dx 2.0))
(lambda (x) (+ x dx))
b)
dx))
lambdas are simply unnamed procedures. the term lambda comes from Alonzo Church who developed λ calculus.
using let to create local variables
sometimes we want more vars than defined by the formal args.
for example,
f(x, y) = x(1+xy)^2 + y(1-y) + (1+xy)(1-y)
can be expressed
a = 1 + xy
b = 1 - y
f(x,y) = xa^2 + yb + ab
this could be articulated with an auxillery procedure
(define (f x y)
(define (f-helper a b)
(+ (* x (square a))
(* y b)
(* a b)))
(f-helper (+ 1 (* x y))
(- 1 y)))
or with an anonymous procedure
(define (f x y)
((lambda (a b)
(+ (* x (square a))
(* y b)
(* a b)))
(+ 1 (* x y))
(- 1 y)))
this is so useful, we have let to make it easy
(define (f x y)
(let ((a (+ 1 (* x y)))
(b (- 1 y)))
(+ (* x (square a))
(* y b)
(* a b))))
let is syntactic sugar for lambda application
interesting:
(define x 2)
(let ((x 3)
(y (+ x 2)))
(* x y))
12
y is 4, not 5.
1.3.3 Procudures as General Methods
a powerful form of abstraction: procedures that express general methods of computation, regardless of particular functions involved.
finding roots of equations by the half-interval method
the half-interval method is a way to find the roots of an equation, that is, when f(x) = 0. here it is:
-
given points a and b
-
f(a) < 0 < f(b)
-
-
there must be a zero in between
-
let x be the average of a and b
-
if f(x) > 0
-
there must be a zero between a and x
-
-
if f(x) < 0
-
there must be a zero between b and x
-
-
repeat
(define (search f neg-point pos-point)
(let ((midpoint (average neg-point pos-point)))
(if (close-enough? neg-point pos-point)
midpoint
(let ((test-value (f midpoint)))
(cond ((positive? test-value)
(search f neg-point midpoint))
((negative? test-value)
(search f midpoint pos-point))
(else midpoint))))))
assuming given a neg and pos point and f to begin
(define (close-enough? x y)
(< (abs (- x y)) 0.001))
(define (average x y)
(/ (+ x y) 2))
we can have a wrapper procedure to use the algo safely
(define (half-interval-method f a b)
(let ((a-value (f a))
(b-value (f b)))
(cond ((and (negative? a-value) (positive? b-value))
(search f a b))
((and (negative? b-value) (positive? a-value))
(search f b a))
(else
(error "Values are not of opposite sign" a b)))))
(half-interval-method sin 2.0 4.0)
3.14111328125
to find the root of x^3 - 2x - 3 - 0 between 1 and 2
(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3)) 1.0 2.0)
1.89306640625
finding fixed points of functions
a fixed point is where f(x) = x with some functions, you can find a fixed point by making a guess and applying f repeatedly:
f(x), f(f(x)), f(f(f(x))) ...
until the value doesn't change much
(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))
(fixed-point cos 1.0)
(fixed-point (lambda (y) (+ (sin y) (cos y)))
1.0)
we could try to get sqrts this way
(define (sqrt x)
(fixed-point (lambda (y) (/ x y))
1.0))
but it doesn't converge. it will converge if we make modified guesses:
(define (sqrt x)
(fixed-point (lambda (y) (average y (/ x y)))
1.0))
averaging successive approaches (as seen here and the og sqrt procedure of 1.1.7) is called average dampening
1.3.4 Procedures as Returned Values
passing procedures as arguments is neat. returning functions is even better!
average dampening is a useful general technique
(define (average-damp f)
(lambda (x) (average x (f x))))
(define (average a b)
(/ (+ a b) 2))
((average-damp square) 10)
we can use it for sqrts
(define (sqrt x)
(fixed-point (average-damp (lambda (y) (/ x y)))
1.0))
NEWTON'S METHOD
(define (deriv g)
(lambda (x)
(/ (- (g (+ x dx)) (g x))
dx)))
(define dx 0.00001)
(define (cube x) (* x x x))
((deriv cube) 5)
(define (newton-transform g)
(lambda (x)
(- x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
(fixed-point (newton-transform g) guess))
(define (sqrt x)
(newtons-method (lambda (y) (- (square y) x))
1.0))
(sqrt 36)
abstractions and first-class procedures
we've done two sqrts, one with fixed-point search and one with newton's method. each takes a func and finds the fixed point of some transformation of the func.
(define (fixed-point-of-transform g transform guess)
(fixed-point (transform g) guess))
(define (sqrt x)
(fixed-point-of-transform (lambda (y) (/ x y))
average-damp
1.0))
(define (sqrt2 x)
(fixed-point-of-transform (lambda (y) (- (square y) x))
newton-transform
1.0))
neat! tbh i dont fully understand what's going on, but seems cool. i have some idea of the implications. need to spend more time with the math.
!! we programmers should be alert to the underlying abstractions in our programs and build upon and generalize them. thats not to say we should write in the most abstract way possible.
programming languages impose restrictions on how elements can be manipulated. elements with the fewest restrictions are first class.
some first-class rights:
-
they may be named by variables
-
they may be passed as args to procedures
-
they may be returned as results of procedures
-
they may be included in data structures