Pattern calculus (original) (raw)
Pattern calculus bases all computation on pattern matching of a very general kind. Like lambda calculus, it supports auniform treatment of function evaluation. Also, it allows functions to bepassed as arguments and returned as results. In addition, pattern calculus supportsuniform access to the internal structure of arguments, be they pairsor lists or trees. Also, it allows patterns to be passed as arguments andreturned as results. Uniform access is illustrated by apattern-matching function size that computes the size of anarbitrary data structure. In the notation of the programming languagebondi, it is given by the recursive function
| Property | Value | |||||||
|---|---|---|---|---|---|---|---|---|
| dbo:abstract | Pattern calculus bases all computation on pattern matching of a very general kind. Like lambda calculus, it supports auniform treatment of function evaluation. Also, it allows functions to bepassed as arguments and returned as results. In addition, pattern calculus supportsuniform access to the internal structure of arguments, be they pairsor lists or trees. Also, it allows patterns to be passed as arguments andreturned as results. Uniform access is illustrated by apattern-matching function size that computes the size of anarbitrary data structure. In the notation of the programming languagebondi, it is given by the recursive function let rec size = | x y -> (size x) + (size y) | x -> 1 The second, or default case x -> 1 matches the pattern xagainst the argument and returns 1. Thiscase is used only if the matching failed in the first case. Thefirst, or special case matches against any compound, suchas a non-empty list, or pair. Matching binds x to the left componentand y to the right component. Then the body of the case adds thesizes of these components together. Similar techniques yield generic queries for searching and updating. Combining recursion and decomposition in this way yields . The ability to pass patterns as parameters (pattern polymorphism) is illustrated by defining a generic eliminator. Suppose given constructors Leaf for creatingthe leaves of a tree, and Count for converting numbers intocounters. The corresponding eliminators are then elimLeaf = | Leaf y -> y elimCount = | Count y -> y For example, elimLeaf (Leaf 3) evaluates to 3 as does elimCount (Count 3). These examples can be produced by applying the generic eliminatorelim to the constructors in question. It is defined by elim = | x -> | {y} x y -> y Now elim Leaf evaluates to | {y} Leaf y -> y which is equivalent to elimLeaf. Also elim Count is equivalent to elimCount. In general, the curly braces {} contain the bound variables of thepattern, so that x is free and y is bound in | {y} x y -> y. (en) |
| dbo:wikiPageExternalLink | http://bondi.it.uts.edu.au/ https://link.springer.com/book/10.1007/978-3-540-89185-7 https://web.archive.org/web/20120327091406/http:/www-staff.it.uts.edu.au/~cbj/patterns/ https://dl.acm.org/doi/pdf/10.1145/1034774.1034775 | |||||||
| dbo:wikiPageID | 30643952 (xsd:integer) | |||||||
| dbo:wikiPageLength | 4261 (xsd:nonNegativeInteger) | |||||||
| dbo:wikiPageRevisionID | 1108362371 (xsd:integer) | |||||||
| dbo:wikiPageWikiLink | dbc:Lambda_calculus dbr:Data_structure dbr:Lambda_calculus dbr:Recursion_(computer_science) dbr:Pattern_matching dbr:Programming_language dbr:Evaluation_strategy dbr:List_(computer_science) dbr:Tree_(computer_science) dbr:Path_polymorphism | |||||||
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Cite_journal dbt:Code dbt:More_footnotes dbt:Refbegin dbt:Refend | |||||||
| dct:subject | dbc:Lambda_calculus | |||||||
| rdfs:comment | Pattern calculus bases all computation on pattern matching of a very general kind. Like lambda calculus, it supports auniform treatment of function evaluation. Also, it allows functions to bepassed as arguments and returned as results. In addition, pattern calculus supportsuniform access to the internal structure of arguments, be they pairsor lists or trees. Also, it allows patterns to be passed as arguments andreturned as results. Uniform access is illustrated by apattern-matching function size that computes the size of anarbitrary data structure. In the notation of the programming languagebondi, it is given by the recursive function (en) | |||||||
| rdfs:label | Pattern calculus (en) | |||||||
| owl:sameAs | freebase:Pattern calculus wikidata:Pattern calculus https://global.dbpedia.org/id/4tHHm | |||||||
| prov:wasDerivedFrom | wikipedia-en:Pattern_calculus?oldid=1108362371&ns=0 | |||||||
| foaf:isPrimaryTopicOf | wikipedia-en:Pattern_calculus | |||||||
| is dbo:wikiPageWikiLink of | dbr:Matching_wildcards dbr:Pattern_matching | |||||||
| is foaf:primaryTopic of | wikipedia-en:Pattern_calculus |