RE: [Caml-list] strict?

RE: [Caml-list] strict?

[Alexander Bottema]

When writing real compilers, strictness is not that interesting. What we
focus on is whether a function is side-effect free or program-effect
free. Side-effect free basically practically means not doing I/O and
program effect free practically means that we don't write to "unknown"
locations in the heap/memory.

We then allow certain transformations based on whether functions are
side-effect free or program-effect free. You can probably imagine other
categories as well. After all, it is what kind of
optimizations/transformations that you'd like to do that gives your
domain of parameters to control them.

When I learned the concept of strictness it was in the context of pure
functional programming. For me the definition was mostly there to
distinguish non-strict functions, such as if(e,t,f) from other
functions. Bottom encodes essentially two different things,
non-termination or "domain error". The non-termination aspect is crucial
for non-strict functions such as if, since the non-termination of 't' or
'f' may not imply that if() itself will not terminate. However, in real
compiler design, the number of non-strict functions is very small and
usually built-ins. However, this is of course not true if you implement
lazy functional programming languages where basically everything is
non-strict.

Alexander

-----Original Message-----
From: caml-list-bounces@yquem.inria.fr
[mailto:caml-list-bounces@yquem.inria.fr] On Behalf Of skaller
Sent: Thursday, August 03, 2006 07:13 AM
To: O'Caml Mailing List
Subject: [Caml-list] strict?

I'm looking for a pair of concepts such as

nice function/transparent expression

which allow an arbitrary choice of evaluation strategy.

A nice function is basically one like 'sin' which is
total, has no side effects, depends only on its arguments,
and always returns a value. I think this is basically
'total, pure and strict'.

A transparent expression is one which can be evaluated
at any time, anywhere. For example 'sin 1.0' is the same
no matter when and where it is evaluated. More or less
an expression is transparent if it is a constant or
application of nice functions to transparent arguments.

The idea is basically to know when a compiler can choose
the evaluation strategy based on performance, without
worrying that this will change semantics. More precisely
my translator *already* does this .. and I want to know
when this is justified (so I can figure out how to
give the programmer enough annotations and control
to get the result they want, and be able to reason
about their code).

Note I use the word 'function' in the C (or Ocaml) sense here.
Clearly the Wikipedia definition of strict:

	f(bottom) = bottom

is rubbish when applied to a mathematical function like 'sin', 
since bottom isn't a valid argument, but it makes sense
for 'sin' in the programming language sense.


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

_______________________________________________
Caml-list mailing list. Subscription management:
http://yquem.inria.fr/cgi-bin/mailman/listinfo/caml-list
Archives: http://caml.inria.fr
Beginner's list: http://groups.yahoo.com/group/ocaml_beginners
Bug reports: http://caml.inria.fr/bin/caml-bugs

RE: [Caml-list] strict?

[skaller]

On Thu, 2006-08-03 at 08:29 +0100, Alexander Bottema wrote:
> When writing real compilers, strictness is not that interesting. What we
> focus on is whether a function is side-effect free or program-effect
> free. 

In Felix, procedures have side effects, and
functions don't (they're both 'functions' in the C programming sense
which is a bit confusing)

However, a function can contain variables and modify them.
In Ocaml, you can have a function with no side effects too,
but which contains variables:

	let f () = 
		let a = ref 0 in
		let g () = !a in
		let b = g () in
		a := 1;
		let c = g() in
		b + c


Here 'a' is a mutable variable, however f doesn't have side effects.
What's more the evaluation semantics for g() are critical
because it depends on a variable.

Clearly, we can't evaluate lazily or we get the 'wrong' answer:

	g() +g()

would return 2 instead of 1.

> We then allow certain transformations based on whether functions are
> side-effect free or program-effect free. You can probably imagine other
> categories as well. After all, it is what kind of
> optimizations/transformations that you'd like to do that gives your
> domain of parameters to control them.

