ML types for the JVM

[Alexandru Nedelcu]

Hi,

I'm a rookie looking to implement a language for fun & profit :)

I want to know if there are any publications on efficiently mapping
the ML type-system to Java, like tuples, unions, closures ... or like
implementing generics through reification or through code-
specialization (I can't think of a reason why not, but I don't have
the experience).

Or any articles on implementing static language features on top of the
JVM (I can see there's a lot of talk on dynamic features in the Docs).

Thanks,

[Per Bothner]

On 11/25/2009 08:57 AM, Alexandru Nedelcu wrote:
> Or any articles on implementing static language features on top of the
> JVM (I can see there's a lot of talk on dynamic features in the Docs).

Kawa is relatively static (compared to most of the languages
involved in this list) in that it has static modules, declarations,
and types. So you might find the Kawa internals documentation
of interest, though it as isn't complete or up-to-date as I'd like:

http://www.gnu.org/software/kawa/internals/index.html
--
--Per Bothner
p...@bothner.com http://per.bothner.com/

[Miles Sabin]

You'll probably find lots of things of interest in the collection of
Scala related publications here,

http://www.scala-lang.org/node/143#papers

Scala's case classes and matching constructs correspond very closely
to ML/Haskell style algebraic data types and matching, so I would
expect that the papers relating to matching will be of particular
interest.

Cheers,


Miles

--
Miles Sabin
tel: +44 (0)7813 944 528
skype: milessabin
http://www.chuusai.com/
http://twitter.com/milessabin

[Patrick Wright]

A couple of pointers
LambdaVM (JVM backend for GHC)
http://www.cs.rit.edu/~bja8464/lambdavm/

CAL (Haskell-influenced language for the JVM)
http://groups.google.com/group/jvm-languages/browse_thread/thread/24927841cb387ffb/fa2199fd9714bbb8?lnk=gst&q=cal#fa2199fd9714bbb8

There is more on CAL available via the Wayback Machine. If you go to this page
http://web.archive.org/web/20071008042640rn_1/labs.businessobjects.com/cal/

you will find some documents towards the bottom; there's a section on
implementation (search for "Implementation documents" within the
page).

I think there were earlier attempts to port Haskell to the JVM which
were abandoned; Jaskell (http://jaskell.codehaus.org/) was one, but I
didn't find any implementation docs on a quick search.


HTH
Patrick

[Mark Derricutt]

CAL looked interesting and even had a full eclipse based IDE as well,
sadly it seems to be a dead project (and as you say, only really
available from the way back machine).

Which is a pity as now JVM languages are getting more and more popular
and CAL would be a welcome player.

--
Pull me down under...

[Patrick Wright]

On Wed, Nov 25, 2009 at 9:16 PM, Mark Derricutt <ma...@talios.com> wrote:
> CAL looked interesting and even had a full eclipse based IDE as well,
> sadly it seems to be a dead project (and as you say, only really
> available from the way back machine).

No, I think their project somehow got split; some of the old links now
redirect to somewhere in the nether regions of SAP's website, but Open
Quark is still available, with CAL bundled, as far as I can see
http://openquark.org/Open_Quark/Welcome.html

I didn't include that link because I couldn't easily locate docs on
implementation. But it appears to be still active in some form or
another. I think they may be downplaying CAL itself in favor of the
Quark framework, though. Who knows?


Patrick

[segoe]

I will also point to Yeti: http://mth.github.com/yeti/

It is a ML-like language on the JVM, it compiles to JVM bytecode
and the performance is quite good.

[Tom Davies]

CAL was developed by Business Objects, and then open sourced. I
believe that BO doesn't really use it any more.

I've done a lot of playing with it, and rather like it, but I don't
get enough time to do anything substantial. One day...

See http://groups.google.com/group/cal_language for some more recent
activity.

Here's a direct link to a CAL inyternals document:
http://openquark.org/Documents/cal_runtime_internals.pdf

On Nov 26, 7:16 am, Mark Derricutt <m...@talios.com> wrote:
> CAL looked interesting and even had a full eclipse based IDE as well,
> sadly it seems to be a dead project

While no development is currently being done on CAL, it is high
quality code which hasn't bit-rotted, and shouldn't be referred to as
dead! Just pining for someone with the time to work on it...

Tom

[Jon Harrop]

You might also appreciate the OCamlJava project that tries to run OCaml on the
JVM:

http://ocamljava.x9c.fr/

To the best of my knowledge, this project is also almost entirely unused.

--
Dr Jon Harrop, Flying Frog Consultancy Ltd.
http://www.ffconsultancy.com/?e

[fo...@x9c.fr]

Selon Jon Harrop <j...@ffconsultancy.com>:

It is quite true that only few people showed interest for OCaml-Java.
One major hurdle is that the project is plagued with performance problems.
You know what happens when an holiday project turns into a codebase with
more than 100k lines: early design decisions are paid with cumulated
interests ... Plus, my mantra has always been "first make it work, then
make it fast".

However, I am closely following this list to gain a better knowledge of
the JVM, and hopefully a version with decent performances should be available
for mid-2010.


As an answer to the original poster, I would like to point out that
some JVM features that are advertised as "for dynamic language" will
also be hugely beneficial to "static" languages of the ML family.
Two short examples:
- the memory profiles of both language categories are quite similar:
lot of small, short-lived objects are allocated, and hence a
garbage collector tuned for "dynamic" languages will also be a huge
win for "functional" languages;
- the "invokedynamic" instruction is a must-have for reasonable
implementations of "dynamic" languages, but "functional" languages
will also leverage its power to implement closures far more efficiently.


As a conclusion, I would say that, although I am strong advocate of "static"
languages, my understanding of the current situation on the JVM is:
"what is good for dynamic languages is indeed also good for static functional
languages".


Xavier Clerc

[Daniel Hicks]

Something I don't understand is why the Java PTB have no plans to fit
dynamic objects into the Java language. It wouldn't take much to
accomplish that, at least conceptually. Seems odd to add the feature
to the JVM and not the language.

[Tom Davies]

On Nov 27, 1:45 am, fo...@x9c.fr wrote:
>   - the "invokedynamic" instruction is a must-have for reasonable
>     implementations of "dynamic" languages, but "functional" languages
>     will also leverage its power to implement closures far more efficiently.

Could you explain more about that, Xavier?

[Ben Evans]

I think this might be a good time to reference Mark Reinhold's blog post about closures for Java:

http://blogs.sun.com/mr/entry/closures

I was fortunate enough to hear Mark speak about his ideas for Java closures at Devoxx, and at the JDK7 BoF asked him about what was in his mind for implementing them, and whether the implementation would be based around method handles.

Mark indicated that he hadn't thought much about implementation yet, but that he didn't think that method handles were the most likely way to implement closures for the Java langauge.

It may be worth reading Mark's post carefully, as the behaviour he describes for the closure structure he's describing seems to me to be somewhat different from the closure behaviour seen in (some?) other languages, and I'm not sure that the behaviour described for Java closures (Jclosures?) really covers all use cases for closures present in dynamic languages.

Of course, it's always entirely possible that I missed something vital in the substance of Mark's comments - so patches to my understanding (as always) welcome.

Thanks,

Ben

[fo...@x9c.fr]

Selon Ben Evans <benjamin....@googlemail.com>:

> On Thu, Nov 26, 2009 at 9:29 PM, Tom Davies <tgda...@gmail.com> wrote:
>
> > On Nov 27, 1:45 am, fo...@x9c.fr wrote:
> > > - the "invokedynamic" instruction is a must-have for reasonable
> > > implementations of "dynamic" languages, but "functional" languages
> > > will also leverage its power to implement closures far more
> > efficiently.
> >
> > Could you explain more about that, Xavier?

In fact, two different ideas were merged into this bullet point:
one is related to the "invokedynamic" instruction per se, while
the other one is related to the support provided for it.

Concerning the support, current builds of JDK7 propose a "java.dyn"
package that provides not only method handles but also out-of-the-box
support for partial application of methods. As of today, it seems that
code generators for functional languages overcome the lack of method
handles by either using reflection, or generating many small classes.
The first solution is slow while the second one is cumbersome.
Method handles will therefore make things faster and more elegant.

Concerning the instruction itself, my understanding is that it may
open the door to optimizations that are quite difficult to encode today.
I am indeed wondering if it may be a convenient way to implement
monomorphization: instead if using "invokevirtual" or "invokestatic",
one may use "invokedynamic" to dispatch to the implementation specialized
for a specific type in order to avoid paying the price of polymorphism.
This is just a wild guest, and would be glad to hear others' read on this idea.

> I think this might be a good time to reference Mark Reinhold's blog post
> about closures for Java:
>
> http://blogs.sun.com/mr/entry/closures

This is indeed an interesting article but, as outlined in some comments,
those are not "closures" (at least from the standpoint of a functional
programmer).

> I was fortunate enough to hear Mark speak about his ideas for Java closures
> at Devoxx, and at the JDK7 BoF asked him about what was in his mind for
> implementing them, and whether the implementation would be based around
> method handles.
>
> Mark indicated that he hadn't thought much about implementation yet, but
> that he didn't think that method handles were the most likely way to
> implement closures for the Java langauge.

Well, I don't know which exact semantics will be given to Java closures,
and am not really aware of retrofit issues (i. e. how to make closures
nicely interact with collections, event handlers, and the like) and hence
cannot say if method handles would be a good implementation base.
But, regarding functional languages my feeling is that to encode a closure
we just want a structure with a code pointer and some values. A method
handle will just be perfect to act as the code pointer.

> It may be worth reading Mark's post carefully, as the behaviour he describes
> for the closure structure he's describing seems to me to be somewhat
> different from the closure behaviour seen in (some?) other languages, and
> I'm not sure that the behaviour described for Java closures (Jclosures?)
> really covers all use cases for closures present in dynamic languages.

The blog entry does not give many details, but the unability to capture
(non-final ?) variables is against the tradition of what is usually referred
to as "closures". It is presented as a safeguard, but I think that people
that get accustomed to closures are indeed aware of the incurred danger and
are willing to pay the price as it comes with greater expressivity.


Xavier Clerc

[Rémi Forax]

fo...@x9c.fr a �crit :

[...]

> The blog entry does not give many details, but the unability to capture
> (non-final ?) variables is against the tradition of what is usually referred
> to as "closures". It is presented as a safeguard, but I think that people
> that get accustomed to closures are indeed aware of the incurred danger and
> are willing to pay the price as it comes with greater expressivity.
>

Perhaps the unability to capture (non-final ?) variables is against the
tradition but the main
use cases for closures in Java is the ability to express blocks of codes
that will run in parallel.
Multi-cores CPU are no more a wet dream :)

>
> Xavier Clerc
>
R�mi

[fo...@x9c.fr]

Selon R�mi Forax <fo...@univ-mlv.fr>:

> Perhaps the unability to capture (non-final ?) variables is against the
> tradition but the main
> use cases for closures in Java is the ability to express blocks of codes
> that will run in parallel.

And we all know that "final" is a synonym for "immutable" ...
No offense intended, but I had a good laugh.


Xavier Clerc

[John Wilson]

2009/11/27 <fo...@x9c.fr>:
> Selon Rémi Forax <fo...@univ-mlv.fr>:

Nitpick but final is a synonym for 'being assigned a value at most
once" which is quite different to "immutable". That is to say that a
final variable can have up to two values in its lifetime. One is the
default value for that data type the second is the value it is
assigned at initialisation (the initialisation may never happen
because of an exception being thrown). The Java closure spec will have
to take this into account (like the inner class spec already does).

The final attribute is not enforced by the JVM so some non Java
languages can (I believe) cause odd things to happen with values
declared final in Java.

Pedantry aside:) I think the major interest of non Java language
designers and implementers on the JVM is to ensure that the Java
Closure spec allows their Closures/Lambdas to appear as Java Closures
to Java and Java Closures appear as Closures/Lambdas in their
languages. This may or may not be high up on the priorities of the
Java guys but they have asked for community involvement so I would
suggest that those interested in alternative languages for the JVM get
involved and lobby for their interests.

John Wilson

[Patrick Wright]

> Pedantry aside:) I think the major interest of non Java language
> designers and implementers on the JVM is to ensure that the Java
> Closure spec allows their Closures/Lambdas to appear as Java Closures
> to Java and Java Closures appear as Closures/Lambdas in their
> languages. This may or may not be high up on the priorities of the
> Java guys but they have asked for community involvement so I would
> suggest that those interested in alternative languages for the JVM get
> involved and lobby for their interests.

