Derive Your Dreams

Twitter: @kinaba

10:14 08/04/29

いろいろ

来月末

東京メトロ沿線ウォーキング のために、じゃなかった、友人の結婚式があるらしいので、ちょっと一瞬日本に戻ります。 いやまあ、メトロウォーキングには行きますが。

りふぁらにれす

アニメ、というのが通説らしいですが個人的にはゲーム。

プログラミングと俺(続き)

前回 書き忘れた。中学校の"技術"の授業で LOGO でタートルグラフィックスとかもやりました。 使ってた処理系でどこまでできたのかは全く知らないのですが、まあひたすらお絵描きしてました。 つまりメガデモ製作です(違。いろんな図形を描くときそれに伴って動くタートルをいかに作品内に取り込むか など真剣に考えたりしてました。LOGO っていう言語についてはもう、「てじゅんは」っていうキーワードしか 覚えてないですね。タートルグラフィックスって、適当なコードを適当にパラメタ変えて色々走らせると すぐフラクタル的なというかカオス的な絵が出てくるのでそれも楽しかった気もする。

そんでまあ話を元に戻して、VC++ に移ってから MFC に慣れるべく作り始めたのが TextSmile とかですね。 あとは、「なんでもいいからプログラム書きたいけどネタ思いつかないからなんかくれ!」 ってこの人に振ったら返してくれたネタから 作られたのが Noah です。 今なら言い切れますけど "俺にとってプログラム書くのは手段じゃないですよ目的ですよ" という、その傾向がだんだん垣間見られるようになってきましたね。 あとはこの頃 プログラミングコンテスト的なもの に初めて参加。

そして、高2のときだったかな、インターネットがうちにやってきた!のでした。 早速ほーむぺーじを作るべくHTMLやJavaScriptを書き始めます。プロバイダがサーバに CGI 置かせてくれなかったので Perl は全然触らなかったですね。この頃から Perl やらなんやら 触ってたら今頃全然違う方面にいるかもしれない。いないかもしれない。 まあともかく、Noah 等々を Vector に登録して、 いわゆるオンラインソフト屋さんになりはじめました。

また話それますが、 "初心者はWebアプリを作るべきじゃないのか" っていうはまちちゃんのエントリ見て思ったのが、Webアプリ版ベクターみたいなの欲しいよなーということなのだった。 前ちょっと書いたけど、他の人はどうか知らないけど 自分は「自分の作ったものに対して反応もらえる場」っていうのがいっつも欲しい人でして。まあ今はどうでも よくなってきましたが、初心者だった頃は、そういうのをモチベーションにすることでプログラミングを続けていた 気がするのです。オンラインソフトでいうと、Vectorがあって、そこにダウンロード数ランキングや新着ソフトレビュー みたいなのがあったりして、んでもってVectorや窓の杜を熱心にウォッチしてる「オンラインソフトマニア」が 多数存在して、他にもオンラインソフト専門のレビューサイトやニュースサイトがいくつもあって、っていう状況で、 とりあえずVectorに載っけてみるとどんなショボい小ネタでもどこかの誰かが拾ってくれて楽しかった。 …で、今、Webアプリ作ってみたときに、Webアプリマニアの目に留めたいと思ったらどうすればいいんだろう?という。

あとは「プログラミング言語と俺」みたいな感じになりますが、えーと、 大学に入ってわりとすぐに Lispの本MLの本 読んだ。S式ってこれなら俺でも parseできる!と思ってNoahの拡張スクリプトが似非似非S式になったりしました。あと演習の授業が Java だったので 初めて Java 触った。しばらくして、新 YZ1.DLL 作るときに yz32lib がSTL使ってたので仕方なくSTL覚え始めたり (yz32libのやまざきさんと「STLだ怖い!」「vectorとstring使ってるだけだから怖くないよ」 「vectorとstringだけでも怖いっす!」みたいなやりとりした記憶があるのがBoost本を書く2年前程度 とかなので人間って変わるものですねえ)、その勢いで Exceptional C++Modern C++ Design 読んで C++ 信者に。そんな感じで今にいたる。

10:54 08/04/27

プログラミングと俺

なんの脈絡もなく懐古。

最初に触ったのが CASIO の FX-860P で、BASIC でした。小学2年とか3年とかの頃だと思う。最初はなんかひたすらPRINT文を並べて お絵描きしてたんですが、それをプログラミングというかは微妙なところであります。 EXE キー連打するとパラパラ漫画的にアニメーションしたりとか。 そうこうしているうちに父が簡単なプログラム(CPUとじゃんけん勝負!や、 4×4のマップ上をランダムウォークしてる敵を捕まえるゲーム、など)を作ってみせてくれたので それの見様見真似で色々。なんと5×5のマップ上をランダムウォークしてる敵を捕まえたりする。

んで数年の月日が過ぎて Mac がうちにやってきた!のでした。こんなグラフィカルなマシンなら本格的なゲーム作れる、 ってゆーか具体的にはドラクエ3クローン作れる!!と思って、プログラム組める環境入れてくれくれ君に なって親にねだったら THINK C / Symantec C++ がうちにやってきた!のでした。BASIC のつもりだったのにいつの間にか C になっててどうしようかと思いました。 てか今思ったんですけど Symanetc C++ ってことは ウォルタン のコンパイラだったんですかね、これ、もしかして。

この頃作ってたのは…当初の予定ではドラクエ3を作るはずだったんですが、なぜかいつの間にか ローグライクというかトルネコライクなターン制ゲームになってました。ローグライクというのも違うかなあ。 なんか数ターンに1匹ずつ敵が発生するモンスターハウスが何ステージか繰り返される感じ。"今のレベル≦出現順" な敵を倒すとレベルアップして使える技が増えたりするシステムだったので、できるだけ敵を出現順に倒す方が レベルアップ効率がよくて、最終的にはいかに技を駆使して敵をきっちり順番に倒すかの作戦を練るゲームに なっていったのであった。 C++ は全然つかってなくて、C を 林晴比古さんの本 で勉強して書いてたと思います。といっても、あんまりまともに勉強してなかったので関数という概念の使い所が わかんなくて、 この頃の俺は全部mainの中に書いてました。5000行くらいあったんじゃないかな。独学って怖いですねー。

しばらく前に id:haru-s さんのエントリ を見て 昔の自作ゲーム残ってるのいいなあうらやましいなあ、と思ったのですが、自分のはたぶんどこにも残って なさそうだなあ…。残念無念。

そしてまた数年の月日が過ぎて、高校に入るときに自分用に PC-9821 Ls12 買ってもらいました。Windows。今度の開発環境は Visual C++ の 4 です。 これについてきた冊子で学びながら C++ を使い始めました。ここでやっと関数の使い所がわかったよ。 この頃は物凄く3Dグラフィックしたい病にかかっていて、三角関数の勉強したり行列の勉強したり、生涯で 唯一マジメに数学を勉強した時期だと思います。んで隠面消去(という用語はその時知らなかったけど)を どうやればいいのか全く思いつかんなーと悩んで、とりあえずワイヤーフレーム3Dエンジンを自前で作るなど していました。そして数ヶ月後に DirectX というものの存在を知ったのでなんだかどうでもよくなりました。 shi3zさんの本 にはとてもお世話になりました。 隠面消去はZバッファという方法で実装されるらしい。それ考えたけどそんなもんが実際まともに動くとは思わなかった! あと COM かっこいい。 ちなみにその後 3D に関しては結局、高校の文化祭で校舎を3Dでモデリングして自由に歩き回れます! という素晴らしいけど 0.5fps くらいしか出ない酷い展示をしたっきり縁がないですね。大変ひどい。

(つづく、かどうか不明)

12:43 08/04/19

ろんぶん

CIAA 2008 通ったらしい。 (*AUTHORS*) さんの論文 (*TITLE*) が accept されましたっていう テンプレート埋まってないぞ感バリバリのメールが来ました。 初 LNCS ですドキドキです。

Inorder, no stack

https://www.cs.tcd.ie/research_groups/fmg/IFMSIG/winter2000/HughGibbonsSlides.pdf を誰も解説してくれないから

ときどきの雑記帖 i戦士篇

正直そこまで面白いこと書いてない気がするんですが適当に解説にトライ。 問題は、二分木をinorderでたどったリストを返す関数…要するにこれ

inorder(t) =
  if t == null then []
               else inorder(t.left) ++ [t.value] ++ inorder(t.right)

を「再帰なし、自分でスタック作るのもなし、各ノードにboolフラグ足すのもなし」で実装せよ、というもの。 わりとよく知られてる手続き型の解があるんですけど、それを、できるだけ純粋関数型の範囲で プログラムの変形手続きで導出しよう。

1ステップ目。これがキーアイデア。 inorder(t.left) ++ [t.value] ++ inorder(t.right) は、 inorder( t.left の右下端に {left=null, value=t.value, right=t.right} をくっつけた木 ) と等しい。

inorder(t) =
  if t == null then []
               else if t.left == null then [t.value] ++ inorder(t.right)
                                      else inorder( join(t.left, build(null,t.value,t.right)) )

build は引数3つから木のノードを作る関数。これは再帰してない。 join は木の右下端に別の木をくっつける関数。これは普通にやると実装に再帰が必要なので、まだダメ。 この join をなんとかして消さないといけません。

2ステップ目。それはそれとして、とりあえず末尾再帰にしてみた。

inorder(t, S=[]) =
  if t == null then S
               else if t.left == null then inorder( t.right, S++[t.value] )
                                      else inorder( join(t.left, build(null,t.value,t.right)), S )

3ステップ目。joinを消すための前準備として、ノードの「右側の子」を得る操作を、 直接 t.right と書くんじゃなくて、関数としてパラメタライズしてみる。デフォルトは普通に.rightを返す処理。

inorder(t, S=[], rt=(fun p -> p.right)) =
  if t == null then S
               else if t.left == null then inorder( rt(t), S++[t.value], rt )
                                      else inorder( join(t.left, build(null,t.value,rt(t))), S, rt )

4ステップ目。join(l,r) ってのは「l の一番右端のノードの "right" が r を指すようにする」 という処理でした。今"right"を取得する部分を関数でパラメタライズしてあるので、そこをいじれば、 実際のjoin処理なしで、巧くごまかしてやることができます。 具体的には、rt の代わりに「l の一番右端の子孫が引数に渡されたら r を返す。それ以外の場合はrtと同じに 振る舞う」という関数を渡してやればOK。

inorder(t, S=[], rt=(fun p -> p.right)) =
  if t == null then S
               else if t.left == null then inorder( rt(t), S++[t.value], rt )
                                      else let p = rightmost(t.left) in
                                             inorder( t.left, S, rt[p=>build(null,t.value,rt(t))] )
       where
         rightmost(p) = if rt(p)==null then p else rightmost(rt(p))
         rt[p => q]   = (fun t -> if t==p then q else rt(t))

これでjoinはinorderの中に溶け込んで消えてしまいました。使われている再帰関数(inorder, rightmost)は どちらも末尾再帰なので、これで「再帰なし」は実現できたと言っていいでしょう。 まだ問題なのが引数 rt で、これ、木を一段降りるたびに build(null,t.value,rt(t)) っていう情報を 内部に蓄えてってるんですよね。要するにスタックじゃん。てことで、次はbuildを消します。

5ステップ目。build(null,t.value,rt(t)) って、left が null なの以外は t と同じです。 なので基本的には inorder( t.left, S, rt[p=>t] ) こうしちゃう方針でbuildを消していきます。 ただし、本当にそれだけやると無限ループするので、「rtをいじってできたrightmost(t.left)--->tの辺を たどってtに戻ってきたときは、leftには進まない」ように工夫します。

inorder(t, S=[], rt=(fun p -> p.right)) =
  if t == null then S
               else if t.left == null then inorder( rt(t), S++[t.value], rt )
                                      else let p = rightmost(t.left) in
                                             if rt(p) == t then  -- ループ時はleft==nullの時と同じ
                                                inorder( rt(t), S++[t.value], rt )
                                             else
                                                inorder( t.left, S, rt[p=>t] )
       where
         rightmost(p) = if rt(p)==null || rt(p)==t then p else rightmost(rt(p))
         rt[p => q]   = (fun t -> if t==p then q else rt(t))

6ステップ目。ちょっと証明(と手続き型的に考える時)の都合により、 リストと一緒に終了時のrtも返すようにします。あと、ループから戻った時にrtを元に戻すようにします。 inorder列挙処理自体にはあんまり関係ありません。

inorder(t, S=[], rt=(fun p -> p.right)) =
  if t == null then (rt,S)
               else if t.left == null then inorder( rt(t), S++[t.value], rt )
                                      else let p = rightmost(t.left) in
                                             if rt(p) == t then  -- ループ時はleft==nullの時と同じ
                                                inorder( rt(t), S++[t.value], rt[p=>null] )
                                             else
                                                inorder( t.left, S, rt[p=>t] )
       where
         rightmost(p) = if rt(p)==null || rt(p)==t then p else rightmost(rt(p))
         rt[p => q]   = (fun t -> if t==p then q else rt(t))

これで変形終わり。純粋関数型ゾーン終わり。

で、何?

詳細は略しますが、スライドに書いてあるようにやると、 このアルゴリズムが無限ループしないでちゃんと停止することと、終了時の rt が (fun p->p.right) と 関数として等しいことが示せるそうです。

最終形は、「末尾再帰をループに展開」「rt の仮想的な変更を、実際の破壊的なポインタ差し替えに変更」を 機械的に実行すると、こんな風な手続き型プログラムになります。

inorder(t) =
  S = []
  while t != null:
     if t.left == null:
        t = t.right
        S << t.value
     else:
        -- p = rightmost(t.left)
        p = t.left
        while p.right!=null && p.right!=t:
           p = p.right

        if p.right == t:
           t = t.right
           S << t.value
           p.right = null -- rt[p=>null]
        else:
           t = t.left
           p.right = t    -- rt[p=>t]
  return S

これが完成系。これで、再帰無しスタック無しフラグ無しinorder列挙ができました。 関数型バージョンで証明された「終了時の rt が (fun p->p.right) と関数として等しい」をこっちに当てはめると、 「色々ポインタ書き換えながら実行してるけど、最後は元通りにちゃんと戻してるよ」ということが証明されてる ことになります。

07:52 08/04/16

プログラミング言語の学会
(言語オタク編)

lucille development blog さんの 『プログラミング言語の学会』 は並列化やコンパイラに焦点を当ててまとめてらしたので、 こちらは、「○○言語の△△という機能が云々!」という話が好きな私みたいなヤツ視点で纏めてみました。

大きな学会はたいてい、メインの conference に加えて、近い話題を扱う co-located workshop が何個か 併設で開かれてます。どの学会にどのworkshopが併設されるというのは特に決まってるわけではないですが、 傾向としてどれとどれはいっつも一緒にやってるよねみたいなのはあるので、適当にくっつけてご紹介。 あまり正確ではないです。

POPL

Principles of Programming Languages。 プログラミング言語全般がターゲットですが、その中でも、やや理論寄りな傾向あり。 型が型型したりするみたいな。併設ワークショップも PEPM (プログラム変換、部分評価etc)、 VMCAI (モデル検査etc)、 FOOL (オブジェクト指向の基礎理論) などなど、わりと理論理論してる。

PLDI

Programming Language Design and Implementation。 これもプログラミング言語全般がターゲットですが、どちらかというと実装寄りというか、ローレベル寄りな印象。 メモリモデルが最適化でどーとかみたいな。併設で LCTES (組み込み向け言語/処理系)、 PLAS (セキュリティのためのプログラム解析) などなど。

OOPSLA

Object Oriented Programming, Systems, Languages, and Applications。 オブジェクト指向プログラミングの学会の総本山。 オブジェクト指向ならなんでも来い的な感じ。併設で DLS (動的言語シンポジウム)、 LCSD (ライブラリから考えるソフトウェア設計)、 GPCE (メタプログラミングetc) などなど。

ICFP

International Conference on Functional Programming。 名前の通り、こちらは関数型プログラミングの学会。プログラミングコンテストで有名です。併設で ML WorkshopHaskell SymposiumErlang WorkshopScheme Workshop、 と4大関数型言語の集まりなどがあります。

そのほか

大きいのはこの4つ、だと思う。あげていくと本当にきりがないですが、 他には論理型言語の ICLP (International Conference on Logic Programming) (併設で CHR (制約解消系etc) などなど)や、 アスペクト指向の元締め AOSD (Aspect-Oriented Software Development) なんかもありますね。グラフィックスでいう EUROGRAPHICS に当たる…のかどうかわかりませんが、 ECOOP (European Conference on Object-Oriented Programming) も調べ物してて当たることが結構あります。 POPLよりももっと理論的な…例えば圏論や領域理論をバリバリと使ってプログラムの数学的意味を探る 的なのはプログラミング言語というより論理学の学会になる印象。

他にメジャーなところとしてESOP/ETAPSもあります。 あと、それほどメジャーかどうかわかりませんがAPLASも宜しくお願いします。:-)>皆様

