2010-10-13

setできないsetプロパティ

気がつけば一年近くも何も書いてなかったとは我ながら呆れる。

さて本題。ド嵌り系の内容です。

某社のお手伝いで単体テストコードを書いた時のこと。
使用する先方のライブラリのソースは提供されていない状態だったので、クラスの提供しているインターフェースを確認するためVisualStudioでClassAという名前を右クリックし、[定義へ移動]でメタデータから確認すると

public class ClassA
{
	public ClassA();// デフォルトコンストラクタのみ
	…
	public ClassB BProperty { get; set; }
	public ClassC CProperty { get; set; }
}

こんな感じだった。

んで単体テストコードで

ClassA a = new ClassA();
ClassB b = new ClassB();
a.BProperty = b;

Assert.AreEqual( b, a.BProperty);// 一応確認

のような感じのテストを書いてNUnitでテストしたら失敗するわけだ。

Expected : bの内容
But was : null

全く意味がわからん。

他のコードを全部取っ払って、本当に上記だけ記述したテストを作ってみてもやはり同様。

But was : null

というメッセージが出ている以上「何も」セットできていない。

先方に問い合わせた結果、
「BPropertyのsetの内部実装は空である」
「ClassCのプロパティでClassBを設定できるのでClassC作ってそこにClassBを設定して、それをClassAに設定して下さい」とのこと。

ってことは内部実装は

    public ClassB BProperty {
        get { return c_member.BProperty; }
        set {}
    }

って感じになってるのか。

久々に脱力。
なぜsetプロパティ用意した？

2009-11-17

ただし技術書に限る

Book

暇なので割と最近読んだ本を簡単に紹介。
漫画を入れると量が100倍ぐらいになるのでやめておく。

空間的データ構造とアルゴリズム

作者: Elmar Langetepe,Gabriel Zachmann,中本浩
出版社/メーカー: ボーンデジタル
発売日: 2007/04/01
メディア: 単行本
購入: 1人クリック: 61回
この商品を含むブログ (8件) を見る

比較的新しい技術の概要がざっと紹介されている本。
自分が読むには前提となる基礎知識が圧倒的に足らない。
難しい。

ゲームプログラマになる前に覚えておきたい技術

作者: 平山尚
出版社/メーカー: 秀和システム
発売日: 2008/11/14
メディア: 単行本
購入: 112人クリック: 3,473回
この商品を含むブログ (193件) を見る

割と評判だったので買ってみた本。
内容は各種ゲームのシーケンス・リソースの管理・簡単な2次元/3次元衝突検出・現在の3D描画の概要など。
所々、開発で嵌りそうなポイントや回避策なども記述されており、チーム開発や規模の大きな開発をしたことがない人にオススメ。
人一人撲殺できそうなぐらい分厚い本だが丁寧に書かれており読みやすい。小さなC++プログラムを書いたことがある程度の新入社員に読んでほしい。

ゲームプログラミングのための数学と物理

作者: DANNY KODICEK,加藤諒,秋山謙一,杉山明,中村達也
出版社/メーカー: ボーンデジタル
発売日: 2006/03/25
メディア: 大型本
購入: 4人クリック: 430回
この商品を含むブログ (23件) を見る

なんとなく買った本。
解説している数学と物理については高校で習う程度＋アフィン変換＋四元数程度のレベル。
あとは3D描画の基礎・ベジエ曲線・迷路生成・ゲーム理論とAIなどなど。
非常に広範囲を網羅しているため本は分厚いがその割に深いところには突っ込まないので内容は薄い。
また訳があまり良くないのか読みにくい点が多々ある。
個人的にはオススメできない。

2009-02-05

文脈自由文法のチョムスキー標準形への変換

はてな計算機科学

※本エントリは人力検索はてなの質問http://q.hatena.ne.jp/1233731707に対する回答の一部です

まずいくつかの用語を定義することにします。

