Lambda the Ultimate

What are the differences that I'm missing?

" The similarities are not surprising, as Needle is based on the same type system as Nice (ML-Sub) and on one of my research articles on typing multi-methods (presented at FOOL 2002).

From the slides, it seems that Needle has a more functional taste (let notation, and type inferrence, and I suppose no overloading). From the LL2 talk, it compiles to a specific virtual machine. This probably means that libraries will have to be written from scratch. It seems to be in a pre-alpha state since there is no public release yet, and no manual. "

Note that the type inference presented in the talk is the exact application of my FOOL 2002 paper. My name is quoted, but not the references so here they are: Daniel Bonniot. Type-checking multi-methods in ML (a modular approach). In The Ninth International Workshop on Foundations of Object-Oriented Languages, FOOL 9, Portland, Oregon, USA, January 2002. http://cristal.inria.fr/~bonniot/bonniot02.ps

So I guess that the two projects will head to somewhat different directions: I can feel a lisp/scheme inspiration in Needle, and Nice targets integration with Java. I hope they can also benefit from each other.

(It seems I can edit my post, I got: "Can't post to this page because the "referer" did not match the expected "referer")

What (multiplatform) VM would one choose from for a experimental new language like Needle?

I've had a headcold - suggesting that I've had it for
more than a couple of days would be unkind ;-)

Kawa also has support for full tail calls. I think it is more general (i.e. tail-calling unknown functions), but also has a higher overhead.

No, I've never worked on Mondrian; I'm just funded by them. :)

You can actually implement proper tail recursion on the JVM. True, there is no native support for it, some it needs some tricks. See for instance Kjetil Valstadsve's Compiling Scheme for the JVM

That works for mutual recursion, but not for, as you mentioned, unknown functions or functions which happen to be in different class files.

The only way I know to get proper tail recursion in the JVM in all cases is to implement a main "event" loop which dispatches each non-local function call. ("Trampolining"?) But if you go that far, what have you got? It's just an interpreter now!

Kawa also has support for full tail calls. I think it is more general (i.e. tail-calling unknown functions), but also has a higher overhead.

How does Kawa do it? I bet it uses the trampoline trick...

OTOH, if Needle were to support call/cc on JVM it would probably need to use that technique anyway, since upward (non-escaping) continuations require that you have activation frames on the heap, and as I recall you cannot copy the JVM stack.

Anyway, my point was just that you cannot compile an FPL with proper tail recursion to the JVM, in the sense that it uses the JVM's own primitive control mechanisms; if you are willing to do interpretation, that's another story, but then you are usually paying the cost of an interpreter twice, since the JVM itself is usually implemented as an interpreter.

The operative word here is "good." It is, of course, possible to compile functional languages to JBC, the same way you can target real CPUs.

The real issue is whether the VM does anything to help (e.g., by properly supporting tail calls), and whether achieving proper tail recursion requires having access to all source code (including library functions), and whole program analysis.

It would be great if someone could write a summary of the issues involved, like the summary Oleg wrote for LtU about tail call optimization in imperative languages.

Principle Issues:

• Tail Recursion:return to an evaluation loop (called 'trampoline' by some?)"--Nigel Perry
• Polymorphism: use objects.--Nigel Perry
• Closure/Laziness:"Local (anonymous) classes with an ENTER() method."--Nigel Perry
• Identifiers: "One of the more gratuitous illustrations of that is how that method and field names are required by the verifier to conform to Java syntax, e.g., you can't use "+" as a method name, even though "+" is a perfectly good (and standard) identifier in Lisp languages. The result is that identifiers have to be "mangled." No big deal, but it's a minor annoyance." --Per Bothner

Performance & Reliability:

• "A highlight is that for MLj all polymorphism is expanded out. This is pretty important for Java, since otherwise all integers etcetera would have to be Objects. The Object overhead in Java can be pretty considerable."--George Russell
• "[O]ne of our biggest problems was being a hostage to the mistakes of the various JVMs out there. (For example Microsoft's was often the fastest but we kept having to insert hacks to work around Microsoft bugs & so on & so on.)"--George Russell
• "[P]oor performance [could result] from representing heap objects (closures in the STG-machine, graph nodes in the G-machine etc.) as java classes. Class instance initialisation seems to be rather heavy-weight operation in the JVM."--Artur Zawlocki
• "returning more than one value is a problem. C#/.NET supports non-heap-allocated objects, so you can return a pair more efficiently, which is nice."--Per Bothner
• "If you have (or generate) a collection of classes, there is a lot of wasted space, due to symbol duplication, because each class requires its own constant pool. "--Per Bothner

There is also the interesting paper "Compiling Lazy Functional Programs for the Java Virtual Machine", Journal of Functional Programming, 9(6), November 1999, pp. 579-603, available here. As well as a prior LtU topic.

A long, but not exhaustive list, of efforts to compile languages to the JVM is here (it has nothing for ML, but I know that at least there was MLj), as well as a haphazard list of other VMs here.

What other issues are there? If the JVM is not a good target, are there any other VMs which would give a new FL the advantage of running on many platforms and having access to pre-existing libraries?

Sorry for the delay, but I look at LtU only intermittently. I wanted to confirm that Needle does look very similar to Nice, because I've taken advantage of a lot of the great work that Daniel Bonniot has done. He deserves a lot of thanks, because seeing that work was a really big inspiration to me. He also has a very good eye: the main inspirations for Needle were Dylan and Ocaml, so I do indeed want to go in a lispy/functional direction.

Digression: I'm curious what impact the addition of generics in Java 1.5 will have on Nice, since it has a different set of rules for parametric types than Nice does.

Shame on you

See Trampolined Style, Steven E. Ganz, Daniel P. Friedman, and Mitchell Wand. ICFP 1999.

What you can translate from GJ to Nice:

// JAVA interface Comparable<T> { int compareTo(T); }

class String implements Comparable<String> { ... }

// NICE abstract interface Comparable { int compareTo(alike); }

class java.lang.String implements Comparable;

One advantage of the Nice approach is that the declaration that a class implements an "abstract interface" (a kind) can be made independantly of the definition of the class, for instance in a different package in which the abstract interface is defined.

I am actually thinking of automatically doing this translation from "legacy" Java 1.5 code to Nice, given the declaration

abstract interface Comparable = native java.lang.Comparable<T>;

What you cannot translate from GJ to Nice: a class or interface that has a different variance than one of its parents. This is because Nice has an structural type system , where type constraints can always be decomposed to atomic constraints. It would be useful to lift that restriction, but that touches a corner stone of the type system, so it might be perilous. Comments?

What you cannot translate from Nice to GJ: The abstract interfaces are more powerful than GJ's form F-bounded polymorphism. One reason is the additional modularity given earlier. Another is that in GJ types are restricted to implement a given interface with only one set of type parameters. The Java 1.5 says that this restriction is made to allow translation by erasure, but I am not sure why. Additionally, GJ cannot express multible bounds (or more complex constraints) allowed in Nice/ML-sub.

Are there other differences that you were thinking of?

Can it be because you want type safety AND separate compilation?

(Just thinking out loud here. It has been awhile since I looked into GJ.)