from 住井さん。ありがとうございます!

そんな感じで。専門家の突っ込みお待ちしています。 あと、『○○の学会』まとめブームの発生が待たれるところです。

リンク集

13:08 08/04/15

malloc → HeapAlloc

Visual C++ 7.0 は小さなメモリ割り当ても全てこのヒープ API に丸投げなようですよと.

Windows のヒープ管理 - Firefox3 のメモリ使用量 (2)

うっそマジですかーと思って手元の VC2005 の CRT のソースを見たら確かに HeapAlloc に丸投げしてました。 _malloc_base → _heap_alloc → HeapAlloc。知らなかった! WinMe / VC6 で CRT を使わない縛り(笑)でコード書いてた頃は、HeapAlloc に全部渡すと場面によっては目に見えるくらい 遅かったので自前でアロケータを持つようにしてたんですけど、NT系ならそんな心配要らなかったのですね。 『ヒープ : 喜びと苦悩』によると NT4SP4 / Win2kβ2 以降のヒープは超頑張ってるらしい。

MegaTokyo

But... I don't want to be a fantasy.

MegaTokyo 5巻まで読んでから残りウェブで追いつきました。 てか、ファウストに載った ってマジですかー知らなかった!

ストーリーとか登場人物の紹介は wikipedia にある通りで、アニオタのPiroとゲーオタのLargoがひょんなことからメガ東京のメガゲーマーズに 住み着くことになって、ドタバタするお話。かと思ったらPiroの側はヒロイン5人くらいでてきてsnegな展開になる。 なるんだけど一方、重度のゲーム脳(笑)ということにされてるLargoの側は、 メガ東京を闊歩するゾンビ軍団と脳内で戦ってることになってて相変わらずドタバタ。 と思いきや、この世界では本当にそういうのも「アリ」ってことにだんだんなってきて、 "Retired Magical Girl" と "L33t Ninja" が 空中戦 を繰り広げはじめたりする。でもその真横で普通にベタベタのラブ話が展開されてたりして、 こう、なんというか、Magic(al girl) Realism とでも呼ぶべき感じの不思議な世界になってます。 メインキャラ7人のほとんど7C2通りの組み合わせでストーリーがある感じなんだけど、 同じページ内、下手すると同じコマ内で並行して複数の筋を進めてくるのも巧くて面白い。