I imagine when the first prototype is downloadable this would be a
good effort to pursue via this list--asking the various language
community leaders to see what integration issues there are and ensure
there is also communication between the language communities outside
of Java. The good thing is the communication channels to and from Sun
are open via the various mailing lists. This all could be exciting!


Cheers
Patrick

[fo...@x9c.fr]

Selon John Wilson <tugw...@gmail.com>:

> 2009/11/27 <fo...@x9c.fr>:
> > Selon R�mi Forax <fo...@univ-mlv.fr>:

> >
> >> Perhaps the �unability to capture (non-final ?) variables is against the
> >> tradition but the main
> >> use cases for closures in Java is the ability to express blocks of codes
> >> that will run in parallel.
> >
> > And we all know that "final" is a synonym for "immutable" ...
> > No offense intended, but I had a good laugh.
>
>
> Nitpick but final is a synonym for 'being assigned a value at most
> once" which is quite different to "immutable". That is to say that a
> final variable can have up to two values in its lifetime. One is the
> default value for that data type the second is the value it is
> assigned at initialisation (the initialisation may never happen
> because of an exception being thrown). The Java closure spec will have
> to take this into account (like the inner class spec already does).

Well, my answer was indeed sarcastic ...

The point is that "final" is a qualifier for a reference,
while the argument put forward by Remi Forax would hold if the
qualifier guaranteed that the value referenced is "immutable"
(counterexample: a "final" array is clearly mutable).
When playing with multicores, it seems that the properties that
you are interested in are related to immutability, and moreover
to the absence of side-effects at large. A guarantee that coincide
for sure with "finality" only for primitives types.
Hence the irony of my answer.


