Lambda the Ultimate

This post is triggered by Jules asking, essentially, how could FRP support imperative structures? Part of the answer is about interface -- a command becomes an input stream of commands, which is a common pattern in systems like Max/MSP, and most FRP systems also provide mutable reactive cells (... a worthwhile topic for another day). More interesting is when we want a particular imperative implementation that the automatic incrementalizer wouldn't have picked, such as a hand-tuned one in a lower-level language. Sometimes, a reactive language supports interfacing with alternative implementations in other languages automatically, as in Crossing State Lines: Adopting OO Frameworks to Functional Reactive Languages, but, as long as the incrementalization algorithm supports foreign computations, even language users can do it (e.g., Flapjax supports manual lifting of the DOM, I also did arrays, etc.).

The following recent paper, Traceable Data Types for Self-Adjusting Computation, can be interpreted as an explanation of why it has been sensible performance-wise for an FRP system like Flapjax to lift a library like the DOM: in a typed setting, the library is an ADT that has been tuned to take care of its own incrementalization and thus we just need a bit of glue to lift it:

In this paper, we extend dependence-tracing to work at the granularity of the query and update operations of arbitrary (abstract) data types, instead of just reads and writes on memory cells. This can significantly reduce the number of dependencies that need to be kept in the trace and followed during an update. We define an interface for supporting a traceable version of a data type, which reports the earliest query that depends on (is changed by) revising operations back in time, and implement several such structures, including priority queues, queues, dictionaries, and counters. We develop a semantics for tracing, extend an existing self-adjusting language, ∆ML, and its implementation to support traceable data types, and present an experimental evaluation by considering a number of benchmarks. Our experiments show dramatic improvements on space and time, sometimes by as much as two orders of magnitude.

A little more out there, and why I liked this paper, is its typed phrasing allows you to reduce the typical lifting+FFI approach for automatic incrementalization of general programs to being an instance of the the expression problem.