kagamihogeの日記

kagamihogeの日記です。

JEP 305: Pattern Matchingをテキトーに訳した

http://openjdk.java.net/jeps/305 をテキトーに訳した。

JEP 305: Pattern Matching

Author   Brian Goetz
Owner   Gavin Bierman
Created 2017/05/30 19:48
Updated 2017/06/16 16:25
Type    Feature
Status  Candidate
Component   specification/language
Scope   SE
Discussion  amber dash dev at openjdk dot java dot net
Priority    3
Reviewed by Mark Reinhold
Issue   8181287

Summary

Java言語をパターンマッチング(pattern matching)による機能強化を行います。初回のサポートは、switchステートメントmatches式による、型テスト(type-test)と定数パターン(constant patterns)になります。パターンの適用範囲と言語でパターンマッチングをサポートする要素の拡張は、以降の開発で行います。

Motivation

おおむね大半の言語は、ある式が特定の型や構造を持つことのテストと組みわせる一連のロジックがあり、その次に、以降の処理で使うために状態のコンポーネントを条件付きで展開します。たとえば、Javaではinstanceof-and-castイディオムが良く知られています。

if (obj instanceof Integer) {
    int intValue = ((Integer) obj).intValue();
    // use intValue
}

ここには三種類の処理があります。test(xはIntegerである)、conversion(objをintegerにキャスト)、destructuring(IntgerからintValueコンポーネントを抽出)。このパターンは単純でありJavaプログラマには馴染み深いものですが、最適とは言い難い理由がいくつかあります。まず冗長さで、型テストとキャストはやることが被っています(instanceofしたあと他に何をやるというのだろうか?)。キャストとdestructuringという突然現れるボイラープレートにより、それに続く重要なロジックが見辛くなります。しかし最も甚大なのは、ポイラープレートの繰り返しがプログラムにエラーを気付かれないまま紛れ込ませる可能性がある点です。

複数のターゲット型がありうる場合をテストする場合にこの問題は更に悪化します。上述の例をif...elseテストチェーンに書き加えます。

