Eberhard Karls Universität Tübingen

Mathematisch-Naturwissenschaftliche FakultätProgramming Languages and Software Technology

Automatic Refunctionalization to a Language with Copattern Matching: With Applications to the Expression Problem

Publisher's version
10.1145/2784731.2784763
Author's version
rendel15automatic.pdf

by Tillmann Rendel, Julia Trieflinger, and Klaus Ostermann

In Proceedings of International Conference on Functional Programming, pages 269–279. ACM, 2015.

This publication is part of 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.