Bidirectionalization for Free! (Pearl) Export

@inproceedings{Voi09a, abstract = {A bidirectional transformation consists of a function get that takes a source (document or value) to a view and a function put that takes an updated view and the original source back to an updated source, governed by certain consistency conditions relating the two functions. Both the database and programming language communities have studied techniques that essentially allow a user to specify only one of get and put and have the other inferred automatically. All approaches so far to this bidirectionalization task have been syntactic in nature, either proposing a domain-specific language with limited expressiveness but built-in (and composable) backward components, or restricting get to a simple syntactic form from which some algorithm can synthesize an appropriate definition for put. Here we present a semantic approach instead. The idea is to take a general-purpose language, Haskell, and write a higher-order function that takes (polymorphic) get-functions as arguments and returns appropriate put-functions. All this on the level of semantic values, without being willing, or even able, to inspect the definition of get, and thus liberated from syntactic restraints. Our solution is inspired by relational parametricity and uses free theorems for proving the consistency conditions. It works beautifully.}, address = {New York, NY, USA}, author = {Voigtl\"{a}nder, Janis}, booktitle = {POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages}, citeulike-article-id = {5202164}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=1480881.1480904}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/1480881.1480904}, citeulike-linkout-2 = {http://wwwtcs.inf.tu-dresden.de/~voigt/popl09-2.pdf}, doi = {10.1145/1480881.1480904}, editor = {Pierce, Benjamin C.}, isbn = {978-1-60558-379-2}, keywords = {applications, bidirectionality, databases, free-theorems, functional-programming, generic-programming, haskell, parametricity, polymorphism, program-transformation, type-classes, view-update}, location = {Savannah, GA, USA}, month = {January}, pages = {165--176}, posted-at = {2009-07-19 07:07:52}, priority = {0}, publisher = {ACM Press}, title = {Bidirectionalization for Free! (Pearl)}, url = {http://dx.doi.org/10.1145/1480881.1480904}, year = {2009} }

TY - CONF ID - Voi09a L3 - citeulike-article-id:5202164 N2 - A bidirectional transformation consists of a function get that takes a source (document or value) to a view and a function put that takes an updated view and the original source back to an updated source, governed by certain consistency conditions relating the two functions. Both the database and programming language communities have studied techniques that essentially allow a user to specify only one of get and put and have the other inferred automatically. All approaches so far to this bidirectionalization task have been syntactic in nature, either proposing a domain-specific language with limited expressiveness but built-in (and composable) backward components, or restricting get to a simple syntactic form from which some algorithm can synthesize an appropriate definition for put. Here we present a semantic approach instead. The idea is to take a general-purpose language, Haskell, and write a higher-order function that takes (polymorphic) get-functions as arguments and returns appropriate put-functions. All this on the level of semantic values, without being willing, or even able, to inspect the definition of get, and thus liberated from syntactic restraints. Our solution is inspired by relational parametricity and uses free theorems for proving the consistency conditions. It works beautifully. CY - Savannah, GA, USA SN - 978-1-60558-379-2 AD - New York, NY, USA EP - 176 TI - Bidirectionalization for Free! (Pearl) PB - ACM Press T2 - POPL '09: Proceedings of the 36th annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages SP - 165 KW - applications KW - bidirectionality KW - databases KW - free-theorems KW - functional-programming KW - generic-programming KW - haskell KW - parametricity KW - polymorphism KW - program-transformation KW - type-classes KW - view-update AU - Voigtländer, Janis A2 - Pierce, Benjamin PY - 2009/01// UR - http://dx.doi.org/10.1145/1480881.1480904 ER -