Scribble at 2024-10-21 08:38:27 Last modified: 2024-10-21 09:11:43
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.
従来の条件文という制御構造に制約なり、あるいは使い辛いと感じることがあるのは確かなんだよね。論文でも列挙されているように、(1) 一度に一つのアイテムしかマッチングできない、(2) パターンの一部を同じパターンの別の部分に依存させることができない、(3) パターンと計算を交互に実行することができない、という制約があるから、これらを解決するには条件文をネストさせる必要がある。そこで、この論文では、(1) 同じ条件内で複数のアイテムを連続してパターンマッチングできるとか、(2) パターンと計算を交互に実行できるとか、(3) 条件分岐を任意の場所で分割できる条件文のシンタクスを考案したという。
でも、それで本当に解決するのはなんだろうか。結局、アルゴリズムが同じである以上は、プログラムが実行する内容は同じはずである。したがって、ここでの問題はプログラマという作業者の可読性だけではないのか。つまり、コーディングの際にアルゴリズムという抽象的なアイデアを一定のシンタクスに従いつつソースコードへ instantiation する場合に混乱しないようにするとか、誰かのソースコードを読解するときに誤解しないようにするといったことだ。すると、僕にはこの論文が提唱している「新しい条件文」で、この手の問題が解決するとは思えない。逆に、複数の条件判断を集約することで、見た目はシンプルになるかもしれないが、逆にそこで実現しているアルゴリズムがどうなっているのかは分かりにくくなるような気がする。一つ一つの building block を個々のルーチンとしてネストさせてまで書き分けているからこそ、或るていどの可読性が保たれているのではなかろうか。つまり、僕には「プログラムの中にプログラムを埋め込む」ようなアイデアは、あまり良いとは思えないわけである。僕が、素晴らしい技巧だとは思って感心することが多いけれど、たとえば正規表現やクロージャの複雑な処理表現をあまり好まないのは、そういう理由がある。そもそも、僕は大学院で科学哲学の学生としてロジック（数理論理学、集合論、モデル理論などの総称）も少しは齧ったけれど、やはりラムダ関数のところは難しいと感じた。