Recursively traverse linked list -- help!

[Terry Reedy]

"Paul Rubin" <phr-n2002a at nightsong.com> wrote in message
news:7xadu3wwr5.fsf at ruckus.brouhaha.com...
> "Jason Orendorff" <jason at jorendorff.com> writes:
> > > > def f(val):
> > > >   global f
> > > >   f = val and f1 or f2
> > > >   return f(val)
> > >
> > > This is not tail recursion.  The "global f" declaration shadows
> > > the "f" that names the function.

I picked about the simplest example I could that would illustrate the
point that a tail call that looks like tail recursion, when viewed by
itself, is not necessary so in Python due to dynamic name-object
binding.  The rebinding could occur in any function on the call chain
under f.  It could also take place after some calls that really are
recursive.

> > That's not true.  The f that names the function is global anyway.
> > It's the assignment that causes the problem.
>
> Oh yes, you're correct.  However, the tail call should still be
> optimized, compiled as an indirect jump to f.

I can accept 'maybe could' (see below) but 'should'?  What sense of
shouldness are you using?  "It would be nice if"?  The passive 'be
optimized' glides over the 'who' that 'should' do the work and
maintain it for the next decade.  Automated object code optimization
seems to be a tricky process.  Other suggestions have been made, and
some volunteer work done, but the last report I have read from Tim
Peters is that the CPython interpreter sticks to straightforward
tranlation to PyCode.

As for 'maybe could': by 'indirect', I presume you mean after looking
up the name to find its current binding.  If so, then it really does
not matter what the name is that is looked up.  So, are you suggesting

A. general tail call optimization?

  If so, 'jump to' is problematic, since there is no frame object to
jump to, the avoidance of creating such being part of the purpose of
the optimization.  If the call is not recursive, I could imagine
replacing the contents of the current frame. But I do not know how
feasible this is with the current implementation.

or B. just tail recursive call optimization (where the call is
recursive)?

  If so, there is still the two tasks of 1) determining whether the
target of the jump is the same as the currently executing code body,
and 2) doing the jump properly.

Terry J. Reedy