Yhc/Javascript/Inner workings

From HaskellWiki
< Yhc‎ | Javascript
Revision as of 20:02, 16 November 2006 by DimitryGolubovsky (talk | contribs) (Added a section about internal indices)

Jump to: navigation, search

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

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
HSCons C *         Builds a list CONS cell head:
head element
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 of the function known by the compiler
expression to apply to function's arguments and evaluate
HSDly C       *   A special object to wrap around a saturated function call thunk:
saturated function call that is a HSFun object with number of arguments applied to (_a) equal to the function arity (_x); evaluation of this thunk will be delayed until it is applied to an argument which would have oversaturated the call in the absence of HSDly
HSData C         * Builds a data object other than a CONS cell or an Empty List con:
index of the constructor
a Javascript Array containing contructor arguments
_r P * * * * * Boolean: true when a thunk may be evaluated.
  • true in HSFun when the call is saturated (_a.length == _x)
  • Always true in HSDly
  • 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 unless the call is saturated (_a.length == _x) in which case it applies the function body (_b) to the accumulated arguments array (_a) and returns whatever the body returns
  • In HSDly, evaluates the delayed function call first and then applies the oversaturating arguments to the result (_ap), and returns whatever results from this (a non-function value or unsaturated function call or saturated function call wrapped in another HSDly object)
  • No action in HSCons, HSEOL, HSData
_a P     * *   Array:
  • in HSFun, holds accumulated arguments
  • in HSDly, holds oversaturating arguments
_ap M     * *   Apply function call/delayed saturated call to argument(s)
  • In HSFun, clones the HSFun object, and concatenates its argument to the accumulated arguments array (_a) of the copy. If the copy becomes a saturated call, sets it's _r property to true and returns the copy wrapped into HSDly, otherwise just returns the copy
  • In HSDly, clones the HSDly object and concatenates its argument to the oversaturating arguments array (_a) of the copy. No evaluation is done at this time; it will be performed by the _c method
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 saturated function call (HSFun object with _a.length == _x: the first argument of the HSDly constructor is copied here
_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.

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.

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:


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.

Special Notes


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.