Synthesizing Functional Reactive Programs

Bernd Finkbeiner, Felix Klein, Ruzica Piskac, Mark Santolucito

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.

Introduction

Functional Reactive Programming (FRP) is a powerful paradigm for building systems that react to continuous streams of input, such as user interactions or sensor data. By treating inputs as time-varying values, FRP allows for more declarative code. However, as reactive programs scale, managing state transitions and "control flow"—the logic governing when to switch between different behaviors—becomes increasingly complex and error-prone.

While Temporal Stream Logic (TSL) was recently developed to synthesize abstract Control Flow Models (CFMs) from high-level requirements, a significant gap remained: there was no established method to transform these theoretical models into executable code compatible with existing FRP libraries. This research bridges that gap, providing a "last mile" solution for translating synthesized models into real-world code for various FRP flavors, including Arrowized, Monadic, and Applicative implementations.

The Synthesis Pipeline

The authors propose a multi-stage synthesis pipeline designed to move from abstract specification to concrete implementation:

  1. Specification: The developer defines the system's behavior in TSL. This logic effectively separates "control" (the timing and conditions of events) from "data" (the pure functions that transform values).
  2. Synthesis: A reactive synthesis engine (specifically strix) processes the TSL specification to generate a Control Flow Model (CFM), which acts as an abstract graph of the system's temporal behavior.
  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 expressive enough to represent synthesized logic while remaining simple enough for static analysis and hardware optimization.
Fundamental Arrow combinators: (a) lifting functions, (b) composition, (c) processing the first component of a pair, and (d) feedback loops.

As illustrated in the figure above, the translation utilizes standard Arrow combinators to structure the reactive logic. By using these primitives, the authors create a modular template that specializes the CCA model into specific Haskell-based FRP libraries. This allows a single high-level specification to generate code for diverse targets:

  • Yampa: Arrowized FRP for desktop applications.
  • threepenny-gui: Monadic FRP for web applications.
  • ClaSH: Applicative FRP for hardware description (FPGAs).

Evaluation: The Kitchen Timer Benchmark

The approach was evaluated using a real-world kitchen timer application. The requirements—handling resets, minute/second increments, and countdown logic—served as a benchmark to test the synthesis engine's limits and the correctness of the generated code across three distinct environments.

Key Results

  • Efficiency: Synthesizing the kitchen timer model (comprising 1,188 vertices) took only 4.965 seconds, demonstrating the feasibility of the approach for practical applications.
  • Portability: The authors successfully deployed the same synthesized logic to a desktop app, a web app, and an iCE40HX1K FPGA board without altering the underlying logic.
  • Bug Discovery: During evaluation, the authors 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 simultaneously, highlighting how formal synthesis can catch design flaws that manual programming might miss.

Insights and Future Work

A primary insight of this work is the effective separation of concerns. By using TSL, developers are relieved of writing the "glue" code for reactive state; they provide only the pure data functions and temporal logic, while the synthesis engine handles state management. Furthermore, identifying CCA as a "universal language" for synthesis ensures that the generated code is efficient enough for hardware deployment.

Despite these successes, some limitations remain. TSL synthesis is undecidable in the general case, meaning a solution is not guaranteed for every possible specification. Additionally, the current approach targets "static" FRP networks and does not yet support dynamic structures where the program graph changes at runtime. Future work will explore the relationship between TSL and continuous-time FRP to further expand the reach of synthesized reactive programs.

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},
}
Figure