SCIP 1.1: The Elements of Programming

Mix.install([])

1.1 The Elements of Programming

> We are about to study the idea of computational process. Computational processes are abstract beings that inhabit computers. As they evolve, processes manipulate other abstract things called data. The evolution of a process is directed by a pattern of rules called a program. People create programs to direct processes. (1)

Programming languages have three mechanisms for combining simple ideas to form more complex ideas:

• primitive expressions, which represent the simplest entities the language is concerned with
• means of combination, by which compoud elements are built from simpler ones
• means of abstraction, by which compound elements can be named and manipulated as units

There are two kinds of elements in programming:

• procedures: descriptions of the rules for manipulating data
• data: the stuff we want to manipulate

1.1.1 Expressions

Type an expression in an interpreter and it will respond with the result of its evaluating that expression.

486

An expression representing a number can be combined with an expression representing a primitive procedure to form a compound expression that represents the application of said procedure.

137 + 349

Combinations are expressions formed by a delimited list of expressions.

A combination will contain an operator and operands. The value of a combination is obtained by applying the procedure specified by the operator to the arguments that are the values of the operands.

1.1.2 Naming and the Environment

A name identifies a variable whose value is the object.

size = 2
size * 5

A language’s convention for naming represents its simplest means of abstraction. define for Lisp, $ for PHP, var/const/let for JS, etc.

The interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment.

1.1.3 Evaluating Combinations

In order to evaluate a combination, we must perform the evaluation process on each element of the combination. Thus the evaluation rule is recursive in nature: to evaluate it must evaluate.

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

Recursion allows us to deal with hierarchal, treelike objects. The “percolate values upward” form of the evaluation rule is an example of a general kind of process known as tree accumulation.

To evaluate a combination, do the following:

1. Evaluate the subexpressions of the combination
2. Apply the procedure that is the value of the operator to the operands

graph TD;
  390-->*;
  390-->26
  390-->15
  26-->+
  26-->2
  26-->24
  15-->+_
  15-->3
  15-->5
  15-->7
  24-->*_
  24-->4
  24-->6

The exceptions to the general evaluation rule are special forms. Each special form has its own evaluation rule.

The various kinds of expressions (and associated eval rule) constitute the syntax of a programming language.

1.1.4 Compound Procedures

A procedure definition is a abstraction technique by which a compound operation can be given a name and then referred to as a unit.

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

We can read this as:

`(define (square     x)        (*      x      x     ))`
  |          |       |          |      |      |
  To      square something, multiply  it by itself

The special form for a procedure definition is:

(define([name] [formal params]) [body])

in which:

• name is a symbol to be associated with the procedure definition
• formal params are the names used within the body of the procedure to refer to the arguments of the procedure
• body is an expression that will yield the value of the procedure application when the formal params are replaced by the actual arguments.

1.1.5 The Substitution Model for Procedure Application

We can assume a basic evaluation mechanism of: To apply a compound procedure to arguments, evaluate the body of the procedure with each formal param replaced by the corresponding argument.

This is the Substitution Model for Procedure Application. The purpose is to help us think about procedure application, not to provide a description of how the interpreter really works. In practice, the “substitution” is accomplished by using a local environment for the formal parameters.

Let’s discuss two evaluation methods:

• Normal-Order Evaluation: “fully expand, then reduce”. Substitute operand expressions for parameters until an expression with only primitives is reached, and then evaluate
• Applicative-Order Evaluation: “evaluate the arguments, then apply”. Evalute the operator and operands and then apply the resulting procedure to the resulting arguments

For:

def square(x) do
  x * x
end
def sum_of_squares(x, y) do
  square(x) + square(y)
end

Normal-Order Evaluation

scheme

(sum_of_squares (+ 5 1) (* 5 2))
(+   (square (+ 5 1))      (square (* 5 2))     )
(+   (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2))  ) ; primitives reached, note the multipduplicated eval
(+   (* 6       6)         (* 10      10)       )
(+   36                    100                  )

elixir

sum_of_squares((5 + 1), (5 * 2))
square(5 + 1)       + square(5 * 2)
((5 + 1) * (5 + 1)) + ((5 * 2) * (5 * 2)) # primitives reached, note the duplicated eval
( 6      *  6)      + ( 10     *  10)
  36                +   100

Applicative-Order Evaluation

scheme

(sum_of_squares (+ 5 1) (* 5 2))
(sum_of_squares 6       10          )
(+   (square (6))        (square (10)) )
(+   (* 6 6)             (* 10 10)     )
(+   36                  100           )

elixir

sum_of_squares((5 + 1), (5 * 2))
sum_of_squares(6, 10)
square(6)  + square(10)
(6 * 6)    + (10 * 10)
36         +   100

1.1.6 Conditional Expressions and Predicates

