Compiling Lazy Functional Programs Based on the Spineless Tagless G-machine for the Java Virtual Machine

A systematic method of compiling lazy functional programs based on the Spineless Tagless G-machine (STGM) is presented for the Java Virtual Machine (JVM). A new specification of the STGM, which consists of a compiler and a reduction machine, is presented; the compiler translates a program in the STG language, which is the source language for the STGM, into a program in an intermediate language called L-code, and our reduction machine reduces the L-code program into an answer. With our representation for the reduction machine by the Java language, an L-code program is translated into a Java program simulating the reduction machine.The translated Java programs also run at a reasonable execution speed. Our experiment shows that execution times of translated benchmarks are competitive compared with those in a traditional Haskell interpreter, Hugs, particularly when Glasgow Haskell compiler’s STG-level optimizations are applied.