3 ms·

How come?

sklogic 11y ago
It's got some severe built-in limitations. Firstly and most importantly, there is no support whatsoever for the proper tail calls (and F# is using the .tail prefix quite a lot). Secondly, no stack allocation (value types in .NET). Another thing which may harm optimisation significantly (although not sure if F# is using it - but the other functional languages most definitely would have benefited from this) is a very low hard limit on a method size, which forbids any extensive inlining and specialisation.
- ectoplasm 11y ago
  Thanks for clarifying. I think tail call conversion to iteration for Java bytecode could be added to a JVM implementation without changing the spec, and you could also do it when converting F# to bytecode. Apparently it's on the todo list but not high priority. Stack allocation is trickier if it's specified in F# code, because it isn't part of the VM spec, but automatic stack allocation for Java has been demonstrated in a research context and I think either HotSpot or J9 can do it too. The method size limit is something like 2^16 bytecodes, but even if that's a problem, JITs are free to inline beyond that as much as they want. So, I agree it would take some work but I don't think it's fundamentally impractical. Adding stack allocation to the class file format would be the hardest thing to push through I think.
  - sklogic 11y ago
    > I think tail call conversion to iteration You cannot convert a tail call to an iteration in a generic case. Consider the following: `let f g x = g x` Here, call `g x` is a tail call, and you've no idea what `g` is, so you cannot statically inline it or convert to a loop. > JITs are free to inline beyond that as much as they want JITs are primitive and do not have much time to do anything interesting. Inlining is very important alongside with partial evaluation - which is very heavyweight and must be done statically. Anyway, without proper tail calls inlining on JIT level won't help much. > it's fundamentally impractical Everyone who ever tried implementing any ML-like language on top of JVM failed miserably.
    - ectoplasm 11y ago
      How is a "proper tail call" implemented if you aren't talking about conversion to iteration? I found the following article helpful. http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044 http://www.drdobbs.com/jvm/tail-call-optimization-and-java/2...
      - sklogic 11y ago
        Usually it is implemented by reshuffling stack frame + jumping to the call destination. See how it is done in .NET, for example. Do not confuse tail recursion, which is the least interesting narrow case of a tail call, with tail calls in general.
        ectoplasm 11y ago
        Why can't you modify a JVM to do this? I don't get it.
        sklogic 11y ago
        Of course you can (but you have to add another instruction or an instruction prefix). But Oracle won't ever do it.
    - dragonwriter 11y ago
      > Everyone who ever tried implementing any ML-like language on top of JVM failed miserably. How is "ML-like" defined here? AFAIK, Haskell is usually considered "ML-like", and Frege is a Haskell dialect implemented on the JVM.
      - sklogic 11y ago
        Haskell is nowhere near an ML-like language, it's lazy, while ML is eager. And Frege is nice and all that, but it's very far from being efficient, nothing close to F# performance.

How come?

It's got some severe built-in limitations. Firstly and most importantly, there is no support whatsoever for the proper tail calls (and F# is using the .tail prefix quite a lot). Secondly, no stack allocation (value types in .NET). Another thing which may harm optimisation significantly (although not sure if F# is using it - but the other functional languages most definitely would have benefited from this) is a very low hard limit on a method size, which forbids any extensive inlining and specialisation.

ectoplasm 11y ago
Thanks for clarifying. I think tail call conversion to iteration for Java bytecode could be added to a JVM implementation without changing the spec, and you could also do it when converting F# to bytecode. Apparently it's on the todo list but not high priority. Stack allocation is trickier if it's specified in F# code, because it isn't part of the VM spec, but automatic stack allocation for Java has been demonstrated in a research context and I think either HotSpot or J9 can do it too. The method size limit is something like 2^16 bytecodes, but even if that's a problem, JITs are free to inline beyond that as much as they want. So, I agree it would take some work but I don't think it's fundamentally impractical. Adding stack allocation to the class file format would be the hardest thing to push through I think.
- sklogic 11y ago
  > I think tail call conversion to iteration You cannot convert a tail call to an iteration in a generic case. Consider the following: `let f g x = g x` Here, call `g x` is a tail call, and you've no idea what `g` is, so you cannot statically inline it or convert to a loop. > JITs are free to inline beyond that as much as they want JITs are primitive and do not have much time to do anything interesting. Inlining is very important alongside with partial evaluation - which is very heavyweight and must be done statically. Anyway, without proper tail calls inlining on JIT level won't help much. > it's fundamentally impractical Everyone who ever tried implementing any ML-like language on top of JVM failed miserably.
  - ectoplasm 11y ago
    How is a "proper tail call" implemented if you aren't talking about conversion to iteration? I found the following article helpful. http://www.drdobbs.com/jvm/tail-call-optimization-and-java/240167044 http://www.drdobbs.com/jvm/tail-call-optimization-and-java/2...
    - sklogic 11y ago
      Usually it is implemented by reshuffling stack frame + jumping to the call destination. See how it is done in .NET, for example. Do not confuse tail recursion, which is the least interesting narrow case of a tail call, with tail calls in general.
      - ectoplasm 11y ago
        Why can't you modify a JVM to do this? I don't get it.
        sklogic 11y ago
        Of course you can (but you have to add another instruction or an instruction prefix). But Oracle won't ever do it.
  - dragonwriter 11y ago
    > Everyone who ever tried implementing any ML-like language on top of JVM failed miserably. How is "ML-like" defined here? AFAIK, Haskell is usually considered "ML-like", and Frege is a Haskell dialect implemented on the JVM.
    - sklogic 11y ago
      Haskell is nowhere near an ML-like language, it's lazy, while ML is eager. And Frege is nice and all that, but it's very far from being efficient, nothing close to F# performance.