ブログトップ 記事一覧 ログイン 無料ブログ開設

おびなたん☆

1981 | 11 |
2004 | 08 | 09 | 10 | 11 | 12 |
2005 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2006 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2007 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2008 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 10 | 11 | 12 |
2009 | 01 | 02 | 03 | 04 | 05 | 06 | 07 | 08 | 09 | 11 | 12 |
2010 | 01 | 02 | 03 | 05 | 12 |
2011 | 02 | 03 | 05 | 07 |
2012 | 02 |
2013 | 02 | 04 | 05 | 06 |
2014 | 01 | 02 |
2015 | 12 |

Apr 27, 2009. Mon

[]モールス符号google

Googleのトップページがモールス符号に。

http://gyazo.com/408e7a44e92a6cf0813d77c55287ee41.png

今日はサミュエル・モールスの誕生日だったのね。電磁誘導を応用して電信を発明し、その通信としての基本的な考え方が約250年後にはインターネットの発明へとつながることになった偉大な発明家です。

Apr 18, 2009. Sat

[][]型レベルプログラミングの会

f:id:earth2001y:20090418121138j:image

東京駅から丸の内線に乗ったが、溜池山王駅が屈指の地下ダンジョンであることをすっかり忘れていて、丸ノ内線国会議事堂前駅の最後尾車両を降りてから、ATTの最寄り出口まで20分も歩く羽目になってしまった。しかも途中で2回引き返しをしている。ふんがー。

C++ テンプレートでカレンダー

で、このさいなので一昨年の夏プロシンのショートセッションでしゃべったネタを再版論文にはなっていないので、一般には初公開?

セッションは好きなプログラミング言語でカレンダーを実装する、というお題で、おいらはC++テンプレートを使った。

他に、竹内先生がLispで宇宙カレンダーを作ったり(ref:竹内郁雄@Lispハッカーは、日本のゲルトミューラーだ/Tech総研)、ささださんがRubyVMにカレンダー命令を組み込んだり、にしおくんがpythonワンライナーっぽい正方形プログラムを書いたりしていた。

C++ テンプレートでカレンダー

概要

C++テンプレートによるメタプログラミングで、コンパイルタイムにカレンダーを計算し、オブジェクトプログラムへ結果を組み込むプログラムを作成する。またそのプログラムの記述方法から、C++テンプレートと関数型言語との類似点を紹介する。

はじめに

C++テンプレートはコンパイルタイムで駆動する型ベースの計算システムで、マルチパラダイムプログラミング言語C++の総称性プログラミング部分を担う。[1]

C++テンプレートはチューリング完全性を備えていることが分かっており[2]、総称性プログラミングの範囲を超えてアルゴリズムを記述することができる。これをテンプレートメタプログラミングと呼ぶ。

本稿ではC++のテンプレートメタプログラミングを使い、お題であるカレンダー作成をコンパイルタイムで行うプログラムを作成する。

テンプレートによるメタプログラミング

関数の記述

C++のテンプレートメタプログラミングでは型をオブジェクトに、型を引数とするクラステンプレートを関数に見立てる。そして、テンプレートをインスタンス化する操作が関数適用に相当する。

例えば、f(x,y) = g(p(x),q(y))のような関数fは次のように記述する。

template<class X, class Y>
struct F {
  typedef Q<Y> q;
  typedef typename G<P<X>,q>::ev ev;
};

関数に見立てたテンプレートには全て、評価(evaluation)を意味するevという名前のメンバ型を持たせ、関数の評価値に相当する型をtypedefしておく。このevを参照することで評価値を得ることができる。この記述は一種のダックタイピングであり、typedef操作は変数の宣言および束縛に相当すると言える。

関数の評価とパターンマッチ

テンプレートはそのインスタンスが実際に必要とされるまでインスタンス化されない。そのため、evを参照する位置によって評価のタイミングをコントロールでき、遅延評価を行うことも可能である。また、テンプレートは参照透過性が確保されており、一度評価されると後はパターンマッチにより評価が省略される。

テンプレートにはifステートメント相当の記法が無く、テンプレートメタプログラミングではテンプレートの部分特殊化を多用する。テンプレートの部分特殊化とは引数の一部が特定の場合のテンプレートを定義しておくことで、インスタンス化の際に引数のパターンマッチで適切なテンプレートが選択される。

