Book 1.1: The Elements of Programming

From Chapter 1: Building Abstractions with Procedures

The acts of the mind, wherein it exerts its power over simple ideas, are chiefly these three:

1. Combining several simple ideas into one compound one, and thus all complex ideas are made.
2. The second is bringing two ideas, whether simple or complex, together, and seeing them by one another so as to take a view of them at once, without uniting them into one, by which it gets all its ideas of relations.
3. The third is separating them from all other ideas that accompany them in their real existence: this is called abstraction, and thus all its general ideas are made.

—John Locke, An Essay Concerning Human Understanding (1690)

In simpler terms you can do 1 of 3 things.

1. Combine simple ideas to make complex ones.
2. Compare ideas to create relation.
3. Separate ideas to make them more general.

What it means to be a Master Software Engineer

Master software engineers have the ability to organize programs so that they can be reasonably sure that the resulting processes will perform the tasks intended.

Imagine if a master carpenter only needed to be reasonable sure that the chair they built will no break when the chair is used for the intended purpose of sitting down. We would laugh at them, surely.

It does make a good point in a similar vein of comparison to real engineers. Like nuclear reactors, software should be built in a modular way so as to make debugging and fixing problems as easy as possible. Without affecting other parts of the system.

LISP

Created by John McCarthy in the 1950's for solving mathematical equations like algebraic expressions.

It's called lisp because it contained new data objects called atoms and lists.

LISt Processing

Lisp is the second oldest largely used language behind only Fortran.

It's been evolving in a more natural way and it's community has been resistant to formal declarations of an official version of the language. Instead it's now known as a family of languages. Each slightly differing from the last to be tackle the problems it's used for.

Although superseded by other languages it was used heavily for operating system scripting and editors.

Lisp was chosen for this book because it expresses the parts of programming which are good concepts to learn.

1.1: The elements of programming

A computer programming language is more than a set of instruction for completing tasks. It provides a framework for organizing ideas.

When assessing a programming language we should look at the means it provides for combining smaller ideas into more complex ideas.

There are three mechanisms:

1. primitive expressions, simplest entities in a language i.e. numbers
2. means of combination, combination allows compound elements such as arrays to be built from simpler primitive expressions
3. means of abstraction, where compound elements can be named and manipulated as units i.e. assigning an array to a variable is naming the compound element which makes it simpler and can then be manipulated as a simplified abstracted unit

Two kinds of elements:

1. Data, which is "stuff"
2. Procedures, which are a set of rules for manipulating data

A good programming language should be able to describe primitive data and primitive procedures.

Primitive procedures:

"built-in procedures not written in scheme but in the language which scheme is built using".

A good programming language should be provide methods for combining and abstracting procedures and data.

1.1.1 Expressions

Interpretation of input expressions.

> 486
486

The interpreter runs in the following loop; read, evaluate, print.

Scheme will evaluate the primitive numerical datatype expression (base 10). Lisp will then print this number.

> (+ 1 2)
3

Primitive expressions can be combined with primitive procedures to make compound expressions. This represents the application of the procedure to those numbers.

Combinations

The formation of a combination is a leftmost operator with a list of delimited primitive expressions all within parenthesis.

(operator operand)

There can be 0 or more operands but only one operator. The structure of this is known as prefix notation.

A benefit of using prefix notation is that you do not repeat the symbol for the operator when using more than 2 operands.

Prefix V.s. infix (traditional mathematical notation)

(operator operand operand operand operand operand)
(operator operand operator operand operator operand operator operand operator operand)

This paves the way for combinations of combination expressions. Prefix allows for combinations to be noted in a way which is easy to read.

;(operator (operator operand operand) (operator operand operand))

(- (* 3 4) (+ 1 2))
9

Where are the limitations?

Humans offer the biggest limitation. We get easily confused by computationally straightforward compound expressions.

There is not necessarily a limit to the depth of nesting that lisp can interpret.

We can improve readability by putting using new lines to read a sub expressions more easily.

(- 
    (* 3 4)
    (+ 1 2))

This is known as pretty-printing.

1.1.2 Naming and the Environment

A computational object can be a primitive or a combination of primitives in a more complex data structure.

