  Pattern matching is an important feature of programming languages for data
abstraction. Many pattern-matching extensions have been proposed and
implemented for extending the range of data types to which pattern matching is
applicable. Among them, the pattern-matching system proposed by Egi and
Nishiwaki features practical pattern matching for non-free data types by
providing an extensible non-linear pattern-matching facility with backtracking.
However, they implemented their proposal only in an interpreter of the Egison
programming language, and a method for compiling pattern-matching expressions
of Egison was not discussed. This paper proposes a method for translating a
program that contains pattern-matching expressions of Egison to a program that
contains only the existing syntax constructs of functional programming
languages. This method is based on the three key ideas: (i) transformation of a
matcher to a function that takes a pattern and a target, and returns lists of
triples of a pattern, a matcher, and a target; (ii) compilation of match-all to
application of the map function; (iii) transformation of a value pattern to a
function that takes an intermediate pattern-matching result and returns a
value. This paper shows the proposed method works by showing Scheme macros that
provide the users the pattern-matching facility of Egison. This paper also
presents benchmark results that show Egison pattern-matching embedded in Gauche
Scheme is faster than the original Egison interpreter.
