Personal tools

STG in Javascript

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
 
Line 4: Line 4:
   
 
----
 
----
  +
  +
= Aug 22, 2006 =
   
 
Several people expressed interest in the matter, e. g.: [http://www.haskell.org//pipermail/haskell-cafe/2006-August/017286.html], [http://www.haskell.org//pipermail/haskell-cafe/2006-August/017287.html].
 
Several people expressed interest in the matter, e. g.: [http://www.haskell.org//pipermail/haskell-cafe/2006-August/017286.html], [http://www.haskell.org//pipermail/haskell-cafe/2006-August/017287.html].
Line 19: Line 21:
 
<pre>
 
<pre>
 
thunk = {
 
thunk = {
c:function(){ ... }, // code to evaluate a thunk
+
_c:function(){ ... }, // code to evaluate a thunk
a1:..., // argument 1
+
_1:..., // argument 1
a2:...,
+
_2:...,
aN:... // argument n
+
_N:... // argument n
 
};
 
};
 
</pre>
 
</pre>
Line 54: Line 56:
   
 
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.
 
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:
  +
  +
<pre>
  +
f :: Int -> Int -> Int
  +
  +
f a b = (a + b) * (a - b)
  +
  +
g = f 1 2
  +
</pre>
  +
  +
compiles into (part of the Javascript below was inserted manually):
  +
  +
<pre>
  +
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());
  +
</pre>
  +
  +
  +
When running, the script produces:
  +
  +
<pre>
  +
Running...
  +
-7
  +
-3
  +
</pre>
  +
  +
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.

Revision as of 11:34, 23 August 2006

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.


1 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.

2 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.