A useful idiom is to be able to define tests and to perform different operations depending on the result of a test. This construct is case analysis. The form is:

(cond (([p1] [e1])
      ([p2] [e2])
      ([p3] [e3]))
      (else [e4]))

([p1] [e1]) is known as a clause. [p1] is known as the predicate. [e1] is the consequent expression. else is a special sumbol that can be used in place of the p as the final clause.

The word predicate is used for expressions or procedures that return true or false.

If there are precisely two cases in a case analysis, the special form if can be used:

(if [p] [c] [a])

[p] is known as the predicate. [c] is the consequent. [a] is the alternative.

Compound predicates can be constructed using logical operators:

(and [e1] [e2])
(or [e1] [e2])
(not [e])

and evaluates each expression left-to-right. If any expression is false, then the value of the and expression is false. If all evaluate to true, the value of the and expression is the final expression.

or evaluates each expression left-to-right. If any of the values of the expressions evaluate to true, that is the result of the or expression. If none of the expressions evaluate to false, then the or expression’s value is false.

Note that in scheme, and and or are special forms as not all expressions may need to be evaluated. not is an ordinary procedure.

1.1.7 Example: Square Roots by Newton’s Method

Mathematical functions are not identical to computer procedures. Procedures must be effective.

This contrast is a reflection of describing the properties of things vs. how to do things:

• Imperative: how to?
• Declarative: what is?

1.1.8 Procedures as Black-Box Abstractions

A computation can be broken down into several subproblems. Each of these tasks is achieved by a different procedure.

Each procedure should accomplish an identifiable task. Procedural abstraction allows you to use a procedures without concern for how, but what they do.

The meaning of a procedure should be independent of the parameter names used by its author. Parameter names must be local to body of the procedure.

Bound Variable: a formal parameter of a procedure that is bound by the procedure definition.

Free Variable: an unbound variable.

Scope: the set of expressions for which a binding defines a name.

Block Structure: a nesting of definitions, so that local subprocedures can be internalized by the procedure.

Lexical Scoping: free variables in a procedure are taken to refer to bindings made by enclosing procedure definitions.

Exercises

Exercise 1.3

Define a procedure that takes three numbers as arguments and returns the sum of the squares of the two larger numbers.

defmodule SquareSum do
  def square(x) do
    x * x
  end

  def sum_of_squares(x, y) do
    square(x) + square(y)
  end

  def evalLargerTwo(x, y, z) do
    cond do
      # Note this cumbersome logic finds the two largest by 
      # laying out the order of all three params
      # Unnecessary! 
      # Ask: 
      #  - what is the question the function is answering?
      #  - what is the minimal amount of information required to answer?
      # 
      # x >= y and y >= z -> sum_of_squares(x, y)
      # y >= z and z >= x -> sum_of_squares(y, z)
      # z >= y and z >= x -> sum_of_squares(y, z)

      # Note cleaner logic only finds the smallest, not the order
      z <= x and z <= y -> sum_of_squares(x, y)
      x <= y and x <= z -> sum_of_squares(y, z)
      true -> sum_of_squares(x, z)
    end
  end
end

IO.puts(
  "Test 1, 2, 3: " <>
    to_string(SquareSum.evalLargerTwo(1, 2, 3) == SquareSum.sum_of_squares(2, 3))
)

IO.puts(
  "Test 3, 1, 2: " <>
    to_string(SquareSum.evalLargerTwo(3, 1, 2) == SquareSum.sum_of_squares(2, 3))
)

IO.puts(
  "Test 3, 2, 1: " <>
    to_string(SquareSum.evalLargerTwo(3, 2, 1) == SquareSum.sum_of_squares(2, 3))
)

IO.puts(
  "Test 5, 5, 5: " <>
    to_string(SquareSum.evalLargerTwo(5, 5, 5) == SquareSum.sum_of_squares(5, 5))
)

Exercise 1.5

(define (p) (p))

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

(test 0 (p))

What behavior will one observe with an interpreter that uses applicative-order evaluation?

Given that AOE stipulates “eval, then apply”, this will result in an infinite loop:

• 0 will eval to 0
• (p) will eval to (p)
• (p) will eval to (p)…

What behavior will one observe with an interpreter that uses normal-order evaluation?

Given that NOE stipulates “expand, then reduce”, this will result in:

• (text 0 (p))
• (if (= 0 0) 0 (p))
• (= 0 0) will be hit and evaluation will trigger, yielding the consequent 0

defmodule RecursiveDanger do
  def p do
    p()
  end

  def test(x, y) do
    if x == 0 do
      0
    else
      y.()
    end
  end
end

defmodule RecursiveInfinite do
  def p do
    p()
  end

  def test(x, y) do
    if x == 0 do
      0
    else
      y
    end
  end
end

