6 ms·

Tail Call Recursion in Java with ASM (2023)

96 points by hyperbrainer 1y ago

ncruces 1y ago
It's been a long time since I've messed with Java bytecode [1], but shouldn't the private method call use INVOKESPECIAL? In general I don't think you can do this to INVOKEVIRTUAL (or INVOKEINTERFACE) as it covers cases where your target is not statically resolved (virtual/interface calls). This transformation should be limited to INVOKESTATIC and INVOKESPECIAL. You also need lots more checks to make sure you can apply the transformations, like ensure the call site is not covered by a try block, otherwise this is not semantics preserving. 1: https://jauvm.blogspot.com/ https://jauvm.blogspot.com/
lukaslalinsky 1y ago
I never understood the need for tail recursion optimization in imperative languages. Sure, you need it in FP if you don't have loops and recursion is you only option, but what is the benefit of recursive algorithms, that could benefit from tail optimization (i.e recursive loops), in a language like Java?
cempaka 1y ago
Very nice article demonstrating a neat use of ASM bytecode. The Java language devs are also working on Project Babylon (code reflection), which will bring additional techniques to manipulate the output from the Java compiler: https://openjdk.org/projects/babylon/articles/code-models https://openjdk.org/projects/babylon/articles/code-models
- gavinray 1y ago
  This was delivered in JDK 24 as the "Class-File API" https://openjdk.org/jeps/484 https://openjdk.org/jeps/484
  - algo_trader 1y ago
    Can this improve/replace AspectJ and similar instrumentations? We do lots of instruction level modifications
droideqa 1y ago
Cool, now ABCL can have TCO!
- dapperdrake 1y ago
  Finally. The ANTLR guys went through terrible contortions for their parsers. Never felt like working those details out for ABCL.