このように、C++テンプレートは関数型言語に類似した側面を持つが、λ関数に相当する記法が無いこと、テンプレートそのものをオブジェクトとして扱えないことなどが関数型言語とは決定的に異なる。

テンプレートの停止性

C++テンプレートはチューリング完全なコンパイルタイムの計算モデルなので、テンプレートを使ったプログラムが有限時間内にコンパイル可能かどうかを判定することは一般的にはできない。チューリング機械の停止問題に帰着するこの問題を回避するため、C++の仕様ではテンプレートの再帰は最低17回までしか保証しないことになっている。

実装

暦計算プログラム

アルゴリズムにZellerの合同式[3]をC++テンプレートメタプログラミングで実装した、暦計算プログラムを以下に示す。

基本の整数型N<n>を定義した後、各関数を定義する。全ての関数は最終的にN<n>に評価される。N<n>::vlで対応するint型整数nを取り出す。

template<int n> // 全てのevの基底
struct N {
 typedef N<n> ev;
 static const int vl = n;
};

template<class N1, class N2>
struct ADD {
 typedef N<N1::ev::vl + N2::ev::vl> ev;
};

template<class N1, class N2>
struct SUB {
 typedef N<N1::ev::vl - N2::ev::vl> ev;
};

template<class N1, class N2>
struct MUL {
 typedef N<N1::ev::vl * N2::ev::vl> ev;
};

template<class N1, class N2>
struct DIV {
 typedef N<N1::ev::vl / N2::ev::vl> ev;
};

template<class N1, class N2>
struct MOD {
 typedef N<N1::ev::vl % N2::ev::vl> ev;
};

template<class N1, class N2>
struct LT {
 typedef N<(N1::ev::vl < N2::ev::vl)?1:0> ev;
};
template<class C, class N1, class N2>
struct IF {
 template<class _C, class _N1, class _N2>
 struct _IF {
  typedef typename _N1::ev ev;
 };
 template<class _N1, class _N2>
 struct _IF<N<0>, _N1, _N2> { // 部分特殊化
  typedef typename _N2::ev ev;
 };
 typedef typename
  _IF<typename C::ev,N1,N2>::ev ev;
};

template<class Y, class M, class D>
struct Z {
 static const int a = DIV<Y,N<100> >::ev::vl;
 static const int b = MOD<Y,N<100> >::ev::vl;
 static const int m = M::ev::vl;
 static const int d = D::ev::vl;
 typedef N<(static_cast<int>(m*2.6-0.2)+d+b+b/4+a/4+5*a)%7> ev;
};

template<class Y, class M, class D>
struct ZELLER {
 typedef Z<SUB<Y,N<1> >,ADD<M, N<10> >,D> E1;
 typedef Z<Y, SUB<M, N<2> >, D> E2;
 typedef typename
  IF<LT<M,N<3> >, E1, E2>::ev ev;
};

template<class Y, class D>
struct DIF {
 typedef typename
  DIV<SUB<DIV<Y,D>,SUB<Y,N<1> > >,D>::ev ev;
};

template<class Y>
struct LEAP {
 typedef DIF<Y,N<4> >   E1;
 typedef DIF<Y,N<100> > E2;
 typedef typename
  ADD<SUB<E1,E2>,E2>::ev ev;
};

template<class Y, class M>
struct DS {
 template<class _Y, class _N> struct _DS {};
 template<class _Y>
 struct _DS<Y0, N<1> > { typedef N<31> ev; };
 template<class _Y>
 struct _DS<_Y, N<2> > {
  typedef typename
   ADD<N<28>,LEAP<_Y> >::ev ev;
 };
 template<class _Y>
 struct _DS<_Y, N<3> > { typedef N<31> ev; };
 template<class _Y>
 struct _DS<_Y, N<4> > { typedef N<30> ev; };
 template<class _Y>
 struct _DS<_Y, N<5> > { typedef N<31> ev; };
 template<class _Y>
 struct _DS<_Y, N<6> > { typedef N<30> ev; };
 template<class _Y>
 struct _DS<_Y, N<7> > { typedef N<31> ev; };
 template<class _Y>
 struct _DS<_Y, N<8> > { typedef N<31> ev; };
 template<class _Y>
 struct _DS<_Y, N<9> > { typedef N<30> ev; };
 template<class _Y>
 struct _DS<_Y,N<10> > { typedef N<31> ev; };
 template<class _Y>
 struct _DS<_Y,N<11> > { typedef N<30> ev; };
 template<class _Y>
 struct _DS<_Y,N<12> > { typedef N<31> ev; };
 typedef typename
  _DS<Y, typename M::ev>::ev ev;
};|
カレンダーを出力

