Parsing well-designed computer languages should not be a hard problem, be it for humans or for machines. This is not a new idea: in 1973, Vaughan R. Pratt argued against formalistic grammar specifications and in favor of a more intuitive and meaningful approach to designing and parsing syntax. In this Pearl, we take the reader on a journey through handwritten recursive descent parsing, revisiting Pratt’s original philosophy in a modern, statically-typed functional programming language. Contrary to many existing tutorials on the subject, we do not stop at simple expression languages: we also discuss how to tackle the full syntax of a simple programming language while avoiding the pitfalls of ad-hoc implementations. Indeed, a downside of recursive descent parsing is that the specification of what the parser accepts is written in code, which may contain subtle bugs and is not easily accessible to end users. We describe a simple recipe for architecting extensible recursive descent parsers that can automatically produce a readable representation of the syntax specification. We illustrate our approach by implementing a parser for a variant of Caml Light. Overall, this paper serves both as a pedagogical introduction to Pratt parsing in a modern programming language and as a practical guide to programmers who just want to implement, without unnecessary headaches, a computer language that is easy to parse and easy to read.

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.

Abstract We introduce the curve complexity heuristic (CCH), a KD‐tree construction strategy for 3D curves, which enables interactive exploration of neighborhoods in dense and large line datasets. It can be applied to searches of k‐nearest curves (KNC) as well as radius‐nearest curves (RNC). The CCH KD‐tree construction consists of two steps: (i) 3D curve decomposition that takes into account curve complexity and (ii) KD‐tree construction, which involves a novel splitting and early termination strategy. The obtained KD‐tree allows us to improve the speed of existing neighborhood search approaches by at least an order of magnitude (i. e., 28×for KNC and 12×for RNC with 98% accuracy) by considering local curve complexity. We validate this performance with a quantitative evaluation of the quality of search results and computation time. Also, we demonstrate the usefulness of our approach for supporting various applications such as interactive line queries, line opacity optimization, and line abstraction.