Automatic Refunctionalization to a Language with Copattern Matching: With Applications to the Expression Problem
by Tillmann Rendel, Julia Trieflinger, and Klaus Ostermann
In Proceedings of International Conference on Functional Programming, pages 269–279. ACM, 2015.
This publication is related to the Uroboro research project.
Abstract
Defunctionalization and refunctionalization establish a correspondence between first-class functions and pattern matching, but the correspondence is not symmetric: Not all uses of pattern matching can be automatically refunctionalized to uses of higher-order functions. To remedy this asymmetry, we generalize from first-class functions to arbitrary codata. This leads us to full defunctionalization and refunctionalization between a codata language based on copattern matching and a data language based on pattern matching.
We observe how programs can be written as matrices so that they are modularly extensible in one dimension but not the other. In this representation, defunctionalization and refunctionalization correspond to matrix transposition which effectively changes the dimension of extensibility a program supports. This suggests applications to the expression problem.
