Manuel Serrano
email: manuel.serrano@inria.fr

JavaScript AOT Compilation

Keywords:

Static compilation, a.k.a., ahead-of-time (AOT) compilation, is an alternative approach to JIT compilation that can combine good speed and lightweight memory footprint, and that can accommodate read-only memory constraints that are imposed by some devices and some operating systems. Unfortunately the highly dynamic nature of JavaScript makes it hard to compile statically and all existing AOT compilers have either gave up on good performance or full language support. We have designed and implemented an AOT compiler that aims at satisfying both. It supports full unrestricted ECMAScript 5.1 plus many ECMAScript 2017 features and the majority of benchmarks are within 50% of the performance of one of the fastest JIT compilers.

Introduction

Nowadays, JavaScript is no longer con ned to the programming of web pages. It is also used for programming serverside parts of web applications, compilers (Microso 2013), and there is a growing trend for using it for programming internet-of-things (IoT) applications. All major industrial actors of the eld are looking for, or are already providing, Java-Script based development kits (IoT.js, Espruino, JerryScript, Kinoma.js, …). In this application domain, JavaScript programs execute on small devices that have limited hardware capacities, for instance only a few kilobytes of memory. Justin-time (JIT) compilation, which has proved to be so e ective for improving JavaScript performances [START_REF] Chang | Tracing for web 3.0: trace compilation for the next generation web applications[END_REF]Chevalier-Boisvert andFeeley 2015, 2016;[START_REF] Gal | Trace-based just-in-time type specialization for dynamic languages[END_REF], is unthinkable in these constrained environments. ere would be just not enough memory nor CPU capacity to execute them at runtime. Furthermore memory write operations on executable segments are sometimes impossible on the devices, either because of the type of memory used (ROM or FLASH) or simply because the operating system forbids them (iOS for instance). Pure JavaScript interpreters are then used, but this comes with a strong performance penalty, especially when compared to assembly or C programs, that limits the possible uses. When JIT compilation is not an option and when interpretation is too slow, the alternative is static compilation, also known as ahead-of-time (AOT) compilation. However, this implementation technique seems not to t the JavaScript design whose unique combination of antagonistic features such as functional programming support, high mutation rates of applications, introspection, and dynamicity, makes most known classical AOT compilation techniques ine ective.

Indeed, JavaScript is hard to compile, much harder than languages like C, Java, and even harder than Scheme and ML two other close functional languages. is is because a JavaScript source code accepts many more possible interpretations than other languages do [START_REF] Gong | JITPROF: Pinpointing JIT-unfriendly JavaScript Code[END_REF]. It forces JavaScript compilers to adopt a defensive position by generating target codes that can cope with all the possible, even unlikely, interpretations.

Let us illustrate this problem with a running example. It shows well-known JavaScript folklore, but readers unfamiliar with this language might nd it helpful to grasp the challenges that must be overcome to implement JavaScript e ciently. Let us consider the following statement: while( i < a.length ) sum += a[ i++ ];

It seems innocuous, especially to C and Java programmers that will see here nothing more than a mundane loop summing all the elements of an array. e assembly code that compilers are expected to generate, is easy to guess as a mere isomorphic translation would already be e cient.

With JavaScript, this is another story. Of course, as with C and Java, the code fragment can be used to sum array elements, but it can also be used di erently, for instance for summing the a ributes of an arbitrary object as in:

var a = { length: 3; 1 : 1, 3 : 3, 2 : 2 }; while( i < a.length ) sum += a [ i++ ];

is is worrisome for the compiler that cannot assume that the elements to sum are stored consecutively in memory. To keep the thing relatively simple, let us assume that a is indeed an array. e problem posed to the compiler is still far from simple. JavaScript supports sparse arrays, so a being an array is not enough for assuming that the elements are aligned. Even worse, because of the prototype chaining, it might well be that some elements are stored in another object, as in:

Since the element 2 is removed from a, the prototype chain is followed when the element a[2] is fetched, which yield the value 28. Obviously, with such data structures, the assembly code generated for this JavaScript loop is unlikely to look like a mere iteration over a couple of assembly instructions that fetch and sum consecutive memory locations! e index i also deserves some a ention as nothing imposed it to be an integer. For instance, it could well be a oating-point number or, more interestingly, a string, or any other object that will then be converted into either a number or a string at runtime. For the example, let us consider that i is a string. In that case, the i++ expression rst converts the initial string into a number and then increments it.

Even more challenging, let us replace i++ with i+=1. In JavaScript i++, i+=1, and i=i+1 are not all semantically equivalent, when type conversions are involved. When i is a string, i+=1 no longer adds the integer 1 but it appends a su x "1" to the string. is enables a yet another input data type to be used with the program. For instance, the following program, also adds 3 (0+1+2) to the sum variable var i = 0 var a = { length: 011 , 0 : 0, 01 : 1, 011 : 2 }; while( i < a.length ) sum += a[ i += 1 ]; Notice that it is still possible and correct, to use this version of the loop, with a being an array and i being an integer! Finally, notice that we have only studied the modi cations of the type and shape of variables i and a, but of course it might be possible as well to use various types for the variable sum, with other interesting challenges for the compiler.

is example illustrates that in general compilers can assume very li le about JavaScript programs. e situation is worsened further by the raise as li le errors as possible principle that drives the design of the language. JavaScript functions are not required to be called with the declared number of arguments, fetching an unbound property is permi ed, assigning undeclared variables is possible, etc.

All these di culties seem to prevent classic static compilers to deliver e cient code for a language as dynamic and as exible as JavaScript. We do not share this point of view. We think that by carefully combining classical analyses, by developing new ones when needed, and by cra ing a compiler where the results of the high-level analyses are propagated up to the code generation, it is possible for AOT compilation to be in the same range of performance as fast JIT compilers.

is is what we a empt to demonstrate with this study. Of course, our ambition is not to produce a compiler strictly as fast as the fastest industrial JavaScript implementations.

is would require much more engineering strength than what we can a ord. Instead, we only aim at showing that static compilation can have performances reasonably close to those of fastest JavaScript implementations. Reasonably close is of course a subjective notion, that everyone is free to set for himself. For us, it means a compiler showing half the performances of the fastest implementations. We will show in Section 7 that this objective has been reached or is closed to be reached for many benchmarks.

We have developed such a static compiler. It is named Hopc. It supports the full unrestricted ECMAScript 5.1 and many features of ECMAScript 6 (ECMA International 2015). It passes all the ECMAScript 5.1 test262-51 (ECMA International 2016) test suite and many other compatibility tests such as the Kangax test suite [START_REF] Kangax | ECMAScript Compatibility Table[END_REF], the MDN examples, and most Nodejs tests. is paper focuses on how it uses type information to generate e cient code. It is organized as follows. Section 2 presents the main structure of the compiler. Sections 3-6 overview the typing analyses we have developed and some parts of the code generator. Section 7 presents a performance evaluation and Section 8 presents the related work.

AOT Compilation

e syntax of a JavaScript program gives a general information about its meaning, but it gives almost no clue about the nature of the values it manipulates, as the while loop example of Section 1 that has been used with all sorts of data. JIT compilers wait until they receive the actual values to compile a program. When they generate the target code, they know both the static structure of the program and the dynamic memory layout of the data. So, they are able to approach the performance of compilers of more static languages that know these two things statically.

We have accommodated the principle of JIT compilation customization [START_REF] Chambers | Customization: Optimizing Compiler Technology for SELF, A Dynamically-Typed Object-Oriented Programming Language[END_REF] to AOT compilation by generating two versions for each function: a generic version that can cope with all the possible interpretations, and an optimized customized version, specialized for speci c data representation. In order to decide which customized versions to generate, Hopc extracts as much as possible information from the source code. Modular compilation, a.k.a., separate compilation, prevents it to always being able to make such deductions. In that case, it speculates beforehand on the data structures that are likely to be used by the exported functions.

e key principle of the speculation is the following assumption. e most likely data structure a program will use is the one for which the compiler is able to produce its best code.

e intuition behind the speculation is that the best code will be generated for stable, simple, and classical data structures that are used for implementing classical algorithms. In other words, the data structures that are likely to correspond to the programmer's intentions. In the example of Section 1, many data types and many usages are possible. However, the most likely one is the iteration over a at array of numbers.

is is the principle that governs Hopc design. Hopc uses many analyses and optimizations. Some are simple adaptations to JavaScript of existing analyses. ese are not presented in this paper because already described in the literature. For instance, the Scope Narrowing optimization that is a pre-requisite to all other analyses is not presented here because it is a direct adaptation of Scheme's letrec compilation [START_REF] Ghuloum | Fixing Letrec (reloaded)[END_REF][START_REF] Waddell | Fixing Letrec: A Faithful Yet E cient Implementation of Scheme's Recursive Binding Construct[END_REF]. Others are new or adapted to t JavaScript.

