Composing bidirectional programs monadically (with appendices)

Li-yao Xia, Dominic Orchard, Meng Wang

TL;DR

This paper introduces a novel framework for composing bidirectional programs (like parsers/printers, lenses, and generators) using monads, a familiar concept in functional programming. This approach simplifies the development of bidirectional transformations, making them more composable and easier to reason about, particularly for round-tripping properties.

What Problem Does This Paper Address?

Software often involves converting data between different representations (e.g., parsing text into a structured format, or updating a view in a database). Traditionally, this requires writing separate functions for each direction (e.g., a parser and a printer). This is error-prone and leads to duplicated effort. Bidirectional programming aims to solve this by defining a single program that can operate in both directions. However, existing bidirectional programming techniques often rely on specialized, less familiar programming idioms and combinator libraries, hindering their adoption. This paper addresses the challenge of making bidirectional programming more accessible and composable by leveraging the power of monads, a well-established abstraction in functional programming.

Methods

The core contribution is a framework for composing bidirectional programs monadically. This is achieved by:

  • Monadic Profunctors: The paper defines a unifying structure called a "monadic profunctor." This structure combines the properties of profunctors (which handle bidirectional transformations) with monads (which provide sequential composition).
  • Fwd and Bwd Constructions: Two fundamental building blocks, Fwd and Bwd, are introduced. Fwd captures the forward direction (e.g., parsing) as a covariant functor, while Bwd captures the backward direction (e.g., printing) as a contravariant functor. These are then combined to form monadic profunctors.
  • Compositionality and Reasoning: The paper develops a compositional reasoning framework for verifying round-tripping properties. Instead of proving properties for entire complex programs, it focuses on proving them for atomic components, which are then guaranteed to hold for the composed program. This is achieved through concepts like "weak backward round tripping" and "weak forward round tripping," which are compositional, and "purification" to recover stronger properties.
  • Applications: The framework is demonstrated on three key domains: parsers/printers, lenses, and generators/predicates.

Datasets

Not discussed in the paper. The paper focuses on theoretical framework development and code examples rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Monads as a Unifying Abstraction: The paper shows that monads, a familiar tool in functional programming, can be effectively used to structure and compose bidirectional programs, making them more accessible.
  • Compositionality for Reasoning: The key insight is that while strong round-tripping properties might not be compositional, weaker versions are. By focusing on these compositional properties and using a "purification" step, one can still reason about the overall bidirectional program effectively.
  • Bridging the Gap: The approach bridges the gap between specialized bidirectional programming languages and mainstream functional programming, allowing developers to use familiar abstractions like monads.
  • Generators as Bidirectional Programs: The paper extends bidirectional programming to generators, framing them as programs that can both generate values and check predicates, offering a novel perspective on property-based testing.

Key Results

  • Framework for Monadic Bidirectional Programming: The paper presents a general framework for composing bidirectional programs using monadic profunctors.
  • Applications to Parsers, Lenses, and Generators: The framework is successfully applied to parsers/printers, lenses, and generators/predicates, demonstrating its generality.
  • Compositional Reasoning Framework: A scalable reasoning framework is developed, enabling compositional verification of round-tripping properties.
  • Haskell Libraries: The authors have implemented these ideas as Haskell libraries, showcasing the practical viability of their approach.

Limitations and Future Work

  • Partiality: The paper acknowledges that bidirectional transformations often involve partiality (e.g., a view might not exist for a given source). While the framework handles this using Maybe, it notes that enforcing domain restrictions is crucial.
  • Forward Round Tripping: The paper highlights that forward round tripping is generally not compositional, even in a weakened form. While quasicompositionality is introduced as a partial solution, it requires injectivity-like restrictions.
  • Expressivity vs. Correctness Trade-off: The monadic approach offers greater expressivity but sacrifices some of the compile-time correctness guarantees found in specialized lens languages.
  • Future Work: The authors suggest exploring biparsers with lookahead, adapting monadic lens laws, and formalizing an adjunction model for bidirectionality. They also mention the possibility of adapting the framework to applicative programming.

Summary updated

Abstract

Software frequently converts data from one representation to another and vice versa. Naively specifying both conversion directions separately is error prone and introduces conceptual duplication. Instead, bidirectional programming techniques allow programs to be written which can be interpreted in both directions. However, these techniques often employ unfamiliar programming idioms via restricted, specialised combinator libraries. Instead, we introduce a framework for composing bidirectional programs monadically, enabling bidirectional programming with familiar abstractions in functional languages such as Haskell. We demonstrate the generality of our approach applied to parsers/printers, lenses, and generators/predicates. We show how to leverage compositionality and equational reasoning for the verification of round-tripping properties for such monadic bidirectional programs.
BibTeX
@inproceedings{xia2019composing,
  author = {Li-yao Xia and Dominic Orchard and Meng Wang},
  title = {{Composing bidirectional programs monadically (with appendices)}},
  booktitle = {ESOP},
  year = {2019},
  url = {https://openreview.net/forum?id=CjYMwLbVy8},
}

Loading related content...

Figure