Composing Bidirectional Programs Monadically

Li-yao Xia; Dominic  Orchard; Meng Wang

doi:10.1007/978-3-030-17184-1_6

Composing Bidirectional Programs Monadically

Li-yao Xia, Dominic Orchard, Meng Wang

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

4 Citations (Scopus)

221 Downloads (Pure)

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.

Original language	English
Title of host publication	Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings
Subtitle of host publication	28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings
Editors	Luís Caires
Publisher	Springer, Cham
Pages	147-175
Number of pages	29
ISBN (Electronic)	9783030171841
ISBN (Print)	9783030171834
DOIs	https://doi.org/10.1007/978-3-030-17184-1_6
Publication status	Published - 6 Apr 2019

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	11423 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Research Groups and Themes

Programming Languages

Access to Document

10.1007/978-3-030-17184-1_6

Full-text PDF (final published version)
This is the final published version of the article (version of record). It first appeared online via Springer at https://link.springer.com/chapter/10.1007%2F978-3-030-17184-1_6 . Please refer to any applicable terms of use of the publisher.
Final published version, 1.16 MBLicence: CC BY

Handle.net

Persistent link

Embargoed Document

Full-text PDF (accepted author manuscript)
Accepted author manuscript, 448 KB

Dr Meng Wang
- meng.wangbristol.acuk
- School of Computer Science - Associate Professor of Programming Languages
Person: Academic

Cite this

Xia, L., Orchard, D., & Wang, M. (2019). Composing Bidirectional Programs Monadically. In L. Caires (Ed.), Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings: 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings (pp. 147-175). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11423 LNCS). Springer, Cham. https://doi.org/10.1007/978-3-030-17184-1_6

Xia, Li-yao ; Orchard, Dominic ; Wang, Meng. / Composing Bidirectional Programs Monadically. Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings: 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings. editor / Luís Caires. Springer, Cham, 2019. pp. 147-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{e65e4dc70b074363914f34e5a346dce2,

title = "Composing Bidirectional Programs Monadically",

abstract = "Software frequently converts data from one representation to another and vice versa. Na{\"i}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.",

author = "Li-yao Xia and Dominic Orchard and Meng Wang",

year = "2019",

month = apr,

day = "6",

doi = "10.1007/978-3-030-17184-1_6",

language = "English",

isbn = "9783030171834",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer, Cham",

pages = "147--175",

editor = "Lu{\'i}s Caires",

booktitle = "Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings",

address = "Switzerland",

}

Xia, L, Orchard, D & Wang, M 2019, Composing Bidirectional Programs Monadically. in L Caires (ed.), Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings: 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 11423 LNCS, Springer, Cham, pp. 147-175. https://doi.org/10.1007/978-3-030-17184-1_6

Composing Bidirectional Programs Monadically. / Xia, Li-yao; Orchard, Dominic ; Wang, Meng.
Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings: 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings. ed. / Luís Caires. Springer, Cham, 2019. p. 147-175 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 11423 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference Contribution (Conference Proceeding)

TY - GEN

T1 - Composing Bidirectional Programs Monadically

AU - Xia, Li-yao

AU - Orchard, Dominic

AU - Wang, Meng

PY - 2019/4/6

Y1 - 2019/4/6

N2 - 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.

AB - 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.

U2 - 10.1007/978-3-030-17184-1_6

DO - 10.1007/978-3-030-17184-1_6

M3 - Conference Contribution (Conference Proceeding)

SN - 9783030171834

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 147

EP - 175

BT - Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings

A2 - Caires, Luís

PB - Springer, Cham

ER -

Xia L, Orchard D, Wang M. Composing Bidirectional Programs Monadically. In Caires L, editor, Programming Languages and Systems - 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Proceedings: 28th European Symposium on Programming, ESOP 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6–11, 2019, Proceedings. Springer, Cham. 2019. p. 147-175. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-030-17184-1_6

Composing Bidirectional Programs Monadically

Abstract

Publication series

Research Groups and Themes

Access to Document

Handle.net

Embargoed Document

Fingerprint

Profiles

Dr Meng Wang

Cite this