Hacker News Reader

Comment by tsmarsh | Hacker News Reader

Clojure has recur, which is tail recursion that detects not being in the tail. I prefer that to implicit tails with quiet , expensive fails like scheme.

View on HN

Tail call optimization is more than optimized tail recursion.

Recur provides an explicit form of support for the latter, but not the former.

I wonder whether you could add a tail-call construct to Clojure, not just a tail-recursion construct. But I guess, to preserve JVM semantics, you'd need a trampoline or so.

There was an effort, in 2012, to create a generalized TCO in Clojure using CPS and trampolining. I don't remember why it wasn't fully pursued, but the JVM team is now talking about eventually fixing the core issue behind not supporting tail calls.

Clojure Conj 2012: http://youtu.be/RLqqGSthmC0

Source: https://github.com/cjfrisz/clojure-tco

I experimented with this too. It doesn't work out because you need to know at fn definition time and at the call site that you're using a non-standard calling convention. You can't rewrite all functions without a substantial performance overhead, so you need to be selective. Scala has a compiler plugin for type-directed CPS, but you have to annotate the crap out of your functions and things break down in a bad way for generic higher-order functions. If you wanted to take a real run at this in Clojure, you'd have to compile two versions of every function: the usual `invoke` methods plus an `invokeCPS` method with compiler-inserted call-site trampolining code. Then the programmer would still be saddled with ^:cps metadata or similar.

In practice recursion probably covers most of the cases where it matters. Corecursion could (if awkwardly) be converted into ordinary recursion.

It doesn't. Most of the advantage of tail calls over loops comes exactly from the fact that they work for all tail calls not just direct recursive calls. Examples: loops with a non-trivial iteration structure, programming in CPS, programming with monads, and doing state machines.

Corecursion doesn't mean what you think it means. You mean mutual recursion.

(read this with a mild trollface) Given functions f and g, it is possible to write them as the same function M. Supply an extra argument called "mode": if 0, then the function behaves like f, and if 1, then the function behaves like g. If you want to call f or g, call M with the "mode" argument as 0 or 1 respectively. If f and g take different numbers of arguments, let M take the larger number of arguments, and when you intend to call the function that takes fewer arguments, supply 0s for the extra args. This should indeed implement mutual recursion in terms of self-recursion.

The grandparent commenter did say "Corecursion could (if awkwardly) be converted into ordinary recursion", which I would say is technically correct, which some say is the best kind of correct. (Perhaps he has a somewhat less awkward scheme in mind.)

You seem to be talking about mutual recursion.

http://en.wikipedia.org/wiki/Corecursion

http://en.wikipedia.org/wiki/Mutual_recursion

It occurs to me that the existence (and nature) of "coroutines" probably primes this mistake.

No, it doesn't. Think about composition and partial application.

Reply on news.ycombinator.com