"with" loss of generality

07:13 04/08/31

情報元は失念…。 「釜井たちの夜」 というソフトがとても面白いんですけど! どういうものかはリンク先の スクリーンショットを見ると一発でわかると思いますが、もう、思わず 朝っぱらからカメラの前をうろうろしてしまいました。

14:02 04/08/25

Wittgenstein

shelarcyさんに紹介いただいたので『認知意味論』 を読んでみようかと思います。ありがとうございます。著者名に見覚えがある…と思ったら、 昔、同じ人の共著『レトリックと人生』を読んだことがありました。

4段目

これで最後。

左の山は雑誌とか通販のカタログとか学会のproceedingsとか楽譜とかのデカブツ。

と、我が家の本棚はこんな感じになりました。冊数的には今までに自分が読んだ本の一割にも 満たないですが、80-20の法則にのっとると、自分の4割はこいつらで出来ているような 気もします。

00:58 04/08/25

最上段

すぐ増えて二列になりそうだけど、現時点では一列だけ。

再びマンガのみ。どれもこれも大好きなシリーズ達です。どれもこれも 人によって好き嫌い分かれそうですが…。右から

00:51 04/08/24

2段目

趣味の棚。

右には辞書的なものを集めました。語学関係が幾つかありますね。 ちなみに戦歴を書いておくと

左はドラクエⅢゾーン。ゲームボーイ版の公式攻略本買ってないや…。

手前も引き続き趣味の棚。

17:50 04/08/23

3段目

本棚の整理をしていると片っ端から読み返してしまい、ふと気づくと日が傾いているのでした。

小説類その2。ラノベが多い。

小説類その3。手前には、今の自分がもっともハマってる作家さん達の本を。 どれも全力でオススメです。文庫と単行本が混ざってるのは購入時期の問題で、 文庫が出てたら基本的に文庫を買ってます。右から順に…

20:31 04/08/22

5段目

スペースの都合上、二列で置くことにします。

奥にはマンガ。取り出しにくい場所であることを考えて、今の自分の趣味とは 微妙に離れてきてるシリーズを配置。なんかガンガン系ばっかですね。

手前にはSF系の本などを。中途半端に揃った星新一と、中途半端に揃ったアシモフの ロボットもの。写真撮ってから気づいたけど、ファウンデーションものが一組混じってる…。 『宇宙の旅』シリーズはバイブルです。『火星年代記』は星新一の 影響で買って読んでみて面白くてはまった本。他も『夏への扉』に『リプレイ』、『たったひとつの~』など など、名作と言われるものはやっぱり面白いです。定番ばかりで本棚晒しとしては 面白くないですが…。他に、持っていないけど好きなSFである『百万年の船』を 買おうかなと考え中。

16:31 04/08/21

最下段

とりあえず一番下の段を埋めてみました。

背の高い本を全部ここに。ほとんどがコンピュータ関係ですね。背表紙の色でまとめて 並べてみたのですが、『Generative Programming』(右から7冊目)が実にいい仕事をしています。むしろ、 それがやりたくてこの配置だったりします。右から順に軽く紹介…

さて、あと5段をどう埋めるか。

16:31 04/08/21

緊急

なんか騒がしいと思ったら、四軒となりが火事だー!

02:00 04/08/21

ちまたでは本棚.orgが人気ですけどその流れとは全く関係なく、 我が家にリアル本棚がやってきたー!

無精なもので引っ越してから5ヶ月の間段ボールから本を掘り出す日々を 送ってきましたが、やっと部屋にならべておくことができます。さて、 どういう順に置こうかな…と悩むのがこれまた楽し。

22:51 04/08/17

黒白赤青黄

昔は山手線の目黒目白ってどっちがどっちだったかすぐ間違えてしまったものです。最近はまあなんとか ようやく覚えましたけど、たぶん…。それはともかく、『新・歩いて見よう東京』というのを読んでいて、実は東京に5色、 目黒不動・目白不動・目赤不動・目青不動・目黄不動と存在することを知りました。 今度巡ってみようと思います。あと、この『新・歩いて~』は、一週間かけて 様々な切り口で東京を歩くルートの紹介で、なかなか面白いです。

継続の話の続き

