J is for JavaScript: A direct-style correspondence between Algol-like languages and JavaScript using first-class continuations

It is a time-honored fashion to implement a domain-specific language
(DSL) by translation to a general-purpose language. Such an implementation is more portable, but an unidiomatic translation jeopardizes performance because, in practice, language implementations favor the common cases. This tension arises especially when the domain calls for complex control structures. We illustrate this tension by revisiting Landin’s original correspondence between Algol and Church’s lambda-notation.

We translate domain-specific programs with lexically scoped jumps to JavaScript. Our translation produces the same block structure and binding structure as in the source program, a la Abdali. The target code uses a control operator in direct style, a la Landin. In fact, the control operator used is almost Landin’s J—hence our title. Our translation thus complements a continuation-passing translation a la Steele. These two extreme translations require JavaScript implementations to cater either for first-class continuations, as Rhino does, or for proper tail recursion. Less extreme translations should emit more idiomatic control-flow instructions such as for, break, and throw.

The present experiment leads us to conclude that translations should preserve not just the data structures and the block structure of a source program, but also its control structure. We thus identify a new class of use cases for control structures in JavaScript, namely the idiomatic translation of control structures from DSLs.