Recent Posts

2012-06-27

ラグ輪

この間「鴨川」という単語を聞いて以来「ジャージの女の子、何か持ってるー」というフレーズが頭の中で回っていて困ったのでCDを買った。

何で当時買っていなかったのだろうと疑問に思うのだけど、OPに洗脳される前に話自体に嫌気がさしたのかもしれない。

歌詞カードを見て後ろの声がLag-Rin Lag-Rinと言っていたことを知る。Lag-Rinってなんだと思っていたら輪廻のラグランジェの公式サイトのURLが目に入った。lag-rin.jpだった。そ、そうだったのか……。

2012-06-09

世界名作劇場

何のきっかけだったか、youtubeで世界名作劇場の(どの作品か忘れたけど)第一話を見かけた。その関連動画を見たら名劇作品の第一話だけがずらっと並んでいて、え？　と思いよく見たらアップロードしたのはNipponAnimationというユーザーだった。たぶん日本アニメーション自身が宣伝のために第一話だけアップロードしているのだろう。続きはこちら、みたいなリンク付きだし。

それでいくつか第一話を眺めた後、試しにGyaOで買って見たのは「私のあしながおじさん」。こういう成長ものはやっぱり良いなと思いますね。赤毛のアンとかも近いものがあるかな。

ところで世界名作劇場ってWikipediaによると、最も広い定義で1969年の『ムーミン』以降の作品なのだとか。私はフランダースの犬以降だと思っていました。

以下、Wikipediaのリストの中で自分が見たことがあるものをリストアップしてみる。

全話見たはず(1～2話くらいは見逃したかも):

  • アルプスの少女ハイジ
  • フランダースの犬
  • フランダースの母をたずねて三千里
  • 赤毛のアン
  • トム・ソーヤの冒険
  • 小公女セーラ
  • 愛の若草物語
  • 私のあしながおじさん
  • トラップ一家物語
  • 大草原の小さな天使 ブッシュベイビー
  • 若草物語 ナンとジョー先生
  • 七つの海のティコ
  • ロミオの青い空
  • 名犬ラッシー
  • 家なき子レミ

半分くらい見たような気がする:

  • 愛少女ポリアンナ物語

1話以上見たことがあるはず:

  • 家族ロビンソン漂流記 ふしぎな島のフローネ
  • 牧場の少女カトリ

たぶん見てない:

  • どろろと百鬼丸
  • ムーミン
  • アンデルセン物語
  • 山ねずみロッキーチャック
  • 南の虹のルーシー
  • アルプス物語 わたしのアンネット
  • 小公子セディ
  • ピーターパンの冒険
  • レ・ミゼラブル 少女コゼット
  • ポルフィの長い旅
  • こんにちは アン ～Before Green Gables

分からない:

  • ムーミン(新)
  • ペリーヌ物語

見た中で一番好きなのは何か、と聞かれると結構困りますね。どれも良い作品ばかりです。いや、でも、私の中で世界名作劇場はロミオの青い空で終わっているかな。

この系統の作品は最近少ないですけど、比較的最近で印象に残っているのは風の中のエミリーですね。大きくなって友達と離れ、自分は何者にもなれずに終わってしまうのではないかという不安を抱えながら執筆を続ける姿が良いんですよ。

2012-05-28

銀河へキックオフ!!

銀河にキックオフ!!には西園寺玲華というぽっちゃり(かなり控えめな表現)とした女子のチームメイトが登場するのですが、OPには 太っている ぽっちゃりとしたチームメイトは出てこなくて、同じ髪の色、ほぼ同じ髪型のチームのユニフォームを着た女子が出てくるんですよ。えー、これってひょっとして痩せた姿なの？　気になるじゃないか。

話自体も普通に面白いですよ。

ちなみに作中によく出てくる橋は府中四谷橋ですね。

2012-05-22 ,

org-modeの中でテキストで図を書けるようにする

Emacsのorg-modeで文書を書いていると、ふと図を差し込みたくなることがある。

図と言ってもいろいろあるが、いくつかの図はテキストで書けるものだ。たとえばGraphvizのdotというツールを使えばグラフ構造をdigraph{A->B; A->C; B->C;}といったテキストで書ける。ditaaというツールを使えば簡単なダイアグラムをアスキーアートで書ける。PlantUMLではUMLをテキストで書ける。テキストで書いた「図」はそれらのツールによって画像に変換できる。

org-modeにはそれらテキストで書いた図を混ぜ込んだ文書を適切に変換して出力してくれる機能がある。それを使えばテキストエディタの中だけで、ちょっとした図を含む文書が書けてしまう。

なので今日はその機能の使い方を勉強しながら、試しにその機能を利用した文書を書いてみた。

org-modeで図を書けるようにする

2012-05-14

考えなければ与えられない

なんか最近どんどん考えるのが億劫になって、嫌になっちゃうんだけど、たまにちゃんと考えてちゃんと答えが出ると、まだまだ見捨てられていないなと思う。
そんな日はちょっと嬉しくなっちゃうね。
まあ、長続きはしないんだけどさ。

2012-04-20

C++における(抽象)構文木の表現

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) {}
};

コードに対する補足説明:

  • public:とかprivate:とか書くのが面倒なので、すべてstructにしてある。
  • Locationはいきなり出てきたが、ソースコード上の位置を記憶しておくためのもの。こういったものがあるかどうかも設計に微妙に影響してくる。
  • 各ノードはshared_ptrで取り回すことにした。解放が楽なので。循環参照の危険も今回はないので。

上のコードは式の基底クラスであるExprと、その派生クラスであるBinOp、IntLit、FloatLitを定義している。

素直なC++のコードだが、次の点が気になる。

  • const Location &locやExpr(loc)があちこちに出現する。Exprにメンバを追加するたびにこれらを修正しなければならない。
  • ノードを巡回する方法が未定。

一つ目の問題はコードの重複を気にするものだが、あまり良い方法は見当たらないのでひとまず置いておく。C++で継承をするとよくこの問題にぶつかる。マクロを使ったり、Exprを直接引数にとったり、包み込む別のクラスを作ってlocをそちらへ移動したり、初期化リストで初期化するのを諦めたり、独自のプリプロセスを行ったり、いくつか手は考えられるのだが、それぞれ良い面と悪い面がある。

二つ目の問題は実際に構文木を構築した後、どのように使うのかということだ。プログラムで構文木の各ノードを一つ一つ見て処理をしていく場合に、どうやって各ノードの種類を判別し、適切な処理を起動するのか。

dynamic_castによる訪問

例えば各ノードを訪問してテキスト出力するようなプログラムは次のようになる。 

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パターンによる訪問

この手の問題への解決方法にはVisitorパターンというものがよく知られている。どんな感じになるのかはWikipediaにC++の例が載っているので、見れば分かると思う。

C++で実装する典型的なVisitorパターンにはいくつか欠点があるように思う。

  • 侵入的
  • 各派生クラスにacceptを仕込む工夫が必要
  • 一つの派生クラスに関する定義・宣言が複数の場所に散乱しがち(各accept関数の中身を書くにはVisitorインタフェースの完全な定義が必要だが、Visitorインタフェースを定義するには各派生クラスの宣言が必要。なので、各派生クラス毎に前方宣言を書くか、accept関数の定義をクラスの定義から分離するかしないといけない、と思う)
  • accept関数の戻り値を自由にできない
  • accept関数の引数型を自由にできない(constにするかしないか、参照で受けるかポインターで受けるか、shared_ptrで受けるか等)

種類を取得するメンバ関数を追加する方法

派生クラスの判別をどのように行うか。派生クラス自身に尋ねれば良い。この方法によって、典型的な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が返す値(派生クラスの識別子)を正しく維持しなければならない点だろう。新しい派生クラスが追加されることを考えると、ある程度自動的に識別子を設定して欲しい。

少し考えただけでも次のような方法が思い浮かぶ。

  • typeidを使う方法
  • プリプロセッサでナンバリングする方法
  • 型リストを使う方法

型リストを使って派生クラスの識別子を設定する

次のような型リストを作っておけば、 

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がコンパイルできないのでエラーになる。

boost::variantを使った構文木の表現

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を別途受け取らなければならなかったりして意外と面倒。

2012-04-15

新番組ファーストインプレッション

新番組多すぎ。このクソ忙しいのに。頑張って可能な限り見た。

  • ○宇宙兄弟
  • ×緋色の欠片
  • △→×しばいぬこさん
  • ×GON-ゴン-
  • △→×あらしのよるに
  • △これはゾンビですか？オブザデッド
  • △めだかボックス
  • △LUPIN THE Third 峰不二子という女
  • △→×しろくまカフェ
  • △→×あっちこっち
  • △→×さんかれあ
  • ○アクセルワールド
  • ○ZETMAN
  • ×夏色キセキ
  • △銀河へキックオフ！！
  • △→×ジュエルペット　きら☆デコッ！
  • △プリティーリズム・ディアマイフューチャー
  • △謎の彼女X
  • △へうげもの
  • △黄昏乙女×アムネジア
  • ×這いよれ！ニャル子さん
  • ○黒子のバスケ
  • ○ヨルムンガンド
  • ×クイーンズブレイド リベリオン
  • ○坂道のアポロン
  • ○つり球
  • △咲-Saki-阿知賀編 episode of side-A
  • △エウレカセブンAO
  • △→×戦国コレクション
  • △→×シャイニングハーツ　幸せのパン

新番組30○7△10×13。数が多い割にはこれはというものは無い。しいて言えば坂道のアポロンあたりか。やっぱりノイタミナは固い。

© 2025 AKIYAMA Kouhei, all rights reserved.