Tail calls and exceptions - comp.lang.functional

Message from discussion Tail calls and exceptions

Matthias Blume

View profile

More options Dec 14 2005, 10:17 am

Newsgroups: comp.lang.functional

From: Matthias Blume <f...@my.address.elsewhere>

Date: Wed, 14 Dec 2005 09:17:39 -0600

Local: Wed, Dec 14 2005 10:17 am

Subject: Re: Tail calls and exceptions

  Reply to author
  |
  Forward
  | Print
  | View thread
  | Show original
  | Report this message
  | Find messages by this author
  

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

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

Reply to author Forward