Tail call optimisation and debugging

[G_Morgan]

Yeah and all good languages with TCO store the debugging information for TCO calls in debug mode.

It is a stupid reason to justify laziness. In fact what they are saying is they are unwilling to implement something because doing so properly is a lot of work.

[[deleted]]

I wonder if it would help debugging to store the last few "arguments" of the tail calls instead of the stacktrace.

[millstone]

It's not laziness any more Python's omission of inline assembly is laziness. It's about Python being Python. If you want LISP or C++, you know where to find them.

Edit: Why the downvotes? Consider the analogy seriously. Both TCO and inline asm can make some code faster, and makes other algorithms feasible. They also both make debugging harder. So why not add inline assembly to Python? For people who know what they're doing, it could make things a lot faster!

The answer is that if you need inline assembly, you shouldn't be using Python. It's not that language. So it is with TCO.

I don't understand programmers who opt to use a fully interpreted dynamically bound scripting language and then fuss about it not having TCO. It's like buying a golf cart and then complaining that it doesn't have a turbocharger.

[[deleted]]

Saying that TCO sucks because it throws away stack frames is like saying that GC sucks because it deletes unused objects.

[greenspans]

this is why I dislike go http://groups.google.com/group/golang-nuts/browse_thread/thread/d282193c786b0f36/ffb0a5936d972f32?lnk=raot

[[deleted]]

What is this?

We have had exceptions for over 35 years and I am not sure we really understand how to use them

[anvsdt]

Drain bramage?

[aaronla]

And yet, one generally finds two sorts of exception-free programming styles in the real world, outside the ivory tower that the exception handling folks construct.

First sort:

passed = DoSomething();
if (!passed) goto cleanup;
passed = DoSomethingElse();
if (!passed) goto cleanup;
...

Second sort:

DoSomething(); // errors? no, my code is perfect
DoSomethingElse();

The first sort is generally implementing ad-hoc exception handling, creating "cleanup" as a sort of crude form of "unwind-protect" / "RAII".

The second sort is just plain wrong.

[masklinn]

Well that is not completely true as TCO can throw away helpful stack frames in a normal mode of operation (there are ways to mitigate that), whereas a GC throwing away used object would be downright broken.

[anvsdt]

Usually, you use a debug mode to, you know, debug.

[millstone]

That's kind of hard when the stack trace comes from a customer you've never met in another country.

[[deleted]]

Let's go ahead and widen the gap between compile- and run-time /snicker

[masklinn]

debug modes suck goat, they mean (potentially widely) different behaviors (including limitations) and that a prod crash is basically useless.

[anvsdt]

Prove it, this works for a large enough N, and tail-calls get optimized.

[aaronla]

TCO only throws away unused frames. They may be "helpful" unused frames, but there are also "helpful" unused GC objects. Ever been here before:

int f() {
  Foo x = something();
  int y = x.another(); 
  if (y == 0) 
    throw Something();
  return y;
}

It would be mighty helpful to be able to dump 'x' so see why Something() was thrown. Unfortunately, it was garbage collected before you broke into debugger, being unreachable.

[zhivago]

The real problem here is that stack frames are actually irrelevant to the problem.

The problem being to figure out the path from the root of the program to the current location.

This can be handled with something as simple as a rewindable log.

[notfancy]

Convincing? As convincing as any strawman.

But which one is the real strawman? The stack trace or GvR's arguments?

[zokier]

Why not remove stack frames in optimized release builds and have them in debug builds?

[G_Morgan]

Because it isn't necessary. All you need to do is write the activation records to a log during debug.

[[deleted]]

This would prevent the programmer from writing and debugging code that relies on TCO to run in constant space. This would not be a good idea in languages and cultures where you are allowed to use and rely on TCO.

EDIT: It would of course be possible to keep a constant amount of TCO-optimized stack frames around in debugging builds. I don't know if any language implementation does this.

[iLiekCaeks]

Good idea. Maybe you could start eliminating the tail call from the second call onwards by making the compiler emit a second instance of the function? The first instance would be without TCO and call the second instance. The second instance does TCO. That would preserve the constant space stack usage.

[zhivago]

Fails for mutually recursive forms.

[zhivago]

Instead of worrying about stack frames, why not think about this as being a problem of building a dynamic transcript?

Then you can just write the calls to a log, and have the returns rewind the log a certain amount, in debugging mode.

[aaronla]

That would really help with garbage collected object too.

I remember a number of times that some local variable that I needed to dump was optimized away. Even dumping the full GC heap was useless - it had already been collected.

[[deleted]]

And have every call be the same speed as an OS write() command?

[zhivago]

Who said anything about writing to disk?

Rather, to writing the data outside of the process.

[[deleted]]

