Filtrage par motif | EPFL Graph Search

Le filtrage par motif est la vérification de la présence de constituants d'un motif par un programme informatique, ou parfois par un matériel spécialisé. Par contraste avec la reconnaissance de forme, les motifs sont complètement spécifiés. De tels motifs concernent conventionnellement des séquences ou des arbres. Par exemple "HDpdf" peut signifier : "Toute chaîne contenant HD et se terminant par pdf". Le filtrage par motif permet de vérifier si l'objet du filtrage possède une structure donnée, s'il s'y trouve telle ou telle sous-structure spécifique et laquelle, pour y retrouver des parties par l'organisation de leur contenu, et/ou éventuellement pour substituer quelque chose d'autre aux motifs reconnus. Les séquences (particulièrement les chaînes de caractères) sont souvent décrites par des expressions rationnelles. Elles peuvent aussi être vues comme des arbres. Les motifs d'arbre peuvent être utilisés par les langages de programmation comme un outil général pour traiter leur

Object-oriented pattern matching

Burak Emir

Pattern matching is a programming language construct considered essential in functional programming. Its purpose is to inspect and decompose data. Instead, object-oriented programming languages do not have a dedicated construct for this purpose. A possible reason for this is that pattern matching is useful when data is defined separately from operations on the data – a scenario that clashes with the object-oriented motto of grouping data and operations. However, programmers are frequently confronted with situations where there is no alternative to expressing data and operations separately – because most data is neither stored in nor does it originate from an object-oriented context. Consequently, object-oriented programmers, too, are in need for elegant and concise solutions to the problem of decomposing data. To this end, we propose a built-in pattern matching construct compatible with object-oriented programming. We claim that it leads to more concise and readable code than standard object-oriented approaches. A pattern in our approach is any computable way of testing and deconstructing an object and binding relevant parts to local names. We introduce pattern matching in two variants, case classes and extractors. We compare the readability, extensibility and performance of built-in pattern matching in these two variants with standard decomposition techniques. It turns out that standard object-oriented approaches to decomposing data are not extensible. Case classes, which have been studied before, require a low notational overhead, but expose their representation, making them hard to change later. The novel extractor mechanism offers loose coupling and extensibility, but comes with a performance overhead. We present a formalization of object-oriented pattern matching with extractors. This is done by giving definitions and proving standard properties for a calculus that provides pattern matching as described before. We then give a formal, optimizing translation from the calculus including pattern matching to its fragment without pattern matching, and prove it correct. Finally, we consider non-obvious interactions between the pattern matching and parametric polymorphism. We review the technique of generalized algebraic data types from functional programming, and show how it can be carried over to the object-oriented style. The main tool is the extension of the type system with subtype constraints, which leads to a very expressive metatheory. Through this theory, we are able to express patterns that operate on existentially quantified types purely by universally quantified extractors.

EPFL2007

Compiling Regular Patterns to Sequential Machines

Burak Emir

Pattern matching combined with regular expressions has many applications including text and XML processing, lexical analysis, classification of DNA segments and content-based routing. Patterns contain variables to refer to parts of the matching input. But regular patterns pose the problem of ambiguity: Words can be matched against 'overlapping' sections of the pattern in several ways, yielding different variable bindings. A match policy like shortest or longest match disambiguates the outcome of matching. In order to implement the longest/shortest match policies, we propose to compile regular patterns to sequential machines. This intuitive approach %to resolving ambiguities by means of shortest/longest match %policies (and the slightly different ungreedy/greedy match), with lets us derive a compilation scheme with linear runtime complexity. \par The main contributions of this paper are firstly, a decision procedure for unambiguous regular patterns, which can be matched with a single traversal of the input, and secondly, algorithms to obtain deterministic sequential machines from ambiguous patterns. These produce the shortest(longest) match in two consecutive runs. The first run produces an intermediary result from which all possible variable bindings can be reproduced. The second run then chooses the unique binding which adheres to the given match policy. In the general case, this approach is optimal.

2004

Object-oriented pattern matching

Burak Emir

EPFL2007