SICP Chapter 1.3 Notes

SICP

Chapter 1.3

Higher-order procedures are procedures that can take other procedures as arguments or return procedures as values, this provides more expressivity through a higher level of abstraction

Procedures as Arguments

Common patterns between procedures show they can be abstracted to essentially, generate a template procedure which could perform a variety of tasks

Consider the following 3 procedures:

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

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

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

They all similar, the common patterns here are, they all perform a summation of series, a is passed to some function to compute the next value and the functions provide the next value of a
The template procedure can be modified to import more arguments, specifically, the procedures that will be used to replace term and next

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

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

Lambda

lambda is a special form, used to create procedures without explicitly naming them and defining them with names associated in the environment
```
(lambda (<parameters>) (<body>))
```

The pi-sum procedure can be expressed without defining the auxiliary procedures pi-next and pi-term

(define (pi-sum a b)
    (sum (lambda (x) (/ 1.0 (* x (+ x 2))))
         a
         (lambda (x) (+ x 4))
         b))

Useful if functions are only used in one place and aren't likely to be reused
Lambda expressions create closures, allowing it to capture the lexical environment of which they are defined
- Access to variables outside its scope, reduced parameters in some cases
However, excessive use of anonymous procedures can lead to unreadability

let

lambda can be used to create local variables by specifying an anonymous procedure to bind local variables. The body then becomes a call to that procedure

((lambda (⟨var1⟩ ... ⟨varn⟩)
    ⟨body⟩)
 ⟨exp1⟩
 ...
 ⟨expn⟩)

(define (f x y)
    ((lambda (a b)
        (+ (* x (square a))
           (* y b)
           (* a b)))
      (+ 1 (* x y))
      (- 1 y)))

let is another special form designed to make what happened in the last example more convenient, its general form is:
```
(let ((⟨var1⟩ ⟨exp1⟩)
      (⟨var2⟩ ⟨exp2⟩)
       ...
      (⟨varn⟩ ⟨expn⟩))
   ⟨body⟩)
```
- For each variable, an expression is evaluated and assigned to it
- These variables are within scope for the body
- Variables are binded as locally as possible, meaning if you have local variable x assigned using let, its value takes precedence if used to evaluate an expression in the body, rather than using some other defined x on the outer scope if it exists

Finding fixed points of functions

x is a fixed point of f(x) if f(x) = x

For some functions, a guessing method with tolerance can be applied repeatedly: f(x), f(f(x)), f(f(f(x))), ...

(define (fixed-point f first-guess)
    (define (close-enough? v1 v2)
        (< (abs (- v1 v2))
           0.00001))
    (define (try guess)
        (let ((next (f guess)))
            (if (close-enough? guess next)
                next
                (try next))))
(try first-guess))

Consider the square root computation as a fixed-point search
- The square root of a number x equal to y², where we are trying to determine y
- Put the equation into the form y = x/y, we notice we're looking for the fixed point of the function y -> x/y
```
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))
```
- The issue with this search is it does not converge because the subsequent guesses of y oscillate about the answer due to drastic changes
- Prevent guesses from changing a lot by setting bounds, the answer is between y and x/y
- Produce a guess between the bounds and over time, the average of y and x/y becomes closer to y as it approaches the square root of x
- Fixed point: y --> 0.5 * (y + x/y)
```
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))
```

Procedures as returned values

Procedures can be returned from procedures to achieve even more expressive power
Consider the technique average-damping to make approximations converge. Specifically, the function f(x), where x is equal to the average of x and f(x)
- f is a procedure passed as an argument
- average-damp returns a produced by lambda that when applied to x, produces the average of x and f(x)
```
(define (average-damp f)
    (lambda (x) (average x (f x))))
```
- The returned procedure can be used to reformulate procedures such as the square-root procedure, now they become more clearer through abstractions
- fixed-point search --> average-damping --> y -> x/y
```
(define (sqrt x)
    (fixed-point (average-damp (lambda (y) (/ x y)))
                 1.0))
```
It's crucial to consider where and when these abstractions can be beneficial, experienced programmers will know when to apply certain techniques