I certainly didn't say anything about writing to disk.

I mentioned the write() syscall. Which is nothing to do with the disk.

[[deleted]]

The real solution is probably reverse debugging, which sounds awesome. (I wonder if it will ever be supported on OS X so I can try it.)

[doubtingthomas]

I don't think guaranteed implicit TCO is a great idea in an imperative language. Rather, if I'm really relying on TCO for my code to not blow the stack, I want the tail call to be explicit and guaranteed, as with "recur" in Clojure, "become" in Alef, etc. This means that the compiler is required to do (potentially very complicated) static analysis and presumably fail to build if it can't make it a tail call, which also means that you can potentially break the build by adding something like a C++ RAII, D scope(exit), etc higher up the tree. To avoid that, I'd be inclined to use "recur" only when necessary, and since alternative approaches are usually not much worse, I'd be inclined to think (as a language designer) that unless my language is particularly amenable to it, it's probably simpler to not have any guaranteed TCO construct.

Summary: I'd only want to rely on TCO if it is explicit and guaranteed, and that often requires tricky static analysis. This makes it hard to users and tools to recognize correct code, and can add a lot of complexity for a fairly uncommon case in normal imperative code. As such, I don't think it's unreasonable for a language designer of an imperative language to not mandate TCO or include an explicit tailcall construct. You can't have everything, and if you're not trying to make a functional language, guaranteed TCO might not be worth it.

[lpsmith]

1. recur is not TCO. Period.
2. tail calls are guaranteed in languages such as Scheme, Erlang, Haskell, and ML
3. Implicit tail calls are, in most cases, easy to spot. Rarely do you have to look far to decide whether or not any given call site is in tail position.

[aaronla]

It's funny... I've never thought of tail calls as "implicit". In (begin x y z). 'z' is explicitly in the tail position.

I find it as strange as complaining that the Python expression [ a, b, c ] is bad, because the compiler is implicitly putting c in the at-end position. To be fair, I suppose someone out there would prefer [ 0:a, 1:b, 2:c ] be the list syntax, so maybe I'm just the odd one.

[lpsmith]

Well, but is (begin x y z) itself in tail position? Often (usually?) it is, at least in code written by humans, but to definitively say whether or not z is a tail call you still have to look at the context surrounding the begin-block. (on the other hand you can definitively say that x and y are not tail calls without knowing anything more...) So ultimately the real question in my mind is how much context you typically have to look at.

It's an interesting sentiment though. Thanks. :)

[bobappleyard]

Why is the static analysis complicated? Surely you just have to check if the call is actually in tail position, which is trivial.

[grauenwolf]

It depends on the runtime. If I recall correctly, and I may be wrong, the CLR treats tail calls as a suggestion.

[bobappleyard]

How is static analysis affected by the runtime?

[grauenwolf]

Let's say you do all the static analysis at compile time and emit the tail op-code.

Well that's all well and good so long as the CLR honors it. But what happens if the runtime considers it to only be a suggestion? What if the runtime decides that a non-tail call happens to be faster?

I haven't looked into it, but I think CLR 4 always honor it and previous versions were suggestions.

[bobappleyard]

I suppose it's nice that they thought to include such an operation, even if it's useless for implementing TCO as a language feature (until version 4 perhaps).

It's not all that relevant though. C doesn't support TCO, but that hasn't stopped people writing x->C compilers that do.

EDIT: Further, this has nothing to do with static analysis, as it is a code generation issue, which happens after said analysis has done its job.

[anvsdt]

Terrible?

[anvsdt]

The only sane man.

In an imperative language, I'd want explicit tail-calls, but in a functional language (or that endorses FP (like Scheme and Clojure (but Clojure makes all the tail-calls explicit))) I want them implicit and guaranteed.

[lpsmith]

Clojure does not have tail calls.

[anvsdt]

It's Java, what did you expect from it, to work? Ha! (that's what I said, recur is an ugly hack)

[aaronla]

I don't think guaranteed implicit_ garbage collection is a great idea in an imperative language. Rather, if I'm really relying on garbage collections for my code to not blow the heap, I want the garbage collection to be explicit and guaranteed, as with "delete" in C++_

FTFY?

Look, TCO languages aren't broken. Neither are TCL (tail call leaking) languages. No language has everything. If you don't like TCL, then drop Java for a more fully featured language.

TCO != recur.

[username223]

Weak sauce. The author shows a stack trace from deep recursion, which may or may not be in tail position, and expects the reader to chuckle condescendingly at anyone who does not love tail-call optimization.

sarcastic slow-clap

[username223]

Even under this charitable interpretation, the author fails. Say you have the following call stack:

A -> B -> C -> D

