SCIP 1.2 Procedures and the Processes They Generate

Mix.install([])

1.2 Procedures and the Processes They Generate

The ability to visualize the processes (consequences) generated by procedures is critical to being an expert programmer.

A procedure is a pattern of the local evolution of a process, specifying how each stage is built one upon the other.

1.2.1 Linear Recursion and Iteration

It is important to observe the shape of a process to understand it.

We must not confuse the notion of process with the notion of a procedure. Let’s look at two types of processes:

Linear Recursive Process: A process that chains together deferred evaluation until N recursive steps are reached.

a recursive procedure

(define (factorial n)
  (if (= n 1)
        1
        (* n (factorial (- n 1)))))

a linear recursive process

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

Iterative Process: a process in which the state is maintained according to a fixed set of state variables, logic for how the state is updated, and an optional end test that dictates when the process should terminate.

a recursive procedure

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
        (if (> counter max-count)
    product
    (fact-iter (* counter product)
               (+ counter 1)
               max-count)))

a linear iterative process

(factorial 6)
(fact-iter   1 1 6)
(fact-iter   1 2 6)
(fact-iter   2 3 6)
(fact-iter   6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

We can describe both of these as recursive procedures in that the procedure calls the procedure itself. However such a statement informs us only of the syntactic fact of how the procedure is written, not how the procedure’s process evolves.

Many languages are designed so that the interpretation of any recursive procedure results in an amount of memory that grows with the number of procedure calls, even if the procedure is in principle iterative. These languages will introduce looping constructs in order to support iterative processes: for, while, etc.

If an interpreter is able to execute an iterative process in constant space, even if defined by a recursive procedure, it is termed tail-recursive.

1.2.2 Tree Recursion

Consider the following procedure:

(define (fib n)
  (cond ((= n 0) 0)
        ((= n 1) 1)
        (else (+ (fib (- n 1))
                 (fib (- n 2))))))

Let us observe what happens when we call (fib 5)

• the process looks like a tree
• the branches split into two at each level
• the entire computation of (fib 3) is duplicated

Note that each vertical step is of the same size, whereas the horizontal steps expand exponentially.

The number of steps required by a tree-recursive process will be proportional to the number of nodes in the tree, while the space required will be proportional to the maximum depth of the tree.

The Fibonacci sequence could be rewritten to use an 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))))

While the linear recursive process is exponential in its growth, it is easier to understand. One can observe that a recursive process could be recast as an iterative one with three state variables.

1.2.3 Orders of Growth

Processes differ considerably in the rates at which they consume computational resources. An order of growth can be used to obtain a gross measure of the resources required by a process as the inputs become larger.

$n$ = the size of the problem.

$R(n)$ = the amount of resources the process requires for a problem of size $n$.

$R(n) = \Theta(f(n))$ if there are positive constants $k^1$ and $k^2$ independent of $n$ such that:

$k1 f(n) \leq R(n) \leq k2 f(n)$

($\Theta(f(n))$ is pronounced “theta of $f(n)$”)

Some common orders of growth:

$\Theta(n)$ grows linearly.

$\Theta(1)$ is constant.

$\Theta(n^2)$ is quadratic.

$\Theta(log\ n)$ is logarithmic.

1.2.4 Exponentiation

A linear recursive process requires $\Theta(n)$ steps and $\Theta(n)$ space.

A linear iterative process requires $\Theta(n)$ steps and $\Theta(1)$ space.

However, there are equations like exponentiation where we do not have to proceed incrementally but can instead compute it using a combination of specific calculations.

Let’s say we want to solve $b^8$

Rather than:

$b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot (b \cdot b))))))$

We could:

$b^2 = b \cdot b$

$b^4 = b^2 \cdot b^2$

$b^8 = b^4 \cdot b^4$

This can be expressed as:

(define (fast-expt b n)
  cond ((= n 0) 1)
       ((even? n) (square (fast-expt b (/ n 2))))
       (else (* b (fast-expt b (- n 1)))))

