C++でパターンマッチ欲しい
パターンマッチの良さとかに関する日記書いてるつもりが、いつの間にかC++の話がメインになっていたでござる。
パターンマッチについては http://togetter.com/li/6990 http://togetter.com/li/216989 あたりを参照のこと。
サンプルとして、整数と変数と足し算と掛け算から成る式を考え、その表示と分配法則による変換をします。
式 ::= 整数 | 変数 | 式+式 | 式*式
これの、OCaml(+パターンマッチ)とC++のそれぞれでの実装例を示し、
パターンマッチで解決したい問題や利点などをつらつらと。
ここに使われている例題のC++実装は、オブジェクト指向としては中途半端で微妙ではあります。
継承を使うなどの選択肢も考えましたが、本質的には問題は解決しない気がしています。
解決するような設計があれば教えてください、使いたいです(切実
複数のオブジェクトの内部構造に同時に関わる処理(distribute関数参照)を行う必要があるので、
継承やカプセル化を使って整理できるのは1つのオブジェクトに関する処理だけで、
その他のオブジェクトに関しては依然として今回の例のように外側からifなどで条件分岐するアクセスが必要になってくるのだと思います。
(継続スタイルでごにょごにょやればできることもあると思いますが、書きにくい…)
OCaml+パターンマッチによる実装例
type op = (* 演算子; とりあえず + と * のみ *) | Add (* + *) | Mul (* * *) let print_op o = match o with | Add -> print_string "+" | Mul -> print_string "*" type expr = (* 式 *) | BinOp of op * expr * expr (* 二項演算 *) | Var of string (* 変数 *) | Int of int (* 整数 *) (* 式の表示 *) let rec print_expr e = match e with | BinOp (o,e1,e2) -> print_string "("; print_expr e1; print_op o; print_expr e2; print_string ")" | Var v -> print_string v | Int i -> print_int i (* 式の分配法則による変換; 簡単のために、単純なケースのみ *) let rec distribute e = match e with | BinOp(Mul, BinOp(Add,a,b), c) (* (a+b)*c を (a*c)+(b*c)に変換する *) -> BinOp(Add, BinOp(Mul,a,c), BinOp(Mul,b,c)) | _ -> e ;; let e = BinOp(Mul, BinOp (Add, Int 1, Var "a"), Int 3) in (* (1+a)*3 *) print_expr e; print_newline (); print_expr (distribute e); print_newline ();
実行結果:
$ ocaml expr.ml ((1+a)*3) ((1*3)+(a*3))
C++による実装例
注: メモリリークしてます(Exprオブジェクトがdeleteされない)がそこは本質的ではないのでとりあえずスルーしてください。
#include <stdio.h> enum OP{ OP_ADD, // + OP_MUL, // * }; void print_op(enum OP o) { if( o == OP_ADD ){ printf( "+" ); } else if( o == OP_MUL ){ printf( "*" ); } } class Expr{ public: void print_expr() const{ if( isBinOp() ){ // 検査 printf( "(" ); getExpr1()->print_expr(); // アクセス print_op(getOp()); // アクセス getExpr2()->print_expr(); // アクセス printf( ")" ); } else if( isVar() ){ // 検査 printf( "%s", getVar() ); // アクセス } else if( isInt() ){ // 検査 printf( "%d", getInt() ); // アクセス } } const Expr *distribute() const{ // (a+b)*c を (a*c)+(b*c)に変換する if( isBinOp() && getOp() == OP_MUL && getExpr1()->isBinOp() && getExpr1()->getOp() == OP_ADD ){ Expr *a = getExpr1()->getExpr1(); Expr *b = getExpr1()->getExpr2(); Expr *c = getExpr2(); return createBinOp( OP_ADD, createBinOp(OP_MUL,a,c), createBinOp(OP_MUL,b,c) ); } else return this; } bool isBinOp() const { return typ == EXPR_BINOP; } enum OP getOp() const { return o; } Expr *getExpr1() const { return e1; } Expr *getExpr2() const { return e2; } bool isVar() const { return typ == EXPR_VAR; } const char *getVar() const { return var; } bool isInt() const { return typ == EXPR_INT; } int getInt() const { return i; } static Expr *createBinOp(enum OP o, Expr *e1, Expr *e2){ Expr *e = new Expr(); e->typ = EXPR_BINOP; e->o = o; e->e1 = e1; e->e2 = e2; return e; } static Expr *createInt(int i){ Expr *e = new Expr(); e->typ = EXPR_INT; e->i = i; return e; } static Expr *createVar(const char *var){ Expr *e = new Expr(); e->typ = EXPR_VAR; e->var = var; return e; } private: enum{ EXPR_BINOP, EXPR_VAR, EXPR_INT } typ; enum OP o; // 演算子; EXPR_BINOP用 Expr *e1, *e2; // EXPR_BINOP用 const char *var; // 変数; EXPR_VAR用 int i; // 整数; EXPR_INT用 }; int main() { Expr *e = // (1+a)*3 Expr::createBinOp( OP_MUL, Expr::createBinOp( OP_ADD, Expr::createInt(1), Expr::createVar("a") ), Expr::createInt(3) ); e->print_expr(); printf( "\n" ); e->distribute()->print_expr(); printf( "\n" ); return 0; }
実行結果:
$ g++ -o expr -Wall -Wextra expr.cpp $ ./expr ((1+a)*3) ((1*3)+(a*3))
検査とアクセスと変数スコープを一つに
まず、どうにかしたいのは、@kinabaさんの表現を借りると「検査とアクセス」の二つがC++版では分離していること。
一部抜粋すると、
void print_expr() const{ if( isBinOp() ){ // 検査 printf( "(" ); getExpr1()->print_expr(); // アクセス print_op(getOp()); // アクセス getExpr2()->print_expr(); // アクセス printf( ")" ); }
こんな感じで、isBinOp()で式が二項演算かどうか検査した後、その二項演算の各部分へのアクセスをgetExpr1()などで行っています。
問題としては、isBinOp()がfalseの場合でも(あるいは検査しなくても問答無用で)getExpr1()にアクセスできてしまうので、安全ではありません。
解決策の一つとして、検査とアクセスの両方を行う一つの関数を作ることがあります。
class Expr{ public: void print_expr() const{ Expr *e1, *e2; // 部分情報を格納するための変数宣言 enum OP o; const char *var; int i; if( isBinOp(&o,&e1,&e2) ){ // 検査+アクセス printf( "(" ); e1->print_expr(); print_op(o); e2->print_expr(); printf( ")" ); } else if( isVar(&var) ){ // 検査+アクセス printf( "%s", var ); } else if( isInt(&i) ){ // 検査+アクセス printf( "%d", i ); } } const Expr *distribute() const{ // (a+b)*c を (a*c)+(b*c)に変換する Expr *a, *b, *c, *e; enum OP o, o2; if( isBinOp(&o,&e,&c) && o == OP_MUL && e->isBinOp(&o2,&a,&b) && o2 == OP_ADD ){ return createBinOp( OP_ADD, createBinOp(OP_MUL,a,c), createBinOp(OP_MUL,b,c) ); } else return this; } bool isBinOp(enum OP *o, Expr **e1, Expr **e2) const { if( typ == EXPR_BINOP ){ *o = this->o; *e1 = this->e1; *e2 = this->e2; return true; } else return false; } bool isVar(const char **var) const { if( typ == EXPR_VAR ){ *var = this->var; return true; } else return false; } bool isInt(int *i) const { if( typ == EXPR_INT ){ *i = this->i; return true; } else return false; } // 後は同じ
isBinOpなどが成功した時には、渡したポインタ経由で各部分の情報も一緒に取ることができます。
これなら、不正なアクセスはできません。isBinOpが成功した時だけ、部分式の情報が得られます。
distributeのような、複数段/複数オブジェクトに渡る構造マッチングのコードも、少し見やすくなった気がします。
しかし、これでもまだ完全にきれいではありません。
- 「部分情報を格納するための変数宣言」と「検査+アクセス」が別。
- やはり、isBinOpなどを自分で書かないといけない
スコープの問題については、
void print_expr() const{ ... else if( const char *var = isVar() ){ // 検査+アクセス printf( "%s", var ); } ... } const char *isVar() const { if( typ == EXPR_VAR ) return this->var; else return NULL; }
みたいにすると回避できることもありますが、これは bool にすると false になる値を元のgetVar()が返さないことが前提です。
なので、このままではたとえば isInt() には適用できません。
何らかのwrapper classを返すことも考えられますが、以下に示すように1段分変換が必要であるような気がします。
class IntWrapper{ public: IntWrapper() : valid(false), i(0){} IntWrapper(int v) : valid(true), i(v){} operator bool() const { return valid; } int getValue() const { return i; } private: bool valid; int i; }; ... class Expr{ ... void print_expr() const{ ... else if( IntWrapper intWrapper = isInt() ){ printf( "%d", intWrapper.getValue() ); } ... } IntWrapper isInt() const { if( typ == EXPR_INT ) return IntWrapper(this->i); else return IntWrapper(); }
暗黙にIntWrapperを本来の値、この場合はintにキャストする演算子を定義することで変換を省く方法もあるかもですが、
その場合 bool へのキャスト演算子と衝突を起こすので使わない方がいいと思います。
(うっかり if( intWrapper.getValue() != 0 ) のつもりで if( intWrapper ) と書いてしまうと…)
OCamlのパターンマッチだと、
- 検査とアクセスを一つにすることによる安全性
- アクセスした結果の変数スコープが、検査結果の条件が成立するスコープと一致
- (わざわざ検査+アクセスメソッドとか書かなくてもOK)
ということが実現されます。
(* 式の表示 *) let rec print_expr e = match e with | BinOp (o,e1,e2) -> print_string "("; print_expr e1; print_op o; print_expr e2; print_string ")" | Var v -> print_string v | Int i -> print_int i
BinOp(o,e1,e2) の部分で、eがBinOpであるかの検査が行われ、成功したら部分構造がo,e1,e2の変数に入ります。
o,e1,e2の変数宣言も一緒にやっているようなもので、これらの変数はこの検査が成功した部分(同じ行の->右側部分)からのみアクセスできます。
分岐ケース記述漏れチェックが強力
OCamlのVariant型との組み合わせとかだと、全ての場合をカバーできているかの検査をコンパイラがやってくれます。
C++版で、isBinOpかisVarかisIntかのどれかがtrueになる、というのは設計意図としてはありますが、コンパイラはチェックしてくれません。
int foo() const{ if( isBinOp() ) return 0; else if( isVar() ) return 1; else if( isInt() ) return 2; // 設計上ではここに到達しないはずだけど、コンパイラにはそれが分からんのです // -> return必要だよ♪値返してね♪って言ってくる }
なので、こういう風に書くこともあるのではないでしょうか。しかし気持ち悪いです…
int foo() const{ if( isBinOp() ) return 0; else if( isVar() ) return 1; else if( isInt() ) return 2; assert(false); return -1; // 適当な値 }
あるいは
int foo() const{ if( isBinOp() ) return 0; else if( isVar() ) return 1; else /* if( isInt() ) */ return 2; }
また、例えば新しく1項演算式(例: ~1)を表すUnaryOpを追加して、isUnaryOp()の検査を追加する場合、追加し忘れてもコンパイラはあまり文句を言ってくれません。
(上のようにassert突っ込んでおけば実行時に落ちてはくれますが…)
OCamlだと、たとえば print_expr で Int に関するパターンマッチを抜かすと:
(* 式の表示 *) let rec print_expr e = match e with | BinOp (o,e1,e2) -> print_string "("; print_expr e1; print_op o; print_expr e2; print_string ")" | Var v -> print_string v (* Int i のパターンマッチを削除 *)
ちゃんとコンパイル時にWarningを上げてくれて、どのケースが抜けているかまで教えてくれます:
Warning 8: this pattern-matching is not exhaustive. Here is an example of a value that is not matched: Int _
これを利用すると、UnaryOp を追加 → コンパイル → Warningの列が出るので片っ端からUnaryOpに関するマッチを追加 → 設計変更完了!
ということができます。
(catch-allのマッチ書いてあるとひっかからないですが…)
C++だと、enumの値でswitchすると、case書き忘れはコンパイル時にwarning出してくれますが、
イカのように全部網羅しても warning: control reaches end of non-void function って出ますね…
int bar(enum OP o) { switch(o){ case OP_ADD: case OP_MUL: return 0; } }
その他パターンマッチの利点
強力な構造検査
複数段に渡る構造マッチングとか簡潔に書きたい。これは2段ですが、もっと深くなると更に強力に。
| BinOp(Mul, BinOp(Add,a,b), c) (* (a+b)*c を (a*c)+(b*c)に変換する *) -> BinOp(Add, BinOp(Mul,a,c), BinOp(Mul,b,c))
「値の構築とデータの取り出し」の構文が似ている
@kinabaさん哲学その2。
| BinOp (o,e1,e2) -> ... (* 検査+アクセス *) let e = BinOp(Mul, BinOp (Add, Int 1, Var "a"), Int 3) in (* 構築 *)
if( isBinOp(&o,&e1,&e2) ){ // 検査+アクセス Expr::createBinOp(OP_MUL, Expr::createBinOp(OP_ADD, Expr::createInt(1), Expr::createVar("a")),Expr::createInt(3)); // 構築
まぁこういうことです。
構文が似ていると、変換前(取り出し構文で記述)と変換後(構築構文で記述)の比較がしやすいです。
| BinOp(Mul, BinOp(Add,a,b), c) (* 変換前 *) -> BinOp(Add, BinOp(Mul,a,c), BinOp(Mul,b,c)) (* 変換後 *)
まとめ
- 安全
- 検査とアクセスを一度に行うことで、検査せずにアクセスすることを防ぐ
- アクセスした結果が格納される変数のスコープが、検査成功が成立するスコープと一致するので、検査が成功しなかった場合にはアクセス結果の変数が見えない
- 強力
- 複数段に渡る構造のマッチングとかできます
- 分岐ケース記述漏れチェックが強力です
- 読みやすい
- 構築とアクセスの構文が似ているのでプログラマが読み書きしやすいです
- 楽
- 言語built-inだとわざわざ検査+アクセスメソッドとか自分で書かなくてもOK
