Tail recursion to while iteration in 2 easy steps

[Jussi Piitulainen]

Alain Ketterlin writes:
> Antoon Pardon writes:
> 
> > Op 07-10-13 19:15, Alain Ketterlin schreef:
> 
> [...]
> >> That's fine. My point was: you can't at the same time have full
> >> dynamicity *and* procedural optimizations (like tail call opt).
> >> Everybody should be clear about the trade-off.
> >
> > Your wrong. Full dynamics is not in contradiction with tail call
> > optimisation. Scheme has already done it for years. You can rebind
> > names to other functions in scheme and scheme still has working
> > tail call optimisatiosn.
> 
> See
> http://en.wikipedia.org/wiki/Scheme_%28programming_language%29#Lexical_scope
> 
> (first sentence, about variable bindings).

# ... Scheme is lexically scoped: all possible variable bindings in a
# program unit can be analyzed by reading the text of the program unit
# without consideration of the contexts in which it may be called ...

The actual procedure to be called is still not known at compile time,
in general. It can be a parameter. It needn't even be the value of any
explicit variable (needn't be "bound to a name").

def call(f, a):
   ...
   return f(a)  # tail call
   ...

def wev(...):
   ...
   return (fs if c(k) else gs)[k](a)  # tail call
   ...

In the Scheme reports, a variable is said to be bound to a location,
which is lexically apparent to the language processor; the value is
stored in that location, and assignment to the variable means storing
a new value in that location. It works like Python or Java; Python
just has a different way of talking about how it works - binding names
directly to values in a namespace, and rebinding to different values.

However, Scheme processors know that the local variables are not
accessible from anywhere else but the local code, so there are more
opportunities for compile-time analysis. They can optimize many of
those locations away, for example.