$A \to \epsilon$ のような置き換え規則をε規則と呼ぶ( $A$ は非終端記号、 $\epsilon$ は空系列)
$A \to B$ のような置き換え規則を読み換え規則と呼ぶ( $A,B$ は非終端記号)
$A \to u$ (uは長さが3以上の系列)のような規則を長文規則と呼ぶ

上に挙げた3つの置き換え規則は、文脈自由文法の置き換え規則としては許されるものですが、チョムスキー標準形には当てはまらないものです。
(ε規則は左辺の非終端記号が開始記号の場合だけはチョムスキーの標準形に当てはまります)
文脈自由文法の置き換え規則の中で上に挙げたものがある場合、その置き換え規則を除去して等価な置き換え規則を追加していけばチョムスキー標準形になるという理屈です。

(1) 新しい開始記号の導入
まず、文脈自由文法の開始記号 $S$ を別の開始記号 $S'$ に置き換えます。
つまり、非終端記号に新たな $S'$ を追加し、この $S'$ を開始記号にして、なおかつ置き換え規則に
$S' \to S$
を追加します。
こうしてできた文法は開始記号が異なるだけなので元の文法と等価です。
これにより、文法の開始記号が置き換え規則の右辺に現れないことが保証されます。

(2) ε規則の除去
文法の置き換え規則の中に、ε規則
$A \to \epsilon$
がある場合、Ａが開始記号でないならばＡが置き換え規則の右辺に現れる置き換え規則を適用可能な限り全て変更します。
例えば、置き換え規則
$B \to uAvAw$
がある場合、この置き換え規則を除去し、代わりに
$B \to uAvAw$
$B \to uvAw$
$B \to uAvw$
$B \to uvw$
を置き換え規則に追加します。
このような処理を全て行った後、元のε規則 $A \to \epsilon$ を置き換え規則から除去します。
これは元の文法と等価です。
開始記号からのε規則 $S' \to \epsilon$ 以外の全てのε規則をこのように除去します。

(3) 読み換え規則の除去
文法の置き換え規則の中に、読み換え規則
$A \to B$
がある場合、 $B$ が置き換え規則の左辺に現れる置き換え規則を全て $A$ からの置き換えに変更します。
例えば、置き換え規則
$B \to v$
がある場合、この置き換え規則を除去して
$A \to v$
を置き換え規則に追加します。
このような処理を全て行った後、元の読み換え規則 $A \to B$ を置き換え規則から除去します。
これは元の文法と等価です。
全ての読み換え規則をこのように除去します。

(4) 長文規則の除去
文法の置き換え規則の中に、長文規則
$A \to u_1u_2u_3 \ldots u_n \quad (n \ge 3)$
がある場合、新たな非終端記号 $B_1,B_2, \ldots ,B_{n-1}$ を導入して
$A \to u_1B_1$
$B_1 \to u_2B_2$
...
$B_{n-2} \to u_{n-1}B_{n-1}$
$B_{n-1} \to u_n$
を置き換え規則に追加し、元の長文規則 $A \to u_1u_2u_3 \ldots u_n$ を置き換え規則から除去します。
これは元の文法と等価です。
全ての長文規則をこのように除去します。

(5) 最終処理
ここまでの操作により、形式文法内の全ての置き換え規則の右辺の系列の長さは2以下になります。
なぜならば、右辺に長さ3以上の系列を持つ置き換え規則は(4)で除去されているからです。
右辺の系列の長さが0のものがあるとすれば、(2)の操作により開始記号からのε規則
$S' \to \epsilon$
だけであることが保証されています。
また、右辺の系列の長さが1のものがあるとすれば、(3)の操作により終端記号への置き換え
$A \to a$
の形のものだけであることが保証されています。

最期に右辺の系列の長さが2のもの
$A \to u_1u_2$
があるとします。( $u_1,u_2$ は終端記号か非終端記号)
この $u_1,u_2$ が共に非終端記号であれば、それは
$A \to BC$
という形なのでチョムスキーの標準形の条件を満たします。