テンプレートはコンパイルタイムの計算システムなので、計算結果はコンパイラの出力を媒体とする。ここではオブジェクトファイルにカレンダーを出力する。いわば、コンパイラはテンプレートのインタプリタである。

出力コード

以下に、オブジェクトファイルの定数セクションに曜日方向の日付配列を曜日名で出力するコードを示す。

template<class Y, class M, class E>
struct DATE {
 typedef SUB<N<1>, ZELLER<Y,M,N<1> > > Z;
 typedef typename 
  IF<LT<ADD<E,Z>, N<0> >,    N<0>,
  IF<LT<DS<Y,M>, ADD<E,Z> >, N<0>,
  ADD<E,Z> > >::ev ev;
};

typedef N<_YEAR>  Y;
typedef N<_MONTH> M;
#define DAY(D,DD) 
extern const char D[] = { 
 DATE<Y,M,N<DD>    >::ev::vl,
 DATE<Y,M,N<DD+7>  >::ev::vl,
 DATE<Y,M,N<DD+14> >::ev::vl,
 DATE<Y,M,N<DD+21> >::ev::vl,
 DATE<Y,M,N<DD+28> >::ev::vl,
 DATE<Y,M,N<DD+35> >::ev::vl,
}
DAY(su,0); DAY(mo,1); DAY(tu,2); DAY(we,3);
DAY(th,4); DAY(fr,5); DAY(sa,6);|
出力操作

最後に計算結果の確認操作を行う。以下はx86 Linuxでの操作例であるが、環境毎のオブジェクトファイルの形式に合わせるため、nmコマンドなどbinutilsを併用するとよい。

% c++ -o -D_YEAR=2007 -D_MONTH=8 cal.cpp
%% objdump -x cal.o
% od -tdC -j 064 -N 42 --width=6 cal.o
0000064    0    5   12   19   26   0
0000072    0    6   13   20   27   0
0000100    0    7   14   21   28   0
0000106    1    8   15   22   29   0
0000114    2    9   16   23   30   0
0000122    3   10   17   24   31   0
0000130    4   11   18   25    0   0

おわりに

C++のテンプレートメタプログラミングを使って、コンパイルタイムでカレンダーを計算した。

Stroustrap曰く「テンプレートを総称型以外にやたらと使うなよ」。しかし現実には、Boost.MPLのようなテンプレートメタプログラミングライブラリが普及し、C++ 0xやD言語標準化にも影響を与えている。

コンパイルタイム計算はデバッグが大変だが、ぜひテンプレートメタプログラミングを楽しんで欲しい。

参考文献

  1. Stroustrap, B.: The Design and Evolution of C++ (1994), 邦訳「C++ の設計と進化.
  2. Veldhuizen, T. L.: C++ Templates are Turing Complete (2003).
  3. 和田英一:Haskellプログラミング暦法算法, 情報処理, Vol.47, No.1, pp.54-62 (2006).

Apr 9, 2009. Thu

[]丸の内撮影会をやりたい

一日丸の内でお仕事。天気がよかったからか、丸の内のビル群とか皇居とかがすごく絵になるように見えた。

天気のいい日はぜひ丸の内撮影会をやりたいね。基本、オフィス街なので、平日のほうが絵になると思うんだけど、休日の人が少ないところをゴーストタウンぽく意外性を表現するのもいいかも。

ちなみに、屋根無しパスをみかけた。長野でも善光寺御開帳期間中、観光路線として運行している。バス自体も被写体として面白いし、バスからの視界も楽しそう。

Apr 5, 2009. Sun

[]蒲田

高専カンファレンス後、juneくんの家へおしかけ。蒲田の西口は初めてだなー。

夜な夜なUstしながら寝落ち

昼前に起きて、食事を求めて蒲田駅方面へ。

大田区役所の「大田区」の英語表記が「OTA CITY」、頭にWをつけたい衝動に駆られる。しかもいろいろ調べてみると、大田区の地域情報ポータルサイトドメインotaku-town.com 。こっちのほうが直接的だw

