Pattern calculus
 | This article includes a list of general references, but it lacks sufficient corresponding inline citations. (November 2016) |
Pattern calculus bases all computation on pattern matching of a very general kind. Like lambda calculus, it supports a uniform treatment of function evaluation. Also, it allows functions to be passed as arguments and returned as results. In addition, pattern calculus supports uniform access to the internal structure of arguments, be they pairs or lists or trees. Also, it allows patterns to be passed as arguments and returned as results. Uniform access is illustrated by a pattern-matching function <syntaxhighlight lang="text" class="" style="" inline="1">size</syntaxhighlight> that computes the size of an arbitrary data structure. In the notation of the programming language bondi, it is given by the recursive function <syntaxhighlight lang="haskell">let rec size =
| x y -> (size x) + (size y) | x -> 1
</syntaxhighlight>
The second, or default case <syntaxhighlight lang="text" class="" style="" inline="1">x -> 1</syntaxhighlight> matches the pattern <syntaxhighlight lang="text" class="" style="" inline="1">x</syntaxhighlight> against the argument and returns <syntaxhighlight lang="text" class="" style="" inline="1">1</syntaxhighlight>. This case is used only if the matching failed in the first case. The first, or special case matches against any compound, such as a non-empty list, or pair. Matching binds <syntaxhighlight lang="text" class="" style="" inline="1">x</syntaxhighlight> to the left component and <syntaxhighlight lang="text" class="" style="" inline="1">y</syntaxhighlight> to the right component. Then the body of the case adds the sizes of these components together.
Similar techniques yield generic queries for searching and updating. Combining recursion and decomposition in this way yields path polymorphism.
The ability to pass patterns as parameters (pattern polymorphism) is illustrated by defining a generic eliminator. Suppose given constructors <syntaxhighlight lang="text" class="" style="" inline="1">Leaf</syntaxhighlight> for creating the leaves of a tree, and <syntaxhighlight lang="text" class="" style="" inline="1">Count</syntaxhighlight> for converting numbers into counters. The corresponding eliminators are then <syntaxhighlight lang="haskell"> elimLeaf = | Leaf y -> y elimCount = | Count y -> y </syntaxhighlight>
For example, <syntaxhighlight lang="text" class="" style="" inline="1">elimLeaf (Leaf 3)</syntaxhighlight> evaluates to <syntaxhighlight lang="text" class="" style="" inline="1">3</syntaxhighlight> as does <syntaxhighlight lang="text" class="" style="" inline="1">elimCount (Count 3)</syntaxhighlight>.
These examples can be produced by applying the generic eliminator <syntaxhighlight lang="text" class="" style="" inline="1">elim</syntaxhighlight> to the constructors in question. It is defined by <syntaxhighlight lang="haskell"> elim = | x -> | {y} x y -> y </syntaxhighlight>
Now <syntaxhighlight lang="text" class="" style="" inline="1">elim Leaf</syntaxhighlight> evaluates to | {y} Leaf y -> y which is equivalent to <syntaxhighlight lang="text" class="" style="" inline="1">elimLeaf</syntaxhighlight>. Also <syntaxhighlight lang="text" class="" style="" inline="1">elim Count</syntaxhighlight> is equivalent to <syntaxhighlight lang="text" class="" style="" inline="1">elimCount</syntaxhighlight>.
In general, the curly braces <syntaxhighlight lang="text" class="" style="" inline="1">{} </syntaxhighlight> contain the bound variables of the
pattern, so that <syntaxhighlight lang="text" class="" style="" inline="1">x</syntaxhighlight> is free and <syntaxhighlight lang="text" class="" style="" inline="1">y</syntaxhighlight> is bound in | {y} x y -> y.
External links
- Archive mirror of the links below (which are no longer online)
- Jay, C. Barry (November 2004). "The pattern calculus". ACM Trans. Program. Lang. Syst. 26 (6): 911–937. doi:10.1145/1034774.1034775. S2CID 14252624. — the original paper, but not most general.
- Jay, B.; Kesner, D. (2006). "Pure Pattern Calculus". In Sestoft, P. (ed.). Programming Languages and Systems. ESOP 2006. Lecture Notes in Computer Science. Vol. 3924. Springer. pp. 100–114. doi:10.1007/11693024_8. hdl:10453/1684. ISBN 978-3-540-33096-7.
- Jay, Barry (2009). Pattern Calculus: Computing with Functions and Structures. Springer. doi:10.1007/978-3-540-89185-7. ISBN 978-3-540-89185-7.
- bondi programming language research site
- Given-Wilson, T.; Gorla, D.; Jay, B. (2010). "Concurrent Pattern Calculus". In Calude, C.S.; Sassone, V. (eds.). Theoretical Computer Science. TCS 2010. IFIP Advances in Information and Communication Technology. Vol. 323. Springer. doi:10.1007/978-3-642-15240-5_18. ISBN 978-3-642-15240-5.