[ectoplasm]

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]

> 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.

[dragonwriter]

> 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]

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.

[codygman]

I don't think you can say "Haskell is nowhere near an ML-like language" based on just lazy vs eager evaluation.

See here[0]:

> Since Haskell is inevitably an ML (descending from Lazy ML) derivative, one might begin by pointing out the similarities:

    - First-class support for algebraic datatypes (disjoint unions)
    - Pattern matching on primitive and custom values
    - Arbitrarily higher order functions
    - Type synonyms
    - Hindley-Milner Type Inference
    - Parametric Polymorphism (define arbitrary Functors etc.)
    - Ad-hoc polymorphism (Haskell through type classes, SML through modules)
    - scorn of inclusion polymorphism (sub-type relations, a la object-wise inheritance)
    - Monads (and other exotic algebraic structures)—"Haskell has monads" is a common claim of superiority, but the reality is that at the language level a monad is nothing more than an abstraction pattern, and hence every language (can) have monads. Including a monad or not in any given language is a library-level decision.

> While the bread-and-butter language features may be similar, building software in Haskell vs SML is actually quite a different affair:

So we can see a lot in common there.

0: http://www.quora.com/What-are-the-key-differences-between-Ha...

[sklogic]

> based on just lazy vs eager evaluation.

It's not "just", it's fundamental. We're talking about an efficient implementation, remember? And therefore the underlying execution semantics is the single most important thing for classifying languages. The rest that you listed is very high level, consider it syntax sugar. It is all lowered down long before any of the important optimisations start to kick in.

> So we can see a lot in common there.

Not that much. Just think of the deeply fundamental difference between SECD and, say, STG.

[ectoplasm]

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/2...

[sklogic]

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]

Why can't you modify a JVM to do this? I don't get it.

[sklogic]

Of course you can (but you have to add another instruction or an instruction prefix). But Oracle won't ever do it.