一週間前の自分がメモを残してたのでコピペ。Continuationのヤな所とか。

fからthrow

前回は、継続というのを「fからreturn」として説明しました。

function f() { return 0; }
function g() { var k = new Continuation();
                   k(0); }

ところで、最近の言語では関数から抜けるにはreturnの他に、例外のthrowという 可能性もあります。ということは、「fからreturn」の他に「fからthrow」も Continuationオブジェクトを通してできると自然。

function h() { throw "Error"; }
function i() { var k = new Continuation();
                   k(new ContinuationException("Error")); }

Rhino w/cだとこんな感じに、ContinuationExceptionという特別なオブジェクトを 突っ込んだときだけ特殊処理になって、returnではなくthrowで戻ります。 あんまりこの書き方は好きでないのですが、そういうものらしいです。たぶん 他の言語だともっと別の書き方があるのではないかと思います。

いつも何度でも

一見何の変哲もない、ファイルを開いて、一行ずつコールバック関数に 渡していく関数。

function file_iter( filename, f )
{
  var fp = open_file( filename )
  while( str=fp.read_line() )
    f( str )
  close_file(fp)
}

でも、言語の機能に "継続" があるのなら、それを考慮して考えてみないと いけません。例えば次のような使い方をされると?

var global_k = null
function evil_f(s) {
  if( !global_k )
    global_k = new Continuation()
}

file_iter( "test.txt", evil_f )
global_k() // !!

global_k() のところで最初のevil_fの呼び出しから帰る地点に戻って しまうので、1回のopen_fileに対して2回close_fileが呼ばれてしまいます。というか それ以前に、既にclose_fileされたファイルに対してread_lineを呼んでしまいます。 こんな風に継続がからんでくることで、ユーザ側の関数を呼ぶときはそこでどんな風に 継続が捕まえられる可能性があるか、まで考慮しないと全ての実行順序を予想しきれなく なってしまいました。

純粋関数型に書いた関数なら同じ式が何回呼ばれようが全然OKなはずで、 その場合はこの点は問題になりません。またそうでなくても、「そんなヘンな 関数を渡す方が悪い」と決めてしまうのも、まあありでしょう。

呼ばれないfinally

というかそもそもさっきのサンプル、継続なんか持ち出さないでも、fが例外を 投げる関数だった場合、正常にclose_fileが行われる保証がどこにもありませんでした。 こういう時には、finally節を使って必ずコードが実行されるようにしないといけませんね。

function file_iter( filename, f )
{
  var fp = open_file( filename )
  try {
    while( str=fp.read_line() )
      f( str )
  } finally {
    close_file(fp)
  }
}

finallyは、try節がどんな終わり方をしようとも、必ずclose_fileを読んでファイルを 閉じてくれるという働きをするスグレモノです。これを使いこなすことで、ファイルを 開きっぱなしにしてしまうバグなどは激減します。さてでは、このfile_iter関数を、 前回のas_iteratorを使って外部イテレータにして使ってみましょう。

var it = as_iterator( function(f){file_iter("test.txt",f)} )
print( it.Current ); it.moveNext()
print( it.Current ); it.moveNext() // 二行表示

…いつ、ファイルが閉じられるのでしょう?ファイルが三行以上あった場合、 try中のwhileループがまだ終わっていませんから、finally節もまた実行されません。 このままイテレータitを使わないでプログラムが進んでいってしまったら、いつまで たってもファイルは閉じません。必ずファイルを閉じてくれるはずのfinallyが、 まったくもって役立たずです。

finally → finalizer

問題は、本来finallyの実行タイミングは「try節から抜けるとき」ではなく、 「今後try節の中身が二度と実行されなくなるとき」であるべきであった、という 点にあります。今回の例ならば、イテレータitがどこからも参照されなくなった瞬間に、 finallyの中身が実行されるべきです。

というわけで次善の策として、「GCが継続オブジェクトを回収する時に、その 継続に付属したfinnaly節を全部実行」という仕様にする手があります。GCによる 回収はいつ行われるかわからないという欠点があります(ユーザが気を付けてusing/autoを 使うようにすればよいですが、気をつけて使わなきゃいけない関数はそもそも安全とは 言い難いです。)が、全く呼ばれないよりは遙かにマシ。C#の場合は実際にそういう仕様になっているそうです。

