[clean-list] Clean in the Real World

[Fergus Henderson]

On 15-Dec-2003, Marco Kesseler <m.wittebrood@mailbox.kun.nl> wrote:
> Fergus wrote:
> >am I right to presume that you mean
> >that this construct could be used in contexts where there is no World
> >passing or nondeterminism monad?
...
> >For example, could it be used in
> >
> >	foo :: Int
> >	foo
> >	    = bar
> >	    catch DivideByZero = baz
> 
> Yes.

> >If so, then either (a) I won't be able to safely apply equational reasoning
> >to my programs any more, or (b) compiler optimizations will be inhibited
> >for any code which might be guarded by a catch.
> 
> You will:
> (a) be able to apply equational reasoning within your program, in the 
> sense that if an exception occurs within foo, it will always deliver 
> the same result (baz), because it will always throw the same 
> exception, by virtue of the compiler generating a fixed evaluation 
> order for bar.

Suppose the expression "a + b" occurs in the definition of "bar".
I can't safely apply equational reasoning to replace this with "b + a",
because that might change the value returned from foo.

Or, if we consider a slightly different example,
where foo takes a parameter x,

	foo :: Int -> Int
	foo x
	    = bar x
	    catch DivideByZero = baz x

you may have "foo (a + b)" being different than "foo (b + a)".

> (b) have compiler optimisations both in bar and baz, as it does not 
> matter which exception gets thrown in bar, as long as it is the same 
> one each time within a single program.
> 
> The one thing that is not possible, in terms of optimisation, is to 
> simply replace occurences of foo by bar. You cannot, because foo does 
> not just equal bar, and there is no notation to attach the handler to 
> a loose bar. And you should not because then the compiler would have 
> to ensure that each of these occurences of bar employs the same 
> evaluation order.

That's not the only thing which is not possible, in general.
You also can't easily specialize occurrences of foo.
That's not important for that original example,
but consider another slight variation:

	foo :: Int -> Int -> Int
	foo f
	    = bar f
	    catch DivideByZero = baz f

If "bar" calls "f" often, and there is a call to "foo (\ x y -> x + y)",
then it may be very important for performance to specialize both
"foo" and "bar", so that the calls to f can be inlined to a single
cheap add instruction rather than the expensive sequence of instructions
needed for a call to an unknown higher-order function term.

Well, I suppose the compiler could do the specialization, provided that it
was done _after_ any optimizations that change the order of evaluation.
But normally the compiler should do such specializations first, and then
apply all the other optimizations, such as inlining, constant propagation,
etc., so that the specialized code can be simplified.

> I am not willing to violate referential transparency (just yet). If I 
> were, this discussion would not have become this long. Speaking of 
> referential transparency: what is so referentially transparent about 
> the Monadic approach:
> 
> getException x >>= (\v1 ->
> getException x >>= (\v2 ->
> return (v1 == v2)
>
> Why question this? For the simple fact that "getException x" does not 
> deliver the same value each time.

"getException x" always evaluates to the same value, an IO action.

When you talk about "delivering" a value, you mean applying this action
to some particular world state to get a concrete value rather than
an IO action.  If you apply the action to two different states then
naturally you may get different values delivered.  That is the case in
your example above.

> >If we have
> >
> >	foo :: Int
> >	foo
> >	    = bar
> >	    catch _ = baz
> >
> >	bar = (1/0) + loop
> >
> >and the compiler evaluates the addition left-to-right, then "bar"
> >will throw a DivideByZero exception, and so "foo" will return "baz",
> >but if the compiler evaluates the addition right-to-left, then neither
> >"foo" nor "bar" will terminate.
> 
> Well, luckily our programs only have to be referentially transparent 
> if they terminate.
> 
> In practice, this is a non-issue.

If the compiler transforms a terminating program into a non-terminating
one, that is usually considered to be a rather serious issue :)

-- 
Fergus Henderson <fjh@cs.mu.oz.au>  |  "I have always known that the pursuit
The University of Melbourne         |  of excellence is a lethal habit"
WWW: <http://www.cs.mu.oz.au/~fjh>  |     -- the last words of T. S. Garp.