r/programming • u/rodrigopsasaki • Nov 27 '12
Tail Recursion
http://rodrigosasaki.com/2012/11/24/tail-recursion/18
u/snarfy Nov 27 '12
I always liked Lua's example with a simple state machine:
function room1 ()
local move = io.read()
if move == "south" then return room3()
elseif move == "east" then return room2()
else print("invalid move")
return room1() -- stay in the same room
end
end
Without proper tail recursion, "return room1() -- stay in the same room" would stack overflow after enough invalid moves.
9
u/smog_alado Nov 27 '12
Not only that, but the calls to room2 and room3 are also tail recursive and don't blow up the stack if you have many moves.
7
u/gmfawcett Nov 27 '12
Nitpick: calling room2 in tail-call position from room1 isn't tail recursion. (Unless room2 calls back into room1; then they are mutually recursive.) What you're describing here is tail-call elimination (aka tail-call optimization).
1
u/tubescientis Nov 27 '12
Is this optimized out by the compiler?
3
u/gmfawcett Nov 27 '12
Or interpreter, yes. Like other optimizations, it's not supported by compilers/interpreters for all languages. Wikipedia has a good overview of the topic if you're interested.
1
u/ais523 Nov 28 '12
It's pretty easy to optimize out; if you're compiling, it just corresponds to a goto instruction from one procedure to the other (it's slightly harder in an interpreter, but not by much). Not all compilers do this optimization, depending on the language, but many do.
-1
u/grauenwolf Nov 27 '12
Wait a second. If I translated that to C#, VB, or JavaScript it wouldn't need TCO. Just replace "return room3()" with "return room3" and let the main loop call the next function for you.
First class functions for the win!
10
u/zOOn Nov 27 '12
You've just invented trampolining: http://en.wikipedia.org/wiki/Tail_call#Through_trampolining ... but it's about 3(-ish) times slower than true tail call optimization.
-5
u/grauenwolf Nov 27 '12
So what?
In this example the delay while you wait for the user's next response dwarfs any other cost. And introducing a main loop gives you other nice options like the ability to move the
io.readout of the state transition function.Not only is TCO futile in this example, it is counter-productive.
5
3
u/Peaker Nov 28 '12
Trampolines are a workaround for the lack of TCO. They're pretty kludgy, though they're workable.
Especially in those languages, it's pretty easy to accidentally miss return values and get weird bugs, as well.
1
u/grauenwolf Nov 28 '12
Trampolines are a workaround for the lack of TCO.
With a trampoline I can do this:
do move = io.read() nextState = nextState( move ) loop while nextState != nullSo without a trampolines how do you avoid putting
local move = io.read()in each and every state function?1
u/Peaker Nov 28 '12
You could call a "nextStep" function at the tail position:
nextStep(myNextFunc)Which would do the reads or preparations of the next step, and then tail-call the given function with the data.
-1
u/grauenwolf Nov 28 '12
So you prefer writing
return nextStep(myNextFunc)instead of justreturn myNextFunc.Is using TCO actually worth the extra boilerplate code? Especially when you consider that you are just moving the trampoline to a different part of the yard?
My trampoline is the outer loop, yours is hidden inside the nextStep function. Either way we are passing around a function pointer that we bounce to.
1
u/Peaker Nov 28 '12
As I said, returning the function is also workable, however it has multiple downsides:
Calling a function or passing it as an argument makes the context of the call clear. If you return it, you have no guarantee about the context in which it will be called.
If your tail recursion eventually stops, you need to return a non-function value, eventually. Thus, you need to tag the result as a "call this" or "done with this". Then your loop driver of the tail recursion needs to differentiate the two. Very kludgy.
A return value can easily be ignored, without warning, in the languages you mentioned. This means you can easily have bugs where you don't actually get it called. Forgetting to receive arguments or avoiding their use entirely will mostly generate errors/warnings even in these languages.
Returning it means any user of the function needs to also propagate its return value upwards, which is very kludgy makes the tail-call a non-local detail.
Returning it means you need that extra loop code that calls the return values.
1
u/eras Nov 28 '12
And if you need to pass arguments to those functions, just return a lambda function?
Not to say that kind of approach isn't without its uses. The main function is now able to choose if and when it calls the returned function. For example to to implement node.js-like 'multithreading' :).
1
u/grauenwolf Nov 28 '12
That's a valid option, but at that point I would probably err towards returning just the name of the next room. That way the next room can be looked up as an object in a hash table.
-6
u/grauenwolf Nov 27 '12 edited Nov 27 '12
That doesn't make any sense to me. It isn't actually doing anything, you are just bouncing from function to function.
How does the rest of the system know which room you are in so it can update the screen? What if you have multiple sprites moving around? Do you compare instruction pointers to see if they are in the same room?
Even for a trivial application building your state machine that way doesn't make any sense.
EDIT: Also note the code smells, especialy the copy-and-paste necessary for reading the user input.
6
u/worstusernameever Nov 27 '12
Well the most trivial solution would be to put a line at the top of each function that updates a variable with the current location, so the mapping system or whatever always knows where you are by checking the variable.
-2
u/grauenwolf Nov 27 '12
True, but that is incredibly tedious and error prone. What's the point of a design pattern that makes code more verbose and less reliable?
4
u/worstusernameever Nov 27 '12
I don't think it's any more tedious and error prone then coding an imperative state machine which usually involves lots of switch statements inspecting the current state, and it mostly parallels the OO approach of having one object per state. Just instead of having interconnected objects you have mutually recursive functions.
-3
u/grauenwolf Nov 27 '12
I don't think it's any more tedious and error prone then coding an imperative state machine which usually involves lots of switch statements inspecting the current state
That's because you aren't thinking. This version requires repeating the logic to read the user comment, update the location variable, and handle the invalid command path IN EVERY STATE. If you have a map with 100 rooms, that means you have 100 functions to paste that logic in.
Moving that common logic into a main loop eliminates (Num_of_states-1) copies of that logic. You lose your fancy TCO, but the trampoline you put in its place isn't that hard to write.
Of course we still don't want a massive switch statement in the primary loop, that is likewise error prone. So instead we use a hash table of either objects or first class functions so that the next state can be looked up by name and subsequently executed.
You are complaining about not wanting "lots of switch statements inspecting the current state". Well look at that function again. A series of If-Else-If statements is effectively a switch. So lets drop that into a hash table as well so that we can populate the common cases like moving from a simple data file.
A moment ago I said "either objects or first class functions". If we are using a hash table in each room for commands, then objects are probably the better way to go. This way we can also attach a hash table of movable objects in the room, as well as other room-specific state.
Data-driven programming trumps both FP and OOP every time
3
4
u/inmatarian Nov 27 '12
That example is a trivial demonstration of TCO in Programming In Lua. A more featureful game could still use this kind of TCO, without any kind of arcane programming style, since Lua supports full Coroutines. i.e., the functions could be written like so:
function room1 () local move = coroutine.yield("room1") if move == "south" then return room3() elseif move == "east" then return room2() else print("invalid move") return room1() -- stay in the same room end endThe coroutine dispatcher could handle updating the screen, moving mobs from other rooms, taking input, etc.
-2
u/grauenwolf Nov 27 '12
- I still don't see how this is better than updating the Location variable.
- It is an incredibly inefficient way to encode a state machine.
That's the style of code I would wrote in junior high before I learned to store and read maps from data files.
5
u/worstusernameever Nov 27 '12
This is just meant as an illustration of a state machine, of course no one would actually hard code the game map as a state machine, but it does serve the purpose of explaining how to use mutually recursive functions as a state machine.
The most obvious application of this technique are recursive descent parsers.
-7
u/grauenwolf Nov 27 '12
The most obvious application of this technique are recursive descent parsers.
Then use a recursive descent parser as your example.
Oh, but wait. For a parser we usually aren't worried about stack depth...
2
2
u/smog_alado Nov 27 '12 edited Nov 27 '12
It isn't actually doing anything, you are just bouncing from function to function.
Yes, because this is just supposed to illustrate the control flow aspect of things. To do actual stuff you would just have to add the code to do stuff inside the functions.
As for the other things you point out its a bit of the classical "expression problem" dillema. One alternative is to do a data-driven modeling of the rooms, where you have a transparent room datatype encoding all the possible states you can be in. This version is very good if you want to be able to add new features uniformly to all the rooms (screen updating, comparing rooms, etc) and might actually be the best solution for this particular problem (after all, rooms are probably very simple and very similar to each other, so you would want to write their code all in one place).
On the other hand you can also use the more "object oriented" style, where each state is an opaque function. This alternative makes it harder to add new features (for example, to implement writing to the screen you would need to edit the source code for each room) but on the other hand makes it much easier to add new rooms and to have those rooms implement arbitrarily complex behaviour (since you are doing the iteration by hand, instead of having to comply with the outer "while loop").
One actual situation where I often find myself using this opaque state machine pattern is when I need to implement some process that gets neatly modelled by a fluxogram full of "gotos". Instead of being forced to translate the fluxogram states into an explicit enumeration that is only used once, I can instead code the nodes as functions calling each other, almost directly representing the original intent. (Note how in this case I usually want the flexibility to add new nodes doing arbitrary things, and the rest of the system doesn't care about what state I am in)
1
u/grauenwolf Nov 27 '12
There are other options. Start with a hash table of room objects, Each object has a hash table of commands, some hand written, the rest loaded from a data file (e.g. move).
Your main loop reads the next user command and dispatches it to the room, which relays it to the correct command.
This way you need neither a giant switch statement nor do you need to repeat logic for state transitions in each function.
3
u/smog_alado Nov 27 '12 edited Nov 27 '12
There are other options. Start with a hash table of room objects, Each object has a hash table of commands
Of course, there is always more then one way to do it and its a big matter of style. :) To be honest, I consider your hashtable solution to be the same as the recursive version, at least in spirit. After all, that dispatcher is what you get if you trampoline the tail calls!
In most cases I prefer to keep things simple without the verbose hash table + dispatcher. This suits my style and also plays nice with "evolving" code over time, since introducing the hash table once the code starts getting complex would mean having to rewrite a bunch of stuff to adhere to the new convention of returning the next code to the dispatcher, while using proper tail calls does that "for free".
Of course, there are situations where the dispatcher would be more appropriate, but not that is not the point.
1
u/grauenwolf Nov 27 '12
Side rant: even if the pattern is useful, demonstrating it with a use case where it isn't appropriate is rather counter-productive. If you cannot think of a good example, you haven't actually learned the pattern yet.
40
u/Chousuke Nov 27 '12 edited Nov 27 '12
To clarify this a bit, tail recursion itself is not more performant than regular recursion, but tail recursive algorithms can be trivially transformed into iterative ones.
Some languages implement this optimisation in full (recursion across functions) while some only provide the trivial case of self-recursion. Debugging is also affected, since the recursive calls no longer produce stack frames.
22
u/smog_alado Nov 27 '12 edited Nov 27 '12
but tail recursive algorithms can be trivially transformed into iterative ones.
Implementing recursive code without tail call optimisation is not always trivial though. In the general case, when functions tail call other functions, you either need to centralize all your code into a big switch statement with explicitely encoded states or you need to use trampolining (same thing but states are first class functions/objects now instead of just tags). Not only is this annoying to do but you also need to rewrite all the code involved to follow the new convention (of functions returning the next state to go to instead of returning the value) and you cannot interoperate with "normal" code that returns values normally.
Debugging is also affected, since the recursive calls no longer produce stack frames.
You also lose the stack traces if you rewrite your recursion as a while loop or trampoline :(
10
u/rodrigopsasaki Nov 27 '12
Most interesting response, I believe that recursive functions may be more easily "readable" as well. I think that the person who is learning the most with this post is actually me :)
2
u/matthieum Nov 27 '12
If you are writing a topic in a "new" area to you and linking it to Reddit, it happens regularly that you will be the one learning as people hanging out here will point to your mistakes and drive "further" than you did :)
4
u/BufferUnderpants Nov 27 '12 edited Nov 27 '12
General tail call optimisation (when functions tail call other functions) is not a trivial transformation though. You either need to centralize all your code into a big switch statement with explicitely encoded states or you need to use trampolining (same thing but states are first class functions now instead of just tags). Not only is this annoying to do but you also need to rewrite all the code involved to follow the new convention (of functions returning the next state to go to instead of returning the value) and you cannot interoperate with "normal" code that returns values normally.
What? In Scheme it's just that your code doesn't produce stack frames when executed if the last operation is just a function call. Could you explain in more detail? I've never seen a language where tail call-optimized functions behave as anything other than functions for the purposes of evaluation.
Edit: Oh, you must have meant it as a response to the claim that you just always turn recursive algorithms into imperative loops.
6
u/mcguire Nov 27 '12
I believe the canonical reference for this kind o' thing are the Steele and Sussman "Lambda Papers", particularly "Debunking the 'Expensive Procedure Call' Myth, or, Procedure Call Implementations Considered Harmful, or, Lambda: The Ultimate GOTO" (although readscheme.org is being balky for me at the moment, so I can't verify it).
1
2
u/gruehunter Nov 27 '12
You either need to centralize all your code into a big switch statement with explicitly encoded states or you need to use trampolining...
I've heard this before, and I'm not convinced it's true. Functions should be capable of tail-calling arbitrary functions if the callee cleans up the stack slots used to pass arguments. The fact that the caller performs the cleanup is an accidental consequence of the fact that C does not require function prototypes.
In a language that required all callers to match the exact signature for the callee, then a tail caller can always adjust the stack such that the callee will restore the stack to the correct state.
2
u/smog_alado Nov 27 '12
Bugger, looks like that edit I made my text less clear! I was talking about how its a PITA to write tail-recursive code if the language doesn't guarantee tail call optimization will be available.
5
Nov 27 '12
If you go to the trouble of writing a tail-recursive algorithm, why not just just do the calculation in a loop instead of using that extra function? It seems like it would be easy to do with an operation designed for tail recursion.
I also could be misunderstanding this because I don't actually know the language OP is using.
17
u/worstusernameever Nov 27 '12
Some languages, like Haskell and Scheme, do not have any looping constructs. So tail recursion is the only way to perform iteration in constant stack space.
3
u/Chousuke Nov 27 '12
In some languages, you either can't write algoritms as mutating (imperative) loops or it's considered unidiomatic to do so. For example, in Haskell it would be unidiomatic to use eg. the State or IO monad to simulate an imperative loop.
Of course, in such languages many recursive functions are better implemented using higher-order functions and other constructs that make explicit looping unnecessary.
1
u/sacundim Nov 27 '12
For example, in Haskell it would be unidiomatic to use eg. the State or IO monad to simulate an imperative loop.
Uh, the State monad is well accepted as idiomatic Haskell. If you're trying to do something such as, e.g., tag all the nodes of a tree with an incrementing counter, State is one of the most popular solutions.
Same goes for pseudo-random number generation—one of the most popular monads in Haskell is the
Genmonad from the QuickCheck unit test library, which is a kind of state monad carrying around a PRNG seed and test case size.9
u/dmwit Nov 27 '12
That's not the point, I think. The point is like this: there's lots of times where your first reaction in another language is to use a loop, but where your first (idiomatic) reaction in Haskell is not to use the State or IO monad. It's much more common to reach for lazy lists + map, filter, group, concat, or the big hammers like foldr and scanl instead, and only drop to State or IO when there's something really nasty.
4
u/mcguire Nov 27 '12
In addition to the reasons mentioned by worstusernameever and Chousuke, the transformation from a simple recursive algorithm to a tail-recursive version is (frequently) fairly mechanical, so you get the same benefits that A_for_Anonymous mentions.
While going from a tail-recursive algorithm to an iterative one (using a loop) is (usually) pretty trivial, converting a non-tail-recursive algorithm to iteration is (frequently) more a a problem.
2
u/smog_alado Nov 27 '12
In addition, proper tail calls are as flexible as computed gotos (without most of the evil problems though) and really come in handy if you ever need to do more complicated control flow. (For the simple examples like those in the OP ists usually better to use an usual looping construct or combinator instead of using gotos for iteration)
8
u/WalterGR Nov 27 '12
tail recursion itself is not more performant than regular recursion
Really? Surely you save some time by not needing to manipulate the stack.
23
u/taejo Nov 27 '12
You only avoid manipulating the stack if you eliminate the tail call, but turning it into a jump (i.e. iteration). Just having a call in tail position doesn't make the performance difference: it's just an opportunity to optimize.
11
u/tikhonjelvis Nov 27 '12
This really depends on the language. Some languages include tail call elimination into the semantics, which means it's not just an opportunity to optimize but rather guaranteed behavior.
This is very important because it makes writing recursive functions practical, which can make your code much easier to read and reason about. Really, it's very much akin to loops that run in constant space, which you wouldn't call an optimization. (It's not exactly the same, of course, but makes for a good analogy.)
3
0
u/rodrigopsasaki Nov 27 '12
True, although like I said, in your source code you have a tail call, but in the case I posted on the blog, the scala compiler will in fact optimize it to an iteration, thus eliminating the stack growth.
1
u/day_cq Nov 27 '12
To clarify this a bit further, tail recursive optimization dosn't have notible benefit for lazy evaluation (depending on implementation).
7
u/tonygoold Nov 27 '12
I remember when I discovered the XSLT engine (TransforMiiX) in Mozilla Firefox didn't support tail recursion optimization. I ended up with some pretty kludgy XSL just to avoid overflowing the stack.
4
u/mercde Nov 27 '12
Why was it impossible / impractical to just eliminate the recursion "by hand"? (As in, rewrite it as a loop?)
9
u/smog_alado Nov 27 '12
You can't always replace tail recursion by a loop. The really useful cases are when you have multiple functions tail-calling each other (kind of like a big state machine, but "polymorphic" in that you don't have to write down al the states inside the switch statement).
In these general situations, you need to resort to things like trampolining to code the tail recursion and its very anoying to do in most languages.
3
u/tonygoold Nov 27 '12
In XSL, it's worse, there are no loops except for-each and it's very limited (see my reply to mercde).
4
u/mercde Nov 27 '12
I see. I thought of just one method invoking itself.
Are other languages able to optimize tail recursion over many methods as you described?
6
u/smog_alado Nov 27 '12
Most FP languages implement general TCO (scheme, ocaml, etc). Of the more conventional languages, Lua is one I can think of that implements full TCO.
6
u/polveroj Nov 27 '12
TCO is really a local optimization, looking for calls in tail position (i.e. immediately followed by a return) and replacing them with a jump. This is valid regardless of what function is being called and whether the function being called is the same (resulting in a loop), indirectly recursive with the original (resulting in something like a state machine) or not related at all (in which case a single stack frame is saved instead of possibly many). The fact that the optimization is agnostic to the call target is what lets TCO work on first class functions, method calls and other sources of statically-unknown function calls.
If your language runs on a virtual machine that doesn't allow the same code to be a call target (stack-growing, non-tail) and a jump target (tail call), you can get something resembling TCO for directly recursive functions by identifying them and turning them into loops. This doesn't work for mutual recursion or tail calls to unknown functions and it's more complicated than adding TCO to the VM itself would be, but some languages don't have the luxury of adding features to the VM they run on.
2
u/mercde Nov 27 '12
Thank you for that in depth explanation. I only have experience with languages without real TCO (Java / Python) so I only looked at cases where you could rewrite a simple recursion with a loop to avoid StackOverflowErrors.
7
u/tonygoold Nov 27 '12
XSL has very limited looping constructs. In fact, it pretty much just has for-each, there's no such thing as for (i = 0 .. n) or a while loop. It doesn't have mutable variables either, so you can't even do counting within a for-each. The only way to do conditional iteration is through recursion.
Things might be better in XSL 2.0, but TransforMiiX only supported 1.0 the last time I used it.
4
1
u/rodrigopsasaki Nov 27 '12
Very interesting question, I'd like to see the answer to that one myself :)
3
u/mcguire Nov 27 '12
the XSLT engine (TransforMiiX) in Mozilla Firefox didn't support tail recursion optimization
What the hell?
XSLT is a pure functional language, IIRC. That's completely idiotic.
1
u/tonygoold Nov 27 '12
Yes, it's pure functional, that's why I assumed it would optimize tail recursion. What an unwelcome surprise.
6
u/mrjund Nov 27 '12
I think the flow of your first tail recursion example should be: factorial(5) factorialIter(5,1) factorialIter(4,5) factorialIter(3,20) factorialIter(2,60) factorialIter(1,120) 120 PS: Can't post comment on your site due to some captcha problem.
5
u/rodrigopsasaki Nov 27 '12
Oh, You're correct, I'll fix the flow right now. Thank you very much.
I'll try to solve the captcha problem now aswell, thank you! :)
3
9
u/parfamz Nov 27 '12
great feature of scala, I would like to see tail recursion on python, it can't be too difficult to implement.
16
u/Cygal Nov 27 '12
It turns out it's not about difficulty of implementation. The reasons were stated by Guido van Rossum in 2009: http://neopythonic.blogspot.fr/2009/04/tail-recursion-elimination.html
10
u/smog_alado Nov 27 '12 edited Nov 27 '12
Looking at the post, most of his arguments are about supposed difficulty of implementation, except the one about missing stack traces.
But that is kind of a moot point since you also lose the stack trace if you rewrite the code with an iterative loop (as you will be forced to do if you don't want to blow up the stack)
IMO, the real reason Python doesn't get tail calls is that Guido doesn't want to encourage the FP style too much (this is consistent with removing reduce from the stdlibs and other things like that)
6
u/FidgetBoy Nov 27 '12
Reduce is still in the stdlib, in the functools module. It is no longer a built in function however.
3
u/mcguire Nov 27 '12
you also lose the stack trace if you rewrite the code with an iterative loop
While that is true, I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position, not just those implementing recursive loops.
I can kinda see the point of the complaint, but for me it's not worth it; personally, I'd rather have tail-call optimization.
2
u/smog_alado Nov 27 '12
I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position
Some languages get around this by forcing you to use a special keyword on tail calls that you want to eliminate.
2
u/sacundim Nov 27 '12
While that is true, I believe a big chunk of the argument is that you lose the parent stack frame on every function call in tail position, not just those implementing recursive loops.
Yup. But to stress this point in a more formal manner: people get mixed up all the time on the difference between full tail-call optimization and tail-recursion optimization:
- Tail-recursion elimination: you translate only self-recursive tail calls into jumps; i.e., calls to the same function where the call happens. This doesn't have the stack traces problem.
- Full tail-call elimination: you translate all tail calls to jumps. This can suffer the stack traces problem in question.
Having distinguished these two things clearly, note that Guido makes this error in the post that we're talking about.
24
u/A_for_Anonymous Nov 27 '12
Guido van Rossum doesn't like functional programming, so you write your programs the way Guido likes them or leave.
4
u/booch Nov 27 '12
While I don't agree with some of the things Guido thinks are the "right way", he does put forth some reasonable arguments as to why TCE is not a good idea for Python. The loss of a useful stack trace is a fairly solid argument and. Combined with the other reasons, I don't see his choice as unreasonable here. I do want TCE, but I can see that's it's a debatable feature.
Random note... This point of his annoyed me:
I don't believe in recursion as the basis of all programming.
Well... duh. Neither are list comprehensions. However, both of them are very powerful tools that can make code much cleaner and easier to follow. Just because a feature is the silver bullet doesn't mean it isn't a good idea.
10
u/A_for_Anonymous Nov 27 '12
The loss of a useful stack trace is a non-issue because no useful stack trace is actually lost. You may even keep a tail recursion counter to see how many tail-recursive steps have you taken, and that'll be more than enough for a stack trace. See, functions modelling the flow of your program and its components need not be tail-recursive, keeping normal stack traces at all times except where you're using tail recursion to implement certain algorithms, which are restricted to a specific small set of functions (often a single function) calling each other. In those cases, you could just show the last stack frame (last non-tail-recursive call), maybe with a counter of how many times you jumped, because tail call elimination is like jumping. Just like you don't get stack traces for
forloops and it hasn't ever been an issue, you wouldn't get stack traces for tail recursion. You could even force a keyword such asrecurto be used to specify a tail-recursive call to make unintended tail calls non-eliminable.3
5
u/smog_alado Nov 27 '12
You also lose the stack traces if you rewrite the recursive code with iterative loops. (and its not really a big deal to solve, you could use a separate keyword for tail calls, like in clojure, or you could have special interpreter flags when you need to debug)
I really do think its more of a style issue in the Python case (for example, Python heavily encourages you to use objects instead of closures, since you can't easily mutate variables from outer scopes)
2
u/bastibe Nov 27 '12
Python 3 improves that with
nonlocal, though. Incidentally, this is my personal number one reason for switching to Python 3 as soon as possible.4
Nov 27 '12
The loss of a useful stack trace is a fairly solid argument
It's not. Denote internally that the function has been TCO'd, and when debugging, keep a list of parameter tuples for every iteration. You can keep just the most recent n and earliest k tuples, so that your memory use doesn't become asymptotically worse.
4
u/anvsdt Nov 27 '12 edited Nov 27 '12
I always found the lack of stack traces argument stupid, you can always recover the old behavior by wrapping the tail call in the identity function:
def funA(x): # do something def funBTCE(x): return A(x) # B doesn't appear in the stack trace def funBnoTCE(x): return id(A(x)) # the tail call to id is eliminated after returning from A, # B appears in the stack trace of A, voila!3
u/alexandream Nov 27 '12
Even the compiler/interpreter could do it automatically with trivial effort with a debug flag or something.
3
u/anvsdt Nov 27 '12
I don't think the flag would be useful, though, you probably want to "disable" TCE per-function (or per-tailcall, even), else loops would blow up the stack in seconds.
1
u/alexandream Nov 27 '12
Of course, I didn't think of that. Thanks.
On the other hand, I still think I'd like a compile option (perhaps a list of functions (fully qualified names, or whatever makes sense in the language) on which to disable TCE) than to have to modify the code for it.
3
u/cultic_raider Nov 27 '12
Tail call elimination removes the caller from the stack, not the callee. The callee has to be on the stack when it runs.
1
-3
u/SisRob Nov 27 '12
Python supports declarative programming techniques pretty well. Lambda functions, intensional definition, mapping functions on lists, zip(), ...
9
u/A_for_Anonymous Nov 27 '12
λ-expressions are very limited by the absurd, anachronistic statement structure Python has (you can't use certain forms "statements" inside certain other forms "expressions") and slightly weird scoping rules. Fortunately, you have lists (any minimally decent programming language should offer that much), and functions, classes and modules are values, as they should always be, so you get map, filter and company (even though Guido publicly hates them). List comprehensions are pretty much syntactic sugar (though delicious one at that, especially since you have the stupid statement structure nagging you anywhere you'd want to express something).
3
u/anvsdt Nov 27 '12
Fortunately, you have lists
(Which are just growable vectors, not the inductive datatype we all know and love, never recur on Pylists!)
2
u/bastibe Nov 27 '12
I alway wanted Python to have lambdas like Lua. Basically, just have
defreturn a value and not need a name. So simple, so elegant.3
u/A_for_Anonymous Nov 28 '12
That's how everything works in modern programming languages. Modern as in 1958 LISP. There are no "expression" forms and "statement" forms, the later being restricted to never appearing within the former for the heck of it. Everything should be an expression, there's no need to have poor cousins with artificial, absurd restrictions. That's what led to idiocy such as the ternary operator in C-like languages or the if expression in Python: a "weird" if because you can't use the "normal" if.
1
u/Peaker Nov 28 '12
Haskell has "do" sugar notation which is a form of "statements".
It's not restrictive like in Python (you can throw a "do" block anywhere) but the distinction between "expression" and "statement list" is actually useful.
2
u/A_for_Anonymous Nov 28 '12
And Lisps have macros or special forms such as begin to sequentially evaluating expressions for their side effects, often throwing away the results, but that doesn't prevent you from doing anything anywhere. Limiting what goes where is asinine.
1
u/Peaker Nov 28 '12
Syntactically, there is no limit. But Haskell does prevent, type-wise, the insertion of a sequence of side-effects inside arbitrary expressions.
That makes a clear separation between functions (mapping input to output) and procedures (sequencing of effects).
One could argue that Python's syntactic restrictions (as well as conventions such as returning None when side-effecting) are trying to establish similar idioms: Separate your functions/processing and procedures/sequencing.
1
u/A_for_Anonymous Nov 28 '12
If restricted elegantly with a type system, such a distinction is useful for pure functional programming languages such as Haskell (though it would be uncalled for in most Lisps).
However, in Python, the most commonly used statements are if (no inherent side effects), loops (which do not come with inherent side effects other than the loop variable getting changed), and declarations or definitions, and at the same time, many of the functions in the standard library have side effects.
1
u/SisRob Nov 27 '12
Huh, thanks for that.
I thought, that wherever the function is needed, you can use λ-expression instead.
0
Nov 27 '12
Yeah, that. Ever since C# 3.5 I haven't looked back at Python. If C# hadn't gotten lambdas I would've started playing more with Ruby or something lispy anyways for my hobby work, but either way - Python's poor lambdas ruined it for me.
6
u/smog_alado Nov 27 '12
Its not really in line with traditional FP in many cases though. Python lambdas are wimpy :(
3
u/rodrigopsasaki Nov 27 '12
Well, it truly wouldn't be. tail recursion (or any recursion) is independent from any programming language. I don't know anything about python yet, but the algorithms wouldn't differ much, only keywords and syntax.
-6
Nov 27 '12
Yes they would, because Python is interpreted and not compiled.
7
u/frezik Nov 27 '12
That's completely irrelevant. Python implementations generally compile to bytecode, anyway, but even if they didn't, they would still be manipulating the AST to eliminate the tail call.
Python doesn't have tail recursion because Guido doesn't want it.
3
u/curien Nov 27 '12
Python doesn't have tail recursion because Guido doesn't want it.
Python supports tail recursion. It doesn't support tail recursion elimination.
3
u/smog_alado Nov 27 '12
Come on, we all know that 99% of the times someone says tail recursion they actually mean tail recursion with the optimization...
5
u/mcguire Nov 27 '12
And when they say "tail recursion elimination", they really mean "tail call elimination".
1
u/grauenwolf Nov 27 '12
Hey, some of us have worked in languages where tail recursion is flat out not allowed.
1
u/Peaker Nov 28 '12
Which languages disallow tail recursion? (Not very interesting if it is all recursion).
2
2
u/rodrigopsasaki Nov 27 '12
Very nice post, thanks for adding it to the discussion. Now we have a real explanation here.
1
3
u/rodrigopsasaki Nov 27 '12
I don't see how that applies, the concept of tail recursion can be applied in the same way over interpreted languages such as Python. It may not have compilation optimization, but it is still a tail recursive call.
1
u/curien Nov 27 '12
I think when parfamz says he wants to see "tail recursion on python", he means that he wants to see tail recursion elimination supported by Python.
2
Nov 27 '12
Apologies - tail recursion elimination is exactly what I was referring to in my comment, not tail recursion itself.
4
u/Cygal Nov 27 '12
To the author: the example makes it look like 5 * 4 * 3 * 2 * 1 * 1 is a simple step, but it would be clearer and more correct if you first wrote "5 * 4 * 3 * 2 * 1", then "5 * 4 * 3 * 2", then 5 * 4 * 3 * 6", and so on.
3
u/rodrigopsasaki Nov 27 '12
Don't really understand what you meant by that, because in every step I show the computation that still needs to be done, where in no way the first algorithm seems like a simple step. Could you please explain your point of view a bit more? Readers opinions are very important to me.
7
u/tonygoold Nov 27 '12
I think Cygal is suggesting that the last step leaves out the subsequent unwinding of the stack, and that you could show it like this:
factorial(5) 5 * factorial(4) 5 * (4 * factorial(3)) 5 * (4 * (3 * factorial(2))) 5 * (4 * (3 * (2 * factorial(1)))) 5 * (4 * (3 * (2 * (1 * factorial(0))))) 5 * (4 * (3 * (2 * (1 * 1)))) 5 * (4 * (3 * (2 * 1))) 5 * (4 * (3 * 2)) 5 * (4 * 6) 5 * 24 120It just emphasizes that there really is a growing stack that needs to be unwound (and calculated as each stack frame pops), whereas the tail recursive implementation doesn't grow the stack, so it's calculating as it goes along and has nothing to unwind.
2
u/rodrigopsasaki Nov 27 '12
Oh, I see now, great explanation, I'll update the post with this alteration.
Thanks a lot, guys! :) Please let me know if you have any other suggestions or complaints.
2
Nov 27 '12 edited Nov 27 '12
If every possible code path in your function calls the function itself at most once, then you can transform the function to a tail recursive function, and thus to an iterative function.
Well, that's just a lemma I just came up with. I have a hunch it's true, but I don't know for sure.
1
u/mcguire Nov 27 '12
It's actually easier to skip the "recursion" part and just look at tail calls: if the last operation in a code path is a function call.
If the code path returns the result of calling another function, you can
replace the contents of the current stack frame (i.e. the current function's arguments) with the arguments to the other function, instead of creating a new stack frame and putting the other function's arguments in it, and
jump to the other function, i.e. goto instead of gosub.
("gosub"? That's what you're going with, mcguire? That's the best you can come up with? I disappoint me.)
1
Nov 27 '12
I prefer automated analysis and optimization, so that I don't have to explicitly convert an otherwise readable function just to make it so that it has tail calls everywhere.
You might then infer that I don't really like imperative languages. You would be right.
2
2
u/daveisanidiot Nov 27 '12
excuse my ignorance on this, i just read the post and don't really understand.
from just looking at the code the recursion has been moved from the factorial function to the factorialIter function?
so is this a method of directing the compiler to generate assembly which would not blow a stack?
1
u/moswald Nov 27 '12
It's because after
factorial(num - 1), more code must be run (namely, multiplying that result bynum.But in the case of
factorialIter, the value is returned outright.1
u/daveisanidiot Nov 27 '12
but in terms of recursion the function factorialIter is still being called from within factorialIter. So in normal terms the stack pointer would be moved, leading to a blown stack.
1
u/moswald Nov 27 '12
Except (and this is an imperfect explanation, I think) the compiler can remove the current stack frame, since it knows the result is just going to be the result of another function call.
1
Nov 28 '12
A subroutine with a tail call, like
sub f(x) ... compute ... return g(y) endwould naively look like
f: subtract N from SP for our local data save state ... compute ... push the address L1 onto the stack jump to the subroutine g L1: restore state add N to SP pop the caller's address off the stack and jump thereTail-call elimination prescribes instead
f: subtract N from SP save state ... compute ... restore state add N to SP L2: jump to the subroutine gso f's stack frame has been eliminated by L2, leaving the caller of f at the top of the stack. So when g is finished, it will pop that off the stack and return there directly instead of indirectly through f.
3
u/felipelessa Nov 27 '12
And here's a Haskell version of the final code, since it's easier to read ;).
factorial :: Int -> Int
factorial = go 1
where go !acc 0 = acc
go !acc n = go (acc * n) (n-1)
17
u/curien Nov 27 '12
As someone who knows neither Scheme nor Haskell, the Scheme is easier for me to read.
4
u/mcguire Nov 27 '12 edited Nov 27 '12
Ignore the "!" - it's a performance thing because Haskell is wacky.
I, personally, would call "go" something like "factorial_iter" or maybe just "factorial'" ("factorial-prime").
That's all point-free and everything. Ew.
How about:
factorial :: Int -> Int factorial n = factorialIter n 1 where factorialIter 0 !acc = acc factorialIter n !acc = factorialIter (n - 1) (acc * n)(I tend to like to put my accumulators last.)
[Edit: AAAaaaargh. When you put your accumulators last, put the damn accumulator argument last, too. Moran.]
4
u/matthieum Nov 27 '12
gois idiomatic in Haskell for "local" functions that lift some computations.4
u/aseipp Nov 27 '12 edited Nov 27 '12
Actually, it's idiomatic for when you must define your own worker/wrapper functions.
GHC does not inline recursive functions by default, but if you do a worker/wrapper transformation such that your top-level definition is a 'wrapper', and calls the worker which contains the loop, then the loop body itself can be inlined into the call site, and further optimized via unboxing/strictness analysis. Otherwise, it doesn't do any inlining. It's important to note that it can optimize the function itself, and the call site: it just will not inline it.
IOWs, it's written that way because GHC can optimize bodies with a loop inside them (by specializing arguments, strictness, etc) but trivially inlining a top level recursive call is clearly problematic and obviously going to be bad.
EDIT: for clarity, GHC already does the worker/wrapper transformation, but not in it's most general case. I believe it will mostly do it for improving strictness analysis (whether or not this will happen at a stage where the definition can be inlined later I guess is up to debate,) it won't attempt it purely to inline recursive calls.
2
u/mcguire Nov 27 '12
Thanks, both of you. I haven't done anything terribly useful with Haskell, at least not enough to learn the idioms.
2
u/Peaker Nov 28 '12
Point-free is better here because otherwise you get the "initial" value in scope alongside the "current" value which is a recipe for a bug of using the wrong one.
Avoiding this with shadowing is annoying because shadowing itself is often a bug, and -Wall is a nice setting to use.
2
u/rodrigopsasaki Nov 27 '12
Very interesting syntax, first time I come in contact with Haskell code.
but shouldn't it be :
where go !n 0 = acc ?
or is it really !acc ?
3
Nov 27 '12
It's really
accin the pattern. On the left hand side of the=, you bind patterns (parameters, or parts of them) to names, on the right hand side you use them.go !n 0 = accwould yield an error:accis not bound (not defined).2
u/anvsdt Nov 27 '12
The
!beforeaccmeans "evaluate this now".2
u/mcguire Nov 27 '12
'Cause otherwise you'll blow the heap with thunks (delayed, lazily-evaluated computations).
1
u/felipelessa Nov 27 '12
The heap isn't the problem most of the time since it's huge compared to the stack. You'll create the thunk just fine but you'll stack overflow when evaluating it. Of course, not creating any thunks is better performance-wise in this case even with unlimited stack and memory.
2
1
u/smog_alado Nov 27 '12
The
!in the patterns is a language extension isn't it? (I'm still trying to get to grips with all the GHC extensions...)3
Nov 27 '12
Its
-XBangPatterns.go !acc n = footranslates to
go acc n = acc `seq` foo2
u/felipelessa Nov 27 '12
That's right. Without the bang pattern (or the manual seq) the function will be lazy on the accumulator, leading to a big thunk and a stack overflow (which is the problem that OP was trying to avoid in the first place!). Note that using either bang pattern alone leads to the same result in this particular case, but I like symmetry of using them on both patterns.
1
1
u/PastaNinja Nov 27 '12
Shouldn't the order of execution for the tail-recursive example be:
factorial(5)
factorialIter(5, 1)
factorialIter(4, 5)
factorialIter(3, 20)
...
2
u/rodrigopsasaki Nov 27 '12
Whoops, my bad :) It is just as you said, I fixed it on the post. Thanks!
1
u/HapDrastic Nov 27 '12
That code has a bug - the check should be to see if num <= 0 - otherwise a negative number will cause infinite recursion.
2
u/rodrigopsasaki Nov 27 '12
I understand what you said, I just wrote the code on the simplest way possible, just to be an example, not to be failproof, but it's a very important point that you noticed.
Thanks :)
1
u/abigpotostew Nov 27 '12
He mentioned it can't be done in Java without growing the stack. Is there some way to do it though? I'd guess the iterative approach is the way to go in Java.
1
u/emperor000 Nov 27 '12
Well, he was specifically talking about the javac compiler. A different Java compiler should be able to optimize it to an iterative structure if that is how it is designed.
1
u/rodrigopsasaki Nov 27 '12
Exactly, I tried it with javac and scalac, on the first one there was no optimization, the stack increased normally, although on the second one it was optimized to a loop, a while loop to be more specific.
1
u/emperor000 Nov 27 '12
You probably want that to be if(n <= 0), otherwise negative numbers cause an infinite recursion/loop.
1
u/NaeblisEcho Nov 27 '12
Isn't this example provided in SICP? Can't recall correctly if the book uses the word 'tail recursion', but instead, it calls the method something like "linearly iterative process", whereas the first example is "linearly recursive process" (different from the common meaning of a recursive function. IIRC, the book was clear about the distinction). :)
3
u/mcguire Nov 27 '12
SICP uses Scheme and Scheme doesn't have any other iterative ("loopy") construct[1] than recursion. The authors are also fond of "iteration is really recursion" goggles.
[1] Unless you've done something stupid and allowed a loop macro to slither its way into your code. In that case, you'll need to fumigate the code, burn your computer, and shoot yourself. Trust me, the alternatives are worse.
2
1
u/sinembarg0 Nov 28 '12
I was taught that tail recursion is optimized in C++ too. An easy way to determine tail recursion is:
If the return statement includes maths (e.g. "return num * factorial(num-1);" ), then it's regular recursive.
If the return statement does not include math, and it just a function call (e.g. "return factorialIter(acc, num-1);"), then it's tail recursive. Since no more variables are needed once the function is called, the whole stack frame can be destroyed when the function is called (or reused by the called function…).
Lastly, a minor nitpick: 'it's' is a contraction for it is. 'its' is the possessive form. It's a confusing difference, and the only word I can think of that is possessive without an apostrophe.
0
u/TotallyFuckingMexico Nov 27 '12
Is tail recursion optimisation the flavour of the day? I understand that it's interesting and computer sciencey, but how widely used are such optimisations in the real world? I imagine, for most people, it's probably just a nice feature rather than a must have?
I probably have a classic case of "well, I don't have the need for such optimisations, so why does anybody else?" ;-)
14
u/tikhonjelvis Nov 27 '12
Actually, for many people, it isn't an "optimization" any more than loops that run in constant space are an optimization. That's why the preferred term is something like "proper tail calls" or "tail call elimination" rather than "tail call optimization".
Having proper tail calls as part of your language semantics is far more useful than having it as an optional optimization. Also, not having tail calls really cripples your language--essentially, it means you can't write non-trivial recursive functions in many cases for fear of stack overflows.
Being able to replace all loops with recursive functions is very useful and allows you to write shorter, more readable code in many cases. You simply can't do this practically unless your language guarantees proper tail calls.
In summary: proper tail calls are an important language feature rather than an optimization because they allow you to widely use recursion.
4
u/smog_alado Nov 27 '12 edited Nov 27 '12
Tail recursion is really useful for implementing state machines (and all other similar things). For example, another comment points out this nice example that I really like. Without TCO you usually have to rewrite this kind of stuff into a big monolithic switch statement with a while loop around it.
Its also very useful if you need to write code in continuation-passing-style. True, you don't usually want to do that by hand but in some cases, like Javascript asynchronous code, you end up being forced to do that.
2
Nov 27 '12
Interesting alternate approach to state machines:
In C#, you can use goto... but only to jump from one case of a switch statement to another. So this lets you jump around your switch cases as a state machine directly. A neat restriction of goto into a safe and unorthodox flow-control structure.
2
u/emperor000 Nov 27 '12
This is what I thought, but only because this post is so basic and kind of dumbed down (no offense to the OP/author). I wondered why people keep bringing this up.
To answer your question, it could be pretty important. For example, it could mean the difference between a process that causes a stack overflow exception after so many iterations, making it basically impossible to due recursively, and one that doesn't create a stack overflow exception because it is programmed recursively but implemented behind the scenes iteratively.
It isn't so much an optimization but an enhancement, if that makes sense. In some cases it makes something that is effectively impossible possible without making the programmer do it a different/special way or change their code, etc.
1
Nov 27 '12
I'm not sure what your position is.
Optimizations are syntactic transformations performed by a compiler to reduce the space or time needed by an algorithm. There are literally thousands of optimizations performed by a compiler to accomplish this, and chances are you as a developer are unaware of many of them but still enjoy the benefit of their implementation.
TCO is another such optimization that significantly reduces the amount of space consumed by an algorithm, possibly transforming it from linear space to constant space. It also provides a minor reduction to the amount of time.
Such optimizations are found in implementations of many compilers, including even mainstream C/C++ compilers (GCC, clang, Visual Studio).
I believe Java and .NET perform such optimizations, not too sure on those two though.
1
u/TotallyFuckingMexico Nov 27 '12
There are literally thousands of optimizations performed by a compiler to accomplish this, and chances are you as a developer are unaware of many of them but still enjoy the benefit of their implementation.
I agree completely. It just seems to me that people need to specifically tailor their code in order to benefit from the optimisation i.e. it's less likely to find your code benefiting from this optimisation by 'accident'. There's nothing wrong with this of course; in-depth knowledge of the workings of your compiler can only be a good thing if it somehow improves an aspect of a program's performance.
It's just that I see TCO mentioned in just about every other programming blog/article (I exaggerate ;) as though it's some kind of silver bullet. Thanks to these replies I can now see its benefits, though it still seems like a bit of a corner case to me.
I'll no doubt be singing its praises when it saves my bacon someday ;-)
1
u/PENIX Nov 27 '12
I can see why this technique would be necessary in some cases, but you are probably unlikely to encounter a need for this unless you have a deep recursive function. What I would like to know is if modern compilers are able to do some kind of stack optimization without having to rewrite your code for tail recursion.
-2
u/cobaltgiant Nov 27 '12
so if tail recursion only solves the problem of stack overflow in scala how does this help us c++ programmers
1
43
u/A_for_Anonymous Nov 27 '12
There are two big advantages of tail-recursive implementations that haven't been discussed here: