Narrative Javascript

I was going to post this to the front page, but it's already a Forum Topic. So go there to read about a preprocessor that adds continuations to JavaScript by transforming to CPS (I think).

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Posted in Python?

I think LtU should have an Javascript/EcmaScript department!

ooops - removed the python

ooops - removed the python tag. sorry about that.

Mini poll

Should we?

I've no problem with that...

...though if you wanted to be more general, it'd probably be something along the lines of Embedded Scripting, which would incorporate scripting languages that reside inside of other application environments (browser, etc...).

Of course, the problem with using the term embedded is that it connotes real time software, which is not what you're aiming for. Perhaps, Internet Scripting. :-)


How about application-specific scripting languages, that way it isn't tied down to Internet scripting?

re: Internet scripting

Perhaps, Internet Scripting.

But isn't Javascript/ECMAscript also used for things like OS X widgets? Not to mention as the onboard activity description language for the James Webb Space Telescope. Javascript/ECMAscript seems to be moving beyond its "internet scripting" roots. According to Google "embedded scripting" seems to be used more to refer to Javascript-like usage than anything to do with embedded systems, so I don't see a problem with your original suggestion.

I probably complicated the vote more than I should've

The question should probably be more along the lines of what's important from a PL standpoint. Is JavaScript an important PL topic in its own right? Or should the discussion center around the more general idea of embedded PLs?

Personally, I have no problems with adding classifications, other than I dislike seeing a topic added - and then the contributing editors letting it languish. So, really the question ought to be whether there will be enough stories posted to warrant having the topic added.


Application-Embedded Scripting?


Should we?


Dave, if I set it up, you

Dave, if I set it up, you know you are the one who has to make sure good content flows into it, right?

stay tuned

There should be plenty to talk about very soon... I recommend creating a JavaScript topic before this Friday. :)

implicit continuations

a preprocessor that adds continuations to JavaScript by transforming to CPS (I think)

It doesn't quite add full continuations to JavaScript, at least not fully explicit first-class continuations. It adds a facility for registering asynchronous event handlers (such as setTimeout) with the implicit continuation of the caller. For example, instead of writing:

setTimeout(1000, function() { a(); b(); c() })

You'd write:


You're right that CPS is the implementation strategy: by creating an explicit continuation for every statement, the continuation of the setTimeout->(1000) call can be used as the second argument.

Note that without proper tail calls, this compilation strategy won't scale up. A large body of code will result in the confusing too much recursion error message.

Hopefully we should see proper tail calls making into ECMAScript edition 4...

proper tail calls

In Links we have both tail calls and first class continuations in the source language, which we compile into CPS JavaScript. We make further use of the continuations to implement processes. There's a choice of tricks to accomplish TCO (trampolines, etc.); the method we chose is to call setTimeout() every n function calls, passing the continuation as the parameter. After calling setTimeout the calling thread exits (by simply returning). This method has (at least) two benefits:

  • setTimeout throws away the stack, so we don't get the confusing too much recursion message
  • it gives other processes an opportunity to run, so we get a sort of simple scheduler "for free".

As long as we're improving JavaScript....

...what's the chance of getting a Yield (wait, nice, etc...)? It's frustrating to have to divvy up a cpu intensive task into chunks that allow the threads to interleave properly.


Not sure if accomplishes what I need...

...but then I'm not sure what I need is really a language issue. Generators and the yield here will be nice features for sure, but AFAICT they are geared towards inter-javascript continuations.

From a perspective, my main frustration at the moment has to do with the fact that the browser in which the JavaScript runs doesn't seem to play multitasking very well. If you have some intense JavaScript, the user is locked out from doing anything other than waiting for the script to complete. Indeed, the browsers have recently gone to detecting intense JS and issue a warning message that allows you to abort the script.

What I need is a way to do scripting that occurs in the background as the user is going through the forms. The scripting shouldn't effectively lock out all aspects of the browser (or whatever environment you happen to be scripting in). A simple Relinquish or Nice operation that could be scattered in the JavaScript, that would allow other non-script related activities to jump into the Round Robin sure would be nice.

But as I say, this is not really a JavaScript language feature, so much as it is something that would allow the JavaScript to be a little less painful to write. If the Yield described in the slides can be used to accomplish something along these lines, then I'd be a happy camper - effectively yielding for a finite amount of time to surrounding application.


I suspect setTimeout does what you want. See Jeremy's comment, "proper tail calls". I've used setTimeout to do TCO in a very intensive program, but a side effect of using setTimeout is that the program won't trigger browser warnings, and leaves the browser responsive.

That's the workaround...

...but it means you have to divide up the processing in terms of discrete function calls. Kind of what I'm complaining about- if I have to go off in a loop for a thousand items, I have to do it as a chopped up series of some arbitrary number (do 50, call setTimeout, do 50 more, etc....). Oc course, how you chop it up depends on how time consuming it is - i.e. how it effects the responsive for the UI.

