Re: Tailcalls. Was Re: Manual timeslicing the VM.

[Glenn Maynard <glenn@...>]

On Fri, Aug 05, 2005 at 12:32:11PM -0500, Rici Lake wrote:
> >That makes some sort of sense for recursive tail calls, but if f tail
> >calls g, f is the real caller of g--if f was originally called by a,
> >I don't want debug calls telling me that g was called by a; it wasn't.
> >Since it doesn't know anymore, I'd much rather have it say "don't know"
> >than to give a wrong answer (like C stack traces do).
> 
> I guess it depends on how you define "recursive". A state machine
> implemented through tailcalls (see section 6.3 of Programming in Lua
> for a nice simple example) is technically recursive, but not
> self-recursive.

Here, I was referring to self-recursion: it may make sense, when debugging,
to want to know which function kicked off a tight recursion, but in the
state machine case it feels wrong and unintuitive for a debugging function
being asked "who called this function" to return the function that started
the state machine originally.

> // This module implements foo'ing a directory. The header
> // only exports the function counted_foo.
> 
> // The actual implementation of foo is in another file; we
> // don't expose it to API users, so we need to declare it here.
> int foo (struct s *context, const char *dir);
> 
> // Keep some statistics
> int counted_foo (struct s *context, const char *dir) {
>   if (dir[0] == '/')
>     ++context->absolute_dir_count;
>   else
>     ++context->relative_dir_count;
>   return foo(context, dir);
> }
> 
> The counted_foo stack frame is pure noise. foo is actually indirectly
> recursive -- it calls a sequence of handlers some of which recursively
> call counted_foo -- so the back traces look like this:

"counted_foo" isn't noise, if it's what's being called by users.  If I have:

void do_it()
{
    /* five lines of code */
    counted_foo(s, "/baz");
    /* five more lines of code */
}

my stack trace may look like:

 main
 do_it
 foo

I have to do a lot of careful prodding to figure out how the heck I got to
"foo", since do_it never called it.  I can't tell if it's missing stack
frames due to tail calls, if my stack is corrupt, or if it's just a stray
symbol on the backtrace (which happens with some backtracers which fall
back on heuristics, when frame pointers don't exist or aren't trusted).

-- 
Glenn Maynard