Is “lazy evaluation” part of the compilation process or a run-time feature?

I'm studing the Clean functional programming language, and like other functional PL it uses Lazy Evaluation.

The thing that I can't get is when a PL that using that kind of evaluation evaluates the needed parameters. Does the compiler recognize which parameters are used and generate the code for evaluating them? or maybe some run-time mechanism takes responsibility to evaluate the parameters?

I am not familiar with Clean; this answer addresses Lazy Evaluation in general.

Lazy evaluation happens at runtime.

The most fundamental form of lazy evaluation is leftmost reduction in lambda calculus. I will not burden this answer with a full introduction to lambda calculus. The intuition is that terms in lambda calculus consist of function definitions and function applications (and little to nothing else). Runtime of a program (which is a term) means evaluating the term. For an application term (which you can think of as $$f(a)$$), both $$f$$ and $$a$$ are also terms. Evaluating $$f(a)$$ may entail evaluating $$f$$ and/or $$a$$. The principle of leftmost reduction (lazy evaluation) means that $$f$$ is evaluated before $$a$$. Let us say $$f$$ is the function defined by $$f(x)=x+x$$ and $$a$$ is the term $$1+2$$. Then, lazy evaluation proceeds with the following steps:

1. $$f(a)$$
2. $$a+a$$
3. $$(1+2)+a$$
4. $$(1+2)+(1+2)$$

(At least if $$+$$ does not have a definition of its own. If it has, then after 2. the definition of $$+$$ will be expanded.)

If, on the other hand, $$f$$ is defined by $$f(x)=0$$, the evaluation is

1. $$f(a)$$
2. $$0$$

You notice that $$a$$ is not evaluated (because it is not needed), hence the connection to lazy evaluation. One final comment on this part: Lambda terms are in prefix notation, so "leftmost" actually means "outermost" when you think in terms of nested function applications.

In the second example above, lazy evaluation led to a speedup, because the term $$a$$ was not evaluated. In the first example, it led to a slowdown, because $$a$$ was evaluated twice. Actual lazily evaluated functional programming languages usually (again, I am not familiar with Clean) make the following optimization: Terms are not stored as syntax trees but as syntax dags. That is, in the first example, the two $$a$$ in term 2 would be the same node, also shared among all other positions of all other terms into which $$a$$ might have been copied. As soon as lazy evaluation dictates that $$a$$ is evaluated, the result is stored in place of the node $$a$$, becoming immediately available at all other occurences of $$a$$. The effect is a bit like memoization.

• (Almost) all evaluation happens at runtime, whether lazy or not. In a compiled language, the compiler must produce code to perform the evaluation. The only question is the order of computation. (Of course, that's highly simplified. But compiling lazily evaluated languages is clearly possible: both Haskell and Clean are compiled.) – rici Jul 7 '19 at 23:28