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

(define (sum-int a b)
  (if (> a b)
      0
      (+ a
         (sum-int (+ a 1) b))))

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²
i=a

(define (sum-sq a b)
  (if (> a b)
      0
      (+ (square a)
         (sum-sq (1+ a) b))))

for leibniz way of finding pi/8,

(define (pi-sum a b)
  (if (> a b)
      0
      (+ (/ 1 (* a (+ a 2)))
         (pi-sum (+ a 4) b))))

three variations an identical technique

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

(define (sum term a next b)
  (if (< a b)
      0
      (+ (term a)
         (sum term
              (next a)
              next
              b))))

we can easily translate those old programs to sum

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

  f  y + y/x
y ↦  -------
        2

f(√x) = √x

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

(define (sqrt x)
  (fixed-point (λ (y) (average (/ x y) y))
               1))

write this by "wishful thinking"
we don't have fixed-point yet but we wish we did

(define (fixed-point f start)
  (define (iter old new)
    (if (close-enuf? old new)
        new
        (iter new (f new))))
  (iter start (f start)))

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)

(define (sqrt x)
  (fixed-point
   (average-damp (lambda (y) (/ x y)))
   1))

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.

(define average-damp
  (lambda (f)
    (lambda (x) (average (f x) x))))

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

(define (sqrt x)
  (newton (lambda (y) (- x (square y)))
          1))

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

(define (newton f guess)
  (define df (deriv f))
  (fixed-point
   (lambda (x) (- x (/ (f x) (df x))))
   guess))

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"

(define deriv
  (lambda (f)
    (lambda (x)
      (/ (- (f (+ x dx))
            (f x))
         dx))))

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