$u_1$ が非終端記号で $u_2$ が終端記号の場合には、新たな非終端記号 $U$ を導入してこの規則を
$A \to u_1U$
$U \to u_2$
と変更すればそれぞれチョムスキーの標準形の条件を満たします。
また、逆に $u_1$ が終端記号で $u_2$ が非終端記号の場合も同様です。

$u_1,u_2$ が共に終端記号であれば、新たな2つの非終端記号 $U$ および $V$ を導入してこの規則を
$A \to UV$
$U \to u_1$
$V \to u_2$
としてやればよいのです。

以上の変換によって文脈自由文法の全ての置き換え規則がチョムスキーの標準形を満たすものになることがわかります。

参考文献：計算理論とオートマトン言語理論―コンピュータの原理を明かす (Information & Computing)

2009-01-06

基礎固め

プログラミング

一応ここ十年ほどプログラマとして飯を食っているのだが、実を言うと情報や計算機科学を体系的に学んだことはほとんどない。
これまではターゲットとなる業界が3次元系のソフト開発というニッチな世界だったことや、知識溢れる先輩や同僚に恵まれたこともあってこれまでどうにかこうにかやってこれた。

が、ここのところ自分の頭の回転の鈍さを度々自覚するようになってきた。
いい発想が浮かんでこない、昔やったことが思い出せない、などなど…。

ちょっとこれではヤバイ。
今は何とかなるとしても、この先自分は体力・脳ミソ共に衰えていく一方だ。
このままでは将来限界を迎えて、どこかで破綻するのは目に見えている。
他人を使うのがド下手な自分がプロジェクトマネージャーになってやっていけるとは思えないし、なにより自分は生涯技術職でやっていきたい。

そこで今更ながらしっかりと足場固めをすることにした。
基礎をしっかりと固めることで、これまでなんとなくバランス悪く積み上げてきた知識をしっかり固めて自分のものにしたい。
そこで教科書として以下を購入。

数学的基礎とデータ構造 (アルゴリズムイントロダクション)

作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
出版社/メーカー: 近代科学社
発売日: 2007/03/01
メディア: 単行本
購入: 13人クリック: 378回
この商品を含むブログ (59件) を見る

アルゴリズムの設計と解析手法 (アルゴリズムイントロダクション)

作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
出版社/メーカー: 近代科学社
発売日: 2007/03/01
メディア: 単行本
購入: 10人クリック: 169回
この商品を含むブログ (48件) を見る

アルゴリズムイントロダクション第3巻精選トピックス

作者: T.コルメン,R.リベスト,C.ライザーソン,Thomas H. Cormen,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,梅尾博司,和田幸一,岩野和生,山下雅史
出版社/メーカー: 近代科学社
発売日: 1995/12
メディア: 単行本
購入: 1人クリック: 37回
この商品を含むブログ (28件) を見る

(楽天ブックスだとなぜか第1巻と第2巻の表紙の画像が逆だったりする)

まずはこれまでなんとなくでしか理解できていなかったO記法やアルゴリズム実行時間の評価などからしっかり自分のモノにしておきたい。
直接的には仕事の役に立つことはなくとも、これまで得た知識の理解を一層深めたり、頭の中で整理したり、これから学ぶアルゴリズムの理解を助けることになると信じている。

2008-11-30

双曲線同士の交点計算

数学

そういえば2次元平面上の二次曲線同士の交点計算ってどうやって解くのだろうと疑問に思った。
高校数学の範囲では
$\frac{x^2}{a^2}+\frac{y^2}{b^2}=1$ といった楕円や $\frac{x^2}{a^2}-\frac{y^2}{b^2}=1$ といった双曲線など「綺麗な」ものしか習わなかったと思う。(いわゆる標準形)
これは楕円であれば長軸短軸がＸＹ軸と一致するものだ。
そうでなければまず座標系に一次変換や平行移動を施して標準形に変形して考えたと思う。

しかし、より一般的な二次曲線の式はこうなる。
$Ax^2+By^2+Cxy+Dx+Ey+F=0$
従って、一般的な二次曲線同士の交点を解析的に求めようとすれば、
例えばｙを消去してルートを削除することにより4次方程式を解かねばならず、非常に厄介だ。

