5 ms·

I've been hoping for tail call elimination[1] on the JVM for a long time, and historically it has been blocked by a security requirement[2]. Changing the number

I've been hoping for tail call elimination[1] on the JVM for a long time, and historically it has been blocked by a security requirement[2]. Changing the number of stack frames between two calls would cause an error. Apparently that check is no longer there so TCE is possible! [1] Using the word 'optimization' suggests that eliminating tail calls is optional, but for it to be really useful it has to be guaranteed. If you're writing in recursive style, your program becomes instantly incorrect if TCE goes away because many acceptable inputs will start causing stack overflows. [2] See this answer: https://softwareengineering.stackexchange.com/a/272086 https://softwareengineering.stackexchange.com/a/272086

cryptonector 6y ago
> in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them. That's... lame. BTW, tail code elimination could keep a count of tail calls for this. It wouldn't work so well for mutual recursion, but maybe that would suffice. In any case, nothing should be so dependent on stack traces!
- saagarjha 6y ago
  Java's security manager model is fairly lame in general.
  - cryptonector 6y ago
    Yes. And JAAS won't die even though applets did.
- abecedarius 6y ago
  How to do it for mutual recursion is sketched in my other comment. Java's stack inspection doesn't inherently require counting stack frames -- it's a choice. I agree it's a bad model anyway.
slaymaker1907 6y ago
I know for JavaScript it was not implemented due to issues around debugging. I think for that reason if tail call optimization was done, you would need some sort of control over it such as an annotation to turn it on or off per method, maybe even a global flag for it.
abecedarius 6y ago
It's actually possible to implement calling in such a way that TCO is compatible with Java's security architecture (or at least as it was back in the late 90s when I cared about this). IIRC you'd have a finite state machine along with your calls, which would transit when you're making a tail call of the sort which would matter to the security checks. In other words, the amount of security state needed by a tail-call chain was bounded, if you implemented the spec in a tail-call conscious way. I thought stack inspection was a bad idea anyway, but you could implement it together with TCO. [edited because truncated by misclick]
malkia 6y ago
I remember the rationale behind clojure's recur - if you want to use it, your recur calls needs to be tail call optimizable, otherwise it fails to compile (sorry was long time since I've done any clojure, so could be wrong here). At first it was - why such requirement? Then it hit me - this is not bad - it's actually enforcing that either you would succeed doing that, and the compiler would also do it, or not. So there is a strong guarantee there.
- wtetzner 6y ago
  Unfortunately Clojure’s recur only works for self tail calls.
dreamcompiler 6y ago
This does not appear to be general TCE (i.e. between two possibly different functions), but strictly recursive TCE. So with mutual recursion you could still overflow the stack. Nevertheless it seems like a big step forward.

cryptonector 6y ago

> in jdk classes [...] there are a number of security sensitive methods that rely on counting stack frames between jdk library code and calling code to figure out who's calling them. That's... lame. BTW, tail code elimination could keep a count of tail calls for this. It wouldn't work so well for mutual recursion, but maybe that would suffice. In any case, nothing should be so dependent on stack traces!

saagarjha 6y ago
Java's security manager model is fairly lame in general.
- cryptonector 6y ago
  Yes. And JAAS won't die even though applets did.
abecedarius 6y ago
How to do it for mutual recursion is sketched in my other comment. Java's stack inspection doesn't inherently require counting stack frames -- it's a choice. I agree it's a bad model anyway.

slaymaker1907 6y ago

I know for JavaScript it was not implemented due to issues around debugging. I think for that reason if tail call optimization was done, you would need some sort of control over it such as an annotation to turn it on or off per method, maybe even a global flag for it.

abecedarius 6y ago

It's actually possible to implement calling in such a way that TCO is compatible with Java's security architecture (or at least as it was back in the late 90s when I cared about this). IIRC you'd have a finite state machine along with your calls, which would transit when you're making a tail call of the sort which would matter to the security checks. In other words, the amount of security state needed by a tail-call chain was bounded, if you implemented the spec in a tail-call conscious way. I thought stack inspection was a bad idea anyway, but you could implement it together with TCO. [edited because truncated by misclick]

malkia 6y ago

I remember the rationale behind clojure's recur - if you want to use it, your recur calls needs to be tail call optimizable, otherwise it fails to compile (sorry was long time since I've done any clojure, so could be wrong here). At first it was - why such requirement? Then it hit me - this is not bad - it's actually enforcing that either you would succeed doing that, and the compiler would also do it, or not. So there is a strong guarantee there.

wtetzner 6y ago
Unfortunately Clojure’s recur only works for self tail calls.

dreamcompiler 6y ago

This does not appear to be general TCE (i.e. between two possibly different functions), but strictly recursive TCE. So with mutual recursion you could still overflow the stack. Nevertheless it seems like a big step forward.