Pattern Matching Based on Object Graphs

Abstract

Pattern matching has been widely adopted in functional programming languages, and is gradually getting popular in OO languages, from Scala to Python. The structural pattern matching currently in use has its foundation on algebraic data types from functional languages. To better reflect the pointer structures of OO programs, we propose a pattern matching extension to general statically typed OO languages based on object graphs. By this extension, we support patterns having aliasing and circular referencing, that are typically found in pointer structures. With the requirement of only an abstract subtyping preorder on types, our extension is not restricted to a particular hierarchical class model. We give the formal base of the graph model, that is able to handle aliases and cycles in patterns, together with the abstract syntax to construct the object graphs. More complex cases of conjunction and disjunction of multiple patterns are explored with resolution. We present the type checking rules and operational semantics to reason about the soundness by proving the type safety. We also discuss the design decisions, applicability and limitation of our pattern matching extension.

Keywords

• Pattern matching
• object graph
• subtyping
• type system
• operational semantics
• programming language