Non-linear Pattern Matching with Backtracking for Non-free Data Types
Non-linear Pattern Matching with Backtracking for Non-free Data Types
复制标题
非自由数据类型的回溯非线性模式匹配
DOI：
10.1007/978-3-030-02768-1_1
复制
发表时间：
2018
期刊：
影响因子：
--
通讯作者：
Nishiwaki Yuichi
中科院分区：
文献类型：
--
作者：
Egi Satoshi;Nishiwaki Yuichi
非自由数据类型是指其数据没有规范形式的数据类型。例如，多重集是非自由数据类型，因为多重集具有其他两种等效但实际上不同的形式。众所周知，模式匹配提供了一个方便的工具集来处理此类数据类型。尽管迄今为止已经提出了许多关于实用编程语言的模式匹配和实现的研究，但我们发现这些研究都没有满足实用模式匹配的所有标准，这些标准如下：（i）非线性模式回溯算法的效率，（ii）匹配过程的可扩展性，以及（iii）模式的多态性。本文旨在设计一种满足所有上述三个标准的新型面向模式匹配的编程语言。所提出的语言具有干净的类似方案的语法和高效且可扩展的模式匹配语义。这种编程语言对于处理复杂的非自由数据类型特别有用，这些数据类型不仅包括多重集和集合，还包括图形和符号数学表达式。我们讨论了实际模式匹配标准的重要性以及我们的语言设计如何自然地从这些标准中产生。所提议的语言已经作为 Egison 编程语言实现并开源。
Non-free data typesare data types whose data have no canonical forms. For example, multisets are non-free data types because the multisethas two other equivalent but literally different formsand.Pattern matchingis 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 thecriteria 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 newpattern-matching-orientedprogramming 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.