String formatted = "unknown";
if (obj instanceof Integer) {
    int i = (Integer) obj;
    formatted = String.format("int %d", i);
}
else if (obj instanceof Byte) {
    byte b = (Byte) obj;
    formatted = String.format("byte %d", b);
}
else if (obj instanceof Long) {
    long l = (Long) obj;
    formatted = String.format("long %d", l);
}
else if (obj instanceof Double) {
    double d = (Double) obj;
    formatted = String.format(“double %f", d);
}
else if (obj instanceof String) {
    String s = (String) obj;
    formatted = String.format("String %s", s);
}

上のコードは見慣れたものですが、多数のよろしくない要素が含まれています。既に述べたように、こうした繰り返しコードはプログラマを苛立たせます。また、ビジネスロジックはポイラープレートの中にたやすく埋もれてしまいます。しかしより重要なのは、このやり方はコーディングエラーを残したままにしてしまう点で、その理由は過剰な制御構造になっているためです。上のコードの意図は、if...elseチェーンの各箇所でformatted変数に何らかの値を代入することです。しかし、ここで実際に発生することをコンパイラで検証可能にする術がありません。もし、あるブロックが、実際上滅多に実行されないブロックだとして、formattedへの代入を忘れているとバグになります(blank localもしくはblank finalでformattedにしておけば少なくとも"definite assignment"分析には入れられますが*1、常に行われるわけではありません)。最後に、上のコードは最適化の余地が限られており、absent compiler heroics,*2 基底のプログラムはおおむねO(1)なのに、O(n)の複雑さを抱えています。

Description

アドホックな解決策に頼るより、Javaにもパターンマッチング(pattern matching)を入れる時が来たと我々は判断しています。パターンマッチングは1960sにさかのぼる事プログラミング言語でさまざまな異なるスタイルに適用されてきた技術で、SNOBOL4とAWKなどのテキスト指向言語、HaskellとMLなどの関数型言語、最近ではScalaC#などのオブジェクト指向言語にも拡張されています。

パターン(pattern)とはターゲットに適用可能な述語(predicate)の組み合わせです。述語はバインド変数(binding variables)と共に使用し、もし述語が適用される場合はターゲットから抽出されたものがバインド変数になります。バインディングパターンの形の一つは型テスト(type test)パターンで、以下のようなものです(matches演算子は概念的なものです)。

if (x matches Integer i) {
    // can use i here
}

Integer iというフレーズが型テストパターンです。iは新規の変数宣言で、宣言済みの変数ではありません。ターゲットはIntegerインスタンスかどうかテストされ、次に、Integerにキャストされてバインド変数iintコンポーネントがバインドされます。

先に触れたように、if...elseの連続は過度に制御構造を多用しているので望ましくありません。Javaには既にswitchというmulti-armed*3な等価テストの機構があります。しかしswitchは(今のところは)極めて限定的なものです。ごく少数の型、numbers, strings, enums、のみswitch可能で、さらに、定数に対する等価性しかテスト出来ません。とはいえこれら制限はおおむね歴史的経緯なだけであり、switchステートメントはパターンマッチングにパーフェクトに"マッチ"します*4。もしcaseラベルでパターンを指定可能になれば、switchで上述の例を以下のように書けるようになります。

String formatted;
switch (obj) {
    case Integer i: formatted = String.format("int %d", i); break;
    case Byte b:    formatted = String.format("byte %d", b); break;
    case Long l:    formatted = String.format("long %d", l); break;
    case Double d:  formatted = String.format(“double %f", d); break;
    case String s:  formatted = String.format("String %s", s); break
    default:        formatted = obj.toString();
}

これにより、正しく制御構造を使用するようになったため、コードの意図がかなり明瞭になります。つまり、"式objは以下の条件のうち少なくとも一つにマッチし、マッチした行を実行する"という意図を示しています。加えて、最適化可能性も良くなり、この例の場合はO(1)でディスパッチ可能となる可能性が高いです。

従来のcaseラベル(コンパイル時の定数、数値・Stringenum、との比較)は、両者がObject.equals()で等価の場合にターゲットが定数パターンにマッチするという点で、定数パターン(constant patterns)と言えます。なお、マッチした定数パターンは何もバインディングしません。

初回の機能拡張では、定数パターン、switchステートメントでのバインディングmatches式による型テストパターン、のサポートを目的とします。ガード(マッチするにはtrueにならなければならない補助的なboolean式、たとえばcase String s && !s.isEmpty()と、switch内のcontinueステートメント、の両方あるいは片方)をサポートする可能性もあります。

Future Work

型テストパターンとswitchのパターンは最初の一歩に過ぎませんが、それでも明らかに第一歩です。将来的な取り組みの対象となりうる領域(JEPのターゲットになる)には以下があります。

Deconstruction Patterns. クラスには単にデータを保持するものが多くあります。コンストラクタで生成し、その際にN個の引数を取り集約を生成しますが、基本的にはアクセサで一度に一つのコンポーネントをフェッチします。 型テスト-キャスト-バインドの操作と一つの型テストパターンを組み合わせられるので、型テスト-キャスト-複数抽出と一つのdeconstruction patternを組み合わせられます。いま、Nodeの型階層があり、そのサブタイプに、IntNode(単一のintを持つ)、AddNodeMulNode(二つのnodeを持つ)、NegNode(単一のnodeを持つ)があるとすると、Nodeに対するマッチをして特定のサブタイプにおける挙動をすべてワンステップに収められます。

int eval(Node n) {
    switch(n) {
        case IntNode(int i): return i;
        case NegNode(Node n): return -eval(n);
        case AddNode(Node left, Node right): return eval(left) + eval(right);
        case MulNode(Node left, Node right): return eval(left) * eval(right);
        default: throw new IllegalStateException(n);
    };
}

現状、上記のようなアドホックポリモーフィックな計算を表現するには、"Visitor"パターンを使います。パターンマッチングを使うことで、より透過的で単純な理解しやすいものになります。

Nested Patterns. 上の例で既にnested patternを使用しており、deconstruction patternsの"引数"である、Node nなどは、既にこれ自身がパターン(この場合は型テストパターン)です。いま、左側がゼロのIntNodeAddNodeとマッチさせたい場合、もう一段階ネストを追加します。

case AddNode(IntNode(0), Node right)

上の例では、deconstruction pattern(AddNode(...))で左側のコンポーネントが更に別のeconstruction pattern(IntNode(...))にマッチし、このパターンの内側では一つのコンポーネントが定数パターン0にマッチします。

Expression switch. switch statementは今のところステートメントですが、結果を処理して続行したい場合、いくつかのやり方から選ぶことになります。*5switchを式にも出来るようにすることでswitchステートメントで式のようなことを実現せざるを得ない歪みを矯正します。

Sealed types. switchのcaseが網羅的であると事前に分かっていることは有用です。つまり、基本的な状況下では決して実行されないdefaultを書く必要が無い、ということです。階層構造に網羅性を組み込めるのであればクライアントに対し有益な制約を示すことになり、コンパイラの網羅性分析の助けになります。

Alternatives

型テストパターン(deconstruction patternsでは無い)はifswitchステートメントもしくはtype switchflow typingによっても実現できます。パターンはこれら制御構造を汎用化するものです。

Dependencies

実装にはおそらくDynamic Constants in the JVMを使用します。(https://bugs.openjdk.java.net/browse/JDK-8177279).

*1:“definite assignment” analysis in this effortが原文。日本語での表現が良くわからんかったので、うまく訳に自信が無い。

*2:よくわからん

*3:日本語でなんていうか分からんけど、このすぐ下のswitch caseの例のように並列にcaseが並んでる様を「多腕」と表現しているのだろう

*4: perfect “match” for pattern matching.が原文で、意図的にmatchを二回出してると思われ、いわゆるダジャレの匂いがする。

*5:The switch statement is currently a statement, but very often when we are choosing between several alternatives, we want to populate a result and keep going.が原文。うまく訳せない