Synthesizing quotient lenses

Solomon Maina, Anders Miltner, Kathleen Fisher, Benjamin C. Pierce, David Walker, Steve Zdancewic

Research output: Contribution to journalArticlepeer-review

11 Scopus citations

Abstract

Quotient lenses are bidirectional transformations whose correctness laws are loosenedž by specified equivalence relations, allowing inessential details in concrete data formats to be suppressed. For example, a programmer could use a quotient lens to define a transformation that ignores the order of fields in XML data, so that two XML files with the same fields but in different orders would be considered the same, allowing a single, simple program to handle them both. Building on a recently published algorithm for synthesizing plain bijective lenses from high-level specifications, we show how to synthesize bijective quotient lenses in three steps. First, we introduce quotient regular expressions (QREs), annotated regular expressions that conveniently mark inessential aspects of string data formats; each QRE specifies, simulteneously, a regular language and an equivalence relation on it. Second, we introduce QRE lenses, i.e., lenses mapping between QREs. Our key technical result is a proof that every QRE lens can be transformed into a functionally equivalent lens that canonizes source and target data just at the edgesž and that uses a bijective lens to map between the respective canonical elements; no internal canonization occurs in a lens in this normal form. Third, we leverage this normalization theorem to synthesize QRE lenses from a pair of QREs and example input-output pairs, reusing earlier work on synthesizing plain bijective lenses. We have implemented QREs and QRE lens synthesis as an extension to the bidirectional programming language Boomerang. We evaluate the effectiveness of our approach by synthesizing QRE lenses between various real-world data formats in the Optician benchmark suite.

Original languageEnglish (US)
Article number3236775
JournalProceedings of the ACM on Programming Languages
Volume2
Issue numberICFP
DOIs
StatePublished - Sep 2018

All Science Journal Classification (ASJC) codes

  • Software
  • Safety, Risk, Reliability and Quality

Keywords

  • Bidirectional Programming
  • Program Synthesis
  • Type Systems
  • Type-Directed Synthesis

Fingerprint

Dive into the research topics of 'Synthesizing quotient lenses'. Together they form a unique fingerprint.

Cite this