Programming the Internet: Reactive Systems, Events, and KRL


Billard balls

Imagine walking into Borders and having your smartphone alert you to the fact that the book you put on your Amazon wish list this morning is available right now and on sale. As another example, think about an application that gathers relevant articles from your RSS and Twitter feeds based on searches you've performed or that are related to an email your received from a friend today. These examples show the power that can be achieved when we start programming the Internet and not just the Web. There's no reason that clients in different domains (like your smartphone and Web browser) shouldn't be cooperating under your guidance to help you get things done. But to make that happen, we need new architectures and programming paradigms.

One way of viewing the Internet is a big reactive system. When you browse, tweet, email, and so on the Internet reacts to what you're doing, or so it seems. Programming on the 'Net requires reacting to user activities. Web programs do this in a fairly ad hoc manner because most Web frameworks provide little support for managing program data and control flow across individual user interactions.

When we invented KRL, the Kynetx Rule Language, our goal was to build notational support for the hard things that Web programmers face everyday--especially on the client-side. The goal is let the machine take care of the details. Linguistic expression and abstraction give programmers the tools to do amazing things without making heroic efforts. One example of this principle at work is the integration of the Twitter API and OAuth into KRL so that developers don't have to manage the OAuth protocol dance by themselves. But there are bigger fish to fry than OAuth.

Thus far, most KRL apps have been fairly simple reactive systems because the responsibility for responding to more complicated scenarios rested firmly on the programmer's shoulders. For example, if you wanted to respond to a user visiting page A only after they've visited page B in KRL, you had to use persistent variables to store the page A visit and then check in the rule responding to the page B visit if that variable had been set. More complicated scenarios required that the developer design and then manually construct whatever state machine was appropriate to keep track of the user's current spot in the scenario.

One of our short term goals in KRL is to support what we call "dialoguing"--essentially KRL apps that react to user's actions in ways that any normal Web application would. Dialoguing will support the ability to create and respond to forms within KRL and interact with users in much more sophisticated ways. Building your own ad hoc response state machine--as defined above--wasn't acceptable (even though this is essentially what all other Web frameworks require).

If we were to classify KRL, it would be called an "event-condition-action" (or ECA) rule language. The basic pattern is

when Event
if   Condition
then Action

So, I call KRL an ECAE language with the last 'E' standing for 'effect.' The ECA pattern is typical of most business rule systems and is a great way to write reactive systems.

A while back I ran across a bunch of research done on active databases in the 90's and realized that the ideas developed for specifying and implementing complex event expressions in databases would serve nicely for the kinds of things we want to do in KRL. (If you're interested in such things, I've made my bibtex file on rule languages available.) A good event language adds considerable power to rules. By incorporating events more fully into KRL, we can allow developers to create much more complicated rules without requiring that they manage the scenarios themselves.

The key to understanding these ideas is to realize that how KRL has traditionally used events and how this can be expanded into a more full-featured and complete event system. Here's the high-level diagram:

Endpoints and KNS

The three components in this diagram are the user client (traditionally a browser), the endpoint (traditionally a browser extension), and the Kynetx Network Service (KNS). Before today KRL had just one primitive event: pageview. When you write a select statement in a rule, you're specifying the event on which to select the rule. For example, consider the following select statment:

select using "/archive/\\d+/" 

This select statement says when the user visits a page matching the regular expression "/archive/\\d+/" select the rule. When the browser extension, acting as the endpoint, raises a "pageview" event with KNS, KNS selects rules that match that event. Of course, if nothing matches then nothing is selected.

In addition to the single "pageview" event supported by the select statement, KRL also supported two other event types, but only as second-class citizens in the callback postlude: click and change.

Today we're announcing a more generalized event expression language for KRL. Event expressions come in two forms:

  • primitive events - these specify the primitive event in a given domain.
  • complex events - these combine primitive events using event constructurs such as then or between

Primitive events will depend on the domain. For now, we have pageview with more coming. Complex event expression allow us to combine primitive events to form event scenarios. The following event operators are available now:

  • A before B - event A occured before event B:
  • select 
      when   pageview "bar.html" 
      before pageview "/archives/(\\d+)/x.html" setting (year)
    
  • A then B - event A occured then event B occured with no intervening (salient) events
  • select 
      when pageview "bar.html" 
      then pageview "/archives/(\\d+)/foo.html" setting (year)
    
  • A and B - event A occured and event B occured in any order.
  • select 
      when pageview "bar.html" 
      and  pageview "/archives/(\\d+)/foo.html" setting (year)
    
  • A or B - event A occured or event B occured.
  • select 
      when pageview "bar.html" 
      or   pageview "/archives/(\\d+)/foo.html" setting (year)
    
  • A between(B, C) - event A occured between event B and event C
  • select 
      when pageview "mid.html" 
         between(pageview "firs(.).html" setting(b),
                 pageview "las(.).html" setting(c))
    
  • A not between(B, C) - event A did not occured between event B and event C
  • select 
      when pageview "mid.html" 
        not between(pageview "firs(.).html" setting(b),
                    pageview "las(.).html" setting(c))
    

Of course, these can be nested as well. Parentheses specify execution order where precedent is not apparent.

select 
  when (pageview "mid.html" 
    between(pageview "firs(.).html" setting(b),
            pageview "las(.).html" setting(c)))
  before pageview "/archives/(\\d+)/foo.html" setting (year)

I anticipate that we'll add other event expressions operators as we get more experience with them. Also while the only primitive event shown in the previous examples is pageview, other primitive events will soon be available. There's no restriction that requires all of the primitive events in a particular scenario coming from a single domain.

This new event expression language gives us a great platform for growing the expressive power of KRL in the the coming months. In increasing the expressiveness of KRL for events, we can move along three dimensions:

  1. Adding event expressions with composition operators that allow the expression of complex event scenarios through the combination of multiple primitive events.
  2. Adding new primitive events to the Web domain by making click and change first-class events in the language and adding any other relevant events that a browser extension might raise. Note that these need not be limited to the events available in Javascript, although those are all good candidates, but also browser events like "bookmark added" and so on.
  3. Adding new event domains so that endpoints for mail clients, RSS handlers, queue services, telephony engines, and so on can raise events with KNS. In addition to endpoint events, we anticipate adding temporal events to event expressions.

Item (1) is done and incorporated in KRL now--more on that in a minute. We're working on (2) and expect to have additional primitive events in the Web domain in the next few weeks. We also have an active project to develop an endpoint--and corresponding event primitives--in an IMAP client that hope will start to address (3) in the next several months.

You might be wondering how we can add complex event scenario evaluation to KRL efficiently. The key is that event expressions are actually no more powerful than regular expressions over the alphabet of primitive events. We compile each event expression into a corresponding state machine as part of the ruleset optimization process. Then we simply keep a state marker for each rule in each ruleset that each user has installed. The storage requirements aren't that great and reacting to an event only requires looking at the user's current state for a rule and calculating the next state. If the state machine is in a final state the rule is selected and the state machine reset. The exact details of how event expressions compile to state machines is left as an exercise for the reader based on the bibliography given above and basic computational theory.

I'm very excited about this release; I've been working on it for 3 months. Support for complex events are the most fundamental shift in the core KRL execution engine in the 2.5 years we've been working on it. These changes significantly increase the expressive power of KRL now and lay the foundation for furture improvements. More importantly, a robust event expression language will make it easier for developers to create applications that work across multiple domains, helping users achieve their purpose and get things done.