Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Tail-call optimization in C is relatively recent (2025)

lwn.net

Post reply on HN
Print view View original

11–20 of 126 posts

Re: Tail-call optimization in C is relatively recent (2025)

#11

Post by pfdietz »

guenthert wrote: post #9
pfdietz wrote: post #3

Earlier quoted context omitted.

Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.

Only if they are using an insufficiently smart compiler. SBCL handles TCO just fine, as do a number of other implementations, see : https://0branch.com/notes/tco-cl.html

Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO.

Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or map to go along a list.

Re: Tail-call optimization in C is relatively recent (2025)

#13

Post by groundzeros2015 »

mmsc wrote: post #2

and TCO was added then removed from js! https://stackoverflow.com/a/54721813 This leads to fun stack-overflow bugs too in a lot of js code (one solution is to flatten: https://joshua.hu/javascript-infinite-tail-call-recursion-st... )

Js really should have it. I think the shift in style from functional and manual prototype chains to Java classes is quite disappointing.

Re: Tail-call optimization in C is relatively recent (2025)

#14

Post by guenthert »

pfdietz wrote: post #11
guenthert wrote: post #9

Earlier quoted context omitted.

Only if they are using an insufficiently smart compiler. SBCL handles TCO just fine, as do a number of other implementations, see : https://0branch.com/notes/tco-cl.html

Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO. Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or map to go along a list.

> Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO.

Presumably one intends to debug the code, when setting (debug 3). Then it'll be helpful to see the stack, no?

> Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or map to go along a list.

Not going to argue with seasoned lispers here, but IMHO recursive code makes most sense when accessing recursive data structures.

Re: Tail-call optimization in C is relatively recent (2025)

#15

Post by pjmlp »

kenjin4096 wrote: post #4

I think Anton is replying to me in that LWN article IIRC. I personally didn't know C only had tail calls that late and learnt something new there! On the other hand, I am pretty new to the compiler space myself, and I count early 2000s as a pretty long time ago, though again it is not that far back considering how long other language implementations had tail calls like in ML or variants since 1980-90s.

It still doesn't, this is a compiler specific language extension.

You won't find anything on ISO/IEC 9899:2024 about tail calls, like it happens on Scheme.

https://www.open-std.org/jtc1/sc22/wg14/www/docs/n3220.pdf

Section 3.5 of R7RS.

https://standards.scheme.org/official/r7rs.pdf

Re: Tail-call optimization in C is relatively recent (2025)

#16

Post by pjmlp »

pfdietz wrote: post #3
mmsc wrote: post #2

and TCO was added then removed from js! https://stackoverflow.com/a/54721813 This leads to fun stack-overflow bugs too in a lot of js code (one solution is to flatten: https://joshua.hu/javascript-infinite-tail-call-recursion-st... )

Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.

Mostly because they forget Scheme is one of the few languages where TCO is part of the language standard, making it a required feature for any compliant implementation.

This has always been an issue regarding TCO support across programming languages.

Re: Tail-call optimization in C is relatively recent (2025)

#17

Post by swiftcoder »

> In 2001 Mark Probst implemented tail-call optimization in GCC

MSVC didn't add tail-call optimisation until sometime in the 2010s, IIRC.

I distinctly remember sending a tail-recursive C++ program to someone who developed on Windows, and it crashing, in the late mid-to-late 2000s.

Re: Tail-call optimization in C is relatively recent (2025)

#18

Post by tialaramex »

StilesCrisis wrote: post #8
tialaramex wrote: post #7

Earlier quoted context omitted.

This footgun is the reason I'm so enthusiastic about the Rust `become` keyword. This proposal would give Rust a specific keyword which says that you intend TCO and so two things happen: 1. The compiler goes to more length to deliver TCO even where it wouldn't "just work" and 2. If it cannot deliver TCO your code doesn't compile, because you asked for TCO.

Sounds like clang::must_tail?

I am not a Clang expert, but first, obviously that's a C++ attribute and so while Clang can decide what it means in Clang in the programming language itself it has no semantic weight because the ISO document says attributes are always ignorable.

Secondly however in these languages you often won't naively get TCO because you have at least one local variable which C++ would say has a "non-trivial destructor" or Rust would say "implements Drop". These both mean that naively the "tail call" wasn't actually the last thing to happen, the destructor / Drop::drop happen at the end of the function, after the tail call.

The proposed become keyword tries to core::mem::drop any such variables, if it succeeds now that tail call is last and we can do TCO, if it fails [e.g. because the variables it wants to drop are needed for the tail call] we can diagnose the problem. I believe the Clang attribute doesn't have this behaviour.

Re: Tail-call optimization in C is relatively recent (2025)

#19

Post by pfdietz »

guenthert wrote: post #14
pfdietz wrote: post #11

Earlier quoted context omitted.

Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO. Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or map to go along a list.

> Even SBCL doesn't do TCO at all times. Compiling at (debug 3) means no TCO. Presumably one intends to debug the code, when setting (debug 3). Then it'll be helpful to see the stack, no? > Another related footgun is deep recursion of other kinds, for example when recursively traversing down lists. For long lists it's easy to exceed the stack size limit. The common idiom is to recur on list elements, but iterate or m…

One place where this shows up is in parse trees. The grammar for a list of things may involve productions that look like list constructors. This, directly translated into a data structure, would give a very long chain of parse tree nodes dangling off to the right. It's a recursive data structure, but a very deep one for large lists, and traversing it recursively can use a lot of stack.

This can also be seen as an argument against building parse trees that way. Instead, have a node with an unbounded number of children, the elements of the list.

Re: Tail-call optimization in C is relatively recent (2025)

#20

Post by pfdietz »

pjmlp wrote: post #16
pfdietz wrote: post #3

Earlier quoted context omitted.

Lack of TCO is also a common footgun for Scheme programmers using Common Lisp.

Mostly because they forget Scheme is one of the few languages where TCO is part of the language standard, making it a required feature for any compliant implementation. This has always been an issue regarding TCO support across programming languages.

Well, and also because of the "I've been told in Scheme you should do it this way, so by gum I'm going to do it this way!"
Post reply on HN