RE: [Caml-list] strict?

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

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