※追記: Chapter 0 の前半はその後とちょっと雰囲気が違うので、 途中で挫折しそうになっても Chapter 1 まではたどりつくべし!

17:26 08/04/10

PPL 2008

PPL2008の論文が公開 (via 酒井さん) されたそうなので読みまくっています。

『Konoha: ハイブリッドな型検査システムを備えたスクリプティング言語』: Konoha という言語について。 表題になってる型システムについてはあまり興味わかなかったのですが、 二つめのトピックになってる "run anytime" compiler っていうの、 これ地味に凄く便利じゃないですか。コンパイルエラーになったら、当然そこでエラー表示はするのだけれども それはそれとして、エラー箇所を実行時例外を投げるコードに置き換えることで、コンパイルは 続行して、とにかく実行可能な出力を生成するという。 型の inconsistency の回避方法 とかとも関係する話題だと思うんですけど。 実行に少々時間がかかるプログラムを実装してる途中や、 あるいはC++やHaskellみたいにコンパイルが遅い言語を使ってるときなど、 「テスト実行とコーディング」あるいは「コンパイルとコーディング」を並列実行してしまうわけですが、 そうすると「さっきのコンパイル&テストランの間に機能Aは実装できて機能Bは実装途中。 即座に次のコンパイル&実行タスクを走らせて機能Aの確認したいけど、今やると機能Bのとこで コンパイルエラーになっちゃう面倒だなあ」という事態が頻繁に発生するので、これが回避できると便利だ。 parse error までこれで救ってくれると嬉しいんだけどそれはさすがに無茶な希望かなあ…とりあえず Konoha 使ってみなきゃ。

