1 - Building Abstractions with Procedures

Building Abstractions with Procedures

We are going to be using Scheme, a version of Lisp.
Why Lisp?

Lisp descriptions of processes, called procedures, can themselves be represented and manipulated as Lisp data.
Good for writing programs that manipulate other programs as data (such as interpreters and compilers).
Its good fun...

The Elements of Programming

Every powerful language has three mechanisms in order to achieve task performance, effective framework, and a means to combine simple ideas together:

Primitive Expressions - represents the simplest entities the language is concerned with.
Means of Combination - by which compound elements are built from simpler ones.
Means of Abstraction - by which compound elements can be named and manipulated as units.

Expressions

Below are some common numerical expressions (in Lisp) formed by delimiting a list of expressions within parentheses in order to denote procedure application, these are called combinations.
The left most element in the list is the operator and the other elements are operands.

(+ 50 50)
100
(- 1000 250)
750

One of the major benefits of this is the lack of ambiguity. The left most element in a set of parentheses is always the operator.
Below demonstrates what I mean in regard to it always being clear what is going on.

(+ 21 35 12 7)
75

(* 25 4 12)
1200

(+ (* 3 5) (- 10 6))
19

There is no limit to the depth of nesting. This mode of operation is often expressed by saying the interpreter runs in a read-eval-print loop

Naming and the Environment

A name identifies a variable whose value is the object
In Scheme we name things with define, below we create a variable called size with a value of 2:

(define size 2)

Some further examples:

(define pi 3.14159)
(define radius 10)
(* pi (* radius radius))
314.159
(define circumference (* 2 pi radius))
circumference
62.8318

define is our language's simplest means of abstraction The memory that keeps track of these name-object pairs we are creating with define is called the environment (more specifically the global environment).

Evaluating combinations

To evaluate a combinations:

Evaluate the operands of the outer most expression (this can lead to you entering nested expressions).
Once all operands are primitive, apply the operator.

The way that combinations are calculated follows a process known as tree accumulation.
NOTE: define statements are not combinations or expressions! These are called special forms (A special form of expression).

Compound Procedures

This is, in a way, a function but we will continue to refer to them as compound procedures
Compound procedures are great because they provide isolation for what is in the body, scoping.
Take squaring for example:

(define (square x) (* x x))

We define a compound procedure called square that takes "x" and then we multiply x with itself, we square it.
Procedures take the general form:

(define (<name> <formal parameters>) <body>)

To demonstrate how useful this can be, see the code block below:

(define (sum-of-squares x y)
    (+ (square x) (square y)))
(sum-of-squares 3 4)
25
(* (cond ((> a b) a)
((< a b) b)
(else -1))
(+ a 1))
To illustrate this lets evaluate the following where f is the earlier combination
```Scheme
(f 5)

We begin by retrieving the body of f:

(sum-of-squares (+ a 1) (* a 2))

Then we replace the formal parameter a by the argument 5

(sum-of-squares (+ 5 1) (* 5 2))

These two sub-problems must be solved, next we apply the sum-of-squares procedure with 6 and 10 passed in as parameters.

(+ (* 6 6) (* 10 10))

(+ 36 100)

136

This whole process described is called the substitution model for procedure application.
2 MAIN POINTS:
1. Substitution is used to help us think about procedure application.
2. Over the course of this book, more increasingly elaborate models will be covered.
In general, when modeling phenomena in science and engineering, we begin with simplified, incomplete models and as we examine in greater detail. These simple models become inadequate and must be replaced by more refined models. For example when using procedures with mutable data, the substitution model breaks down.
Lisp uses APPLICATIVE ORDER rather than NORMAL ORDER mainly due to the efficiency boost of avoiding duplicate evaluations of expressions.
Normal order is still a valuable tool and has good use cases (discussed in later chapters)

Conditional Expressions and Predicates

The construct of a case analysis in this context refers to conditionals.
It is nice to think of conditionals in Lisp as switch cases.
NOTE: Conditionals are another kind of special form
- It has multiple predicates (cases)
- Is used like so in Lisp:

(define (abs x)
    (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (- x))))

(define (abs x)
    (cond ((< x 0) (- x))
        (else x)))

A general form can expressed like so:

(cond (⟨p1 ⟩ ⟨e1 ⟩)
    (⟨p2 ⟩ ⟨e2 ⟩)
    ...
    (⟨pn ⟩ ⟨en ⟩))

The first expression in each pair above is a predicate (an expression that evaluates to true or false)
Essentially how it works is that if the predicate it true the value that its paried with is used or whatever is there is executed.
If it's false, we move on to the next predicate.

In Scheme true and false is represented as #t and #f Another way we can do the abs function (the example above) is with the special form if, NOTE that this can only be used when there is strictly only 2 cases.

(define (abs x)
    (if (< x 0)
        (- x)
        x))

The general form for if is:

(if ⟨ predicate ⟩ ⟨ consequent ⟩ ⟨ alternative ⟩)

Three very commonly used predicates are and, or and not

and - evaluates to true if all elements are true
or - evaluate to true if at least one element is true
not - evaluates to true if the element is false Some examples:

(and (> x 5) (< x 10))

Below are 2 examples of how to create the greater than or equal to operation.

(define (>= x y) (or (> x y) (= x y)))

(define (>= x y) (not (< x y)))

Procedures and the Processes they Generate

A procedure refers to syntactical meaning.
- a pattern for the local evolution of a computational process.
- think of it as abstract, the rules.
- ie. When a procedure makes a call to itself.
A process refers to how a procedure plays out, or the shape of it when writing it all out via the substitution model.
- a concrete realization of a procedure.
- what actually happens.
Recursive procedure: A procedure that calls upon itself.
Iterative procedure: A procedure which iterates through a means without calling itself (not available in Scheme)
Recursive process: A process that behaves recursively.
- This means that it operates via deferred operations, expanding itself out until a rule is met and all deferred operations can then sequentially be performed.
- Its shape is triangular.
- Is more memory intense due to having to store all the deferred operations that will need to be calculated later.
Iterative process: A process that keeps track of state variables and uses rules to iterate until a condition is met.
- In scheme we do this recursively (syntactically), but it behaves iteratively.
- Its shape is linear.
- Constant memory space required as it only needs to remember the current state.
tail-recursive: iteration can be expressed using ordinary procedure mechanisms, special iteration constructs like loops are only useful as syntactic sugar.
- A recursive procedure that has an iterative process that uses a counter to track the state variables (like in factorial) could be described as tail-recursive.
Tree Recursion refers a recursive procedure that calls upon itself more than once, leading to multiple branches.
- The number of steps required by a tree-recursive process is proportional to the number of nodes in the tree.
- The space required is proportional to the maximum depth of the tree.
- Below we can see the tree recursive approach with Fibonacci:
```
(define (fib n)
    (cond ((= n 0) 0)
          ((= n 1) 1)
          (else (+ (fib (- n 1))
                    (fib (- n 2))))))
