[Sablevm-developer] Issues with FP mappings to the JVM

[Brent F. <bre...@xp...>]

The issue most functional programming languages have when "compiled"
into JVM bytecode seem to fall into two areas (drawn from the Wakeling,
J. Functional Programming January 1998):

1.  Things that can be done inside the JVM without changing the API:

(a) Poor memory allocation performance:  Functional languages such as
Haskell or Scheme tend to do a lot of memory allocation.  A full order
of magnitude slowdown on the JVM has been documented as a result of 
memory allocation issues.  A more efficient memory allocator would
greatly improve performance in this area.

(b) ?? Tail-recursion:  (Quoting from Wakeling, '98) "In functional 
programs, the result of one function application is often given by 
another with exactly the right number of arguments. ... an implementation
can save stack space by ensuring that the two function calls use the 
same frame.  But the JVM specification does not require that tail 
recursive method invocations use the same stack frame.  As a result,
a straightforward implementtion of a tail recursive functional program
... could easily overflow the stack".  The benefits here are obvious,
but I'm not sure how this would be implemented.

2.  Things that require and API change.

(a)  Stack reduction:  (Paraphrasing Wakeling, '98)  Lazy functional 
languages (Haskell) are often implemented using some form of Graph
Reduction in which expressions are represented by graphs, which are
then simplified until the final result is obtained.  Apparently, many
implementations make use of a 'reduction stack', which holds pointers
to the graphs representing parts of expressions, etc.  Since there is
no way to represent such pointer-to-object semantics in the JVM 
because there is no way to access the JVM stack.  Representing these
constructs in Java through arrays is costly because of the memory
issues I mentioned above, plus bounds checking cost.  This issue may
be eased somewhat by a better memory allocator -- I think this option
should be set aside for the time being, as I have no idea how to
attack it.

And that's about it.  It seems we could make some good progress by
trying to address 1.(a) and 1.(b).  I suspect 1.(a) might not be too
difficult to address.

Christian Tismer (and others) implemented a so-called "stackless" 
variant of the Python compiler/interpreter.  I wonder if any of the
techniques he used could enhance the SableVM system?  I'm cc'ing
him so I don't inadvertently put words in his mouth, but he took
a look at Kaffe at one point to see if he could generate a 'stackless'
version, but felt there were serious architectural issues.  Perhaps
he could give us his reasons, and Etienne could comment on whether
the same design trade-offs were made with SableVM.

Thanks,

-Brent