Recursion to Iteration, Part 4: The Trampoline (2013)
blog.moertel.com
blog.moertel.com
The more general principal is that you can introduce small virtual machines to extend a language with features not present in the original one. In an extreme case, you can extend C with a virtual machine that implements all of Common Lisp. Much less extreme is an asynchronous event loop using generators. (A language isn't just its syntax.)
http://www.pythontutor.com/visualize.html#mode=display
Separate topic: Comment of the first part of the series:
>Alternative title: I wish Python had tail-call elimination.
I really like Python a lot and there are many features that could be added to Python, but on the other hand, Python is just nice as it is, as long as what you're trying to do fits into its capabilities. There's also the case of some of those potential features threatening to go against the Zen of Python (particularly "There should only be one way to do it" and "If the implementation is hard to explain, it's a bad idea.")
If you are going to require high-performance * , or things that collide with the Global Interpreter Lock, etc, then simply Python is not the best choice. I'd also liked Python to have Tail Call Elimination, along with many other features I would love Python to have, but for those I simply use Common Lisp, which does have them (plus a ton of other features), however it will not produce code as beginner-friendly as with Python.
* PyPy can only get you so far here.
It seems like "Zen of Python" is applied inconsistently, especially the "one way to do it" rule. Python is horrid about "one way to do it"--list comprehensions vs loops, decorator syntax vs `x = decorate(x)`, try/except/finally vs with, etc etc. In particular, if we are going to force a choice between iterative and recursive based on "one way to do it", then I would vote recursion + tco. Of course, this is a false dichotomy and we could have the best of both worlds.
> if you are going to require high-performance * , or things that collide with the Global Interpreter Lock, etc, then simply Python is not the best choice.
Unfortunately, people rarely realize their performance requirements until they're neck-deep in Python. Basically if you ever, ever, ever think you might need decent performance, there are performant languages that beat Python at its own friendliness/maintainability game (Go comes to mind).
Good. I think we would all be better off if we forgot about it entirely.
My own rules for "list/dict comprehension" versus "loops" versus "generator expressions" are the following:
* use a loop where you are interested only in the side-effects or where it will make the code easier to read
* use generator expressions where you don't really need to instantiate a list, for example when you are just iterating over the result and throwing it away.
* use list or dict comprehensions where you need to build and save a list/dict and the resulting code does not resemble a lisp program (where the choice does not make the program harder to read).
In the Lisp source file below, I provide a tlet operator whose syntax resembles labels, but which compiled to a tagbody in which the "functions" are just labels.
There is also deftail for tail calling among global functions, which is based on dynamic non-local returns and a dispatch mechanism.
http://www.kylheku.com/cgit/lisp-snippets/tree/tail-recursio...
I'm not sure exactly why people bring up performance when tail call elimination is mentioned. Maybe because sometimes it's called "tail call optimization"? Besides replacing a call with a jump, it's more of an "optimization" in the sense that it allows an optimizing compiler to see and optimize a loop. However, CPython is not an optimizing compiler, and it would barely be an optimization.
Rather, tail call elimination is a feature that allows for a very controlled goto statement, and even a computed goto. However, "continue" and "break" seem to work well enough for most cases. Perhaps the strongest objection to having TCO is that stack traces become more inscrutable.
Yes, you are correct, however i was mentioning TCO and performance as separate topics. This nonwithstanding, consider that TCO allows writing recursive functions without utilizing call stack space, and this might have some performance impact as well.
1. Add first node to inventory, set node.visit=false.
2. Query for 1st of any nodes with visit=false. (Order doesn't really matter in the end.)
3. If none found, stop.
4. If the found node has branches, add them to inventory with visit=false.
5. Process current node.
6. Mark current node with visit=true.
7. Go to 2.
The fact that almost everything is a PyObject and requires allocation?