Flapjax won the OOPSLA MIP award for 2009 (though the SIGPLAN website isn’t yet up to date). Our blog post is about the slightly unconventional way we worked: most of the Flapjax work happened in 2006 and 2007, but we didn’t even try to write the paper until several years later (Leo and I were in grad school). Rather than recapitulate those ideas, go read the post!

Flapjax is nothing more than a coherent set of callback combinators. The key insight to this set of callback combinators is the “Event” abstraction — a Node in FJ’s implementation. Once callbacks are Nodes, you get two things:

1. a handle that allows you to multiply operate on a single (time-varying) data source, and
2. a whole host of useful abstractions for manipulating handles: mergeE, calmE, switchE, etc.

The last I saw the implementations of Resume and Continue, they were built using this idea. The more I think about it, the more the FJ-language seems like the wrong approach: the FJ-library is an awesome abstraction, in theory and practice.

I have to say, I can breathe a sigh of relief now that the expression problem has been solved in JavaScript. All of the interpreters and compilers I’d written in JavaScript were so inextensible!

Then again, I’m not sure I’ll ever get the chance. It’s interesting that PL — and many other fields — is often more defined by the tools it happens to use (or happened to use at some point in the past) rather than problems of interest. What circumstances determine the used features of a programming language? How can feature use be encouraged (or discouraged)?

I consider the (excellent) Flapjax tutorial prerequisite reading, so it will be hard to follow along if you’re not vaguely familiar with Flapjax.

The following code is all working JavaScript (in Firefox, at least), so feel free to follow along.

We’ll define a few functions and classes:

1. timer_e, the simplest event stream
2. Event, the class defining event streams
3. showStream, a way to show event streams on the page
4. lift_e, our focus, a way to apply standard operations to event streams
5. hold_e, a lead in to behaviors
6. Behavior, event streams that continuously have a value
7. lift_b, lift_e extended to Behavior

It really will help to follow along, typing in the code: it helped me when I wrote all of this back in March! I could post the collated code from this, but I don’t see the point: it’s all here. If you’d like to see it, just ask away.

Our first event stream: timer_e

We’ll jump right in and define timer_e. timer_e is a timer that fires events at a given interval. JavaScript veterans will ask: how does timer_e differ from window.setInterval? The DOM API function window.setInterval registers a callback: it takes a function and an interval i, and calls the function every i milliseconds. timer_e takes an interval i and returns an event stream; every i milliseconds a new value (the time in milliseconds since the Epoch) will come down the event stream.

The key difference is that window.setInterval doesn’t return anything: you give it a callback, your callback gets called. timer_e gives you a handle to a value that encapsulates the timer itself. This is useful because the timer can be passed around as a value, allowing you to abstract out that part of your program.

function timer_e(millis) {
  var e = new Event();
  window.setInterval(
    function () { e.newValue(new Date().getTime()); },
    millis);
  return e;
}

Every time the interval — a repeated timer — triggers, the current milliseconds-since-epoch will be sent as a new value on the event stream.

The core event-stream structure: Event

We can make this more concrete by defining Event.

function Event() {
  this.listeners = [];
  this.newValue = function (v) {
    for (var i = 0;i < this.listeners.length;i++) {
      this.listeners[i](v);
    }
  };
  return this;
}

That is, an event stream is just a callback manager, support structure for the observer pattern. Callbacks can be registered on an event stream by running e.listeners.push(...);. To send a new value on the event stream, you can call newValue to notify the listeners. This is how timer_e hooked setInterval up to the Event class: every time the interval called its callback, an event’s newValue method is called with the time since the epoch. (As an aside, Event is called Node in Flapjax, since it represents a node in the callback graph.)

Output: showStream

A function like timer_e is a constructor for integer-valued event streams; that is, Event objects with integer values. For event streams to be useful, we also need a deconstructor for event streams. Since JavaScript runs in browsers, it makes sense to have event stream deconstructors that affect the HTML page through the DOM. In Flapjax, insertDomE is a deconstructor for events with printable values (e.g., strings and numbers, not objects and lists). Given a hook into the HTML page — a unique id, for example — and an event stream, insertDomE will update the HTML page with new values as they appear on the stream.