で、調べてみたらこんなPDFを発見した。
http://www.mlab.im.dendai.ac.jp/~saitoh/CADCAM/080421P.pdf

簡単にまとめると以下のようになる。

2つの二次曲線を $f(x,y)=0,g(x,y)=0$ とすると
$f(x,y)=0 \wedge g(x,y)=0$
⇔ $f(x,y)=0 \wedge f(x,y) + \alpha g(x,y)=0 \quad (\alpha \neq 0)$
である。
ここで $f(x,y)+\alpha g(x,y)=0$ も二次曲線であるが、ゼロでない適当な $\alpha$ を選んでやると
この二次曲線を $f(x,y)+\alpha g(x,y) = (ax+by+c)(dx+ey+f) = 0$ というように
特殊な二次曲線である2直線にすることができる。

つまり二次曲線同士の交点は、1つの二次曲線と2つの直線の交点に帰着できる。
(二次曲線と直線の交点は二次方程式として解析的に解ける)

これは束(Pencil)の概念を利用した考え方だ。
高校で線束、円束を習った覚えがある人もいると思う。

うーん、素晴らしい。

2008-05-22

boost::spirit

プログラミング C++

現在受けている仕事は簡単な用件ばかりであり特に実装に悩むことはほとんどない。(納期の短さと実装量の多さ以外は)
そんな中でただ一箇所どうしようか頭を悩ませていたものがある。
数式入力が可能な電卓を実装しなくてはならないのだ。

つまり、『1+2』と入力された時点で『3』と計算結果のみが画面に表示される通常の電卓のようなものではなく
『1+2』と入力したら『1+2』と入力がそのまま表示され、計算ボタンを押した段階で式の評価を行う必要があるのだ。

ちなみに『1 2 +』と入力する逆ポーランド記法ではスタックを用いて簡単に実装可能である。
が、今回はいわゆる普通の式の記述(中間記法)に対して実装しなければならない。
また括弧にも対応しなければならないので括弧の対応がおかしな数式はエラーとして検出しなくてはならない。

一般的にはこのような四則演算と括弧だけを用いた中間記法の数式は

式 ::= 項 ( '+'項 | '-'項 )*
項 ::= 因数 ( '*'因数 | '/'因数 )*
因数 ::= 数値 | '(' 式 ')'

といった書き換え規則で表せる。(数値の定義は割愛)
このような書き換え規則の記述方法は拡張BNF記法という。
つまり式とは項に対して0個以上の項を足したり引いたりしたものであり、
また、項とは因数に対して0個以上の因数を掛けたり割ったりしたものであり、
因数とは数値もしくは式を括弧で括ったものである。
また逆にこの置き換え規則で表せないものは(四則演算と括弧だけを用いた)式ではない。

ちなみにこのような置き換え規則によって生成される文字列は文脈自由言語といい、プッシュダウンオートマトンで受理できる言語となる。
なお比較的良く知られた正規表現で記述できる正規言語は有限オートマトンで受理できる言語で、文脈自由言語の一種である。
このあたりは以下の書籍が詳しい。

計算理論とオートマトン言語理論―コンピュータの原理を明かす (Information & Computing)

作者: 丸岡章
出版社/メーカー: サイエンス社
発売日: 2005/11/01
メディア: 単行本
購入: 2人クリック: 6回
この商品を含むブログ (5件) を見る

話が少し逸れたが、今回の案件を正確に実現するには

字句解析
構文解析
式として正しい文字列かの評価
構文解析木の生成
式の評価

をしなくてはならない。これを短期間で実装するのは容易ではない。

そこで調べてみるとboostライブラリにまさにピッタリのライブラリがあることがわかった。
boost::spiritライブラリである。
このライブラリを紹介している各個人ページでは軒並み「変態的」との評価を受けている。
いったいどのぐらい「変態的」なのか見てみよう。

まずは文法を定義する構造体を定義する。

