Higher-order matching for program transformation

We present a simple, practical algorithm for higher-order matching in the c ontext of automatic program transformation. Our algorithm finds more matche s than the standard second order matching algorithm of Huet and Lang, but i t has an equally simple specification, and it is better suited to the trans formation of programs in modern programming languages such as Haskell or ML . The algorithm has been implemented as part of the MAG system for transfor ming functional programs. (C) 2001 Elsevier Science B.V. All rights reserve d.