Xavier Clerc

[John Wilson]

2009/11/27 Patrick Wright <pdou...@gmail.com>:

> I imagine when the first prototype is downloadable this would be a
> good effort to pursue via this list--asking the various language
> community leaders to see what integration issues there are and ensure
> there is also communication between the language communities outside
> of Java. The good thing is the communication channels to and from Sun
> are open via the various mailing lists. This all could be exciting!

I would have thought first prototype was a bit late in the day.

It would be interesting to see on this list what people would like.

The most straightforward thing would be to have an interface or a
family of interfaces which an class could implement to allow dispatch
of the Closure method.

I haven't looked at what's been published about the proposed
implementation to tell if that fits in with the current intent.

John Wilson

[Alexandru Nedelcu]

On Fri, 2009-11-27 at 15:32 +0100, Rémi Forax wrote:
> Perhaps the unability to capture (non-final ?) variables is against the
> tradition but the main
> use cases for closures in Java is the ability to express blocks of codes
> that will run in parallel.
> Multi-cores CPU are no more a wet dream :)

Hi, sorry to chip in,

The problem in this case is probably the main use case, which is a
shortsighted one.

It's generics with type-erasure (with the screwed use-site variance) all
over again. And I'm pretty sure the main use case for the current
generics implementation was covered, but now looking in retrospective,
was it really worth it?

