STG in Javascript

From HaskellWiki
Revision as of 18:29, 22 August 2006 by DimitryGolubovsky (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

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.

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
  a1:...,                               // argument 1
  aN:...                                // 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}

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.