Indeed, but that's the question. Generally I want the compiler
to chose whether to inline a function or not, and how to
inline arguments into the inlined function. For simple functions
lazy evaluation often yields faster code, because inlining
basically flattens the code into primitives.

However, sometimes the programmer expects eager evaluation
and sometime lazy.

Lazy is mandatory for most imperative control structures: 
if/then/else, match, loops, etc. Eager is mandatory when
some calculation depends on a variable: you can defer calculation
only up to the point the variable is modified.

OTOH, sometimes lazy is expensive, particularly when you cannot
inline, because then you have to pass a closure.

Some languages define application as eager (Ocaml) and some
lazy (Haskell) but Felix does both and neither :)

The basic idea is some things are eager, some lazy, but most
are 'up to the compiler'.

So actually, three significant factors seem to exist:
side effects or not, dependence on a variable or not,
and finally whether the function is strict.

> When I learned the concept of strictness it was in the context of pure
> functional programming. For me the definition was mostly there to
> distinguish non-strict functions, such as if(e,t,f) from other
> functions. 

My understanding is you can evaluate strict functions eagerly,
because the function is 'defined' to 'crash' if evaluation
of one of its arguments does. As you say, if(e,t,f) isn't
strict: e can be evaluated eagerly, but t and f must be
evaluated lazily.

But this is already somewhat confusing .. the 'function'
actually has one argument, a tuple of three components.
It's neither strict nor non-strict.. its strict in the
first projection, but not the second and third.

> Bottom encodes essentially two different things,
> non-termination or "domain error". The non-termination aspect is crucial
> for non-strict functions such as if, since the non-termination of 't' or
> 'f' may not imply that if() itself will not terminate. However, in real
> compiler design, the number of non-strict functions is very small and
> usually built-ins. 

A real compiler for what?  I think many HOF are non-strict,
when they're control structures -- such as if/then/else.

> However, this is of course not true if you implement
> lazy functional programming languages where basically everything is
> non-strict.

I suspect many functions are still strict .. giving you 
a choice of when to evaluate. However the default is lazy
evaluation (hence 'strictness analysis' to determine when
it is equivalent to evaluate more eagerly).

But in a procedural language .. well things seem more complex :)


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

Re: [Caml-list] strict?

[Alan Falloon]

skaller wrote:
> Some languages define application as eager (Ocaml) and some
> lazy (Haskell) but Felix does both and neither :)
>
> The basic idea is some things are eager, some lazy, but most
> are 'up to the compiler'.
>
> So actually, three significant factors seem to exist:
> side effects or not, dependence on a variable or not,
> and finally whether the function is strict.
>   
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

Re: [Caml-list] strict?

[skaller]

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

Re: [Caml-list] strict?

[skaller]

On Thu, 2006-08-03 at 09:08 +0200, Francis Dupont wrote:
>  In your previous mail you wrote:
> 
>    Clearly the Wikipedia definition of strict:
>    
>    	f(bottom) = bottom
>    
>    is rubbish when applied to a mathematical function like 'sin', 
>    since bottom isn't a valid argument, but it makes sense
>    for 'sin' in the programming language sense.
>    
> => as a student many years ago of the inventor of the "strictness" concept
> I don't understand your statement: 

well .. I'll simplify it then: "I'm confused" :)

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

Re: [Caml-list] strict?

[Francis Dupont]

 In your previous mail you wrote:

   Clearly the Wikipedia definition of strict:
   
   	f(bottom) = bottom
   
   is rubbish when applied to a mathematical function like 'sin', 
   since bottom isn't a valid argument, but it makes sense
   for 'sin' in the programming language sense.
   
=> as a student many years ago of the inventor of the "strictness" concept
I don't understand your statement: a strict function is simply a function
which uses its argument. In semantics this is caught by f(bottom) = bottom
where bottom is a semantics value (not a real one) so by definition always
a valid argument.

Regards

Francis.Dupont@fdupont.fr

PS: the inventor is Jean Vuillemin and of course the strictness concept
is central in the evaluation strategies.