Variational Data Structures

Variability is ubiquitous in software, whether or not programmers realize it. Probably the most widely-known form is in C preprocessor macros for conditional compilation, i.e., #ifdef and friends. But it also occurs regularly in data and data structures, yet a lack of support in languages forces programmers to take ad hoc approaches.

Consider implementing a map tool to compute driving directions. One potential data structures for this task is a graph where the edges and paths correspond to roads and routes. Users might want to avoid toll roads, or make use of public transporation, which involves subtly different sets of edges. However, it would be enormously wasteful to generate a separate graph for each possible configuration of options. This calls for a structure that represents arbitrarily many similar graphs at once, which we call a variational graph.

Designing variational data structures turns out to be challenging project with lots of performance pitfalls and subtle, interwoven design considerations.

See our FOSD paper on variational linked lists.

Variational List

Variational Pictures

Variational Pictures

Variational pictures are structures that model many related pictures at the same time. This turns out to have many applications, such as for exploratory illustration and graphic design and even a kind of picture version control.

We are working to design a formal model for variational pictures that can serve as a basis for the design of picture editor tooling that helps avoid issues such as update anomalies.

Haskell DSL for Information Visualization

Visualization DSL

We designed a Haskell-embedded DSL for the creation and transformation of data visualizations. By building up abstractions and combinators, programmers can construct simple charts with a single function call or dig into the details of composing primitive shapes.

The visualization functor instance provides powerful conditional formatting techniques and a visualization monad instance supports the creation of custom drill-down and roll-up operations.

See our GPCE paper on this language.

Bars!