$$\sum _{\mathrm{a}\le i\le b}i$$

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

$$\sum _{\mathrm{a}\le i\le b}{i}^2$$

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

Computers were created to take care of menial tasks, so avoid repitition. Divide everything into smaller pieces, then each small piece needs to be debugged/understood only once.

$$\sum _{\genfrac{}{}{0px}{}{\mathrm{a}\le i\le b}{\mathrm{by\; 4}}}\frac{i(i+\; 2)}{}$$

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

When dealing with patterns, find the abstraction.

General pattern in the above sums:

(define (<name> a b)
  (if (> a b)
      0
      (+ (<term> a)
         (<name> (<next> a) b))))

And now more correctly:

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

term and next are both procedural arguments.

Rewritten sum-int, sum-sq and pi-sum are shown below.

(define (sum-int a b)
  (define (identity a) a)
  (sum identity a 1+ b))

(define (sum-sq a b)
  (sum sq a 1+ b))

(define (pi-sum a b)
  (sum (lambda (i) (/ 1 (* i (+ i 2))))
       a
       (lambda (i) (+ i 4))
       b))

There are multiple ways of implementing sum. Below is an iterative version.

(define (sum term a next b)
  (define (iter j ans)
    (if (> j b)
        ans
        (iter (next j)
              (+ (term j) ans))))
  (iter a 0))

Computers to make people happy, not people to make computers happy.

Returning to the square root procedure, note that we have been searching for a fixed point of $f$. ($x$ is a fixed point of $f$ if $f(x)=x$.)

$$y\stackrel{𝑓}{\mapsto }\frac{y+\frac{x}{y}}{2}$$

$$f\left(\sqrt{x}\right)=\sqrt{x}$$

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

(define (fixed-point f start)
  (define tolerance 0.00001)
  (define (close-enough? u v)
    (< (abs (- u v)) tolerance))
  (define (iter old new)
    (if (close-enough? old new)
        new
        (iter new (f new))))
  (iter start (f start)))

Note that $y\mapsto \frac{x}{y}$ with $y=1$ and $x=2$ leads to a never-ending oscillation. The dampener is required to ensure that progress towards to answer is maintained.

More clearly stated:

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

average-damp takes a procedure as an argument and returns a procedure as a value.

Newton's method, also known as the Newton-Raphson method, is an algorithm to produce successively better approximations to the zeroes (i.e. roots) of functions. (Find $y$ s.t. $f(y)=0$ .)

Start with a guess $y+0$ . Then

$$y_{n+1}=y_{n}-\dfrac{f(y_{n})}{\frac{df}{dy}|_{y=y_{n}}}$$

Re-implementing sqrt using Newton's method:

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

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

Use wishful thinking to assume magic can be done with anything with a name. Wishful thinking is essential for good computer science.

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

And magically we have the derivative! Evidently this isn't perfect and should make numerical analysts skin crawl.

Christopher Strachey, grandfather of computer science, logician and inventor of denotational semantics, was one of the first to make procedures first-class citizens in programming langauges.

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

Turning procedures into first-class citizens allows for powerful abstractions.

Note to self: orgmode and latexml are lifesavers.