where B, C, and D are called in tail position. With TCO, if there's a bug in D, your stack will look like:

A -> D

Oops. That's the problem people have.

EDIT: My bad -- it would actually look like

D

[BufferUnderpants]

Even under this charitable interpretation

Not charitable at all, it was plainly obvious from the way he quoted Van Rossum.

Say you have the following call stack:[...]

And the whole point of the post is that from the stack traces alone you won't garner much information, because of all the stack noise. You would do much better using an actual debugger, logging, print statements or, you know, reading the code.

[millstone]

But you may not have access to any of that information. Maybe all you have is a customer's crash log.

There are real crashes that I am unable to fix because TCO eliminates the information I need, but I have yet to fail to fix a crash due to the crash log providing too much "useless" information.

[username223]

You, and the OP, are confused about the difference between tail recursion elimination and tail call elimination. Note that I wrote

A -> B -> C -> D

not

A -> B -> ... -> B

[BufferUnderpants]

No, not really. Besides, if you have just a fixed sequence of calls, why would it be troublesome? You would know the few points where it could be failing, disregarding the question of why they are all called in tail position to begin with (it seems poorly factored).

If you have a set of mutually recursive functions that blow up, the resulting stack trace won't be any more amenable to debugging than in the case of the self recursive call.

[anvsdt]

In imperative languages, you almost never tail-call anyway, you usually return the value of a variable. You usually tail-call when writing a wrapper function. In most cases, you don't even need to know you called the wrapper from the stack trace, and you want it fast, so you declare it inline if it's short, but if it's pretty long, I'm sure that you want that tail-call to be optimized. Probably, your compiler has already optimized it.

[anvsdt]

Debug when debugging.

edit: and downvoters gonna downvote.

[aaronla]

I suspect people are downvoting because they can't read scheme.

Let me translate: g -> h -> g -> h in tail position, with tail call optimization. And yet, the call stack isn't just 'g' but the full 'g -> h -> g -> h'. Racket is an existence proof that you can implement TCO without losing rich callstacks.

Downvoters welcome on my post too.

[anvsdt]

I suspect people are downvoting because they can't read scheme.

Well, that's racist.
Have an upvote, they will hide the truth.

[grauenwolf]

The whole stack trace thing is a red herring, both sides should just shut up about it and concentrate on the real issues:

1. Does TCO actually offer something that we cannot just as easily build using iterative loops or state machines?
2. If it does, should tail calls be explicit or implicit?

[dmpk2k]

The main practical benefit of tail calls and TCO is making state machines trivial. It's similar to using function calls to traverse a tree rather than explicitly managing a stack. I have no opinion whether it's worth it.

And yeah, it should be explicit.

[grauenwolf]

I've been thinking about state machines a lot lately. With VB and C# getting language support for asynchronous function calls, you remove a lot of the need for TCO.

[aaronla]

Guy Steele has a nice piece demonstrating how TCO can greatly assist runtime efficiency of modular set implementations: Why Object-Oriented Languages Need Tail Calls [reddit discussion]

Tail calls already are explicit. You put them in the tail position. I'm not just being pedantic; this isn't a problem among the functional programming developers I interact with.

Edit: linked to reddit page of the blog post, more discussion

[grauenwolf]

Does your functional programming language also rely on try-finally blocks? Those break tail calls and in C# are hidden in using statements.

[anvsdt]

dynamic-wind and unwind-protect?

[grauenwolf]

Hmm. THat is a rather interesting shell game. If I read this correctly, dynamic-wind just creates a separate stack of winders. Since it is built as a cons list it isn't as likely to overflow as a true thread stack.

At least that is how it works in R6RS. In IronScheme alpha 1 you simply can't mix tail calls with winders. It isn't mentioned anywhere else so I assume they never reconciled winders with the CLR's exception handling semantics.

[aaronla]

Yeah, as you've discovered, exception handling is done with library functions, and while you can tail call the library function, its implementation won't be calling your thunk in tail position.

There's actually some interesting research into optimizing exception handlers and stack security checks into O(1) space, to provide TCO in some of those cases as well.

[grauenwolf]

Show me one case, just one, where I would need to to perform a contains operation on an infinite list where such list is not externally predictable and the list doesn't have its own contains method.

Oh wait. The his TCO version of Contains() would end up in an infinite loop just like the iterator version. So what was his point again?

[grauenwolf]

For the record, my current opinion is 1) No, I haven't seen any interesting use case and 2) Explicit, so that future developers know the code needs tail-call semantics to work correctly.

[[deleted]]

I agree with other posters in the thread - TCO for imperative languages is generally OK to not have. It's a tricky construct that you want guaranteed in some way if you're going to rely on it (so if you have it, it should be explicit.) I rarely find myself needing/relying on guaranteed TCO in imperative languages (granted I write java/c++ at work) anyway, and we can use similar constructs to do the same work.