```
- Now for comparison purposes see Fibonacci being implemented through linear iterative process:
```
(define (fib n)
    (fib-iter 1 0 n))
(define (fib-iter a b count)
    (if (= count 0)
        b
        (fib-iter (+ a b) a (- count 1))))
```
Tabulation or Memoization are strategies that involve storing computed values in a table so that we we are doing something like tree recursion that may involve lots of repeated calculations. We can check the table to see if it's already been computed before.
Order of Growth is a way to measure the time and space complexity of a process.
- It allows us to have an idea for how the resources required for running the process will change as inputs change.
- Think of Big O notation.
- It is also good for a quick indicator as to how the process runs, its shape as it evolves over execution.

Exponentiation

Linear Recursive Process:

(define (expt b n)
    (if (= n 0)
        1
        (else (* b (expt b (- n 1)))))
)

Linear Iterative Process:

(define (expt b n)
    (expt-iter b n 1)
)
(define (expt-iter b counter product)
    (if (= counter 0)
        product
        (else (expt-iter b (- counter 1) (* b product))))
)

Greatest Common Divisors: is the largest number that divides into 2 numbers with no remainder
- Euclid's Algorithm was derived in order to compute the GCD effectively.
- It essentially recursively divides the larger number by the smaller one of the pair and continues this until this division results in a zero remainder.
```
(define (gcd a b)
    (if (= b 0)
        a
        (gcd b (remainder a b))))
```
- Applicative Order is much more efficient here as it only calls the remainder function 4 times.
- Normal Evaluation Order results in calling the remainder function 18 times.
- Lame's Theorem is related to Euclid's Algorithm, it states:
  - If Euclid's Algorithm requires k steps to compute the GCD of some pair, then the smaller number in the pair must be greater than or equal to the k^th Fibonacci number.
Testing for prime numbers
- One way takes O(squareRoot(n)) number of steps, based off the rule that if n is not prime it must have a divisor less than or equal to the square root of n
```
(define (prime? n)
    (= n (smallest-divisor n)))
(define (smallest-divisor n)
    (find-divisor n 2))
(define (find-divisor n test-divisor)
    (cond ((> (square test-divisor) n) n)
          ((divides? test-divisor n) test-divisor)
          (else (find-divisor n (+ test-divisor 1)))))
(define (divides? a b)
    (= (remainder b a) 0))
