An Alternative to Pattern Matching, Inspired by Verse

Abstract

Senior thesis:

Pattern matching appeals to functional programmers for its expressiveness and good cost model via compilation to a decision tree, but certain computations can only be expressed verbosely using pattern matching primitives. The problem can be solved by extensions, but these are not standardized, and no single popular programming language contains all the extensions to pattern matching. By contrast, equations in Verse are both expressive and succinct, with no obvious need for extensions; however, Verse’s cost model is a challenge. To resolve these problems, I propose a new language, 𝑉 −, which uses Verse’s equations with some restrictions. I show that 𝑉 – subsumes 𝑃+, a core language with three popular extensions to pattern matching. I also show that 𝑉 − can be compiled to a decision tree.

Research areas: Programming Languages, compilers, language implementation.