Book 1.3: Formulating Abstractions with Higher-Order Procedures

From Chapter 1: Building Abstractions with Procedures

A procedure is a compound set of primitive expressions. It is used to describe a process, generally. It is useful because we reduce the amount of code written by hand as we deal with an abstraction directly. For example, we could call (* 3 3 3) each time we need to cube a number, but this is slow to write it's easier to understand the writer specifically wanted to cube this number. Both conceptually and practically it's better to work directly with the abstraction. So as not to get bogged down in the individual operations.

procedures are abstractions that describe compound operations on numbers independent of the particular numbers. [page 56]

A higher order procedure is one which takes procedures as arguments and manipulates them or they return procedures as values.

A powerful abstraction technique [page 57]

1.3.1 Procedures as Arguments

By identifying common patters between procedures there is likely cause for the use of abstraction in order to reduce rewritten code.

Each part of the code which changes between each example become formal parameters.

3 examples of procedures with common patterns

#lang racket
(require (planet dyoo/simply-scheme:2:2))

; Helpers

(define (cube n)
  (* n n n))

; Normal Procedures with a common pattern

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

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

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

; examples

(sum-of-integers 1 10)
(sum-of-cubes 1 10)
(pi-sum 1 10)

These procedures are simple and work, but they use a shared pattern. This shared pattern is below.

; the common pattern found here is

;(define (general-name term start-int next end-int)
;  (if (> start-int end-int)
;      0
;      (+ (term start-int) (general-name (next start-int) next end-int))))

; writing this as usable code

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

term is the operation performed on each step between a and b
next is the operation performed on a to get the next step

Below I have rewritten the procedures as higher-order functions.

; rewriting the functions to use the higher-order abstraction

; helpers

(define (inc n) (+ n 1))

(define (indetity x) x) ; this one is meta, it defines itself which in the case of this high-ord procedure it's itself

(define (pi-term a)
  (/ 1.0 (* a (+ a 2))))

(define (pi-inc n) (+ n 4))

; new sum functions

(define (sum-ints a b)
  (sum identity a inc b))

(define (sum-cubes a b)
  (sum cube a inc b))

(define (sum-pi a b)
  (sum pi-term a pi-inc b))

; examples

(sum-ints 1 10)
(sum-cubes 1 10)
(pi-sum 1 10)

I am unconvinced this is the best way to code. We had three neat functions. Now we have 8 functions, which have a hierarchy or dependence.

What is more modular? Something which relies on other functions or something which you can change without breaking a chain of use.

Define the definite integral of a function

This is an example of a higher order function using a higher order function. Through doing this kind of abstraction and using functions as arguments, we can start to build more complex procedures which are useful in applications such as complex mathematical operations. Which can then be abstracted and used simply in another function... the cycle continues.

#lang racket
(require (planet dyoo/simply-scheme:2:2))

; Helpers

(define (cube n)
  (* n n n))

; common sum pattern

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

; integral of a function using the common sum pattern

(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)
(integral cube 0 1 0.001)
(integral cube 0 1 0.0001)
(integral cube 0 1 0.00001) ; closer to 1/4

Exercise 1.29

Simpson's rule is a more accurate method of numerical integration.

Note: this is a real weakness. I have never learnt integration. I couldn't have written this answer without using references to other answers.

#lang racket
(require (planet dyoo/simply-scheme:2:2))

; Helpers

(define (cube n)
  (* n n n))

(define (inc n) (+ n 1))

; common sum pattern

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

; Simsons rule higher order function

(define (simpson f a b n)
  (define h (/ (- b a) n))
  (define (term k)
           (* (f (+ a (* k h)))
              (if (or (= k 0) (= k n))
                  1
                  (+ 2 (* 2 (remainder k 2))))))
  (* (/ h 3) (sum term 0.0 inc n)))

; tests

(simpson cube 0 1 2)
(simpson cube 0 1 100)
(simpson cube 0 1 1000)

Exercise 1.30

Exercise 1.30 asks you to rewrite the higher-order procedure which generates linear recursion to a procedure which is iterative.

"Linear Recursion: A linear recursive function is a function that makes only a single call to itself each time the function runs."
"Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes."

Old

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

New

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

I'm not sure why it's called iterative, because iter is also and example of linear recursion.

Exercise 1.31

Write a procedure which returns the product of the values of a given function over a range.

Sum

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

Product

(define (product term a next b)
  (if (> a b)
      1 ; this needs to be 1 because if 0 the answer will be zero as the base case will times everything by 0
      (* (term a) (product term (next a) next b))))

The next part of the exercise asks you to define factorial in terms of product.

; Factorial in terms of product

(define (factorial n)
  (product identity 1 inc n))

(factorial 1)
(factorial 2)
(factorial 3)
(factorial 4)

The final part of the question is to use the formula shown in the figure to create a procedure which computes approximations to pi.

Using this wikipedia page there is an easier to understand version of the function. If I was better at maths then I would probably know how to decompose the example given in the book into something more manageable.

(define (pi)
  (define (john-wallis n)
    (* (/ (+ n 1) n)
       (/ (+ n 1) (+ n 2))))
  (* (product john-wallis 1 inc2 100000) 2))