Critically a programming language provides a means by which to name computational objects.

The names are then used to refer to the objects.

Variable is an object.

Name identifies a variable and that variable has a value which is an object.

(define length 2)
(define width 3)
(define depth 6)

Once associated, we can call on the name.

> length
2

We can associate name-object pairs to complex compound operations.

(define output (- (* 3 4) (+ 1 2)))

This is the simplest form of abstraction.

It would be time consuming to write out the full expression for output each time we want to use it in the program, so instead we abstract it's value by providing it with a name where we can refer to its value.

Each time we abstract in this way we are making it easier for ourselves to understand and simplify something more complex. Lisp programs are built using this abstraction technique. As are most languages.

The name value pairs are stored in the global environment. As the interpreter needs to keep track of the value pairs.

1.1.3 Evaluating Combinations

Tree accumulation is used for evaluating nested combinations of operations. It does this through the use of recursion.

Two rules exist for evaluating combination:

1. Evaluate the subexpressions of the combination.
2. Apply the operator to the operands i.e. do the math.

Step one calls itself as the subexpressions may have subexpressions of their own which need evaluating. This is a recursive process.

(* 
    (+ 2 
        (* 4 6))
    (+ 3 5 7))

Once all possible sub expressions are evaluated the primitive expressions can be evaluated. This is the base case.

When a primitive is reached evaluation is taken care of with the following rules:

• The values of numerals are the numbers that they name.
• The values of built-in operators are the machine instruction sequences that carry out the corresponding operations.
• the values of other names are the objects associated with those names in the environment i.e. other definitions.

Environment

• can have a different value based on which environment they are run. You could say the the + is in the global environment but it could be changed. It is meaningless to speak of the value of an expression without knowing the environment in which it is being run.

Special forms

The general evaluation rule does not apply to definitions.

(define x 3)

The statement is not a combination. Instead define associates through naming abstraction x to 3. This type of procedure is known as a special form. The procedure define is a special form.

Each special form has it's own rules for evaluation.

All the types of expressions including special forms and standard combinations both have their associated evaluation rules. These expressions make up the syntax of the programming language.

Lisp has a small set of expressions which can all be described by a simple general rule and then a few additional special forms with their own rule.

1.1.4 Compound procedures

In lisp there are built in procedures and we can can define new procedures. From just looking at the procedure call itself it is impossible to tell which is defined within the interpreter like the primitive arithmetic operators and which are defined within the program or library.

There are two types of procedures:

1. Primitive procedures
2. Compound procedures, this builds on the above

Adding procedure definitions builds on the basic pillars of a programming language:

• Numbers and operators
• Nesting combinations
• Naming data values as a means of abstraction

This is a much more powerful version of abstraction.

The structure of a defined procedure is:

(define ({name} {formal parameters}...  {formal parameters})({body}))

Taking square for example, we can create a new procedure using the form above.

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

The name is used as a symbol which refers to as a unit.

The formal parameters are used within the body of the procedure. They act as a placeholder which is substituted for the actual value when the argument is evaluated when the procedure is called (depending on the execution order).

Building on procedures

Once we have defined a procedure we can use that within another procedure definition.

Take a sum of squared for instance:

(define (sum-of-squares x y) (+ (square x) (square y)))

You can take this further and further. Building on procedures defined using other procedures.

1.1.5 The Substitution Model for Procedure Application

The process by which a compound procedure is evaluated is called the substitution model.

This process is to substitute all formal parameters within the body of the procedure replaced with the corresponding argument.

This is purely a way of thinking about the process, it's not actually how the interpreter does it.

Normal & Applicative order

There are two orders in which we can evaluate a compound procedure.

1. Normal - evaluate the operands only at the point they are used
2. Applicative - evaluate the operands initially.

Lisp uses applicative order. It means we evaluate an operant less times, therefore it is more efficient.

Normal

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

    (+ (* (+ 1 6) (+ 1 6)) (* (* 2 5) (* 2 5)))
    
        (+ (* 7 7) (* 10 10))
        
            (+ 49 100)

149

Evaluations: 7

Applicative

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

(sum-of-squares 7 10) 

    (+ (* 7 7) (* 10 10))

        (+ 49 100)

149

Evaluations: 5

