Interactive Synthesis of Interactive Diagrams

EDDIE is an interactive tool for building interactive diagrams without writing code.

Diagrams are a powerful graphical method for communication, and interactive diagrams that respond to user-input are particularly powerful, in diverse domains ranging from business settings, website design, and technical communication.

In many of these domains, the author of the diagram generally does not have programming skills, but despite years of research into graphical editors and direct-manipulation environments, the vast majority of techniques for adding interactivity to a static diagram involve programming.

That is, the state of the art is to "go learn JavaScript/Flash/Mathematica".

We believe this is a fundamental problem to the adoption and usage of interactive diagrams and developed EDDIE to address this issue.

EDDIE is a runtime system for interactive diagrams, a direct-manipulation editor for building static diagrams, and a synthesis engine for automatically enriching static diagrams with end-user interactivity. Here's a very quick, 30s preview of our technique:

In EDDIE, the diagram author needs to only specify where the diagram should capture input -- EDDIE's synthesis engine then figures out how that input should affect the rest of the diagram and makes an educated guess as to the meaning of user-input.

If EDDIE guesses incorrectly, the author can change the meaning of user-input by choosing from a list of self-animating previews.

That's it! These two steps are all that's necessary to author an interactive diagram in EDDIE -- no programming, no arcane interaction models, just self-animating previews. We believe EDDIE enables non-programmers to directly author interactive diagrams that would otherwise be inaccessible and conducted a usability study with high-school teachers that supports our hypothesis.

For more details, including our implementation techniques and usability study methodology, please see our paper or ~3:00 minute video overview.


Interactive Parser Synthesis

Parsify is an interactive tool to bring parsing "to the masses". Parsing is a ubiquitious problem, but unfortunately, current techniques for specifying parsers do not present a sufficient layer of abstraction between specifications and algorithms. As a consequence, current techniques are inaccessible to people without formal knowledge in parsing theory (i.e., most programmers).

Our tool uses human recognition (e.g., "1+2" is-an Expr) to synthesize production rules for a GLL parser. We assume users desire parse trees (and not parse forests), and so we also synthesize filters for disambiguation of ambiguous parses.

For more information, read our paper or check out our website.


RTM Garbage Collection

Chihuahua is a novel algorithm for concurrent, incremental garbage collection. Automatic memory management (a.k.a. garbage collection) is a popular language feature. Common algorithms for garbage collection periodically stop application code (known as a pause), which is acceptable for some problems but disastrous for others (e.g., embedded systems, UIs, etc). For such systems, incremental garbage collection attempts to limit the maximum time within any one pause.

Chihuahua uses some nice properties (namely, strong atomicity) of Intel's Restricted Transactional Memory (RTM) as the core of a concurrent, incremental collection algorithm.

We have implemented an incomplete prototype of Chihuahua (that is also parallel) in JikesRVM. For more information, here's our report on some of our preliminary findings and our techniques.