The second part to this exercise is to rewrite the product procedure in an iterative form.

(define (pi)
  (define (john-wallis n)
    (* (/ (+ n 1) n)
       (/ (+ n 1) (+ n 2))))
  (* (product john-wallis 1 inc2 10000) 2))

Exercise 1.32

We need to prove that the sum and product procedures are can be generalized further.

Recursive

(define (accumulate_ combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner a (accumulate combiner null-value term (next a) next b))))

Iterative

(define (accumulate combiner null-value term a next b)
  (define (iter a result)
    (if (> a b)
        result
        (iter (next a) (combiner result (term a)))))
  (iter a null-value))

Exercise 1.33

For this exercise we made the accumulate function even more general by adding a filter predicate which decides if the value is to be combined or not.

; filtered-accumulate

(define (filtered-accumulate filter? combiner null-value term a next b)
  (if (> a b)
      null-value
      (combiner
       (if (filter? a) (term a) null-value)
       (filtered-accumulate filter? combiner null-value term (next a) next b))))

a

; sum of the squares of primes between a and b

(define (prime-sum-of-squares a b)
  (filtered-accumulate prime? sum_two 0 square a inc b))

b

; helper

(define (gcd a b)
  (define (iter n)
    (if (or
         (and
          (equal? (remainder a n) 0)
          (equal? (remainder b n) 0))
         (equal? n 1))
        n
        (iter (- n 1))))
    (iter (smaller a b)))

; the product of all the positive integers up to n which are relatively prime to n

(define (product-of-relative-prime n)
  (define (filter a)
    (equal? (gcd a n) 1))
  (filtered-accumulate filter product_two 1 identity 0 inc n))

1.3.2 Constructing Procedures Using `Lambda`

Lambda expressions are a nameless procedure. Also known as an anonymous procedure.

Lambda is useful when you do not with to define a procedure for use as a parameter.

Especially if that procedure is simple.

For example in the higher order function we created called sum, it is called by procedure sum-ints.

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

(define (sum-ints a b)
  (sum identity a inc b))

As part of this, we have had to define 2 more functions inc and identity.

(define (inc n) (+ n 1))

(define (identity x) x)

Instead of writing these two trivial functions, we can define a lambda procedure.

(define (sum-ints a b)
  (sum (lambda (x) (+ x))
       a
       (lambda (x) (+ x 1))
       b))

The lambda version of each of the helper procedures takes up less room and you can see what they do without finding where they are defined.

Note: the lambda version of identity has to provide an operation + of only one parameter instead of the identity procedure which only contains the parameter without operation. This is because the program was returning an error saying that "application: not a procedure; expected a procedure that can be applied to arguments given: 0".

The lambda procedure takes the following form:

(lambda ({formal-parameters}) {body})

Breakdown of a lambda procedure

(lambda (x) (+ x 4))

lambda the procedure
(x) of an argument x
(+ that adds
x x
4) and 4

Calling an anonymous `lambda` procedure straight away

((lambda (a) (+ a 1)) 1)

Wrap the lambda in parenthesis and add the arguments to the right within the outer parenthesis.

Using `let` to create local variables

Often when creating procedures we need intermediate values to be stored with names that are easily accessible further on in the procedure.

For example the following quadratic can be written using a locally scoped procedure in order to execute the equation using locally scoped and computed variables.

f(x, y) = x(1 + xy)^2 + y(1 - y) + (1 + xy)(1 - y)

There are sub expressions which would make this equation simplified.

a = (1 + xy)

b = (1 - y)

f(x, y) = xa^2 + yb + ab

The Scheme procedure which declares the function above programmatically using define, then another using a lambda function.

; locally scoped variables using a normal define keyword

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

; locally scoped variables using lambda

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

; using let to locally scope variables