これってもうちょい根本的な解決は知られていないんでしょうかね。

18:38 04/08/14

Design by ContractTM

つい最近D言語のリファレンスから"Design by Contract"(メソッドの入出力仕様や 正常オブジェクトが常に満たすべき条件などをコードとしてプログラム中に明示的に 記述しておく設計パラダイム。Eiffelの開発者であるB.Meyers氏によって提唱された概念。) って語句が全て消えて"Contract Programming"に変わっていたので、なんでかな? と思ってたら、どうも商標を取られちゃい そうらしい。

QuickDir

林檎の木で紹介されてたQuickDirというソフトが便利すぎて死にそうです。これは、表示されてるウインドウの タイトルバーを中クリック(またはShift+左クリック)すると、そのアプリのexeのある フォルダの内容をメニューとして表示してくれるもの。メニューをクリックすると、 そのファイルやフォルダを開くことができます。ReadMeが読みたい時やプラグインを入れる 時など、自分はしょっちゅうexeのあるフォルダを開くので、これを入れてから 実に快適です。Noah につけてた Ctrl+F (Noah.exeのあるフォルダを開くショートカット) も不要になったかも。

実家に帰って

久しぶりにテレビというものを見たですが、オリンピック楽しいなあ。

21:36 04/08/12

書き殴り

Boost at OOPSLA 2004。あー行きたい。 一ヶ月で何か面白いライブラリをでっちあげられたら出してみたいですが、ネタがないなあ。 しかし最近WikiでCFPってよく見かけるようになりました。

