Composing Bidirectional Programs Monadically

Li-yao Xia, Dominic Orchard, Meng Wang

TL;DR

This paper introduces a novel framework for composing bidirectional programs (like parsers/printers or data transformations) using monads, a familiar concept in functional programming. This approach simplifies the development of bidirectional programs, making them more composable and easier to reason about, especially for complex data conversions.

What Problem Does This Paper Address?

Software often needs to convert data between different representations (e.g., from a string to a structured data format and back). Traditionally, this involves writing separate functions for each direction (parsing and printing), which is error-prone and leads to duplicated code. While "bidirectional programming" aims to solve this by defining both directions from a single specification, existing techniques often rely on specialized, less intuitive programming idioms. 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 defining bidirectional transformations as "monadic profunctors." A profunctor is a type constructor that is covariant in its second argument and contravariant in its first. By combining this with monads, the authors create a structure that allows for sequential composition of both forward and backward transformations using familiar monadic do-notation.

Key techniques include:

  • Monadic Profunctors: The paper defines and utilizes monadic profunctors as the unifying structure for bidirectional programs. This allows for a general approach that can be applied to various domains.
  • Fwd and Bwd Constructions: Two fundamental profunctor constructions, Fwd and Bwd, are introduced. Fwd discards the contravariant parameter (useful for forward-only operations like parsing), while Bwd maps from the contravariant parameter (useful for backward operations like printing).
  • Compositional Reasoning Framework: To address the challenge of verifying bidirectional properties, the paper proposes a framework based on "compositional" and "quasicompositional" properties. This allows proving properties for complex programs by composing proofs of their simpler components, rather than proving properties for the entire program at once.
  • Purification: A "purification" operation is introduced to recover the original backward round-tripping property from a weaker, compositional version.

The paper demonstrates the generality of this approach by applying it to:

  • Parsers/Printers: Defining bidirectional parsers (biparsers) that can parse strings into ASTs and print ASTs back into strings.
  • Lenses: Characterizing lenses, which provide access and update capabilities for structured data, within the monadic profunctor framework.
  • Generators/Predicates: Extending random generators (used in property-based testing) to bidirectional generators (bigenerators) that can both generate values and check if values satisfy a predicate.

Datasets

Not discussed in the paper. The paper focuses on a theoretical framework and its application to abstract data types and programming constructs, rather than empirical evaluation on specific datasets.

Key Insights and Ideas

  • Monads as a Unifying Abstraction: The paper shows that monads, a fundamental concept in functional programming, can be effectively used to structure and compose bidirectional transformations, making them more accessible and familiar to programmers.
  • Monadic Profunctors for Bidirectionality: By framing bidirectional programs as monadic profunctors, the authors provide a powerful and general abstraction that unifies different bidirectional programming patterns.
  • Compositionality for Reasoning: The key insight for reasoning about bidirectional programs is the shift from proving properties for entire programs to proving compositional properties for their atomic components. This significantly simplifies the verification process.
  • Weakening Properties for Compositionality: The paper demonstrates that stronger bidirectional properties (like strict round-tripping) are often not compositional. By weakening these properties (e.g., to "weak backward round tripping"), they become compositional, allowing for scalable reasoning. The original properties can then be recovered through additional, non-compositional steps like purification.
  • Bridging the Gap: The approach bridges the gap between specialized bidirectional programming languages and mainstream functional programming, allowing developers to leverage familiar tools and abstractions.

Key Results

  • A general framework for composing bidirectional programs monadically using monadic profunctors.
  • Demonstration of the framework's applicability to parsers/printers, lenses, and generators/predicates.
  • A compositional reasoning framework for verifying round-tripping properties of bidirectional programs.
  • The development of weakened, compositional versions of round-tripping properties and a method to recover the stronger properties.
  • The paper includes proofs and examples, with machine-checked Coq proofs available in supplementary material, demonstrating the correctness of the approach.

Limitations and Future Work

  • Partiality: The paper acknowledges that bidirectional transformations often involve partial functions (e.g., a parser might fail on invalid input). The framework handles this using Maybe and MonadPartial instances, but the implications of partiality for compositionality are an ongoing area of research.
  • Forward Round Tripping: While backward round tripping can be made compositional, forward round tripping is more challenging. The paper introduces "quasicompositionality" and relies on injectivity-like restrictions to handle this, but it's noted as a more complex area.
  • Domain-Specific Effects: The paper mentions that the monadic approach allows for more expressive bidirectional programs that can handle domain-specific effects (e.g., a "put" operation requiring additional input). However, fully exploring and reasoning about these effects remains an open challenge.
  • Lookahead in Parsers: The paper notes that while lookahead in parsers can be expressed, its interaction with compositional round-tripping properties requires further investigation.
  • General Adjunction Model: The authors suggest that an underlying structure based on an adjunction model might capture bidirectionality even more concretely than monadic profunctors, pointing to a potential avenue for future research.

Summary updated

Abstract

Software frequently converts data from one representation to another and vice versa. Naïvely 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}},
  booktitle = {ESOP},
  year = {2019},
  url = {https://openreview.net/forum?id=CjYMwLbVy8},
}
Figure