(define (f_let x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

The general notation for the let special form is as follows:

(let ((var1 exp1)
      (var2 exp2))
  (body))

This is an alternative expression for lambda:

((lambda (var1 var2)
   (body))
 (exp1 exp2))

The let expression binds the evaluated expressions to the paired variables for use within the body as locally scoped variables.

Local scoping with `let`

It can get confusion when the a let variable name is the same as the variable used in the expression where the let variable is used.

let will scope the variable as closely to where it is used as possible so the following expression evaluates as 38 when the value of x as the operand to + is 5.

(let ((x 5))
  (+ (let ((x 3))
       (+ x (* x 10)))
     x))

The outer x is equal to 5 and the inner x is equal to 3.

The reason why this works is because the variables values are computed outside the let. So you can even have this kind of monstrosity where the variable x is assigned to a local variable of x.

(let ((x 5))
  (+ (let ((x x))
       (+ x (* x 10)))
     x))

Convention of using `let` instead of define

Although it is possible to do the following and it is almost programmatically the same it is convention to use let. One reason is that the let keyword scopes the variables to the block of the let command.

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

Do this instead.

(define (f_let x y)
  (let ((a (+ 1 (* x y)))
        (b (- 1 y)))
    (+ (* x (square a))
       (* y b)
       (* a b))))

1.3.3 Procedures as General Methods

Compound methods are one form of abstraction. There are more forms of abstraction. This section goes into depth with two complex examples.

Exercise 1.34

Finding roots of equations by the half-interval method

This is a way of finding the roots of an equation. e.g. when given a quadratic equation the roots are the numbers which satisfy the equation. We are finding the zeros. What satisfies the equation when the answer is 0.

x^2 - 7x + 10 = 0

when $x = 2$ , $22 - 7(2) + 10 = 4 - 14 + 10 = 0$ .
when $x = 5$ , $52 - 7(5) + 10 = 25 - 35 + 10 = 0$ .

f(x) = 0

Finding zero

Given and equation and two points, such that $f(a) < x < f(b)$ there will be one or more points between a and b that will equal 0.
Make x the average of a and b.
Once x is calculated test if it is more or less than zero.
If x is greater than 0 then f must have a zero between a and x and vice versa.
We then pass in the midpoint average found as either the a and b value depending on if it is greater than zero or not.
The number will trend closer to zero and we need to test if it is close enough or not.

(define (search f neg-point pos-point)
  (let ((midpoint ((lambda (a b) (/ (+ a b) 2)) 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))))))

(define (close-enough? x y) (< (abs (- x y)) 0.001))

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

(half-interval-method (lambda (x) (- (* x x x) (* 2 x) 3)) 1.0 2.0)

Output

3.14111328125
1.89306640625

Finding fixed points of functions

Similar to the example above we are creating a compound higher order procedure, this time called fixed-point. The point of this procedure is to find the value which satisfies a procedure.

(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)))
        ; (display guess) (newline)
        (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)
(define (sqrt_oscilate x)
  (fixed-point (lambda (y) (/ x y))
               1.0))
(define (average a b)
  (lambda (a b) (/ (+ a b) 2)))
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
              1.0))

(sqrt 19)

Exercise 1.35

Show that the golden ratio is a fixed point of the transformation:

x → 1 + 1/x

(define (golden-ratio)
  (fixed-point (lambda (x) (+ 1 (/ 1 x)))
              1.0))

(golden-ratio)

1.6180327868852458

x = \frac{1+ \sqrt{5}}{2} = φ

(define (golden-ratio)
  (/ (+ 1 (sqrt 5)) 2))

(golden-ratio)

1.6180327868852458
1.618033988749895

These are both very close.

Exercise 1.36

Modify fixed-point to display the guess on each iteration.

(display guess) (newline)

Average Damping

Average damping aids in convergence of fixed-point numbers.

(fixed-point (lambda (x) (/ (log 1000) (log x))) 2.0) ; without damping
(fixed-point (lambda (x) (average x (/ (log 1000) (log x)))) 2.0) ; with damping

0
965784284662087
004472209841214
279195757507157
759850702401539
215843784925895
182207192401397
8277650983445906
387593384662677
671250085763899
481403616895052
6053657460929
5230849678718865
577114682047341
541382480151454
564903245230833
549372679303342
559606491913287
552853875788271
557305529748263
554369064436181
556305311532999
555028263573554
555870396702851
555315001192079
5556812635433275
555439715736846
555599009998291
555493957531389
555563237292884
555517548417651
555547679306398
555527808516254
555540912917957
555532270803653
0
9828921423310435
922168721308343
628224318195455
568346513136242
5577305909237005
555909809045131
555599411610624
5555465521473675
555537551999825

It takes far less iterations in order to converge enough when using average damping.

Exercise 1.37

Continued fractions are fractions which are recursively passed into themselves as a part of the fraction.

It is often useful to have a finite continued fraction, which truncates the fraction after a kth term.

(define (cont-frac-rec n d k)
  (define (rec i)
    (if (equal? i k)
        0
        (/ (n i)
           (+ (d i) (rec (+ i 1))))))
  (rec 1))

(define (cont-frac-iter n d k)
  (define (iter i acc)
    (if (equal? i 0)
        acc
        (iter (+ i 1) (/ (n i) (+ (d i) acc)))))
  (iter k 0))


(cont-frac-rec (lambda (i) 1.0)
           (lambda (i) 1.0)
           12)

(golden-ratio)

In both recursive and iterative forms.

Book 1.3: Formulating Abstractions with Higher-Order Procedures

From Chapter 1: Building Abstractions with Procedures​

1.3.1 Procedures as Arguments​

3 examples of procedures with common patterns​

Define the definite integral of a function​

Exercise 1.29​

Exercise 1.30​

Exercise 1.31​

Exercise 1.32​

Recursive​

Iterative​

Exercise 1.33​

a​

b​

1.3.2 Constructing Procedures Using Lambda​

Breakdown of a lambda procedure​

Calling an anonymous lambda procedure straight away​

Using let to create local variables​

Local scoping with let​

Convention of using let instead of define​

1.3.3 Procedures as General Methods​

Exercise 1.34​

Finding roots of equations by the half-interval method​

Finding zero​

Finding fixed points of functions​

Exercise 1.35​

Exercise 1.36​

Average Damping​

Exercise 1.37​