Re: [Caml-list] Re: Help me find this pdf

[Jon Harrop <jon@ffconsultancy.com>]

On Friday 19 October 2007 22:43:42 Andreas Rossberg wrote:
> Wow, that made my FUD sensors go wild.

This whole thread made my FUD sensors go wild. :-)

> 1. Purity and evaluation regime are separate issues. You can very
> well have a pure language that is eager.

IIRC, you then need the option of laziness to be able to implement all 
programs with the same asymptotic complexity as impure/eager or pure/lazy.

> 2. However, in a pure language the details of evaluation order are
> largely immaterial to its semantics, which obviously is an advantage.

I'm not sure that unknown evaluation order is an "obvious" advantage in 
general. For example, when evaluating "f && g" where f is O(1) and g is O(n!) 
you might want to know that "f" gets evaluated first.

> 3. Lazy evaluation by itself is as precise an evaluation scheme as
> eager evaluation. There is no inherent vagueness.

Does a thunk preventing a large data structure from being deallocated count 
as "inherent vagueness"?

> 4. In fact, the semantics of OCaml arguably is more vague than that
> of Haskell, because evaluation order is underspecified (and can vary
> between compilers) even where it matters semantically. Haskell only
> leaves it unspecified where it is not semantically observable.

IIRC, ocamlc and ocamlopt really do evaluate in different orders sometimes.

> 5. The problem with Haskell and laziness on the other hand is not
> semantic bugs, but the fact that it can make space complexity hard to
> predict sometimes.

And time performance hard or impossible to achieve.

> 6. Nevertheless, evaluation is fully deterministic, thus it certainly
> cannot cause Heisenbugs, neither semantically nor performance-wise.

Perhaps I've missed something but surely evaluation order can alter asymptotic 
complexity? If so, moving from one compiler to another can change the 
asymptotic complexity of your program?

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/products/?e