- 1932812267 1y ago
  This isn't a _general_ tail call optimization--just tail recursion. The issue is that this won't support mutual tail recursion. e.g.: (defun func-a (x) (func-b (- x 34)) (defun func-b (x) (cond ((<= 0 x) x) ('t (func-a (-x 3)))) Because func-a and func-b are different (JVM) functions, you'd need an inter-procedural goto (i.e. a tail call) in order to natively implement this. As an alternative, some implementations will use a trampoline. func-a and func-b return a _value_ which says what function to call (and what arguments) for the next step of the computation. The trampoline then calls the appropriate function. Because func-a and func-b _return_ instead of actually calling their sibling, the stack depth is always constant, and the trampoline takes care of the dispatch.
  - knome 1y ago
    Sounds like a manual form of clojures recur function. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur
    - 1932812267 1y ago
      Clojure's loop/recur is specifically tail recursion like scala's tailrec or the optimization described in the blogpost. It doesn't use trampolines to enable tail calls that aren't tail recursion.
bradley13 1y ago
Every compiler should recognize and optimize for tail recursion. It's not any harder than most other optimizations, and some algorithms are far better expressed recursively. Why is this not done?
- _old_dude_ 1y ago
  Parroting something i have heard at a Java conference several years ago, tail recursion remove stack frames but the security model is based on stack frames, so it has to be a JVM optimization, not a compiler optimization. I've no idea if this fact still holds when the security manager will be removed.
  - smarks 1y ago
    The security manager was removed (well, “permanently disabled”) in Java 24. As you note, the permissions available at any given point can depend on the permissions of the code on the stack, and TCO affects this. Removal of the SM thus removes one impediment to TCO. However, there are other things still in the platform for which stack frames are significant. These are referred to as “caller sensitive” methods. An example is Class.forName(). This looks up the given name in the classloader of the class that contains the calling code. If the stack frames were shifted around by TCO, this might cause Class.forName() to use the wrong classloader. No doubt there are ways to overcome this — the JVM does inlining after all — but there’s work to be done and problems to be solved.
    - thfuran 1y ago
      Is there? As you say, there's already inlining, and I don't see how tco presents a harder case for that.
      - smarks 1y ago
        There are similarities in the problems, but there are also fundamental differences. With inlining, the JVM can always decide to deoptimize and back out the inlining without affecting the correctness of the result. But it can't do that with tail calls without exposting the program to a risk of StackOverflowError. We've been using TCO here ("tail call optimization") but I recall Guy Steele advocating for calling this feature TCE ("elimination") because programs can rely on TCE for correctness.
1932812267 1y ago
Scala has been using this technique for years with its scala.annotation.tailrec annotation. Regardless, it's cool to see this implemented as a bytecode pass.
- gavinray 1y ago
  Kotlin as well, with the "tailrec" keyword, e.g. "tailrec fun fibonacci()" https://kotlinlang.org/docs/functions.html#tail-recursive-functions https://kotlinlang.org/docs/functions.html#tail-recursive-fu... Kotlin also has a neat other tool, "DeepRecursiveFunction<T, R>" that allows defining deep recursion that is not necessarily tail-recursive. Really useful if you wind up a problem that is most cleanly solved with mutual recursion or similar: https://kotlinlang.org/api/core/kotlin-stdlib/kotlin/-deep-recursive-function/ https://kotlinlang.org/api/core/kotlin-stdlib/kotlin/-deep-r...
  - deepsun 1y ago
    Interesting, does it depend on Kotlin compiler or it can be implemented in Java as well?
    - gavinray 1y ago
      The "DeepRecursiveFunction<T,R>" could be implemented in Java. The Kotlin implementation leverages Kotlin's native coroutines and uses continuations. It'd require a bit of engineering to get something working in native Java I'd imagine, even with the new JDK Structured Concurrency API offering you a coroutines alternative. On the other hand, "tailrec" is a keyword and implemented as a compiler optimization. The closest I've seen in Java is a neat IntelliJ plugin that has a transformation to convert recursive method calls into imperative loops with a stack frame. This transformation and resulting tool was the result of someone's thesis, it's pretty cool: https://github.com/andreisilviudragnea/remove-recursion-inspection https://github.com/andreisilviudragnea/remove-recursion-insp...
curtisszmania 1y ago
[dead]
fsckboy 1y ago
the "lambda the ultimate" papers and the birth of scheme was a loong time ago, so it grates on my ears to hear this topic presented as "an optimization". Yes, it is sometimes an optimization a compiler can make, but the idea is much better presented as a useful semantic of a language. in the same way that passing parameters to a subfunction "creates" a special set of local variables for the subfunction, the tail recursion semantic updates this set of local variables in an especially clean way for loop semantics, allowing "simultaneous assignment" from old values to new ones. (yes, it would be confusing with side effected C/C++ operators like ++ because then you'd need to know order of evaluation or know not to do that, but those are already issues in those languages quite apart from tail recursion) because it's the way I learned it, I tend to call the semantic "tail recursion" and the optimization "tail call elimination", but since other people don't do the same it's somewhat pointless; but I do like to crusade for awareness of the semantic beyond the optimization. If it's an optimization, you can't rely on it because you could blow the stack on large loops. If it's a semantic, you can rely on it. (the semantic is not entirely "clean" either. it's a bit of a subtle point that you need to return straightaway the return value of the tail call or it's not a tail call. fibonacci is the sum of the current with the next so it's not a tail call unless you somewhat carefully arrange the values you pass/keep around. also worth pointing out that all "tail calls" are up for consideration, not just recursive ones)
- ekimekim 1y ago
  In a weird way it kinda reminds me of `exec` in sh (which replaces the current process instead of creating a child process). Practically, there's little difference between these two scripts: #!/bin/sh foo bar vs #!/bin/sh foo exec bar And you could perhaps imagine a shell that does "tail process elimination" to automatically perform the latter when you write the former. But the distinction can be important due to a variety of side effects and if you could only achieve it through carefully following a pattern that the shell might or might not recognize, that would be very limiting.
  - nagaiaida 1y ago
    this is pretty much exactly how my "forth" handles tail call elimination, and it's the main thing that's added the quotes so far since it shifts the mental burden to being aware of this when writing code to manipulate the return stack. as you imply towards the end, i'm not confident this is a trick you can get away with as easily without the constraints of concatenative programming to railroad you into it being an easily recognizable pattern for both the human and the interpreter.

96 points by hyperbrainer 1y ago

It's been a long time since I've messed with Java bytecode [1], but shouldn't the private method call use INVOKESPECIAL? In general I don't think you can do this to INVOKEVIRTUAL (or INVOKEINTERFACE) as it covers cases where your target is not statically resolved (virtual/interface calls). This transformation should be limited to INVOKESTATIC and INVOKESPECIAL. You also need lots more checks to make sure you can apply the transformations, like ensure the call site is not covered by a try block, otherwise this is not semantics preserving. 1: https://jauvm.blogspot.com/ https://jauvm.blogspot.com/

lukaslalinsky 1y ago

I never understood the need for tail recursion optimization in imperative languages. Sure, you need it in FP if you don't have loops and recursion is you only option, but what is the benefit of recursive algorithms, that could benefit from tail optimization (i.e recursive loops), in a language like Java?

cempaka 1y ago

Very nice article demonstrating a neat use of ASM bytecode. The Java language devs are also working on Project Babylon (code reflection), which will bring additional techniques to manipulate the output from the Java compiler: https://openjdk.org/projects/babylon/articles/code-models https://openjdk.org/projects/babylon/articles/code-models

gavinray 1y ago
This was delivered in JDK 24 as the "Class-File API" https://openjdk.org/jeps/484 https://openjdk.org/jeps/484
- algo_trader 1y ago
  Can this improve/replace AspectJ and similar instrumentations? We do lots of instruction level modifications

droideqa 1y ago

Cool, now ABCL can have TCO!

dapperdrake 1y ago
Finally. The ANTLR guys went through terrible contortions for their parsers. Never felt like working those details out for ABCL.
1932812267 1y ago
This isn't a _general_ tail call optimization--just tail recursion. The issue is that this won't support mutual tail recursion. e.g.: (defun func-a (x) (func-b (- x 34)) (defun func-b (x) (cond ((<= 0 x) x) ('t (func-a (-x 3)))) Because func-a and func-b are different (JVM) functions, you'd need an inter-procedural goto (i.e. a tail call) in order to natively implement this. As an alternative, some implementations will use a trampoline. func-a and func-b return a _value_ which says what function to call (and what arguments) for the next step of the computation. The trampoline then calls the appropriate function. Because func-a and func-b _return_ instead of actually calling their sibling, the stack depth is always constant, and the trampoline takes care of the dispatch.
- knome 1y ago
  Sounds like a manual form of clojures recur function. https://clojuredocs.org/clojure.core/recur https://clojuredocs.org/clojure.core/recur
  - 1932812267 1y ago
    Clojure's loop/recur is specifically tail recursion like scala's tailrec or the optimization described in the blogpost. It doesn't use trampolines to enable tail calls that aren't tail recursion.

bradley13 1y ago

Every compiler should recognize and optimize for tail recursion. It's not any harder than most other optimizations, and some algorithms are far better expressed recursively. Why is this not done?

_old_dude_ 1y ago
Parroting something i have heard at a Java conference several years ago, tail recursion remove stack frames but the security model is based on stack frames, so it has to be a JVM optimization, not a compiler optimization. I've no idea if this fact still holds when the security manager will be removed.
- smarks 1y ago
  The security manager was removed (well, “permanently disabled”) in Java 24. As you note, the permissions available at any given point can depend on the permissions of the code on the stack, and TCO affects this. Removal of the SM thus removes one impediment to TCO. However, there are other things still in the platform for which stack frames are significant. These are referred to as “caller sensitive” methods. An example is Class.forName(). This looks up the given name in the classloader of the class that contains the calling code. If the stack frames were shifted around by TCO, this might cause Class.forName() to use the wrong classloader. No doubt there are ways to overcome this — the JVM does inlining after all — but there’s work to be done and problems to be solved.
  - thfuran 1y ago
    Is there? As you say, there's already inlining, and I don't see how tco presents a harder case for that.
    - smarks 1y ago
      There are similarities in the problems, but there are also fundamental differences. With inlining, the JVM can always decide to deoptimize and back out the inlining without affecting the correctness of the result. But it can't do that with tail calls without exposting the program to a risk of StackOverflowError. We've been using TCO here ("tail call optimization") but I recall Guy Steele advocating for calling this feature TCE ("elimination") because programs can rely on TCE for correctness.

1932812267 1y ago

Scala has been using this technique for years with its scala.annotation.tailrec annotation. Regardless, it's cool to see this implemented as a bytecode pass.

gavinray 1y ago
Kotlin as well, with the "tailrec" keyword, e.g. "tailrec fun fibonacci()" https://kotlinlang.org/docs/functions.html#tail-recursive-functions https://kotlinlang.org/docs/functions.html#tail-recursive-fu... Kotlin also has a neat other tool, "DeepRecursiveFunction<T, R>" that allows defining deep recursion that is not necessarily tail-recursive. Really useful if you wind up a problem that is most cleanly solved with mutual recursion or similar: https://kotlinlang.org/api/core/kotlin-stdlib/kotlin/-deep-recursive-function/ https://kotlinlang.org/api/core/kotlin-stdlib/kotlin/-deep-r...
- deepsun 1y ago
  Interesting, does it depend on Kotlin compiler or it can be implemented in Java as well?
  - gavinray 1y ago
    The "DeepRecursiveFunction<T,R>" could be implemented in Java. The Kotlin implementation leverages Kotlin's native coroutines and uses continuations. It'd require a bit of engineering to get something working in native Java I'd imagine, even with the new JDK Structured Concurrency API offering you a coroutines alternative. On the other hand, "tailrec" is a keyword and implemented as a compiler optimization. The closest I've seen in Java is a neat IntelliJ plugin that has a transformation to convert recursive method calls into imperative loops with a stack frame. This transformation and resulting tool was the result of someone's thesis, it's pretty cool: https://github.com/andreisilviudragnea/remove-recursion-inspection https://github.com/andreisilviudragnea/remove-recursion-insp...

curtisszmania 1y ago

[dead]

fsckboy 1y ago

the "lambda the ultimate" papers and the birth of scheme was a loong time ago, so it grates on my ears to hear this topic presented as "an optimization". Yes, it is sometimes an optimization a compiler can make, but the idea is much better presented as a useful semantic of a language. in the same way that passing parameters to a subfunction "creates" a special set of local variables for the subfunction, the tail recursion semantic updates this set of local variables in an especially clean way for loop semantics, allowing "simultaneous assignment" from old values to new ones. (yes, it would be confusing with side effected C/C++ operators like ++ because then you'd need to know order of evaluation or know not to do that, but those are already issues in those languages quite apart from tail recursion) because it's the way I learned it, I tend to call the semantic "tail recursion" and the optimization "tail call elimination", but since other people don't do the same it's somewhat pointless; but I do like to crusade for awareness of the semantic beyond the optimization. If it's an optimization, you can't rely on it because you could blow the stack on large loops. If it's a semantic, you can rely on it. (the semantic is not entirely "clean" either. it's a bit of a subtle point that you need to return straightaway the return value of the tail call or it's not a tail call. fibonacci is the sum of the current with the next so it's not a tail call unless you somewhat carefully arrange the values you pass/keep around. also worth pointing out that all "tail calls" are up for consideration, not just recursive ones)

ekimekim 1y ago
In a weird way it kinda reminds me of `exec` in sh (which replaces the current process instead of creating a child process). Practically, there's little difference between these two scripts: #!/bin/sh foo bar vs #!/bin/sh foo exec bar And you could perhaps imagine a shell that does "tail process elimination" to automatically perform the latter when you write the former. But the distinction can be important due to a variety of side effects and if you could only achieve it through carefully following a pattern that the shell might or might not recognize, that would be very limiting.
- nagaiaida 1y ago
  this is pretty much exactly how my "forth" handles tail call elimination, and it's the main thing that's added the quotes so far since it shifts the mental burden to being aware of this when writing code to manipulate the return stack. as you imply towards the end, i'm not confident this is a trick you can get away with as easily without the constraints of concatenative programming to railroad you into it being an easily recognizable pattern for both the human and the interpreter.