This would require $\Theta(log\ n)$ steps and $\Theta(log\ n)$ space.

1.2.6 (skipping 5): Probabilistic Method

There is a class of algorithms that while correctness is not guaranteed, the chance of error becomes arbitrarily small and thus allows the confident use of them. These are probabilistic algorithms.

Exercises

Exercise 1.9

Depict and describe the procedures and their corresponding processes.

Procedure A is a recursive procedure in that it invokes itself.

(define (+ a b)
  (if (= a 0)
  b
  (inc (+ (dec a) b))))

Process A is a linear recursive process. You will note that inc evaluations are chained together until the conditional is fulfulled.

(+ 5 5)
(inc ( + 4 5 ))
(inc ( inc ( + 3 5)))
(inc ( inc ( inc (+ 2 5))))
(inc ( inc ( inc (inc (+ 1 5)))))
(inc ( inc ( inc (inc (inc (+ 0 5))))))
(inc ( inc ( inc (inc (inc 5)))))
(inc ( inc ( inc (inc 6))))
(inc ( inc ( inc 7)))
(inc ( inc 8))
(inc 9)
(10)

Procedure B is a recursive procedure in that it invokes itself.

(define (+ a b)
  (if (= a 0)
  b
  + (dec a) (inc b)))

Process B is a linear iterative process. While it invokes itself, it is deferring no evaluation and is instead tracking a variable state through the iterations.

(+ 5 5)
(+ 4 6)
(+ 3 7)
(+ 2 8)
(+ 1 9)
(+ 0 10)
(10)

Exercise 1.10

The following procedure computes a mathematical function called Ackermann’s function.

(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

What are the values of the following expressions:

(A 1 10)
(A 2 4)
(A 3 3)

Each of these will be a linear recursive process, as the y param will defer evaluation of x until y = 1 at which point x will evaluate and, if not 0, prompt another chain of deferred evaluations of itself as y is invoked again until 1.

Exercise 1.17

Devise a logarithmic alternative to this linear recursive procedure using double and halve procedures:

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

defmodule MultiplyRecursive do
  defp print_step(a, b), do: IO.puts("Step: (" <> to_string(a) <> ", " <> to_string(b) <> ")")

  defp double(n), do: n * 2

  defp halve(n), do: div(n, 2)

  def mult_log(a, b) when b == 0 do
    print_step(a, b)
    0
  end

  def mult_log(a, b) when rem(b, 2) == 0 do
    print_step(a, b)
    mult_log(double(a), halve(b))
  end

  def mult_log(a, b) do
    print_step(a, b)
    a + mult_log(a, b - 1)
  end

  def mult_lin(a, b) when b == 0 do
    print_step(a, b)
    0
  end

  def mult_lin(a, b) do
    print_step(a, b)
    a + mult_lin(a, b - 1)
  end
end

IO.puts("Linear Multiplication")
MultiplyRecursive.mult_lin(12, 14)

IO.puts("Logarithmic Multiplication")
MultiplyRecursive.mult_log(12, 14)

Exercise 1.18

Make an iterative version of the logarithmic multiply procedure.

defmodule MultIterLogarithmic do
  defp print_step(a, b, acc),
    do:
      IO.puts("Step: (" <> to_string(a) <> ", " <> to_string(b) <> ", " <> to_string(acc) <> ")")

  defp double(n), do: n * 2
  defp halve(n), do: div(n, 2)

  def mult_iter(a, b) do
    mult_iter_loop(a, b, 0)
  end

  defp mult_iter_loop(a, 0, acc) do
    print_step(a, 0, acc)
    acc
  end

  defp mult_iter_loop(a, b, acc) when rem(b, 2) == 0 do
    print_step(a, b, acc)
    mult_iter_loop(double(a), halve(b), acc)
  end

  defp mult_iter_loop(a, b, acc) do
    print_step(a, b, acc)
    mult_iter_loop(a, b - 1, acc + a)
  end
end

IO.puts("Iterative Logarithmic")
MultIterLogarithmic.mult_iter(12, 14)