• Data-ow Type Analysis performs a type analysis that is used to establish the hint typing hypotheses. It is based on the occurrence typing [START_REF] Kent | Occurrence Typing Modulo eories[END_REF][START_REF] Tobin-Hochstadt | Logical Types for Untyped Languages[END_REF] but it is presented here to show that in spite of the JavaScript highly dynamic nature, useful type information can be computed statically. e main originality of this contribution is not the analysis itself that is based on [START_REF] Logozzo | RATA: Rapid Atomic Type Analysis by Abstract Interpretation -Application to JavaScript Optimization[END_REF] but the way its results are used by the code generator to avoid boxing and tagging and to implement array indices e ciently. Type information alone is not enough to generate fast code. For that, the compilation chain has to include all sorts of optimizations such as inline property caches, closure allocation, function inlining, data-ow analysis, register allocation, etc. Hopc includes many of them but it is out of the scope of the present paper to describe them all. We have chosen to only focus on the code generation for array accesses (Section 6) because it is a di cult and characteristic problem posed by the JavaScript compilation and also because arrays are ubiquitous in JavaScript programs.

Data-ow Type Analysis

Types improve the quality of the generated code by enabling the compiler to eliminate runtime tests and to use e cient data representations. In Hopc, types are collected using four di erent analyses, each re ning the information collected by the others. e st analysis is a data-ow type analysis. It is based on the occurrence typing [START_REF] Kent | Occurrence Typing Modulo eories[END_REF][START_REF] Tobin-Hochstadt | Logical Types for Untyped Languages[END_REF].

e Data-Flow Type Analysis distinguishes variable declarations and variable references. It assigns a potentially di erent type to each occurrence of the same variable. For that, it follows the execution ow and gathers the explicit and implicit type information the program contains. Let us illustrate its behavior on the following de nition: e variable o is explicitly checked on line 2. In the positive branch the type string is associated to the variable. For a similar reason it is associated the type number on line 3. On line 4, it is only checked if toString is a property of o. is implies that in the following execution ow o is of type object (line 4 and 5), as the operator in requires its right-and-side argument to be an object, and raises an error otherwise. We call this an implicit type check.

Typing algorithm

For the sake of simplicity, we present a simpli ed version of the algorithm actually implemented in Hopc. We consider only a subset of the actual source language, where throw, break, and continue are omi ed and where return is considered always in tail position. Under these assumptions, the typing algorithm can be presented as a set of inference rules. e language we consider is:

= | nil | bool | object | ... | τ → τ
Γ is a type environment mapping variables to types. Each program location is associated with one type environment.

A type judgment is of the form [Γ inst ⇒ τ , Γ ]), meaning that the instruction inst is of type τ and evaluating that instruction modi es the type environment into Γ . As statements are only evaluated for their side-e ect, they produce no value and their judgments are wri en [Γ s ⇒ ⊥, Γ ]. e core typing rules are given in Figure 1. All types are subtypes of the type any also noted . ⊥ is a fake type designating the lack of precise type information. We denote Γ 1 Γ 2 the least upper bound of Γ 1 and Γ 2 . Γ\{x } designates the environment where the variable x is ltered out. When an expression e evaluates to a function, we denote e ↓bod its body.

e typing algorithm does not keep track of values stored in objects. As such, the typing of the property access Property is typed with . Typing object properties has the potential of signi cantly helping the compiler producing be er code. It will be studied in future work. Function calls are split in two rules. Call is used when the called function is known statically. e type of the expression is the return type of the function and the typing environment is extended with that of the called function. Funcall is used otherwise.

e type of the expression is unknown (⊥) and all mutated variables are stripped of the typing environment. In our actual implementation, only the mutated global variables and the mutated local variables that appeared free in at least one function are removed from the typing environment. For both calls, the potential side e ects of the function expression and the argument expression are propagated to the produced type environment. Not accounted by the Call rule, when a constant function is called, the types of the actual argument values are accumulated. When a function is used as a reference, that is not in the syntactic position of a function in a call, the type is assigned to its argument.

e If rule types separately its two branches. e type environment it produces is the least upper bound of the type environments computed for the two branches. To compute it, when two types are not strictly equal, they are merged into the type . e peculiarity of the While rule comes from the handling of the side e ects that might occur when evaluating the test and the body, as illustrated by the following examples:

When entering the rst while, the variable x is known to be an integer, a er one iteration, its type has changed to string. A er executing the second while the variable x is a string, as the body is never evaluated.

Collecting types

We now consider an extension of the core language that enables the typing algorithm to infer types from the program control-ow by using the additional rules given in Figure 2.

e rules Typeof, TypeofTrue, and TypeofFalse are used for typing conditional expressions whose tests compare a variable value to a type name. ese rules use the additional function T N ame that maps a type to its external type name (for instance, in JavaScript the bool type is named boolean).

e rule Typeof types the then branch of the conditional statement with an environment where the variable x is known to be of type τ . It applies when no precise type information is known about the variable. When the type of x is known then either TypeofTrue or TypeofFalse applies and only the live branch is typed.

e instanceof typing shares similarities with typeof. In the then branch of a test, the variable is known to be an object. Additionally the rule also assigns the type function to its right-hand-side expression, as it is required to be a function.

is is visible in the VInstOfV rule. A similar reasoning is used for the Call rule, where the variable x is known to be a function in the rest of the evaluation, and for the in rule where x is known to be an object.

e other rules (Binop, SLength, and SIndexOf) are straightforward. Although not presented here, the compiler uses many other similar rules for typing known library functions and other operators.

Control ow breaks

e occurrence typing has been introduced in the context of the Scheme programming language, which is an expressionbased functional language. JavaScript is statement-based and this demands to adapt the occurrence typing to cope with the control ow operators the language provides. Let us consider the following example: control breaks are optional. at is, from the typing point of view, it is enough to consider the function h equivalent to:

1 function f() { 2 function h( x ) { 3 if( x > 0 ) throw x;
function h( x ) { if( x > 0 ) throw x; if( fake ) errno = 3; }
To implement this solution, we extend the language as follows:

statements s ::= ... | break | continue | throw e
and we add a new parameter to the typing rules. It accounts for the presence of breaks in the control ow. It is true if an instruction may break or return. It is f alse otherwise. Type judgments become Γ inst ⇒ τ , κ, Γ . Figure 3 we add three rules for the new statements (Break, Cont, and Throw). We modify the ,Return rule as we no longer impose it to be terminal and we split the Seq rule in two. If the rst statement of a sequence does not break, its typing is unchanged. If it breaks, the sequence is typed as a conditional instruction, meaning that the resulting typing environment is the merge of those of the two sub-statements (rule SeqBrk). Provided with these additional rules, the data-ow typing can cope with the full JavaScript language.

Wrap up

A er the data-ow analysis completes, the compiler executes another traversal of the tree to assign precise types, i.e., types that are neither or ⊥, to local variables and formal parameters for which the analysis has proved that a single type is preserved at all initialization and assignment locations.

is yields a decorated AST of the program where types are added to variable declarations and variable references.

4 Hint Typing e data-ow type analysis collects types for all occurrences of all variables and formal parameters but it looses track of values when: i) functions are exported, ii) functions are used as closures, iii) values are stored in data structures. e hint typing helps in these situations. It re nes the inferred types, and restarts the whole typing process with these more precise pieces of information. A x point iteration proceeds until no new type is collected.

e hint typing consists in traversing the program, scanning variables references in order to allocate heuristic types, or hints, to variable occurrences that the data-ow typing has not been able to determine precisely. Hints are assigned according to the syntactic contexts of the references and to the types already collected. Once hints have been collected, the most likely type of each yet untyped function parameter is elected and the function de nition is duplicated for the specialized typed arguments. e initial calls for which the argument types match are replaced with calls to the specialized function.

Let us illustrate this principle with the reverse function below that reverses the elements of an array-like data structure.

e example also de nes two other functions, areverse that calls reverse with an array, and oreverse that calls it with an object. is polymorphic use confuses the data-ow analysis that merges the two types, array and object, into a single any type. e source code below shows the function de nitions and the types inferred by the data-ow typing, expressed using the TypeScript syntax: In the function reverse, the expression a.length/2 reveals that the variable a is likely to be an array or a string, as these are the two widely used JavaScript primitive types that have a length property. is suspicion is strengthened by the expression a[i] that suggested an indexed access. Array type is even more suspected as strings are generally not accessed character by character but rather using API methods or regular expressions. e hypothesis of a being a string is de nitively invalidated by the expression a[i]=v as JavaScript strings are immutable. Using that reasoning, the hint typing allows us to transform this program into: function reverse$$A(a:array):array { for( let i:int = 0; i < aLen(a)/2; i++ ) { v = aRef( a, aLen(a)-1-i); aSet(a, aLen(a)-1-i, aRef(a, i)); aSet(a, i, v); } } function reverse$$(a:any):any { for( let i:int = 0; i < a.length/2; i++ At the price of a code growth, the new code is faster because the array accesses have been specialized.

) { let v = a[ a.length-1-i ]; a[ a.length-1-i ] = a[ i ]; a[ i ] = v; } } const
is enables two additional optimizations: an array bound checking optimization (Section 5) and the inlining of array accesses (Section 6).

