(jordyn sicp)

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)

(define (identity x) x)
(define (sum-integers a b)
  (sum identity a inc b))
(sum-integers 1 10)

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

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)

(integral cube 0 1 0.001)

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))

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)

to find the root of x³ - 2x - 3 - 0 between 1 and 2

(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
                      1.0
                      2.0)

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