Basic Pattern Matching Calculi: A Fresh View on Matching Failure

Wolfram Kahl

pp. 276-290 in Y. Kameyama and P. Stuckey (eds.) Functional and Logic Programming, Proceedings of FLOPS 2004, Nara, Japan, April 7--9, 2004, LNCS 2998, Springer-Verlag, 2004.

(.bib, .ps.gz, .pdf )


We propose pattern matching calculi as a refinement of lambda-calculus that integrates mechanisms appropriate for fine-grained modelling of non-strict pattern matching.

Compared with the functional rewriting strategy usually employed to define the operational semantics of pattern matching in non-strict functional programming languages like Haskell or Clean, our pattern matching calculi achieve the same effects using simpler and more local rules.

The main device is to embed into expressions the separate syntactic category of matchings; the resulting language naturally encompasses pattern guards and Boolean guards as special cases.

By allowing a confluent reduction system and a normalising strategy, these pattern matching calculi provide a new basis for operational semantics of non-strict programming languages and also for implementations.

See also the PMC page.

Wolfram Kahl