* 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
#+BEGIN_SRC scheme
  (define (sum-integers a b)
    (if (> a b)
	0
	(+ a (sum-integers (+ a 1) b))))
#+END_SRC

one that computes the sum of cubes between a and b
#+BEGIN_SRC scheme
  (define (sum-cubes a b)
    (if (> a b)
	0
	(+ (cube a) (sum-cubes (+ a 1) b))))
#+END_SRC

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)
#+BEGIN_SRC scheme
  (define (pi-sum a b)
    (if (> a b)
	0
	(+ (/ 1.0 (* a (+ a 2))) (pi-sum (+ a 4) b))))
#+END_SRC

how can we abstract this?
#+BEGIN_SRC 
  (define (⟨name⟩ a b)
    (if (> a b)
        0
	(+ (⟨term⟩ a)
	   (⟨name⟩ (⟨next⟩ a) b))))
#+END_SRC

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,
#+BEGIN_SRC scheme :noweb yes :session s
  (define (sum term a next b)
    (if (> a b)
	0
	(+ (term a)
	   (sum term (next a) next b))))
#+END_SRC

back to sum-cubes
#+BEGIN_SRC scheme :session s
  (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)
#+END_SRC

#+RESULTS:
: 3025

#+BEGIN_SRC scheme :session s
  (define (identity x) x)
  (define (sum-integers a b)
    (sum identity a inc b))
  (sum-integers 1 10)
#+END_SRC

#+RESULTS:
: 55

#+BEGIN_SRC scheme :session s
  (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))
#+END_SRC

#+RESULTS:
: 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
#+BEGIN_SRC scheme :session s
  (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)
#+END_SRC

#+RESULTS:
: 0.24998750000000042

#+BEGIN_SRC scheme :session s
  (integral cube 0 1 0.001)
#+END_SRC

#+RESULTS:
: 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
#+BEGIN_SRC scheme
  (define (pi-sum a b)
    (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
	 a
	 (lambda (x) (+ x 4))
	 b))
#+END_SRC

and integral
#+BEGIN_SRC scheme
  (define (integral f a b dx)
    (* (sum f
	    (+ a (/ dx 2.0))
	    (lambda (x) (+ x dx))
	    b)
       dx))
#+END_SRC

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
#+BEGIN_SRC scheme
  (define (f x y)
    (define (f-helper a b)
      (+ (* x (square a))
	 (* y b)
	 (* a b)))
    (f-helper (+ 1 (* x y))
	      (- 1 y)))
#+END_SRC

or with an anonymous procedure
#+BEGIN_SRC scheme
  (define (f x y)
    ((lambda (a b)
       (+ (* x (square a))
	  (* y b)
	  (* a b)))
     (+ 1 (* x y))
     (- 1 y)))
#+END_SRC

this is so useful, we have let to make it easy
#+BEGIN_SRC scheme
  (define (f x y)
    (let ((a (+ 1 (* x y)))
	  (b (- 1 y)))
      (+ (* x (square a))
	 (* y b)
	 (* a b))))
#+END_SRC

let is syntactic sugar for lambda application

interesting:
#+BEGIN_SRC scheme
  (define x 2)
  (let ((x 3)
	(y (+ x 2)))
    (* x y))
#+END_SRC

#+RESULTS:
: 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
#+BEGIN_SRC scheme :noweb yes :session search
  (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))))))
#+END_SRC
assuming given a neg and pos point and f to begin

#+BEGIN_SRC scheme :session search
  (define (close-enough? x y)
    (< (abs (- x y)) 0.001))
  (define (average x y)
    (/ (+ x y) 2))
#+END_SRC

we can have a wrapper procedure to use the algo safely
#+BEGIN_SRC scheme :session search
  (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)
#+END_SRC

#+RESULTS:
: 3.14111328125

to find the root of x^3 - 2x - 3 - 0 between 1 and 2
#+BEGIN_SRC scheme :session search
  (half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3))
			1.0
			2.0)
#+END_SRC

#+RESULTS:
: 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
#+BEGIN_SRC scheme
  (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)
#+END_SRC

we could try to get sqrts this way
#+BEGIN_SRC scheme
  (define (sqrt x)
    (fixed-point (lambda (y) (/ x y))
		 1.0))
#+END_SRC
but it doesn't converge.
it will converge if we make modified guesses:
#+BEGIN_SRC scheme
  (define (sqrt x)
    (fixed-point (lambda (y) (average y (/ x y)))
		 1.0))
#+END_SRC
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
#+BEGIN_SRC scheme
  (define (average-damp f)
    (lambda (x) (average x (f x))))
  (define (average a b)
    (/ (+ a b) 2))
  ((average-damp square) 10)
#+END_SRC

we can use it for sqrts
#+BEGIN_SRC scheme
  (define (sqrt x)
    (fixed-point (average-damp (lambda (y) (/ x y)))
		 1.0))
#+END_SRC

*** NEWTON'S METHOD

 #+BEGIN_SRC scheme
   (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)
 #+END_SRC

*** 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.

#+BEGIN_SRC scheme
  (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))
#+END_SRC
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