3.12 Lazy Evaluation

The evaluation of an expression $t$ is the process of obtaining a value $v$ from $t$.

A value is an expression consisting only of builtin literals and/or data constructors and/or variables.

The value $v$ is obtained from $t$ by replacing an instance of the left-hand side of a rule with the corresponding instance of the right-hand side. For example, referring to the function square defined in Section 3.5.1:

an instance of $\text{<em class="ltx\_emph ltx\_font\_italic">square</em>}x$ is replaced with the corresponding instance of $x*x$. For example, $4+\text{<em class="ltx\_emph ltx\_font\_italic">square</em>}(2+3)$ is replaced by $4+(2+3)*(2+3)$.

The evaluation of an expression $t$ proceeds replacement after replacement until an expression $v$ in which no more replacements are possible is obtained. If $v$ is not a value, the evaluation fails, otherwise $v$ is the result of a computation of $t$. For example, the following function head computes the first element of a (non-null) list:

An attempt to evaluate “head []” fails, since no replacement is possible and the expression is not a value since it contains a function.

Often, an expression may contain several distinct replaceable subexpressions, e.g., from $(2+3)*(2+3)$ we can obtain both $5*(2+3)$ and $(2+3)*5$. Even a single subexpression may allow several distinct replacements when non-deterministic functions are involved. The order in which different subexpressions of an expression are replaced is not determined by a program. The choice is made by an evaluation strategy. The semantics of the language guarantees that any value obtainable from an expression is eventually obtained. This property is referred to as the completeness of the evaluation. To ensure this completeness, expressions must be evaluated lazily. A lazy strategy is a strategy that evaluates a subexpression only if its evaluation is unavoidable to obtain a result. The following example clarifies this delicate point.

The following function computes the list of all the integers beginning with some initial value $n$ [Browse Program][Download Program]:

An attempt to evaluate “from 1” aborts with a memory overflow since the “result” would be the infinite term:

However, the function “from” is perfectly legal. The following function returns the $n$-th element of a list:

The expression “nth 3 (from 1)” evaluates to 3 despite the fact that “from 1” has no (finite) value:

lazy> nth 3 (from 1)
3

Infinite data structures are an asset in the conjunction with lazy evaluation. Programs that use infinite structures are often simpler than programs for the same problem that use finite structures. E.g., a function that computes a (finite) prefix of “[1,2,3,...” is more complicated than “from”. Furthermore, the functions of the program are less interpedendent and consequently more reusable. E.g., the following function, initially applied to 0 and 1, computes the (infinite) sequence of the Fibonacci numbers:

The function “nth” can be reused to compute the $n$-th Fibonacci number through the evaluation of the expression “nth $n$ (fibolist 0 1)”, e.g.:

lazy> nth 5 (fibolist 0 1)
3

All the occurrences of same variables are shared. This design decision has implications both on the efficiency and the result of a computation. For example, consider again the following definition:

The evaluation of say square $t$ goes through $t$ * $t$. Without sharing, $t$ would be evaluated twice, each evaluation independent of the other. If $t$ has only one value, the double evaluation would be a waste. If $t$ has more then one value, this condition will be discussed in Section 3.13.1, sharing produces the same value for both occurrences.