[Edit Note: I suspect a tail call may do the trick, so I'll have to investigate further.]

[Edit/Edit Note: What I mean is that if you have proper continuations, you could emulate a wait(n seconds) type of command by throwing the storing off the current continuation point, calling a timeout, and then having the timeout jump back to that continuation point. Still, it be nicer to just call that wait().].

I think this will work for you

Narrative JavaScript does exactly what you describe here. (Look for the example sleep() method in the docs.) Give it a shot and drop me feedback whether you like it or not.

Looks to be what I'm looking for

Unfortunately I got deadlines looming - having to become an instant expert in formulary drugs over the next week - so it'll be a week or two till I get around to testing.

I've run into this problem in a number of apps that I've written. One was a cement analysis program that processes log information - gets pretty intense as the data being processed can be in the multi-megabyte range. Also run into on some of the more complex forms that I've coded around.

Though I can use it for some practical applications, I'll probably test it out on my toy Unlambda interpreter first, where the fibonacchi program kills firefox at the moment. The reason I mention this page is that I've a slight suggestion for the Narrative JavaScript compiler. Currently it seems to work exclusively with file i/o for the compilation process - which for most long term use is the best way to use the compiler. However, for those of us that are experimenting, it might be nice if you just had a web page that allowed you to paste the code to be translated into a textarea, punch a button and have the translated code spit out in another textarea. This is pretty well what Chris Barker's combinator calculator does (which I lifted and modified in the above link).

Good idea

The web-page compiler is a good idea. I'll put it high on my to-do list. Thanks.


Running it within a web page, you'll probably need some sleep() statements interspersed here and there, just in case the compiler gets into some tight loops (and the user wants to abort the process). :-)

Partial CPS

..but it means you have to divide up the processing in terms of discrete function calls. Kind of what I'm complaining about- if I have to go off in a loop for a thousand items, I have to do it as a chopped up series of some arbitrary number (do 50, call setTimeout, do 50 more, etc....).

I agree that a function to do this properly is the right solution. But it's possible to abstract out the divvying up of processing fairly well. I typically use a function which takes a continuation function and counts the number of times it's been called, invoking setTimeout on every Nth call:

var call_max = 300;
var call_count = 0;

// note that k should be a continuation function, i.e. don't
// expect counted_call to return a value to its caller.
function counted_call(k) {
    if (call_count < call_max) {
    } else {
        call_count = 0;
        setTimeout(k, 0);

It's often possible to get away with calling this function in a few strategic places, e.g. in general recursion functions and in status display functions. For example, put it inside fold functions, and use those fold functions to do your iteration and recursion:

// fold_left(f, init, xs, k) : typical fold_left adapted for 
// Javascript arrays.  k should be a continuation.
function fold_left(f, init, xs, k) {
    var loop = function (result, i) {
        if (i < xs.length)
            counted_call(function () { loop(f(xs[i], result), i+1) });
    loop(init, 0);

With a little library of functions like this, the main program may not need to worry about anything except constructing continuations to pass to the library functions. If counted_call is being called frequently enough — which it should be if all your iteration and recursion is going through functions such as these — then UI responsiveness should not be an issue. The browser will have plenty of time to breathe, and performance of the program shouldn't be significantly affected.
Just for completeness, here's a test function for the above, although not a very realistic one:

function test() {
    var testdata = [];
    for (i = 0; i < 10000; i++) {
        testdata.push(Math.floor(Math.random() * 100));
    fold_left(function (n, sum) { return n+sum }, 0, testdata, 
       function (x) { alert(x) });

Two possible downsides to this are that (a) your Javascript code will no longer all be idiomatic; and (b) constructing continuation functions can be unnatural in some cases. But in most cases, given the kind of stuff one is doing in a browser, it's easy enough.

BTW, I'm not arguing against using a tool to do the CPS rewrite automatically — that ought to be a fine solution.

Small improvement

This is very nice, but one suggestion: I would use time in the counted_call, performing a setTimeout every 50ms or so.

Too much recursion

Have you tried that? The problem with using time is that it's not correlated to stack depth. You'd have to figure out the right interval for a given machine, at least. For example, testing on a 1GHz machine, 50ms is too long and blows the stack. Something under about 20ms will work, but on a 2GHz machine, you have to reduce it to 10ms. But back on the 1GHz machine, 10ms makes a program run noticeably slower.

[[Edit: I realized I'm thinking in terms of using this code to support recursion (and suspend/resume), which is the main way I've used it. The fact that it makes the browser behave better is just a bonus for me. For what Chris wants to do, he could (try to) avoid recursion, and in that case you're right that a 50ms interval ought to work fine.

However, it would then be necessary to pay closer attention to when a function like counted_call is called. For example, if you have a long-running Javascript 'for' loop, it's much messier to call setTimeout or a function like counted_call from inside the for loop, because it has state that'll be lost. Using recursive operations like fold solves this problem, and provides a natural place to encapsulate calls to counted_call. But that means you need to be able to handle unbounded recursion, which means counted_call needs to be careful about stack depth, which explains my original response at the beginning of this comment.]]

good idea

That's a pretty nifty solution. I'll have to think about how that might be added into NJS.

Lightweight threads

I put a very simple lightweight thread example togther using Narrative Javascript. It uses the setTimeout trick described in comments above to stop the too much recursion error, and to give time back to the browser.