『Efficient flonum handling on a stack-based VM for dynamically typed languages』 と 『Ruby処理系での軽量な浮動小数点数表現』: それぞれ Gauche と YARV のインプリメンタによる、Float を全部ヒープに置いてるのは色々無駄なので どうしたらよいかというお話。Shiro さんのは、いわゆるスタックマシンのスタックに加えてFloat値を 置いとく用の"arena"という領域を用意しておいて、計算途中のテンポラリな Float は(ヒープではなく) arena に配置。外に逃げるヤツだけあとでヒープに移す。Floatオブジェクト自体の表現は、実体へのポインタと いう形で変わらない。笹田さんのは、IEEE754のビット表現をうまいことハックして、オブジェクト自体の表現である VALUE に Float 値を埋め込むことで、IEEE754のフルの精度が必要ない値は間接参照なしで使えるようにする。 ふむむー。 なんか直接論文と関係ない感想なんですけど、笹田さんが関連研究として参照してらした Typed Virtual Addressing というの知らなかったんですがこれ発想が格好いいな。アドレス空間広ければ「この型はこの辺りのアドレス」 みたいに型ごとにアドレスを分けちゃえばアドレス値に型情報埋め込めたことになるじゃん!っていうの。ほへー。

『index長に依存した長さの先読みを行う構文解析器生成系』: インデントが意味を持つ文法をダイレクトに記述するのは文脈自由文法じゃ足りないんだけど、 Indexed Grammar(文脈自由文法の終端記号にスタックを引数として渡せるようにして スタックトップによって分岐できるようなもの)の制限バージョン(スタックじゃなくて単に自然数 s(s(...s(z)..) だけ渡せる)辺りを使ってみるとどうよ?という提案で、そういう文法に対するLL風の 構文解析器を作ったというお話。 また直接内容と関係ない感想なんですけど "提案する構文解析器生成系はD 言語を用いて実装を行った。" というのが大変素敵でした。公開されないのかなー。

13:06 08/04/10

ICPC

最終結果 でてますね。 選手のみなさんおつかれさまです! 相変わらず、ロシア勢の頭のなかはどうなっているのか…

[PDF] 問題文。 解かれ具合を見るに、簡単な方から F < K, B, J, A, I <<<< G < E <<<<<<<< C,D,H なのかな。パッと見 E が面白そう。あとで考える。

10:49 08/04/09

Hash + C++

ちゃいます

いわゆるハッシュは <unordered_set> / <unordered_map> として標準化され て…ると言い切るのはアレですが、 中身はこれで固定して次の標準に入るのは確定、というステージにはなっていて、 gcc にしろ vc にしろ、おおむね標準に合わせて実装済みです。で、unordered という名前からわかるように、 常にソートした状態のデータ群も持っておかなきゃいけない ってことは決してないです。標準化前の各ベンダの独自実装(<hash_map> 等) もそういう仕様でした。

二分木とハッシュの速度差に関しては…VC7のhash_mapは実装が酷すぎるので忘れることにして、 最近の επιστημη さんの記事『BoostでC++0xのライブラリ「TR1」を先取りしよう (5)』 が自分の体感とだいたい合ってる感じがするなあ…と思いました。 つまり、「100万要素くらいのオーダーで使うと、ハッシュの方がやや速い。 再ハッシュ頻度等考えて使うと、まあ結構速い」くらいの感覚。 感覚なので適当ですが。

でも、実は細かい数値はどうでもよくて。 「連想配列」はどう実現すべきか、 問題は速度ではないです。

「二分木は、要素同士の大小比較 < が定義されてる時しか作れない」 「ハッシュ表は、要素同士の等値比較 == とハッシュ関数 hash が定義されてる時しか作れない」 ので、そもそも格納できる要素が違う。 Java でいうと、TreeMap に入れるには compareTo を実装する必要があるし、 HashMap なら equals と hashCode を実装する必要がある、と。 (※ VC++ の hash_set やD言語の連想配列なんかのように < と hash を使うものも ありますが、そうでないものの方が一般的と思う)

一概には言えませんが、==(と hash)は、どんな型に対しても(型の違うオブジェクト同士の比較であっても) 比較的自然に定義できることが多いですが、< は必ずしもそうではありません。 なので、キーにできる要素の種類が多い、というところに 「連想配列」を「ハッシュ」で実装する意味があると思うのです。

追記

shinhさんのベンチマーク

hash_mapの実装が…というのは この辺 など。頑張ってるのはわかるんだけども変な方向に頑張っちゃった感が。

お誕生日

おめ

20:31 08/04/06

DST期の終わり

今日は一日が25時間あるみたいです、っていうと不思議な感じだな。 UTC+11 → UTC+10 になりました。 ちなみに私はうっかり時計を逆向きにずらしてしまって午前中混乱してたなんてことは決してありませんが、 ノートPC=Windowsが自動で合わせてくれるので正しい時間、携帯電話=手でサマータイムのON/OFF設定しないと いけないのを忘れてて1時間ずれ、腕時計=なぜか2時間ずれ、という時間にとらわれない生活を送っていました。

予定では逆向きの切り替えは経験しないで帰るんだよなー。ちょっと残念。

Unmisusability

そんな単語はない、けど。

「よい設計とは何か」の、自分の中での評価基準は2つあって、一つは平鍋さん提唱の 「EoT (テスト容易性) の高い設計」なのです。 そしてもう一つが、「誤用不可能性」とでも言いましょうか、 「使い方を間違えることができない」ものほど良い。

例えば「使い終わったら最後に必ず Close メソッドを呼んでください」みたいなのは良くない。 「うっかり Close を呼び忘れることができる」から。 逆に例えば Ruby の ブロック付き open みたいな方法だけが提供されていたとすると、あえて狙っても ファイルを閉じ忘れるのは難しい。

二重の否定語を除いて「Usability (使いやすさ)」と言ってしまうと、なんか違うんですよね。 例えば Haskell や OCaml のパターンマッチ。あれは全パターン網羅しないことも言語仕様的に許されていて、 実際その方が使いやすいからそうなってるわけですけど、でもこれは 「うっかりパターン列挙し忘れることができる」。絶対全パターン網羅しないといけない 仕様なら、間違えて Match_failure を飛ばすことは不可能だ。だからその方が良い、と思う。

全部この方針を貫くべき、とは思いません。適当に妥協しないと…実際Rubyでファイルを開く方法が ブロック付きopenだけだったら困りますし。パターンマッチも、ここにはこのパターンしか来ない、 とプログラマがわかっているときは省略したいですし。まあ、でも、傾向として。 (余談ですが、Ruby や C# や Python や D にある 「スコープの終わりで確実にオブジェクト破棄」タイプの機構に加えて、「親オブジェクトの寿命の終わりで 確実に子オブジェクト破棄」を強制する機構があれば、っていうか要するにC++ならってことですけど、 ここで妥協せずにかなりやってけると思ってます。)(パターンマッチも Dependent Type とかで "省略可能とわかってるんだったらそれをコンパイラにわからせるような型をつけろ" 方向に進むと 妥協しなくてもよくなるのかもしれない。)

なんとゆーか「使い間違えられるものなら使い間違えてみやがれ!」くらい言ってもらえると、 安心して使えるじゃないですか。あと、「正しい使い方」を覚える必要がないので何も考えず使える。 楽ちん。

……というようなことを、Boost.Proto のドキュメントに "cannot be misused" の3語を見つけて徒然考えてみたり。

18:13 08/04/04

ぶすーと

Let's Boost を 1.35 に合わせて更新しました。 MPI なんて触ったの5年ぶりであるよ。

あと Boost といういうと最近MLで話題になってた Geometry Library が気になってます。まだ色々足りてないような感じですが、 これはかなり使いたいかもしれない。

ACM-ICPC

そんな季節かー。 がん ばっ くだ さい!

09:18 08/04/02

いろいろ

ゴルフ は今 38B です。 37になりそうな気がしてならないのだけど。

今見ても シナリオライター陣 が エイプリルフールにしか見えないこれはやばい!!!!!!!111

昨日のネタ

数日前の 郵便はみがきさんの記事 で「コールスタック」って文字を見て、ふとキューにしたくなったのでやりました。

単にキューにするだけなら 1.部分継続のある言語でホントにキューを作る 2.普通の継続でエミュレートするのもそんな面倒でない 3.インタプリタ実装するなら 仮想マシンへのコンパイルでやる、のが簡単なんですけど、「せっかくだから4/1のネタにしよう」 「するとキューの動きを途中で止めて見られるようにしないとわかりにくい」 「評価を途中で止めるなんて Dissection のためにあるようなネタ じゃないか!」 と思っちゃった上に CSB 等のせいで気づいたら 土日が終わっているなどしたために、すごい中途半端になっちゃいました。 実装も結局穴あき構文木をたどりまくるだけの代物で。 動作をイメージしにくい のは明らかに可視化に失敗してるせいですすみません全部ロードカオスが悪い。

一応 解説記事 として補足しておくと、

04:01 08/04/01

Я9Я∽

Scheme は、末尾再帰の扱いや、第一級の継続など、 関数呼び出しフローの繊細な扱いに定評があるプログラミング言語です。 最新の言語仕様である Я9Я∽ でも、この方面がさらに強化されています。 軽くご紹介。

コールキュー

Я9Я∽ 最大の特徴は、なんといっても、関数呼び出しをスタック (LIFO) で管理するのをやめたことです。 全部キュー (FIFO) でやります。fがgを呼んでgがhを呼んでhがreturnすると、 スタックならgの続きが実行されますが、キューなのでfの続きが実行されます。 もはやスキームというよりスキュームです。Я9Я∽ なだけに

キューになると嬉しい例として、リストの逆転処理を Я9Я∽ で書いてみましょう。

(define (reverse lst)
    (if (null? lst) ()
                    (cons (car lst)
                          (reverse (cdr lst)))))

(reverse (list 1 2 3))

できた! スタックを使う従来の仕様では、reverseは、リストの結合処理 append を補助関数として定義するか、アキュムレータを使った二引数の補助関数を作るか、 いずれにせよ関数1つでは書きにくい処理でした。Я9Я∽ では、cons と car と cdr と再帰だけで、補助関数要らずで綺麗に書けています。

※ 右にJavaScriptで書いた簡単なインタプリタをつけました(IE6とFx2で動作確認)。 [Start] を押すと実行開始します。コールキューの動きを見やすくするため、 関数呼び出し直後と、return直後に止まるようにしてます。[Next] を押すと次に進みます。 ------- より下が現在実行中の関数の内容で、上がコールキューです。 コールキュー内の <> は、その位置で関数を呼んだことを表します。 組み込み処理cons/car/cdr等は関数として扱ってないので、上の例の場合は reverse 関数の呼び出しだけがコールキューに出てきます。

・(cons 1 <>)・(cons 2 <>)・(cons 3 <>) とコールキューを積んでから、 スタックならば逆順に 3, 2, 1 と戻りながら cons を実行するところですが、キューなので 1, 2, 3 の順で cons を実行して、結果 reverse が実現されてます。

フィボナッチ!

スタックがキューになると、今までに作った関数が全然違う動きをするようになるのでは…? とご心配の方もいらっしゃるかもしれません。でも大丈夫、多くの関数はスタックでもキューでも 同じ答えを返します。例として、フィボナッチ関数を書いてみました。

(define (fib x)
    (if (<= x 1) 1 (+ (fib (- x 1)) (fib (- x 2)))))

(fib 5)

これは 8 になります。コールスタックでも同じ結果になるのはみなさまご存じでしょう。

マップ!

他のサンプルとして、リストの各要素に関数を適用する map 関数はどうなるか。 これもフィボナッチ同様、コールスタックの時と変わりません。

(define (map f lst)
    (if (null? lst) ()
                    (cons (f (car lst)) (map f (cdr lst)))))

(define (dbl x) (+ x x))

(map dbl (list 1 2 3 4 5))

結果は (((((2 . 4) . 6) . 8) . 10) . ()) になりますが、 Lisp 使いには括弧は空気のようなものなので、目に見えません。 これは 2 4 6 8 10 というリストです。 実はこのmapのポイントは、計算結果ではなく 計算過程にあります。右のJavaScriptで[Next]を連打していただけるとわかりますが、 コールキューの深さが一定範囲にとどまっています。 実は、リストの長さがいくつであろうと、コールキューの長さは常に3段以下になります。 つまり、末尾再帰じゃない実装でも、深~い再帰をしちゃって大丈夫! オーバーフローしないのです。素晴らしい。

付録

インタプリタのソース
→ 戦略切り替え: Queue Stack
 ([Start] 時にどっちにスイッチが入ってたかでこのページのサンプルの動作が変わります)

presented by k.inaba (kiki .a.t. kmonos.net) under CC0