fixの話 … Perl版、 Perl版、 C++版、 C++版、 Scheme版、 Concurrent Clean版。 （9/4追記: Ruby版、 Erlang版、 Squeak版、 D版。 Sukuna版。 Erlangのprocessを使ったメモ化の例は見てみたいかも。）。 で、 メモ化の話 … Python版、 Python版 （9/4追記: ET版、 Erlang版、 Java版、 PostScript版。 ）。 decoratorは流石かっこいいですね。C++版は…うーん、個人的には、このくらいなら Boost に頼らないで直球ストレートで書いてあげたいところです。 彼はやればできる子なんです。
template<int (*G)(int(*)(int),int)>
int fix(int x)
{
return G( fix<G>, x );
}
#include <map>
template<int (*G)(int(*)(int),int)>
int fix_memo(int x)
{
static std::map<int,int> memo;
return memo.count(x) ? memo[x] : memo[x]=G( fix_memo<G>, x );
}
int fib_maker( int(*f)(int), int x )
{
return x<=1 ? 1 : f(x-1)+f(x-2);
}
#include <iostream>
void test()
{
int (*fib)(int) = fix<fib_maker>;
for( int i=0 ; i!=10 ; ++i )
std::cout << fib(i) << std::endl;
}
直球ストレートといいながらfib_makerをuncurry化するという変化球を投げてますが、 意味的には変化ないので、ということでお許しを。関数テンプレートをテンプレート引数として 使えるようにC++の仕様が変われば、fib_makerの第一引数はテンプレート引数に 追い出せます。あるいは fix も fib_maker も全部関数オブジェクト化してしまえば、 そのまま下で私の書いたJavaScriptと同じ形にできます。 （→こんな）
ダメぽ。
スピード勝負では絶対100位に入れない自信があるので、いずれにせよ1000点問題を 解かねば勝てない…と踏んでいきなり最難問に突撃 → 40分経過 → 解き方わからん → 0点は格好悪いので300点問題解いとくか、みたいな流れで、こう。 …って、あと300/450点で足りたんか。 作戦ミスったああぁー。
250位以内だから通ったは通ったぽいんだけど … ちょっと幾らなんでもそりゃないだろレベルの酷いコードを連発してしまいました。 撃墜タイム（仮称。コーディング時間終了後に、他の参加者のコードを見て、間違いを 指摘できたらポイントGetできる時間）に他の人のコードと比べて死にたくなったorz。 特に250点問題の自分のソース、ギャグとしか思えない。笑える。ぷぷぷ。
下の記事は色々と別方面に思考を巡らせたせいで回りくどくなっちゃいましたが、 それぞれの要素はどれももっとお手軽にいけます。汎用メモ化関数だけを JavaScript で普通に書くならだいたいこんな感じでしょう。 beyond.jsにもあるらしい。 PerlだとMemoize.pmなど。
function memoize(f) {
var memo = {}
return function() {
var x = Array.prototype.join.call(arguments)
return x in memo ? memo[x] : memo[x]=f.apply(this,arguments)
}
}あとfix関数は遅延評価のできる言語ならシンプルに
fix g = g (fix g)で。遅延評価なしでもカリー化があれば
let rec fix g x = g (fix g) xとか。補足終わり。
さようなら。わたしの愛した曲がり角。
マンガの話でもしてみる。最近は『Dance Dance Dance!』がマイブームです。１巻が出たときに本屋で見かけた、 上に引用した惹句が気になって帯買いしました。なかなかスロースタートな物語で ２巻に入らないと展開が全く見えてこなかったですが、守りたいものは "町" の未来であり "美しい町" である… っていう物語の骨格が見えてきて、面白くなってきた感じです。 "世界" のような曖昧なものではなく、"町"。…なんか自分では上手く書けないんですが、 検索したら見事な書評があったので激しく同意しつつリンクしときます。
あと、主人公がすごく赤毛のアンっぽくて、他のキャラも含めて全体的に そのまま世界名作劇場へ持っていけそうな雰囲気も好きだったり。
任意の再帰的に定義された関数をメモ化(memoization)する関数、というのは、計算量と 高階関数が好きな人なら誰しも書いてみたくなるものです。 高階関数と来たら関数型言語…と思いがちですが、 Haskell や OCaml での実装は、これはちょっと美しくない。どの方法にしても、memo化される側の 関数を普通の再帰定義とは多少違った形に書き換えなければならないのが、不自然です。
これは、Haskell や OCaml では副作用を特別な形でしか扱わない（よーするに、 変数への"代入"ができない）ことが原因で、他の言語なら例えば cipher や Io のように fib の中身を一切書き換えずにmemo化ができてハッピーな感じになります、と。
で、私は副作用を普通に扱える言語の方が好きなので、ここで終わろうかとも 思いました。が、「memo化される側の形を書き換えるのが不自然」と言い切ってしまったのが 気になるので、しばらく徒然なるままに考えてみました。あれは逆に、ある意味 自然な形に書き直しているとも言えるのではないかと。
HaskellやOCamlで外からのMemo化を実現するために、具体的にどんな書き換えが 必要になるかというと…再帰関数としてフィボナッチ関数を考えると、こんなです。 例によってコードはJavaScriptで。（使うのやめるんじゃ なかったんかという突っ込みはナシの方向で。）
// 普通のフィボナッチ関数の定義
// function fib(x) {
// return x<=1 ? 1 : fib(x-1)+fib(x-2)
// }
// メモ化しやすい定義
function fib_maker(f) {
return function(x) { return x<=1 ? 1 : f(x-1)+f(x-2) }
}
もともとの定義はfibの中で再びfibを呼んでいる、いわゆる再帰的定義でした。 書き換え後は再帰が消えた代わりに、関数を受け取って関数を返す、高階関数に なってます。何か「関数f」を受け取ると、「フィボナッチっぽく、ただし中でfを呼ぶ 関数」を返す関数。「元の定義では中ではfibを呼ぶ」と固定されてて、fibを 後で書き換えられない関数型言語では手が出せなくなっていましたが、その部分を パラメータ化すれば、再帰的に中で呼び出すfにもメモ化版fibを指定できるように なるわけです。（詳細は上の方のリンク先参照）
ところで実は、このfib_makerというのは、数学的にプログラムの意味論を考えるときに 重要な意味を持っています。fibという関数の意味は『fib_makerの最小不動点 （※不動点：関数に通しても値が変わらない値のこと。例として、 square(x)=x2の不動点は0と1。）』なのである、と定義するのが 常套手段なのです。 ここの606 参照。 つまりこの書き換えは、memo化のためにポッと出たものではなく、再帰関数の意味に さかのぼるという自然なやり方なのかも、とも思えてきたのでした。
ちなみにfib_makerなど再帰関数を定義する関数を渡すと、その不動点を計算する関数、 なんてものもプログラムとして書くことができて、こんな風になります。こうやって 定義したフィボナッチ関数はちゃんと普通に使えます。
function fix(G) {
return G( function(x){ return fix(G)(x) } )
}
fib = fix(fib_maker)
print( fib(1), fib(2), fib(3), fib(4), fib(5) ) // 1 2 3 5 8
そしてfixの定義をもーちょい読みやすくしようと変形したら、こんなん出ました。
function fix(G)
{
function f(x) { return f(x) }
f = G(f)
return f
}自分で書いてて意味が30秒ほど理解できなかったのですけど。なんだコレ。
冒頭でリンクしたHaskellによるmemoizationの記事に「この部分を見ると、
memoise が特殊な ($) に見えてきませんか。
」という一節がありました。
$ は Haskell の関数適用演算子です。f$x は f x
（JavaScriptで書くなら f(x)）と同じ。
これを頭に入れてから見直してみると、
function fix(G)
{
function f(x) { return f(x) } // $…fにxを適用するということ、の定義っぽい
f = G(f) // Gの不動点だと主張してるっぽい
return f // それを返してるっぽい
}強引ですがそれっぽく見えてきました。よし。更にここで関数適用の定義っぽい部分を、 メモ化するっぽく変更すればメモ化されたフィボナッチができます。
function fix_memo(G)
{
// メモ済みだったらその値を返す。未メモだったら普通に適用して結果をメモ
// …というmemoization的$を定義しているっぽい
var memo = []
function f(x) { return x in memo ? memo[x] : (memo[x]=f(x)) }
f = G(f)
return f
}
fib_memo = fix_memo(fib_maker) // 高速fibの完成
関数適用の際には引数と返値を表示するように定義してみると
function fix_memo(G)
{
// デバッグプリント付き関数適用っぽく
function f(x) { print("call-"+x); var r=f(x);
print("retn-"+r); return r }
return f=G(f)
}
fib_debug = fix_debug(fib_maker) // うるさいfibの完成
もちろんfixやfix_memo、fix_debugは、fib_makerに限らず他のmaker関数にも 全く同じように適用することができます。なかなか面白い。Googleってみたら このテーマで論文書いてる人もいたみたい。一応注意しておかないといけないのは、 メモ化にしろデバッグプリント挿入にしろ副作用があれば*_maker化しないで 直接変換関数は作れるってことですかね。ただ、プログラムの意味を理論的に 考える場面で、この*_makerとfix_*ていう分離組み合わせには、何か使いどころが あるのではないかと、ちょっと妄想してみました。
ところで、改めて上のfix_*がやってることを見ていると、どうもアスペクト指向 っぽい気がする。「プログラム＝*_makerの集合」「アドバイス＝fix_*」 「アスペクト＝*_makerとfix_*の関連付け」とかいう意味論はどうだろう。 どうだろうというか、自分はアスペクト指向言語の意味論を全く知らないので、 普通に当たり前かもしれない。普通にダメダメかもしれない。うーむ。
一身上の都合によりRound 1以降は参加できないかもしれないのだけど、 とりあえず結果。去年さんざんミスったので今年は よーく見直してからSubmitする方針で。多少遅くても全問解ければ大丈夫 …… って危ねー。
幽仙庵で震災時帰宅支援マップの話題があったので反応してみる。
前に立ち読みしてみた感想では、 この地図は震災時に限らず、普通に東京圏を歩き回るのにかなり便利そうと思いました。 "進行方向が常に上"の地図は目的地が決まっているときにはやっぱり便利だし、 ルート上で目印とすべき建物についても記載されていて、普通の地図よりもずっと 迷いにくくなってます。あと、次に休めそうなポイントの情報も載っていたりして。 災害時の備えとして…などと考えなくても、歩き回るのが趣味な人が、 初めて行くルートのお供に持って行くには適したアイテムではないかと。
先日、ノートPCを買い換えました。「64bit機」「A4以下」「2Kg以下」 という条件で探したらドスパラの Cressida64 しか見つからなかったので、これで。さらにWinXP x64版モデルを選べたので、迷わず導入。
内蔵の無線LAN機能はまだドライバがなくて使えないとのことだったので、この辺で動いたと書かれていた バッファローのカードを買って挿してみたら無事動作しました。プリンタ・スキャナの ドライバも揃いが悪い、と店の人には注意していただいたのですが、駄目元で 我が家のDeskJet 815cを試してみたらこれも普通に印刷OK。懸念のハードウェア周りは 完璧セーフでした。ソフトウェア面では、msysのsh が動かないのに一瞬焦りましたが、リンク先に書かれていた workaround で回避。 あとは32bitシェル拡張はダメで、他はほぼ問題なく動く、と、想定どおり。折り窓が 普通に動いたのだけは逆に予想外でした。
で、なんでそんな微妙に苦労しながら64bitにこだわったかというと、「32bit環境では もういい加減ファイル操作するプログラムを書くのが面倒だから」が主な理由。例えば XacRett の .dmg 展開ルーチンはまずファイルに埋め込まれた特定 のXML文書を探して、その部分をParseしつつ一部base64デコードしてデータ領域 のOffsetを取得したらファイルのそのOffsetから始まるHFS+ファイルシステムのヘッダを 読みとりつつページへの間接参照を辿って実データを取り出していて、つまり 何がいいたいかと言うと、ファイルアクセス用のAPIとして一番よく使われている「fseek と fread」型の方法（seekで"ファイルポインタ"をファイル中の好きな位置に移動して、 readで"ファイルポインタ"から指定文字数読み取る、系の方法）ではあんまり 書きたくない作業だった、ということなのです。
もちろん seek/read をラップして、配列っぽくランダムアクセスできるライブラリを 書くことは簡単です。でもそれは非効率的ですし、そもそも大抵のOSではファイルを直接メモリ にマップできるわけで、これを使わない手はない。というわけで XacRett もメモリマッピングで実装しました。
ただし問題がひとつ。32bit Windowsでは、そもそもユーザー用アドレス空間が (たしか) 2GB しかない。つまり、2GB以上のファイルの全体を一度にメモリ空間に マップすることは不可能なのあります。もちろん mmap をラップして巨大ファイルでも ランダムアクセスできるライブラリを書くことは簡単です。でもそれは非効率的ですし、 そもそも64bit Windowsなら仮想メモリ空間は16TBもあるわけで、これ使えば なんにもややこしいこと考えなくてよくなるじゃん！やった！
つーわけで64bitなのでした。
↓↓そんな日記を書いた次の日に読売が勧誘にやってきたこの不思議。
ふらふらと Google でさまよっていたら Al Zimmermann’s Programming Contests というページにたどり着きました。 自明な最適解があるたぐいの問題ではなく、できるだけ良い解を出したほうが 良いスコア、という得点形式のコンテスト。どの問題もシンプルかつ面白くて いいですね。暇を見つけて解いてみよう。
しかし、プログラムを組むとき、これまでは言語の制約が特にないならいつも JavaScript を使っていました。が、最近は言語としての面白さという 意味での JavaScript もブームっぽい感じがするので、ひねくれ者としては 逆に使わないで行きたくなってきます。
…とかいいながらGreaseMonkey/Trixieスクリプトを書いていたりするのでした。
駄目じゃん。でもこれ、便利ですな。MM/Memo の recent ページのうちコメントが
ないエントリの文字サイズを半分にするとか、freettにポップアップ広告を
出させないようにするとか(既にありそう)、target="_blank"
を潰すとか(既に絶対ある)、試しに作ってました。便利便利。
20日から、朝日新聞の夕刊で北村薫の連載小説が始まるらしい。『さて、どうにも
ならない障害があるため愛が一層輝く ――といった物語は数多くあります。
そういう「形」を、読者の涙を絞るためのあざといものと眉をひそめる人も、
多いと思います。ところが、そうした人間関係の「形」も、現実には泣けるだけの
ものではありません。そんなところを見つめながら、書き始めようと思っています。』
ということで、その「形」をどう表現してくれるのか、期待です。わくわく。勧誘員の
ひとは今うちに来れば確実に購読するのに、もったいないなあ。
しばらく前に会った方の帰り際に、「Noah作ってるinabaさんですよね、実は自分も アーカイバを作ってます」と話しかけられたことがありました。その時はまあ「はい そーです」と答えたわけです。で、よく考えたら、なんてアーカイバを作ってる方なのか 訊き忘れてました。なんてこった。検索してみたら発見できたので、えーと、その節はどうもでした。