Synthesizing functional reactive programs

Bernd Finkbeiner, Felix Klein, Ruzica Piskac, Mark Santolucito

TL;DR

This paper introduces a method to automatically generate Functional Reactive Programming (FRP) code from high-level specifications written in Temporal Stream Logic (TSL). By bridging the gap between formal synthesis and practical software engineering, the authors allow developers to specify what a reactive system should do (e.g., "increment the counter when the button is clicked") while automatically generating the complex, error-prone control logic required to implement it across various platforms like web, desktop, and hardware.

What Problem Does This Paper Address?

Functional Reactive Programming (FRP) is a powerful paradigm for building systems that react to continuous streams of input (like user clicks or sensor data). However, as these programs grow, managing state transitions and "control flow"—deciding exactly when to switch behaviors—becomes incredibly difficult and bug-prone.

While a logic called Temporal Stream Logic (TSL) was recently developed to synthesize "Control Flow Models" (CFMs) from abstract requirements, there was no clear way to turn these theoretical models into actual, executable code that works with popular FRP libraries. This paper solves the "last mile" problem: taking a synthesized model and translating it into real-world code for different FRP flavors (Arrowized, Monadic, and Applicative).

Methods

The authors propose a multi-stage synthesis pipeline:

  1. Specification: The user writes the system's behavior in TSL. This logic separates "control" (the logic of when things happen) from "data" (the pure functions that transform values).
  2. Synthesis: A reactive synthesis engine (specifically strix) processes the TSL to create a Control Flow Model (CFM). This is an abstract graph of how the system should behave over time.
  3. Translation to CCA: The core technical contribution is mapping this CFM to Causal Commutative Arrows (CCA). CCA is a restricted version of FRP that is powerful enough to represent the synthesized logic but simple enough to be statically analyzed and optimized.
  4. Code Generation: The authors provide a modular template that specializes the CCA model into specific Haskell-based FRP libraries. This allows the same high-level specification to generate code for:
  5. Yampa (Arrowized FRP for desktop apps).
  6. threepenny-gui (Monadic FRP for web apps).
  7. ClaSH (Applicative FRP for hardware/FPGAs).

Datasets

As a programming languages and formal methods paper, it does not use traditional "big data" training sets. Instead, it evaluates its approach using a real-world kitchen timer application as a benchmark. The requirements for this timer (handling resets, minute/second increments, and counting down) were used to test the limits of the synthesis engine and the correctness of the generated code across three different execution environments.

Key Insights and Ideas

  • Separation of Concerns: The biggest "aha moment" is that developers shouldn't have to write the "glue" code for reactive state. By using TSL, the developer only provides the pure data functions (like increment or render) and the temporal logic; the computer handles the messy state management.
  • CCA as the "Universal Language": The authors identified that Causal Commutative Arrows (CCA) serve as a perfect intermediate representation. Because CCA avoids higher-order features like dynamic "switching" (which are hard to synthesize), it ensures the generated code is efficient and predictable enough for hardware (FPGAs).
  • Real-world Realizability: The paper proves that a single formal specification can be "compiled" into vastly different domains—from a JavaScript-heavy web page to a physical hardware circuit—without changing the underlying logic.

Key Results

  • Efficiency: The synthesis of the kitchen timer (a model with 1,188 vertices) took only 4.965 seconds.
  • Portability: The authors successfully deployed the same synthesized logic to a desktop app (Yampa), a web app (threepenny-gui), and an iCE40HX1K FPGA board (via ClaSH).
  • Bug Discovery: During their evaluation, they attempted to synthesize a specification from a popular FRP study (FRPZoo) and discovered the original English specification was actually unrealizable (it contained a logical conflict when two buttons were pressed at once). This highlights the power of formal synthesis in catching design flaws early.

Limitations and Future Work

  • Undecidability: The authors acknowledge that TSL synthesis is "undecidable" in the general case, meaning there's no guarantee the tool will always find a solution for every possible specification.
  • Static Networks only: The current approach targets "static" FRP networks. It does not yet support "dynamic" networks where the structure of the program changes at runtime (e.g., adding or removing UI elements on the fly).
  • Discrete vs. Continuous Time: While the kitchen timer works in continuous time, the formal model currently uses a discrete time step. The authors suggest that exploring the relationship between TSL and continuous-time FRP is a promising next step.

Summary updated

Abstract

Functional Reactive Programming (FRP) is a paradigm that has simplified the construction of reactive programs. There are many libraries that implement incarnations of FRP, using abstractions such as Applicative, Monads, and Arrows. However, finding a good control flow, that correctly manages state and switches behaviors at the right times, still poses a major challenge to developers. An attractive alternative is specifying the behavior instead of programming it, as made possible by the recently developed logic: Temporal Stream Logic (TSL). However, it has not been explored so far how Control Flow Models (CFMs), as synthesized from TSL specifications, can be turned into executable code that is compatible with libraries building on FRP. We bridge this gap, by showing that CFMs are indeed a suitable formalism to be turned into Applicative, Monadic, and Arrowized FRP. We demonstrate the effectiveness of our translations on a real-world kitchen timer application, which we translate to a desktop application using the Arrowized FRP library Yampa, a web application using the Monadic threepenny-gui library, and to hardware using the Applicative hardware description language ClaSH.
BibTeX
@inproceedings{finkbeiner2019synthesizing,
  author = {Bernd Finkbeiner and Felix Klein and Ruzica Piskac and Mark Santolucito},
  title = {{Synthesizing functional reactive programs}},
  booktitle = {Haskell@ICFP},
  year = {2019},
  doi = {10.1145/3331545.3342601},
}

Loading related content...

Figure