lazy eval

[John Skaller2]

I need to fix the lazy eval issue. Here is some analysis.

For primitive bindings a function like:

fun ite: c * b * b -> b = “$1?$2:$3”;

can fail because whilst the second and third arguments are substituted, which is lazy
evaluation, they can be pre-processed eagerly, for example

var r = ite (c, texpr,fexpr);

can be expanded to

var t = texpr;
var f = f expr;
var r = ite (c,t,f);

so that the true and false conditions are eagerly evaluated, leading to a crash
in a case like

ite (b==0,0,a/b)

which does a division by zero. A way to prevent lifting subexpressions out
of primitive function arguments is needed.

In Felix, the way to do this is mess: you pass a closure and invoke it on demand:

fun ite (c:bool, t: 1-> int, f: 1-> int) => match c with
| true => #t
| false => #f
;

however this can be inefficient because Felix isn’t good at closure elimination.
In fact .. the semantics more or less rely on the fact that closures can’t be
eliminated (because if they were their bodies might be subject to lifting).

For primitives you can also pass a Felix function closure, although it’s hard
do because you don’t know the type in C++ terms (though with auto, it could
be easier in C++11). Also we could pass a C++ lambda. In fact, if Felix closures
had operator (), we could pass any callable (including C functions, Felix closures,
and lambdas as well as anything else). However the code would be like
Felix functions, you’d have to explicitly invoke the callable, which isn’t hard:

$1.()

for example! However we’d be relying on C++ compiler to eliminate the
callable. For C++ it should be possible to pass a T directly and just
prevent lifting,, which ensures substitution and hence laziness.
But the type is NOT the same as passing a closure.

For Felix functions, if inlined we can also do substitution. It’s impossible
to directly substitute in that same function if it’s a closure and we lose
track of the function body (eg indexing an array of closures). In this case
we have to pass a closure to the closure.

So for the C stuff, we could us the notation

lazy T

or just

{T}

The problem is to wrap a “nolift” constructor around the corresponding
argument:

{e}

isn’t quite right, because that’s a function 1->T.





—
John Skaller
ska...@internode.on.net