WWYMPとりあえず1巻目は買うつもり。 こっち方面で論文を書きそうなのはどっちかというと私ではないような(笑

最近はPCに向かうのと本屋をブラブラする以外のことをしていないような気がします。 ところで 世界名作劇場文庫 なんてのが刊行されてたんですね! しかも素晴らしいことに、主題歌のCD付き。 10年前の記憶なので幾分か美化されているかもしれませんが、このシリーズは名曲揃いで、 特に『空へ…』(ロミオの青い空)と『Twinkle Talk』(七つの海のティコ)と 『少年の丘』(名犬ラッシー)は自分の中で3本の指に入る歌といっても過言ではない というとやや過言ですが10本の指には確実に入るくらい。

23:36 04/08/10

Pythonのイテレータ周りはこんなですよ、というのを掲示板 >>4898 に投稿いただきました。感謝感謝。

継続の話 (contd.)

引き続きSchemeな人とRubyな人には常識以前の話だと思うのでスキップ推奨。 あと、昨日書き上げたあとに存在に気づいたのですが mayah氏の記事 と内容がかぶってるかもしれない…。それと、単にcontd.って書きたかっただけ なので、以下の記事は昨日のイテレータの話とは関係無しに読める内容のつもり です。目指せ世界で157番目くらいにわかりやすい「継続」の解説。

f から return

さて、RhinoWithContinuationsでは、new Continuation() と書くと "次はここから再開するべし情報" が記録されたオブジェクトが作られます。その"ここ"というのは具体的には、 "new Continuation()を呼んだ関数が終わった直後" という位置。 できたオブジェクトを関数として呼ぶと、記憶された位置から実行再開されます。

function f()
{
  var k = new Continuation()
  k()
}

上の例は、k() を呼ぶと f() が終わるとこから実行再開するわけで、 f() はなにもしない関数です。というか、「実行再開のための情報を記憶」とか 偉そうなことを言ってはいますが、よーするに、k()のやることは「fの呼び出し元から 実行を再開…」つまりぶっちゃけ「fからreturn」するだけ。 だからこの関数は function f() { return } と同じです。ちなみに return と同じなんだから、値も返せます。

function f()
{
  var k = new Continuation()
  k(100)
}
print( f() )

は100を表示します。function f() { return 100 } と全く同じ。

Continuation が普通の return と違うところは、一度作った Continuation を持ち運べば、あとはどこから呼んでも「fからreturn」してくれる点。

function g(k)
{
  k(100)
}

function f()
{
  var k = new Continuation()
  g(k)
  print("ここには来ない")
}

print( f() )

gの中で「fからreturn 100」をやってるので、結果としては"100"とだけ表示されます。

たとえ f が既に終了しちゃってたとしても、意地でも「fからreturn」するのが Continuationの偉いところ。

var global_k
function f()
{
  global_k = new Continuation() // グローバル変数に記憶
}

f()            // (*)
print("hoge")
global_k()

global_k() を実行すると (*) の行で呼んだfからreturnして、 次のprint("hoge")をまた実行して次にglobal_k…なわけで、 要するに無限ループで"hogehogehogehoge..."と表示されることになります。

ただし、fからreturnすると言っても、実行の位置がそこに戻るだけで、 全ての変数の値が"fからreturn"の瞬間の値に戻ったりするわけじゃありません。 ここ注意。場所は戻れど時間は戻らない。

var global_k
function f()
{
  global_k = new Continuation() // グローバル変数に記憶
}

var i = 0
f()            // (*)
print( i++ )
global_k()

こうすると i の値は毎回1ずつ増えてって、0 1 2 3 4...と表示されます。

これが、Continuation(継続)のすべて。簡単でしょ? この、「出来ることはfからreturnだけ」の機能が実に豊かな表現力を 持つのだから、不思議なものです。

参考1: call/cc

ほとんどの言語は、new Continuation() のような継承を直接作る処理ではなく、 call/cc (call with current continuation) という関数をプリミティブと して用意しています。この関数は、Rhino で定義すると、こんなの。

function call_cc(f)
{
  return f( new Continuation() )
}

関数fを引数としてcall_ccに渡すと、「call_ccからreturn」できる継続をfに 渡してくれる、と、それだけ。call_ccの呼び出し元から見れば、「今のこの場所に 戻ってくるためのContinuation」を引数としてfを呼び出してくれるもの。 上の定義を見ればわかるように、fの中で"call_ccからreturn"継続を 使わなかったら、単にfの返値がcall_ccの返値になります。

call/ccは数学的な意味が恐ろしいほどに美しいということと、 "この場所に戻ってこい"というのが継続の使い方の頻出パターンであることから call/ccをリミティブとして採用する方が好まれるのですが、いざ解説をcall/ccから 始めようとするとなかなか難しい。(ので、この記事ではcall/ccはおまけ扱い(^^;)

参考2: Continuationの実装

コンパイラ等の内部でどうやって実装されているか、ですが、Continuation が 覚えるのは"場所"でしたから、記憶しておけばよいのは基本的に「関数からreturnする 先の場所」です。Continuationで戻ったあと、さらにその関数を抜けたあとに戻る先… なども覚えておかないといけないので、要するに覚えるものはその時点の「コールスタック」です。

あと、上に書いたようにfが終わっちゃった遙か後でも「fからreturn」を可能にするために、 Continuationが作られた時点のスタック(ローカル変数置き場)が潰されないように 待避しておく必要があるかもしれません。「場所は戻っても変数の内容は戻らない」 とはいいましたが、スタックを書き潰して変数の存在自体が抹消されるとさすがに困りますので。 スタックを使わないで実装された処理系なら、特にこの心配が必要ないこともあります。

昨日の実装について

で、昨日の続きに戻ります。(どうでもいいけど、Continuation のことは「継続」と 訳すより「続き」と訳した方がわかりやすいんじゃないかな、と今一瞬思ったり。) 昨日の問題というのは、

function fib_each(f) {
  var a=0, b=1, tmp
  do { f(a); tmp=a;a=b;b=tmp+b } while(1)
}

のような、関数を受け取ってその関数に引数をどんどん放り込んでいく 関数(例えば、コンテナの内部イテレータ)を外部イテレータに変換 するにはどうすればいいか? というものでした。次のように、Current で 現在値を取得できて、好きなタイミングで moveNext() を呼ぶと次の値を 得られるようなオブジェクトに変換してくれるas_iterator関数が欲しい。

var it = as_iterator(fib_each)
for(var i=0; i!=10; ++i)
  { print(it.Current); it.moveNext() }

Continuationを使ってこの問題を解いてみます。方針としては、fib_each には 「moveNext側に戻ってくる」処理をする関数を渡して、moveNextでは「fib_each側に戻る」 処理をします。 昨日書いた実装は変数名が抽象的だったり、かなりECMAScript特有の書き方を してしまったりしていたので、反省して少し書き直しました。

function as_iterator( fmap )
{
	var return_f
	var return_moveNext

	// (1) オブジェクトを作る。あとでこいつにmoveNextメソッドを定義して、
	//     外部イテレータに仕立て上げます。
	var ite = new Object()

	// (2) fmapに渡す関数fの定義。
	var f = function(x)
	{
		// (2.1) fmapのくれた値をイテレータに記憶
		ite.Current = x
		// (2.2) "fからreturnしてfmapの中に戻る" ためのContinuationを記憶
		return_f = new Continuation()
		// (2.3) moveNextからreturnして、moveNextの呼び出し元に戻る
		return_moveNext()
	}

	// (3) moveNextメソッドの定義
	ite.moveNext = function()
	{
		// (3.1) "moveNextからreturnして呼び出し元に戻る" ためのContinuationを記憶
		return_moveNext = new Continuation()
		// (3.2) fからreturnして、fmapの続きを実行
		return_f()
	}

	// (4) fmapを呼び出して値の取得を開始…
	//     …したいのだけど、いきなり fmap(f) してもreturn_moveNextできない。
	//     そこで、return_moveNextに"このas_iterator関数に戻ってくる"ような
	//     ダミーのContinuationを突っ込んでおいてから、fmap(f) を呼び出し。
	function start() {
		return_moveNext = new Continuation()
		fmap(f)

		// fmapが終わったらここに来る。全ての値を辿り尽くしたという
		// ことなので、Currentフィールドを消しておく。で、moveNextから戻る
		delete ite.Current;
		return_moveNext()
	}
	start()
		// <== 一回目のreturn_moveNext()ではここに戻ってくる

	// (5) 作った外部イテレータオブジェクトを返す
	return ite
}

流れ図を書きながらじっと睨めば、もうこのコードが読めるはず。

参考3

上とほぼ同じ処理を整頓すると、 このくらい(Rubyでの例) 簡潔になるそうな。感激的。

12:40 04/08/09

イテレータ

Schemeな人とRubyな人には常識以前の話だと思うのでスキップ推奨。 あとこの文脈でPython,Satherなどなどに触れないと言うのは物凄い抜けがあるような 予感がしていますが、その辺全然知らないのでご勘弁を。

ループ

リストの各要素について操作(例えばprint)を適用する場合、大きく分けて、 二つの流儀があります。一つは、リストを走査するためのオブジェクトを作って、 それを動かすループで全要素を列挙する方式。C言語でポインタや配列の添え字で ループを回す場合とか、C++、Javaの標準ライブラリのイテレータがこれに当たります。

List lst = [1,2,3]
for( Iterator i=lst.begin; i!=lst.end; ++i )
    print (*i)

もう一つは、リストを回るためのメソッド/関数/構文を用意しておいて、 処理内容を記述した関数やブロックをそれに渡せばよいという方式。 Rubyのイテレータや、関数型言語のfold/inject系関数、D言語のforeach文などなど。

lst.each { |e| print (e) }

List.iter print lst

seq::for_each( lst, print );

foreach( int e ; lst ) { print(e) }

前者から後者への変換はほぼ明らかで、 "自分自身から繰り返し用オブジェクトを取り出してぐるぐる回るメソッド" を定義しちゃえば一発です。使うときにはループの中身に書いていた処理内容を 関数として切り出さないといけないので、無名内部関数が書けない言語だと 苦しいですが。

lst.each = function(f) {
  for( var i=this.begin; i=this.end; ++i )
     f (*i)
}

「前者」「後者」のままではこの先書きにくいので、一般に使われている名前を借りて、 前者を「外部イテレータ方式」、後者を「内部イテレータ方式」と呼びます。 上に書いたように、リストの実装者が外部イテレータとして定義しても、 使う側は内部イテレータとして使うなんてこともできるので、誰にとって ○部イテレータなのか、には注意が必要。

利点1

まず、「リストの各要素を回る」という操作を「イテレータ」として抽象化 することの利点は、リストでなくても配列でも木構造でも両頭待ち行列でも ストリームからの入力でも、イテレータを通して操作することに決めれば、 考え方を分けずに、全て同じ方法で記述ができるようになる点でしょう。

利点2

じゃ、それぞれの方式の利点は?「外部イテレータ」の利点は、 使う側がループを自由に制御できるという点。例えば、 2つのリストの各要素の和を持つ新しいリストを作る場合、 まぁ、ごそごそと2つイテレータを取ってきてループを回せばよろしい。

for( Iterator i1=lst1.begin,i2=lst2.begin;
              i1!=lst1.end && i2!=lst2.end;
              ++i1, ++i2 )
    lst_new.push (*i1 + *i2)

…ってまあこのくらいなら内部イテレータでもなんとでもなって、 二つのリストをペアにするzip関数などを使ってから処理を回せばOK。 なんか内部イテレータの方が簡単になっちゃったけどOK。

lst_new = zip(lst1,lst2).map( fun x,y -> x+y )

他には、二つのソート済みリストをマージするとか。

Iterator i1=lst1.begin,i2=lst2.begin;
while( i1!=lst1.end && i2!=lst2.end )
   lst_new.push (*i1<*i2 ? *i1++ : *i2++)
while( i1!=lst1.end ) lst_new.push (*i1++)
while( i2!=lst2.end ) lst_new.push (*i2++)

条件を満たす要素の次の要素を表示とか。

unless( lst.empty )
  for( Iterator i=lst.begin; next(i)!=lst.end; ++i )
    if( *i < 100 )
       print (*next(i))

どちらも内部イテレータでも書けなくはないですが、 なかなか直感的なコードにはなりません。

利点3

対して内部イテレータの利点は、実装者が書きやすいことと、 使用者が読みやすいこと。読みやすさについては、外部イテレータも 内部イテレータに変換しちゃえば同じなので、重要なのは前者。 データ構造に対するもっとも自然な記述は、自然と内部イテレータになります。 例えば2分木の全ての葉ノードに関数fを適用しろ、と言われたら、 特別な理由がない限り、このように再帰で書くと思います。

BinTree.each = function(f) {
  f( this.data )
  if( this.left  != null ) this.left.each(f)
  if( this.right != null ) this.right.each(f)
}

こう書けばもう、言語にもよりますが、それだけで内部イテレータになっております。 今度は逆に、木構造を順に訪れる外部イテレータを書こうと思ったら、ちょっと 頭をひねらないといけません。また、乱暴な言い方をすると関数コールバック方式で 書けるものなら何でも内部イテレータと見なせるので、

fib.each = function(f) {
  int a=0, b=1
  loop { f(a); (a,b)=(b,a+b) }
}

例えばフィボナッチ数列の無限列を回るイテレータ(上の例)とか、 何かシステムリソースを列挙してcallbackしてくれるAPIとか、ワイルドカードを指定してディレクトリ走査とか、 データ構造でないところまでも簡単に応用を広げることができます。

ここまでのまとめ

おーけい、では、内部イテレータを書いたら自動で外部イテレータに変換される 仕組みがあればどちらも楽ちん。万事解決だ。

yield return

解決策として、C# 2.0の方法がある(らしい)です。

class BinTree<T> {
  IEnumerable<T> each() { // 内部イテレータっぽく実装すると
    yield return data;
    foreach( T e in  left.each() ) yield return e;
    foreach( T e in right.each() ) yield return e;
  }
  ...
}
BinTree<T> b;
IEnumerator<T> i = b.each().getEnumerator(); // 外部イテレータが作れるようになる
i.moveNext();
i.moveNext();
Console.WriteLine( i.Current ); // 2番目を表示、とか。

   // なおeach()の実装で使ったforeach文は外部イテレータを内部イテレータっぽく
   // 使うための構文なので、直接 IEnumerator<T> を触らなくてもOK.

実はMono1.0もVC#2005も落としたっきり使ってないので、構文間違ってたらごめんなさい。 IEnumerable を返すメソッドの中では yield return という構文が使えて、returnのように値を関数の外へ返しつつ、「次はここから 再開すればよい」という情報を記憶します。で、moveNext() されるたびにさっき記憶した 位置から実行を再開して、次のyield returnでまた呼び出し側に戻るの繰り返し。 詳しくは "Iterator blocks" と "The yield statement" 辺りをどうぞ。

これは、上で挙げた問いに対する完璧な答えになっています。 "全要素にyield returnを適用する"という内部イテレータ的な実装をすると、 外からはIEnumeratorインターフェイスを通して外部イテレータ的に使える、と。 最適化コンパイル方法も想像できるので、パフォーマンスも良さげ。

でも、更にこの方法をもうちょい徹底させてみます。

Continuation Rules.

C#の方法では、yieldを使って内部イテレータを書くことで、外からはそれを 外部イテレータとして使うことが出来ました。でも、従来通りの内部イテレータ、 つまり「関数などを受け取ってそれを各要素に適用するメソッド」を 外部イテレータに変換できるわけではありません。 「俺はもう今までに100個くらい関数適用型の内部イテレータを書いちゃったんだい!」 という人の過去の資産を救うには、どんな言語機能があればよいでしょう。

…(第一級の)継続 / (First Class) Continuation と呼ばれている機能が助けになります。これは、yield return の "次はここから再開すればよいという情報を記憶" という部分だけを取り出して 使えるようにしたもの。継続を扱える言語は多々ありますが、ここでは 私の好きなECMAScriptの実装系の一つ、RhinoWithContinuations を使ったサンプルをどうぞ。別に私が考えたわけではなくて、よく知られたテクニックですが。

// 内部イテレータ関数fmapを受け取って
// 外部イテレータオブジェクトthisを返すコンストラクタ
function Enumerator( fmap )
{
	// private変数。this側の継続(≒実行再開に必要な情報)と、fmap側の継続
	var this_cont
	var fmap_cont = function() { fmap(switch_to_this) }

	// fmap側からthis側に制御を移す手続き
	var switch_to_this = function(x)
	{
		fmap_cont = new Continuation() // fmap側の継続を保存
		this_cont(x)                   // this側の継続を実行
	}

	// this側からfmap側に制御を移す手続き
	var switch_to_fmap = function()
	{
		this_cont = new Continuation() // this側の継続を保存
		fmap_cont()                    // fmap側の継続を実行
		this_cont(undefined)           // fmapからreturnしたらここにくる
		                                   // - this側には未定義値を返すことにする
	}

	// moveNext : fmap側を動かして、返帰ってきた値を保存
	this.moveNext = function() { this.Current = switch_to_fmap() }
	this.moveNext() // 最初の値を取得しておく
}

いい加減長くなったので詳細は次回としますが、

function fib_each(f) {
  var a=0, b=1, tmp
  do { f(a); tmp=a;a=b;b=tmp+b } while(1)
}

var it = new Enumerator(fib_each)
for(;;it.moveNext()) print( it.Current )

こんな感じで。0,1,1,2,3,5,8,13,...

00:16 04/08/09

まじかる

とある繋がりのおかげで、やねうさんちの美咲ちゃんが我が家にやってきたので、読んでみました。

…感想。面白い。暇を見つけて一章ずつでも読もうかー、と思っていたのですけど、 1時間ノンストップで最後まで読み通しちゃいました。 特に前半は順を追って平易に解説されてるので、サクサク読めます。 内容は"いかにしてソフトのクラック(不正コピー)が行われるか"という技術と対する 防衛策の解説で、「美咲ちゃん」と「お兄ちゃん」の二人の対話形式で 進みます。この形式をとったことで説明のやさしさ/わかりやすさに磨きがかかって いるように感じました。

クラックする側はもちろん、される側になることもなさそうという趣味プログラマな人でも、 「元ソースが無いライブラリの中をデバッガで追うはめになったのだけど、アセンブリ言語 レベルじゃ何がどう繋がって動いてるのかさっぱりだよウワーン」 といった不安の 解消に役立ちそう。

ろじかる

話は全く変わって、野矢茂樹氏の 『はじめて考えるときのように』 が文庫で出ているのを発見。 "考える" って何だろう? 例えばgooの国語辞典で検索すると 「物事について、論理的に筋道を追って答えを出そうとする。思考する。」 と出るけど、その "論理的に" というのは、具体的に、どうすることなのだろう? …という、"考える" について考えてみる本。一応哲学書ですけど、 こちらも読みやすいです。オススメ。

ちなみにこの本では、"論理"と"考える"の関係について「よく言われる「論理的に 考える」ということは、実はできないということも証明します。

23:59 04/08/02

昨日のことを今日書く日記。

本屋巡り

面白いの出てないかなと棚を眺めていたら、 『Winning Ways for Your Mathematical Plays』 というシリーズが4冊並んでいるのを発見。 第二版の4巻目がわりと最近出たものみたいです。パラパラと見た感じ、 石取り とか 棒消し のような感じのゲームを色々紹介しつつ、必勝法などについて考察していく本、かな? 多色刷りで図がたくさん入っていて、かなり楽しそうです。これは買わねば! と思ったけど値段を見て躊躇。とりあえず家に帰って今熟考中です。あ、Amazon だと多少安くなってる…。

次に目に付いたのが Bruce Eckel 氏の 『Thinking in C++』の Volume Two。この方の本はWebからダウンロードして無料で読めるように 公開されてるので、大雑把には既に読んでましたが、本の形になってると雰囲気があって いいですね。中身は文法などの基礎事項がわかっている人向けで、"C++的考え方" っていうのがどんなもなのか、の把握にぴったりだと思います。まず例外と例外安全の 話から入る辺りがステキ。"○○言語的考え方" って他の言語でプログラムを書くときにも 参考になるので、C++プログラマ以外にもお勧めしたい一冊です。

おとうさんがいっぱい』の愛蔵版が出てるー。

あと、ふらふらと東京駅の付近を歩いてたらインテルのデジタル 体験スペースなるものが目に入ったので、立ち寄ってみました。 と、寄ってみたはいいけど特にすることもないので、とりあえずGoogleを開いて、 やっぱり特にすることもないので適当に "Intel" と検索してみるという ブロードバンド体験でした。

00:57 04/08/01

黒猫

池袋から目白の間あたりを歩いていると、ところどころに黒猫の落書きを目にするの です。で、「今度の土日に歩き回って全部で何匹いるのか数えてみよう」と思ってた のですが、ふと「なんかそれって凄いデイリーポータルZの企画っぽい…」と思って 調べてみたらホントにやっ てるし

確か鬼子母神の商店街に、もう一匹いたような。

どっとどっと

今話題の『圧縮ファイル解凍の脆弱性』ですが、この問題が気になる方は、Noah 3.193 と XacRett #48.2 (要するに現時点での最新版)を解凍用途に使用すべきでは ありません。Lhasa や Lhaz ではこの手の書庫に対する措置が執られているよう なので、そちらをオススメ。

Noah

検証用書庫を作って現状確認中。「絶対パス入り7z」 と 「絶対パス入りArj」 は作るのにCRC合わせが必要ぽくて大変なので、まだ未調査です。あと、cpt は書庫を作れる環境にないので試してませんが、たぶん 「..入り」 が問題に引っかかります。現時点での最新版DLLを使うこと前提で、”意図しない” 場所にファイルが展開される可能性があるのは、「..入り の lzh, zip, cab, rar, arj 書庫」です。

zipは今でも何とかできるので良しとして lzh, cab, rar, arj ですが、 これはNoahではDLL側の対応待ちとします。

検証用書庫が要り用な人は、メール下さい。送ります。作るのにトリックがいるわけでもないし、不正な書庫でも なんでもないんだから、ユーザが自分でチェックできるように公開すべきだと 個人的には思うんですが。元サイトも窓の杜も伏せてるので横並び。

08/01 訂正 Unlha1.90h は「ルートディレクトリ越え".."」 のみチェックで「基準ディレクトリ越え」ではないみたいなので、未対応という ことになります。「DLL側の対応待ち」にlzhを追加。08/02 追記 1.90i で「基準ディレクトリ越え」をチェックするオプションがつきました。Noah 3.194 でそのスイッチを入れてみます。

XacRett

b2eとかが無いので、変えちゃうとユーザ側から ".." を許可できなくなるのを どうしたものか…。iniで戻せるようにすればいいか。ということで、XacRettの 方も近いうちに更新しようと思っています。

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