5 ms·

I'm curious as to what effect Java's crappy tail recursion has I tried running a ruby sudoku solver in jruby that functions basically like an n-queens solver an

by j2d2 17y ago

I'm curious as to what effect Java's crappy tail recursion has I tried running a ruby sudoku solver in jruby that functions basically like an n-queens solver and it couldn't handle it. Not sure I'd expect erjang to do better since the issue is with the jvm.

bad_user 17y ago
Tail-recursion can be implemented on top of the JVM. For self-recursion you just issue a GOTO. For mutual recursion, the compiler can generate a trampoline. There are two problems with a trampoline ... one is that the stack-trace will no longer be accurate. And the second problem is that interoperability with Java suffers because the bytecode of the method or that of the call-site will be different from what-you-see in your code. For example one way of doing it is to modify the recursive function ... fn (a) => b ... to be ... fn (a) => M[b] ... where M[b] contains either the returned value "b" or the reference + arguments of the next call done by the trampoline. And then the compiler modifies the call-sites to call the trampoline instead of our method. About efficiency ... if you want to have a generic trampoline module (instead of many trampolines defined for each group ... which would consume permgen memory), you could implement such a trampoline on top of the new invokedynamic support in JDK7 ... this could allow for the call-sites in the trampoline to be cached and ultimately JITed. I'm not sure if invokedynamic could help here (I know little about how the call-sites will be cached) but I don't see why not.
- gordonguthrie 17y ago
  > the stack-trace will no longer be accurate ...as indeed it isn't in Erlang...
- Drkrab 17y ago
  You can read how I do tail recursion at http://wiki.github.com/krestenkrab/erjang/how-erjang-compiles-tail-recursion http://wiki.github.com/krestenkrab/erjang/how-erjang-compile...

5 ms·

I'm curious as to what effect Java's crappy tail recursion has I tried running a ruby sudoku solver in jruby that functions basically like an n-queens solver an

by j2d2 17y ago

bad_user 17y ago
Tail-recursion can be implemented on top of the JVM. For self-recursion you just issue a GOTO. For mutual recursion, the compiler can generate a trampoline. There are two problems with a trampoline ... one is that the stack-trace will no longer be accurate. And the second problem is that interoperability with Java suffers because the bytecode of the method or that of the call-site will be different from what-you-see in your code. For example one way of doing it is to modify the recursive function ... fn (a) => b ... to be ... fn (a) => M[b] ... where M[b] contains either the returned value "b" or the reference + arguments of the next call done by the trampoline. And then the compiler modifies the call-sites to call the trampoline instead of our method. About efficiency ... if you want to have a generic trampoline module (instead of many trampolines defined for each group ... which would consume permgen memory), you could implement such a trampoline on top of the new invokedynamic support in JDK7 ... this could allow for the call-sites in the trampoline to be cached and ultimately JITed. I'm not sure if invokedynamic could help here (I know little about how the call-sites will be cached) but I don't see why not.
- gordonguthrie 17y ago
  > the stack-trace will no longer be accurate ...as indeed it isn't in Erlang...
- Drkrab 17y ago
  You can read how I do tail recursion at http://wiki.github.com/krestenkrab/erjang/how-erjang-compiles-tail-recursion http://wiki.github.com/krestenkrab/erjang/how-erjang-compile...