CSci 450-01: Organization of Programming Languages
CSci 503-01: Fundamental Concepts in Languages
Fall 2014

Note: This set of notes should be expanded to talk about the substitution model for execution.

Evaluation Concepts and Terminology

Here are a few related concepts:

• Applicative order reduction.

  Reduce leftmost innermost reducible expression (redex) first order.

  Eager evaluation.

  Evaluate any expression that can be evaluated regardless of whether the result is ever needed. (For example, arguments of a function are evaluated before the function is called.)

  Strict semantics.

  A function is only defined if all of its arguments are defined. For example, multiplication is only defined if both of its operands are defined, 5 * UNDEFINED == UNDEFINED.

  Call-by-value parameter passing.

  Evaluate the argument expression and bind its value to the function's parameter.

• Normal order reduction.

  Reduce leftmost outermost redex first.

  Lazy evaluation.

  Do not evaluate an expression unless its result is needed.

  Nonstrict (lenient) semantics.

  A function may have a value even if some of its arguments are undefined.

  Call-by-name parameter passing.

  Pass the unevaluated argument expression to the function; evaluate it upon each reference.

In general, call-by-name parameter passing is inefficient. However, a referentially transparent language like Haskell can replace call-by-name parameter passing with the equivalent, but more efficient, call-by-need method.

In the call-by-need method, the unevaluated argument expression is passed to the function as in call-by-name. The first reference to the corresponding parameter causes the expression to be evaluated; subsequent references just use the value computed by the first reference. Thus the expression is only evaluated when needed and then only once.