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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
In fact, this phenomenon that “pattern matching against a single value yields multiple results” does not occur for free data types. This is the unique characteristic of non-free data types.
- 2.
- 3.
Here, we suppose that the number of decompositions by each pattern constructor can be approximated by the size of the target object.
References
Attributes::attnf - Wolfram Language Documentation. http://reference.wolfram.com/language/ref/message/Attributes/attnf.html. Accessed 14 June 2018
Introduction to Patterns - Wolfram Language Documentation. http://reference.wolfram.com/language/tutorial/Introduction-Patterns.html. Accessed 14 June 2018
Orderless - Wolfram Language Documentation. http://reference.wolfram.com/language/ref/Orderless.html. Accessed 14 June 2018
PAKCS. https://www.informatik.uni-kiel.de/~pakcs/. Accessed 14 June 2018
ViewPatterns - GHC. https://ghc.haskell.org/trac/ghc/wiki/ViewPatterns. Accessed 14 June 2018
The Egison programming language (2011). https://www.egison.org. Accessed 14 June 2018
Egison Mathematics Notebook (2016). https://www.egison.org/math. Accessed 14 June 2018
Antoy, S.: Programming with narrowing: a tutorial. J. Symb. Comput. 45(5), 501–522 (2010)
Antoy, S.: Constructor-based conditional narrowing. In: Proceedings of the 3rd ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (2001)
Antoy, S., Hanus, M.: Functional logic programming. Commun. ACM 53(4), 74–85 (2010)
Braßel, B., Hanus, M., Peemöller, B., Reck, F.: KiCS2: a new compiler from Curry to Haskell. In: Kuchen, H. (ed.) WFLP 2011. LNCS, vol. 6816, pp. 1–18. Springer, Heidelberg (2011). https://doi.org/10.1007/978-3-642-22531-4_1
Egi, S.: Non-linear pattern matching against non-free data types with lexical scoping. arXiv preprint arXiv:1407.0729 (2014)
Egi, S.: Scalar and tensor parameters for importing tensor index notation including Einstein summation notation. In: The Scheme and Functional Programming Workshop (2017)
Egi, S.: Scalar and tensor parameters for importing the notation in differential geometry into programming. arXiv preprint arXiv:1804.03140 (2018)
Erwig, M.: Active patterns. In: Kluge, W. (ed.) IFL 1996. LNCS, vol. 1268, pp. 21–40. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-63237-9_17
Erwig, M.: Functional programming with graphs. In: ACM SIGPLAN Notices, vol. 32 (1997)
Fischer, S., Kiselyov, O., Shan, C.: Purely functional lazy non-deterministic programming. In: ACM Sigplan Notices, vol. 44 (2009)
Hanus, M.: Multi-paradigm declarative languages. In: Dahl, V., Niemelä, I. (eds.) ICLP 2007. LNCS, vol. 4670, pp. 45–75. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74610-2_5
Hinze, R., Paterson, R.: Finger trees: a simple general-purpose data structure. J. Funct. Program. 16(2), 197–217 (2006)
Krebber, M.: Non-linear associative-commutative many-to-one pattern matching with sequence variables. arXiv preprint arXiv:1705.00907 (2017)
McBride, F., Morrison, D., Pengelly, R.: A symbol manipulation system. Mach. Intell. 5, 337–347 (1969)
Okasaki, C.: Views for standard ML. In: SIGPLAN Workshop on ML (1998)
Syme, D., Neverov, G., Margetson, J.: Extensible pattern matching via a lightweight language extension. In: ACM SIGPLAN Notices, vol. 42 (2007)
Thompson, S.: Lawful functions and program verification in Miranda. Sci. Comput. Program. 13(2–3), 181–218 (1990)
Thompson, S.: Laws in Miranda. In: Proceedings of the 1986 ACM Conference on LISP and Functional Programming (1986)
Tullsen, M.: First class patterns? In: Pontelli, E., Santos Costa, V. (eds.) PADL 2000. LNCS, vol. 1753, pp. 1–15. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-46584-7_1
Turner, D.A.: Miranda: a non-strict functional language with polymorphic types. In: Jouannaud, J.-P. (ed.) FPCA 1985. LNCS, vol. 201, pp. 1–16. Springer, Heidelberg (1985). https://doi.org/10.1007/3-540-15975-4_26
Wadler, P.: Views: a way for pattern matching to cohabit with data abstraction. In: Proceedings of the 14th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (1987)
Acknowledgments
We thank Ryo Tanaka, Takahisa Watanabe, Kentaro Honda, Takuya Kuwahara, Mayuko Kori, and Akira Kawata for their important contributions to implement the interpreter. We thank Michal J. Gajda, Yi Dai, Hiromi Hirano, Kimio Kuramitsu, and Pierre Imai for their helpful feedback on the earlier versions of the paper. We thank Masami Hagiya, Yoshihiko Kakutani, Yoichi Hirai, Ibuki Kawamata, Takahiro Kubota, Takasuke Nakamura, Yasunori Harada, Ikuo Takeuchi, Yukihiro Matsumoto, Hidehiko Masuhara, and Yasuhiro Yamada for constructive discussion and their continuing encouragement.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2018 Springer Nature Switzerland AG
About this paper
Cite this paper
Egi, S., Nishiwaki, Y. (2018). Non-linear Pattern Matching with Backtracking for Non-free Data Types. In: Ryu, S. (eds) Programming Languages and Systems. APLAS 2018. Lecture Notes in Computer Science(), vol 11275. Springer, Cham. https://doi.org/10.1007/978-3-030-02768-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-030-02768-1_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-02767-4
Online ISBN: 978-3-030-02768-1
eBook Packages: Computer ScienceComputer Science (R0)