# in Elixir, I tell it when to eval a function and thus
# have control over whether to invoke a loop:
# conditionally:
# RecursiveDanger.test(0, fn -> RecursiveInfinite.p() end)
# on purpose:
# RecursiveInfinite.test(0, RecursiveDanger.p())

Exercise 1.6

Let’s say you define your own if function:

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

It works with primitive arguments:

(new-if (= 2 3) 0 5)

What will happen when you use it with complex expressions?

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

The parameter subexpressions will be evaluated before the procedure body itself is evaluated as new-if is a function.

Exercise 1.7

Newton’s method for computing square roots says that whenever we have a guess y for the value of the square root of a number x, we can compute a better guess by averaging y with x/y.

i.e. divide the number (the radicand) by the guess, and then average the quotient and the guess

If x = 2 and we guess y = 1, then we have:

“divide the radicand by the guess”

y/x => 2/1 = 2

“average the quotient and the guess”

q + y/2 => (2 + 1) / 2 = 1.5

We can then define a recursive function that successively calls this guessing function until a number that is sufficiently close to a predetermined tolerance is found. The text suggests a basic good-enough? test:

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

Why is good-enough insufficient for very small and very large numbers?

First let’s define a module with the existing logic:

defmodule NewtonSqrt do
  def average(x, y) do
    (x + y) / 2
  end

  def improve(radicand, guess) do
    average(guess, radicand / guess)
  end

  def good_enough(radicand, guess) do
    abs(guess * guess - radicand) < 0.0001
  end

  def sqrt_iter(radicand, guess) do
    if good_enough(radicand, guess) do
      IO.puts("Good: " <> to_string(guess))
      guess
    else
      IO.puts("Not Good: " <> to_string(guess))
      sqrt_iter(radicand, improve(radicand, guess))
    end
  end

  def sqrt(radicand) do
    sqrt_iter(radicand, 1)
  end
end

Let’s do a basic test:

NewtonSqrt.sqrt(16)

Now let’s try a very small number:

NewtonSqrt.sqrt(0.0000009876)

This is not correct. The initial good_enough function defines a tolerance of 0.0001. However the radicand in this case is smaller than the tolerance. Therefore the guess cannot, by definition, measure the correctness of the guess.

Now let’s try a very large number:

# Commenting out inifinite loop so livebook can eval
# NewtonSqrt.sqrt(1929472300180183)
# 43925758.9596376...
# 43925758.9596376...

We can see here that we are getting stuck in an infinite loop when the guess hits 43925758.9596376. What’s happening with good_enough on this number? Is it less than 0.0001?

abs(43_925_758.9596376 * 43_925_758.9596376 - 1_929_472_300_180_183)

It is not. Let’s improve the guess:

NewtonSqrt.average(43_925_758.9596376, 1_929_472_300_180_183 / 43_925_758.9596376)

Wait a minute! The improved guess is the same as the old one!

What we are witnessing here is a result of floating point rounding errors. Specifically we have reached the range in which the distance between two floating points are beyond the size of 0.001. The rounding error, the minimum precision, is greater than the specified tolerance.

An alternative would be to watch how guess changes from one iteration to the next and stop when the change is a very small fraction of the guess. Design a square root function that uses this sort of test.

defmodule BetterNewtonSqrt do
  def average(x, y) do
    (x + y) / 2
  end

  def improve(radicand, guess) do
    average(guess, radicand / guess)
  end

  def good_enough(previous_guess, guess) when is_integer(previous_guess) and is_integer(guess) do
    previous_guess == guess
  end

  def good_enough(previous_guess, guess) when is_float(previous_guess) and is_integer(guess) do
    guess = guess / 1.0
    good_enough(previous_guess, guess)
  end

  def good_enough(previous_guess, guess) when is_integer(previous_guess) and is_float(guess) do
    previous_guess = previous_guess / 1.0
    good_enough(previous_guess, guess)
  end

  def good_enough(previous_guess, guess)
      when is_float(previous_guess) and is_float(guess) and guess <= 1 do
    :erlang.float_to_binary(previous_guess, decimals: 253) ==
      :erlang.float_to_binary(guess, decimals: 253)
  end

  def good_enough(previous_guess, guess)
      when is_float(previous_guess) and is_float(guess) and guess > 1 do
    :erlang.float_to_binary(previous_guess, decimals: 6) ==
      :erlang.float_to_binary(guess, decimals: 6)
  end

  def sqrt_iter(radicand, guess) do
    if good_enough(guess, improve(radicand, guess)) do
      IO.puts("Good: " <> to_string(guess))
      guess
    else
      IO.puts("Not Good: " <> to_string(guess))
      sqrt_iter(radicand, improve(radicand, guess))
    end
  end

  def sqrt(radicand) do
    sqrt_iter(radicand, 1)
  end
end

BetterNewtonSqrt.sqrt(1_929_472_300_180_183)

BetterNewtonSqrt.sqrt(0.0000009876)