Tuesday, March 19, 2013

Lazy Evaluation

The basic idea of lazy evaluation is that the machine doesn't do any work unless we know it needs to.  Modern imperative programming languages almost always have a certain amount of lazy evaluation in expressions, but if you give the machine a list of instructions in an imperative program, the machine will execute them all, regardless of whether they are needed for the final result.

Part of the reason for this is that the compiler can't hope to keep track of all of the side-effects of imperative commands and determine whether a command is necessary.  In functional programming, however, there is the idea of "pure" functions, which have no side effects, so we can say categorically that they need not be evaluated unless we know we need their results.

When we say that a pure function has no side-effects, we not only mean that it does not impact the outside world, but also that it does not draw input from the outside world.  In other words, the result of a pure function depends on nothing other than the content of the function and its inputs.

We will implement aggressive laziness in Toyl by letting the system choose which expressions to evaluate, and allowing it to evaluate them in whatever order is necessary.  Not only that, but within the body of the function, we will evaluate bound variables and parameters only when (or if) we need them.

Going back to our sample closure (Fig. 4.1), and continuing to develop this idea using C# syntax, we can make the environment variables z and k into attributes whose underlying expressions are not evaluated until they are needed, as follows:
class MyFunction {
    // Environment Part
    public ISignature<int32> z;
    public int32 z {
        get {
            return this._z.Value();
        set {}

    public ISignature<int32> k;
    public int32 k {
        get {
            return this._k.Value();
        set {}


Fig. 6.1: A closure with lazy environment variables
Doing this with the parameters x and y is not as slick in C# syntax, so here is one area where we will begin to depart from what we can easily express in C#.  To implement lazy evaluation of the parameters, we would need syntax like this:
// Control Part
public DateTime Value(ISignature<DateTime> x, ISignature<int32> y) {
    return x.Value().AddYears(int.Parse(y.Value().ToString()) + z * k);

Fig. 6.2: Lazy evaluation of parameters
In the next post, I'll address how to handle a mixed environment where not all functions can be pure.

No comments:

Post a Comment