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.
The 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); // NB should be HMain.f_T(1,2)._c()
};
// Compiler code ends
print(HMain.f_T(3,4)._c());
print(HMain.g_T()._c()._c());
When running, the script produces:
Running... -7 -3
So, for each Haskell function, two Javascript functions are created: one creates a thunk when called with arguments (so it is good for saturated calls), another is the thunk's evaluation function. The latter will be passed around when dealing with partial applications (which will likely involve special sort of thunks, but we haven't got down to this as of yet).
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.
NB: indeed, the thunk evaluation function for HMain.g should evaluate the thunk created by HMain.f_T. Laziness will not be lost because HMain.g_C will not be executed until needed.
Sep 12, 2006
To simplify handling of partial function applications, format of thunk has been changed so that instead of _1, _2, etc. for function argument, an array named _a is used. This array always has at least one element which is undefined. Arguments start with array element indexed at 1, so to access an argument n, the following needs to be used: this._a[n].
For Haskell programs executing in a web browser environment, analogous to FFI is calling external Javascript functions. Imagine this Javascript function which prints its argument on the window status line:
// Output an integer value into the window status line
putStatus = function (i) {window.status = i; return i;};
To import such a function is a Haskell program, the following FFI declaration is to be used:
foreign import ccall "putStatus" putStatus :: Int -> Int
Note the type signature: of course it should be somewhat monadic, but for the moment, nothing has been done to support monads, so this signature is only good for testing purposes.
The current NHC98-based implementation compiles the above FFI declaration into this:
Test2.putStatus_T=function(_1){return {_c:Test2.putStatus_C, _w:"7:1-7:56", _a:[undefined, _1]};};
Test2.putStatus_C=function(){
return (putStatus)((this._a[1])._c());
Note that like a primitive, a foreign function evaluates all its arguments before it starts executing.
A test page illustrating this can be found at:
http://www.golubovsky.org/repos/nhcjs/test2.html
When this page is loaded, the window status line should display "456" while the rest of the page remains blank. The Haskell source for this test page is: