https://dl.acm.org/doi/10.1145/3689746 skip to main content * ACM Digital Library home * ACM Association for Computing Machinery corporate logo * Advanced Search * Browse * About * + Sign in + Register * * Advanced Search * Journals * Magazines * Proceedings * Books * SIGs * Conferences * People * * More * Search ACM Digital Library[ ] SearchSearch Advanced Search Proceedings of the ACM on Programming Languages * Journal Home * Just Accepted * Latest Issue * * Archive * Authors + Author Guidelines + Calls for Papers + PACMPL Policies + ACM Author Policies + Author List * Editors + Editorial Board + Associate Editors Welcome Video * Reviewers * Open Access + PACMPL Open Access + ACM Open Access * Award Winners * About + About PACMPL + Announcements + Abstracting/Indexing + PACMPL Affiliations * Contact Us * More * Home * ACM Journals * Proceedings of the ACM on Programming Languages * Vol. 8, No. OOPSLA2 * The Ultimate Conditional Syntax research-article Open access [icon-small][icon-small][icon-small] Share on * * * * * * The Ultimate Conditional Syntax Authors: [contrib-99]Luyu Cheng, [default-pr]Lionel ParreauxAuthors Info & Claims Proceedings of the ACM on Programming Languages, Volume 8, Issue OOPSLA2 Article No.: 306, Pages 988 - 1017 https://doi.org/10.1145/3689746 Published: 08 October 2024 Publication History Related Artifact: The Ultimate Conditional Syntax (Artifact) October 2024 software https://doi.org/10.5281/zenodo.13621222 0citation2,489Downloads Metrics Total Citations0 Total Downloads2,489 Last 12 Months2,489 Last 6 weeks2,489 Get Citation Alerts New Citation Alert added! This alert has been successfully added and will be sent to: You will be notified whenever a record that you have chosen has been cited. To manage your alert preferences, click on the button below. Manage my Alerts New Citation Alert! Please log in to your account PDFeReader * Contents Proceedings of the ACM on Programming Languages Volume 8, Issue OOPSLA2 PREVIOUS ARTICLE Refinement Type Refutations Previous NEXT ARTICLE On the Expressive Power of Languages for Static Variability Next + Abstract + References ACM Digital Library * + Information & Contributors + Bibliometrics & Citations + View Options + References + Media + Tables + Share Abstract Functional programming languages typically support expressive pattern-matching syntax allowing programmers to write concise and type-safe code, especially appropriate for manipulating algebraic data types. Many features have been proposed to enhance the expressiveness of stock pattern-matching syntax, such as pattern bindings, pattern alternatives (a.k.a. disjunction), pattern conjunction, view patterns, pattern guards, pattern synonyms, active patterns, 'if-let' patterns, multi-way if-expressions, etc. In this paper, we propose a new pattern-matching syntax that is both more expressive and (we argue) simpler and more readable than previous alternatives. Our syntax supports parallel and nested matches interleaved with computations and intermediate bindings. This is achieved through a form of nested multi-way if-expressions with a condition-splitting mechanism to factor common conditional prefixes as well as a binding technique we call conditional pattern flowing. We motivate this new syntax with many examples in the setting of MLscript, a new ML-family programming language. We describe a straightforward desugaring pass from our rich source syntax into a minimal core syntax that only supports flat patterns and has an intuitive small-step semantics. We then provide a translation from the core syntax into a normalized syntax without backtracking, which is more amenable to coverage checking and compilation, and formally prove that our translation is semantics-preserving. We view this work as a step towards rethinking pattern matching to make it more powerful and natural to use. Our syntax can easily be integrated, in part or in whole, into existing as well as future programming language designs. References [1] William Aitken and John H. Reppy. 1992. Abstract Value Constructors: Symbolic Constants for Standard ML. Cornell University. https:// hdl.handle.net/1813/7130 Google Scholar [2] Lennart Augustsson. 1984. A Compiler for Lazy ML. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (LFP '84). Association for Computing Machinery, New York, NY, USA. 218-227. isbn:0897911423 https://doi.org/10.1145/800055.802038 Digital Library Google Scholar [3] Lennart Augustsson. 1985. Compiling pattern matching. In Functional Programming Languages and Computer Architecture, Jean-Pierre Jouannaud (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 368-381. isbn:978-3-540-39677-2 Google Scholar [4] Emilie Balland and Pierre-Etienne Moreau. 2006. Optimizing pattern matching compilation by program transformation. 19. https:// inria.hal.science/inria-00001127 Google Scholar [5] Hendrik Pieter Barendregt. 1984. Chapter 2 - Conversion. In The Lambda Calculus, H.P. BARENDREGT (Ed.) (Studies in Logic and the Foundations of Mathematics, Vol. 103). Elsevier, 22-49. issn:0049-237X https://doi.org/10.1016/B978-0-444-87508-2.50010-1 Crossref Google Scholar [6] Geoff Barrett and Philip Wadler. 1987. Derivation of a Pattern-Matching Compiler. https://homepages.inf.ed.ac.uk/wadler/ papers/pattern/pattern.pdf Google Scholar [7] Jonathan Immanuel Brachthauser, Philipp Schuster, Edward Lee, and Aleksander Boruch-Gruszecki. 2022. Effects, capabilities, and boxes: from scope-based reasoning to type-based reasoning and back. Proc. ACM Program. Lang., 6, OOPSLA1 (2022), Article 76, Apr, 30 pages. https://doi.org/10.1145/3527320 Digital Library Google Scholar [8] Jonathan Immanuel Brachthauser, Philipp Schuster, and Klaus Ostermann. 2020. Effects as capabilities: effect handlers and lightweight effect polymorphism. Proc. ACM Program. Lang., 4, OOPSLA (2020), Article 126, Nov, 30 pages. https://doi.org/10.1145/3428194 Digital Library Google Scholar [9] R. M. Burstall. 1969. Proving Properties of Programs by Structural Induction. Comput. J., 12, 1 (1969), 02, 41-48. issn:0010-4620 https: //doi.org/10.1093/comjnl/12.1.41 arxiv:https://academic.oup.com/ comjnl/article-pdf/12/1/41/885019/12-1-41.pdf. Crossref Google Scholar [10] R. M. Burstall and John Darlington. 1977. A Transformation System for Developing Recursive Programs. J. ACM, 24, 1 (1977), Jan, 44-67. issn:0004-5411 https://doi.org/10.1145/321992.321996 Digital Library Google Scholar [11] R. M. Burstall, D. B. MacQueen, and D. T. Sannella. 1980. HOPE: An experimental applicative language. In Proceedings of the 1980 ACM Conference on LISP and Functional Programming (LFP '80). Association for Computing Machinery, New York, NY, USA. 136-143. isbn:9781450373968 https://doi.org/10.1145/800087.802799 Digital Library Google Scholar [12] Warren Burton, Erik Meijer, Patrick Sansom, Simon Thompson, and Philip Wadler. 1996. Views: An extension to Haskell pattern matching. Google Scholar [13] Luca Cardelli. 1984. Compiling a functional language. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (LFP '84). Association for Computing Machinery, New York, NY, USA. 208-217. isbn:0897911423 https://doi.org/10.1145/800055.802037 Digital Library Google Scholar [14] Giuseppe Castagna. 2024. Programming with union, intersection, and negation types. arxiv:2111.03354. Google Scholar [15] Giuseppe Castagna and Alain Frisch. 2005. A gentle introduction to semantic subtyping. In Proceedings of the 7th ACM SIGPLAN International Conference on Principles and Practice of Declarative Programming (PPDP '05). Association for Computing Machinery, New York, NY, USA. 198-208. isbn:1595930906 https://doi.org/10.1145/ 1069774.1069793 Digital Library Google Scholar [16] Giuseppe Castagna, Victor Lanvin, Mickael Laurent, and Kim Nguyen. 2022. Revisiting occurrence typing. Science of Computer Programming, 217 (2022), May, 102781. issn:0167-6423 https://doi.org/10.1016/ j.scico.2022.102781 Digital Library Google Scholar [17] Giuseppe Castagna, Kim Nguyen, Zhiwu Xu, and Pietro Abate. 2015. Polymorphic Functions with Set-Theoretic Types: Part 2: Local Type Inference and Type Reconstruction. In Proceedings of the 42nd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '15). Association for Computing Machinery, New York, NY, USA. 289-302. isbn:9781450333009 https://doi.org/10.1145/2676726.2676991 Digital Library Google Scholar [18] Luyu Cheng and Lionel Parreaux. 2024. The Ultimate Conditional Syntax (Artifact). https://doi.org/10.5281/zenodo.13621222 Digital Library Google Scholar [19] Stephen Dolan. 2017. Algebraic subtyping. Ph. D. Dissertation. isbn:978-1-78017-415-0 Google Scholar [20] Stephen Dolan and Alan Mycroft. 2017. Polymorphism, subtyping, and type inference in MLsub. ACM SIGPLAN Notices, 52, 1 (2017), Jan., 60-72. issn:0362-1340 https://doi.org/10.1145/3093333.3009882 Digital Library Google Scholar [21] ECMA International. 2023. ECMA-334: C# Language Specification (7th Edition). https://ecma-international.org/publications-and-standards/ standards/ecma-334/ Accessed: 2024-08-05 Google Scholar [22] Martin Erwig. 1997. Active patterns. In Implementation of Functional Languages, Werner Kluge (Ed.). Springer Berlin Heidelberg, Berlin, Heidelberg. 21-40. isbn:978-3-540-69239-3 Google Scholar [23] Martin Erwig and Simon Peyton Jones. 2001. Pattern Guards and Transformational Patterns. Electronic Notes in Theoretical Computer Science, 41, 1 (2001), 3. issn:1571-0661 https://doi.org/10.1016/ S1571-0661(05)80540-7 2000 ACM SIGPLAN Haskell Workshop (Satellite Event of PLI 2000) Crossref Google Scholar [24] Arthur Evans. 1968. PAL--a language designed for teaching programming linguistics. In Proceedings of the 1968 23rd ACM National Conference (ACM '68). Association for Computing Machinery, New York, NY, USA. 395-403. isbn:9781450374866 https://doi.org/10.1145/800186.810604 Digital Library Google Scholar [25] Tim Freeman and Frank Pfenning. 1991. Refinement Types for ML. In Proceedings of the ACM SIGPLAN 1991 Conference on Programming Language Design and Implementation (PLDI '91). ACM, New York, NY, USA. 268-277. isbn:978-0-89791-428-4 https://doi.org/10.1145/ 113445.113468 event-place: Toronto, Ontario, Canada Digital Library Google Scholar [26] Daniel P. Friedman and David S. Wise. 1976. CONS should not Evaluate its Arguments. https://help.luddy.indiana.edu/techreports/TRNNN.cgi? trnum=TR44 In I. S. Michaelson and R. Milner (eds.), Automata, Languages and Programming, Edinburgh University Press, Edinburgh (1976), 256-284 Google Scholar [27] Robert Harper. 2016. Practical foundations for programming languages. Cambridge University Press. Digital Library Google Scholar [28] P. J. Landin. 1966. The next 700 programming languages. Commun. ACM, 9, 3 (1966), Mar, 157-166. issn:0001-0782 https://doi.org/10.1145/ 365230.365257 Digital Library Google Scholar [29] Fabrice Le Fessant and Luc Maranget. 2001. Optimizing Pattern Matching. ACM SIGPLAN Notices, 36 (2001), 08, https://doi.org/10.1145 /507635.507641 Digital Library Google Scholar [30] David MacQueen and M Baudinet. 1985. Tree Pattern matching for ML. Unpublished manuscript. Google Scholar [31] David MacQueen, Robert Harper, and John Reppy. 2020. The history of Standard ML. Proc. ACM Program. Lang., 4, HOPL (2020), Article 86, Jun, 100 pages. https://doi.org/10.1145/3386336 Digital Library Google Scholar [32] Luc Maranget. 1994. Two Techniques for Compiling Lazy Pattern Matching. INRIA. https://inria.hal.science/inria-00074292 Projet PARA Google Scholar [33] Luc Maranget. 2008. Compiling Pattern Matching to Good Decision Trees. In Proceedings of the 2008 ACM SIGPLAN Workshop on ML (ML '08). Association for Computing Machinery, New York, NY, USA. 35-46. isbn:9781605580623 https://doi.org/10.1145/1411304.1411311 Digital Library Google Scholar [34] Conor McBride and James McKinna. 2004. The view from the left. Journal of Functional Programming, 14, 1 (2004), 69-111. https:// doi.org/10.1017/S0956796803004829 Digital Library Google Scholar [35] Robin Milner. 1978. A theory of type polymorphism in programming. J. Comput. System Sci., 17, 3 (1978), Dec., 348-375. issn:0022-0000 https://doi.org/10.1016/0022-0000(78)90014-4 Crossref Google Scholar [36] Robin Milner. 1984. A proposal for standard ML. In Proceedings of the 1984 ACM Symposium on LISP and Functional Programming (LFP '84). Association for Computing Machinery, New York, NY, USA. 184-197. isbn:0897911423 https://doi.org/10.1145/800055.802035 Digital Library Google Scholar [37] Nadia Nedjah. 1998. Minimal deterministic left-to-right pattern-matching automata. SIGPLAN Not., 33, 1 (1998), jan, 40-47. issn:0362-1340 https://doi.org/10.1145/609742.609748 Digital Library Google Scholar [38] Nadia Nedjah and Luiza de Macedo Mourelle. 2002. Optimal Adaptive Pattern Matching. In Developments in Applied Artificial Intelligence, Tim Hendtlass and Moonis Ali (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 768-779. isbn:978-3-540-48035-8 Google Scholar [39] Martin Odersky, Philippe Altherr, Vincent Cremet, Burak Emir, Sebastian Maneth, Stephane Micheloud, Nikolay Mihaylov, Michel Schinz, Erik Stenman, and Matthias Zenger. 2004. An overview of the Scala programming language. Google Scholar [40] Lionel Parreaux. 2020. The Simple Essence of Algebraic Subtyping: Principal Type Inference with Subtyping Made Easy (Functional Pearl). Proc. ACM Program. Lang., 4, ICFP (2020), Article 124, Aug., 28 pages. https://doi.org/10.1145/3409006 Digital Library Google Scholar [41] Lionel Parreaux and Chun Yin Chau. 2022. MLstruct: Principal Type Inference in a Boolean Algebra of Structural Types. Proc. ACM Program. Lang., 6, OOPSLA2 (2022), Article 141, Oct, 30 pages. https: //doi.org/10.1145/3563304 Digital Library Google Scholar [42] David J. Pearce. 2013. Sound and Complete Flow Typing with Unions, Intersections and Negations. In Verification, Model Checking, and Abstract Interpretation, Roberto Giacobazzi, Josh Berdine, and Isabella Mastroeni (Eds.) (Lecture Notes in Computer Science). Springer, Berlin, Heidelberg. 335-354. isbn:978-3-642-35873-9 https:/ /doi.org/10.1007/978-3-642-35873-9_21 Digital Library Google Scholar [43] Mikael Pettersson. 1992. A term pattern-match compiler inspired by finite automata theory. In Compiler Construction, Uwe Kastens and Peter Pfahler (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg. 258-270. isbn:978-3-540-47335-0 Google Scholar [44] Matthew Pickering, Gergo Erdi, Simon Peyton Jones, and Richard A. Eisenberg. 2016. Pattern synonyms. In Proceedings of the 9th International Symposium on Haskell (Haskell 2016). Association for Computing Machinery, New York, NY, USA. 80-91. isbn:9781450344340 https://doi.org/10.1145/2976002.2976013 Digital Library Google Scholar [45] Martin Richards. 1967. BCPL Reference Manual. Designated Memorandum M-352 of MIT Project MAC. https://www.bell-labs.com/usr/dmr/www/ bcpl.html Available at Bell Labs website Google Scholar [46] Kevin Scott and Norman Ramsey. 2000. When Do Match-compilation Heuristics Matter? University of Virginia, Department of Computer Science. https://doi.org/10.18130/V3GB4M Crossref Google Scholar [47] R. C. Sekar, R. Ramesh, and I. V. Ramakrishnan. 1995. Adaptive Pattern Matching. SIAM J. Comput., 24, 6 (1995), 1207-1234. https:// doi.org/10.1137/S0097539793246252 arxiv:https://doi.org/10.1137/ S0097539793246252. Digital Library Google Scholar [48] Giacomo Servadei. 2018. Toward a more expressive pattern matching in Haskell. Google Scholar [49] Yuriy Solodkyy, Gabriel Dos Reis, and Bjarne Stroustrup. 2013. Open pattern matching for C++. In Proceedings of the 12th International Conference on Generative Programming: Concepts & Experiences (GPCE '13). Association for Computing Machinery, New York, NY, USA. 33-42. isbn:9781450323734 https://doi.org/10.1145/2517208.2517222 Digital Library Google Scholar [50] Sam Tobin-Hochstadt and Matthias Felleisen. 2008. The Design and Implementation of Typed Scheme. In Proceedings of the 35th Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '08). Association for Computing Machinery, New York, NY, USA. 395-406. isbn:9781595936899 https://doi.org/10.1145/1328438.1328486 Digital Library Google Scholar [51] D Turner. 1986. An overview of Miranda. SIGPLAN Not., 21, 12 (1986), Dec, 158-166. issn:0362-1340 https://doi.org/10.1145/15042.15053 Digital Library Google Scholar [52] D. A. Turner. 1979. A new implementation technique for applicative languages. Software: Practice and Experience, 9, 1 (1979), 31-49. https://doi.org/10.1002/spe.4380090105 arxiv:https:// onlinelibrary.wiley.com/doi/pdf/10.1002/spe.4380090105. Crossref Google Scholar [53] D. A. Turner. 1981. The semantic elegance of applicative languages. In Proceedings of the 1981 Conference on Functional Programming Languages and Computer Architecture (FPCA '81). Association for Computing Machinery, New York, NY, USA. 85-92. isbn:0897910605 https: //doi.org/10.1145/800223.806766 Digital Library Google Scholar [54] Philip Wadler. 1987. The Implementation of Functional Programming Languages. Prentice Hall. https://www.amazon.com/ Implementation-Functional-Programming-Prentice-hall-International/dp/ 013453333X Google Scholar [55] P. Wadler. 1987. 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 (POPL '87). Association for Computing Machinery, New York, NY, USA. 307-313. isbn:0897912152 https://doi.org/10.1145/41625.41653 Digital Library Google Scholar [56] Hongwei Xi and Frank Pfenning. 1998. Eliminating array bound checking through dependent types. In Proceedings of the ACM SIGPLAN 1998 Conference on Programming Language Design and Implementation (PLDI '98). Association for Computing Machinery, New York, NY, USA. 249-257. isbn:0897919874 https://doi.org/10.1145/277650.277732 Digital Library Google Scholar [57] Hongwei Xi and Frank Pfenning. 1999. Dependent types in practical programming. In Proceedings of the 26th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL '99). Association for Computing Machinery, New York, NY, USA. 214-227. isbn:1581130953 https://doi.org/10.1145/292540.292560 Digital Library Google Scholar Index Terms 1. The Ultimate Conditional Syntax 1. Software and its engineering 1. Software notations and tools 1. Formal language definitions 1. Semantics 2. Syntax 2. General programming languages 1. Language features 1. Control structures 2. Language types 1. Functional languages 2. Theory of computation 1. Design and analysis of algorithms 1. Data structures design and analysis 1. Pattern matching Recommendations * APAREL--A parse-request language APAREL is described: this language is an extension to an algorithmic language (PL/I) that provides the pattern-matching capabilities normally found only in special purpose languages such as SNOBOL4 and TMG. This capability is provided through parse-... Read More * PLCC: a programming language compiler compiler SIGCSE '14: Proceedings of the 45th ACM technical symposium on Computer science education This paper describes PLCC, a compiler-compiler tool to support courses in programming languages, compilers, and computational theory. This tool has proven to be useful for implementing interpreters, building compilers, and creating parsers for context-... Read More * An Empirical Investigation into Programming Language Syntax Recent studies in the literature have shown that syntax remains a significant barrier to novice computer science students in the field. While this syntax barrier is known to exist, whether and how it varies across programming languages has not been ... Read More Comments Please enable JavaScript to view thecomments powered by Disqus. Information & Contributors Information Published In cover image Proceedings of the ACM on Programming Languages Proceedings of the ACM on Programming Languages Volume 8, Issue OOPSLA2 October 2024 2691 pages EISSN:2475-1421 DOI:10.1145/3554319 * Editor: * Author PictureMichael Hicks Amazon, USA Issue's Table of Contents Copyright (c) 2024 Owner/Author. This work is licensed under a Creative Commons Attribution International 4.0 License. Publisher Association for Computing Machinery New York, NY, United States Publication History Published: 08 October 2024 Published in PACMPL Volume 8, Issue OOPSLA2 Permissions Request permissions for this article. Request Permissions Check for updates Badges * [icon-large]Artifacts Available / v1.1 * [icon-large]Artifacts Evaluated & Reusable / v1.1 * [icon-large]Results Reproduced / v1.1 Author Tags 1. pattern matching 2. programming language design 3. syntax Qualifiers * Research-article Contributors [loader-7e6] Other Metrics View Article Metrics Bibliometrics & Citations Bibliometrics Article Metrics * 0 Total Citations * 2,489 Total Downloads * Downloads (Last 12 months)2,489 * Downloads (Last 6 weeks)2,489 Reflects downloads up to 17 Oct 2024 Other Metrics View Author Metrics Citations View Options View options PDF View or Download as a PDF file. PDF eReader View online with eReader. eReader Get Access Login options Check if you have access through your login credentials or your institution to get full access on this article. Sign in Full Access Get this Article Media Figures Other Tables Share Share Share this Publication link Copy Link Copied! Copying failed. Share on social media XLinkedInRedditFacebookemail Affiliations [contrib-99] Luyu Cheng Hong Kong University of Science and Technology, Hong Kong, Hong Kong https://orcid.org/0000-0001-8267-3126 View Profile [default-pr] Lionel Parreaux Hong Kong University of Science and Technology, Hong Kong, Hong Kong https://orcid.org/0000-0002-8805-0728 View Profile Download PDF Go to Go to Show all references Request permissionsExpand All Collapse Expand Table Authors Info & Affiliations View Issue's Table of Contents Export Citations Select Citation format[BibTeX ] * Please download or close your previous search result export first before starting a new bulk export. Preview is not available. By clicking download,a status dialog will open to start the export process. The process may takea few minutes but once it finishes a file will be downloadable from your browser. You may continue to browse the DL while the export process is in progress. Download + Download citation + Copy citation Footer Categories * Journals * Magazines * Books * Proceedings * SIGs * Conferences * Collections * People About * About ACM Digital Library * ACM Digital Library Board * Subscription Information * Author Guidelines * Using ACM Digital Library * All Holdings within the ACM Digital Library * ACM Computing Classification System * Accessibility Statement Join * Join ACM * Join SIGs * Subscribe to Publications * Institutions and Libraries Connect * Contact us via email * ACM on Facebook * ACM DL on X * ACM on Linkedin * Send Feedback * Submit a Bug Report The ACM Digital Library is published by the Association for Computing Machinery. Copyright (c) 2024 ACM, Inc. * Terms of Usage * Privacy Policy * Code of Ethics ACM Digital Library home ACM Association for Computing Machinery corporate logo Your Search Results Download Request We are preparing your search results for download ... We will inform you here when the file is ready. Download now! Your Search Results Download Request Your file of search results citations is now ready. Download now! Your Search Results Download Request Your search export query has expired. Please try again.