Re: [Caml-list] strict?

[skaller <skaller@users.sourceforge.net>]

On Fri, 2006-08-04 at 14:03 -0400, Alan Falloon wrote:
> skaller wrote:
>  
> It sounds like you are talking about "lenient" evaluation. I was looking 
> into this stuff a while ago. As far as I can tell, there aren't many 
> papers out there about it, but this one is pretty good: 
> http://www.cs.cmu.edu/~seth/lenient.pdf.
> 
> The citeseer page might get you some more info 
> http://citeseer.ist.psu.edu/schauser95how.html

I had a read of some of that, but it isn't clear to me
whether my 'sloppy' evaluation is the same as 'lenient'.

As I understand it, lambda calculus has a few possible
orders of applying reductions, which are the evaluation
strategies. 'Lenient' evaluation looks like just another
determinate order, whereas 'sloppy' means the order
is indeterminate (but I'm sure I didn't understand 
the paper!)

However what I'm aiming for is to provide both lazy
and eager evaluation, and let the programmer specify which
to do on a 'case by case' basis .. as well as provide
for 'default' cases whether the compiler makes the choice.

I'm trying to wrap my brain around the ideas so I can
understand the right constructions .. perhaps another
way of saying this is: when something gets evaluated
at the wrong time, when it is a design bug in my
system, and when can I just blame the programmer
for not being specific enough about their intent?

In Ocaml, for example, it is the programmers fault if
side effects in 

	f e1 e2 e3

don't happen in the expected order: the manual says the
order of evaluation is indeterminate AND there is a way
to force the order:

	let a1 = e1 in
	let a2 = e2 in
	let a3 = e3 in
	f a1 a2 a3

To turn that around, if you want the compiler to try
to do a good job optimising, you give it freedom and write

	f e1 e2 e3

when e1,e2,e3 *dont* have side effects. This has the downside
you can't factor complex expressions .. so in Felix:

	var a1 = e1; // note 'var=variable'
	var a1 = e2;
	var a3 = e3;
	return f a1 a2 a3;

forces eager evaluation, but perhaps you could write

	val a1 = e1; // note 'val=value'
	val a2 = e2;
	val a3 = e3;
	return f a1 a2 a3;

and it doesn't. The compiler is free to substitute the
values to which a1,a2,a3 are bound for occurrences of
a1,a2,a3 respectively (this is just illustration).

Of course even in the 'eagerly strict' case, the compiler
can use the 'as if' rule to perform optimisations based
on analysis. And, conversely, in the sloppy case the compiler
can also perform the analysis and warn in some cases that
behaviour is indeterminate. The difference is when the
compiler's analysis is incomplete, what assumptions
it makes in the two cases. (Also add 'lazy' option,
which I think I'll encode 'fun a1 => e1 ..')

So basically most languages provide
constructions with explicit evaluation orders, but not
very many 'let the compiler chose' constructions:
order of argument evaluation is one in Ocaml. For inlining
functions, the 'sloppy' case allows usage analysis
followed by a choice of substitution where used (lazy
evaluation) or eager evaluation (to save recomputations).
Substitution is particularly efficient in some cases
because it helps eliminate closures. So I want the programmer
to use 'val'ues where possible .. and the question arises,
what exactly does 'where possible' mean?

The only way to reason in the presence of indeterminate
evaluation order is when it makes no difference.
So the question is -- exactly when doesn't it matter?

-- 
John Skaller <skaller at users dot sf dot net>
Felix, successor to C++: http://felix.sf.net