News for hackers. Stuff that matters.
Re:How recursion got into programming: a comedy of errors by supahfly_remix on Wednesday July 23, 2014 @07:28AM (#8073749)
Oh, I definitely see the elegance of expression programs or concepts recursively.

Is TCO used in C++? I've only ever seen it mentioned in reference to Scheme and Haskell. It's a compiler optimization, so it would be transparent to the programmer, right?

Re:How recursion got into programming: a comedy of errors by sunfish on Wednesday July 23, 2014 @09:01AM (#8074095)
Most C++ compilers perform TCO when convenient, but the C++ language doesn't guarantee that TCO will be done, so it's unwise to write code that depends on it. In practice, every compiler decides when to do TCO in its own way. Also, it's useful to be able to run code with optimization disabled. Also, it's easy to accidentally have a variable that needs a destructor call which makes TCO impossible. This is all in contrast to Scheme, which does give you a guarantee, and which makes it easy.
Re:How recursion got into programming: a comedy of errors by jejones3141 on Wednesday July 23, 2014 @08:40AM (#8074012)
It's implementation-dependent; a particular compiler may do it, or may not. Scheme, OTOH, has it written in the spec--you WILL do tail call optimization, so programmers can count on it.
Re:How recursion got into programming: a comedy of errors by actsasbuffoon on Wednesday July 23, 2014 @07:39AM (#8073786)
TCO is available in plenty of other languages as well. Scala, Clojure, Erlang, and Elixir support it out of the box. Ruby has a VM setting for it, and there was a proposal to add it to JavaScript. I'm sure there are plenty of others.
Re:How recursion got into programming: a comedy of errors by lostcolony on Wednesday July 23, 2014 @09:56AM (#8074355)
Per ch4s3's comment on Clojure, Scala also does not have TCO, at least, last I checked. The JVM doesn't allow it. It has a specialized handling of functions that call themselves, which it can optimize, but A that calls B that calls A that etc is not (nor, in the more general case where any function that ends with a function is removed from the stack).
Re:How recursion got into programming: a comedy of errors by pjmlp on Thursday July 24, 2014 @02:41AM (#8078415)
Yes it does.

That is an implementation detail. It doesn't matter if it is does at compiler or whatever runtime is targeted.

This is called lowering in compiler design speak.

Re:How recursion got into programming: a comedy of errors by lostcolony on Friday July 25, 2014 @03:58PM (#8087306)
Umm...yes, it does matter.

Closures? Can't be optimized. Polymorphic method? Can't be optimized (even if every implementation is tail recursive).

This is more than an implementation detail, it actively influences the way you write your code.

And Scala -doesn't- optimize A calls B calls A etc cases. It requires the developer to explicitly make use of scala.util.control.TailCalls. See http://www.scala-lang.org/api/2.11.2/index.html#scala.util.c... and associated white paper.

What Scala gives you is that if A calls A (calls A calls A), and is tail recursive, and A can not be overridden, it will optimize it.

Re:How recursion got into programming: a comedy of errors by TickleSteve on Wednesday July 23, 2014 @08:10AM (#8073884)
Just to be picky.... Clojure doesn't have TCO, it has 'recur' as a substitute instead.
Re:How recursion got into programming: a comedy of errors by ch4s3 on Wednesday July 23, 2014 @08:44AM (#8074027)
To add a finer point, Clojure doesn't have TCO per se because the JVM doesn't have tco. Recur optimizes the special case of "tail-recursive self-call and not the generalized tail call."[0] That is to say when the tail of A calls A, but not when A calls B which calls A.

[0] "The Joy of Clojure," Fogus and Houser

Re:How recursion got into programming: a comedy of errors by noblethrasher on Wednesday July 23, 2014 @08:51AM (#8074058)
Interestingly, the 64bit CLR JIT does TCO while the 32 bit variety does not.
Re:How recursion got into programming: a comedy of errors by kvb on Wednesday July 23, 2014 @09:56AM (#8074360)
That's not accurate. In fact, in the .NET 2.0 timeframe the opposite was the case (the 64-bit JIT would fail to honor the IL tail. prefix in many cases, though it would also make tail calls in other cases even when the prefix wasn't applied)[1]. But as of .NET 4.0, both platforms honor the tail. prefix except in a very limited set of circumstances[2] (e.g. calls from untrusted code to trusted code).

As far as I know, F# is the only reasonably popular .NET language to emit the tail. prefix, though[3].

[1] http://blogs.msdn.com/b/davbr/archive/2007/06/20/tail-call-j...

[2] http://blogs.msdn.com/b/clrcodegeneration/archive/2009/05/11...

[3] http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-c...

Re:How recursion got into programming: a comedy of errors by supahfly_remix on Wednesday July 23, 2014 @07:44AM (#8073800)
Thanks, that's good to know.
Re:How recursion got into programming: a comedy of errors by sjolsen on Wednesday July 23, 2014 @10:33AM (#8074558)
The problem with TCO in C++ is destructors; unless you're using a very limited set of types, they all but guarantee you're going to have code to execute after returning from what would otherwise be a tail call.
Re:How recursion got into programming: a comedy of errors by skittles on Wednesday July 23, 2014 @09:25AM (#8074218)
TCO isn't really transparent to the programmer. Some recursive calls cannot be optimized, so the programmer has to know how to write recursive functions that can be.
Re:How recursion got into programming: a comedy of errors by supergauntlet on Wednesday July 23, 2014 @07:32AM (#8073759)
C++ optimizes only with -O2 or /O2 passed to the compiler (for GCC and MSVC++, not sure about Clang).
Re:How recursion got into programming: a comedy of errors by pflanze on Wednesday July 23, 2014 @08:59AM (#8074083)
You can't count on it in the general case even with gcc (even when taking care to heed the restrictions like not passing pointers to data on the stack, and putting all functions into the same compilation unit). I did tests a couple years ago where it would compile up to about a handful of mutually recursive functions with TCO, then when you added one more, it would disable TCO. I guess because some algorithm will stop analyzing the call graph past a certain mark and then disallow TCO from being applied.
Re:How recursion got into programming: a comedy of errors by pjmlp on Thursday July 24, 2014 @02:43AM (#8078421)
If it isn't on the standard, anything goes.

There are much more compilers out there than those three.