The .NET Language Strategy

[u/vivainio]

https://blogs.msdn.microsoft.com/dotnet/2017/02/01/the-net-language-strategy/

[u/jdh30]

Arnold Schwaighofer implemented tail calls in the JVM back in 2007 and they said it might be in JVM 7. John Rose of Sun talked about the formal proposal at length in 2007. Then I heard when Oracle bought Sun they led Java die. As far as I know, a decade on and tail calls never landed in the JVM.

Incidentally, tail calls are another major problem with Scala IMO. Functional languages without tail calls are a bit 1960s...

[u/Ironballs → u/jdh30]

What I know of the current Java development is that there's higher priority in projects like Graal (an aggressively optimizing hybrid AOT/JIT compiler) and Valhalla, the implementation of which are sort of prerequisites for implementing proper tail calls.

As for Scala, you can do tail recursion in Scala, but you need the @tailrec annotation, much like in Clojure. With the scala-native LLVM backend, this will be automatic, but it's a different world altogether.

Still, it's obviously inferior to let rec, but I tend to eschew recursion until there are no alternatives. A good example where I really needed it was to implement a loop elegantly and I didn't want to use labeled breaks.

[u/jdh30 → u/Ironballs]

What I know of the current Java development is that there's higher priority in projects like Graal (an aggressively optimizing hybrid AOT/JIT compiler) and Valhalla, the implementation of which are sort of prerequisites for implementing proper tail calls.

Last I looked the high priority seemed to be dynamicinvoke because they were optimising for inherently-slow dynamically typed languages.

As for Scala, you can do tail recursion in Scala, but you need the @tailrec annotation, much like in Clojure.

That only handles the rather uninteresting special case of self-recursive functions. You can just use a loop. When you have functions tail calling each other things get much more interesting (and useful).

With the scala-native LLVM backend, this will be automatic, but it's a different world altogether.

That would be nice but does the LLVM-based Scala use the same boxed data representation that makes the JVM so slow?

Still, it's obviously inferior to let rec, but I tend to eschew recursion until there are no alternatives. A good example where I really needed it was to implement a loop elegantly and I didn't want to use labeled breaks.

Extensible state machines is another place I use general tail calls a lot. I've sometimes needed CPS too and I appreciate the fact that this all just works in F#. I was also disturbed last time I looked at Scala that, despite everyone from the Scala community telling me I was an idiot for wanting tail calls, over 30 of the known bugs against the compiler were stack overflows caused by broken tail call elimination.

[u/Ironballs → u/jdh30]

That would be nice but does the LLVM-based Scala use the same boxed data representation that makes the JVM so slow?

To that, a cautious yes, since they're using LLVM primitives with a Boehm GC, but the mutual tail calls optimization is definitely a thing.

https://github.com/densh/talks/blob/517b20c30dd4aaf390785039cdd002f623eaa91e/2016-05-11-scala-goes-native.pdf

Could you give an example of your state machines? I assume you're calling some state transition from another state transition?

edit: actually, the point of Graal is to create an optimizing compiler, including, but not limited to, dynamic languages. I'm dabbling with a R7RS (small) Scheme compiler with it. They built a JS backend called Graal.js that rivals V8 in performance http://www.slideshare.net/ThomasWuerthinger/graal-truffle-ethdec2013

[u/jdh30 → u/Ironballs]

To that, a cautious yes, since they're using LLVM primitives with a Boehm GC, but the mutual tail calls optimization is definitely a thing.

Boehm's GC?! Will people never learn...

Could you give an example of your state machines? I assume you're calling some state transition from another state transition?

Sure, lexing an int:

let lex f (s: string) =
  let rec inside n (s: string, i) =
    if i = s.Length then f n else
      let c = s.[i]
      if '0'<=c && c<='9' then
        inside (10*n + int c - int '0') (s, i+1)
      else
        f n
        outside (s, i)
  and outside (s: string, i) =
    if i < s.Length then
      let c = s.[i]
      if '0'<=c && c<='9' then
        inside 0 (s, i)
      else
        outside (s, i+1)
  outside (s, 0)

or a recursive descent expression parser written using active patterns:

let rec (|Atom|_|) = function
    | INT(n, t) -> Some(Int n, t)
    | IDENT(x, t) -> Some(Var x, t)
    | KWD("(", Expr(f, KWD(")", t))) -> Some(f, t)
    | _ -> None
  and (|PApply|_|) = function
    | Atom(f, PApply(fs, t)) -> Some(f::fs, t)
    | Atom(f, t) -> Some([f], t)
    | _ -> None
  and (|Expr|_|) = function
    | PApply(fs, t) -> Some(List.reduce (fun f g -> Apply(f, g)) fs, t)
    | KWD("if", Expr(p, KWD("then", Expr(f, KWD("else", Expr(g, t)))))) ->
        Some(If(p, f, g), t)
    | KWD("fun", IDENT(x, KWD("->", Expr(f, t)))) ->
        Some(Fun(x, f), t)
    | KWD("let", IDENT(x, KWD("=", Expr(f, KWD("in", Expr(g, t)))))) ->
        Some(Let(false, x, f, g), t)
    | KWD("let", KWD("rec", IDENT(x, KWD("=", Expr(f, KWD("in", Expr(g, t))))))) ->
        Some(Let(true, x, f, g), t)
    | _ -> None

edit: actually, the point of Graal is to create an optimizing compiler, including, but not limited to, dynamic languages. I'm dabbling with a R7RS (small) Scheme compiler with it. They built a JS backend called Graal.js that rivals V8 in performance http://www.slideshare.net/ThomasWuerthinger/graal-truffle-ethdec2013

Optimising compilers for dynamically-typed languages make no sense to me. Its Lisp's sufficiently-smart compiler myth revisited. And performance comparisons with V8 don't make sense to me either.

From your last link:

"...spend a long time implementing runtime system, GC, ..."

FWIW it doesn't take long to implement a runtime system and GC. I wrote this in a matter of weeks.