• There is a clear advantage in the context of evaluation efficiency for applicative order.

1.1.6 Conditional Expressions and Predicates

Conditional expressions offer a language the ability to test. Through testing we can build more complex procedures.

To perform tests we need more special forms. These are cond and if.

Cond

Cond stands for "conditional"

The syntax for this is the keyword, then a list of clauses and finally an else.

A clause contains a predicate which will return true or false i.e. a boolean. The clause also contains a value which is evaluated if the predicate is true. If no predicates are true then the else clause is evaluated.

Take the following case analysis

Without conditionals we cannot create this programmatically.

With conditionals it looks like this:

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

The word predicate is used when a procedure which returns true or false.

If

If is a shortened version of cond. With only one clause and an else. The case analysis from above can be written using an if in the following way:

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

This nicely reduces the size of the procedure. Implicitly dealing with the case that x is 0.

(if {predicate} {consequence} {alternative})

Most common predicates

1. (and {e1} ... {e1}) - special form
2. (or {e1} ... {e1}) - special form
3. (not {e1}) - normal procedure

and and or are both special forms because their sub expressions are not necessarily all evaluated.

Exercise 1.1

> 10
10

> (+ 5 4 3)
12

> (- 9 1)
8

> (/ 6 2)
3

> (+ (* 2 4) (- 4 6))
6

> (define a 3)
> (define b (+ a 1))
> (+ a b (* a  b))
19

> (= a b)
#f

> (if (and (> b a) (< b (* a b)))
           b
           a)
4

> (cond ((= a 4) 6)
        ((= b 4) (+ 6 7 a))
        (else 25))
16

> (+ 2 (if (> b a) b a))
6

> (* (cond ((> a b) a)
           ((< a b) b)
           (else -1))
     (+ a 1))
16

Exercise 1.2

Turning this math equation into Scheme code

(5 + 4 + (2 - (3 - (6 + (4/3)))))/(3(6 - 2)(2 - 7))

Scheme implementation

>  (/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5))))) (* 3 (- 6 2) (- 2 7)))
-37/150

Exercise 1.3

A procedure which takes three number arguments and returns the sum of the square of the two largest numbers.

(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (sum-of-largest-two x y z)
  (cond
    ((and (>= x y) (>= x z) (>= y z))(sum-of-squares x y))
    ((and (>= x y) (>= x z) (>= z x))(sum-of-squares x z))
    (else (sum-of-squares z y))))

(sum-of-largest-two 1 2 2)
(sum-of-largest-two 3 2 2)
(sum-of-largest-two 1 2 6)

This implementation is better. More efficient as less tests are needed.

(define (square x) (* x x))
(define (sum-of-squares x y) (+ (square x) (square y)))
(define (sum-of-largest-two x y z)
  (cond
    ((and (<= x y) (<= x z))(sum-of-squares y z))
    ((and (<= y x) (<= y z))(sum-of-squares x z))
    (else (sum-of-squares x y))))

Outcome

8
13
40

Exercise 1.4

(define (a-plus-abs-bn a b)
    ((if (> b 0) + -) a b))

Describe the above.

Functionally it will sum a and the absolute value of b. b will always be positive.

It does this by assessing the value of b to see if it's larger than 0. If b is not larger than 0 then a and b are subtracted, if it is a and b are summed. in essence meaning a will always increase in size by the absolute value of b.

Exercise 1.5

(define (p) (p))
(define (test x y)
  (if (= x 0)
      0
      y))
(test 0 (p))

My initial answer

In applicative order the parameters are x and y are evaluated at the point the test procedure is called. In normal order x is evaluated within the if special form and y is evaluated only if the special form is false.

In the true case x and y are evaluated once each for both applicative and normal order. In the false case for normal order the x parameter is evaluated once and the y is not evaluated so the normal order interpretation has the ability to be more efficient.

The above would be true if p returned a number value. It does not, instead it recursively calls itself.

The actual answer

In normal order the y parameter isn't evaluated because the function enters the true case and then returns 0. If function is interpreted in applicative order then the y parameter is evaluated and the program enters an endless loop of recursion.

1.1.7 Example: Square Roots by Newton's Method

What is the difference between a mathematical function and a software procedure?

