Evaluation Stategy

Felix has an unusual evaluation strategy, so it is worth seeing how this came about.

As a high level language designed to integrate as seamlessly as possible with C and C++ without being stuck with their disasterous syntax, the Felix language does not define primitive types and operators. Instead, the language provides type combinators such as tuples, arrays, unions, functions and procedures, and requires the user to lift primitives from C/C++ with special binding constructions. Here's an example:

0001:  type Int = "int";
0002:  const Zero = "0";
0003:  const One = "1";
0004:  fun add : Int * Int -> Int = "$1+$2";
0005:  ctor int : Int = "$1";
0006:  ctor Int : int = "$1";
0007:  var x = add (One, add (One, One));
0008:  assert x.int = 3;
0009:  

I hope its clear what's going on. You can mouseover coloured words for more information. Briefly the type binder lifts a type from C++ to Felix, the const binder lifts a value and the fun binder defines a function. The ctor binder is a special function definition that defines a type conversion from the argument type to the type used as the function name.

So now, the question is: how should the variable assignment of x look in C++?  There are two possible answers:

  int x = (1 + 1) + 1;

is the obvious answer. A less obvious answer is:

  int One = 1;
  int tmp = One + One;
  int x = tmp + One; 

The first answer uses substitution. The generated code resembles the source. It seems more efficient and is this is the strategy Felix usually adopts. The second answer unravels expressions into subterms each of which is assigned to a temporary. Felix sometimes does this, simply for clarity of the generated code.

If you think this is all obvious .. think again! The first method is lazy evaluation, the second is eager evaluation. These two strategies don't always do the same thing! For example:

0001:  fun cond: bool * int * int -> int = "$1?$2:$3";
0002:  var x = 1;
0003:  var y = 0;
0004:  println$ cond(y == 0, 0, y / x);
0005:

it is clear the lazy method will result in 0 being printed whereas the eager method will cause a division by zero error. This is in fact because the C conditional operator uses lazy evaluation, sometimes called short cut evaluation in C circles.

So lazy evaluation is not only often faster than eager evaluation, it is also more powerful because it can yield results which would cause an exception with eager evaluation. There are also other cases where eager evaluation leads to a infinite loop whilst lazy evaluation does not.

 Although lazy evaluation would seem the best, and is indeed the strategy mandated by Haskell, it has a serious problem. If a functions uses an argument many times, the expansion can not only result in code bloat but clearly a performance loss. It may be possible to fix this with a technique known as memoisation which involves saving the calculated value the first time the calculation is done.

However there's yet another problem: how can we implement lazy evaluation without expanding a function definition for every call of the function? It's not just the code bloat that's the problem here: if the function is separately compiled, the definition may not be available to expand!

The solution is to use a construct known as a closure. This is just a function together with its environment and arguments, but not evaluated yet. The evaluation is deferred. We pass the closure to our function and it evaluates it when the argument is needed. This technique also lends itself to memoisation.

But there's a problem. Closures are expensive to construct. In Felix they're heap allocated C++ class objects, and this also poses a memory management problem.

In these circumstances where a function isn't inlined, we generally prefer to evaluate the arguments eagerly. This technique is used in C and is familiar: we evaluate the argument and assign the result to a local variable.

So in review: we will get the best performance in many cases by lazy evaluation, when it involves a small number of substitutions. In cases of multiple use of an argument, or where the function cannot be cloned to allow replacing parameters with arguments, we get best performance from eager evaluation.

I call the evaluation strategy in which the compiler can choose either eager or lazy evaluation indeterminate evaluation, and this is the default evaluation strategy used by Felix. The system provides ways for the programmer to override the default.  Felix ensures variables assignments have eager semantics, and supports values of function type to allow closures to be passed as arguments.

Finally, there is an important question to ask: when does it actually make a difference which strategy is chosen. We will answer this question indirectly by explaining when it does not make a difference. A function will be called strict if it fails to return normally when given an argument the evaluation of which does not return normally.

If a function has multiple arguments we instead ask whether the function is strict in a particular argument. For example conditional evaluation is strict in the condition argument, but it is not strict in the true and false case arguments.

And now we can state our result: if a function is strict, the semantics of lazy and eager evaluation are identical, and we're free to choose either strategy based entirely on convenience or performance considerations.
Now we need another definition. A function is pure if it depends only on its arguments. It may not depend on a variable outside its scope, although variables inside the function are OK. It may not depend on a variable accessed via a pointer, nor on any mutable state hidden by an abstraction. The key feature of a pure function is that if it returns normally, it will always map its argument to the same value every call.

In Felix, functions may not have side-effects. However they do not need to be pure. Clearly a pure function can be evaluated at any time, so if a function is strict and an argument is pure, indeterminate evaluation has determinate semantics. This is now clear!

Now clearly, if a function is impure, it can depend on a variable. However an impure closure passed into a function still had determinate semantics with indeterminate evaluation. This is because during the lifetime of the function, the value of the variable cannot change because side-effects aren't allowed. And the clear corollary is that purity of the argument of a procedure really does matter because the procedure may change a variable an impure closure argument depends on.

It is important to note the qualification for functions, that it doesn't matter if a closure is pure or not inside a function: it does matter if the closure is returned because this delays the evaluation of the closure to some indeterminate time in the future, and in between the variable it depends on may change.

Now an example:

0001:  var x = 1;
0002:  fun get () => x; // impure
0003:  var f = get; // closure
0004:  println$ f(); // 1
0005:  x = 2;
0006:  println$ f(); // 2

It's clear that get is not only impure .. it's meant to be. Most get functions are impure because they're intended to fetch a mutable value. The its clear why the closure f yields different results each call, because its just the get function! Closures capture their environment, but for variables this means they capture the variable not the current value of it.

Now I know this seems obvious but now we can finally understand the following gotcha:

0001:  for var i in 1 upto 3 do spawn_fthread { println$ i; }; done
0002:  var lst = Empty[1->0];
0003:  for i in 1 upto 3 do lst = lst + { println$ i; }; done;
0004:  for p in lst do p(); done

which prints:

3
3
3
3
3
3

This is not a bug! Nor is it a reason to fear indeterminate evaluation. Here's the answer:

0001:  var lst = Empty[1->0];
0002:  noinline proc capture (var i: int) () { println$ i; }
0003:  for var i in 1 upto 3 do lst = lst + capture i; done;
0004:  for p in lst do p(); done

This only works if capture is noinline. This is quite tricky! Even when constructing this example I got it wrong myself! So we have to do the analysis by desugaring the code:

0001:  fun capture (var i: int) = { 
0002:    proc inner () {
0003:      println$ i; 
0004:    }
0005:    return inner;
0006:  }

Now we can see that if capture is inlined, it is always returning its argument. Even though i is eagerly evaluated to the loop control variable i, the procedure inner is referring to a single variable. So when it is evaluated, it returns the current value of i which is 3 at the time all three copies of the procedure are executed. To fix this we need three copies of capture each with its own variable i, in other words, we need to ensure capture is a closure and not inlined. Then each copy of inner refers to its separate enclosing scope, namely a discrete copy of capture.

In case you think, hey, this is all wrong.. no, remember the whole point of a get function is to return the current value of a variable.