Paisley: A Pattern Matching Library for Arbitrary Object Models

Abstract: Professional development of software dealing with structured models re-quires more systematic approach and semantic foundation than standard practice in general-purpose programming languages affords. One remedy is to integrate tech-niques from other programming paradigms, as seamless as possible and without forc-ing programmers to leave their comfort zone. Here we present a tool for the imple-mentation of pattern matching as fundamental means of automated data extraction from models of arbitrary shape and complexity in a general-purpose programming language. The interface is simple but, thanks to elaborate and rigorous design, is also light-weight, portable, non-invasive, type-safe, modular and extensible. It is compat-ible with object-oriented data abstraction and has full support for nondeterminism by backtracking. The tool comes as a library consisting of two levels: elementary pat-tern algebra (generic, highly reusable) and pattern bindings for particular data models (specific, fairly reusable, user-definable). Applications use the library code in a small number of idiomatic ways, making pattern-matching code declarative in style, easily writable, readable and maintainable. Library and idiom together form a tightly em-bedded domain-specific language; no extension of the host language is required. The current implementation is in Java, but assumes only standard object-oriented features, and can hence be ported to other mainstream languages.