[clean-list] Clean in the Real World

[Fergus Henderson]

On 15-Dec-2003, Marco Kesseler <m.wittebrood@mailbox.kun.nl> wrote:
> Fergus wrote
> >On 15-Dec-2003, Marco Kesseler <m.wittebrood@mailbox.kun.nl> wrote:
> >> 
> >> As long as it optimises at compile time, it is free to do whatever it 
> >> wants, except at a few locations that hold catch statements.
> >
> >That's not correct.  If you want to preserve the nice properties of
> >pure functional programming, then optimization would be inhibited in any
> >code which might be called from a catch statement.  Since it is common
> >practice to put an exception handler at the very top level, this would
> >typically mean the entire program.
> 
> a) I have to disagree. It would not be uncommon to have exception 
> handlers deeper down, provided that the language does not make it 
> almost impossible.

It's common to have exception handlers deeper down, but usually there
will also be a top-level handler to catch any unexpected exceptions.

> b) Most code does NOT get called by the handler. Or are you referring 
> to the guarded code?

Yes, I'm referring to the guarded code.

> >If you don't inhibit such optimizations, then you would end up in the
> >situation where applying simple and obvious transformations such as
> >replacing a variable with its definition might change the program's
> >behaviour.
> 
> Suppose I have:
> 
> Start
>     = program
>     catch DivideByZero = abort "divide by zero"
>     catch StackOverFlow = abort "stack overflow"
>     catch ...

In your example code above, you didn't give a precise syntax or semantics
for the new "catch" construct... 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

?

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.

> Yes, I agree that it depends on the optimisations which exception 
> will get thrown first.

Right.  And that in turn means that the value of "Start" (or "foo") may
differ depending on what optimizations are applied.  Which may depend
on seemingly unimportant details of the implementation of "program"
(or "bar").

Unless code which catches exceptions is restricted to a nondeterminism
monad or equivalent, referential transparency will be violated.
Programmers will no longer be able to safely apply equational reasoning
to transform the definition of "bar", because such transformations
might change the value of "foo".

> But I don't see why the "program" expression cannot be optimised.

If you're willing to violate referentially transparency,
you can certainly perform such optimizations.  But then you lose
most of the nice properties of pure functional programming, like
equational reasoning.

> >> And then, there is still the possibility to enforce catch statements 
> >> to always deliver the same constant expression on any exception.
> >
> >Not if you permit statements that might not halt.  Otherwise the compiler
> >in general still can't reorder code, such as the evaluation of x and y in
> >"x + y", because "catch(1/0 + loop)" will terminate whereas
> >"catch(loop + 1/0)" will loop.
> >
> >Automatic termination analysis is still not yet good enough to want to
> >rely on it -- after all, this is the classic halting problem!
> 
> Well, perhaps we are not thinking/talking about the same thing. I 
> meant to say that the _handler_ always delivers the same expression 
> for the same set of function arguments, independed of the actual 
> exception it caught (i.e. independent of optimisation).

I understood that.  But maybe you didn't understand my reply, which I
admittedly did not explain very clearly.  The problem is that as well
as exceptions, there is also nontermination, and the semantics for
"catch" needs to deal with them both.

> In that way, it becomes impossible to detect from the outside of the
> function (Start above) what exception was throw. This is trivially so,
> if the  handler does not get the exception value as an argument.

You can't detect what exception was thrown, but "catch" can still be
used to distinguish the order of evaluation, because you can detect the
difference between throwing an exception and going into an infinite loop.
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.

-- 
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.