Copenhagen Programming Language Seminar


Deterministic Higher-order Matching for Program Transformation

Tetsuo Yokoyama,
University of Tokyo and DIKU

Thursday, May 18th, 15:15-16:00
DIKU, Universitetsparken 1, room N018


Higher-order patterns are important for describing concise calculation rules. They are capable of checking and binding subtrees far from the root, which is useful for program manipulation. To obtain the bindings of higher-order variables, higher-order matching is used. There are three major problems from the practical viewpoint, though. First, it is difficult to explain why a particular desired matching result cannot be obtained because of the complicated higher-order matching algorithm. Second, the general higher-order matching algorithm is of high cost, which may be exponential time at worst. Third, the (possibly infinite) nondeterministic solutions of higher-order matching prevent its use in a functional setting.

To resolve these problems, we take two approaches. First, we impose reasonable restrictions on the form of higher-order patterns to gain predictability, efficiency, and determinism. Our deterministic patterns induce the linear time algorithm. Second, for nondeterministic patterns, we impose restrictions on the algorithm. We define reasonable orders on solutions and only return the largest solution. As a result, the algorithm becomes linear time.

We show that our deterministic higher-order patterns and deterministic higher-order matching are powerful tools to support concise specification and efficient implementation of various kinds of program transformation for optimizations.

Scientific host: Robert Glück, Administrative host: Camilla Jensen. All are welcome.
The Copenhagen Programming Language Seminar (COPLAS) is a collaboration between DIKU, ITU and KVL.
COPLAS is sponsored by FIRST Graduate School.
To receive information about COPLAS talks by email, send a message to prog-lang-request@mail.it-c.dk with the word 'subscribe' as subject or in the body.

For more information about COPLAS, see http://www.coplas.org