Templates in FPL?

George Russell ger@tzi.de
Fri, 18 May 2001 18:22:07 +0200


The MLj compiler from ML to the Java Virtual Machine (which is being 
actively worked on by the geniuses at Microsoft as we speak) expands 
out all polymorphism.  I helped develop this compiler and I believe 
this approach to be a good one.  There are particular reasons why it's
good for this case
(1) as has been said before, ML does not have polymorphic recursion;
(2) the cost of object creation in Java used at least to be horrendous,
    so it was well worth working hard to get rid of it.
However I think long term it's a good idea for normal Haskell compilers
because my guess is you will Win Big on quite a lot of things, because
you don't have to carry around and use dictionaries (for method lookup
in class instances) and can do a lot more specialisation and inlining.
Strict values can also be unboxed.  Of course you can control specialisation 
used unboxed values already in Glasgow Haskell, but it requires special
annotations or special types.

The minus points are thuswise, so far as I know:
(1) the compiled code is bigger.  This means the code might indeed run
    more slowly.  But with MLj I think we found that in normal cases it
    isn't THAT much bigger (maybe about 50%), because the functions which
    get specialised a lot (like "length" and "map") tend to be pretty small.
    Of course you can construct artificial cases where the code size will
    explode.
(2) It takes much longer to compile.  I'm waiting for Moore's law here, but
    at present I would be surprised if (say) Glasgow Haskell could compile itself
    inlining out all polymorphism, without it taking a very long time or
    a very fast computer or lots of nasty imperative optimisations.
(3) You can't inline everything, because of polymorphic recursion, and
    also because it would be nice to allow Haskell code to be dynamically
    linked in (see GHCi).  Or you can inline everything, but then you
    need to implement a Haskell Virtual Machine which does the inlining
    (and the whole compiler backend) on demand at runtime.  I don't think
    you have to inline everything; it should surely be possible to leave
    polymorphic versions of the functions around, to use for hard cases.