Personal tools

Yhc/Javascript/Inner workings

From HaskellWiki

< Yhc | Javascript
Revision as of 15:00, 21 November 2006 by DimitryGolubovsky (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

In this section, internal structure of Javascript objects and runtime support algorithms is reviewed.

Contents

1 Structure of Javascript Objects

The table below summarizes types of Javascript objects used in the ycr2js generated Javascript code.

Javascript Object Types and Their Methods and Properties
Member/
Constructor
Prop
Meth
Constr
H
S
C
o
n
s
H
S
E
O
L
H
S
F
u
n
H
S
D
l
y
H
S
D
a
t
a
Description/Arguments
HSCons C *         Builds a list CONS cell head:
head element
tail:
remainder of the list
HSEOL C   *       Final element of a list or an empty list  
HSFun C     *     Creates a function thunk with no arguments applied to name:
function name to be used for debugging/exception tracing
arity:
arity of the function known by the compiler
body:
expression to apply to function's arguments and evaluate
HSDly C       *   A special object to hold arguments a function is applied to: these objects form a stack adding an element with every application fun:
a HSFun object applied to arguments this instance of HSDly holds
up:
a HSFun or HSDly object up stack
targs:
arguments to be held in this object
HSData C         * Builds a data object other than a CONS cell or an Empty List con:
index of the constructor
arrs:
a Javascript Array containing contructor arguments
_r P * * * * * Boolean: true when a thunk may be evaluated.
  • true in HSFun if represents a nullary function
  • true in HSDly if number of arguments accumulated in the stack is equal or exceeds the delayed function arity (_d._x)
  • Always false in HSCons, HSEOL, HSData
_c M * * * * * Evaluate a thunk. If this method is said as "has no action", this means that it just returns this and does nothing else.
  • No action in HSFun for arity > 0; otherwise it invokes the function body (_b) and returns whatever the body returns
  • In HSDly, retrieves arguments from the stack (following the chain of objects linked by their _u properties until meets one with _u == null , splits the arguments obtained into saturating and oversaturating (if any) portions, evaluates the delayed function call first applying it to the saturating portion of arguments and then carries the oversaturating arguments over reusing itself and linking itself upstack to whatever the delayed function returned.
  • No action in HSCons, HSEOL, HSData
_a P       *   Array:
  • holds the portion of arguments from the current application
_ap M     * *   Apply function call/delayed saturated call to argument(s)
  • In HSFun, creates a new HSDly object with fun and up pointing to this, and targs referring to _ap's arguments, that is, creates one more level of stack
  • In HSDly, creates a new HSDly object with fun pointing to this._d, up pointing to this and targs referring to _ap's arguments, that is, creates one more level of stack
targs:
Array containing the arguments to be applied to
_b P     *     Holds the expression to apply to function's arguments and evaluate: the third argument of the HSFun constructor is copied here
_x P     *     Holds the function arity: the second argument of the HSFun constructor is copied here
_n P     * *   Holds the function name: the first argument of the HSFun constructor is copied here
_d P     * *   Holds the delayed function object reference: the first argument of the HSDly constructor is copied here; in HSFun always points to this
_y P     * *   Holds the total number of arguments accumulated in the stack
_u P     * *   Holds the up stack reference; in HSFun is always null
_t P * *     * Constructor index for a Data or a CONS/Empty list cell to be used for pattern matching
  • In HSData, contains index of the constructor that created the Data object
  • In HSCons, always contains 3 (index of Prelude.:)
  • In HSEOL, always contains 2 (index of Prelude.[])
_f P * *     * Constructor arguments (may be empty)
  • In HSData, the second argument of the HSData constructor is copied here
  • In HSCons, this is an array of two elements: copies of the first (head) and the second (tail) arguments of the HSCons constructor
  • In HSEOL, always empty
toString M *         Method of Object overridden by HSCons. Used for unmarshalling of Haskell lists (including Strings) into Javascript as Strings. The method evaluates all elements of the list (therefore it should be finite) and if the list contains characters, they are concatenated into a Javascript String, otherwise the _toArray method is called, and the toString method is called upon _toArray's result.
_toArray M *         Method used for unmarshalling of Haskell lists (including Strings) into Javascript as Arrays. The method evaluates all elements of the list (therefore it should be finite) and concatenates them into a Javascript Array. Internal representation of Haskell type Char is its numeric value, so a Haskell String will be converted into a Javascript Array of Number's.

2 Evaluation of Expressions

The Javascript runtime support library provides a function exprEval which is used to evaluate all expressions starting with the toplevel expression (starting point).

In essence, this function looks like this:

function exprEval (e) {
  for (var ex = e; ex != undefined && ex._r ; ex = ex._c())
    ;
  return ex;
};

This is a loop that checks whether a given expression exists (not undefined) and can be evaluated (_r == true). In this case, it calls the expression's _c method and analyzes its return. If the returned expression also may be evaluated, the function loops and evaluates it. This is repeated until an expression that no longer can be evaluated is returned (normal situation, e. g. a primitive value or a Data object), or an undefined value is returned (this is abnormal situation).

While evaluating an expression, exprEval may be recursively called to evaluate nested expressions.

3 Internal Indices

To optimize size and performance of generated Javascript code, names of constructors and functions are indexed. The Javascript Runtime support library declares three global variables to serve as indices: conIdx, funIdx, and strIdx. First two indices map constructor or function name into an internal index, the latter maps internal index to a name.

Indexation of constructors gives an advantage to reduce pattern matching to comparison of primitive values. Indeed, to match on a constructor name, say, Module_46MyData, two strings have to be compared. By indexing constructor names, and storing indices in HSData objects, only primitive indices have to be compared which can be done much faster.

Value stored in the _t member of a HSData object may be either a positive number, or, with the help of Javascript untypedness, a primitive boolean (true/false). Indices are assigned sequentially by the converter right before Javascript generation. Certain special constructors are forced to have special index values:

Prelude.True true
Prelude.False false
Prelude.[] 2
Prelude.: 3

Because of constructor name indexing, user-written Javascript code should obtain correct constructor index for using with HSData like this:

return new HSData(conIdx['Echo.JS'],[new Number(exprEval(a))]);

Developers should not not try to make any assumptions about possible value of constructor index.

The index of functions named funIdx helps map external names of Haskell functions into internal indices used in the generated Javascript code. It contains only entries for names of functions which were used as reachability roots when the linked core was built.

In order to call a Haskell function from Javascript code by name, its index should be obtained like this:

funIdx['Echo.main']

Name of the function must be qualified.

The last index, named strIdx helps find function name by its internal index which may be useful for debugging purposes and exception tracing. It has entries for functions defined in the Haskell source and few others, but functions appearing as result of lambda-lifting are usually excluded.

4 Special Notes

4.1 Oversaturation

Oversaturation happens when a function thunk (HSFun object) is applied to more arguments than function arity (_x).

For example, this piece of Haskell code:

  let g = fst tup
      x = g (5::Int) (6::Int)

converts into the following Javascript (indentation manual):

var Bug_46Bug_46Prelude_46217_46g=
  new HSFun("Bug.Bug.Prelude.217.g", 0,  function(){
    var v285=new HSFun("v285", 0, function(){
      return  Prelude_46Prelude_46Num_46Prelude_46Integer;}
    );
    return (Prelude_46fst)._ap([(Bug_46tup)._ap([v285])]);
  });
var Bug_46Bug_46Prelude_46218_46x=
  new HSFun("Bug.Bug.Prelude.218.x",  0,  function(){
    return (Bug_46Bug_46Prelude_46217_46g)._ap([5, 6]);
  });

As it can be clearly seen, g is defined with arity = 0 which is reasonable: its definition does not have any formal arguments. But when computing x, g is called with two arguments: 5 and 6.

To preserve laziness, the thunk of g should not be evaluated earlier than it is actually needed, i. e. when the value of x is needed. Calling the _ap method of g would have resulted in oversaturation and inevitable error in computations.

To work this around, logics of HSFun._ap method was changed, and special object type HSDly was introduced. HSFun._ap may accept any number of arguments in an array. Length of the array of arguments is compared with number of arguments needed to saturate the call. If the call becomes under- or completely saturated after the arguments have been applied to, no special action is taken: undersaturated call remains the same, saturated is wrapped in HSDly. If however oversaturation is about to happen, portion of arguments necessary to saturate the call is absorbed into the accumulated arguments array, and the rest of arguments are carried over to the HSDly._ap method.

Behavior of HSDly objects is as follows: the _ap method accepts as many arguments as provided, and accumulates them inside. The _c method evaluates the delayed thunk first, and then calls its _ap method with all the arguments accumulated up to the moment. In this case it is expected that the delayed thunk will evaluate into another function call (as can be seen in the example above). These actions may lead to either a value computed as result of application, or another function call, under-or completely or over-saturated. In the two latter cases, the result will be wrapped into another HSDly object with arguments remaining carried over.