Answer holds on to one of 2 things: either a FnPlusArgs to call later, or an actual answer (return value) for our function. FnPlusArgs holds a function pointer, and some arguments to be passed to it. Let's imagine for a second we have some classes, which I'll define later. So how would we write code that is tail call optimised in C++? Possibly of more interest to me personally: if we were generating C++ as the output format for some other language, what code might we generate for tail call optimised functions? Tail call optimised C++ Languages which have this feature by design, like Scheme (and D?) can do it more predictably. It is difficult to implement for all cases, especially in C++ since destruction of objects can cause code to be executed where you might not have expected it, and it doesn't appear to be easy to tell when a compiler will or will not do it without examining the generated assembly language. Apparently, some compilers, including MS Visual Studio and GCC, do provide tail call optimisation under certain circumstances (when optimisations are enabled, obviously). * Tail call optimisation isn't in the C++ standard. So, let's see what happens when we compile and run this: $ ulimit -S -s 16ĭid I mention that C++ doesn't do the tail call optimisation?* The key feature of this implementation is that the recursive function times_two_recursive_impl uses a tail call to do the recursion: the value of calling itself is immediately returned, without reference to anything else in the function, even temporary variables. The inner function uses a counter variable and calls itself recursively, reducing that counter by one each time, until it reaches zero, when it returns the total, which is increased by 2 each time. It consists of an outer function times_two_recursive which just hands off control to the inner function times_two_recursive_impl. Return times_two_recursive_impl( 0, value ) Here is the tail-call version: long times_two_recursive_impl( long total, long counter ) The one we're looking at is one of those. Many recursive functions can be re-cast as tail-call versions (sometimes called iterative versions). The tail call optimisation throws away this unneeded state before calling the new function, instead of after. In this case, we don't need any of the state of the current code any more - we are just about to throw it away and return. A tail call is just the situation where you call a function and immediately return its return value as your return value. There is a special case where you don't need it, though, and this is called a tail call. When you call a function from within some other code, you normally need the state of the current code to be preserved. No, because in several programming languages, the compiler or interpreter performs the "tail call optimisation". So is programming like this useless in practice? Tail call optimisation When you call a function from within a function multiple times, the stack grows and grows, remembering the state all the way down to the place where you started. Why does this fail? Because every time you call a function, the state of the current function is saved, and new information is pushed onto the stack about the new function. Note that I set my stack size to be very small (16K) to make the point - actually, this will run successfully for very large arguments, but it will eat all your memory and take a long time to finish. This is fine, but what happens when you run it for a large input? $ ulimit -S -s 16 Return 2 + times_two_naive_recursive( value - 1 ) Then you might get something like this: long times_two_naive_recursive( long value ) Now imagine that you read somewhere that state was bad, and you could always replace a loop with recursion. (Obviously, this is just a silly example designed to be easy to follow.) We’re going have to use “+”: long times_two_loop( long value ) Now imagine that you don’t have the “*” operator. OK, we can do that: long times_two_hardware( long value ) Imagine for a second that you want to write a function that multiplies a number by two. Here’s a toy problem we will use as our example. Update: Source code for this article is available. For a tiny talk at the recent ACCU conference I looked at how we might do something similar in C++. Some programming languages make recursive programming more practical by providing the tail call optimisation. This series: Lightning talk, Explanation, Performance, Generalisation. Matrix is a Distributed Real-time Database Video. Transcoding video files for playback in a browser.Setting the text selection in a browser: just use setBaseAndExtent.
0 Comments
Leave a Reply. |