#include <boost/spirit/core.hpp>

using namespace boost::spirit;

struct Grammar : public grammar<Grammar>
{
	// 定義
	template<typename S>
	struct definition {
		rule<S> factor;
 		rule<S> term;
		rule<S> expression;

		definition(const Grammar& self) {
			expression = term >> *( ('+' >> term) | ('-' >> term) ) ;
			term = factor >> *( ('*' >> factor) | ('/' >> factor) ) ;
			factor = real_p | '(' expression ')';
		}

		const rule<S>& start() const {
			return expression;
		}
	} ;
} ;

文法のルールとしてexpression,term,factorがあるが、これらがそれぞれ式、項、因数に該当する。
ここで注目して欲しいのは、このルールの記述が前述した書き換え規則である拡張BNF記法をほぼそのまま記述できる点である。
演算子オーバーロードを駆使して、結合は『>>』演算子(『&&』演算子でも可)、選択は『|』演算子、0以上の繰り返しは『(前置)*』演算子を用いることができるので、きわめて自然に記述できるのだ。
ちなみに1回以上の繰り返しは『(前置)+』演算子、省略可能(0回か1回の繰り返し)は『(前置)!』演算子で記述できる。
また、実数の定義はプリミティブなルールとしてreal_pで用意されているのも嬉しい。

さらに最終的に評価を行いたい『式』のルールをstart()メソッドの返り値として返す。
ではこの文法を用いてテストしてみよう。

int main() {
	Grammar gr; // 文法

	std::string str1 = "1 + 2 + 3 + ( 4 + 5 )" ;// 正しい式
	std::string str2 = "1 + 2 +" ;              // 正しくない式(+演算子の後に項がない)
	std::string str3 = "((1+2)+3))";            // 正しくない式(括弧が対応していない)

	if ( boost::spirit::parse( str1, gr, boost::spirit::space_p ).full )
		std::cout << "OK" << std::endl;
	else
		std::cout << "NG" << std::endl;

	if ( boost::spirit::parse( str2, gr, boost::spirit::space_p ).full )
		std::cout << "OK" << std::endl;
	else
		std::cout << "NG" << std::endl;

	if ( boost::spirit::parse( str3, gr, boost::spirit::space_p ).full )
		std::cout << "OK" << std::endl;
	else
		std::cout << "NG" << std::endl;

}

parse()関数に、解析する文字列、文法、スキップパーサ(読み飛ばす文字列のパーサ)を渡せばよい。
(空白にマッチするプリミティブとしてspace_pが用意されている)
また、返り値としてparse_info構造体を返し、このfullメンバがtrueかどうかで構文解析が最後まで到達した(=成功した)かどうかがわかる。
このプログラムの出力は

OK
NG
NG

となり、式として正しいかどうかきちんと解析してくれている。

さて、目的は式を評価することであった。
このboost::spiritライブラリ、当然(?)のように構文解析木を作る機能もサポートしている至れり尽くせりなライブラリなわけだが、
今回はより容易な実装としてセマンティックアクションと呼ばれる機能を利用することにする。
セマンティックアクションとはつまりは文字列が一部のルールにマッチした段階で呼ばれるコールバックを設定できる機能である。

// セマンティックアクション
void print(double val)
{
	std::cout << val << endl;
}

...
// 文法ルールにセマンティックアクションを設定する
			factor = real_p[&print] | '(' expression ')'; // 実数にマッチしたらprintが呼ばれる

『[]』演算子がセマンティックアクションを設定する演算子としてオーバーロードされており、上記の例ではreal_pにマッチした段階でマッチした値が渡され、printが呼ばれることになる。
real_pのように一部のパーサは引数に特殊な型をとるvoid (*action)(double)といった関数ポインタが渡せるが、
一般的なセマンティックアクションはマッチした最初の文字(begin)と最後の文字の次(end)を引数に取るvoid (*action)(const char*, const char*)といった形の
関数ポインタを指定することになる。
また、セマンティックアクションとして関数オブジェクト(ファンクタ)を指定することもできる。