区役所の隣、消費者生活センターの一階にある中華料理屋の餃子が、具が豊富でおいしい。

Apr 4, 2009. Sat

[]高専カンファレンス 006東京LT

場所は田町の株式会社オプティムの会議室。売り上げ300%アップ中の絶好調企業。

今回は運営のおさだくんのかねての想いから小規模での開催。で、全員LT。

ガンレフネタが二つあったり、と規模に関係なく多岐に渡る楽しい話が繰り広げられた。

そのなかでも特筆すべきは、実験LTが行われたガウス加速器

参考までにYouTubeにあったガウス加速器の動画

D

レーンに置いてある磁石に対する磁力ポテンシャルが運動エネルギーになって加速される。何段か重ねたらすごいことになりそう。

遅れてきたはまさきくんのシリコンバレーレポートも面白い。スタンフォードには割と簡単に(中学卒業レベルの英語と数学で)留学できちゃうとか。とりあえず、行って10日ほど滞在するだけなら20万円かからないということなので、時間作っておいらも行ってみたいと思う。

IMG_4761

IMG_4769

ドラ息子が今回も暴れた

おいらトーク

スライド110枚は多すぎました。しかも、発表端末用にPowerPoint形式に変換したら化けてるし。。。

おいら以降の人たちはみんな時計を用意してる。準備は大切だね!

Apr 3, 2009. Fri

[]トークスライド準備

高専カンファレンス 006東京LT のトークスライド準備。

100枚越えちゃったけど持ち時間7分なので、福井の時の80枚/5分よりは余裕あるな。うん。

おいらといがらしさんで、高専カンファレンスのこの一年、組織化をリレー形式にトークします。

Apr 2, 2009. Thu

[]CLANNAD 8

CLANNADオフィシャルコミック (8) (CR COMICS)

CLANNADオフィシャルコミック (8) (CR COMICS)

重い、重いよ。なんて重い終わり方なんだ。

Apr 1, 2009. Wed

[]新社会人ウォッチャー

毎年4月1日恒例の新社会人ウォッチャーズを実施。長野駅前のドトールモーニングコーヒーを飲みながら、街ゆく新社会人を眺めてニヤニヤ。

[]高専カンファレンス実行委員会本格開始

昨年の高専カンファレンスやりますから1年。これまで4回の開催を数えてきた高専カンファレンスですが、並行して昨年末から実行委員会を組織し、役割の明文化作業を進めてきました。

その組織化作業がひととおり完了し、この2009年4月1日をもって定款を発効し、高専カンファレンス実行委員会が本格稼働しました。

組織化の背景としては、

  • 継続的・持続的な開催をしていくためには、だれもが開催できるようにノウハウの共有化、コンポーネント化が必要
  • 各地で「高専カンファレンスやりたい」という声があり、開催時期などについての調整役が必要
  • 外部の機関、コミュニティと交渉ごとが生じるときに、信用の担保となるガバナンスが必要

というもがあります。おそらく、多くのコミュニティや勉強会も同じような悩みを持っているでしょう。

もともと持っているフリーダムな雰囲気を保ちつつ、これらの課題をどう解決するか、これまで高専カンファレンスに参加した老若男女多くの方からの意見を集約しながら、高専カンファレンス実行委員会の存在意義を模索しました。

そこで、高専カンファレンス実行委員会の事業を次のように定めました。(定款第3条)

  1. 高専カンファレンスの開催
  2. 高専カンファレンスの資料の公開
  3. 他団体が行う高専生を対象としたコンテスト、イベント等の支援
  4. その他、前条の目的を達成するために必要な事業

また、カンファレンス開催にあたっては、各開催ごとに小委員会(現地実行委員会)を結成し運営を行いますが、小委員会には実行委員会の役員1名以上を含むことにして、開催のサポートを行うことにします。(定款第5条)

このように、高専カンファレンス実行委員会は、各地の「高専カンファレンスやりたい」という声に対してHUB役となり、必要なノウハウを提供していつでもどこでも開催して楽しめる高専カンファレンスづくりを担っていきます。

一年前、カンファレンス開催を宣言したときには、まさかここまでことが大きくなるとは思ってもいませんでしたが、多くの人の共感・賛同を受けることができました。この組織化とこれからの活動で、より多くの人にカンファレンスを楽しんでもらいたいと思います。