このまえ何とか実験でOCamlを使ってコンパイラやインタプリタを実装したので、それを真似てPerl6で似たようなことをやってみようと思います。
実験ではパーザによってヴァリアント型に落とし込まれた命令列をパターンマッチによって分解しながら実行していくという方針だったのですが、Perl6にはヴァリアント型のようなデータ構造も、パターンマッチもありません。しかし、「似たような」という程度のレベルなら実現する方法がありますので、今回はそれを紹介したいと思います。
代数的データ構造
おそらくPerl6のような型のゆるい言語では、OCamlのヴァリアント型のような構造を格好良くバラすというのは難しいと思います。Perl6的にはおそらくRoleを使って実現するとスマートなのでしょうが、今回は話を簡単にするため、リストを使うことにします。
パターンマッチ
私の理解では、パターンマッチというのは
- 構造によって処理を分岐しつつ
- 構造をバラし、部分ごとに変数に束縛する
という操作です。前述のとおり、今回考える構造はリストだけなので、こいつを上手いことバラしつつ変数に束縛するというのが目標になります。網羅性チェックについては、まぁどう考えても無理なので気にしないことにしましょう。無理なものは無理。
とりあえず今回あつかう対象として次のようなリストを考えます。
[Plus, [Literal, 1], [Minus, [Literal, 2], [Plus, [Literal, 3], [Literal, 4]]]]
ヴァリアント型のデータ構成子に相当するものが無いので、ここでは型オブジェクトで代用することにします。Plusは足し算、Minusは引き算、Literalは評価すると値を返すリテラルを示す命令だと考えてください。
つまり、この式はポーランド記法で(+ 1 (- 2 (+ 3 4)))に相当する式になります。これを評価して正しく-4が計算できるような関数evaluateを考えて行きましょう。
どうやるとスマートか
今までずらずらと書いてきましたが、ようやくここが今日の本題です。
リストの先頭の要素をチェックして大量に分岐するのもいいですが、これも命令の種類が増えてくると破綻が見えてきます。どうするとイイカンジに捌けるようになるのでしょうか。
結論から言うと、関数のmultiple dispatchを使います。これは関数オーバーロードのような機能で、(オーバーロードとは違い)実行時にシグネチャにマッチする実装を呼び分ける機能です。一般的には引数の型や個数を見て処理を分岐するのに用いるのですが、実はmulti宣言された関数のシグネチャにリストを書くと、リストの構造によっても呼び分けることが出来たりします。
具体的に今回の場合について考えると、以下の様なディスパッチを作ることで、命令別に処理を分けることができるようになります。
multi sub evaluate ([Plus, $e1, $e2]) { ... } # 足し算
multi sub evaluate ([Minus, $e1, $e2]) { ... } # 引き算
multi sub evaluate ([Literal, $l]) { ... } # リテラル
multi sub evaluate (*@_) { ... } # 実装されていない命令
これを踏まえて、足し算と引き算を評価できるように実際の処理を書いてみましょう。
use v6;
class Plus {}; #足し算命令
class Minus {}; #引き算命令
class Literal{}; #リテラル命令
multi sub evaluate ([Plus, $e1, $e2]) {
my ($v1, $v2) = ((evaluate $e1), (evaluate $e2));
return $v1 + $v2;
}
multi sub evaluate ([Minus, $e1, $e2]) {
my ($v1, $v2) = ((evaluate $e1), (evaluate $e2));
return $v1 - $v2;
}
multi sub evaluate ([Literal, $l]) {
return $l;
}
multi sub evaluate (*@_) {
fail "Unknown instruction " ~ @_.perl;
}
引数に与えられた式を再帰的に評価して、帰ってきた値を足したり引いたりして式の値を計算します。非常に単純ですね。*@_は全ての引数をリストとして@_に格納するという記述なので、_のように全てにマッチするパターンとして用いています。命令に対する引数の数がおかしかったり、実装されてない命令が見つかると、最後のディスパッチが呼ばれてエラーを吐きだします。
実際に実行した結果を以下に示します。
say evaluate [Plus, [Literal, 1], [Minus, [Literal, 2], [Plus, [Literal, 3], [Literal, 4]]]];
say evaluate [Plus, [Literal, 1], [Literal, 2], [Literal, 3]]; #不正な引数
% perl6 simple.pl
-4
Unknown instruction Array.new([Plus, [Literal, 1], [Literal, 2], [Literal, 3]])
in method gist at src/gen/CORE.setting:10149
in sub say at src/gen/CORE.setting:7460
in block at simple.pl:28
イイカンジに計算できていますね。
まとめ
今回はmultiple dispatchを使ってリストを分解する手法を紹介しましたので、次回からはもう少し機能を増やして行きましょう。値に型をつけたり、roleを用いて更にイイカンジに命令を定義できるようにしたりします。あと3,4回くらいで簡単なインタプリタが完成すると思いますので、気長にお付き合いください。