確か cppll でかなり昔に見た記憶があるんですが、C++ のこれ
int I = 42;
const int CI = I; // OK!
int* pI = &I;
const int* pCI = pI; // OK!
int** ppI = &pI;
const int** ppCI = ppI; // コンパイルエラー! int** から const int** への変換はできません!
は何故こういう仕様になっているのでしょうか？というのは面白いクイズだなーと。 「2番目が安全なのと同じで、3番目も型的には安全では？」と一瞬思ってしまうのですが、 そんなことはなく、このキャストを許すと const なはずのものを書き換えられてしまいます。 具体的にどうやるかは読者の皆様への宿題です（←偉そう）。
知った当時はよく仕様考えてあるなーすげーなーと感心していたのですが、 今にして思うとこれは別に const に限った問題ではなくて、
class A {};
class B : public A {};
int main() {
B b;
A a = b; // OK!
B* pb = &b;
A* pa = pb; // OK!
B** ppb = &pb;
A** ppa = ppb; // コンパイルエラー!
}
と全く同じ問題なんですね。Java の
class A {}
class B extends A {}
B[] b = ...;
A[] a = b;
a[0] = new A();
…が（型チェックは通るけど）実行時に型エラー、というのが一番有名なバリエーションかな。
さらに何となくぼんやりと考えるに、上に上げた二つの問題の類似性からもわかるように、
const は抽象スーパークラス（というと語弊がありますけど。
スーパータイプ）を勝手に自動生成する機能と言えます。言えます。言えることにする。
List ってクラスがあったら const List っていうのが自動で作られる。
こういうイメージ。
class const List {
public:
// constってマークしてあるメソッドだけ自動抽出
virtual Object getAt(int i) = 0;
virtual int size() = 0;
};
class List : public const List {
public:
void push_back(Object obj) { ... }
void setAt(int i, Object obj) { ... }
Object getAt(int i) const { ... }
int size() const { ... }
...
};
実際は、const
ってマークしてあるメソッドの中身が本当にフィールドを書き換えないかのチェックも入るんですが、
そこは今日は無視します。
単純に、このスーパータイプ作る機能を const
以外に任意のユーザー定義キーワードでもできるようにすると、どうでしょうね。
class List {
public:
void setAt(int i, Object obj) { ... }
Object getAt(int i) const { ... }
int size() const stack queue deque { ... }
void push_back(Object obj) stack queue deque { ... }
void pop_back() stack deque { ... }
Object back() const stack deque { ... }
void push_front(Object obj) deque { ... }
void pop_front() queue deque { ... }
Object front() const queue deque { ... }
...
};
stack List s; // size と push_back と pop_back と back できる
queue List s; // size と push_back と pop_front と front できる
const stack List s; // size と back だけできる
はい、実は自分でも書いてて stack と queue と deque は例が悪いなあと思い始めてます。 普通の継承や委譲や構造サブタイピングやnon-intrusiveなinterfaceやその他色々と比べて特に利点も思いつかないんですが、 何か面白い使い道ないですかねえ。const では上手くいっているのは自動チェックのためだけではない気がするので、 他に適用範囲があってもおかしくないとは思うんですが。
最近、なんでもいいので 「ツリーではなくタグっぽく」 物を管理するという方式をプログラミング言語に突っ込んでみることはできないか、 という妄想をすることが多くて、なんとなくこんなものが出てきました。
職場でこの前あった
オープンハウス
なるイベントの基調講演を録画したものが公開されたみたいです。
タンジブル・ビットの石井さんやRubyのまつもとさんの講演ももちろん興味深いのですが、
個人的には、新井さんの「役にたたなきゃ数学じゃない」が、
（とても物申したくなるタイトルに反して）クリーンヒットでした。
※8月末で配信終了予定です
なんてもったいないことが書いてあるのに今気づいたので、今の内にあわててご紹介しておきます。
内容自体は古代ギリシャ以前から始まる数学史的な話で、
そういうのにちょっと詳しい人はよく知ってるような歴史の紹介です。が、その視点が面白いなーと。
論理や記法やシンタックスの、重要さ…というと普通だな、えーと、
「単にセマンティクスを書き表すための手段」という以上の本質的なステップとしてそれらを捉えてみる見方。
オススメ。
CIAA 2009 行ってました。 ところでシドニーから帰ってくるたびに思うんですが、 Oporto は日本でもチェーン展開してくれないでしょうか。
今回一番自分にとって面白かった論文は、"Compact Normal Form for Regular Languages as Xor Automata" という題のものでした。なんでも、正規言語を表すのに Xor-Automaton というモデルがあるらしく、 それの O(n^3) 時間の最小化アルゴリズムができたよーというお話。 最小化自体もまあ面白いのですが、Xor-Automaton という表現を今まで考えてみたことがなかったので、 そのイントロの時点で なるほどなーと感心しまくっていました。調べてみると6～8年くらい前のCIAAに色々出てるなあ…勉強不足…。
簡単に紹介すると…、まず前提として DFA (決定性有限オートマトン) = 状態qと文字aが決まると次の状態は1つに決まる、 と、 NFA (非決定性有限オートマトン) = 状態qと文字aが決まると次の状態は "q1またはq2またはq3" みたいに複数の候補がありうる、 というオートマトンが二大有名どころです（以下この２つに関する知識を前提とした説明）。 この "または" を、C言語で言うところの | (or)ではなくて ^ (xor) で考えるようなオートマトンはどうよ、 というのが Xor-Automaton (NXA)。NFAだと 「q1に行ったら最後に受理状態に辿り着ける | q2(略)受理状態に辿り着ける | q3(略)る」 ならば 「現在の状態qから受理状態に辿り着ける」 とするという定義でしたが、これの代わりに 「q1に行ったら最後に受理状態に辿り着ける xor q2(略)る xor q3(略)る」 という形の遷移規則を考えるのがNXAだそうです。
良いところとして、 ・否定パターンの計算が簡単 （正規表現pに対応するNFAから"pにマッチしない文字列全部にマッチする"NFAを計算するのは計算が大変ですが、 DFAやNXAなら簡単） ・同値性の判定が簡単（2つのNFAが同じ意味かどうか判定するのは計算が大変ですがDFAやNXAなら楽） ・そして今回の論文の結果から、正規形（最小オートマトン）の計算が簡単 などがあるとか。 NFA の状態遷移関係は & と | を乗算加算と見た環の上の行列になっていたのが、 NXA だと & と ^ なので、これは更に体GF(2)になってて、それが見通しを良くしているように素人目には見えました。 言われてみれば凄く当たり前なアイデアだと思うんですけど、なんで自分はこういうことを考えなかったかなあ…、 とついつい過去を振り返ってしまいますね。 AFA (交代有限オートマトン) のような方向にNFAを拡張するのを見慣れてると、論理演算としか見えなくなってて {0,1} の上の計算に見えなくなってました。 面白いなあ。 ただ、NXA って and と or の計算が苦しそうだけど、実際それでどのくらい応用に使えるものなんだろうか。 （※追記: andはproduct constructionするだけだけのよーな気がしてきました。 orもandとnotで書ける。結構使えるかも）
Best Paper Award は "An (n log n) Algorithm for Hyper-Minimizing States in a (Minimized) Deterministic Automaton" という論文でした。去年辺りから局地的にブームな、 DFAを最小化するときに、元とマッチしうる文字列が有限個くらい違ってもいいのでとにかく小さくする、 というアグレッシブな最小化の話。 通常の最小化をした後は「有限ステップで同じ状態に収束する」ような二つの状態が同一視する候補なので、 これは結局1ステップの話に落ちて、 「successorが全て同じだけど受理状態かどうかが違うから通常の最小化ではunifyできてなかった」 辺りから順にmergeしていけばいい、というアルゴリズムと理解。
あとはどの論文だったか忘れてしまったのですが、 実装に The Automata Standard Template Library というライブラリを使ったと書いてあって、これはすごく使いやすそうですね。 こんど使おう。
他には何だっけ、"Nonconstructive methods and deterministic finite automata" というのは O(log n) ビットより少ないオラクル付きのDFAは結局正規言語しか受理できないとか。 REG = DSPACE(1) = DSPACE(o(log n)) と本質的に関係があるんじゃないかなあと思いつつ聞きながらググってたら空間計算量の方は o(log log n) だった。 細かいとこ見てないけど証明の方向も同じだと思うんだけれど、どこで一段違いが出るんだろう。 あとで確認する。
「まともなブログ書いてた人が情報を小出しにして満足するtwitterに行ってしまってもったいない」 という視点が、私の抱いている印象だと逆なんだよなー。 あまり、情報量が減って残念になったと感じる人は思いつかなくて、 逆に情報量が増えた気こそしています。 要は「IRCやmixiやメーリングリストや口頭でのおしゃべりですっごく面白いこと言っているのに、 公開ブログ等誰でもアクセスできる場に現れてこなくてもったいない」 と感じていた類の発言がだいぶ外に出てくるようになってありがたい、という印象でした。 いやもうほんと、IRCやらメッセンジャーやらclosedなところで駄弁りたがるスタンスを憎んですらいたので。 検索しにくさ/読み返しにくさが酷いというのはその通りなんだけど、 それでも内輪以外からは決してアクセスできないよりは遙かにマシだろうと思う。
情報ストレージとして考えると、 「玉と石をより分けるのは自分でやるから、 とりあえず玉でも石でも全部ネットに放り込んでおいてくれノイズ上等」 的な思考になるのかなあ。ただ、 そういう意味で考えても短縮URLが良くない禍根を残すだろうというのは全く100%その通りだと思います。 どうしたもんですかね。
世田谷区の「すぐやる課」のスズメ助け が話題になっていたので、育ち故郷の松戸市にもそんな課があったなーということを懐かしく思い出してました。 私のイメージだと 「すぐやる課」≒「ハチの巣駆除課」 でしたー、などと相当酷い偏見を誇張したつもりでしゃべってたのですが、現実は予想以上で、 昨年の統計によると 要望の47.8%が"スズメ蜂などの巣の駆除" らしい。びっくりした。 「発足当初からの累計」だとそんなに極端ではないので、 きっと私と同じく適当なイメージを持った人が積もり積もった結果なんだろうなあ。
自分のサイトを作ったのは6月10日だった記憶はあるのですが、1999年だったか1998年だったか思い出せません。 どっちかなのは確かなので先月で10周年または11周年ですね。 どっちだったっけ。高二だった気がする（そうなら98年）んだけど、 ネットはじめて比較的すぐだった記憶のある色々を探すと99年の夏だったりする。うーん。