I am thinking about designing a new language on top of a subset of Java,
and assuming I go through with it, a closure in my language will be an
instance of an anonymous class that extends something like Func<TResult,
TVar1, TVar2...>.

If the type of the anonymous class is annotated with something like
@KeepSynTree, then the compiler will also assign to that class a
reference to the syntax tree of the function and a map with the captured
context (it's more or less what Linq does).

In the context of parallel processing, a library designer could take
these syntax trees and rewrite them or transform them to something else.

Imagine an ORM like LinqDB which transforms your closure into
conventional SQL, and then with only one change in your table model it
could work with a NoSQL storage that requires fork/join ... like the
storage used by FriendFeed which shards entries between multiple MySql
servers ... ( http://bret.appspot.com/entry/how-friendfeed-uses-mysql )
... which in the case of RANGE select would first do a query to the
relevant index, then it would issue async requests to all the servers
involved, and then would take the results and do further processing with
a fork/join algorithm that also offloads some workload to your GPUs. All
of this with the same syntax from the user's POV.

I would like to see such features coming in Java in regards to
parallelism, rather than conservatism in regards to the handling of
non-finals. And unfortunately I have to implement my own compiler (I say
unfortunately, because while fun, I need them yesterday).

[Rémi Forax]

Le 27/11/2009 17:33, Alexandru Nedelcu a �crit :

> On Fri, 2009-11-27 at 15:32 +0100, R�mi Forax wrote:
>
>> Perhaps the unability to capture (non-final ?) variables is against the
>> tradition but the main
>> use cases for closures in Java is the ability to express blocks of codes
>> that will run in parallel.
>> Multi-cores CPU are no more a wet dream :)
>>
> Hi, sorry to chip in,
>
> The problem in this case is probably the main use case, which is a
> shortsighted one.
>
> It's generics with type-erasure (with the screwed use-site variance) all
> over again. And I'm pretty sure the main use case for the current
> generics implementation was covered, but now looking in retrospective,
> was it really worth it?
>
> I am thinking about designing a new language on top of a subset of Java,
> and assuming I go through with it, a closure in my language will be an
> instance of an anonymous class that extends something like Func<TResult,
> TVar1, TVar2...>.
>

You should consider the use of MethodHandle,
method handles are reified, not Func<...>.

> If the type of the anonymous class is annotated with something like
> @KeepSynTree, then the compiler will also assign to that class a
> reference to the syntax tree of the function and a map with the captured
> context (it's more or less what Linq does).
>
> In the context of parallel processing, a library designer could take
> these syntax trees and rewrite them or transform them to something else.
>
> Imagine an ORM like LinqDB which transforms your closure into
> conventional SQL, and then with only one change in your table model it
> could work with a NoSQL storage that requires fork/join ... like the
> storage used by FriendFeed which shards entries between multiple MySql
> servers ... ( http://bret.appspot.com/entry/how-friendfeed-uses-mysql )
> ... which in the case of RANGE select would first do a query to the
> relevant index, then it would issue async requests to all the servers
> involved, and then would take the results and do further processing with
> a fork/join algorithm that also offloads some workload to your GPUs. All
> of this with the same syntax from the user's POV.
>
> I would like to see such features coming in Java in regards to
> parallelism, rather than conservatism in regards to the handling of
> non-finals. And unfortunately I have to implement my own compiler (I say
> unfortunately, because while fun, I need them yesterday).
>

If you want to implement an expression tree.
I've written a blog on how to implement that in Java
(only the runtime part):
http://weblogs.java.net/blog/2009/07/31/dlr-expression-tree-java

R�mi

[Rémi Forax]

Le 27/11/2009 16:56, fo...@x9c.fr a �crit :

In my opinion, what we want is immutability of shared object, not for
all objects,
side effects are Ok if they are sandboxed or if you mutate things
like concurrent collections

About final, final also have an impact on the publication of variables.
If bounded local variables aren't final, there is no guarantee.

int sum = 0;
for(int i=0; i<5; i++) {
final int value = i;
new Thread(#() {
sum + = i;
}).start();
}

The example above is not thread safe and if sum is declared volatile
(I suppose here that this is legal to do that) it is again not thread safe.

>
> Xavier Clerc
>

R�mi Forax