functional programming

[Neel Krishnaswami]

Aahz Maruch <aahz at netcom.com> wrote:
> In article <000801bf7daa$80dde000$51a0143f at tim>,
> Tim Peters <tim_one at email.msn.com> wrote:
> >
> >2.5. One great thing that shakes bugs out of Python code is that it
> >   raises an exception whenever it has a reasonable doubt about the
> >   code you told it execute, and a key part of making that *usable*
> >   is Python's never-lies complete stack trace.  If A calls B tails
> >   calls C tail calls D blows up, I damn sure don't want a traceback
> >   claiming that A called D directly.  I want to get a traceback object
> >   with the full chain intact, and I want to crawl up that chain to
> >   examine the state of the locals in B and C at the time they made
> >   their calls.  Optimize intermediate frames away, and tracebacks
> >   would become much harder to decipher.
> 
> Say!  Couldn't you use continuations to store those intermediate frames
> in case you ever throw an exception?

Only if you stop doing tail-recursion elimination in the first place,
since the whole point of tail-recursion elimination is to never
allocate those frames in the first place. :)

Consider the following tail-recursive Python program:

def fact_tr(n, acc):
    if n == 0:
        return acc
    else:
        return fact_tailrec(n - 1, n * acc)

fact_tr(4,1)  # Compute 4 factorial

With standard Python semantics, the call chain would evaluate like
this (using a pseudo-Python where multiple 'return' statements
represent the frames on the call stack):

fact_tr(4,1) => return fact_tr(3, 4) 
             => return (return fact_tr(2, 12)) 
             => return (return (return fact_tr(1, 24)))
             => return (return (return (return fact_tr(0, 24))))
             => return (return (return (return 24)))
             => return (return (return 24))
             => return (return 24)
             => return 24
             => 24

All tail-recursion elimination means is that you observe that all
those nested 'return's are unneccesary, since all you are doing is
immediately passing the result back to the caller without doing any
additional computation on the call result. Thus you don't have to
allocate intermediate stack frames, since they will be unused. So you
can evaluate it like so:

fact_tr(4,1) => fact_tr(3, 4)
	     => fact_tr(2, 12)
             => fact_tr(1, 24)
             => fact_tr(0, 24)
             => 24

Now, suppose that for some reason our program threw an exception part
way through a call to fact_tr(4,1), say when it tried to evaluate
fact_tr(1,24).

Since none of the stack frames were ever allocated, in the debugger it
would look like the program had immediately called fact_tr(1,24)
rather than fact_tr(4,1). In this particular example, it's not too
tricky, but when you have complex mutually recursive procedures (say
in a recursive descent parser), it can be a real pain to debug.

In fact, it's for precisely this reason that some Common Lisp
implementations have an option to turn off tail-recursion elimination
when they go into debug mode. Likewise, I expect that if Python ever
supports tail-recursion elimination, it will only be turned on with
the -O switch.

Since "first-class continuation" is really just Scheme talk for saying
that the call tree is a first-class language object like numbers and
functions, the issues are the same for call/cc as they are for the
debugger.


Neel