Emacsのorg-modeで文書を書いていると、ふと図を差し込みたくなることがある。
図と言ってもいろいろあるが、いくつかの図はテキストで書けるものだ。たとえばGraphvizのdotというツールを使えばグラフ構造をdigraph{A->B; A->C; B->C;}といったテキストで書ける。ditaaというツールを使えば簡単なダイアグラムをアスキーアートで書ける。PlantUMLではUMLをテキストで書ける。テキストで書いた「図」はそれらのツールによって画像に変換できる。
org-modeにはそれらテキストで書いた図を混ぜ込んだ文書を適切に変換して出力してくれる機能がある。それを使えばテキストエディタの中だけで、ちょっとした図を含む文書が書けてしまう。
なので今日はその機能の使い方を勉強しながら、試しにその機能を利用した文書を書いてみた。
なんか最近どんどん考えるのが億劫になって、嫌になっちゃうんだけど、たまにちゃんと考えてちゃんと答えが出ると、まだまだ見捨てられていないなと思う。
そんな日はちょっと嬉しくなっちゃうね。
まあ、長続きはしないんだけどさ。
ブラウザ一本で手軽に画像を生成したければhttp://sketch.processing.orgへ行けば良い。
C++でプログラミング言語の構文木を表現する方法はそれこそ星の数ほどあると思われる。その中で自分の用途ではどのようなものが適しているのかしばしば考えることがある。
例えば単純な式を表す構文を考えよう。
<expr> ::= <add_expr>
<add_expr> ::= <mul_expr>
| <add_expr> "+" <mul_expr>
| <add_expr> "-" <mul_expr>
<mul_expr> ::= <primary_expr>
| <mul_expr> "*" <primary_expr>
| <mul_expr> "/" <primary_expr>
<primary_expr> ::= "(" <expr> ")"
| <integer_literal>
| <float_literal>
登場するのは+-*/の二項演算子、整数リテラル、浮動小数点数リテラルといった要素だ。これらの要素が抽象構文木のノードとなる。それぞれプログラム上ではBinOp、IntLit、FloatLitと書くことにする。
C++で一番素直な方法と言ったら、やはり継承を使うことだと思う。
struct Location { int line, column; Location(int line, int column) : line(line), column(column){} }; struct Expr { Location loc; Expr(const Location &loc) : loc(loc){} virtual ~Expr(){} }; typedef boost::shared_ptr<Expr> ExprPtr; struct BinOp : Expr { enum OpType { OP_ADD, OP_SUB, OP_MUL, OP_DIV}; OpType op; ExprPtr lhs; ExprPtr rhs; BinOp(OpType op, ExprPtr lhs, ExprPtr rhs, const Location &loc) : Expr(loc), op(op), lhs(lhs), rhs(rhs) {} }; struct IntLit : Expr { int value; IntLit(int value, const Location &loc) : Expr(loc), value(value) {} }; struct FloatLit : Expr { double value; FloatLit(double value, const Location &loc) : Expr(loc), value(value) {} };
コードに対する補足説明:
上のコードは式の基底クラスであるExprと、その派生クラスであるBinOp、IntLit、FloatLitを定義している。
素直なC++のコードだが、次の点が気になる。
一つ目の問題はコードの重複を気にするものだが、あまり良い方法は見当たらないのでひとまず置いておく。C++で継承をするとよくこの問題にぶつかる。マクロを使ったり、Exprを直接引数にとったり、包み込む別のクラスを作ってlocをそちらへ移動したり、初期化リストで初期化するのを諦めたり、独自のプリプロセスを行ったり、いくつか手は考えられるのだが、それぞれ良い面と悪い面がある。
二つ目の問題は実際に構文木を構築した後、どのように使うのかということだ。プログラムで構文木の各ノードを一つ一つ見て処理をしていく場合に、どうやって各ノードの種類を判別し、適切な処理を起動するのか。
例えば各ノードを訪問してテキスト出力するようなプログラムは次のようになる。
void print(const ExprPtr &expr) { if(const BinOp *binop = dynamic_cast<const BinOp *>(expr.get())){ std::cout << "BinOp(" << binop->op << 'n'; print(binop->lhs); print(binop->rhs); std::cout << ")n"; } else if(const IntLit *intlit = dynamic_cast<const IntLit *>(expr.get())){ std::cout << "IntLit(" << intlit->value << ")n"; } else if(const FloatLit *floatlit = dynamic_cast<const FloatLit *>(expr.get())){ std::cout << "FloatLit(" << floatlit->value << ")n"; } else{ throw std::runtime_error("Unknown Expr"); } } template<typename T> ExprPtr new_sp(const T &v) { return ExprPtr(new T(v));} int main() { // (123 + 234) * 1.25 ExprPtr expr = new_sp(BinOp( BinOp::OP_MUL, new_sp(BinOp( BinOp::OP_ADD, new_sp(IntLit(123, Location(1,2))), new_sp(IntLit(234, Location(1,8))), Location(1,6))), new_sp(FloatLit(1.25, Location(1,15))), Location(1,13))); print(expr); }
この方法ではdynamic_castを使用して基底クラスから派生クラスの種類を求めている。様々あるやり方の中では素直な方だし、見た目的にもシンプルで、決して悪い方法とは言えないだろう。ただ、問題があることも確かである。上から順にif文でテストしていくので線形探索相当になる。新しい派生クラスを追加したときにif文を追加し忘れるという問題もある。ディスパッチ処理(dynamic_castによる判別)と呼ばれる処理(テキスト出力)が一緒くたになっているのも気になるが、その気になればテンプレートを使って分離できるのでそれはさほど問題ではない。
この手の問題への解決方法にはVisitorパターンというものがよく知られている。どんな感じになるのかはWikipediaにC++の例が載っているので、見れば分かると思う。
C++で実装する典型的なVisitorパターンにはいくつか欠点があるように思う。
派生クラスの判別をどのように行うか。派生クラス自身に尋ねれば良い。この方法によって、典型的なVisitorパターンのいくつかの欠点は解決するが、また別の欠点が現れてくる。
struct Expr { //略 virtual int get_tag() const = 0; }; struct BinOp : Expr { //略 virtual int get_tag() const { return 0;} }; struct IntLit : Expr { //略 virtual int get_tag() const { return 1;} }; struct FloatLit : Expr { //略 virtual int get_tag() const { return 2;} };
訪問は次のように行う。
template<typename Result, typename Func> Result visit(Func f, const ExprPtr &expr) { switch(expr->get_tag()){ case 0: return f(boost::static_pointer_cast<BinOp>(expr)); case 1: return f(boost::static_pointer_cast<IntLit>(expr)); case 2: return f(boost::static_pointer_cast<FloatLit>(expr)); default: throw std::runtime_error("Unknown Expr"); } } struct Printer { void operator()(const ExprPtr &expr) const { visit<void>(*this, expr); } void operator()(const boost::shared_ptr<BinOp> &binop) const { std::cout << "BinOp" << std::endl; (*this)(binop->lhs); //略 } void operator()(const boost::shared_ptr<IntLit> &intlit) const { std::cout << "IntLit " << intlit->value << std::endl; } void operator()(const boost::shared_ptr<FloatLit> &floatlit) const { std::cout << "FloatLit " << floatlit->value << std::endl; } }; Printer()(expr);
すべての派生クラスにget_tag関数を仕込む手間が生じるという点で少しだけ侵入的であるが、ディスパッチ処理自体は継承ツリーの中に侵入していないので、いくらか柔軟性があると思う。
最大の欠点は0、1、2というget_tagが返す値(派生クラスの識別子)を正しく維持しなければならない点だろう。新しい派生クラスが追加されることを考えると、ある程度自動的に識別子を設定して欲しい。
少し考えただけでも次のような方法が思い浮かぶ。
次のような型リストを作っておけば、
typedef boost::mpl::list< BinOp, IntLit, FloatLit > Types;
次のようなコードで型がリストの中で何番目かをコンパイル時定数で得ることが出来る。
boost::mpl::index_of<Types, IntLit>::type::value //== 1になる。
つまり、例えばIntLit::get_tagは次のように実装できることになる。
struct IntLit : Expr { //略 int get_tag() const { return boost::mpl::index_of<Types, IntLit>::type::value;} //Typesの中で何番目かを返す。 };
もちろんこんなのを派生クラス毎にいちいち書いていられない。
マクロを使って
struct IntLit : Expr { //略 GET_TAG_IMPL(IntLit); };
のように書くようにする手もあるが、少し見苦しい。
struct IntLit : DerivedImpl<IntLit, Expr> { //略 };
くらいにしたいところなので、
template<typename Derived, typename Base> struct DerivedImpl : Base { // コンストラクタ DerivedImpl() : Base(){} template<typename A0> DerivedImpl(const A0 &a0) : Base(a0){} template<typename A0, typename A1> DerivedImpl(const A0 &a0, const A1 &a1) : Base(a0, a1){} // get_tagの実装 int get_tag() const { return boost::mpl::index_of<typename Base::DerivedTypes::Types, Derived>::type::value;} };
のようなget_tagを実装してくれるクラスを用意することにした。
これが動くには基底クラスにDerivedTypes::Typesという名前で派生クラスの型リストが無ければならない。
struct Expr { struct DerivedTypes; //略 }; //各派生クラスの定義。 struct Expr::DerivedTypes { typedef boost::mpl::list< BinOp, IntLit, FloatLit > Types; };
Exprに直接型リストを書かないのは、前方宣言をできるだけしないでいいようにするためである。
型リストからswitch～caseを生成する。
template<typename Result, typename Func, typename Base> Result visit(Func f, Base &a) { typedef typename Base::DerivedTypes::Types Types; switch(a.get_tag()) { case 0: return f((typename boost::mpl::at_c<Types, 0>::type &)a); case 1: return f((typename boost::mpl::at_c<Types, 1>::type &)a); case 2: return f((typename boost::mpl::at_c<Types, 2>::type &)a); //case 3: return f((typename boost::mpl::at_c<Types, 3>::type &)a); //case 4: return f((typename boost::mpl::at_c<Types, 4>::type &)a); } }
型リストの長さを越えてat_cするとコンパイルが通らない。なので、インデックスが型リストのサイズを超えているかどうかでコードを切り替える必要がある。面倒なので説明は省略。
boost::variantのapply_visitorも内部でこのようなコードを使用している。
そんなこんなでライブラリとしてまとめたのが以下。
これの良いところは新しく作った派生クラスを型リストに追加し忘れても、ちゃんとエラーになってくれるところ。get_tagがコンパイルできないのでエラーになる。
Recursive variant types - Advanced Topics - Boost.Variantチュートリアルに興味深い例が載っている。boost::variantを使って簡単な計算機を作る例だ。
これをまねて、今回の構文木に適用してみると、
struct Location { int line, column; Location(int line, int column) : line(line), column(column){} }; struct BinOp; struct IntLit; struct FloatLit; typedef boost::variant< boost::recursive_wrapper<BinOp>, IntLit, FloatLit > ExprBody; struct IntLit { int value; IntLit(int value) : value(value) {} }; struct FloatLit { double value; FloatLit(double value) : value(value) {} }; struct Expr { Location loc; ExprBody body; template<typename Body> Expr(const Body &body, const Location &loc) : loc(loc), body(body){} }; struct BinOp { enum OpType { OP_ADD, OP_SUB, OP_MUL, OP_DIV}; OpType op; Expr lhs; Expr rhs; BinOp(OpType op, const Expr &lhs, const Expr &rhs) : op(op), lhs(lhs), rhs(rhs) {} };
継承を使っていないのでコンストラクタがすっきりする。
しかし、派生クラスの前方参照をずらずら書かなければならなかったり、クラスの定義順に気を使わなければならなかったり、それを回避しようといろいろやっていると、結局ポインターで持った方が良いじゃん！ということになりかねなかったりする。
それと、ノードを作るときにExpr(IntLit(123), Location(1,1))と書かなければならないし、apply_visitorで個別の型を受け取れたとしてもLocationを別途受け取らなければならなかったりして意外と面倒。
新番組多すぎ。このクソ忙しいのに。頑張って可能な限り見た。
新番組30○7△10×13。数が多い割にはこれはというものは無い。しいて言えば坂道のアポロンあたりか。やっぱりノイタミナは固い。
4/4～4/6撮影gifアニメーション。4/4、4/5、4/6の三日間、毎日午前9事前後に撮影。
結構角度が変わってしまったのだけどPhotoshopで無理矢理補正。
MXでやっていたので見た。傑作選なのね。なんか投票もやってるんだとか。
今回放送されていたのは一期の第一話と第二話だったけど、画面比が4:3だから画面左右が青帯で埋められていてなんだか変な感じ。
GAはほぼすべて見ているはずだけど、一番印象に残っているのは顔出し看板ですかね。あとは成りアガリクスダケとか。
確かtwitterで言及されていて興味を持ったんだと思ったけど、出家とその弟子を読んだ。たまにはこういうのを読むのも良いね。
どんなに考えてみても人間ではどうにもできないと思えるから祈るとか願うとかするしか無いでしょ、みたいな感じかなぁ。私は何か超越的な存在(例えば仏様みたいなの)を具体的に信じているわけでは無いので、祈って神仏におすがりする、みたいなのはゾッとする(まあ、すがれとは言っていないと思うけど)。しかし、繰り返し祈り、願うことによって深層意識というか、脳に実現しやすい性質をすり込んでいくというのならば、まだ分からなくも無い。どのみち証拠も無い分からない話ではある。
自分にはできると自分をだますんだ！
今期も終わりましたね。