JS control-structure abstractions, using tailnest flattening and tailcall optimization

Claus Reinke claus.reinke at talk21.com
Fri Jul 8 07:34:09 PDT 2011


Dear all,

we have seen examples of how to define control-structure
abstractions via block-lambdas (and Smalltalk blocks), including
non-local returns out of user-defined loops.

I'd like to provide an example of how to do something like this 
with JS, using only the proposed syntactic sugar for flat syntactic 
tailnests and the upcoming support for flat runtime tailcall stacks 
(for callback chains, the two complement each other).

Building up from small structures, the example aims to implement 
a variant of "yield". With conventional blocks, this requires the 
upcoming generators language extension. Block-lambdas do 
not help here, I think, because yield can suspend and resume at 
statement level, and even the slightly unusual sequel feature 
does only support non-local return, no resume (calling a sequel 
returns to a lexically scoped elsewhere, not to the caller). 

If JS had call/cc or delimited continuations, we could implement 
yield on top of that, but that isn't likely. If we were to rewrite our 
code in continuation passing style (cps), we could implement 
call/cc, but even in languages with lightweight function syntax, 
that is not considered very readable. There are modular variants 
of continuation passing style that can be made to look very similar 
to "normal" code, but these become unreadable in JS syntax. 
Cps without tailcall optimization also quickly overflows the stack.

Which is where tailnests (readability) and tailcalls (efficiency/
useability) come in, addressing the issues that cps in current 
JS leads to overflows in syntactic and runtime stack nesting.

First, the programming pattern: in plain cps, we'd have nested 
callback chains feeding intermediate results into the rest of the
callback chain (assuming currying for the callback parameter):

    operation(..)( function(result) { ..operations..} )

With paren-free right-associative calls (f @< arg) and brace-free
definitions (function(arg) => expr) for expression functions, this
becomes:

    operation(..) @< function(result) => ..operations..

Tailcall optimization guarantees that the callbacks will not 
overflow the runtime stack, and tailnest flattening keeps the
level of syntactic nesting independent of the chain length.

In modular cps, instead of every operation taking a callback
parameter, every operation returns its result in an object 
implementing a single method 'then' (the ideas are standard,
the translation to JS is not). Calling 'then' with a callback feeds 
a value/intermediate result to the callback.

    operation(..).then @< function(result) => ..operations..

(which can be read as a clumsy way to write
"let result <- operation in operations", but the ".then" allows
us to give different meanings to the variable binding, eg., it
could mean "foreach result from operation, do operations", or 
it could store the continuation and jump elsewhere, as yield)

The most basic operation is 'value', which just wraps a value
into a "then-able":

    function value(val) => { then : function(cont) => cont(val) }

Since statements represented as then-ables are objects, 
conditional statements are just conditional expressions:

    cond ? t : e

or, if the condition involves then-able statements, too:

    cond.then @< function( c ) => c ? t : e

which we can either use directly, or wrap in a function (the 
then/else-branch arguments are themselves wrapped to 
delay their evaluation):

    function if_(cond) => function(ft) => function(fe) =>
        cond.then @< function( c ) => c ? ft() : fe()

Hence, a while-loop with then-able condition and delayed body:

    function while_(cond) => function(body) =>
        if_(cond)
            (function() => body().then @< function() => 
                                    while_(cond)(body) )
            (function() => value( null ) )

You can find these examples online [1], so to limit this email,
I'll jump right to the interesting bit, which is implementing yield:

"yield_(val)" produces a then-able that behaves a bit unusually:
instead of passing a value to continuations passed via ".then()",
it swallows all such continuations, storing them for later use
(in plain cps, we'd have the whole continuation at hand; in this
modular cps variation, we have to collect nested continuations).

To get at the yielded value, we can call "yield_(val).value(cont)",
and to restart the "generator", we can call "yield_(val).next()",
which applies the internally stored continuations to "val". In code:

    function yield_(val) => { then: stack(val) };

    function stack(val) => function(c1) =>
      { then:  function(c2)   => stack(val)(comp_then(c2,c1))
      , value: function(cont) => cont(val)
      , next:  function()     => c1(val) }; 

    function comp_then(c2,c1) => function(val) => c1(val).then(c2);

Again, the commented code and a couple of example generators 
can be found online [1]. If you use the desugaring page, you can 
see why this style isn't popular without syntactic sugar. But the
functionality is plain JS, no semantic changes! 

The code could be made more readable by providing 
"let <-"-desugaring to then-ables, but JS is different enough from
other languages providing similar features that I want to make 
sure that this pattern is the one to aim for before proposing that. 
The code could be shortened further by combining  arrow-syntax 
with "@<", instead of the less ambitious expression functions of 
the tailnests proposal. And extended object-literals would shorten
inline then-ables.

Claus

[1] https://github.com/clausreinke/jstr/tree/master/es-discuss

    Examples are in then.js, but if you clone the repo, you can
    load them via tailnests.html, desugar into plain JS via jstr, 
    and evaluate the resulting code. So you can play with it!-)

 


More information about the es-discuss mailing list