Pattern Matching in Order-Sorted Languages

Abstract We study the problem of pattern matching in languages whose type system is hierarchical and whose evaluation strategy is lazy. We propose an extension of the Puel-Suárez compilation scheme to function definitions via order-sorted patterns. Pattern matching trees (PMT's) are defined to have edges labelled not only with structure, but also with subsort constraints. Due to this latter kind of edges, terms are reduced only as far as required to make either a structure or a subsort verification decidable. We show that the PMT is optimal if a decidable property of sequentiality holds for the sets generated during the compilation process. Our method turns out to be applicable for strict languages as well.

Authors

• Delia Kesner

Keywords

No keywords are indexed for this paper.