Hints and type likelihood are computed with rules of the form:

[ [ inst x ] ] → H(x , h 1 , w 1 ), ..., H(x , h n , w n )
which reads as follows: for each occurrence of the instruction inst x involving the variable x, x could have the type h 1 with weight w 1 , …, and type h n with weight w n . When all hints have been computed, a type likelihood is computed for all yet untyped formal parameters. e most likely type is selected and the function is duplicated accordingly. Two rules supplements this overly simple heuristic. In case of equally likely types, the ordering array < string < object applies. When a parameter is i) wri en in the function and ii) hinted as being potentially an object and either null or undefined, no specialization takes place because the compiler will not be able to use the parameter type annotation to generate be er code.

Figure 4 shows a signi cant sample of the rules used by the compiler, where the notation T (e) designates the type of e. e rules apply to a version of the language extended with binary operators, increment, and switch statements. Rules 1, 2, and 3 handle property accesses. Rule 2 and 3 re ne rule 1 by observing that when the property name is an integer or the string "length", the accessed data structure is likely to be an array or a string. Rules 3 and 4 handle property assignments. e weights are chosen to rule out the string type. e rules 6-9 are examples of the numerous rules that handle unary and binary operators. Rule 10 is more interesting. It says that if all the case expressions of a switch are of a certain type τ , the tested expression is then likely to be of that type τ . When two rules apply for the same expression, the hints and weights are summed up. For example, for the expression x++ % y, the two rules H (x, int, 1), H ( , int, 1) apply. Let us show how these rules apply to the reverse function. is establishes that array is the most likely type for the variable a and the compiler will then generate e cient specialized code for that type.

[ [ a[ length ] ] ] by rule (1) ⇒ H(a, object, 1) [ [ a[ length ] ] ] by rule (3) ⇒ H(a,
(

1) [ [ x [e] ] ] → H(x , object, 1) (2) [ [ x [e] ] ] ∧ T (e) = int → H(x , array, 2), H(x , string, 2) (3) [ [ x [ length ] ] ] → H(x , array, 2), H(x , string, 2) (4) [ [ x [e]=e ] ] → H(x , object, 2) (5) [ [ x [e]=e ] ] ∧ T (e) = int → H(x , array, 3) (6) [ [ x << ] ] → H(x , int, 1), H( , int, 1) (7) [ [ x % ] ] → H(x , int, 1), H( , int, 1) (8) [ [ x +e ] ] ∧ T (e) = num → H(x , num, 1) (9) [ [ x ++ ] ] → H(x , int, 1) (10) [ [ switch(x ){case e 1 :...case e n :} ] ] ∧ ∀i ∈ [1..n] T (e i ) = τ → H(x , τ , 1)
Figure 4. Hint typing rules.

Conclusion and further comments

Once hints are computed and functions duplicated, the AST is cleaned up. e function specialization makes it possible to resolve statically some type checks and to remove dead-code.

For some programs, it also happens that the generic function de nition is never used and then removed from the tree. When these simpli cations are applied, the whole typing process restarts. Each iteration improves the opportunities of discovering and re ning new types. In the current version of the compiler, the granularity of the code duplication is the function but it might be worth investigating ner grain duplication, for instance for duplicating loops. Currently, speed is traded for size because functions are duplicated only once, which ensures the computation termination. e hint typing stage delivers a decorated AST. Variable declarations and references hold more precise types than the data-ow analysis alone could have discovered. is AST is suitable for the last type analysis that follows. e hint typing is an incarnation of the assumption motivating this study: it is a tool the compiler uses to estimate the quality of the di erent versions it may generate for a same function.

Range Analysis

e data-ow typing and the hint typing work hand in hand to improve the precision of the types they collect but they are unable to produce re ned annotations for numeric types. For that, the compiler relies on a range analysis. It is a central element toward good performances as the JavaScript speci cation exposes only double IEEE 754 numbers, whose performance do not compete with those of x integer values.

e range analysis annotates precisely the AST so that the code generator can map some numerical values into integer hardware registers and omit over ow checks.

e range analysis computes for each integer expression an approximation of the possible values it may evaluate to, represented as an interval. When the analysis completes, a tree traversal maps the general numerical types integer and number to precise types such as index (an integer in the range [0, 2 32 -2]), length (i.e., [0, 2 32 -1]), uint32, etc. Applied to the reverse$$A function, the analysis establishes the following intervals:

function reverse$$A(a) { for(let i [0,0] = 0; i < aLen(a)/2 [0,(2 32 -1)/2] ; i++ [0,2 32 -2] ) { ... } }
which enables the compiler to map the variable i to an uint32 integer in the generated code. is also enables the expression i++ to be executed without over ow detection and it enables fast array accesses, as shown in Section 6.

e range analysis handles only integer variables (for the data-ow typing and the hint typing, integer values are mere unbounded exact numbers, without range restriction). All other variables are considered as potentially holding in nite values, approximated with the interval [-∞, ∞].

e range analysis is based on RATA, a typed analyzer for JavaScript [START_REF] Logozzo | RATA: Rapid Atomic Type Analysis by Abstract Interpretation -Application to JavaScript Optimization[END_REF] but it departs from the previous work by relying on a new technique for insuring convergence. For the sake of conciseness we brie y present main analysis, as it is fairly standard, and we focus on the convergence operator, usually named widening operator in the abstract interpretation community, as it is a crucial element of the overall quality of the analysis.

e Abstract Interpretation

e range analysis is presented in Figure 5 as a set of typing rules, based on those of Section 3 where expressions are extended to binary numerical operators and types are extended with integer intervals. In addition to the previous notations, is a widening operator (see Section 5.2) and we note Γ {x < n} a new typing environment where the variable x is constraint to be smaller than the value n (see the I R N rule). e critical part of the analysis is the de nitions of the interval operations for binary and unary operators and for tests, as explicitly used in the P rule and implicitly in the I R N , and I R V rules. ese operators govern the whole analysis by specifying how to compute approximations of integer operations. ey are de ned in gure 6. N )

x :

[x l , x h ], : [ l , h ] Γ 1 {x < l } { > x h } s 1 ⇒ ⊥, Γ 2 Γ 1 {x ≥ l } { ≤ x h } s 2 ⇒ ⊥, Γ 3 Γ if(x < ) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 Γ 3 (I R V )
Figure 5. Interval analysis.

Let us consider the following conditional expression: if(x < y) then else else, and let us assume that x and y are known to be in the intervals [x l , x u ] and [ l , u ]. Some knowledge can be deduced in both branches. In the then branch, x is known to be smaller than y, which potentially narrows its approximation. e value x may hold is the interval obtained by computing [x l , x u ] ≺ [ l , u ]. Interestingly, in the then branch, the test also narrows the approximation of y, as it is known to be greater or equal to x.

e same reasoning applies to the else branch, where x is known to be in the interval

[x l , x u ] [ l , u ] and y in [ l , u ] [x l , x u ].

Widening and Stepping

e range analysis relies on a widening operator to ensure its convergence in an acceptable compilation time. For instance, for the for loop of the reverse$$A function, it enables to compute the nal approximation interval [0, 2 32 -2] of the variable i in less than 2 32 -2 steps! For that, instead of adding 1 to i at each iteration as the execution of the program will do, the analysis adds larger and larger integer values. In the range analysis, each time the instruction is analyzed, a larger than before value is added. is is designated as a delaying strategy in [START_REF] Cousot | Combination of Abstractions in the ASTR ÉE Static Analyzer[END_REF]).

e widening takes place a er each abstract interpretation of a numeric operation. Let us illustrate its principle with the i increment. Let us assume that at one moment of the analysis, the variable i is approximated by the interval [l, u].

e constant is interpreted as [1, 1] and the interpretation of the addition produces the interval [l +1, u +1]. is interval is then widened into [m, ] with m ≤ l and ≥ u +1. Following the conventions of the domain, we note

[m, ] = [l +1, u+1].
e widening operator we use relies on numerical scales and a stepping process. Intervals are widened progressively, that is step by step, using two di erent scales for intervals lower and upper bounds. ese scales are established based on the JavaScript speci cation and on some remarkable integer values many programs use.

e JavaScript speci cation makes use of some special integers. First, as numbers correspond to a double-precision 64-bit binary format IEEE 754 values, integers are restricted to the interval [-2 53 , 2 53 ]. Second, JavaScript de nes array lengths as integers in the range [0, 2 32 -1], which implies that the largest array index is smaller or equal to 2 32 -2.

ese integer values are included in our widening scale. We also add a few numbers of our own. Hopc's backend uses two-bit tagged integers, so the largest integer value on a 32 bit machine is 2 30 -1. We include that value in our widening scale and for the negative values, we include -1 and -2, as these numbers are frequently used for terminating decreasing loops. In conclusion, we use the following scales: upper bound steps: 0, int30, index, len th, int53, +∞ lower bound steps: 0, -1, -2, -int30, -int53, -∞ With the following notations: int30 = 2 30 -1. index = 2 32 -2, len th = 2 32 -1, and int53 = 2 53 .

We can now complete the explanation of the result of the range abstract interpretation for the reverse$A function.

e operator aLen returns an array length, then aLen(a) ∈ [0, len th]. We derive aLen(a)/2 ∈ [0, len th/2]. At each iteration of the loop, the variable i is incremented and the interval widened. It is then successively approximated by [0, 0], [0, int30], and ends with [0, index], index being the smallest value of the upper bound scale greater than len th/2.

Final word

Once the range analysis completes, the intervals are used to assign precise integer types to expressions and variable declarations. ese types are used to improve the performance of the generated code. Obviously, they enable type checks removal but even more importantly, they enable numbers to be untagged and unboxed. is is presented in the next section.

Implementation

Fast JavaScript compilers go beyond implementing well a small core language.

ey also deploy a large arsenal of complex optimizations and runtime techniques. Hopc implements some of them. Describing all of Hopc is beyond the scope of this paper. Here, we only focus on the type analyses it performs and how it is used to shape the generated code.

is is illustrated by the code generated for iterating over

addition [l 1 , u 1 ] ⊕ [l 2 , u 2 ] = [l 1 + l 2 , u 1 + u 2 ] substraction [l 1 , u 1 ] [l 2 , u 2 ] = [l 1 -u 2 , u 1 -l 2 ] multiplication [l 1 , u 1 ] ⊗ [l 2 , u 2 ] = [min(l 1 * l 2 , u 1 * u 2 , l 1 * u 2 , l 2 * u 1 ), max(l 1 * l 2 , u 1 * u 2 , l 1 * u 2 , l 2 * u 1 )] division [l 1 , u 1 ] [l 2 , u 2 ] = [trunc(l 1 /u 2 ), ceil(u 1 /l 2 )] smaller than [l 1 , u 1 ] ≺ [l 2 , u 2 ] = i f u 2 ≤ u1 then (i f u 2 > l1 then [min(l1, u 2 -1), u 2 -1] else [l 1 , l1]) else [l 1 , u 1 ] smaller or equal [l 1 , u 1 ] [l 2 , u 2 ] = i f u 2 < u1 then (i f u 2 ≥ l1 then [min(l1, u 2 ), u 2 ] else [l 1 , l1]) else [l 1 , u 1 ] Figure 6. Interval operators.
arrays, which is a recurrent JavaScript programming pa ern as arrays are ubiquitous in this language.

Remember that JavaScript primitive numbers are doubleprecision 64-bit IEEE 754 values but array indexes and bitwise operations are speci ed over 32-bit x integers. Using ad-hoc representations that t hardware integer registers for these numbers is crucial for performances. Hopc uses the results of the previous type analyses (occurrence typing, hint typing, and range analysis) to use the most e cient number representation, expression by expression. at is, as much as possible, it generates code that uses native unsigned 32-bit integers for representing indexes, native signed 32bit integers when values can be negative, and polymorphic representations that use tagged integers and boxed oating point numbers otherwise. Let us consider the following example, compiled for 32-bit platforms:

let i = 0; while( i < a.length ) sum += a[ i++ ];
and let us assume that the hint typing has specialized the code for a being an array. e occurrence typing proves that i is an integer and the range analysis proves that it is in the range [0..2 32 -2] (because of the JavaScript length specication). e variable i can then be mapped to a hardware register and the increment can be implemented as a simple assembly instruction with no type check, no tagging/untagging, and no over ow check. is is optimal but what happens now if we make i polymorphic by assigning it a value of a di erent type as in:

let i = 0; while( i < a.length ) sum += a[ i++ ]; i = null;
At the point of the increment, i is still known to be an integer in the range [0..2 32 -2] but the variable is now polymorphic as it holds integers and the null value. So, it can no longer be represented as a native unsigned 32-bit integer. Its initial value is compiled as a polymorphic value: a tagged integers where the two lower bits are used to encode the integer type and the 30 higher bits are used to encode the actual integer value. 30-bit values are not large enough to encode all possible array indexes so the loop increment may over ow. is must be tested. A er the increment i may either be a tagged 30-bit integer or a boxed double precision number. An additional test is then also needed before each increment to check which representation is used and to select the proper addition operator. On a modern 32-bit platform, we measured a factor of three between the execution times of the two versions. Avoiding polymorphic representations as much as possible is, performance wise, essential.

Integer Boxing/Unboxing

e rst step of the untagging algorithm consists in computing for each integer variable (see Section 5)

, R m ( ) = [L..U ],
the smallest range that is larger than all the ranges in R( ), the set of the ranges of all the occurrences. R m ( ) is the smallest range that veri es ∀[l ..u] ∈ R( ), L l ∧ u U . e second step associates precise types to all expressions, using the following mapping:

(1) R( ) ∈ [0..2 32 -1] → uint32 untagged 32-bit value (2) R( ) ∈ [-2 31 ..2 31 -1] → int32
untagged 32-bit value (3) ot her wise → integer tagged value A variable reference type might be more speci c than its declaration type, as in the example of the introduction. In the loop, the variable i is known to be an uint32. It is declared as an uint32 in the rst version, but it is declared as an any value in the second because of the null assignment. e third step of the algorithm consists in inserting type coercions to switch from native representations to polymorphic representations and vice-versa. Values are tagged or boxed when: i) they are stored in objects and arrays, ii) they are stored in polymorphic variables, iii) they are arguments to untyped or polymorphic function calls, iv they are mutable and captured in a closure. ey are untagged/unboxed in the converse operations.

Arrays

e combined use of the occurrence typing, hint typing, range analysis, and numbers untagging enables Hopc to map JavaScript numbers to 32-bit integers and to map simple operations such as unary operators, binary operators, and array accesses to simple assembly instructions. is is illustrated in this Section where it is studied how Hopc compiles loops over arrays, which is challenging because of sparse arrays and because arrays may dynamically grow and shrink. According to the optimistic assumption presented in Section 2, the compiler favors at and non-extended arrays, which enables to generate e cient code for common situations.

e fast access of an object property relies on the hidden classes technique [START_REF] Deutsch | E cient Implementation of the Smalltalk-80 System[END_REF].

is is e cient for objects but this does not t well arrays that are accessed via integers instead of named properties. Hopc uses another schema that favors fast accesses inside loops. It supports e ciently arrays that are at and that are only accessed via numerical properties.

Arrays are implemented as objects with 4 elds: a properties list for non numerical properties and for sparse array properties; a length that denotes the total number of numerical elements (only those that are indexed by an integer in the interval [0, 2 32 -2]); an ilength that denotes the number of elements of at arrays; and a raw vector that contains the elements of at arrays. Arrays are created at, with an empty properties list. Arrays are un-a ened when an element is removed or when a non contiguous element is added. Generally, arrays remain at during their whole lifetime. When executing a loop as: function sum( a ) { let i = 0, sum = 0; while( i < a.length ) sum += a[ i++ ]; return sum; } the values of the a ributes ilength and vector are unlikely to change. So, they can be preloaded before the loop and used inside, where a mere guard checking that i is smaller than ilength is enough. If during the loop, a changes, either because an element is removed or added or because its length is modi ed, the ilength property is modi ed accordingly, which impacts the result of the guard for the next iteration. Using C's syntax, and eliding slightly, the generated code is equivalent to: obj_t sum( obj_t a ) { uint32_t i, ilen = a->ilength; obj_t *v = a->vector, sum = JS_INT( 0 );

for( i = 0; i < a->length; i++ ) { if( i < ilen ) { // fast path, at array sum = JS_ADD ( sum, v[ i ] ); } else { // slow path, complex array, update needed sum = JS_ADD( sum, JS_GET_PROPERTY( a, i ) ); v = a->vector; ilen = a->ilength; } } return sum; } Using unboxed representations for i and its increment, as suggested in Section 6.1, the generated code loop is almost as fast as an equivalent C loop. It only imposes a mere additional comparison between two registers, one for the index that varies during the loop, and the ilength array eld. Notice however that this almost optimal compilation only applies when the loop involves no code that could potentially delete array elements. In particular, the loop must not contain calls to unknown functions. When this cannot be established by the compiler only one an extra guard is needed before each access inside the loop.

e performance evaluation presented in Section 7 shows how well this principle applies.

e combined use of the occurrence typing, hint typing, range analysis, and numbers untagging is a central element of the compilation process as it enables Hopc to map Java-Script numbers to 32-bit integers and to map simple operations such as unary operators, binary operators, and array accesses to simple assembly instructions.

Performance Evaluation

We have compared Hopc's performance and other JavaScript implementations, namely: Google's V8 (6.2.414.54), Rhino (1.7.7) the rst historical AOT JavaScript compiler that generates JVM byte-code, JJS (9.0.4) the Adobe JavaScript compiler that generates JVM byte-code too, and JerryScript (1.0 c3c0bb8d), a JavaScript interpreter designed for IoT devices.

We have collected the execution times of popular Java-Script tests coming from the Octane, SunSpider, and Jet-Stream test suites. From these test sets, we have ruled out oating point intensive programs because Hopc does not optimize oating point numbers yet and then all these tests are dominated by the garbage collection time. Hopc uses a conservative Mark&Sweep garbage collector [START_REF] Boehm | Garbage Collection in an Uncooperative Environment[END_REF], which is a technique known not to be e cient for handling short living objects. Second we have eliminated browser-only programs for obvious reasons. And nally, we have also eliminated very large tests (larger than 10.000 lines of code in a single le) as our compiler, which is meant for separate compilation, cannot cope with such large source les (compilation times become excessively long, up to 30 minutes, on very large source les). Each program has been executed 30 times and we have computed the median and the deviation of the execution wall clock times. Figure 7 presents these results relatively to V8 performance that establishes the baseline of our comparison. Benchmarks where executed unmodi ed but, when possible, the number of iterations was con gured so that a test runs in no less than 10 seconds.

Unsurprisingly JerryScript, the sole interpreter of our experiment, is in between one and two orders of magnitude slower than compilers. is system has being designed for running on tiny devices, it is optimized for space, not for speed, contrarily to compilers that use the opportunity to generate several versions of the same source code and to use various memory caches to run faster.

On many tests V8 and Hopc are in the same range, separated by a factor of 2 or 3. In the best situations, Hopc outperforms V8 signi cantly (base64, fib, qsort, and splay).

ese are integer and array intensive programs that fully bene t from the type analyses and tagging/untagging optimization presented in Section 6. e tests crypto, crypto-aes, crypto-md5 are actually disguised oating point numbers test.

ey perform many bitwise operations on 32-bit integers and store them into arrays. On 32-bit platforms, Hopc represents these integers as oating point numbers and allocate them. e execution time is then dominated by the garbage collection (henceforth GC) time that represents more than 65% of the overall execution time and by double precision operations that count for 15% of the execution. e test deltablue performs poorly with Hopc compared to V8. It is an allocation intensive programs whose execution time is dominated by allocations of short living objects, which is an allocation pa ern the garbage collector does not handle e ciently. Improving on that aspect, is certainly a subject for further studies [START_REF] Blackburn | Immix: A Markregion Garbage Collector with Space E ciency, Fast Collection, and Mutator Performance[END_REF].

e test tagcloud uses the eval function to create a large data structure. Independently of the signi cant execution time spent in the interpreter, this shows that even in the presence of direct eval in the source, Hopc is still able to generate decently e cient code.

Hint Typing Performance

To evaluate the hint typing impact we have instrumented the code generator to collect statistics about function invocations (Figure 8). e compiler instruments the generated code to mark function calls with one of the following tag: typed, untyped, hinted, unhinted, and dispatch. By comparing the hinted calls, unhinted calls, and dispatch calls numbers we can measure the e ectiveness of the function specialization.

e rst observation is that for all tests where it applies but crypto-md5, the hint typing successfully specializes function de nitions. For some benchmarks such as maze the specialized functions are even invoked directly without going through a dynamic dispatch. is optimal situation happens when the data-ow analysis or the range analysis discover that for a particular call site the specialized function call be called directly. Other tests such crypto, sieve, or splay use the dispatch function. is correspond to situations where the type analyses alone are not able to discover su ciently precise types.

e hint typing gives poor results for the crypto-md5. It is the only test that counts an important number of unhinted calls. is benchmark uses 32-bitwise operations extensively that the hint typing successfully specializes. For instance, for the function md5 ff de ned as the arguments b, c, and d are correctly specialized as int32 integers. However, this test also uses 32-bit literal constants which can only be represented as oating point numbers on a 32-bit platform. is causes type miss-matches between the specialized functions and their actual parameters. Note that this problem disappears on 64 bit platforms where 32-bit are represented as exact integers.

is experiment shows that although simple, the rules presented in Section 4 are su cient to guess correctly runtime program behaviors and that there is no need to invent more complex analyses to discover the best typing context for a function de nition. e ow analysis presented in Section 3 follows a line of research that uses abstract interpretation techniques for assigning types to expressions [START_REF] Jensen | Type Analysis for JavaScript[END_REF]). In the past, these analyses have been mostly used for designing programming environment tools rather than included in a compilation process.

Related Work

is is the objective of the hybrid type inference [START_REF] Hacke | Fast and Precise Hybrid Type Inference for JavaScript[END_REF]. It consists in a static type analysis designed for producing type information used at runtime by a JIT compiler. It shares many similarities with our approach, in particular because the static analysis is unsound and seconded by runtime guards.

e system maintains a dichotomy between static may-have-type and must-have-type and types which could potentially be observed and types that have already been observed at runtime. We do not provide anything similar but we might accommodate this idea in the future.

is study also mentions an integer over ow detection but does not give any details. It seems relatively simple and less precise than our range analysis.

e data-ow type analysis is an occurrence typing analysis tailored for hint typing. It is simpler than the original occurrence typing developed for the Scheme programming language [START_REF] Kent | Occurrence Typing Modulo eories[END_REF][START_REF] Tobin-Hochstadt | Logical Types for Untyped Languages[END_REF] as it only handles simple types and simple type checks. Although this seems precise enough for the needs of the hint typing, it might be worth incorporating more precise analyses in the future.

ere is a whole line of research on JavaScript static analysis.

e main systems are TAJS (Andreasen and Møller 2014), Wala [START_REF] Schäfer | Dynamic determinacy analysis[END_REF], and Safe [START_REF] Park | Scalable and Precise Static Analysis of JavaScript Applications via Loop-Sensitivity[END_REF]. ese systems rely on complex abstract interpretations. ey are able to deduce accurate information about programs, but their complexity and execution times make them unusable in practical compilers.

e range analysis presented in Section 5 departs from RATA, a typed analyzer for JavaScript [START_REF] Logozzo | RATA: Rapid Atomic Type Analysis by Abstract Interpretation -Application to JavaScript Optimization[END_REF]. First, our analysis uses the type information collected by previous compilation stages. Second, we consider a different arithmetic la ice as we target 32 bit machines for which array length cannot be represented as 32 bit integers, if tagging is used. en, we consider uint30/uint32 for tagged/untagged representations, which have to be included in the analysis. Last, the threshold we use for the delayed widening is di erent. We do not collect the constants found in the program as this cannot cope with programs where the loop upper bounds are computed values, for instance, an array length. Instead we use a static scale based on pre-de ned values.

In the seminal description of polymorphic inline cache [START_REF] Hölzle | Optimizing Dynamically-Typed Object-Oriented Languages With Polymorphic Inline Caches[END_REF] the authors mention a type prediction mechanism used in SELF and Smalltalk compilers. In a 7-line long paragraph they mention that the compilers predict that the argument to + are predicted to be integer. is obviously relates to the hint typing but the lack of details of their presentation makes is hard to compare the two approaches.

Samsung's Sjs [START_REF] Choi | SJS: A Type System for JavaScript with Fixed Object Layout[END_REF]) is an AOT JavaScript compiler. It relies on a type system and a type inference that provide information that the rest of the compilation chain uses to generate e cient code. A recent paper [START_REF] Chandra | Type Inference for Static Compilation of JavaScript[END_REF] reports excellent execution times comparable to those of V8 (Google 2018) but also much smaller memory occupations.

ese execution times are be er than those we have reported in Section 7, but this is mitigated by Sjs not considering full-edged JavaScript as V8 or our compiler do. Sjs limits properties polymorphism, it does not comply with JavaScript prototype semantics, and more importantly, it seems not to support introspection and dynamic features such as computed eld names and eld deletions. Sjs cannot run the standard JavaScript unmodi ed.

is is why it is not reported in Section 7. It is also unclear if it supports separate compilation that we need for accommodating the NPM module systems.

ese restrictions enable the type system to report precise information and of course simplify the code generation.

ey are probably imposed by the nature of the type inference algorithm. Our approach does not su er from this limitation. However, it remains that Sjs is an excellent preliminary result and a strong incentive for pursuing investigations on the JavaScript static compilation. It is also a sensitive approach as Sjs is designed for enabling embedded JavaScript, a context in which programs are small, closed, and where it is probably ne not to support all the language features.

Bolz et al. have proposed storage strategies [START_REF] Bolz | Storage Strategies for Collections in Dynamically Typed Languages[END_REF]) for optimizing the representations of homogeneously typed collections. It consists in associating each collection with an ad-hoc strategy that evolves over time when elements are added. is mechanism saves memory space and speeds up data accesses. Experimental results show signi cant bene ts for the Python programming language. Cli ord and his colleagues have developed analog solutions for JavaScript (D. et al. 2015). ey have modi ed the V8 JIT compiler to cope with various storage representations for objects and arrays. ey combine homogeneous data representations for fast storage and access and an allocation logging mechanism that works hand in hand with the garbage collector to avoid allocating extra unused space for objects. ese previous studies focus on the e ciency of data representations. e fast array access array we have presented focuses on the e ciency of the loop control and data ows. ey are di erent, they do not follow the very same goal, but they are complementary. Combining both could yield to fast accesses, fast loops, and e cient data storage.

Conclusion

is paper presents Hopc, a new AOT compiler for JavaScript. It relies on the observation that amongst all the possible interpretations a JavaScript program may have, the most likely is the one for which the compiler can deliver its best code. We have derived this principle in a type analysis called hint typing and in a code generator that uses at untyped number representations. We have implemented the hint typing and the other analyses and optimizations it enables, namely a range analysis and untagging optimization.

e experimental report shows that Hopc approaches the performance of the fast JIT compilers on several benchmarks. Even if Hopc is still usually slower we think that this experiment establishes that AOT compilation is a promising approach for implementing languages as dynamic as Java-Script, especially in application domains such as IoT where many devices cannot use JIT compilers, either because they have too limited capacities or because they only support executable read-only memory, which makes JIT compilation unusable.

  DLS'18, Boston, NY, USA 2018. 978-x-xxxx-xxxx-x/YY/MM. . . $15.00 DOI: 10.1145/nnnnnnn.nnnnnnn

  value ::= nil | bool | ... expr e ::= | x | e(e) | e[e] | new e | function(x ) {s} stmt s ::= x =e | s;s | if(e) {s} else {s} | while(e) {s} | return e type τ ::

Figure 1 .

 1 Figure 1. Data-ow core typing rules.

  expr e ::= ... | typeof e | e instanceof e | e == e | e in e

Figure 2 .

 2 Figure 2. Optional data-ow typing rules.

Figure 3 .

 3 Figure 3. Typing rules with breaking control ow operators.

  reverse = (a:any):any => a instanceof Array ? reverse$$A(a) : reverse$$(a); const areverse = ():array => reverse$$A(a[ 23, 56, 3 ]); const oreverse = ():any => reverse$$({length:2, 0 :1, 1 :45})

  expr e ::= ... | e+e | e<e | x ++ stmt s ::= ... | switch(e) {case e 1 : ...casee n : ...}

  expr e ::= ... | e+e | e<e type δ ::= ... | [int , int ]

  function md5_ff(a, b, c, d, x, s, t) { return md5_cmn((b & c) | ((˜b) & d), a, b, x, s, t); }

  Results of 30 runs collected on an Intel core i7-3520M running Linux4.13/Debian con gured for 32-bit executions. Median of wall clock times relative to V8 performance and deviations divided by the mean. Smaller time is be er. Benchmark sources: † Octane, * Jetstream, • Sunspider, Bglstone, other sources.

		jit		AOT compilers		interpreter
	benchmark	V8	Hopc	jjs	Rhino	JerryScript
	bague	1.00 4.6%	0.99 0.5%		20.29 2.0%	142.50 0.0%
	base64 •	1.00 0.9%	0.59 3.7%	2.00 1.9%	7.07 0.7%
	boyer †	1.00 1.1%	1.47 1.1%	8.10 24.9%	7.44 3.7%
	crypto †	1.00 0.4%	7.31 0.3%	2.97 6.8%	25.60 8.4%	116.54 0.0%
	crypto-aes *	1.00 0.4%	2.34 0.3%	4.56 2.4%	11.68 4.8%	86.88 0.0%
	crypto-md5 *	1.00 2.7%	6.51 0.3%	2.82 8.8%	7.69 2.5%	54.54 0.0%
	deltablue †	1.00 0.4%	6.81 0.2%	6.78 4.2%	54.37 4.7%	290.85 0.0%
	fannkuch	1.00 0.1%	1.70 0.4%	1.80 19.6%	5.89 2.2%	98.10 0.0%
	fib	1.00 0.3%	0.66 0.2%	1.66 1.2%	2.76 0.6%	50.57 0.0%
	maze	1.00 0.6%	1.20 2.9%
	puzzle	1.00 1.7%	1.89 0.2%	2.17 1.2%	6.23 0.8%
	qsort	1.00 0.1%	0.91 0.2%	1.47 1.1%
	richards †	1.00 0.3%	3.34 0.4%	2.59 2.0%	24.64 1.3%	156.71 0.0%
	sieve	1.00 0.3%	5.02 0.7%
	splay †	1.00 16.0%	1.17 0.8%	2.59 5.9%	5.27 1.3%
	tagcloud *	1.00 1.0%	3.45 0.8%	1.99 7.8%	5.80 5.9%
	Figure 7.

  It is frequent that JavaScript variables are assigned values of di erent types and that functions are not called with the declared number of arguments. us, the typing approaches Figure 8. Statistics of function invocations. Typed calls correspond to functions successfully typed by the data-ow and range type analyses. Hinted calls correspond to functions typed by the hint typing. Unhinted calls are functions invocations for which the specialized version has not been selected at runtime. Dispatch calls are the number of hinted function invocations that need a runtime type check. that assign unique types to variable declarations (Anderson and et al. 2005; Lerner et al. 2013) are mildly e ective for real-life JavaScript programs.e code specialization enabled by the hint typing is not a ected by this problem as it chooses the types according to variable uses, not only variable declarations.

	benchmark	typed calls	untyped calls	hinted calls	unhinted calls dispatch calls
	bague	1647×10 9	11	0	0	0
	base64	22	0	0	0	0
	boyer	400	143×10 6	401	1×10 3	1×10 3
	crypto	14×10 6	3×10 6	46×10 6	165×10 3	46×10 6
	crypto-aes	59×10 6	510×10 3	0	0	0
	crypto-md5	126×10 6	0	161×10 6	160×10 6	128×10 6
	deltablue	80×10 3	82×10 6	80×10 3	80×10 3	1
	fannkuch	11	0	0	0	0
	fib	-206752951	0	0	0	0
	maze	38×10 6	80×10 6	1×10 6	0	1×10 6
	puzzle	39×10 6	61	0	0	0
	qsort	66×10 6	39×10 6	0	0	0
	richards	0	902×10 3	1	0	1
	sieve	66×10 6	281×10 6	270×10 6	352×10 3	271×10 6
	splay	0	2×10 6	71×10 6	0	71×10 6
	tagcloud	0	0	2×10 3	0	2×10 3

Γ e ⇒ τ , Γ Γ nil ⇒ nil, Γ (N ) Γ true ⇒ bool, Γ (T ) Γ false ⇒ bool, Γ (F ) x ∈ Dom(Γ) Γ x ⇒ Γ(x ), Γ (V ) Γ e ⇒ τ , Γ 1 Γ x =e ⇒ τ , Γ 1 [x : τ ] (A ) Γ function(x ) {s} ⇒ ⊥ → ⊥, Γ (A ) Γ e 2 ⇒ τ 2 , Γ 2 Γ 2 e 1 ⇒ τ 1 , Γ 1 Γ e 1 [e 2 ] ⇒ , Γ 1 (P ) Γ e ⇒ τ , Γ 1 Γ return e ⇒ ⊥, Γ (R ) Γ e ⇒ τ , Γ 1 Γ new e ⇒ object, Γ 1 (N ) Γ s 1 ⇒ τ 1 , Γ 1 Γ 1 s 2 ⇒ τ 2 , Γ 2 Γ s 1 ;s 2 ⇒ ⊥, Γ 2 (S ) Γ e 1 ⇒ ⊥ → ⊥, Γ 1 Γ 1 e 2 ⇒ τ 2 , Γ 2 Γ[x : τ 2 ] e 1↓bod ⇒ τ , Γ 3 Γ e 1 (e 2 ) ⇒ τ , Γ 3 (C ) Γ Γ 2 e ⇒ τ , Γ 1 Γ 1 s ⇒ ⊥, Γ 2 Γ while(e) {s} ⇒ ⊥, Γ 1 Γ 2 (W ) Γ e 1 ⇒ τ 1 , Γ 1 τ 1 ⊥ → ⊥ Γ 1 e 2 ⇒ τ 2 , Γ 2 Γ e 1 (e 2 ) ⇒ , Γ 2 \{assi V ar s } (F ) Γ e ⇒ τ , Γ 1 Γ 1 s 1 ⇒ ⊥, Γ 2 Γ 1 s 2 ⇒ ⊥, Γ 3 Γ if(e) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 Γ 3 (I )

x = 4; while( x < 10 ) { x =

; } 2 x = 4; while( x = 20 , false ) { x = true }

}According to the rules given in Figure1, the variable errno is assigned the type undefined line 6. Following the call line 7, it is unconditionally assigned the type number line 4, which is wrong because the line is executed only when x is negative or null. By consequence, it is incorrectly considered of type number line 8. Fixing that problem can be solved simply by merely considering that all instructions that follow potential

DLS'18, November 6, 2018, Boston, NY, USAΓ e ⇒ τ , Γ Γ x ⇒ γ , Γ γ = ⊥ ∨ γ = Γ[x : τ ] s 1 ⇒ ⊥, Γ 2 Γ s 2 ⇒ ⊥, Γ 3 Γ if(x == typeof T N ame(τ )) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 Γ 3 (T ) Γ x ⇒ τ , Γ Γ s 1 ⇒ ⊥, Γ 2 Γ if(x == typeof T N ame(τ )) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 (T T ) Γ x ⇒ γ , Γ γ τ ∧ γ ⊥ ∧ γ Γ s 2 ⇒ ⊥, Γ 2 Γ if(x == typeof T N ame(τ )) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 (T F ) Γ x ⇒ τ 1 , Γ Γ e ⇒ τ 2 , Γ 2 Γ 2 [x : object] s 1 ⇒ ⊥, Γ 3 Γ 2 s 2 ⇒ ⊥, Γ 4 Γ if(x instanceof e) {s 1 } else {s 2 } ⇒ ⊥, Γ 3 Γ 4 (VI O ) Γ x 1 ⇒ τ 1 , Γ Γ x 2 ⇒ τ 2 , Γ 2 Γ 2 [x 1 : object, x 2 : ⊥ → ⊥] s 1 ⇒ ⊥, Γ 3 Γ 2 [x 2 : ⊥ → ⊥] s 2 ⇒ ⊥, Γ 4 Γ if(x 1 instanceof x 2 ) {s 1 } else {s 2 } ⇒ ⊥, Γ 3 Γ 4 (VI O V) Γ x ⇒ ⊥ → τ , Γ Γ e 2 ⇒ , Γ 2 Γ x (e 2 ) ⇒ τ , Γ 2 [x : ⊥ → τ ] (C ) Γ e 1 ⇒ string, Γ 1 Γ 1 e 2 ⇒ τ , Γ 2 Γ e 1 [ indexOf ](e 2 ) ⇒ number, Γ 2 (SI O ) Γ e ⇒ τ 1 , Γ 1 Γ e in x ⇒ bool, Γ 1 [x : object] (I ) Γ e1 ⇒ τ 1 , Γ 1 Γ 1 e 2 ⇒ τ 2 , Γ 2 Γ e 1 ==e 2 ⇒ bool, Γ 2 (B ) Γ e ⇒ string, Γ 1 Γ e[ length ] ⇒ number, Γ 1 (SL )

function reverse(a:any):any { for(let i:int = 0; i < a.length/2; i++) { let v = a[ a.length-1-i ]; a[ a.length-1-i ] = a[ i ]; a[ i ] = v; }

Γ e ⇒ τ , κ, Γ Γ break ⇒ ⊥, t r ue , Γ (B ) Γ continue ⇒ ⊥, t r ue, Γ (C ) Γ e ⇒ τ , κ, Γ 1 Γ return e ⇒ ⊥, t r ue, Γ (R ) Γ s 1 ⇒ τ 1 , f al se , Γ 1 Γ 1 s 2 ⇒ τ 2 , κ 2 , Γ 2 Γ s 1 ;s 2 ⇒ ⊥, κ 2 , Γ 2 (S ) Γ s 1 ⇒ τ 1 , t r ue, Γ 1 Γ 1 s 2 ⇒ τ 2 , κ 2 , Γ 2 Γ s 1 ;s 2 ⇒ ⊥, t r ue , Γ 1 Γ 2 (S B )Γ e ⇒ τ , κ, Γ 1 Γ throw e ⇒ ⊥, t r ue, Γ (T )

DLS'18, November 6, 2018, Boston, NY, USA Manuel SerranoΓ e ⇒ δ , Γ Γ n ⇒ [n, n], Γ (N ) x : δ ∈ Γ Γ x ⇒ δ , Γ (V ) Γ e 1 ⇒ δ 1 , Γ 1 Γ 1 e 2 ⇒ δ 2 , Γ 2 Γ e 1 + e 2 ⇒ (δ 1 ⊕ δ 2 ), Γ 2 (P ) Γ e ⇒ δ , Γ 1 Γ x =e ⇒ δ , Γ 1 [x : δ ] (A ) Γ s 1 ⇒ δ 1 , Γ 1 Γ 1 s 2 ⇒ δ 2 , Γ 2 Γ s 1 ;s 2 ⇒ ⊥, Γ 2 (S ) Γ Γ 2 e ⇒ δ , Γ 1 Γ 1 s ⇒ ⊥, Γ 2 Γ while(e) {s} ⇒ ⊥, Γ 1 Γ 2 (W ) Γ e ⇒ δ , Γ 1 Γ 1 s 1 ⇒ ⊥, Γ 2 Γ 1 s 2 ⇒ ⊥, Γ 3 Γ if(e) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 Γ 3 (I ) Γ 1 {x < n } s 1 ⇒ ⊥, Γ 2 Γ 1 {x ≥ n } s 2 ⇒ ⊥, Γ 3 Γ if(x < n) {s 1 } else {s 2 } ⇒ ⊥, Γ 2 Γ 3 (I R


Colin Vidal
email: colin.vidal@inria.fr

Gérard Berry
email: gerard.berry@college-de-france.fr

Manuel Serrano
email: manuel.serrano@inria.fr

Hiphop.js: a language to orchestrate web applications

Keywords: Web Programming, Reactive Programming, Orchestration

INTRODUCTION

We are interested in web orchestration, which is the problem of appropriately handling the asynchronous events appearing in program executions. It is known be one of the major difficulties of web programming (see callback hell [START_REF] Kambona | An evaluation of reactive programming and promises for structuring collaborative web applications[END_REF][START_REF] Mikkonen | Web applications: Spaghetti code for the 21st century[END_REF]).

High-level approaches to orchestrate web applications have been developed in academia or industry. The Functional Reactive Programming (FRP) concept [START_REF] Cooper | FrTime: A language for reactive programs[END_REF] has been carried up to the web by Flapjax [START_REF] Cooper | Embedding dynamic dataflow in a call-byvalue language[END_REF][START_REF] Meyerovich | Flapjax: a programming language for ajax applications[END_REF], which adopts a dataflow programming style: when a variable is modified, any expression that references it is implicitly reevaluated. Others techniques targeting GUI updates [START_REF] Serrano | Functional Reactive Programming with nothing but Promises: Implementing Push/Pull FRP using JavaScript Promises[END_REF][START_REF] Czaplicki | Asynchronous functional reactive programming for guis[END_REF][START_REF]Facebook[END_REF][START_REF] Reynders | Multi-tier functional reactive programming for the web[END_REF] consist in associating a state with a set of graphical elements and automatically updating the graphics on changes. In JavaScript Promises and async/await constructions [START_REF]ECMAScript language specification[END_REF] make it possible to chain asynchronous actions in a specific sequential order. Working at a more abstract level, these solutions avoid using callbacks.

Our goal is to go further with yet another solution based on a new language called Hiphop.js. It is a JavaScript extension of Esterel [START_REF] Berry | The Foundations of Esterel[END_REF] based on three reactive control mechanisms: explicit concurrency, synchronisation using synchronous signals, which makes the handling of concurrent issues much easier, and preemption, i.e. the explicit cancellation of an ongoing orchestration subactivity. Hiphop.js suitably extends the core Esterel notions to deal with web paradigms such as application structure dynamicity. Hiphop.js follows a previous Scheme-based prototype [START_REF] Berry | Hiphop: a synchronous reactive extension for Hop[END_REF], but takes different approaches w.r.t. the interaction with the host language.

This paper gives an informal introduction to Hiphop.js through a small example that compares the programming of a simple eventaware program in both JavaScript and Hiphop.js.

Permission to make digital or hard copies of part or all of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for third-party components of this work must be honored. For all other uses, contact the owner/author(s). SAC 2018, April 9-13, 2018, Pau, France © 2018 Copyright held by the owner/author(s). ACM ISBN 978-1-4503-5191-1/18/04. https://doi.org/10.1145/3167132.3167440

SPECIFICATION OF THE EXAMPLE

We study the timer application of the 7 GUIs project1 where the timer's duration is represented by a slider, the current elapsed time is displayed both by a gauge and as a number, and a Reset button resets the timer.

When running the timer the gauge and numeric field are constantly updated until the duration is reached. From then on, setting a bigger duration immediately restarts the timer from the current elapsed time. At any time, pressing Reset resets the elapsed time to 0 and restarts the timer.

IMPLEMENTATION

We compare the JavaScript and Hiphop.js timer implementations, the latter introducing the Hiphop.js programming style and constructions.

The plain HTML GUI is common to JavaScript and Hiphop.js:

<div > Elapsed time : < meter id =" meter "/ > </ div > <div > < span id =" elapsed "/ >s </ div > Duration :

< input id =" range " type =" range " max ="100" onchange =" setD ( this . value )"/ > < button onclick =" resetE ()" > Reset </ button >

JavaScript implementation

The JavaScript code is as follows:

var D =0 , E =0 , id = -1; window . onload = function () { $ (" meter "). value =E; $ (" meter "). max = D ; $ (" elapsed "). innerHTML = E ; $ (" range "). value =D; Contrary to JavaScript scattered callbacks, in Hiphop.js there is a unique temporal code, which is based on classical sequencing and looping, signal emission, and temporal statements. Each statement has a temporal duration in term of reactions. EMIT emits an signal and terminates immediately, i.e. passes control in sequence in the very same reaction. LOOP immediately starts its body and restarts it immediately when it terminates. PAUSE pauses for one reaction.

} function tick () { if (E <D) { E +=0.1; $ (" meter "). value = E ; $ (" elapsed "). innerHTML = E ; } if (E == D ) { clearTimeout ( id ); id = -1; } } function startIntervalIfNeeded () { if ( id == -1 && E < D) id =
Let us now explain how BasicTimer executes. At initial reaction, LOOP starts its body that emits the elapsed signal with value 0. The IF test is then evaluated. If the value of elapsed is less than that of duration, the TimeoutMod module is ran. As presented in Section 7 this will terminate the reaction, and after 1/100 will resume with the elapsed emission. Otherwise, the reaction terminates.

Adding LOOPEACH immediately starts the BasicTimer. From then on, whenever Reset is pressed, this timer is killed whichever state it was in, and a new timer is immediately restarted afresh. The advantage of temporal programming to modularly describe behavior becomes obvious: no internal state manipulation of BasicTimer needs to be performed by the user.

EXTENSION OF THE SPECIFICATION

The differences between Hiphop.js and JavaScript are more visible as the orchestration problem gets more complex. Let us add a new functionality to the previous specification: the timer can be suspended when it is running. In that case, the elapsed time is no longer incremented until the timer is resumed. The duration slider and Reset button remain active during suspension. In the GUI, we add a Suspend button that toggles the timer between the normal and suspended mode. The Suspend button turns to orange during suspension.

EMIT suspendColor (" orange "); AWAIT ( NOW ( suspend )); EMIT suspendColor (" transparent "); } } } }