We’ll write our own, simple version of insertDomE. We’ll call it showStream, since it will do just that: it’ll just write each value out to the DOM.

function showStream(e) {
  e.listeners.push(function (v) {
    var log = document.getElementById('log');
    log.insertBefore(document.createElement('br'), log.firstChild);
    log.insertBefore(document.createTextNode(v), log.firstChild);
  });
}

If you’re running the code, the code below assumes that there’s an HTML block tag (div, say) with id “log” in the document. Alternatively,you could use FireBug and its console.log feature. (It’s a must for JavaScript, anyway.) In this simple example, I just dump out every new value without removing any of the old ones. If you’re following along, why not change the code as an exercise?

If we go ahead and run it, it’ll spit out the time in milliseconds since the epoch once every 100 milliseconds:

var t = timer_e(100);
showStream(t);

You’ll need to run that code in a function called from body.onload, since showStream will only work once the whole page is loaded.

Lifting

The above is enough to see the beginning of a functional reactive system, even though all we’re doing is playing with callbacks. The real payoff of functional reactivity is the ability to manipulate and combine event streams using ordinary operations. The process of applying a standard operator (like + on numbers) is called lifting, and it’s what you came here for.

function lift_e(f, e) {
  var lifted = new Event();
  e.listeners.push(function (v) { lifted.newValue(f(v)); });
  return lifted;
}

What is the type of this function? The first argument is a function. The second is an event e. The function listens to the event that its passed, and returns a new event. For every value v that appears on e, the new, f(v) appears on the stream of the new, ‘lifted’ event. Note that this definition of lift_e can’t use time-varying functions (i.e., function-valued event streams) or functions with more than one argument. This is to clarify the core idea of lifting; in Flapjax, lifting works for time-varying functions of arbitrary arity. If you’re following along, try it as an exercise — it’s not too difficult, but it’s not trivial. If you do it without looking at what Flapjax does and reimplementing it, I’d be curious to see what you, dear reader, come up with.

In any case, let’s see this in action! We’ll run a lifted function. (This example is ‘lifted’ from the Flapjax website’s second “time” demo.)

var t = timer_e(100);
var t2 = lift_e(function (v) { return Math.floor(v / 1000); }, t);
showStream(t2);

If you’ve been following along, you’ll notice a problem. Redundant values keep getting spit out! The setInterval call in timer_e regularly sends events down the stream, and the lift_e call will happen every time an event occurs. The division and truncation occur ten times a second (or so) with the same result!

Avoiding redundant events: hold_e and Behavior

How can we avoid these redundant events? We need a function to ‘hold onto’ the last value and not propagate identical values. This is quickly and easily written:

function hold_e(e) {
  var held = new Event();
  var valueNow;

  e.listeners.push(function (v) {
    if (v !== valueNow) {
      valueNow = v;
      held.newValue(v);
    }
  });

  return held;
}

We keep the last value seen in valueNow, only propagating new values. (We should probably use a more robust version of equality than === and !==, but that’s irrelevant in this tutorial, where we’ll only use integer-valued events.) If we change the last example to:

var t = timer_e(100);
var t2 = lift_e(function (v) { return Math.floor(v / 1000); }, t);
var t3 = hold_e(t2);
showStream(t3);

Success! Only one message per second appears in the log. In Flapjax, this isn’t exactly the way hold_e is defined. In fact, this definition has a small problem that doesn’t come up with timer_e, but can with other event sources. What happens in lift_e and showStream if no value has come along on a held stream yet?

The first observation is that we have in valueNow a ‘current’ value, a way to track the most recent value sent on an event stream. In fact, even though we don’t give it an initial value syntactically, valueNow has one — undefined! If we turn valueNow into a member variable of a class, rather than a scope variable in a closure, we could use it in functions in place of a default value. The Flapjax solution is to create a subtype of Event, called Behavior. (Actually, it’s to create a subtype of Node called Behaviour. Oy.) Defining this new class isn’t difficult, but it does showcase JavaScript’s funniness.

