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.