1B Procedures and Processes; Substitution Model⁠

# Part 1

# Programs and processes

• The job of a programmer is to design processes that accomplish particular goals, like finding the square root of a number.
• You do this by constructing spells (procedures, expressions) which direct a process to accomplish the desired goal.
• You must understand the relationship between the particular spells you cast and the process you’re trying to control.
• How do particular patterns of procedures and expressions cause particular patterns of execution and behavior in the process?

# Kinds of expressions

So far we’ve seen three main kinds of expressions:

• numbers
• symbols
• combinations

These are also expressions, but they are special forms, so we will worry about them later:

• lambdas
• definitions
• conditionals

# Evaluating combinations

These are the substitution rules for evaluating a combination:

1. Evaluate the operator to get the procedure.
2. Evaluate the operands to get the arguments.
3. Apply the procedure to the arguments.
   1. Copy the body of the procedure.
   2. Substitute the arguments supplied for the formal parameters of the procedure.
   3. Evaluate the resulting body.

# Example

The sos procedure takes the sum of the squares:

(define (sq a) (* a a))
(define (sos x y) (+ (sq x) (sq y)))

Let’s evaluate the sum of the square of 3 and the square of 4:

(sos 3 4)
(+ (sq 3) (sq 4))
(+ (sq 3) (* 4 4))
(+ (sq 3) 16)
(+ (* 3 3) 16)
(+ 9 16)
25

This is not a perfect description of what the computer does. But it is a good enough model for now.

# Evaluating conditionals

To evaluate (if predicate consequent alternative), follow these steps:

1. Evaluate the predicate expression.
   1. If it yields true, evaluate the consequent expression.
   2. If it yields false, evaluate the alternative expression.

# Example

The addition operator in Peano arithmetic uses a conditional:

(define (+ x y)
  (if (= x 0)
      y
      (+ (-1+ x) (1+ y))))

Now we can evaluate (+ 3 4) like so:

(+ 3 4)
(if (= 3 0) 4 (+ (-1+ 3) (1+ 4)))
(+ (-1+ 3) (1+ 4))
(+ (-1+ 3) 5)
(+ 2 5)
(if (= 2 0) 5 (+ (-1+ 2) (1+ 5)))
(+ (-1+ 2) (1+ 5))
(+ (-1+ 2) 6)
(+ 1 6)
(if (= 1 0) 6 (+ (-1+ 1) (1+ 6)))
(+ (-1+ 1) (1+ 6))
(+ (-1+ 1) 7)
(+ 0 7)
(if (= 0 0) 7 (+ (-1+ 0) (1+ 7)))
7

# Part 2

# Pre-visualization

• Programs are made of procedures and expressions, and they evolves processes.
• But how do particular programs evolve particle processes?
• We want to go from particularly shaped programs to particularly shaped processes.
• We want to pre-visualize the process like a photographer pre-visualizes the photo before taking the shot.

# Peano arithmetic

There are two ways to add whole numbers in Peano arithmetic.

(define (+ x y)
  (if (= x 0)
      y
      (+ (-1+ x) (1+ y))))
(define (+ x y)
  (if (= x 0)
      y
      (1+ (+ (-1+ x) y))))

Both are written using recursion, but they are different: the first generates a linear iterative process with $Θ(n)$ time and $Θ(n)$ space; the second generates a linear recursive process with $Θ(n)$ time and $Θ(1)$ space.

The iteration has all of its state in explicit variables. The recursion does not.

# Part 3

# Perturbation analysis

Make small changes to the program and see how it affects the process.

# Fibonacci sequence

We can represent the Fibonacci numbers 0, 1, 1, 2, 3, 5, 8, 13, 21, … in Lisp:

(define (fib n)
  (if (< n 2)
      n
      (+ (fib (- n 1))
         (fib (- n 2)))))

This is a tree-recursive process. We can represent the evaluation with a tree. This is a terribly inefficient process because there is so much redundant computation. The time complexity of this is actually the Fibonacci numbers. The space complexity is linear.

And the reason why people think of programming as being hard, of course, is because you’re writing down a general rule, which is going to be used for lots of instances … You’ve got to write down something that’s a general in terms of variables, and you have to think of all the things that could possibly fit in those variables, and all those have to lead to the process you want to work. —Sussman

# Tower of Hanoi

Move an $n$-high tower from spike from to spike to using spike spare as a spare:

(define (move n from to spare)
  (cond
    ((= n 0) "DONE")
    (else (move (-1+ n) from spare to)
          (print-move from to)
          (move (-1+ m) spare to from))))