Extended pattern matching for embedded languages

Abstract. Users of embedded languages might want to pattern match on embedded programs. Making this possible requires a considerable effort from the developer of the language, because the underlying data types are usually hidden.
This paper first analyses the available solutions for this problem. As pattern synonyms [13] and function patterns [6] seem promising, a compromise between these two is proposed: restricted function patterns. These are more general than pattern synonyms, but it is still possible to process them at compilation time. It is interesting that this proposal makes Haskell's rules about matching numeric literals more regular. It also provides Erlang's list prefix patterns in a consistent way instead of ad hoc implementations.
Finally, a lightweight prototype implementation is presented, which implements the functionality of the proposal, but cannot give the static guarantees that proper compiler support could achieve.