これを利用すると逆ポーランド記法のようにスタックを一つ用意するだけで式の評価ができることになる。
(簡単のためスタックはグローバル変数として定義する)

std::stack<double> st ;

void Push(double val)
{
	st.push( val );
}

void Add(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs + rhs );
}

void Sub(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs - rhs );
}

void Mul(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs * rhs );
}

void Div(const char*, const char*)
{
	double rhs = st.top() ; st.pop();
	double lhs = st.top() ; st.pop();
	st.push( lhs / rhs );
}

struct Grammar : public grammar<Grammar>
{
	// 定義
	template<typename S>
	struct definition {
		rule<S> factor;
 		rule<S> term;
		rule<S> expression;

		definition(const Grammar& self) {
			expression = term >> *( ('+' >> term)[&Add] | ('-' >> term)[&Sub] ) ;
			term = factor >> *( ('*' >> factor)[&Mul] | ('/' >> factor)[&Div] ) ;
			factor = real_p[&Push] | '(' expression ')';
		}

		const rule<S>& start() const {
			return expression;
		}
	} ;
} ;

以上のように実装し、parseを行い、スタックに残っているたった一つの値が式の評価値ということになる。

簡単な例で説明すれば
1+2*3-(4/5+1)
という式の値の評価は次のようなステップで評価されることになる。

1 (real_p)のマッチ(スタック:1)
2 (real_p)のマッチ(スタック:1, 2)
3 (real_p)のマッチ(スタック:1, 2, 3)
*3 ('*' >> factor)のマッチ(スタック:1, 6)
+2*3 ('+' >> term)のマッチ(スタック:7)
4 (real_p)のマッチ(スタック:7, 4)
5 (real_p)のマッチ(スタック:7, 4, 5)
/5 ('/' factor)のマッチ(スタック:7, 0.8)
1 (real_p)のマッチ(スタック:7, 0.8, 1)
+1 ('+' >> term)のマッチ(スタック:7, 1.8)
-(4/5+1) ('-' >> term)のマッチ(スタック:5.2)

ここで最後にスタックに残った5.2が式の評価である。
注意点として、セマンティックアクションはパース途中に呼ばれるため、全体の構文解析が失敗したとしても一部のセマンティックアクションは呼ばれる可能性があることを忘れてはならない。

さて、実際今回の案件では三角関数(sin,cos,tan)や平方根(sqrt)も利用したいということであったがその拡張が容易であることは言うまでもない。
この「変態的な」ライブラリに大いに助けられることになると同時に、本ライブラリがなかったらどうなっていたのだろうかと思うと恐ろしい。

2007-11-23

出張

仕事

先週の週末は出張に行ってました。
とある企業と大学が共同研究しているモノのソフトウェア部分の実装を請け負っているので大学へ出張することが多いのだ。
普段自宅で仕事をしている引きこもりプログラマーとしては出張は決して好きではないのだが、それでも大学へ出張すると一ついいことがある。
大学の生協の書籍コーナーには当然のことながら専門書が充実しているのだ。

田舎に住んでいる自分にとって、専門書を立ち読みして選べるのはとても助かる。
オンライン注文でほとんどの書籍は手に入る時代ではあるが、やはりある程度中身がわからないと買うのは怖い。
専門書はほぼ例外なく高いので「まぁ試しに買ってみるか」と気楽に買えるものではない。
それぐらいお金持ちになるのは夢の一つではあるが。

今回買ってきたのはこちら。

関数プログラミング

作者: R.バード,P.ワドラー,武市正人
出版社/メーカー: 近代科学社
発売日: 1991/04/01
メディア: 単行本
購入: 7人クリック: 82回
この商品を含むブログ (14件) を見る

最近HaskellだとかF#だとか、C#においてもラムダ式だとかやたらと話題になっているので買ってみた。
学術書であるので体系立てて説明されているのが嬉しい一冊だ。

一気に読んでしまいたいところだが、なにぶん忙しい年の瀬。
読破するのはいつになることやら。