STG in Javascript

Disclaimer: Here are my working notes related to an experiment to execute Haskell programs in a web browser. You may find them bizzarre, and even non-sensual. Don't hesitate to discuss them (please use the "Discussion" page). Chances are, at some point a working implementation will be produced.

A Javascript Shell is of great help for this experiment.

---

Aug 22, 2006

Several people expressed interest in the matter, e. g.: [1], [2].

A Wiki page Hajax has been recently created, which summarizes the achievements in the related fields. By these experiments, I am trying to address the problem of Javascript generation out of a Haskell source.

To achieve this, an existing Haskell compiler, namely nhc98, is being patched to add a Javascript generation facility out of a STG tree: the original compiler generates bytecodes from the same source.

After (unsuccessful) trying several approaches (e. g. Javascript closures (see [3]), it has been decided to implement a STG machine (as described in [4]) in Javascript.

The abovereferenced paper describes how to implemement a STG machine in assembly language (or C). Javascript implementation uses the same ideas, but takes advantage of automatic memory management provided by the Javascript runtime, and also built-in handling of values more complex than just numbers and arrays of bytes.

To describe a thunk, a Javascript object of the following structure may be used:

thunk = {
  _c:function(){ ... },                 // code to evaluate a thunk
  _1:...,                               // argument 1
  _2:...,
  _N:...                                // argument n
};

So, similarly to what is described in the STG paper, the c method is used to evaluate a thunk. This method may also do self-update of the thunk, replacing itself (i. e. this.c) with something else, returning a result as it becomes known (i. e. in the very end of thunk evaluation).

Some interesting things may be done by manipulating prototypes of Javascript built-in classes.

Consider this (Javascript shell log pasted below):

Number.prototype.c=function(){return this};
function(){return this}
(1).c()
1
(2).c()
2
(-999).c()
-999
1
1
2
2
999
999

Thus, simple numeric values are given thunk behavior: by calling the c method on them, their value is returned as if a thunk were evaluated, and in the same time they may be used in a regular way, when passed to Javascript functions outside Haskell runtime (e. g. DOM manipulation functions).

Similar trick can be done on Strings and Arrays: for these, the c method will return a head value (i. e. String.charAt(0)) CONS'ed with the remainder of a String/Array.

Aug 23, 2006

First thing to do is to learn how to call primitives. In Javascript, primitives mostly cover built-in arithmetics and interface to the Math object. Primitives need all their arguments evaluated before they are called, and usually return strict values. So there is no need to build a thunk each time a primitive is called.

At the moment, the following Haskell code:

f :: Int -> Int -> Int

f a b = (a + b) * (a - b)

g = f 1 2

compiles into (part of the Javascript below was inserted manually):

var HMain = {m:"HMain"};

Number.prototype._c=function(){return this;};

// Compiled code starts

HMain.f_T=function(v164,v165){return {_c:HMain.f_C,_w:"9:1-9:24",_1:v164,_2:v165};};
HMain.f_C=function(){
return ((((this._1)._c())+((this._2)._c()))._c())*((((this._1)._c())-((this._2)._c()))._c());
};

HMain.g_T=function(){return {_c:HMain.g_C,_w:"11:1-11:9"};};
HMain.g_C=function(){
return HMain.f_T(1,2);
};

// Compiler code ends

print(HMain.f_T(3,4)._c());

print(HMain.g_T()._c()._c());

When running, the script produces:

Running...
-7
-3

Note that the _c() method is applied twice to the output from HMain.g_T: the function calls f_T which returns an unevaluated thunk, but this result is not used, so we need to force the evaluation to get the final result.