Tail calls and exceptions
Dave Benjamin
be tail-call optimized. Is this the case in all functional programming
languages that support exceptions?
I am starting to wonder if recursion and exceptions are fundamentally at
odds with each other. For example, a program might be written with
infinite recursion (an event loop, for instance) -- in the event of an
exception, a full traceback would obviously be impractical.
I notice that OCaml does not give tracebacks at all (or is there some
way to enable this?). It seems that this would make large-scale program
maintenance and debugging tedious. In a functional environment, is
exception use typically kept to a minimum?
Variants could be used as a replacement for exceptions to deal with
out-of-band data, I suppose. It seems like this would have a similar
effect as "checked exceptions" in Java: thorough, but tedious. With
variants, there is no way to let errors invisibly propogate through
function calls -- some see this as a good thing, but especially with
exploratory programming, it can be a nuisance.
Still, another benefit of variants is that functions written in CPS can
pass errors the same way; I notice that in event-driven / asynchronous
programming, I once again have to find other ways of sending out-of-band
data besides exceptions, since exceptions bubble up to the event loop,
not the function that can deal with the error.
What's the best approach here? Am I stubborn to resist letting go of
stack traces for ease in debugging? Can TCO, exceptions, and useful
error reporting co-exist peacefully, and is there a language that
demonstrates this? Or is exception-handling the wrong solution entirely,
despite the conveniences it allows?
Curious,
Dave
Torben Ægidius Mogensen
> In OCaml, it seems that a function that uses exception handling cannot
> be tail-call optimized. Is this the case in all functional programming
> languages that support exceptions?
Unless they radically change the exception model, yes. In (for
example)
f(...) handle E => ...
you can seea the exception handler as something that might be executed
after returning from the call to f, so f is not in tail position even
if the whole expression above is. In general, if (expr handle match)
is in tail position, expr is not, but match is, so you can tail-call
optimize calls in the handler.
> I am starting to wonder if recursion and exceptions are fundamentally
> at odds with each other. For example, a program might be written with
> infinite recursion (an event loop, for instance) -- in the event of an
> exception, a full traceback would obviously be impractical.
If you have exception handlers on all calls, you can build a full
trace-back by letting each handler raise a new exception that is being
handled by the next handler. But you don't need to put a handler on
every call -- in the case of a tail-recursive function, you can put a
handler on the first call to the function but not on the (tail)
recursive calls.
> I notice that OCaml does not give tracebacks at all (or is there some
> way to enable this?). It seems that this would make large-scale
> program maintenance and debugging tedious. In a functional
> environment, is exception use typically kept to a minimum?
I expect exceptions are used more in ML-like languages than in
imperative languages. Imperative languages tend to use exceptions
only for error-handling and reporting, but ML-like languages often use
them for control, such as backtracking.
> Variants could be used as a replacement for exceptions to deal with
> out-of-band data, I suppose.
Indeed, and that is the typical way it is done in Haskell or other
non-struct functional languages. Many SML libary functions use them
too, typically in the form of option types (SOME value or NONE).
> It seems like this would have a similar
> effect as "checked exceptions" in Java: thorough, but tedious. With
> variants, there is no way to let errors invisibly propogate through
> function calls -- some see this as a good thing, but especially with
> exploratory programming, it can be a nuisance.
I tend to use option types if I want the undefined case to be handled
immediately after return of the function and exceptions if it should
be handled further out, thereby aborting an ongoing computation.
> Still, another benefit of variants is that functions written in CPS
> can pass errors the same way; I notice that in event-driven /
> asynchronous programming, I once again have to find other ways of
> sending out-of-band data besides exceptions, since exceptions bubble
> up to the event loop, not the function that can deal with the error.
When you CPS transform exceptions, you get non-tail calls in the
CPS-transformed program. You can CPS-transform once more to get rid
of these (or CPS transform with two continuations at the same time:
one for normal return and one for exceptions).
> What's the best approach here? Am I stubborn to resist letting go of
> stack traces for ease in debugging? Can TCO, exceptions, and useful
> error reporting co-exist peacefully, and is there a language that
> demonstrates this? Or is exception-handling the wrong solution
> entirely, despite the conveniences it allows?
Stack traces and tail-call optimisation can't coexist (you can get
traces of non-tail calls, though). But that isn't really different
from imperative languages not doing back traces of loops.
Torben
Marcin 'Qrczak' Kowalczyk
> In OCaml, it seems that a function that uses exception handling
> cannot be tail-call optimized.
It's not true. When a call is within the 'try' part of a 'try'
construct, then it's not a tail call. But if it's outside 'try',
it might be a tail call.
> Variants could be used as a replacement for exceptions to deal with
> out-of-band data, I suppose.
It doesn't help in making calls tail calls. If a function returning
a variant is called in a tail position, then a function possibly
throwing an exception could be called in a tail position too.
> Still, another benefit of variants is that functions written in CPS
> can pass errors the same way;
A natural way of passing errors in CPS is to let each function take
two contiunuations: a separate for success and separate for failure.
> Can TCO, exceptions, and useful error reporting co-exist peacefully,
Depends what do you mean by "coexist" :-)
--
__("< Marcin Kowalczyk
\__/ qrc...@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Matthias Blume
> When you CPS transform exceptions, you get non-tail calls in the
> CPS-transformed program. You can CPS-transform once more to get rid
> of these (or CPS transform with two continuations at the same time:
> one for normal return and one for exceptions).
The truth of this statement depends on the kind of CPS transform that
you are using. It is fairly easy to build a CPS converter that
performs those two steps in one pass, thus directly constructing a
program without non-tail calls from a program with exceptions and
handlers.
>> What's the best approach here? Am I stubborn to resist letting go of
>> stack traces for ease in debugging? Can TCO, exceptions, and useful
>> error reporting co-exist peacefully, and is there a language that
>> demonstrates this? Or is exception-handling the wrong solution
>> entirely, despite the conveniences it allows?
>
> Stack traces and tail-call optimisation can't coexist (you can get
> traces of non-tail calls, though).
This is *not* true! SML/NJ, for example, has a mode in which programs
are instrumented at compile-time so they give traces that include all
tail-calls -- except those that have been found (dynamically) to form
a loop. The asymptotic space complexity of the annotated program is
the same as that of the orginial un-instrumented program (although
there is a hidden constant factor that depends on the particular
program).
In the trace, non-tail calls are marked CALL, tail-calls are marked
GOTO, and clusters of functions that form strongly connected
components of GOTOs are listed as single nodes. This way one can
easily follow the call chain of the program at the point of an
uncaught exception. In fact, the trace will list every single source
function involved.
> But that isn't really different from imperative languages not doing
> back traces of loops.
Indeed. What's more, most implementations of imperative languages
will not be able to give you a trace of your GOTOs even when those
GOTOs do not form a loop.
Matthias
Torben Ægidius Mogensen
> tor...@app-3.diku.dk (Torben Ægidius Mogensen) writes:
>
> > When you CPS transform exceptions, you get non-tail calls in the
> > CPS-transformed program. You can CPS-transform once more to get rid
> > of these (or CPS transform with two continuations at the same time:
> > one for normal return and one for exceptions).
>
> The truth of this statement depends on the kind of CPS transform that
> you are using. It is fairly easy to build a CPS converter that
> performs those two steps in one pass, thus directly constructing a
> program without non-tail calls from a program with exceptions and
> handlers.
Which is waht I hinted at in the parenthesis.
> >> What's the best approach here? Am I stubborn to resist letting go of
> >> stack traces for ease in debugging? Can TCO, exceptions, and useful
> >> error reporting co-exist peacefully, and is there a language that
> >> demonstrates this? Or is exception-handling the wrong solution
> >> entirely, despite the conveniences it allows?
> >
> > Stack traces and tail-call optimisation can't coexist (you can get
> > traces of non-tail calls, though).
>
> This is *not* true! SML/NJ, for example, has a mode in which programs
> are instrumented at compile-time so they give traces that include all
> tail-calls -- except those that have been found (dynamically) to form
> a loop. The asymptotic space complexity of the annotated program is
> the same as that of the orginial un-instrumented program (although
> there is a hidden constant factor that depends on the particular
> program).
>
> In the trace, non-tail calls are marked CALL, tail-calls are marked
> GOTO, and clusters of functions that form strongly connected
> components of GOTOs are listed as single nodes. This way one can
> easily follow the call chain of the program at the point of an
> uncaught exception. In fact, the trace will list every single source
> function involved.
This is not a complete stack trace, so we kind of agree.
> > But that isn't really different from imperative languages not doing
> > back traces of loops.
>
> Indeed. What's more, most implementations of imperative languages
> will not be able to give you a trace of your GOTOs even when those
> GOTOs do not form a loop.
Very true. And they generate no back-trace of assignments either,
which are equally important when debugging imperative programs. In
other words: In a functional programming language, a backtrace will
give you a more complete picture of what the program did before
arriving at the checkpoint than it will in an imperative language.
Torben
Alain Frisch
> I notice that OCaml does not give tracebacks at all (or is there some
> way to enable this?).
In bytecode, you'll get a trace for uncaught exceptions if you compile
with the -g option and run with the environment variable
OCAMLRUNPARAM set to "b=1".
-- Alain Frisch
Ben Rudiak-Gould
>A natural way of passing errors in CPS is to let each function take
>two contiunuations: a separate for success and separate for failure.
But this doesn't solve the problem of O(n) space consumption in an iterative
calculation where the "tail" call is inside a try block. It just moves the
growth from the stack to the error continuation. I don't think this problem
can be solved. A call inside a try block just isn't a tail call, no matter
how you look at it.
-- Ben
Henning Makholm
> But this doesn't solve the problem of O(n) space consumption in an
> iterative calculation where the "tail" call is inside a try block. It
> just moves the growth from the stack to the error continuation.
If the exception handler does not re-throw the exception, then the
previous exception continuation becomes garbage once the try+tail call
happens. It can then be collected.
If the handler throws a _different_ exception that is not caught by
any handlers in the chain, then the old handlers can also become
garbage if one uses different error continuations for different
exceptions is used. (I don't _think_ this usually happens in
implementations, but it could be done in theory - say, by passing
arround a search tree of error continuations for different exceptions
rather than a single continuation).
Of course, if the stack of exception handlers _expect_ to daisy-chain,
then all of them need to be stored.
--
Henning Makholm "Logic is a system for talking about
propositions that can be true or false, or at least enjoy
properties that are generalized versions of truth and falsehood."
Vesa Karvonen
> In OCaml, it seems that a function that uses exception handling cannot
> be tail-call optimized. Is this the case in all functional programming
> languages that support exceptions?
> I am starting to wonder if recursion and exceptions are fundamentally at
> odds with each other. For example, a program might be written with
> infinite recursion (an event loop, for instance) -- in the event of an
> exception, a full traceback would obviously be impractical.
[...]
Browsing through other messages in this thread, I didn't notice anyone
mentioning Exceptional Syntax:
http://research.microsoft.com/~akenn/sml/ExceptionalSyntax.pdf
-Vesa Karvonen
Dave Benjamin
Is this an equivalent construct?
http://martin.jambon.free.fr/extend-ocaml-syntax.html#lettry
It seems like this would help somewhat, since it enables you to use
let-bindings while keeping the tail-call out of the try-block.
Thanks!
Dave
Dave Benjamin
Thank you! I've been trying to figure this one out for awhile. I missed
the part about the "-g" option. I also got backtraces to work in the
debugger. Whenever I tried to issue a "backtrace" command after an
exception, I got nothing. After studying the docs a bit, I realized that
you have to step backward first.
I assume that this backtrace feature in OCaml is not quite as
sophisticated as what Matthias described regarding SML -- is that correct?
Dave
Dave Benjamin
> Dave Benjamin <dave.b...@gmail.com> writes:
>
>> In OCaml, it seems that a function that uses exception handling
>> cannot be tail-call optimized.
>
> It's not true. When a call is within the 'try' part of a 'try'
> construct, then it's not a tail call. But if it's outside 'try',
> it might be a tail call.
Yes, sorry for my sloppy wording. I have a much clearer picture of the
issue now. The trick, it seems, is to get all the exception handling out
of the way before making the tail call.
>> Variants could be used as a replacement for exceptions to deal with
>> out-of-band data, I suppose.
>
> It doesn't help in making calls tail calls. If a function returning
> a variant is called in a tail position, then a function possibly
> throwing an exception could be called in a tail position too.
Oh, I suppose that's true. In either case, you have to examine the
result of the call if you intend to act on errors. I don't know why I
thought this would be any better.
>> Still, another benefit of variants is that functions written in CPS
>> can pass errors the same way;
>
> A natural way of passing errors in CPS is to let each function take
> two contiunuations: a separate for success and separate for failure.
Indeed, and that does seem a bit more elegant.
>> Can TCO, exceptions, and useful error reporting co-exist peacefully,
>
> Depends what do you mean by "coexist" :-)
=)
Thanks,
Dave
Dave Benjamin
> SML/NJ, for example, has a mode in which programs are instrumented at
> compile-time so they give traces that include all tail-calls --
> except those that have been found (dynamically) to form a loop. The
> asymptotic space complexity of the annotated program is the same as
> that of the orginial un-instrumented program (although there is a
> hidden constant factor that depends on the particular program).
How do I enable this mode?
Thanks,
Dave
Vesa Karvonen
> Vesa Karvonen wrote:
> > Dave Benjamin <dave.b...@gmail.com> wrote:
> >> I am starting to wonder if recursion and exceptions are fundamentally at
> >> odds with each other. For example, a program might be written with
> >> infinite recursion (an event loop, for instance) -- in the event of an
> >> exception, a full traceback would obviously be impractical.
> > http://research.microsoft.com/~akenn/sml/ExceptionalSyntax.pdf
> Is this an equivalent construct?
> http://martin.jambon.free.fr/extend-ocaml-syntax.html#lettry
Looks like it.
> It seems like this would help somewhat, since it enables you to use
> let-bindings while keeping the tail-call out of the try-block.
Yes. Just recently I implemented the try-in-unless construct in a
Scheme implementation and used it to write a tail recursive and error
handling REPL. Previously I've found the try-in-unless construct
quite useful in my SML programming. For instance, I use it in my
simple SML unit testing framework, which needs to be careful to handle
exceptions correctly. (I actually discovered the technique
independently while implementing an early version of my unit testing
framework. Later I read the Exceptional Syntax paper and while adding
an implementation of the try-in-unless construct to my library I
noticed that I was already using an equivalent technique.)
-Vesa Karvonen
Alain Frisch
> I assume that this backtrace feature in OCaml is not quite as
> sophisticated as what Matthias described regarding SML -- is that correct?
Yes, I think this is correct.
-- Alain