```
- Another way uses the Fermat Test and has an order of growth of O(logn).
  - Fermat's Little Theorem: If n is a prime number and a is any positive integer less than n, then a raised to the n^th power is congruent to a modulo n.
    - a modulo n means remainder of a divided by n.
    - congruent here means that both a modulo n and aⁿ will have the same remainder.

Formulating Abstractions with Higher Order Procedures

Procedures that manipulate procedures are called higher-order procedures.
- Usually involves passing a procedure into a procedure or returning a procedure.

Procedures as Arguments

Particularly useful for abstracting general patterns, similar to sigma notation in mathematics.
For example, to represent a procedure that expresses the concept of summation itself rather than only procedures that compute particular sums:
```
(define (sum term a next b)
  (if (> a b)
    0
    (+ (term a)
        (sum term (next a) next b))))
```
- term is essentially the operation that happens to every term to be added.
- next is the operation we apply to get to the next value... usually just an increment of 1 (for summation).
To demonstrate how this can actually be used:
- Take an increment function that increments its argument by 1.
- We can then define a sum-cubes function like so:
```
(define (inc n) (+ n 1))
(define (sum-cubes a b)
  (sum cube a inc b))
```
The goal of this is to be able to create higher and higher levels of abstraction.

Constructing Procedures Using lambda

lambda essentially creates nameless, inline procedures.
Say we want a procedure that increments an input by 4
```
(lambda (x) (+ x 4))
```
It is very useful in terms of avoiding auxiliary procedures.
Lambda can also be used as an operator in a combination... like so:
```
((lambda (x y z) (+ x y (square z))) 1 2 3)
;12
```
We can use let to set variables which can be very beneficial in a similar sense to lambda.

let has the following syntax:

(let ((⟨var1 ⟩ ⟨exp1 ⟩)
      (⟨var2 ⟩ ⟨exp2 ⟩)
      ...
      (⟨varn ⟩ ⟨expn ⟩))
  ⟨body⟩)

Can be though of as "let variable have the value of this expression inside this body".

Formula to express: f(x,y) = x(1+xy)² + y(1-y) + (1 + xy)(1-y), a = 1 + xy, b = 1 - y, f(x,y) = xa² + yb + ab

Using lambda:

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

Using let:

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

let allows you to bind variables as locally as possible.
- To demonstrate this, say x=5:
```
(+ (let ((x 3))
  (+ x (* x 10)))
x)
;38
```
- x will be set to 3 in the let block, then will return to being 5 outside of it.

IMPORTANT: The variables' values are calculated outside the let!

If x=2:

  (let ((x 3) ; 3
        (y (+ x 2))) ; 2 + 2
      (* x y)) ; 3 * 4
  ;12

Procedures as General Methods

Finding Roots of Equations by the Half-Interval Method

The half-interval method finds the roots of an equation f(x) = 0.
- Given points a and b such that f(a) < 0 < f(b).
- f must have at least 1 zero between a and b.
- let x be the average of a and b, compute f(x).
- If f(x) > 0, then there must be a 0 between a and x.
- If f(x) > 0, then there must be a 0 between x and b.
- We repeat this until the interval is small enough.
- Since the interval of uncertainty is reduced by half each step, the order of growth is O(log(L/T)), L being length of the original interval and T is the error tolerance (size of the interval we consider small enough).

Here is the procedure implementing this strategy:

(define (search f neg-point pos-point)
  (let ((midpoint (average 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))

Finding Fixed Points of Functions

A number x is considered a fixed point of a function f if f(x) = x.

We can locate a fixed point by having an initial guess and repeatedly applying f until the value doesn't change much.

(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)))
      (if (close-enough? guess next)
        next
        (try next))))
  (try first-guess))

→ means "maps to", it is the mathematicians way of writing lambda.
average damping can often assist with the convergence of fixed-point searches.
- it essentially involves averaging successive approximations to a solution.

Procedures as Returned Values

More expressive power can be achieved by creating procedures whose returned values are themselves procedures.
Average Damping is a useful tool for finding convergence, it involves considering a function f, we then consider that function whose value at x is equal to the average of x and f(x)
```
(define (average-damping f)
  (lambda (x) (average x (f x))))
```
- Notice that this takes a procedure as an argument and returns a procedure.
- Example: If we apply average-damping to the square procedure, we produce a procedure whose value at some number x is the average of x and x².
  - Applying this to 10 returns the average of 10 and 100... 55.
These higher level abstractions make it much clearer the intent of the function, what the function is doing, and it also makes it easier to reuse different parts of it for other applications.

Newton's Method

Function for derivatives

(define (derivative g)
  (lambda (x) (/ (- (g (+ x dx)) (g x)) dx)))

Describing Newton's method as a fixed point process:

(define (newton-transform g)
  (lambda (x) (-x (/ (g x) ((deriv g) x)))))
(define (newtons-method g guess)
  (fixed-point (newton-transform g) guess))

Abstractions and First-Class Procedures

Rights and privileges of first-class elements are:
- They may be named by variables.
- They may be passed as arguments to procedures.
- They may be returned as the results of procedures.
- They may be included in data structures.
Lisp rewards first-class elements and although this can pose challenges for implementation, it results in an enormous gain in expressive power.

Return

Graduate Program KB

Table of Contents