Hacker News Reader

Clojure does actually support TCO, it doesn't support automatic TCO because of the JVM limitations. And after using explicit TCO calls in clojure for a while I actually prefer it now over automatic TCO. Because I can clearly see from reading my code where tail calls are optimized, and where they build up stack. I don't have to try and work out if the recursive call is in the tail position. It's all explicit.

For mutually recursive TCO there's `trampoline`

https://clojuredocs.org/clojure.core/trampoline

Agreed that explicit is better than implicit but I can't imagine when you might want tail calls to build up stack. And if you do have a use case for it in mind, wouldn't you want to be explicit about that and have TCO be the default?

Well that (default being TCO, and explicitly declaring a stack call) would mean every normal function call (the vast majority) would need to be explicitly declared (call func args...), and the implicit case would need to blow up everywhere it's invoked in a non-tail position.

What I was getting at is: in an automatic TCO language you don't actually know if the call is optimised or not. You might think it's optimised, but it isn't, because it's not in the tail position. You don't find this out until one day in production the stack explodes. The only way to know if it's optimised is to determine if it is in the tail position. That sometimes is straight forwards, but sometimes requires careful thought. It is certainly not always obvious.

Additionally, another coder can come along and break your tail position. You've gone "return func()" and it's TCO and then later someone changes it to "return 1 + func()" and now the call to func is not TCO, but there is no warning and no obvious outward signs that this has changed.

In the explicit TCO of clojure, if the second programmer adds the extension the compiler will explode with something like "recur not in tail position", immediately informing you that this has happened, and then you may either refactor to put it back in the tail position, or change it to a full stack function call once you determine that building up stack is ok in this case.

Now I think loop/recur was implemented in Clojure as a work around the JVM limitations, but in doing so I think Hickey stumbled onto a really great new syntactic formulation for TCO. Explicitly declared TCO. I like it.

This is why I like Scala's approach so much.

It will TCO automatically. If you want to make sure you haven't made a mistake, simply add the @tailrec annotation, and the compiler will give you an error if it can't TCO.

That sounds pretty good! I will check that out.

Clojure's loop/recur is pretty much a degenerate version of Scheme's named let, which has been part of Scheme since long before Clojure was a thing:

  (define (sum xs)
    (let loop ((acc 0)
               (xs xs))
      (if (null? xs)
        acc
        (loop (+ acc (car xs)) (cdr xs)))))

It's often used in Scheme for iteration, including cases where you would otherwise need to define a helper function to implement an iterative (tail-recursive) version of a function, as I did with sum above.

The named let construct is more general than loop/recur, since you can supply a name and properly nest the forms.

You probably wouldn't ever want to not optimize, but the point is that, by being explicit, you know what parts are and which are not.

If you think about it, you can't really do the opposite, because it is not possible to TCO every recursive calls.

I want useful stack traces by default - the cases where I most need a stack trace are usually precisely the cases where I didn't think much about that function when writing it.

TCO is possible in JVM but not in Java. Clojure is just Java library and share all Java problems like TCO, Class sizes or inline limits.

I no longer believe in transpiration or hosted languages. Proper language have LLVM backend. Look at Rust, Swift, Crystal, this is future.

Or you use a VM that was build for that cough cough erlang cough cough

But Clojure and Scala choose to sell theirs souls for Java popularity.

Is "selling their souls" really what they're doing? When writing a new language shouldn't one consider its adoption by the community to be a key part of its success? The purist would say all that matters is sticking to a core philosophy while the pragmatist is willing to make some concessions for long-term viability and adoption so long as it doesn't completely undermine the purpose of the language. Essentially, don't you think Hickey, after several failed attempts at writing new programming languages, had given quite a bit of thought about what makes a language successful (and useful) before making the decision to make Clojure JVM based? Of course he did; even explaining the factors that went into the decision. That's not "selling your soul", it's a practical decision that comes from a lifetime of experience.

Because Clojure is not new language it is another Lisp. Language adoption should not be primary driver.

Clojure is more Java based than JVM based. This is main issue. It inherits all Java limitations and share problems inherited from Lisp world. https://github.com/clojure/clojure/blob/master/src/jvm/cloju...

By selling soul I mean: 1. Clojure will forever have ugly/broken stacktraces. 2. Inline/Class limits on JVM will not disappear. 3. Half of Clojure libraries are just wrappers. 4. Lack of TCO and other recursions optimisation. 5. Performance will be always worse than Java 6. Type system with garbage in -> garbage out approach