In maths they care about "what is", in computer science we care about "how to". This is also known as declarative and imperative.

• Mathematics: Declarative they declare what it is.
• Computer Science: Imperative we work out how to implement it.

For instance in maths this is a perfectly legitimate function.

$$\sqrt{x} = the\;y\;such\;that\;y\;>=\;0\;and\;y^2\;=\;x$$

It tells us nothing about "how to" perform a square root.

I can see why Brian Harvey used a simpler example for recursion. Oh well, let's dive in.

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

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

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt x)
  (sqrt-iter 1.0 x))

(sqrt 9)

(sqrt (+ 100 37))

The point of this is to demonstrate that a "simple procedural language" is enough to perform iteration without any special way of doing it.

Exercise 1.6

Why do we need a special form in order to create an if statement, why can we not just create out own using an if statement?

Here is an example of why...

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(new-if (= 2 3) 'true 'false)
(new-if (= 3 3) 'true 'false)

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x)
                 x)))

This new-if function replaces the if statement in sqrt-iter. The issue is when we execute this code the computer runs out of memory and the program never completes.

Because the new-if statement is not a special form it's running in applicative order so the parameters are evaluated at the point the procedure is called. Unlike in the if special form where they are evaluated in normal order.

A problem with using the new-if function where all parameters are evaluated, is if you pass in a function call as a parameter, then the function will get evaluated, even when the new-if is called within that function. In turn this creates an infinite recursive loop.

sqrt-iter calls new-if which evaluates sqrt-iter...

Exercise 1.7

The good-enough? predicate is not good enough. It's checking if the square of guess is within 0.001 either side of the actual argument you are trying to square root. This fails as numbers smaller than 0.001 will always return true because the differences between the guess and the actual answer will always be less than 0.001. Very large numbers may also fail as they will take a much greater depth of recursion to get within a tolerance of 0.001.

#lang racket
(require (planet dyoo/simply-scheme:2:2))
(define (sqrt-iter guess x)
  (define guess-new (improve guess x))
  
  ;(display guess) (newline)
  ;(display guess-new) (newline)
  
  (if (good-enough-new? guess guess-new)
      guess-new
      (sqrt-iter guess-new
                 x)))

(define (improve guess x)
  (average guess (/ x guess)))

(define (average x y)
  (/ (+ x y) 2))

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

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.000001))

(define (good-enough-new? guess guess-new)
  ;(display (/ (abs (- guess guess-new)) guess)) (newline)
  ;(display (< (/ (abs (- guess guess-new)) guess))) (newline) (newline)
  
  (< (/ (abs (- guess guess-new)) guess) 0.001))


(define (sqrt x)
  (display x) (newline)
  (if  (zero? x)
       0
       (sqrt-iter 1.0 x)))

; very small
;(sqrt 0)
;(sqrt 0.0000009)

; very large 
(sqrt 100000000002343242340001)

(sqrt 9)
;(sqrt 900)
;(sqrt 0.009)

The new, thoughtfully names, good-enough? procedure good-enough-new? will check that difference between the new guess and the last guess is a small enough fraction of the last guess. What this provides is a dynamic approach to checking if the new guess is significantly better than the last with respect to the size of the number whose square root we are finding. Otherwise we are comparing the differences between the guess and a static number.

Exercise 1.8

• y, an approximation to the cube root of x
• x, the number you want to cube root

Then the following equation will produce a number that is closer to the cube root of x.

$$\frac{x / y^2 + 2y}{3}$$

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

(define (cbrt-iter n guess)
  ;(display guess) (newline)
  (if (good-enough? n guess)
      guess
      (cbrt-iter n (newtons-improve n guess))))

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

(define (square n)
  (* n n))

(define (good-enough? n guess)
  (< (abs (- (cube guess) n)) 0.01))

(define (newtons-improve x y)
  (/ (+ (/ x (square y)) (* y 2)) 3))

(define (cbrt n)
  (cbrt-iter n 1))

(cbrt 8)
(cbrt 10)

The results...

2.00000491167
; the real answer is 2

2.15449592515
; the real answer is 2.15443469003

Pretty good but like the square root function we it will not be performant for both very small or very large numbers.

