Tail recursion to while iteration in 2 easy steps
Jussi Piitulainen
jpiitula at ling.helsinki.fi
Tue Oct 8 05:49:29 EDT 2013
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.
More information about the Python-list
mailing list