Rust is a systems programming language. What makes Swift and Crystal more "proper" than JVM languages?

LLVM is "proper" back-end for code generation that produce native executable optimized for any platform.

JVM execute bytecode in Java Virtual Machine. JVM abstract your hardware and have specific runtime that needs to be present.

LLVM is superior model because its avoid additional compilation and can in theory provide much better performance.

You express very strong opinions about Clojure and the JVM in particular, in comparison to the LLVM. Would you mind sharing some particulars of your experience with the two and what domain you work in?

Actually, the JVM can in theory provide much better performance, because code is specialized as it runs. Statically compiled code must be produced to handle the worst-case usage.

As for the runtime being present, it's more of a packaging issue. A language like Go has a runtime that's similar to Java's (except it doesn't JIT-compile), but it is statically linked with your binary. This can be done in Java, too.

I must say that it doesn't seem like you're very knowledgeable when it comes to compilation techniques. LLVM and the JVM do make different tradeoffs, but they're not at all the ones you describe.

> JVM can in theory provide much better performance, because code is specialized as it runs.

Only better if you don't include the runtime compiling (start-up time).

The JVM is usually used for long-running applications so the warmup (not start-up, which is 60ms) time doesn't matter. It's not a great choice for short-lived command-line apps.

The JVM is usually used for long-running application because the warmup is so slow. Were it not so slow, it would be used for things other than servers.

Maybe, but most large, "serious" software is long-running anyway. There is interesting work on reducing warmup (because some banks doing HFT are willing to pay Oracle to do that), but there's not much interest. Not all niches of the software world are equally interesting, and besides, there are some incumbents that are hard to unseat in those smaller niches so it's questionable how much effort should be put into competing in niches that are either small, have well-entrenched incumbents, or both.

> Without TCO, you can't fully leverage functional composition and immutable data structures

Look, I like tail calls as much as any language geek, but this statement is just plain silly. The idea that TCO is needed to "fully" leverage anything is silly. Never mind that necessitating so-called full leverage is pointless, as even supposedly partially leveraged anything can be useful. In the case of Clojure, function composition and immutable data structures are highly leveraged and, after learning the seq abstraction and lib functions, you won't even miss tail calls unless you try to write a direct-style interpreter for a language that supports recursion.

Perhaps TCO is not required for idiomatic Clojure, but for advanced functional programming using e.g. Monads or CPS, TCO is absolutely necessary in practice.

Clojure has TCO, though. This is what recur is for.

No Clojure does not have TCO, due to the JVM. It allows you to manually optimise self-recursion via recur. This is not enough for many advanced FP techniques, such as CPS. For example, using CPS and TCO, I can traverse a tree in constant stack space.

I agree with the parent that lack of TCO in Clojure is probably not an issue for most.

If you are traversing a tree in constant stack space, the closures your continuations are holding on to must be O(ln) in space and representing what would have been on the stack, right?

Yes absolutely, I'd be trading stack for heap.

The fact that monads are not popular in Clojure is a good thing, IMHO. Besides, test.check and clojure.spec get by just fine with macros for generator monads. It's not quite perfect, and everyone would like proper tail calls, but it's far from an impediment for the overwhelming majority of tasks tackled with Clojure.

I have already stated that it is quite possibly not a problem for Clojure, although this hasn't stopped all the downvotes I keep getting (which doesn't leave me with a good impression of Clojure users). My point is that, despite the claims of the parent post, TCO is needed for many advanced functional programming techniques.

You're being down voted because you keep repeating a claim without evidence despite both evidence to the contrary and acknowledgement of the utility of tail calls.

No, I have been disputing the following parent claim:

> The idea that TCO is needed to "fully" leverage anything is silly.

I provided two examples, monads and CPS transforms, which require TCO to fully leverage in a strict language. But really any example where functions are dyamically composed as a pipeline needs TCO to avoid leaking stack. Your examples of a couple of test libraries in Clojure hardly constitute evidence that TCO is of limited utility.

> any example where functions are dyamically composed as a pipeline needs TCO to avoid leaking stack

Sure, but in the rare case that this is a problem, you can trivially workaround it:

    (reduce (fn [acc f] (f acc)) init [f1 f2 f3])

