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

[Rici Lake <lua@...>]

On 5-Aug-05, at 11:47 AM, Glenn Maynard 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.

> I hate when C backtraces are missing frames; it's extremely confusing
> when there are several calls missing because of these optimizations.
> Losing debuggability as a result of optimizations is usually an 
> acceptable
> tradeoff, of course, but it's definitely a trade, and I'm surprised 
> that
> some people actually *like* losing debug information in backtraces.

Life's surprising, isn't it? It is particularly surprising when we
learn that not everyone shares our prejudices. :)

Without going into details about the particular case I was talking 
about,
consider the following unrepresentative and simplified example:

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

  a_handler(...)
  foo(...)
  b_handler_subroutine(...)
  b_handler(...)
  foo(...)
  x_handler(...)
  foo(...)
  ...

If counted_foo were in the same file as a handler, it would get
eliminated by inlining, in all probability. But it's not -- each
handler is in its own file. Of course, some die-hard traditionalists
might implement counted_foo as a macro.

The int return value is a status code. What happens if we now want
to collect statistics correlating the return value of foo with the
argument type? The obvious solution loses the tailcall optimisation,
and adds noise to the back trace.

The real example was not actually much like that. It was not
collecting statistics; rather, it was checking for a rare
condition and correcting for it. The desired change was to
check for a rare post-condition and correct for it, but as in
the above example, that lost the tailcall optimisation.