Hacker News Reader

Comment by Copenjin | Hacker News Reader

For those wondering about the "tail call" part that would be more interesting for Clojure than fibers:

  As adding the ability to manipulate call stacks to the JVM will undoubtedly be required, it is also the goal of this project to add an even lighter-weight construct that will allow unwinding the stack to some point and then invoke a  method with given arguments (basically, a generalization of efficient tail-calls). We will call that feature unwind-and-invoke, or UAI.

  It is not the goal of this project to add an automatic tail-call optimization to the JVM.

[1] https://cr.openjdk.java.net/~rpressler/loom/Loom-Proposal.ht...

View on HN

> It is not the goal of this project to add an automatic tail-call optimization to the JVM.

Wait what? Are we getting TCO or not with Loom?

One issue to implement TCO is that the "security model"/circus of Java is based on the stack frames, so you can not remove stack frames without getting into trouble.

The security manager has to be removed first [1]

[1] https://openjdk.java.net/jeps/411

I interpret this as "we will add a primitive that will allow you to implement TCO yourself (and more), but the behavior of existing java or byte code won't change, and the stack will continue to grow, even if a call occurs in tail position". Presumably because it's hard to impossible to retrofit TCO without changing observable behavior.

Serious question, isn't that just a while/for/do loop? If people want TCO then... just write a loop, surely? I must be missing something.

You are -- non-self tail-calls. If you have mutually tail-recursive functions, say f1, f2, ..., f_n you have two problems without TCO:

1. There is no way to rewrite this into loops by just modifying the insides of these functions.

2. The remedy, which is to transform these functions and everything that calls them into a giant loop causes lots of problems:

The code will become utterly unreadable (if you do this transform manually).

Modularity is completely broken and there's no sane way to expose these functions individually to external callers.

Also, even if you don't care about either of the above: your compiler's optimizer will probably choke on it (https://blog.reverberate.org/2021/04/21/musttail-efficient-i...).

Well, good points but I was rather thinking the compiler should do it as an option.

Of lesser note, I don't believe I've ever come across mutually tail recursive functions, or the need for them, and although that may reflect my lack of experience in some areas, I guess it's not at all common? Maybe in the haskell world perhaps.

They make state machines leagues easier to reason about. Each state is its own function, and you tail-call to the next state (and pass along only the data it relies on, if you're doing things functionally).

Err, goto?

I'll read Steele's paper but introducing complexity only to struggle to delete that complexity is a strange approach

All flow control ultimately boils down to `goto`; it's how we crystallize particular usage patterns that makes it safer. Importantly, optimizing tail calls doesn't change the fact that you could always call another function before you return; you just risked blowing the stack.

I find that recursive solutions are often easier to understand and change than iterative solutions, especially because you need less incidental state (and you can manage the state you have more cleanly), so I'm not sure what you mean by "introducing complexity only to struggle to delete that complexity". That would more aptly describe my experience with writing iterative versions of naturally recursive algorithms.

(I think you may have mistaken me for someone else; I didn't recommend Steele's paper.)

Steele's paper was mentioned in the earlier link.

If goto is easily available in the high level language then creating a state machine is trivial I guess. If it's not then the compiler should be able to do TCO with jumps/gotos in the output asm or transpiled code (IIRC Bison's output uses gotos even though the input yacc rules clearly have none).

I continue to feel I'm missing something vital.

> If goto is easily available in the high level language then creating a state machine is trivial I guess.

It's still painful, because whichever state you're in probably cares about different data. Some data only needs to exist during some states. Factoring states into separate functions means each gets its own scope, and can explicitly pass only data needed for the next state forward.

> If it's not then the compiler should be able to do TCO with jumps/gotos in the output asm or transpiled code

It's nice to be able to indicate explicitly to the compiler (and other developers!) that you expect tail calls to be optimized, rather than crossing your fingers and hoping that nobody else comes along later and accidentally adds something after the call. Scala optimizes tail recursion by default, but it also has a `tailrec` annotation that causes the compiler to throw an error if it isn't able to respect that intent.

That's helpful, thanks!

Reminds me of a description of continuations as "gotos with parameters" which seems to be what you sort of want - I'll do some reading. Appreciated.

> I don't believe I've ever come across mutually tail recursive functions, or the need for them

Well, had you read the link I posted in my reply to your question, you would have ;) Anyway, there are a some useful things that are much harder to do pleasantly and efficiently without it.

Tail-call optimisation on the JVM is already somewhat supported with an annotation / keyword (depending on language). My understanding is that the project will improve the current implementation, but you'll still need to define when a function is tail-recursive, the compiler won't do it automatically.

E.g. Scala provides such an annotation, but that is implemented by rewriting the recursive method to a non-recursive method with a loop.

Isn't that kinda how all TCO works?

First level TCO yes, however the annotation way doesn't work for mutually recursive calls.

to clarity just a tad, the Scala compiler does TCO out of the box and the annotation is added only to check that the method is in fact so optimizable

Unless something changed since 2.0.9 (last time I did anything relevant in Scala), only one level, it isn't clever enough to rewrite mutually recursive calls.

This is rather important, specially when coming from languages like Scheme that have TCO as part of the language specification compliance.

No we won't. [1] does not even mention tail-call elimination. Project Loom does not change the bytecode and does not change it's semantics. I.e. we don't get guaranteed tail-call elimination.

[1]: https://openjdk.java.net/jeps/425

TCO will be part of project valhalla not loom.

Reply on news.ycombinator.com