101.01 - Functions and evaluation

Programming Paradigms

  • imperative (Java, C/C++)

    • modifying mutable variables using assignments;
    • control structures (if-then-else, loops, breaks, etc);

  • functional (Scala, Haskell)

  • logic (Prolog, Datalog)

OO programming is orthogonal to the above.

Imperative languages emulate instruction sequences for a Von Neumann computer. A Von Nuemann computer has a Processor, Memory and a Bus that links them. The Bus is used to read both instructions and data from Memory into the Processor. The "width" of the Bus is one machine-word (32-bits or 64-bits nowadays). There's a strong correspondence between:

Mutable variables ~~ memory cells
Variable dereferences ~~ load instructions
Variable assignments ~~ store instructions
Control structures ~~ jumps

How can we avoid conceptualising programs word by word?

John Backus - "Can Programming Be Liberated from the Von Neumann style?", 1978: imperative programming is limited by the "Von Neumann" bottleneck. We need other ways of defining high-level abstractions (collections, polynomials, shapes, strings, etc) through teories. A theory consists of:

  • one or more data types;
  • operations on the data types;
  • laws that describe the relationships between values and operations;

Theories DON'T describe mutations. For instance, the theory of polynomials defines sums of polynomials like this:

(a * x + b) + (c * x + d) = (a + c) * x + (b + d)

but does not define an operator to change a coefficient while keeping the polynomial the same, like in the following imperative program:

class Polynomial{ 
    public double [] coefficient;
}
Polynomial p = ...;
p.coefficient[0] = 42;

Similarly, the theory of strings defines a concatenation operator ++ which is associative:

(a ++ b) ++ c = a ++ (b ++ c)

but doesn't define an operator to change a sequence element while keeping the sequence the same.

Elements of Programming

Programming languages provide:

  • primitive expressions;
  • ways to combine them;
  • ways to abstract them (i.e. give them a name)

Expression evaluation

  1. Take the leftmost operator
  2. Evaluate its operands
  3. Apply the operator to the operands

The evaluation stops once it results in a value.

Function application evaluation

  1. Evaluate arguments, left to right;
  2. Replace the function application by the function's right-hand side, and
  3. Replace the formal parameters by the actual arguments;

Substitution model

The above evaluation schemes describe the substitution model that reduces a given expression to a value. It can be applied to all expressions. The substitution model is formalised in the lambda-calculus (Alonzo Church). The substitution model can only be applied to expression without a side-effect, like for instance:

x++

Here, the expression has a side-effect (the value of x is incremented between calls), so the expression cannot be evaluated by using the substitution model.

Not all expressions reduce to a values in a finite number of steps. For instance:

def loop: Int = loop

Applying the substitution model to the above expression leads to the following:

loop -> loop -> loop -> ...

Call by value

Function arguments are evaluated prior to applying the function:


sumOfSquares(3, 2 + 2)
sumOfSquares(3, 4)
square(3) + square(4)
3 * 3 + square(4)
9 + square(4)
9 + 4 * 4
9 + 16
25

Call by name

Function arguments are evaluated after applying the function:


sumOfSquares(3, 2 + 2)
square(3) + square(2 + 2)
3 * 3 + square(2 + 2)
9 + square(2 + 2)
9 + (2 + 2) * (2 + 2)
9 + 4 * (2 + 2)
9 + 4 * 4
9 + 16
25

Call-by-value vs Call-by-name

Both strategies reduce to the same value as long as:

  • the reduced expressions consists of pure functions and
  • both evaluations terminate

Call-by-value has the advantage that all arguments are evaluated only once.

Call-by-name has the advantage that a function argument is not evaluated if not used.

Evaluation strategies and termination

  • If CBV evaluation terminates, the CBN evaluation also terminates and both render the same result;
  • If CBN evaluation terminates, CBV isn't sure to terminate;

Scala allows passing parameters as both CBV and CBN (default is CBV, because it is more efficient):

def constOne(x: Int, y: => Int) = 1

Conditionals and value definitions

Conditional expressions are like in Java, but for expressions, not statements:

def abs(x: Int) = if (x >= 0) x else -x

x >= 0 is a Predicate.