I gather than the author is being hyperbolic in order to emphasize his point ("is easier to reason about correctness with recursion"). But the reason recursion doesn't "suck" in python (an other languages without TCE), even with a small call stack, is that usually it is used to tackle problems with a divide-and-conquer strategy. Even if you are handling a massive amount of items, if your recursive calls splits them to handle in two or more parts until there's no more to handle, then it is very hard to deplete the call stack:
log2 1_000_000_000_000_000 => 49.82892142331043
"Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used." [1]
BTW, I sympathize with the author's thesis. I was trying to remember algorithms that are easier to reason about in their iterative form... but I can't remember any. Conversely, compare recursive vs iterative DFS [2].
This article really got me in the mood to play around with Racket again.
Incidentally, I find it hard to square with Guido's belief that recursion isn't the basis of all programming. Sure, Python has some powerful iterators, but my CS professors made it clear that iteration is basically just a special case of recursion.
It might very well be the right decision for Python to prefer iteration, but to deny the role of recursion in computer science altogether seems misguided.
The two of them are exactly the same thing, but in recursion you have an implicit stack that maintains the state of each iteration. In iteration, the stack is either explicit or else condensed down into a few state variables (eg. if you're just keeping a sum, you don't need to store all the intermediate partial sums). Given that Python's philosophy is "explicit is better than implicit", it doesn't surprise me that he prefers iteration to recursion.
His opposition to recursion is well founded on the "principle of least surprise" that also underlies Python. Consider, e.g.
def len1(list, acc=0):
if not list: return acc
else: return len1(list[1:],acc+1)
def len2(list, acc=0):
if not list: return acc
else: return len2(list[1:],acc+1) + 0
First one is using only tail calls, and with proper TRE will run on any sized list. The second one will blow up the stack, despite being equivalent in almost every sense, especially in those senses (of "ease of proof") touted as the main reason to use tail recursion in the first place.
And while this toy examples is easy to reason about, real world examples require more experience to understand - and Python was always intended at non CS people (and is hugely successful in that mission).
Personally, I think the whole discussion is misguided. TRE should be explicit, not some kind of implicit optimization - that is, no TRE/TCO unless you explicity use e.g. a "chain" return keyword:
def len3(list, acc=0):
if not list: return acc
else: chain len1(list[1:],acc+1)
This way, a compiler could warn you about a syntax error should you rely on TRE and it is impossible or not available; Same thing could (and should) be done in scheme/lisp etc; It's easy to shoot yourself in the foot with macros and tailcalls in scheme.
"chain" might not be the right keyword for this, but I haven't found a better one ("tail-return", "return-only", "continue-with" don't seem any better"; maybe reuse "pass"? e.g. "return pass len1(..)" or "pass return len1(...)"
Actually, if you have a compiler with both TRE and constant folding, len2 will run on any sized list, if the optimizer runs constant folding before TRE or interleaves them. Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details.
However, I'll point out that this problem occurs in many situations already. In GC languages, a single allocation can trigger a GC that will lock up the CPU for 50-100ms; this is a particular problem with Javascript animations. In non-GC languages (like Python, Objective-C, or C++), you can get release cascades where the destruction of one object causes the reference counts on many others to go to zero, which causes the same problem. A single blocking call will make your server sit idly. Using a library function with O(N) behavior (like, say, string concatenation in many languages) in a loop will make your algorithm accidentally quadratic.
Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole. I've got some sympathy for the "languages shouldn't have dangerous gotchas" viewpoint, but I think that most of the time it ultimately results in premature micro-optimizations.
> Which I guess is your point, that your program's behavior becomes unreasonably dependent on implementation details.
Exactly.
> Practically speaking, the way we deal with these performance gotchas is to instrument the code heavily, profile, and measure the working system as a whole.
Yes, but that's the wrong way to deal with it. Especially with today's giant memories, you might run testing on a 512GB machine with a billion element list, not realize there's no TRE and it will fail on a machine with "only" 64GB of memory that is perfectly capable of running the same computation if TRE/TCO was done (but wasn't).
I want simple-to-remember-and-use semantics, and implicitly relying on tail recursion semantics does not provide it. O() guarantees are enough (and should be properly documented) - I don't need deterministic time or space guarantees beyond order-of-magnitude precision.
If you need deterministic timing in the 100ms range, most programming languages are not for you. If you need them within 10ms, most operating systems aren't. And if you need them within 100us, most CPUs aren't.
Summing up my 23 years of Python experience, noticeable pauses due to release cascades are extremely uncommon (unlike Javascript / Java pauses) - unlike Java/Javascript, with the exception of free() and a few minor loops, everything that runs is of _your_ making, which makes it easier to reason about and control.
And back to the subject:
My "chain" (or whatever) suggestion above, which I (and others) have made numerous times is basically a static-vs-dynamic typing assertion about how a subroutine uses the call stack at that point: "need it later", "don't need it later". Even for a dynamic language like Python, it makes sense to make this static because it cannot change with argument types. The incoming call stack can either be dropped at a location, or not, independent of inputs. I am surprised it is often countered (as you did here) with "yes, but we can test it so it's not a big deal". It's not a big deal, but it is also comes at basically no cost, AND makes a requirement self-describing and easily verifiable by a static compiler.
return f(a, b, c) # tailcall on f
return f(g(b)) # tailcall on f
return f(a, b, c) + 0 # tail call on +
The last function to be called before a return is tailcall. That's it. Nothing more. It doesn't matter that the return "expression" can be more complex, only the last call is concerned. It's a simple rule.
Now, regarding your concern for the static analysis of stack allocation: This is not a feature you have for any other aspect of the language... you have no way of specifying your expected memory consumption. But you do have your experience, you know the traps, you have learned the patterns to look for. Sure, the annotation could be used by a static linter, but builtin static analysis is not a feature in Python. Why should tailcalls be a syntaxic exception?
(Note: tail recursion is a special case of tail calls! The annotation you are thinking about would be more interesting as a function annotation, as you really don't want to track each of your recursive returns to state your global expectation.)
What you are asking for is common for new language features: You want a red flag, something that highlight the semantic prominently, so that you don't forget and are forced to think about something you aren't used to. Please have a look at your python code: how many returns end with a call to a function? Are you going to decorate each of them with "tailreturn"? It's really a free optimization, your program will run faster and consume less memory once it is there.
(Is Python even specifying that its implementation should use a stack?)
In the presence of try (also with, and perhaps a few others I can't think of right now) even the examples you gave cannot be TCEd.
Personally, I consider broken a language in which enclosing a construct with "try: .... finally: pass" to switch between constant memory and endless memory requirements.
That is already true for scheme in a way. Guido's refusal to break python in this sense is wholly supported by me, even if that's not his reason to refuse.
And "return from" suggested by another poster is the perfect pythonic syntax for such a thing.
And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here.
What's so invisible about your examples? I agree that an optimizing interpreter makes the situation harder to analyse, because we can't remember every simplification it handles. Without it, the tailcalls are very explicit.
Previously, you argued that Python semantics makes it very clear that all costs are visible. This seems to be against any rewrite rule, as the visible cost ("or False", "+ 0", "finally: pass") suddenly disappear. You are using your own rebuttal as an argument to make tailcalls look harder to analyse! They are not.
> And I definitely thing it is a property of the specific call site, NOT the entire function, whether it should be checked for tailness. Decorators are the wrong solution here.
As a caller of a function, the property you care about is "does it consumes a fixed amount of stack?". As the writer of this function, that's the thing that matters in the end: Sure, that means checking each tail calls, but you really want the global guarantee that you didn't forgot one. The local explicit annotation becomes redundant.
> But tailcalls already have a syntax:
>
> return f(a, b, c) # tailcall on f
However, this tail call cannot be eliminated in the context of a try: or with: scope. Ergo, it is NOT tail call syntax. Using it does not guarantee that the tail call can be eliminated:
def write_list_to_file(file, list):
"Looks weird, but it has reason to do this based on overall system architecture"
try:
item = list[0]
list[0] = None
file.write(item)
return write_list_to_file(file, list[1:])
finally:
list[0] = item
Despite being compatible with your "tailcall syntax", this is not actually a tailcall. Ergo: no tailcall syntax.
Proponents of tail calls almost always ignore a very simple practical consideration: If you rely on a tail call being eliminated and it isn't, then your program becomes incorrect, in the sense that it goes from needing constant memory to needing infinite memory.
I simply cannot fathom what argument one might have against an annotation "this tail call must be eliminated for this program to be correct" that can easily be verified by the compiler (is the compiled call site CALL instruction followed by a RET opcode? if so, it's a tail call. If not, it's not!). Not doing so means that an enclosing context can change the meaning of the (recursive equivalent to) "while 1:" to "for x in range(MEMORY): ...; raise OutOfMemoryException();" based on compiler optimization capability.
> You are using your own rebuttal as an argument to make tailcalls look harder to analyse! They are not.
No, I claim that they are extremely easy to analyze for a compiler; They are not as easy for a reader (with/try context 50 lines away converts a tail call into a non tail call. You have to both be aware of the context and of this possibility - or you will be unwittingly replacing a while loop with a limited for loop). If you claim that it is easy to analyze for a reader, then you are not considering Python's original and still significant audience: non programmers.
> As a caller of a function, the property you care about is "does it consumes a fixed amount of stack?".
Yes, you do. And as a caller of a function, you don't see or control its attributes in any way, so that isn't an argument for or against decorators.
> As the writer of this function, that's the thing that matters in the end: Sure, that means checking each tail calls, but you really want the global guarantee that you didn't forgot one. The local explicit annotation becomes redundant.
You have two wrong assumptions here:
1) That if all returns are tail calls, then constant stack use is guaranteed.
2) That I actually want every return to be a tail call
Neither of these are necessary. Therefore, while such a decorator may be useful for your style, it does not make a local explicit annotation redundant.
Consider a very sparse tree data structure with n nodes, and 0-500 children for every node, but with only log(n) of the nodes having more than one child. (It arises in practice e.g. when building a suffix array on some kinds of inputs; The Patricia tree is an optimization of this). Computing on this structure can be done as follows, assuming some special case for 2-children nodes:
def collect(node, acc):
if node.count_children() == 0:
return acc + node.value
if node.count_children() == 1:
return collect(node.get_child(0), acc + node.value) # this is key to memory use
if node.count_chilren() == 2:
return acc + PAIR_START + collect(node.get_child(0), 0) + collect(node.get_child(1), 0) + PAIR_END
acc = acc + MULTI_START
for child in node.get_children():
acc = acc + collect(child, 0)
acc = acc + MULTI_END
return acc
Now, the key collect() call determines overall memory use; if there's TCE, it will be overall O(log n). If there isn't, it will be O(n). If you add a try: finally: (with actual code, not finally:pass) it will become O(n) regardless.
The example is realistic, although somewhat contrived to be compact.
If your argument isn't "well, you don't need new syntax and help from the compiler if you just pay attention and remember not to use with/try if you ever need guaranteed tail calls", then please state it more clearly because I haven't understood it.
And if that's your argument, then I think it is technically right but practically wrong (in the same sense that saying "python is useless, you can do everything in assembly" is technically right and practically wrong)
> If your argument isn't "well, you don't need new syntax and help from the compiler if you just pay attention and remember not to use with/try if you ever need guaranteed tail calls", then please state it more clearly because I haven't understood it.
To clarify: Yes, I believe that whichever stack release semantic is chosen (tailcall optimization or the current behaviour) triggers an understanding of its limitation. Languages that support tailcalls natively yield programmers that "see" tailcalls (so they don't think about it more than necessary), and non-tailcall support yield programmers that "see" stack allocation on recursion (but they don't think about the stack more than tailcall programmers do.)
Now, we both like the "default" behaviour that we have practised the most, because we really understand its limitation. When confronted with the other semantic, we can make it work, but it's slower to trigger our reflexes, and causes frustration:
A tailcall programmer forced to use a non tail-call language will have to "compile" his tail recursion into a loop. A non-tailcall programmer forced to use a tailcall language will gain free stack, but won't have to rewrite his algorithm.
Sure, finally breaks the tailcall syntax, just like it breaks the syntax rule "the function ends on a return".
You are right that I haven't stated my motivation for arguing about tailcalls:
- I really believe that tailcalls should be supported by Python. Recursion is too useful, and it's hard enough to teach without suffering the second class behaviour that Python currently offers.
- A new syntax is harder to sell to programmers and the python team, because it says "tailcalls are not the norm". I claim that "return f()" is used way too much to justify the cost of writing explicitly "return from f()" for a free optimization.
- A beginner doesn't need to know about tailcall to benefit from it, just like we don't teach them about the stack until they hit a stackoverflow. If you have two semantics with respect to stack release, it becomes harder to teach than if you choose only one (it triggers the question "why would you ever NOT write "return from" when you can?")
You seem to disagree that tailcalls should be optimized everywhere possible, but I'm not sure if it's because you don't care about writing "return from" in general (and just want to enforce it when it's actually observable), or think that "return from" isn't always an optimization (but I'm really missing a counter-example?), or really believe that tailcalls makes the semantic of the stack harder because of things like "finally" (in which case I think we both suffer from a bias towards the stack-release semantic that we are used to.)
If Python had tailcalls by default, would we have an argument for a "return after" syntax?
I like static analysis. I just don't think tailcalls require a more explicit annotation than any other language feature: writing "return from collect()" in your example doesn't clarify your intent, it just triggers a warning when someone breaks the tailcall (but he can still break the stack complexity through other means.) You do have to state your global property somewhere: the local tailcall annotation allow you to prove it today, not guarantee its survival upon software evolution. And as a user of your library, my static analyser could benefit from a function annotation on your side, but it won't care about your usage of "return from".
> You seem to disagree that tailcalls should be optimized everywhere possible
I don't disagree, assuming there's a way to turn that off for debugging. I love it when things run faster and take less memory.
I disagree that "there's already a syntax for tail call" (that can be relied upon if Python did TCE) because in Python there isn't. Therefore, even if Python had TCE, it would be brittle (a small change 50 lines away could make it into a non-tail call) and it would be bad style to rely on it as a programming mechanism.
I've used common lisp with tailcalls. They work way better there than they would in Python, although there are still interaction problems with conditions/restarts/continuations/macros, mostly as invisible as they would be in Python. (Though, it's been something like 20 years, my memory is hazy).
My claim can be summarized as follows:
1. TCO is nice and awesome. But it is an OPTIMIZATION, and shouldn't be a central language feature you rely on, unless it is easy to guarantee it happens.
2. If you want to rely on TCE as a general programming technique, you should be able to say "and if this thing isn't a tail call, don't compile" or "and if this thing isn't a tail call, give me a warning".
3. A "return from" in Python could be an excellent way to implement (2) for Python
4. I think a special form for Scheme that says "I rely on the following tail call being eliminated" would have been useful, as it is easy to shoot yourself in the foot relying on it while e.g. using macros - where something that looks like it is a simple call expands to a non-trivial expression. Luckily, in CL (and I assume in Scheme as well), you could do that at the library level with a relatively simple code walker.
The Python Library-Level implementations that I've seen use a decorator to add the trampoline and need you to replace "return f(a,b,c)" with "raise TailCall(f, a, b, c)" (or something to that effect - you can get a much nicer syntax with some limitations). Ugly, inefficient, but available if you really need it.
'If your argument isn't "well, you don't need new syntax and help from the compiler if you just pay attention and remember not to use with/try if you ever need guaranteed tail calls", then please state it more clearly because I haven't understood it.'
I don't have much of a horse in this race...I've just been watching the debate going on in the comment threads...but I'll point out three analogous situations:
In C++, we have the keyword 'virtual' because we needed a syntactic marker to indicate whether a function may be overridden. There are two main pragmatic reasons for this: it lets the compiler keep the existing default of being able to jump directly to a known address in the common case (i.e. you don't pay for functionality you don't use), and it lets you know whenever the code that is executed may not be the code that you're staring at. If you rely on a particular method being called and it is overridden, then your program becomes incorrect, in the sense that it may do something completely arbitrary that you never expected.
In Java, we have the keyword 'new' because we needed a syntactic marker to indicate whenever heap allocation may occur. Without it, any object construction may trigger a long-running garbage collection. If you rely on object construction being a fast operation and it triggers a GC, then your program becomes incorrect, in the sense that it may not return results in the timeframe necessary. This is why Java faced significant barriers to entering the hard real-time space, and that market is still dominated by C and Ada.
In Scheme, we have the special form 'delay' to indicate that an expression should be lazily evaluated. Without it, side-effects become unpredictable, and you may also get unexpected space-leaks or execution cascades. If you rely on an operation being strict and instead it's lazy, then your program becomes incorrect, in the sense that it may execute side-effects at unknown times or have non-local execution effects.
Java decided that the 'virtual' keyword was not necessary, and omitted it in the interests of reducing language complexity. Python decided that the 'new' keyword was not necessary, and omitted it in the interests of reducing language complexity. Scheme decided that something like 'chain' is not necessary, and omitted it in the interests of reducing language complexity. Haskell decided that 'delay' is not necessary, and omitted it in the interests of reducing language complexity.
In all cases, there are situations where that omission comes back to bite users of the language. Java re-introduced @Override to indicate overridden methods. Python isn't used in performance-critical software where you want object-creation to be fast. Scheme code is often brittle, where a simple change to the method results in very different stack consumption. Haskell code often has unpredictably space leaks and execution time.
And yet all of those languages have users, some more niche than others.
My argument isn't really about what Python should or do, because realistically, Python is not getting any form of TRE, and I'm fine with that because I don't use Python in a manner or situation that would require it. But it's that "practically wrong" is a relative term, relative to who's using the language and what they're doing with it. Languages have complexity budgets as well; for all the people who don't use a feature, the existence of that feature makes the language less useful to them.
I agree that some language features have a binary nature, like static/overridable or lazy/strict, but maybe we shouldn't classify all of them like that?
The "new" keyword in Java is very much like the proposed "return from": if you know that something is an object, and that object allocation is always done on the heap, then Foo() is as clear as new Foo(). The "new" keyword is a residual from C++, where you actually had a choice. Is it possible that people don't dismiss Python for Java because of the lack of "new", but because its GC isn't as good?
If we had an hypothetical IDE that used colors to transmit static analysis to the user, then we could categorise the keywords between "this is something the IDE can infer" and "this is something the user should specify". Object allocation falls into the inferable (so rather than writing "new", the IDE would highlight the expression in red); virtual is not inferable; delay is not inferable; tail calls are inferable, and can be shown in pink or whatever.
Anyway, TCE is an optimization: we can run more programs faster when we have it. When we don't use tailrec, we still benefit from it as our program consumes less memory overall. The cost of tailcall elimination is purely cognitive, for people who learned the old C-like stack behaviour (but even C compilers handle TCE now.) If TCE/no-TCE matched the static/virtual and lazy/strict binary choice, then there would be situations were TCE has a negative impact on the code runtime.
Tcl added this relatively recently. They use the "tailcall" command, which immediately replaces the stack frame of the current function with one for the new function. If I recall correctly, it doesn't do any checks for whether or not the call is actually a tail-call, so if you do something like
return [expr [tailcall foo] + 1]
the return and expr simply never get executed, producing incorrect results (which I guess is slightly better than a potential stack overflow, since even the most basic of tests will pick up on the missing +1).
I'd use "return from" for tail recursion, to be analogous to "yield from" for iterators. It doesn't add new keywords and "return from foo(...)" seems to me to explain what it does well.
the comprehension version is actually clearer, though. consider: in filter(P, S)
1. which is the predicate and which is the list?
2. is the list filtered in place (destructively) or is a new list emitted?
3. does filter mean "select when P" or "reject when P"? both are valid readings of the english word 'filter', with common non-scitech usage actually leaning more towards 'filter out'
the list comprehension has none of those ambiguities.
To be explicit, they're clearer _in Python_ due to the prevailing style and sensibilities of the community. It's possible to adopt a different set of guidelines that would eliminate the ambiguity.
For instance, in Haskell the data you're working with is always the last argument. This stems from the way currying works, which makes life much more pleasant if the predicate comes first. Ruby also makes it clear, as there's special syntax for passing an anonymous function to a function call.
For your second point, pure functional languages have complete clarity in this sort of thing. In Haskell it's obvious that you're returning a new list, and you couldn't mutate the original even if you wanted to. Ruby has a convention where ambiguously-mutating function names are suffixed with "!" to indicate that this version mutates.
As for your third point, I can see where you're coming from, but filter is a venerable function name. There's a version of filter in most functionally inspired languages (and a version of map, reduce, etc.) and all the ones I've seen only keep elements that match the predicate. I suppose this may be why Ruby calls it "select" instead of "filter". There's also an inverted version called "reject". All of those also have an in-place variant (select!, reject!, map!).
My point is that the ambiguity is not unavoidable. These things could easily be made clearer with different conventions/language-support. Other languages do quite well with these tools, so it obviously can be done in a clear way.
The C#/LINQ syntax for this is nice for this reason. It's S.Where(P), which makes it clear that the thing on the left is the thing being filtered, and that it's taking values x where P(x) is true.
One could also make the argument that it also suggests that it's a non-destructive operation, but that might just be years of familiarity with SQL semantics talking.
Python 3 really pushes you towards list comprehensions as you have to wrap your filter in a list(). I ended up just going with the flow. However, nesting list comprehensions can get me into a place where I forget what it is I'm doing.
This was the worst thing about switching to Python 3. `map` and `filter` are annoyingly "lazy" and `reduce` is basically shunned.
I wonder if the real reason this was changed was to discourage the use of `map` and `filter`... wrapping them each time with `list` is a pain in the ass and hurts readability.
And it breaks code in hard to anticipate places if you don't.
First thing I do when starting something is change them back in global scope. If I want a generator, I'll write one...
I don't think "lazy" is a problem in real code. They just annoys when in interactive shell which you just want to print their result.
In fact python3 has changed a lot of list like data type or function to "lazy", zip(),dict.items() etc. IMO this helps a lot to reduce memory usage. Thus more efficient with functional programming
> but my CS professors made it clear that iteration is basically just a special case of recursion.
More realistically iteration is a practically usable form of recursion to be used in stack based environments. Why do you think you have to optimise recursion into iteration before you can do anything non trivial with it
"iteration is basically just a special case of recursion"
for and while loop are just special case of usage of goto, but this does not necessary means that we need to use goto.
> , but my CS professors made it clear that iteration is basically just a special case of recursion.
That seems a bit disingenuous, since iteration and general recursion are fundamentally equivalent. So you could say that "recursion is just a special case of iteration".
Unless we're talking about specific iterations like iterating over a list, I guess.
I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure.
Iterating over lists, or integers in a range is pretty straightforward. Iterating over a tree? What does that even mean? I suppose we could take "iterate" to mean a catamorphism. Under that interpretation, structural recursion and "iteration" seem pretty equivalent.
Just feels like quite an extension of what "iteration" usually refers to in a language like C.
But with TCO it is no longer needed to maintain a stack structure, so it would probably be a better stated as a tail-call recursive function is equivalent to iteration (assuming TCO)
> I feel that it is a bit disingenuous to claim they are equivalent if the solution to maintaining a call stack is to explicitly maintain a stack structure.
This was a great article. I've spent the last year filling in gaps in my own CS background including CL, Scheme, Racket, CISP, HtDP, etc. This is the first time I've seen good solid reasoning about Scheme using Assembly and it makes things really clear. I wish the author would have taken a little more time reasoning to the correctness of recursion using the y combinator. That's what he ended up with but it would have been helpful to break that down a bit more. Also, he mentioned that his next article in that series would have covered continuations (specifically call-with-current-continuation) and I REALLY would have enjoyed that since I find continuations a little hard to grasp.
I noticed the implicit y combinator as well... here's something I wrote in python some time ago to play with the idea:
def tco(fn):
"""
tco
---
Usage:
Functions should have the following form:
>>> recursive_fn = lambda fn: lambda x: fn(x+1) if x < 1000000 else x
or
>>> def recursive_fn(fn):
... def recursive_fn_cc(x):
... return fn(x+1) if x < 1000000 else x
... return recursive_fn_cc
The notable difference is that called on their own, these
functions aren't recursive at all. For example,
>>> recursive_fn(lambda x: x)(1)
2
This is easier to see in the anonymous-style definition:
>>> lambda fn: lambda x: fn(x+1) if condition(x) else x
So we go from
>>> def recur(x):
... ( function body modifying x )
... if not base_case_reached:
... return recur(x)
... else:
... return x
to
>>> @tco
... def recur(fn):
... def _lambda(x):
... ( function body modifying x )
... if not base_case_reached:
... return fn(x)
... else:
... return x
... return _lambda
Then call as usual like
>>> recur(x)
Functions need to take this form as it exposes the fixed-point,
namely the recursive `fn`. We need a fixed-point for the modified
y-combinator. The modified combinator is the same, only where the
evaluation step would normally take place, each evaluation is
suspended or "thunked" by wrapping in a `lambda`. The thunks
are then looped over and called in a while-loop, sidestepping
the recursion depth issue.
TODO: save the kwargs; eliminate the need to write the functions
as continuations (i.e. `recur = lambda fn:lambda x: ...`) by creating
new function objects from bytecode, replacing instances of `LOAD_GLOBAL`
with `LOAD_DEREF`, may need to build temp function in order to create
closure so `fn` can be added in `co_freevars`. See e.g.
http://nbviewer.ipython.org/github/bravegnu/python-byte- code/blob/master/Python%20Byte%20Code%20Hacking.ipynb
"""
# y combinator with evaluation step wrapped in throwaway lambda
# which suspends the evaluation step;
# important to give `_t_c_o_` or some other highly unlikely keyword
# argument so we can signal to the loop when stop evaluating;
# want to be able to *return* a function as well, so checking for
# '__call__' in directory is not enough.
# Could also check that argcount is zero, and no other keywords exist;
# if we're really nuts, generate a uuid or timestamp, then assign
# it to `_t_c_o_`
Y = (lambda f: (lambda x: x(x))(
lambda y: f(lambda *args: lambda _t_c_o_=None: y(y)(*args))))(fn)
def tco_cc(*args):
_fn = Y(*args)
while ('__call__' in dir(_fn)) and ('_t_c_o_' in _fn.__code__.co_varnames):
_fn = _fn()
return _fn
return tco_cc
...re-reading this I realize the comments are a bit of a mess... basically, it's a decorator that uses the y-combinator to get around the recursion depth problem by "suspending" the evaluation at each step (I'm sure there's some technical term for this... thunking?), then later performing each evaluation inside a while loop. I tested it a bunch and it seemed to work on anything.
I recall being convinced keyword arguments could be made to work, and also that some byte code hacking would get around the "non-user friendly" bit where recursive functions need to be written as "functionals" in order to expose the recursive function itself as a fixed point.
It was cobbled together more or less from scratch mainly based on stackoverflow questions and wikipedia articles. To be honest, it was still somewhat opaque to me (hence the extraordinarily long comments--trying to explain it to myself) but the javascript link makes things much clearer! Thanks
If your goal is to reason about correctness, recursion can be a useful tool. Assembly... is not the hammer I'd bust out for that particular reasoning task.
It would've been nice if mathematical induction were indicated as the foundation of recursion. You're not assuming "it does the right thing" and then proving "it does the right thing". What you're doing is that you're proving that "it does the right thing" by showing that "it does the right thing for N" if "it does the right thing for N-1", and your terminal condition is something like "it does the right thing for 0". Thus mathematical induction takes care of both correctness and termination.
> my favorite programming language is x64 assembly
So, author is _really_ used to reading asm and also smarter than an average developer (and yours truly) or doesn't really care about being able to reason that much.
(But let me be clear, I'm not being sarcastic and wouldn't be surprised if he's really 10x genius.)
Are you associating x64 assembly with "smart" or "10x genius"?
How do you make this connection?
Do you think that Python is more complex than assembly or vice versa?
Are you suggesting that being able to program a computer using a subset of a relatively small, simple language requires more "smart" or "10x genius" than programming a computer using larger, more complex language?
Please note I am not singling you out, nor am I criticizing your comment nor your opinion.
I have seen a similar view of assembly expressed many, many times on this website and I truly am curious how the thought process behind it works.
In my experience, assembly is hard to read and reason about. Harder than C, much harder than python. It doesn't operate in terms in abstractions I, as a developer, am used to; it doesn't have easy syntax that correlates to logic flow (blocks and event statements). May be if I spent significant time with asm, I'll change my mind.
Also, thanks for the disclaimer, although I don't mind if you criticise my opinion and/or comment. Even if you say that I'm just "too stupid for assembly", I wouldn't really mind.
I don't get the argument about why loop invariants are any more complicated than tail calls. The link doesn't seem to clear it up (the same problem would occur with the direct translation to tail recursion).
Great article. Fun to read about both Scheme and Assembly at the same time since I'm currently taking class on each (6.004, 6.945 @ MIT). It's great to get theory from both ends of the abstraction spectrum.
log2 1_000_000_000_000_000 => 49.82892142331043
"Recursion and iteration are equally expressive: recursion can be replaced by iteration with an explicit stack, while iteration can be replaced with tail recursion. Which approach is preferable depends on the problem under consideration and the language used." [1]
BTW, I sympathize with the author's thesis. I was trying to remember algorithms that are easier to reason about in their iterative form... but I can't remember any. Conversely, compare recursive vs iterative DFS [2].
1: http://en.wikipedia.org/wiki/Recursion_(computer_science)
2: http://en.wikipedia.org/wiki/Tree_traversal#Depth-first_2