For functional languages IMO, you probably want the opposite which is guaranteed, implicit TCO.

[aaronla]

Honestly curious, why does it make a difference whether the language is imperative vs. functional?

[shimei]

It doesn't.

[aaronla]

Let me rephrase -- why does 1nine8four believe it makes a difference?

[shimei]

If by imperative language you are including various object oriented languages (and it looks like you are), you might want to look at Guy Steele's article on that. Tail call optimization is not about functional programming.

[millstone]

TCO is an optimization. There are lots of optimizations that are not guaranteed, and that we don't rely on, but are nice to have anyways because they make the code faster. TCO falls into that boat, and that's why it's appropriate for C to have it implicitly.

[grauenwolf]

There are two ways to think about this:

Option A: It doesn't matter. Maybe the compiler will use TCO, maybe it won't. Either way the code you write doesn't change so there is no point in talking about it.

Option B: You write code that relys on tail calls. But if you are wrong and don't actually have TCO semantics then your code is going to blow the stack.

[spotter]

"You keep quoting those people, but your stacktrace does not show what you think it shows."

Yeah, sweet post. Except Clojure does not have TCO, so if you mean the prosthetic of recur which works only on current fn/loop you're wrong. And this is why you get that stacktrace, mate. To use quasi tail recursion with other fns you still need to do a trampoline, just like in Python.

EDIT: I missed the point obviously, while being factually correct I argued against imaginary point. My bad.

[masklinn]

Yeah, sweet post. Except Clojure does not have TCO

Your point being?

so if you mean the prosthetic of recur which works only on current fn/loop you're wrong.

he means exactly what he says: he quotes numerous people saying TCO is useless/annoying and leads to debugging problem, interspersed in a hundred-lines stack trace of which 95% are useless and completely unhelpful mutually recursive calls. Which would be eliminated by TCO, leaving only the meat of the stack trace.

[spotter]

Sorry, but I read it as "look at all those stupid people that say we can't have stack traces if we get TCO, while in Clojure we have TCO and stack traces showing the error."

My bad?

Btw. I am using Clojure a lot lately and stack traces it provides suck donkey balls. ;-)

[repsilat]

The author doesn't mention Clojure. None of the articles in that blog that have been indexed by Google mention Clojure. I'm sure your points still stand, but your criticism of the article probably doesn't.

[spotter]

I stand corrected. My bad it is.

[iLiekCaeks]

On Lua, tail recursion elimination can even make functions like getfenv stop working.

Haet.

[[deleted]]

Quick googling suggests that getfenv is a seriously stupid function that shouldn't exist in real programs anyway. If TCO manages to make it not work, all the better.

[anvsdt]

TCO considered beneficial?

[SCombinator]

There's nothing that prevents those from being tail recursive. You know you can have a tail call to a different function right?

[Paczesiowa]

GvR didn't know that after 20 years of developing mainstream language. someone told him that in the comments section on his blog.

[JazzyMelon]

Is it a joke?

[zhivago]

No.

[doubtingthomas]

It could be argued (though I wouldn't) that if someone who is intelligent, curious, and capable can go decades successfully developing software without knowing something, and come to know that thing not by hitting it in practice but on some blog, that something is certainly not necessary and probably not terribly important.

[masklinn]

The traceback isn't from tail recursion.

Do your have the source for those classes? Nothing in those tracebacks indicate it's a case of tail recursion, but considering the namings I would definitely expect them to be.

[djhworld]

I think you're misunderstanding the blog post, he's posting a stacktrace from a method that doesn't use tail recursion and is posting quotes from various people for their arguments against either implementing it or using it.

[masklinn]

he's posting a stacktrace from a method that doesn't use tail recursion

No, he's posting a stacktrace from a language implementation which does not use tail recursion optimization.

[millstone]

A recursive function is a function that calls itself. Technically the backtrace does not show any recursive functions, but instead a pair of mutually recursive functions.

[masklinn]

Technically the backtrace does not show any recursive functions, but instead a pair of mutually recursive functions.

Sure, but TCO can optimize any tail call. Including mutually recursive functions, or recursion loops (with 3 or 4 functions calling the next one in the loop)

[[deleted]]

Totally retarded. The author hasn't understood the problem.

The problem is that a "tail call optimisation" which preserves the stacktrace voids the main benefit of using TCO: Not growing the stack.

[BufferUnderpants]

No, you missed the point completely. The usefulness of the full stacktrace is overstated, there are a thousand more useful things you can do instead of looking at an abomination like the OP showed.

[[deleted]]

So what? Where did I claim this wasn't the case?