function Behavior(e, init) {
  Event.call(this); // call ’super’ constructor
  this.valueNow = init;

  var _this = this; // capture this, so we can reference it in a closure
  e.listeners.push(function (v) {
    if (v !== _this.valueNow) {
      _this.valueNow = v;
      _this.newValue(v);
    }
  });

  return this;
}

To paraphrase, a Behavior is an Event with an additional member valueNow; it only propagates events that are different from this value. Basically, we’ve woven together hold_e and Event.

To demonstrate the new form of propagation:

var t = timer_e(100);
var t2 = lift_e(function (v) { return Math.floor(v / 1000); }, t);
var b = new Behavior(t2, 0);
showStream(b);

Our (trusty?) old lift_e will work on this structure: it is an event, after all! But we still don’t do anything with valueNow. Fortunately, we can reuse lift_e in writing a new lifting form for Behavior:

function lift_b(f, b) {
  return new Behavior(lift_e(f, b), f(b.valueNow));
}

Note the subtype-punning with the nested lift_e. Readers familiar with functional-programming will see that we’ve simply threaded the lifting through the new (underlying) datatype.

Using lift_b, we can extend our old example cleanly:

var t = timer_e(100);
var t2 = lift_e(function (v) { return Math.floor(v / 1000); }, t);
var b = new Behavior(t2, 0);
var b2 = lift_b(function (v) { return v % 10; }, b);
showStream(b2);

But we can also show that valueNow is propagated correctly:

var e = new Event();
var b = new Behavior(e, 0);
var b2 = lift_b(function (v) { return v + 1; }, b);
assert(b2.valueNow == 1) // even though no events have been sent

If we so chose, we could extend showStream to work with valueNow. If you’re following along, try it as an exercise! (I love saying that, particularly since I don’t have to do it!)

Now that we have a solid understanding of lifting, we can finally understand what the difference is between just using Flapjax and using the Flapjax language, via the compiler. Using Flapjax as a language, you have to manually lift operations on Flapjax’s time-varying values. When you use compiled Flapjax, this lifting happens automatically. How? Stay tuned!

I’ve implemented a few optimizations to reduce the number of times it needs to be called, but its recursion is brutal. The DOM treeWalker might be more efficient than what I have now. I don’t think it can matter much, because according to this website, IE and Safari don’t support it.

Thinking about it clearly, the problem had to be in cloneNode. I ended up having to write the following recursive fix-up function:

/**
 * List of all DOM event handler names.
 */
var dom_events = 
['onblur', 'onfocus', 'oncontextmenu', 'onload',
'onresize', 'onscroll', 'onunload', 'onclick',
'ondblclick', 'onmousedown', 'onmouseup', 'onmouseenter',
'onmouseleave', 'onmousemove', 'onmouseover',
'onmouseout', 'onchange', 'onreset', 'onselect',
'onsubmit', 'onkeydown', 'onkeyup', 'onkeypress',
'onabort', 'onerror']; // ondasher, onprancer, etc.

/**
 Fixes copy errors introduced by {@link element#cloneNode}, e.g. failure to copy classically-registered event handlers and the value property.

 @param {element} o The original DOM element
 @param {element} copy The result of o.cloneNode()
 @return {element} A modified copy with event handlers maintained
*/
function fix_dom_clone(o, copy) {
    if (!(dom_obj(o) && dom_obj(copy))) { return; }
    
    for (var i = 0;i < dom_events.length;i++) {
        var event = dom_events[i];
        if (event in o) { copy[event] = o[event]; }
    }
    if ('value' in o) { copy.value = o.value; }
    
    // recur
    var o_kids = o.childNodes;
    var c_kids = copy.childNodes;
    for (i = 0;i < o_kids.length;i++) {
        fix_dom_clone(o_kids[i], c_kids[i]);
    }
}

Oof. Unsurprisingly, there are a few efficiency issues.

My bug was weird and unexpected, and the W3C DOM level 2 spec doesn't allude to problems like this, but looking at a Mozilla bug report on the topic, it seems that the W3C DOM level 3 spec says that "[u]ser data associated to the imported node is not carried over". I guess if that's true for event handlers, it's also true for the value property. Oh well. I'd feel better about this irritating API "feature" if they said "associated with".