Non-free data types are data types whose data have no canonical forms. For example, multisets are non-free data types because the multiset @math has two other equivalent but literally different forms @math and @math . Pattern matching is known to provide a handy tool set to treat such data types. Although many studies on pattern matching and implementations for practical programming languages have been proposed so far, we observe that none of these studies satisfy all the criteria of practical pattern matching, which are as follows: i) efficiency of the backtracking algorithm for non-linear patterns, ii) extensibility of matching process, and iii) polymorphism in patterns. This paper aims to design a new pattern-matching-oriented programming language that satisfies all the above three criteria. The proposed language features clean Scheme-like syntax and efficient and extensible pattern matching semantics. This programming language is especially useful for the processing of complex non-free data types that not only include multisets and sets but also graphs and symbolic mathematical expressions. We discuss the importance of our criteria of practical pattern matching and how our language design naturally arises from the criteria. The proposed language has been already implemented and open-sourced as the Egison programming language.
Functional logic programming @cite_4 is an approach towards this integration. It allows both of non-linear patterns and multiple pattern-matching results. The key difference between the functional logic programming and our approach is in the method for defining pattern-matching algorithms. In functional logic programming, we describe the pattern-matching algorithm for each pattern in the logic-programming style. A function that describes such an algorithm is called a . A pattern constructor takes decomposed values as its arguments and returns the target data. On the other hand, in our proposal, pattern constructors are defined in the functional-programming style: pattern constructors take a target datum as an argument and returns the decomposed values. This enables direct description of algorithms.
@cite_4
2149335820 2158107019 2106602483 2754180346
Type-based model checking algorithms for higher-order recursion schemes have recently emerged as a promising approach to the verification of functional programs. We introduce pattern-matching recursion schemes (PMRS) as an accurate model of computation for functional programs that manipulate algebraic data-types. PMRS are a natural extension of higher-order recursion schemes that incorporate pattern-matching in the defining rules. This paper is concerned with the following (undecidable) verification problem: given a correctness property φ, a functional program ℘ (qua PMRS) and a regular input set ℑ, does every term that is reachable from ℑ under rewriting by ℘ satisfy φ? To solve the PMRS verification problem, we present a sound semi-algorithm which is based on model-checking and counterexample guided abstraction refinement. Given a no-instance of the verification problem, the method is guaranteed to terminate. From an order-n PMRS and an input set generated by a regular tree grammar, our method constructs an order-n weak PMRS which over-approximates only the first-order pattern-matching behaviour, whilst remaining completely faithful to the higher-order control flow. Using a variation of Kobayashi's type-based approach, we show that the (trivial automaton) model-checking problem for weak PMRS is decidable. When a violation of the property is detected in the abstraction which does not correspond to a violation in the model, the abstraction is automatically refined by unfolding' the pattern-matching rules in the program to give successively more and more accurate weak PMRS models. Pattern matching is a great convenience in programming. However, pattern matching has its problems: it conflicts with data abstraction; it is complex (at least in Haskell, which has pattern guards, irrefutable patterns, n+k patterns, as patterns, etc.); it is a source of runtime errors; and lastly, one cannot abstract over patterns as they are not a first class language construct. This paper proposes a simplification of pattern matching that makes patterns first class. The key idea is to treat patterns as functions of type "a→ Maybe b"--i.e., "a→ (Nothing|Just b)"; thus, patterns and pattern combinators can be written as functions in the language. The integration of functional and logic programming is a well developed field of research. We discuss that the integration could be improved significantly in two separate aspects: sharing computations across non-deterministic branching and the declarative encapsulation of logic search. We then present a formal approach which shows how these improvements can be realized and prove the soundness of our approach. Pattern matching is a powerful tool for symbolic computations, based on the well-defined theory of term rewriting systems. Application domains include algebraic expressions, abstract syntax trees, and XML and JSON data. Unfortunately, no lightweight implementation of pattern matching as general and flexible as Mathematica exists for Python Mathics,MacroPy,patterns,PyPatt. Therefore, we created the open source module MatchPy which offers similar pattern matching functionality in Python using a novel algorithm which finds matches for large pattern sets more efficiently by exploiting similarities between patterns.