# 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:

square x = x * x

an instance of $\emph{square}\;x$ is replaced with the corresponding instance of $x*x$. For example, $4+\emph{square}\;(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]:

from n = n : from (n+1)

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

[1,2,3,...

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

nth n (x:xs) = if n==1 then x else nth (n-1) xs

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

The reason is that only the third element of “from 1” is needed for the result. All the other elements, in particular the infinite sequence of elements past the third one, do not need to be evaluated.

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:

fibolist x0 x1 = x0 : fibolist x1 (x0+x1)

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

The evaluation strategy of the PAKCS compiler/interpreter, which is used for all our examples, is lazy, but incomplete. The strategy evaluates non-deterministic choices sequentially instead of concurrently.

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:

square x = x * x

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.