Hacker News Reader

Comment by chongli | Hacker News Reader

I hate to be pedantic here but I see the term TCO thrown around all the time. The Scheme standard requires that unbounded tail call functions can run in constant space.

This is a semantic difference, not an optimization. Turning off optimizations should never cause your program to crash.

View on HN

I wrote TCO in the title because with "proper tail calls" the title exceeded the allowed limit on hacker news! Moreover most people will know the term TCO and less the more precise term proper tail calls. You are of course correct that tail calls are a required aspect of the Scheme specification even though many implementations that call themselves "Scheme" don't implement this fully.

If we're being pedantic, it's really a problem of degrees - any space-based optimization, like the padding and ordering of struct members, could cause a program to crash by running out of stack or heap. In that case, turning off (or on!) optimizations may cause a program to crash.

Let's be extra super pedantic.

If (let x () (x)) is allowed to take more than a constant amount of space, then for any finite memory there is always some finite runtime after which the program will exhaust the memory.

With proper tail calls, there is always some finite memory above which the program will not consume, even given an arbitrarily long runtime.

So, while it is a problem of degrees, one degree is infinite while the other is finite.

Reply on news.ycombinator.com