Hacker News new | past | comments | ask | show | jobs | submit login

Clojure has both recur and trampoline which handle tail calls (in general not just with loop) and trampoline for corecursion:

recur:

  (defn factorial
  ([n]
    (factorial n 1))
  ([n acc]
    (if  (= n 0)  acc
    (recur (dec n) (* acc n)))))
trampoline:

  (declare is-even?)

  (defn is-odd? [n]
    (if (zero? n)
      false
      #(is-even? (dec n))))

  (defn is-even? [n]
    (if (zero? n)
      true
      #(is-odd? (dec n))))

  (trampoline (is-odd? 10000))



Yep, and the same can be implemented in any language that supports functions-as-objects (for example, javascript).

It's a practical solution/workaround, but isn't quite composable/generalizable as first-class support for TCO (unless the community is willing to follow some convention like "TCO-like behavior is a 'good thing' and so libraries should try to support and interface compatible with `trampoline`".

This is a little bit like `function` / yield in newer versions of Javascript. It's not TCO, but it is a strong community convention (with the assist of special syntax to enforce the semantic).

Clojure is a great example of how practical/tasteful decisions by language author can create re-usable abstractions that are really powerful (even while at the same time working around limitations of the underlying technology).

Some might also argue that TCO is "bad" because it's less debuggable (e.g. when an exception is thrown, the stack trace is gone). We can see the same phenomena with non-blocking IO, for example. So maybe it's a Good Thing to have "less general" semantics in a language (e.g. function, trampoline, and loop/recur may be good-enough while at the same time preserving debuggability).

There are always tradeoffs. What's nice about general TCO is that the composibility of unrelated libraries/DSLs is more probable whereas with conventions like trampoline, DSL/library authors need to understand the advantages and design the DSL/library in a compatible way in advance. As Clojure shows with lazy sequences, this can absolutely work given enough community awareness of the convention.


Another thing to mention: having guarantee of TCO supports higher-level control-flow abstractions (capturing continuations), which is also an interesting outcome...




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: