This section discusses the differences (and similarities) of JavaScript and Scheme. We limit this comparison to the most significant parts of the two languages. JavaScript has been inspired by Scheme, and most of the similarities are hence not astounding. The following list enumerates some of the shared features:

• types are dynamically checked,
• functions are first class citizens,
• lexical scoping,
• automatic memory management,
• an eval function, which allows one to compile and run code at run-time, and
• n-ary and var-arg functions with an apply primitive that allows to indirectly call these functions on a list or array of arguments.

In other areas JavaScript is however quite different from Scheme. The move from Lisp-style syntax to C-like syntax is certainly the most striking difference, and Section Optimizations3.4 mentions the expression to statement pass which has been implemented as a consequence of the C-like syntax. Other changes have nevertheless far greater impact on the development of a Scheme to JavaScript compiler. Especially JavaScript's peculiar syntactic scoping of variables makes the compilation difficult. In JavaScript a variable declaration is valid for a complete function block wherever the declaration is located. Section Flow Control3.3 shows why this behavior complicates the compilation.

As we will see in the next section, the data types aren't equal either. JavaScript has less data types, and the matching types are not always equivalent. JavaScript strings, for instance, are (contrary to Scheme strings) immutable, and JavaScript numbers are always floating point (whereas Scheme has exact numbers too).

Another difference is the lack of call/cc in JavaScript. The existing try/catch partially compensates for the absence, but is not as powerful as call/cc

JavaScript has basically four main types: booleans, numbers, strings, and objects. Functions are of type object and don't have their proper data type. The JavaScript specification [8] additionally cites undefined and null as respective types. Scheme, despite being a smaller language, uses four more types: pairs, vectors, characters and symbols.

Scm2Js maps Scheme's

• booleans to booleans.
• functions to JavaScript functions.
• numbers to JavaScript numbers. Even though this mapping seems obvious, it makes Scm2Js non conform to R⁵rs. JavaScript's numbers are always floating point, whereas Scheme differentiates exact and inexact numbers.
• pairs to the JavaScript "class" sc_Pair with fields car and cdr. The empty list is represented by null.
• vectors to JavaScript Arrays.¹
• characters to the "class" sc_Char, holding a JavaScript string of length 1.
• strings to a new JavaScript "class", sc_String. It is not possible to reuse JavaScript's strings, as they are immutable. sc_String itself holds one of these immutable strings, and replaces it, when necessary.
• symbols to strings.

JavaScript's typing rules are less restrictive than Scheme's rules. Due to implicit conversions many operations that are errors in Scheme are valid expressions in JavaScript. Scm2Js takes advantage of R⁵rs' liberal error handling. Implementations are rarely forced to detect and signal errors, but are free to handle most errors the way they want to. In particular "[...] it is an error for a procedure to be passed an argument that the procedure is not explicitly specified to handle [...]. Implementations may extend a procedure's domain of definition to include such arguments". In our case, errors are handled by JavaScript. If an operation yields an error according to the JavaScript specification, an error is signaled. If however JavaScript is able to handle an expression that would be invalid in Scheme, no error is reported. The following examples demonstrate this behavior: (car '()) is an invalid expression in Scheme. Scm2Js compiles this expression to null.car. As null doesn't have any fields, JavaScript throws an exception. The compiled version hence raises an error. In the following (invalid) code snippet we try to add a symbol to a number: (+ 3 'sym). The translated code would be 3 + 'sym' which is a valid JavaScript expression concatenating the two strings "3" and "sym". In this case no error will be detected.

Similar missed errors happen when functions are not passed the correct number of arguments, in which case either missing arguments are filled with a special #unspecified value, or additional arguments are ignored.

Scheme has only few flow-control constructs, and all of them have similar counterparts in JavaScript. A direct mapping is however impossible. R⁵rs requires Scheme implementations to be properly tail-recursive. JavaScript on the other hand doesn't even mention this feature. Mapping Scheme function calls naively to JavaScript function calls is hence dependent on the JavaScript implementation and not always² conform. Two popular solutions are trampolines and Henry Baker's "Cheney on the M.T.A." [6]. The concept of trampolines needs the modification of all call locations. Tail calls are replaced by instructions that save the call target and arguments in global variables, followed by a return. Non tail calls, on the other hand, are wrapped into an iterative loop. Initially the original call target is executed. Once the function returns the trampoline checks for the existence of a function in the global variable that temporarily holds the tail call targets. If this variable is not empty the stored function is executed, and the trampoline waits for the next return.

Even though trampolines solve the initial problem of rapidly growing stacks, they are inefficient. Tail calls need to manipulate the global variables, whereas non tail call must be wrapped into an iterative loops. An optimized version of trampolines is presented in [11]. Instead of returning at every tail call, the program is allowed to stack a constant number of tail calls. Only when the limit is reached the continuation is stored in the global variables, and the trampoline is used.

"Cheney on the M.T.A.", on the other hand, transforms the program into Continuation Passing Style (CPS) first, and thereby eliminates the need for stacks. In the paper the authors propose to use the stack as short term memory. Whenever the stack reaches the stack limit a garbage collection is performed, and the program restarts with an empty stack. The stack becomes the youngest generation in a generational garbage collector.

All these techniques introduce some performance penalty and we therefore decided not to implement any. For now Scm2Js just tries to compile tail-recursive calls into iterative JavaScript statements. This approach is however incomplete as it is impossible to statically determine all call-targets. Scm2Js is able to transform the most common recursive calls (like let loop constructs) but leaves other more difficult tail recursive calls untouched.

Even when the call-targets have been determined the tail-rec to iterative transformation is not trivial. A let loop construct, for instance, is mapped to JavaScript's while statement.

Example:

(let loop ((x 1))
  (if (> x 10)
      'done
      (loop (+ x 1))))

is compiled as:

var res = undefined;
var x = 1;
while (true) {
  if (> x 10)
     res = "done";
  else {
    x = x + 1;
    continue;
  }
  break;
}

This simple mapping is efficient but it may break down when closures are built in the body of the loop:

1: (let loop ((x 1))
2:   (store! (lambda () x)) 
3:   (loop (+ x 1)))

In this example the loop variable x is captured by anonymous functions in line 2. The captured x is however freshly allocated at each recursive call and is hence different for each of these functions. An invocation of two different closures would yield two different results. The previous transformation on the other hand hoists loop variables outside the loop, which implies a shared x for all anonymous functions:

1: var res = undefined;
2: var x = 1; 
3: while (true) {
4:   store(function() { return x; });
5:   x = x + 1; 
6:   continue;
7: }

x is now outside the loop (line 2) and it's value is physically modified at each iteration (line 5). As the variable is allocated outside the loop all anonymous functions reference the same x. As this variable is physically changed during each iteration, all anonymous functions return the same result (i.e. the final value of x) when executed.

In JavaScript locally declared variables are visible within the whole function body, and declaring a new variable within the while body doesn't solve this issue. The following code demonstrates this unfruitful attempt:

var res = undefined;
var x = 1;
while (true) {
  var tmp_x = x;
  store(function() { return tmp_x; });
  x = x + 1;
  continue;
  break;
}

Even though tmp_x is declared inside the while construct, the peculiar JavaScript scoping rule makes it visible with the complete function. In practice this means that the order and location of variable declarations is ignored and that there exists never more than one variable of the same name. Once a variable has been declared future declarations of variables of the same name are ignored. In our case this means that the anonymous functions share the same variable (this time tmp_x) again.

There are only two ways of creating new scopes in JavaScript: functions and the with construct. Indeed anonymous functions solve the captured variable problem:

var res = undefined;
var x = 1;
while (true) {
  (function(x) {
    store(function() { return x; });
  })(x);
  x = x + 1;
  continue;
  break;
}

Although they partially defeat the purpose of the iterative while statement (i.e. removing the unnecessary applications), they don't fill the stack and are hence a great improvement over recursive function calls. It is furthermore possible to limit the anonymous function to parts of the loop-body. If the captured variable is only used within one branch of an if it is not necessary to invoke the function in the other branch. Anonymous functions are however too limiting: some JavaScript constructs don't work over function boundaries, and in particular the continue statement must not be moved inside another function.

JavaScript's with statement on the other hand fullfills all our requirements. with takes an object as parameter and pushes it on the execution context stack. Every field of the pushed object becomes a local variable limited to the with scope. It is hence sufficient to create an empty object, store the captured variables in the fields of this object, and finally use the with construct to push it on the execution context stack.

var res = undefined;
var x = 1;
while (true) {
  var tmp = new Object;
  tmp.x = x;
  with(tmp) {
    store(function() { return x; });
  }
  x = x + 1;
  continue;
  break;
}

Some benchmarks indicate that, depending on the interpreter, pushing an empty object on the execution context stack is slightly slower or faster than function calls.

This section discusses common optimizations and compiler techniques and shows how they apply to our compiler Scm2Js. Due to the high level of JavaScript only few optimizations are applicable. It is for instance not easy to take advantage of a typing pass as one can't pass typing information to JavaScript interpreters. We did however implement (amongst others) an inlining optimization.

Scm2Js's inlining is done in two steps. A first pass inlines user functions, whereas a second pass inlines runtime procedures. The first pass is rather rudimentary but fulfills its design goal, to inline all let loop expressions. When a variable is bound to a function and when it is only used once in functional position, then it is inlined. The first condition avoids us to do a control flow analysis, whereas the second condition avoids code growth.³ Even though this optimization is quite limited, it reduces the execution time of some benchmarks to less than 50%

A straightforward compilation of Scheme programs to JavaScript programs maps Scheme calls to JavaScript calls. In many cases this translation introduces an overhead. In particular binary operations like +, -,or % are far less efficient if called via a runtime function. A second pass therefore replaces function calls to specific library functions with the more efficient version: sc_plus(x, y) would become (x + y). Other examples for this optimizations are all list primitives (car, cons, null?, etc.) and vector functions (vector-ref, vector-set! or vector-length). This optimization is especially important as it gives a speed improvement of up to a factor of 25.

We conclude this section with a problem many Scheme compiler encounter: Scheme is expression based, whereas JavaScript is statement based. Some JavaScript constructs can only be used at specific locations. It is for instance not possible to use a while loop at the right hand side of an assignment. Scm2Js introduces temporary variables to store the intermediate results of such statements. Interestingly these statements are mostly the result of optimizations. JavaScript has an equivalent expression for most statements: the if statement if (test) s1 else s2 can be replaced by the conditional operator test ? e1 : e2 and the block statement { s1 s2 } by the sequence expression (e1, e2). The tail-rec pass however introduces some statement-only while loops and makes the technique necessary. Some other JavaScript statements without equivalent expressions are continue, return, break, throw, and try.

In order to evaluate the performance of Scm2Js we ran several benchmarks under three Internet browsers on three different architectures:

• Linux/x86: an Intel Pentium 4 3.40GHz, 1GB, running Linux 2.6.15.

  The used browsers were:

  • Firefox 1.5.0.1,
  • Opera 9.0 pre2, and
  • Konqueror 3.5.1

• Apple/G4: a PowerPC G4 1.67GHz, 2GB, running Mac OS X 10.4.5.

  We used the following browsers:

  • Firefox 1.5.0.1,
  • Opera 9 build 3303, and
  • Safari 2.0.3 (417.9.2)

• Apple/Core: a Intel Core Duo 2GHz, 1GB, running Mac OS X 10.4.5.

  We used the following browsers:

  • Firefox pre 1.5.0.2,
  • Opera 9 build 3278, and
  • Safari 2.0.3 (417.9.2)

It turned out, that the choice of browser has far more impact on the performance than the architecture. Firefox and Opera are sometimes up to ten times faster than Safari or Konqueror. The fastest architecture Intel Core Duo is however only four times as fast as the PowerPC G4. More importantly, the browsers behave similar on the different platforms.

Each program was run 10 times, and the minimum time was collected. The time measurement was done by a small script, which launched the benchmarks. Any time spent on the preparation (parsing, precompiling, etc.) was hence not measured.

Every benchmark has been written in Scheme and JavaScript. We then compiled the Scheme versions using Scm2Js and measured the execution times of both the JavaScript code and the compiled version.

Figure 1, 2 and 3 present the ratio of the JavaScript time by the execution time of the compiled program (resp. on the Pentium 4, Apple G4 and Apple Intel Core Duo). A value of 1.0 therefore represents the reference time of the handwritten JavaScript code. Any value lower (resp. higher) than 1.0 means that the compiled Scheme code ran faster (resp. slower) than this code.

In general the compiled code is nearly as fast as the handcrafted version. Even under the worst condition Scm2Js is only about six times slower than the JavaScript version (benchmark Nested under Firefox on the Pentium 4 in figure 1). Nested consists of several nested loops incrementing a counter in the most nested loop. Scm2Js introduces a temporary variable for each loop, and uses this variable twice per iteration. This more than doubles the size of the loop bodies with a respective performance penalty. Apparently Opera handles this case much better than Firefox. Firefox is about three times faster than Opera when run on the JavaScript files, but Opera degrades more gracefully and beats Firefox on the compiled files.

The Quicksort benchmark suffers from the same problem: a very small loop iterates over an array to find elements smaller or greater than a certain pivot.

In less extreme cases, Scm2Js performs quite well, though, and the rudimentary inlining even allows Scm2Js to beat the handwritten JavaScript in some cases (in particular the Bague benchmark).

Hop rests on the closeness of the syntaxes of Scheme and HTML. A simple syntactic transformation turns HTML documents into Hop programs. Hop adds an extra open parenthesis before opening markups and replaces closing markups with single closing parentheses. In addition Hop attributes are introduced by an identifier starting with a colon character (:) and their value is separated from the name by white spaces. Hence the HTML document of Figure 6 is written as shown Figure 7 in Hop.

<HTML>
   <BODY>
      <TABLE width="100%">
         <TR> <TD>0</TD></TR>
         <TR> <TD>1</TD></TR>
         <TR> <TD>2</TD></TR>
         <TR> <TD>3</TD></TR>
      </TABLE>
   </BODY>
</HTML>

(<HTML>
   (<BODY>
      (<TABLE> :width "100%"
         (<TR> (<TD> 0))
         (<TR> (<TD> 1))
         (<TR> (<TD> 2))
         (<TR> (<TD> 3)))))

In the plain version of Hop, the JavaScript expressions of the GUI stratum are delimited by opening and closing curly braces ({ and }). For the sake of the example, Figure 8 shows a program that displays the local time of the client.

(<HTML>
   (<BODY>
      (<P> "The current date is: ")
      (<SPAN> :id "date" "")
      (<SCRIPT> {
          var el = document.getElementById( "date" );
          el.innerHTML = new Date() + "";
      })))

The HTML tree that forms an answer is computed by the expressions of the main stratum. That is, it is elaborated on the server. During that stage, values can be injected inside expressions of the GUI stratum. This is denoted by the escape character $ inside curly braces. The expression following a $ belongs to the main stratum. It is evaluated during the elaboration. Its results is inserted in the expression of the GUI stratum. Simple atomic values such as strings or numbers as well as compound values such as vectors, references to HTML nodes, and, as presented in Section Hop services5.3, functions can be inserted. The source code of Figure 9 illustrates this capacity. First, line 1 a HTML span element is declared. It is inserted in the answer line 5. A reference to this element is injected in the expression of the GUI stratum line 7. In this example, a second expression is injected line 8.

 1: (let ((el (<SPAN> :id "date" ""))) 
 2:    (<HTML>
 3:       (<BODY>
 4:          (<P> "The current date is: ")
 5:          a-span 
 6:          (<SCRIPT> {
 7:              ($el).innerHTML = "client time: " + new Date() + 
 8:                                " -- server time: " + $(current-date); 
 9:            }))))

The expressions of the two strata of a Hop program are evaluated in different heaps and environments. That is, they do not share data. However, they may communicate by the means of service invocations. A service is a function declared on the server. It is defined using the define-service form. As any function it may accept several arguments. A service is invoked from the GUI stratum with a special hop form:

hop( service( a0, a1, a2, ...), callback )

The values a₀, a₁, a₂, ... are the actual arguments sent to the service. Once the server has completed the evaluation of the service's body, i.e., when it has completed the elaboration of the answer, it applies, on the client, the callback function on the service's answer (converted to a string). The code of Figure 10 shows an example where a table of contents is build on the server from information sent by the client. In addition to illustrating the service call line 11, this example also shows that compound data such as vectors may transit from client and server and vice versa.

 1: (define-service (make-toc sections)
 2:    (<OL> (vector-map <LI> sections)))
 3: 
 4: (<HTML>
 5:    (map (lambda (i)
 6:            (<H1> i (map (lambda (j) (<H2> j)) (iota i))))
 7:         (iota 3))
 8:    (let ((toc (<DIV> "Toc: ")))
 9:       (<BUTTON> :onclick {
10:                    var hs = document.getElementByTags( "h1" );
11:                    hop( $make-toc( hs ), 
12:                         function( res ) { ($toc).innerHTML = res; } );
13:                 } "Click to view the table of contents")))

The Scm2Js compiler lets us replace JavaScript with Scheme in Hop programs. In this new version, the curly braces are replaced with the ~ escape character that introduces expressions of the client stratum. During the elaboration stage, Scheme client expressions are compiled on the fly into JavaScript. The source code of Figure 11 is a direct re-writing of Figure 10.

 1: (<HTML>
 2:    (map (lambda (i)
 3:            (<H1> i (map (lambda (j) (<H2> j)) (iota i))))
 4:         (iota 3))
 5:    (let ((toc (<DIV> "Toc: ")))
 6:       (<BUTTON> :onclick
 7:                 ~(let ((hs (document.getElementByTags "h1")))
 8:                     (hop ($make-toc hs)
 9:                          (lambda (res)
10:                             (set! $toc.innerHTML res))))
11:                 "Click to view the table of contents")))

