TY - GEN
T1 - Matching lenses
T2 - 15th ACM SIGPLAN International Conference on Functional Programming, ICFP'10
AU - Barbosa, Davi M.J.
AU - Cretin, Julien
AU - Foster, Nate
AU - Greenberg, Michael
AU - Pierce, Benjamin C.
PY - 2010
Y1 - 2010
N2 - Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well as one mapping updated views back to updated sources. One thorny issue that has not received sufficient attention in the design of bidirectional languages is alignment. In general, to correctly propagate an update to a view, a lens needs to match up the pieces of the view with the corresponding pieces of the underlying source, even after data has been inserted, deleted, or reordered. However, existing bidirectional languages either support only simple strategies that fail on many examples of practical interest, or else propose specific strategies that are baked deeply into the underlying theory. We propose a general framework of matching lenses that parameterizes lenses over arbitrary heuristics for calculating alignments. We enrich the types of lenses with "chunks" identifying reorderable pieces of the source and view that should be re-aligned after an update, and we formulate behavioral laws that capture essential constraints on the handling of chunks. We develop a core language of matching lenses for strings, together with a set of "alignment combinators" that implement a variety of alignment strategies.
AB - Bidirectional programming languages are a practical approach to the view update problem. Programs in these languages, called lenses, define both a view and an update policy - i.e., every program can be read as a function mapping sources to views as well as one mapping updated views back to updated sources. One thorny issue that has not received sufficient attention in the design of bidirectional languages is alignment. In general, to correctly propagate an update to a view, a lens needs to match up the pieces of the view with the corresponding pieces of the underlying source, even after data has been inserted, deleted, or reordered. However, existing bidirectional languages either support only simple strategies that fail on many examples of practical interest, or else propose specific strategies that are baked deeply into the underlying theory. We propose a general framework of matching lenses that parameterizes lenses over arbitrary heuristics for calculating alignments. We enrich the types of lenses with "chunks" identifying reorderable pieces of the source and view that should be re-aligned after an update, and we formulate behavioral laws that capture essential constraints on the handling of chunks. We develop a core language of matching lenses for strings, together with a set of "alignment combinators" that implement a variety of alignment strategies.
KW - alignment
KW - bidirectional languages
KW - boomerang
KW - lenses
KW - view update problem
UR - http://www.scopus.com/inward/record.url?scp=78249271060&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=78249271060&partnerID=8YFLogxK
U2 - 10.1145/1863543.1863572
DO - 10.1145/1863543.1863572
M3 - Conference contribution
AN - SCOPUS:78249271060
SN - 9781605587943
T3 - Proceedings of the ACM SIGPLAN International Conference on Functional Programming, ICFP
SP - 193
EP - 204
BT - ICFP'10 - Proceedings of the 2010 ACM SIGPLAN International Conference on Functional Programming
Y2 - 27 September 2010 through 29 September 2010
ER -