12.11 Chapter Summary

Programming languages support a variety of parameter-passing mechanisms. The pass-by-value and pass-by-reference parameter-passing mechanisms are widely supported in languages. Binding and assignment are different concepts. A binding is an association between an identifier and an immutable expressed value; an assignment is a mutation of the expressed value stored in a memory cell. References refer to memory cells or variables to which expressed values can be assigned; they refer to variables whose values are mutable. Most parameter-passing mechanisms, except for lazy evaluation, differ in either the direction (e.g., in, out, or in-out) or the content (e.g., value or address), or both, of the information that flows to and from the calling and called functions on the run-time stack.

Lazy evaluation is a fundamentally different parameter-passing mechanism that involves string replacement of parameters with arguments in the body of a function (called β-reduction). Evaluation of those replacement arguments is delayed until the value is required. Thus, unlike other parameter-passing mechanisms, consideration of data flowing to and from the calling and called functions via that run-time stack is relevant to lazy evaluation. The evaluation of an operand is delayed (perhaps indefinitely) by encapsulating it within the body of a function with no arguments, called a thunk. A thunk acts as a shell for a delayed argument expression. There are two implementations of lazy evaluation: Pass-byname is a non-memoized implementation of lazy evaluation, where the thunk for an argument is evaluated every time the corresponding parameter is referenced in the body of the function; and pass-by-need is a memoized implementation of lazy evaluation, where the thunk for an argument is evaluated the first time the corresponding parameter is referenced in the body of the function and the return value is stored so that it can be retrieved for any subsequent references to that parameter. Macros in C, which do not involve the use of a run-time stack, uses pass-by-name semantics of lazy evaluation for parameters. In a language without side effects, evaluating arguments to a function with pass-by-name semantics yields the same result as pass-by-need semantics.

The use of lazy evaluation in a programming language has compelling consequences for programs. Lazy evaluation enables infinite data structures that have application in a variety of artificial intelligence applications involving combinatorial search. It also enables a generate-filter style of programming akin to the filter style of programming common in Linux, where concurrent processes communicate through a possibly infinite stream of data flowing through pipes. In addition, lazy evaluation leads to straightforward implementation of complex algorithms (e.g., prime number generators and quicksort). It factors control from data in computations, thereby enabling modular programming. While possible, it is neither practical nor reasonable to support lazy evaluation in a language with provision for side effect because lazy evaluation requires the programmer to forfeit control over execution order, which is an integral part of imperative programming.

In this chapter, we introduced variable assignment (i.e., side effect) into Camille. We also implemented the pass-by-reference and lazy evaluation parameter-passing mechanisms. Finally, we introduced multiple imperative features into Camille, including statement blocks and loops for repetition. The Camille interpreter operationalizes some language concepts and constructs in the Camille programming language from first principles (e.g., local binding, functions, references), and others using the direct support for those same constructs in the defining language, here Python (e.g., while loop and compound statements).