To fix this we can implement the fix made to the square root code. A slight restructuring of the code will see that the result is good enough if the guess is a diminishing fraction of itself below a threshold.

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

(define (cbrt-iter n guess)
  (define guess-new (newtons-improve n guess))
  ;(display guess) (newline)
  (if (good-enough? guess guess-new)
      guess
      (cbrt-iter n guess-new)))

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

(define (square n)
  (* n n))

(define (good-enough? guess guess-new)
  ;(< (abs (- (cube guess) n)) 0.01))
  (< (/ (abs (- guess guess-new)) guess) 0.001))

(define (newtons-improve x y)
  (/ (+ (/ x (square y)) (* y 2)) 3))

(define (cbrt n)
  (cbrt-iter n 1))

1.1.8 Procedures as Black-Box Abstractions

The square root procedure is a wrapper for a set of procedures which combine to return a value. A user need not know what the parts of that function are called, their formal parameter naming or even the logical steps. They should be able to accept the procedure as a black box which produces the answer they want.

A procedure like the square function is a procedural abstraction as it itself is not a procedure but points to a procedure.

Decomposition

We decompose a problem into smaller definable sub problems. In code this looks like smaller well-defined procedures which are called upon as abstractions. This is far superior to just cutting up code into the first 10 lines then the next 10 lines.

Bound variables

We do not want the variables in one procedure to affect those in another. Because of this we have locally scoped variables. The formal parameters are these locally scoped variables. Actual parameters are then bound to the formal parameters to execute the procedure.

Capturing variables

Within the good-enough? function we have two parameters x and guess. They are both locally scoped variables. We can use any name so long as it's not one of the free variables which have been used, such as abs or -. If we do, it's called a captured variable and it's a bug where a free variable is then bound.

Internal definitions and block structure

Isolation of code is an important implementation for modern programming languages. In Scheme we can include the definitions of procedures within procedures. Those nested procedures are only available to the scope they exist within.

(define (cbrt-iter n guess)
  (define guess-new (newtons-improve n guess))
  (if (good-enough? guess guess-new)
      guess
      (cbrt-iter n guess-new)))

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

(define (square n)
  (* n n))

(define (good-enough? guess guess-new)
  (< (/ (abs (- guess guess-new)) guess) 0.001))

(define (newtons-improve x y)
  (/ (+ (/ x (square y)) (* y 2)) 3))

(define (cbrt n)
  (cbrt-iter n 1))


(cbrt 8)
(cbrt 10)

The code above has no internal definitions or internally scoped variables. The user of cbrt only cares about cbrt and other functions likely want similar good-enough? and improve procedures. These names in the current structure are used. So we can internally defined them in order to partition the code. square and cube are kept in their globally defined state as they are generally useful and do not have specific use cases.

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

(define (square n)
  (* n n))

(define (cbrt n)
(define (cbrt-iter n guess)
  (define guess-new (newtons-improve n guess))
  (if (good-enough? guess guess-new)
      guess
      (cbrt-iter n guess-new)))

  (define (good-enough? guess guess-new)
    (< (/ (abs (- guess guess-new)) guess) 0.001))

  (define (newtons-improve x y)
    (/ (+ (/ x (square y)) (* y 2)) 3))
  
  (cbrt-iter n 1))


(cbrt 8)
(cbrt 10)

A final improvement that can be made is to employ lexical scoping which is to use x within the internally defined procedures without passing them in directly as it's already available as a free variable.

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

(define (square n)
  (* n n))

(define (cbrt n)
  (define (cbrt-iter guess)
    (define guess-new (newtons-improve guess))
    (if (good-enough? guess guess-new)
        guess
        (cbrt-iter guess-new)))

  (define (good-enough? guess guess-new)
    (< (/ (abs (- guess guess-new)) guess) 0.001))

  (define (newtons-improve y)
    (/ (+ (/ n (square y)) (* y 2)) 3))
  
  (cbrt-iter 1))


(cbrt 8)
(cbrt 10)

Note that n is now removed from the formal parameters of each of the internally defined procedures which used it. Instead it's used as a free variable.

I think this goes against the functional programming paradigm as the internally defined procedures are no longer functions as they process the output using a free variable which can change?