* Lecture 2A: Higher Order Procedures
https://youtu.be/eJeMOEiHv8c

we now know how to write lisp--we might be under the dilusion that
this is just basic or pascal with a funny syntax 

today we will disabuse ourself of that idea

to add up integers

 b
 𝚺 i
i=a

#+BEGIN_SRC scheme
  (define (sum-int a b)
    (if (> a b)
        0
        (+ a
           (sum-int (+ a 1) b))))
#+END_SRC
GJS says at this point, reading such a def should be easy. coming up
with such a thing might still be challenging. that's reassuring!


 b
 𝚺 i^2
i=a

#+BEGIN_SRC scheme
  (define (sum-sq a b)
    (if (> a b)
        0
        (+ (square a)
           (sum-sq (1+ a) b))))
#+END_SRC

for leibniz way of finding pi/8,
#+BEGIN_SRC scheme
  (define (pi-sum a b)
    (if (> a b)
        0
        (+ (/ 1 (* a (+ a 2)))
           (pi-sum (+ a 4) b))))
#+END_SRC

three variations an identical technique

any programing language has idioms, we can give the knowledge of the
idiom a name in lisp

#+BEGIN_SRC scheme
  (define (sum term a next b)
    (if (< a b)
        0
        (+ (term a)
           (sum term
                (next a)
                next
                b))))
#+END_SRC

we can easily translate those old programs to sum
#+BEGIN_SRC scheme
  (define (sum-int a b)
    (define (identity a) a)
    (sum identity a 1+ b))

  (define (sum-squares a b)
    (sum square a 1+ b))

  (define (pi-sum a b)
    (sum (λ (i) (/ 1 (* i (+ i 2))))
         a
         (λ (i) (+ i 4))
         b))
#+END_SRC
  
  f  y + y/x
y ↦  -------
        2

f(√x) = √x

look for fixed point (give an input and get the input as output)

#+BEGIN_SRC scheme
  (define (sqrt x)
    (fixed-point (λ (y) (average (/ x y) y))
                 1))
#+END_SRC
write this by "wishful thinking"
we don't have fixed-point yet but we wish we did
#+BEGIN_SRC scheme
  (define (fixed-point f start)
    (define (iter old new)
      (if (close-enuf? old new)
          new
          (iter new (f new))))
    (iter start (f start)))
#+END_SRC

its actually easier than this! wow!

why does this work? why does it converge?

for sqrt, without the averaging, it oscilates about the value (see
book notes)

#+BEGIN_SRC scheme
  (define (sqrt x)
    (fixed-point
     (average-damp (lambda (y) (/ x y)))
     1))
#+END_SRC

average damp takes a procedure and returns a procedure that averages
the value before and after running the procedure. 
we identified it by wishful thinking.

#+BEGIN_SRC scheme
  (define average-damp
    (lambda (f)
      (lambda (x) (average (f x) x))))
#+END_SRC

we've seen higher order procedures that can operate on procedures,
let's have some fun with it. back to newton's method.

: to find a y such that 
:       f(y) = 0
: start with a guess, y0
: y n+1 is yn - f(yn)/derivative wrt y of f eval at y = yn

the math notation is strange, even gjs doesn't like it. im not gonna
write latex to get it here. the lisp is clearer.

*a bit of wishful thinking*

#+BEGIN_SRC scheme
  (define (sqrt x)
    (newton (lambda (y) (- x (square y)))
            1))
#+END_SRC

how do we compute newton's method? lookin for a fixed point!

#+BEGIN_SRC scheme
  (define (newton f guess)
    (define df (deriv f))
    (fixed-point
     (lambda (x) (- x (/ (f x) (df x))))
     guess))
#+END_SRC

functions are a mathematical mapping from a value to another
procedures compute functions

once again we used wishful thinking; by some magic we can do something
we have a name for, not worry about how it will be done.

!! "wishful thinking is essential to good engineering"

#+BEGIN_SRC scheme
  (define deriv
    (lambda (f)
      (lambda (x)
        (/ (- (f (+ x dx))
              (f x))
           dx))))
#+END_SRC

somewhere we would have to 
: (define dx 0.00001)
but that's not really interesting

chris stachey was a proponent of making procedures/functions
first-class

rights & privileges of first-class citizens:
  - to be named by variables
  - to be passed as arguments to procedures
  - to be returned as values of procedures
  - to be incorporated into data structures

this enables *powerful* abstractions