RECORD
Non-linear Pattern Matching with Backtracking for Non-free Data Types
Programming Languages · Submitted 31 Aug 2018
abstract compiled · 2026-09-23 · no language-model review
The authors' main claim The proposed language has been already implemented and open-sourced as the Egison programming language.
The compiled record
The paper's own sentences, arranged. Each label is drawn from a closed vocabulary; the number beside it is the probability the classifier gave that label. Numbers in the tables are the authors', checked by code. No sentence in this record was written by a model.
Open the compiled record
The abstract, sentence by sentence
Non-free data types are data types whose data have no canonical forms. For example, multisets are non-free data types because the multiset $\{a,b,b\}$ has two other equivalent but literally different forms $\{b,a,b\}$ and $\{b,b,a\}$. 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.
background contribution method result interpretation main claim
| # | sentence | role | the authors' own work | states the main conclusion | strength |
|---|---|---|---|---|---|
| s0 | Non-free data types are data types whose data have no canonical forms. | background 1.00 | 0.07 | 0.02 | asserted 1.00 |
| s1 | For example, multisets are non-free data types because the multiset $\{a,b,b\}$ has two other equivalent but literally different forms $\{b,a,b\}$ and $\{b,b,a\}$. | background 1.00 | 0.09 | 0.02 | asserted 1.00 |
| s2 | Pattern matching is known to provide a handy tool set to treat such data types. | background 1.00 | 0.05 | 0.02 | asserted 0.99 |
| s3 | 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. | gap 1.00 | 0.59 | 0.05 | asserted 1.00 |
| s4 | This paper aims to design a new pattern-matching-oriented programming language that satisfies all the above three criteria. | contribution 0.99 | 0.60 | 0.17 | asserted 0.91 |
| s5 | The proposed language features clean Scheme-like syntax and efficient and extensible pattern matching semantics. | contribution 0.90 | 0.79 | 0.16 | asserted 1.00 |
| s6 | 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. | contribution 0.76 | 0.38 | 0.09 | asserted 0.96 |
| s7 | We discuss the importance of our criteria of practical pattern matching and how our language design naturally arises from the criteria. | contribution 0.90 | 0.78 | 0.07 | asserted 0.90 |
| s8 | The proposed language has been already implemented and open-sourced as the Egison programming language. | contribution 0.81 | 0.90 | 0.16 | asserted 1.00 |
What was examined, and what was not
- arXiv listing abstract v2
- full text
- figures and tables
- references and citing sentences
- relations to other papers
- P abstract
- S sections
- T body sentences
- C citations
- R cross-paper relations
The paper
Original abstract
Non-free data types are data types whose data have no canonical forms. For example, multisets are non-free data types because the multiset $\{a,b,b\}$ has two other equivalent but literally different forms $\{b,a,b\}$ and $\{b,b,a\}$. 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.
Human review
How the literature uses it
What this paper does with the arXiv papers it cites
Discussion
Know something about this paper? Leave a comment, or highlight any passage above to comment on it.