This approach may not match the Haskell ideal of FP, but it's actually got many significant advantages. Frequently, programming with data structures is _better_ than programming with function composition. For example, you may choose to do something like this:

    (reduce (fn [acc f] (println "executing" f) (f acc)) init [#'f1 #'f2 #'f3])

Where this is now a pipeline with logging of the stages. You can't do that if you prematurely select function composition as your primary way to structure computations.

The Haskell research community is in the process of undoing this brain damage on the monad front by embracing extensible effects, free(-er) monads, "reflection without remorse", effect interpreters, etc.

Once you need any sort of symbolic reasoning, you drop opaque composition and work with data. This is true in every language, FP or not. People tend to do exactly the right thing already: abandon function combinators and write interpreters over data structures.

I disagree it is always trivial to work around. Typically trampolines are used, but these have a large efficiency hit, up to 1000 times slower. Not a problem in many scenarios, but clearly not good for e.g. a concurrency monad. For your pipeline example, you gave a trivial statically determined one. Try an example where each function decides the transistion (tail calls the next one). This is of course also what my Monad and CPS examples in essence do.

Regarding your comments on replacing function composition with data structures. In essence, this is what trampolining does. But it does have a performance cost and is not appropriate in all cases. IIRC correctly the performance of "Extensible Effects" is still an outstanding issue. Incidently, the primary author of that work, Oleg K, has published a lot of work in which he seeks to avoid intermediate data with "finally tagless".

> The idea that TCO is needed to "fully" leverage anything is silly.

Functional programming relies completely on recursive functions. You just can't do "full" FP without tail call optimizations.

Now, I do side with the other poster up there that is talking about jumps. You don't even need jumps actually, you can use inlining and loops too, but they do make the compiler's life easier.

I think that Clojure's success is proof positive that explicit tail recursion and lazy sequences is sufficient to do meaningful FP in the absence of proper tail calls. However, even if you insist that it is somehow not "full", who cares? Clojure is about practicality, not appeasing some platonic ideals. And I say this as some one who would very much appreciate having proper tail calls.

Of course, having lazy sequences and functions for manipulating them is better than not having them.

Yet that's such a small part of what FP has to offer that it isn't funny.

¯\_(ツ)_/¯

Extremist views are not particularly useful in engineering, despite their utility is science.

Lua isn't homoiconic and doesn't have LISP style macros; yes there's this or that patch available, but like all other attempts at implementing macros in other languages, it never comes close to being as good as what LISP does naturally, because in LISP code is data literally.

In other words, Lua has nothing to do with LISP, except that it's your favorite, hence I don't understand this comment.

As for TCO, it's regrettable that the JVM runtime doesn't provide support, however you can work around it by implementing trampolines, which is how developers of Scala, Clojure and PureScript have managed to live. For example you can implement a fairly efficient and lazy IO type, like the one in Haskell, which then gives you memory-safe tail-calls for free. Examples include the Free monad or the Task type from Scala.

The only downside of this approach is that it involves effectively building your own call-stack and keeping it in heap, which stresses the garbage collector and implies some indirection. But then again, if you'll look at the TCO performance of platforms supporting it (e.g. .NET, ES6), TCO calls have a performance penalty which can be quite significant, so I'm not sure that you'd gain much in terms of performance.

And if you measure the performance of FP-heavy Scala and Clojure, you'll see that it's not bad compared with Scheme implementations or Haskell, in spite of trampolines being used for tail-calls.

You have listed the reasons why I wrote a language that's a superset of Lua and Lisp, allowing lisp style macros to manipulate lua code as data. http://github.com/meric/l2l

I'm getting a bit tired of the "we don't have TCO because the JVM doesn't support it" argument. You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps. That is all a TCO is. It turns a recursive construct into a looping construct. And it's a really simple optimization - just update the local arguments to their new value and jump back to the start of the function instead of a call + return.

No, Clojure doesn't have TCO because of a design decision. We can discuss the rationale behind that decision and the merits of it, but claiming it has anything to do with the JVM is dishonest.

> You know what doesn't have a tail-call construct either? Every hardware architecture in existence. You know what they have though? They have jumps.

Guess what the JVM doesn't have. Remember also that the JVM was originally designed for running untrusted bytecode, so it doesn't generally let code directly manipulate the call stack.

> Guess what the JVM doesn't have.

https://docs.oracle.com/javase/specs/jvms/se7/html/jvms-6.ht...

> so it doesn't generally let code directly manipulate the call stack.

You are doing something wrong if you need to manipulate the call stack to do a tail call. You just have to update the local arguments and jump back to the start of the function. It is literally just turning the call into a loop.

That works for tail recursive functions, but not tail calls.

TCO works for all tail calls, not just the recursive ones, so that jump would be to another function's body. The current stack frame may not have enough space for the new function's.

It's true, but you probably don't want TCO for all tail calls since you lose information in stack traces.

As long as you have control over all the code generated you can in principle compile multiple functions into a single one and just add some stubs for interop purposes. This of course complicates how you track function pointers (or equivalently) and may have some overhead.

Still the cases where you can use recur today could be done automatically by the compiler without much trouble.

Good point!

One worry I have about automatic TCO where recur/loop currently is used is with Lisp's dynamic nature. What happens to everyone who has a reference to the fn when you redefine its def?

You're basically switching (defn f [] (recur [] (loop))) to (defn f [] (f)). What if I do (def g f) and then (def f +)? Will the original f now recur into + when I call (g)? If it still calls into the original f then that creates a mismatch between reloading normal and recur'd functions adding complexity to a language striving for simplicity.

I'm probably overthinking it :)

If you want late binding at the call site it's probably unavoidable to have some extra complexity anyways, what if I changed f into something that wasn't callable?

However Clojure binds at the definition time, e.g.

    > (defn f [] 42)
    #'sandbox9516/f
    > (f)
    42
    > (def g f)
    #'sandbox9516/g
    > (g)
    42
    > (def f 1337)
    #'sandbox9516/f
    > (g)
    42
    > (f)
    java.lang.ClassCastException: java.lang.Long cannot be cast to clojure.lang.IFn

That's because defn binds f to the _value_ of the function, while (f) binds to the _variable_.

  > (defn f [] (f))
  #'sandbox9672/f
  > (def g f)
  #'sandbox9672/g
  > (def f 42)
  #'sandbox9672/f
  > (g)
  java.lang.ClassCastException: java.lang.Long cannot be cast to clojure.lang.IFn

It's not that dishonest. If the JVM supported TCO natively then it would be a no-brainer for Clojure. The alternative is to give up on seamless interop between Clojure and Java libraries.

> The alternative is to give up on seamless interop between Clojure and Java libraries.

Why? The only issue I can see is that you can't tail call to java code, but that would only be a problem if you are trying to do mutual recursion involving both Clojure and Java code.

For multiple Clojure functions with mutual recursion you could just compile all of them into a single function with a state argument to select which function to go to, and then add stub methods that just calls into the combined function with the correct value for the state argument for interop with java. The only artifact of that would be an extra method with a synthetic name in the stack trace.

Stubs == seams, IMO. Self calls are certainly not a problem, as you pointed out, but in that case recur is a pretty elegant way of supporting that while not making Clojure appear to support something it doesn't.

EDIT: Also what you suggest would imply huge changes to the way code is evaluated in Clojure - for example, I can create functions in the REPL and they work the same way as reading functions out of a file. How would that work in your scenario? I think every function would actually have to have a stub not just the mutually recursive ones because you might not know until later which functions to combine.

The ML family of languages and the Lisp one, with exception of Scheme, don't require TCO.

So none of them are worthy of being FP languages according to you.

I think you'll find that you can rely on TCO in all of the languages you mention. Certainly Scheme, Racket and most ML languages and their implementations. Common Lisp does not require it but the most popular implementations (CMUCL, SBCL, CCL, Allegro, LispWorks) all provide full TCO.

I think pjmlp knows about this. The important word was "require", which makes a lot of difference. If you don't guarantee TCO at the language level, you can afford to emit code that performs other useful things (like debugging) while remaining conform to the language specification.

Then your code will become implementation dependent and fail spectacularly when trying to port it.

SBCL does TCE on some circumstances/optimization levels, not on every instance. Nor is it portable nor idiomatic CL. (Although I certainly write code that depends on it sometimes)

>> ...Only Perl 6 comes close to the ease of writing parsers with Lua+LPeg.

I would argue that it doesn't get any easier than using Rebol/Red parse dialect - http://blog.hostilefork.com/why-rebol-red-parse-cool/

You can use a small patch to add the remaining power of call/cc to Lua. I've thought I would need to do this for a game, because I was using both "state stored in execution contexts" and "speculative execution of the game's update() function while waiting for remote players' inputs". I didn't end up making that game though :(

It is not a limitation of Clojure but a limitation of the JVM. And you can use the recur keyword to actually do TCO.

Recur only handles a limited case of tail call elimination, not when the function calls another function on the tail position. Also you can implement TCE on the JVM Kawa Scheme does, just not efficiently. It is a limitation resulting from the design decision of Clojure.