As it can be noticed, the dot-notation of Scm2Js is strongly relevant in the context of Hop. It enables a compact notation for reading and writing fields of instances which are frequent in Hop.

In combination with Scm2Js, we have added a new construction to Hop, namely the with-hop form. Its syntax is:

(with-hop (service a0 a1 a2 ...) continuation)

This form invokes the service with the arguments a₀, a₁, a₂, .... On completion of the invocation, the continuation is applied. Contrary to the hop service invocation presented in Section Hop services5.3, the value sent to the continuation is no longer a string but any simple or compound data type. In particular, Hop is able to automatically create, on demand, classes on the client. That is, when an instance is returned to the client as a result of a service invocation, in addition to sending the object, Hop also sends to the client the code required for declaring the class anteriorly. This enables Hop expressions to access objects independently of the strata. This is illustrated in the example of Figure 12. In this example, a class software is declared in the main stratum (line 24). Instances are created in the service query-by-name and sent back to the client (line 10). On the GUI stratum (line 27, 28, and 29) the value returned by that service is directly accessed as a class instance.

 1: (module example
 2:    (library sqlite)
 3:    (class software 
 4:       name::string
 5:       author::string
 6:       version::string
 7:       license::string))
 8: 
 9: (define-service (query-by-name name) 
10:    (sqlite-select make-software "softwares WHERE (name = ~a)" name)) 
11: 
12: (let ((name (<INPUT>))
13:       (version (<INPUT>))
14:       (license (<INPUT>)))
15:    (<HTML>
16:       (<BODY>
17:          (<TABLE>
18:             (<TR> (<TD> name))
19:             (<TR> (<TD> version))
20:             (<TR> (<TD> license)))
21:          (<INPUT>
22:             :type 'text
23:             :onkeyup ~(if (= event.keyCode 13)
24:                           (with-hop ($query-by-name this.value) 
25:                              (lambda (o) 
26:                                 (when o 
27:                                    (set! $name.value o.name) 
28:                                    (set! $version.value o.value) 
29:                                    (set! $license.value o.value))))))))) 

The previous section detailed only one way of inserting Scheme code into Hop documents. Another way consists of including complete Scheme files (usually libraries) in the <HEAD> section of the page. Figure (ref :figure "file-include") shows an example where two files are included: one JavaScript file, and one Scheme file. The Scheme file is compiled on the fly and then sent the same way as the JavaScript file.

(<HTML>
   (<HEAD>
     (<HOP-HEAD> :jscript "jslib.js")
     (<HOP-SCHEME-HEAD> :sscript "schemelib.scm"))
   (<BODY> "some body text"))

We mentioned in Section JavaScript Integration4 that there are different ways of interfacing with Scheme code. Either the safe interface using js directives, the explicit mode accessing the *js* variable, or the unsafe way where all unbound symbols are considered to be implicitly imported global variables.

In the context of Hop we opted for the unsafe interface. It is the easiest way of combining external files and injected code. Even if external file came with a header file a safe compilation would still be extremely difficult. Scheme code in Hop files is often out of order (the code for a button click might be before the main script with important initializations and declarations) and all injected Scheme expressions are compiled upfront when the file is loaded. The out of order compilation implies potentially undefined variables at early locations, and the upfront compilation means that we don't have any relationship between the different Scheme pieces. Two Scheme expressions might be part of the same page (and should hence share the same variables) or might be completely separated entities (or even dead code). The unsafe interface has however advantages too, and we found it comfortable to use JavaScript libraries without the hassle of import/export declarations.

Replacing JavaScript with Scheme on the client stratum has its pros and cons. On the positive side, it enforces the cohesion between the two strata. Scheme and JavaScript are similar languages but they promote slightly different programming styles. For instance, Scheme promotes recursions and higher-order operators, while JavaScript promotes loops and iterators. Hence, while replacing JavaScript with Scheme does not bring new functionality to Hop, it, undoubtably, makes programs look nicer. A single, coherent syntax is used which gives the feeling of a continum from the server to the client and vice-versa. Switching from server programming to client programming does not require much intellectual effort.

On the dark side, it could be argued that using a single syntax, inside a single source code, for expressions evaluated in different environments and libraries is prone to error. The early experiments tend to show that is not a dramatic drawback. Only the experience will tell if using a single syntax for both strata is a benefit.