This Function is Not Tail Recursive | Hacker News Reader

This Function is Not Tail Recursive

codemonkeyism.com

25 pointsfogus39 comments

No one addressed the parallelization claim, so here goes:

The ability to parallelize purely functional code comes from the Church-Rosser theorem (http://en.wikipedia.org/wiki/Church%E2%80%93Rosser_theorem), which states that you can do beta reductions in any order in the lambda calculus and get the same term.

The thing with tail-recursive code is precisely that there is only one way to do a reduction - the function has to call itself at the end. That's what makes tail-recursive code "iterative."

As soon as you introduce multiple reduction paths, you need a stack for the intermediate results - think of for example a recursive divide-and-conquer algorithm.

This Kornelius Fuhrer dude shouldn't be writing articles on parallel programming, he should be reading books about it.

I can, however, see a compiler turning simple cases of tail recursion into recurrence relations, and re-extracting the loop, but it's a relatively long way to go to get back that iterative bit of the problem, especially as a language in which tail recursion is often used probably won't be working with mutable arrays as often - a loop over input and output arrays being probably the easiest parallelization candidate.

I never thought about it that way. That's quite clever and out of the box!

Guy Steele gave a very good talk about the problem (basically, "tail recursion considered harmful") and solution ("divide and conquer") at ICFP last year: http://docs.google.com/viewer?a=v&q=cache:bBDVKW8DP6UJ:l...

APL-style operators (map/reduce, paralations, NESL, etc.) are definitely the way to go. Not only do you get parallelization "for free," but optimizations like map fusion (see http://www.randomhacks.net/articles/2007/02/10/map-fusion-an..., and Rich Waters' earlier work on SERIES: http://series.sourceforge.net/) become easy - something like that is almost impossible to do with loop analysis. All that, and you end up with clearer, shorter code. Due to all these reasons, I'm convinced that automatic loop parallelization is the biggest waste of time in parallel computing research.

In the example case, and many others, the tail-recursive version is the simple application of an accumulator. So for the factorial example, an accumulator version would be (in haskell since I don't know the example language very well):

  fac1 0 = 1
  fac1 n = (*) n (fac1 ((-) n 1))

  -- tail-recursive
  fac2 0 acc = acc
  fac2 n acc = fac2 ((-)n 1) ((*) acc n)

To me, something in with a pattern of:

f v = g v (f (t v))

where f, g and t are functions (t is a transform on a, in the factorial case it is (-),

Can usually be turned into the form (mechanically even):

f v acc = f (t v) (g v acc)

Does this hold for all cases or am i missing something? If it does hold, could a language just implement the TCO for it, and therefore couldn't we just consider the very first implementation of fac1 to be tail-recursive?

edit: It is ugly but changed my exmple code to match the pattern i describe exactly.

I believe this has some issues if the operation isn't commutative.

For example:

blah 0 = []

blah n = (++) [n] (blah ((-) n 1))

-- blah 5 -> [5,4,3,2,1]

blah2 0 acc = acc

blah2 n acc = blah2 ((-) n 1) ((++) [n] acc)

-- blah2 5 [] -> [1,2,3,4,5]

If we changed the tail to: blah2 (n-1) ((++) acc [n]) it would work in this case, but then we've flipped the arguments, and I have a feeling we could come up with a function where simply flipping the arguments won't work, though I can't think of one at the moment.

Good point! It becomes hard to do mechanical transforms like I suggested when you have to keep track of properties like this for every function. Thanks!

Ya that's the problem. Here's what I originally intended to write, but couldn't think of how to do cons in haskell so I used list addition. With cons (:), you can't rewrite it with the arguments swapped, so no simple mechanical transform will be able to fix this.

blah 0 = []

blah n = (:) n (blah ((-) n 1))

-- blah 5 -> [5,4,3,2,1]

blah2 0 acc = acc

blah2 n acc = blah2 ((-) n 1) ((:) n acc)

-- blah2 5 [] -> [1,2,3,4,5]

As you most likely realize, f base needs to equal the identity function. After that, it looks like t is your iterator and g is the function you want to fold. It looks like f is an iterator-friendly fold function.

A comment on the site itself noted that tail recursion does not imply parallelization -- in fact, I would make a stronger statement that it forces serial execution, at least as far as funneling results of one "iteration" into the next.

The benefit, as "everybody" here of course already knows, is to reduce memory (call stack) usage.

Knowing how to implement tail recursion allows you to write in an "assign only once" type of language, without blowing up the stack. And using such "invariant symbols" in a routine allows the compiler/interpreter to seek parallelization at other points in the function on your behalf. OK, so I just contradicted myself, but the point is there is an rather indirect connection between tail recursion and parallelization.

One way that would make that particular example clearer is to convert the multiplication from an infix operation to a function call:

return n == 0 ? 1 : n * fac(n -1);

becomes

return n == 0 ? 1 : multiply(n, fac(n -1);

This makes it a fair bit clearer, IMO.

I suspect a better approach is to make expected tail recursion a language feature, and have the compiler emit an error if the returned expression is not in fact valid for a tail call.

Imagine if it were 'treturn' or something.

It's not something that bites people who have been around this mulberry bush before, but I think it can very likely catch problems that novices have, thinking they're writing an O(1) space solution but actually using O(n) stack.

OK. But then, even if somebody is using `return', and its tail-recursive, it should be optimized. (`return' should just not raise an error, if it's not tail-recursice.)

Deleted comment

[no longer applies to the comment]

Wow, this is basic stuff. I'm surprised that a researcher would get this wrong.

Also, let us not forget that tail recursion is a specific form of the more general tail call optimization. For example, the following is two TCO-able functions calling each other:

    functionA(...):
        // do stuff
        return functionB(...)

    functionB():
        // dostuff
        return functionA(...)

Whether or not the compiler optimizes this, however, is a completely different question.

Perhaps I'm missing some larger point here, but if all tail recursive operations can be represented as loops, why not code them that way in the first place? It's probably better to know that recursive calls take up stack space on each call, than it is to know that tail recursion optimizes to a loop.

If somebody could provide an example of a tail-recursive function that would be much more difficult to code as a loop, I'll eat my words.

Take a look at parsers. E.g. Parsec (http://www.haskell.org/haskellwiki/Parsec). They probably have lots of tail-calls, and wouldn't look nice with loops. Some parsers also make use of continuation passing (http://en.wikipedia.org/wiki/Continuation-passing_style), which only works with tail-call optimizations.

As it happens, I've actually grown to like Clojure's recur more than tailcalls. And I much loved tailcalls over imperative loops earlier.

recur is still functional, it resembles a loop but isn't one so nothing is mutated, and you can even nest them. And you can recur over a loop or the function itself. Handy.

That's fairly common style in Scheme as well, fwiw; a "named let" is very similar to Clojure's recur, and some programmers prefer it over tailcalls, at least for many common recursion/iteration patterns.

On the JVM, wouldn't * be an operator rather than a function? Would it even make a difference?

It wouldn't, because you would still have to do something else after the recursive call to your function. That would prevent you from applying tail-call optimization, which is the point behind making your function tail-recursive in the first place.

For those who aren't familiar with tail-call optimization, here's a very simplified explanation: if the very last thing you do in a function is call it recursively, then instead of allocating the space for its local variables (and any other local state it might have) for another call, you can simply set the arguments to their new values, reset the local state and do an equivalent of "goto" to the beginning of the function.

No. The very last instruction of tail recursion (on the recursive branch, not the base case of course) should be directly returning the return value of the recursively called function. Otherwise, you cannot overwrite the stack frame (in other words, you need to remember the values of temporary variables of previous iterations).

At the assembly/bytecode level, you still have to save the return value of the recursive call and then do something to it, whereas a tail call wouldn't need to save any intermediate value because it would immediately return it as soon as it got it.

I guess Java's infix notation kind of obscures this. This is one of the reasons why functional programmers prefer to consider everything a function. It's also why some languages (like Clojure) have special syntax for tail calls, with special error messages if you goof up the semantics.

Yes, in Lisp there's no real difference between * or car.

In Haskell, which has more syntax, you can use * in infix notation, but so you can with other function. E.g. the function `on`. Quoting from the documentation:

  on :: (b -> b -> c) -> (a -> b) -> a -> a -> c	
  (*) `on` f = \x y -> f x * f y.

  Typical usage: Data.List.sortBy (compare `on` fst).

I like this idea - never came up to me before

n * fac(n-1) vs. * n fac(- n 1)

or * (n, fac(n-1)) as a method call, which makes it clear * is the last function that's called.

The correction is incorrect.

A function is tail recursive when the last thing it does is call some function, possibly different. Yes, you can have a mess of different functions that are mutually tail recursive. For an example of how this comes up, think "state machines" with each call being another state transition.

I am used to the term Tail Call for a function that returns the result of calling another function. Tail Recursion is then a special case where a function makes a Tail Call to itself. Mutual Tail Recursion is another special case where multiple functions make tail calls to each other in such a way that a function will end up calling itself indirectly.

Not a tail call:

    var even = function (x) { return x == 0 || !even(x-1); }

Mutually Tail Recursive:

    var even = function (x) { return x == 0 || odd(x-1); }
    var odd = function (x) { return x == 1 || even(x-1); }

Your first example is actually a tail call. It's just a tail call to the || operator. Every function has a tail call by definition.

And the next two examples are tail calls of even and odd thanks to shortcutting of ||.

Absolutely the calls to even and odd are tail calls because of the semantics of || in Ruby (and most other languages). I hope we agree that even and odd are still mutually tail recursive, because Mutual Tail Recursion is a special case of tail calling.

I don't understand what his last statement means:

"So please, do not call all functions where the last function call in your source code is a call to itself, tail recursive. A function is tail recursive, if the last operation is a function call to itself."

It reads to me as "Don't call functions that call themselves last tail recursive. A function is tail recursive if it calls itself last."

That's saying the same thing, if my reading of it is right. His oddly-placed commas don't help.

I can't read the article (silly work web filters), but if you're quoting him correctly then I have an idea. (

  function foo(n) {
    ...
    return n+foo(n-1);
  }

is not tail recursive because the last operation is not the recursive function call, but rather the addition.

  function bar(n,acc) {
    ...
    return bar(n-1,acc+n);
  }

is tail recursive because the last operation is now the recursive function call.

He's pointing out that the order of statements in the source code doesn't necessary correspond to the order of evaluation. In this case even though the function call is the last statement in the source code, it's actually an argument to the multiplication, and the multiplication is the last operation being executed. That's non-obvious when just looking at the code, since the function call looks like it's last.

It seems like a difference without distinction to me. I mean, sure, it doesn't fit the precise dictionary definition of tail recursion, but the function would be fairly trivial to implement in a purely tail recursive manner. As such, its close enough for most purposes.

Tail recursion means that there's nothing in the continuation of the recursive call besides a return from the outer call.

This means that a compiler can optimize away the saving of a new stack frame for a recursive call, because the old stack frame of the enclosing call will never be used again. That's tail-call optimization.

If there's stuff in between the return from the recursive call and the return from the enclosing call (like the multiply in this factorial example) then the old stack frame will have to be kept around which means you must use unoptimized recursive calls.

It matters when you have an interpreter/compiler that does tail-call optimization. If the function is tail recursive then the recursion will only use O(1) stack space, while non-tail recursive functions will use O(n).

It makes all the difference in the world - One can be converted by the compiler into a loop that will never use more than one function call's worth of stack, and the other must cause an unbounded amount of memory usage dependent on the input argument.

In other words, it's the difference between O(n) and O(1) memory usage.

> As such, its close enough for most purposes.

Well, this purpose was to make it a tail call so that it could be optimized. Since it either is or it isn't, "close enough" to "is" is, sadly, "isn't". Which turns it from O(1) to O(n).

Sometimes it's trivial, sometimes it's not. Sometimes it's not even possible (e.g. the naive Fibionacci algorithm). Sometimes all you need to do is to add an accumulator argument to the recursive function. Still, it's not something that can be easily automated and I'm yet to see a compiler that does it automatically.

In computer science (and generally, in mathematics), every word of the dictionary definition matter.

Reply on news.ycombinator.com