The code is now made of two parallel arms for controlling the JavaScript timer and for coloring the Suspend button. Since both arms are included in the LOOPEACH, they will be both simultaneously killed and restarted when reset occurs.

Between resets, both arms work in lockstep, i.e. conceptually synchronously. The suspend input signal is broadcast. The first arm automatically suspends and resumes the timer as specified, while propagating its termination. The second arm toggles the button color.

As for the first Hiphop.js implementation, the code makes the temporal behavior explicit, the syntactic nesting of temporal construction explicitly specifying theirs lifetimes and priorities. States are in the code, not in the data, and the BasicTimer code can be directly reused without modification.

LINKING HIPHOP.JS AND JAVASCRIPT

This section explains the link between Hiphop.js and JavaScript. Let us call stm the reactive machine compiled from SuspendableTimer and describe its API. When Reset button is pressed, the GUI calls the resetE JavaScript function. In Hiphop.js, we make this function send the reset signal and trigger a reaction:

function resetE () {
stm . input (" reset "); stm . react (); }

The input signals duration and suspend are respectively handled by functions setD and susp in the same way. Conversely, to transform signal output by Hiphop.js into JavaScript actions, we associate Hiphop.js event listeners with output signals. For instance, the following code updates the gauge and numeric field:

stm . addEventListener (" elapsed ", evt => { $ (" meter "). value = evt . signalValue ; $ (" elapsed "). innerHTML = evt . signalValue ; });

The other outputs are handled in the same way.

CONTROLLING ASYCHRONOUS ACTIONS

The EXEC Hiphop.js statement is used to launch and control external actions whose execution spans several Hiphop.js reactions: a XMLHTTPRequest, a setTimeout call, etc.

Here is the source code of the parametric TimeoutMod timer submodule, parametrized by a number of milliseconds: The Hiphop.js "EXEC start-expr" statement executes the JavaScript expression start-expr. Then, it pauses at each reaction, terminating only when the action has completed. When EXEC starts, a JavaScript function is automatically created, it is referred to as DONEREACT in Hiphop.js. Its call will trigger both the termination of EXEC and a new reaction. An EXEC statement also specifies three optional side-effecting expressions: the ONKILL expression is automatically evaluated when the EXEC statement is killed, for example here by the "LOOPEACH(NOW(reset))" enclosing statement. The ONSUSP expression is automatically evaluated when EXEC gets suspended, and the ONRES statement when it gets resumed.

CONCLUSION

Callback-based orchestration of web applications in JavaScript is known to be quite difficult and hasardous. Better solutions have already been studied in academic and industrial contexts. In our opinion, they are not yet fully satisfactory since they are either too invasive (dataflow programming style), too specific (targetting only the GUI updates), or still limited (promises and async/await).

The Hiphop.js language extends JavaScript with a reacher orchestration solution. Our approach has been to port Esterel concepts and techniques to the web, basing orchestration of web applications on dedicated temporal statements.

In our opinion, Hiphop.js has two important virtues. First, it deals with events orchestration in a very behavioral and modular way, promoting straight code reuse over deep modification of existing code. Second, being smoothly embedded into JavaScript and interfaced with standard code, it does not impose a drastic technical change to users.

  All Hiphop.js keywords are capitalized. MODULE defines a module, here the whole Hiphop.js program. IN and OUT declare the program interface. A Hiphop.js program is executed as a succession of atomic reactions, each handling input signals and possibly generating output signals.

	startIntervalIfNeeded (); }
	3.2 Hiphop.js implementation
	Let us first ignore the Reset button with a BasicTimer:
	MODULE BasicTimer {
	IN duration (0);
	OUT elapsed ;
	EMIT elapsed (0);
	LOOP {
	IF ( VAL ( elapsed ) < VAL ( duration )) {
	RUN ( TimeoutMod (100));
	EMIT elapsed ( PREVAL ( elapsed ) + 0.1);
	} ELSE {
	PAUSE ;
	}
	}
	}
	setInterval ( tick , 100);
	}
	function resetE () {
	E =0; $ (" meter "). value = E ; clearTimeout ( id ); id = -1
	startIntervalIfNeeded ();
	}
	function setD ( value ) {
	D = value ; $ (" meter "). max = D ;

  Reset is achieved by another temporal statement called LOOPEACH placed around the unmodified BasicTimer module:

	MODULE Timer {
	IN duration (0) , reset ;
	OUT elapsed ;
	LOOPEACH ( NOW ( reset )) {
	RUN ( BasicTimer );
	}
	}

https://github.com/eugenkiss/7guis/wiki#time

EXTENDED IMPLEMENTATION

The GUI is extended with a Suspend button:

< button id =" susp " onclick =" susp ()" > Suspd </ button >

New JavaScript implementation

Events triggered by the Suspend button are handled by: The orchestration becomes more complex to understand; the whole program has been modified in a non-local way by adding isSusp, patching existing functions, and adding another function.

New Hiphop.js implementation

The new Hiphop.js SuspendableTimer is as follows: