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.