2006/12/31

整数からなるリストを、指定した自然数の正値をスタートタグ、負値をクローズタグとみなしてグループにくくりたい。ただし、そのようなグループはリストは入れ子になっているかもしれない。

ようするに、こんなふうな結果を得たい。
gosh> test-list
(2 5 3 0 9 1 9 4 -1 9 4 2 1 0 1 9 -2 -1 5 1 -1 4 -1)
gosh> (group-between test-list 1)
(2 5 3 0 9 (1 9 4 -1) 9 4 2 (1 0 (1 9 -2 -1) 5 (1 -1) 4 -1))


condでグループにくくりながら再帰が基本的な戦略だけど、入れ子になっているかもしれないので工夫が必要になる。これには、一番内側にあるグループをくくり出すという操作を、指定した数がリストの表面に見えなくなるまで再帰すればよさそう。そこで、指定した数の正値が連続したら、いったんグループわけを始めたところに戻ってやり直すようにする。そこで call/cc ですよ。←関係ない(2007/5/18追記)
(define (group-between ls n)
(define (group-most-inner ls)
(cond ((null? ls)
'())
((eq? (car ls) n)
(call/cc
(lambda (k)
(let R ((first (list (car ls)))
(rest (cdr ls)))
(cond ((null? rest)
(error "pair unmatched" n))
((eq? (car rest) (- 0 n))
(k (cons (append first (list (car rest)))
(group-most-inner (cdr rest)))))
((eq? (car rest) n)
(k (cons (car ls)
(group-most-inner (cdr ls)))))
(else
(R (append first (list (car rest)))
(cdr rest))))))))
(else
(cons (car ls)
(group-most-inner (cdr ls))))))
(cond ((not (member n ls))
ls)
(else
(group-between (group-most-inner ls) n))))
これを応用して、XMLやHTMLの文書から要素を取り出してくるのに使えそう。構造だけ欲しければsxmlにしてしまえばいいけど、元の文書の「見た目」を変えずに特定の要素だけいじるときには役立つかも。

2006/12/29


男性の性欲は男性の自信と関係しているという説を最近きいたけど、ほんと? そういうもっともらしい意見を女性が信じちゃうと、性欲とかどうでもよくてとにかくかわいい女性が大好き、っていう人間が生きにくくなるので困るんですが。


みんな本当は性欲とかどうでもよくて、単純に女性と一緒にいると楽しくて、でも性的ないいわけがないと照れるから、しかたなく風俗とかいくんじゃないのか。風俗にいったことがないので推測しかできないけどさ、女の子どうしできゃっきゃって楽しそうにしてるのが羨ましくて羨ましくて、いっそのこと自分も女の子になって混ざりたいなあっていう男性の本音を歪めて提供するのがエロ産業なのではあるまいか。

2006/12/28


自転車のタイヤのバルブカバーを盗まれた。走行に支障はないとはいえ、腹がたつ。この手の犯罪はとにかくたちが悪い。やられ損だ。仮に犯罪が発覚しても犯罪者にとってたいした不利にならない。社会的なリスクも対して大きくないから、倫理感がない限り手を染めるほうが得策なんだろう。古今東西、不条理な大人の制裁がない社会で中高生がいきがるのは、これが理由にちがいない。

ハムラビ法展でさえ、たかだか受けた犯罪と同じ報復(懲罰)しか認めない。これはフェアじゃない。最初に目を潰された被害者のほうは、そもそももともと目なんて潰されたくなかったわけで、たまたま犯罪に合うようなことさえなければ幸せに暮らしていられたはず。一方、目を潰すほうには選択肢がある。相手の目を潰したところで高々自分の目を潰されるだけだから、それを覚悟して犯罪により得られるメリット(遺恨を晴らすとか)のほうが大きければ、犯罪のほうを選択できるわけだ。ずるい。

復讐法で対等に扱うべきなのは犯罪そのものの程度ではなく、犯罪により被る被害の程度であるべきだ。だって、仮に自転車のバルブを盗んだやつが僕の前に現れてバルブを返してくれた上に「俺の自転車のバルブをお前が盗んでもいいぜ」と言ってきたとして、僕はそいつの自転車のバルブなんて全然盗みたくないし、それで僕の今の憤慨とか悔しさはとうてい補填できない。かといって、そこでそいつを殴りつけて今の僕と同等の憤慨を感じさせることに成功しても、それで僕は警察に捕まって刑事裁判を受けて刑に服し、いま以上の不快感を味わうことになる。それじゃあやっぱり不公平だ。どうする?

ポイントは、法律にのっとった刑罰の度合が比較的線形に緩やかに厳しくなるのに対し、僕が相手に与えることが可能な苦痛はより急峻に厳しくできるというところにある。だって、そこでカッとなってそいつを殺害したところで、いまみたいな事情なら極刑にはなりそうもない。つまり、相手を殺害するまで至れば、確実に僕のほうが被害の程度が小さくなる。どのへんに損益分岐点があるかはさだかじゃないけど、妄想ではタコ殴りにして半身不随にするところくらいになる気がする。その程度であれば、こっちも懲役10年程度でかつ残りの一生を棒にふるだろうし、相手も一生を棒にふるだろうから、きっとイーブンだ。被害の程度を平等にするという精神にのっとればそれくらいが妥当だってことだ、ざまみろ。どんな犯罪も、せめてそれくらい殺伐とした覚悟でやってもらいたいものである。

頭に血が登っているので適当なことを書いちゃったけど、「自転車のバルブの盗難」を「家族の傷害事件」とかにしたら、それほどふつーの人情とかけ離れていないような気がしてきた。もし家族がそのへんのガキから傷害事件を被ったら、僕は犯罪者と被害の程度が同じになるようにがんばるかもしれない。


現代音楽は抽象的だといわれることが多い。だからわけがわからんと。確かにそういう面はある。


とりあえず何が現代音楽か定義せずに話をすすめるけど、クラシック音楽のいいところは、作曲家のほかに演奏家という存在がコンテンツのオーソリティーとして認知されていることだと思う。音楽を聴くほうにしてみれば、たとえ作曲家の言っていることが強烈すぎてちんぷんかんぷんでも、あるいは稚拙すぎて退屈でも、演奏家というフィルターを通して楽曲に接することができる。ようするに、どんな曲でも演奏家しだいでコンテンツとして成立できるってことだ。Pollini や Boulez を見れば、ここまではあながち間違っていないはず。ただし彼らの演奏が秀でているのは、それが一般人ウケするようなフィルターだからじゃなくて、譜面を読み込んで忠実な解釈を徹底していることにある。だから楽曲の質が大きく影響しているはずなんだけどつまらない曲もキラキラしちゃうから不思議。閑話休題。


彼らのすごさはおいといて、技術書というコンテンツも同じことが言えなくちゃだめだよなあと思う。譜面と演奏の関係が、原稿と編集の間に成り立つのか、それとももっとメタレベルで技術と書籍の間に成り立つのかは知らない。たぶん両方なんだろう。


2006/12/24

call/ccについておまえの知っていることを晒せと脅された。

まずこんな式を考える。
(begin 
(print "hello")
(print "goodbye")
(print "hello again")
(print "goodbye again"))
この式を評価すると、beginの中の環境で(print ...)という式が上からじゅんばんに評価される。結果的にこう出力される。
=>
hello
goodbye
hello again
goodbye again
Schemeでは、式の1つめの要素をオペレータとみなし、残りをオペランドとみなす。Schemeで式を評価するっていうのは、各オペランドを評価したものを引数として、それらをオペレータに適用することを意味している。

上記の例の(begin ...)という式を評価する場合、beginプロシージャに対してオペランドである(print ...)たちを評価したものが適用される。beginは引数として与えられた式を順番に評価していくプロシージャなので、まずどんな動作をするかというと、「(print "hello")を評価した。これから残りの(print ...)たちをbeginに適用する」。

で、この動作を記録にとっておくことにしよう。具体的にはスタックにつむことにする。
(print "hello")を評価した。これから残りの引数を評価する
同様に次の動作もスタックにつむ。
top    : (print "hello")と(print "goodbye")を評価した。これから残りの引数を評価する
bottom : (print "hello")を評価した。これから残りの引数を評価する
これを繰り返すと、beginの評価が終ったときのスタックの状態はこうなる。
top    : (print "hello")と(print "goodbye")と(print "hello again")と(print "goodbye again")を評価した。最後の式の値を返すよ
(print "hello")と(print "goodbye")と(print "hello again")を評価した。これから残りの引数を評価する
(print "hello")と(print "goodbye")を評価した。これから残りの引数を評価する
bottom : (print "hello")を評価した。これから残りの引数を評価する
じつはこの活動記録が「継続」を表している。で、スタックなので通常はいちばん上しか見えないけれど(つまり最後の式の値が返るだけ)、Schemeには途中を捕まえる方法がある。それがcall/cc。
(define c '())
(begin
(print "hello")
(print "goodbye")
(call/cc
(lambda (k) (set! c k)))
(print "hello again")
(print "goodbye again"))
こうすると、call/ccを仕掛けた場所の継続、つまり、くだんのスタックの下から2番目を捕まえて、あらかじめ適当な値で定義しておいたcに代入できる。けっきょくcには、「(print "hello")と(print "goodbye")を評価した。これから残りの引数を評価する」という継続が代入される。そこでcを評価すれば、cは「これから残りの引数を評価する」つもりでまんまんなので、こうなる。
gosh> (c)
hello again
goodbye again
これを応用すれば、たとえば「(a b a c a d)というリストから、最後のaで始まる部分リスト(a d)を取ってくる」とか、「木構造を探索するのに、途中で分岐した場所から別の枝を探索し直す」とかできる。これらは「途中を忘れて覚えておいた場所からやり直す」という人生やりなおし機型の応用といえる。一方、「とにかくcall/ccを仕掛けた場所に戻れる」という性質を利用すれば、いわゆる局所脱出ができるようになる。具体的な例はディヴィグの本とか"Seasoned Schemer"とかを参照。そもそもこの記事は"Seasoned Schemer"のオレ解釈なわけで。

2006/12/08

日本語の疑問文で「それとも」は、 or 条件だと見なしていいだろう。
Cさん:年賀状、出さないですよね? それとも出しますか?
Kさん:うん
出すか出さないかしかないので、この問題の答えは常に true だ。コードにすれば一目瞭然。
(define send-card? (lambda () #f))  ; 出さないつもりでも……
(or (not (send-card?))
(send-card?))

=> #t ; 答えは「うん」
ところが、実際にはこういう会話が成立する。
Cさん:年賀状、出さないですよね? それとも出しますか?
Kさん:いや(出さない)
なんで排中率を放棄して false を返しているのか。
それは鳥頭だからであって、ひとつめの質問を忘れちゃってるだけだよね。
(call/cc
(lambda (k)
(or (not (send-card?))
(k (send-card?))))) ; 忘れた

=> #t ; ???

どうして call/cc で脱出せずに #t が返るの?

2006/12/07


(define (trace ls)
(call/cc
(lambda (skip)
(let R ((ls ls))
(cond ((null? ls)
'())
(else
(call/cc
(lambda (k)
(set! trace (lambda () (k #f)))
(skip (car ls))))
(R (cdr ls))))))))


2006/12/04


本当は好きなものを嫌いと言ってみることでアイデンティティを成立させようとしていた時期があったと思う。

たとえばクラシック音楽への興味は、メジャーな楽曲のメジャーなフレーズへの興味から入って、そのうちマイナーな作品の魅力に気づき、オレだけが知っている的な優越感とともにどんどんマイナーな作家/作品/演奏を指向していって、そのうちメジャーな作家/作品を否定するようになった。このメジャー否定は、小中学校の音楽の時間に超メジャーどころを強制的に視聴させられて感想文を書かされるような体験と調和して増幅した。もう、なんでこんな子どもっぽい曲を聴かなきゃいけないんだ、と。モーツァルト? ヴェーベルンでも聴かせろや。

で、高校生にもなるとクラシックなんかよりハードロックに目覚めるから、モーツァルトもヴェーベルンも忘れさる。モーツァルトを思い出すのはずいぶん年齢を経てからだ。そこで、なんでこれを否定してたんだろうと思って悲しくなる。モーツァルトを否定することで、オレはもっとディープな作品を聴いているんだという優越感を安直に手に入れようとしていたんだろう。

今思い出すと、本当はモーツァルトも好きだった。好きなものを好きと言えるようになるには、たぶんものすごい跳躍が必要だった。どこで飛んだか知らないけど、いまは自分の好き嫌いを社会とのかかわりでとらえなくてすむ場所にいる。生きやすい。

なんで突然こんな個人的なことを書きたくなったかというと、フジテレビで月曜日に放映している「のだめカンタービレ」が楽しくてしかたないから。自意識を一周してきて、ようやくこういうドラマを素直に楽しめるようになったんだなあ。

2006/11/22

Allegro Common Lisp 2006 November Seminar (Japanese)。忘れないうちに3日間の印象を殴り書き。

Lispそのものに興味がある人たちと、むしろSemantic Technologyに興味がある人たちがいて、双方にとって有益なセミナーだったと思う。Franz Inc.と数理システムの皆さんには本当に感謝いたします。

いちばん興味深かったのは、Fritz(Franzの創業者)がGoogleに代表されるSyntacticな検索を明確に否定していたこと。非常に慎重な人なので、Googleのビジネスに対して不快感をあらわにしているのが意外だった。

そしてやっぱりAllegroGraphのすごさが印象的。というか、それを開発しているJansのパワーがすごい(懇親会では手羽餃子の油を背広に跳ね飛ばしてしまった。あらためてごめんなさい)。いくら理念的にSemantic Technologiesに利があるといっても、やっぱりRDFトリプルとして記述されたメタデータに対する操作を大規模なアプリケーションにまでスケールさせるのは困難なわけで、そのへんが軽量なスクリプト言語とXMLベースのWeb 2.0が成長した理由のひとつだろう。そういう事情をひっくり返してSemantic TechnologiesをWeb 3.0(そんなものがあるとして)の支柱にする鍵のひとつになりうるのかもしれない。まあ、そんな大仰なことを言わなくても、ふつうにRDBMSよりグラフのほうが直感的なデータベースは多いような気がする。実際、いままさに頭を悩ませている問題として、出版した書籍と著者や訳者とを管理できるようなデータベースがほしい。そんな出版社向けの汎用データベースをAllegroGraphで作るという夢を見た(著者と書籍の間に単純ではない関係があったりするので、ふつうの住所録を作るよりいくぶんたいへん)。

もうひとつの鍵はプレイヤーの数だと思うんだけど、これはちょっと悲観的にならざるをえない。Web 2.0でやっているのはSyntacticなデータから豊饒なWebアプリケーションを大人数でマッシュアップ(これって音楽業界のマーケティング用語じゃなかったの?)すること。Lispベースの技術でそれだけのジャンクなマンパワーを集められるかっていったら、たぶんできない。Lisp以外で同じことが実現できるようになるかっていたら、たぶんすぐにはできない。

でも、それでいいのかも。Fritzの不快感は「なんでもGoogle」という外野の風潮に対するものであって、それで満足する人はそれでいいけど不足があるならぜひ相談してくれ、という話だったんだと思う(かなりバイアスぎみ)。すでにSyntacticなキーワード検索というアプローチの限界が露呈している分野(バイオとIntelligence Agencies)はSemantic Technologiesに目を向けているし、ある程度大規模な組織の内部に閉じたアプリケーションなんかもSemantic Technologiesに目を向ける潜在的な市場になるとふんでいるらしい。まさに昨年のセミナーでは「Lispでなければ解決困難なほど複雑な問題も世の中にはたくさんある」と強調していたけど、その方法論をSemantic Technologiesに絞ってきたんだなあ、という印象だった。

なによりもFranz社は、Lispをビジネスとして成立させることに興味があって頼もしい。Fritzは2日目のパネルディスカッションで、Franz社が最後のLisp企業だと強く自覚しているように見えたけど、それにはすべての聴衆が素朴に好感を持ったと思う。Semantic! Semantic! っていっても、それはやっぱりビジネスマンとしての売り文句で、純粋に美しいテクノロジーが好きなんだろうなあ。

以下はどうでもいい話。

やっぱり懇親会ではSchemerの肩身が狭い。自分のようなTiny Schemerだとなおさら。でも楽しいのはなんでだろう。

いいかげんな英語でもいいから、話をしないとダメだ。

CLOSを勉強しないとダメだ。小出先生の発表で、「CLOS/MOPがメタ-メタ-…-オブジェクトを云々するのはラッセルのパラドクスにつながるから論理屋には絶対に理解できない」みたいな軽口があったけど、あれはどういう話だったんだろう? それって単純に巨大基数に対応してるんと違う?

2006/11/15

『Binary Hacks』のサンプルPDFでは川合史朗さんによる巻頭言が読めて、プロのプログラマにとって抽象化の壁に無自覚でいるのは致命的だ、と主張されている。もちろんこれはBinary Hacksの巻頭言なので、抽象化が下に有界であることを忘れないようにしないといけないよ、という警鐘と受け止めていいんだと思う。ぶっちゃけていえば、土台を固めろ。もしくは、土台を意識できるようになれ。

その手の抽象化の漏れを自覚することの大切さっていうのは、誰かが抽象化したものを使うときの落し穴を自覚することの大切さだといえる。川合さんの文章にある「箱庭の製作者のアイディアを抜ける」ことは、いわば誰かが手がけた抽象化の漏れを自分でふさぐことを指しているんだろう(勝手な解釈だけど)。

一方で現実の問題を解くうえでは、誰かが抽象化したものをてなずけるだけでなく、自分自身で何かしら抽象化っぽいことをしたい。そのときに求められる自覚は、当たり前だけど、『Binary Hacks』の巻頭言で示唆されている自覚とは別ものだ。もちろん、よりエグいレベルからの抽象化を自分でするなら、まさにBinary Hacksが必要になるんだろう。ただし、たとえばぼくにとっては『Binary Hacks』で扱っているような題材はとうてい自分の力だけでゼロから抽象化できるしろものじゃない。

もっとかわいらしい抽象化のためのHacksも欲しい。「箱庭の箱庭の箱庭を別の屋敷の箱庭にコピーして、さらにその中に自分で箱庭を作るときに抽象化を漏らしにくくするHacks」みたいなの。ちゃちな問題であっても抽象化っていうのはやっぱり強力なので、その無自覚に享受しがちなパワーに目がくらんで掘りがちな落とし穴は何か。そもそも落とし穴を作らないためのHacksは?

たぶん、それは数学なんだと思う。ふだん僕らは、直観的に確からしいと思ってあるアイデアをコーディングし、期待する答えが得られた時点で問題を解いたものとみなしている。問題を解くアプローチや道具を手に入れたところで満足しちゃっている。そのアプローチや道具が本当に適切なのかどうかを確かめるには数学しかない。

ありがちな例はハノイの塔だろう。ハノイの塔の解法を説明した記事は、数学っぽいおはなしでもよく目にする。「一番下の1枚だけ残して隣の棒に移動し、一番下の1枚をあまっている棒に移動して、移動しておいた残りをその上に移動しなきゃいけない」という説明。そんなふうな説明から「n 枚のディスクを移動するのにかかる工数を H(n) とすると、 H(n) = H(n-1) + 1 + H(n-1) 」という関係を導いてくる。1枚ずつディスクを移動するって操作を抽象化して考えることで問題の構造が見えてくるよね、みたいな。でもそれだけだと、どんなに工数がかかったとしてもそれくらいには抑えられるってことしかわかりませんから。もっと少ない方法があるかもしれない。

もちろん実際にはない。ただし、それは数学的帰納法で証明して、はじめて「ない」と断言できる。そして道具や解法の抽象化は、どこまでいっても具体的な事物が対象だからではなく、たぶんこういうところからのほうが漏れやすい。たぶん。

こういう抽象化を漏らさないための数学について、楽しい教科書がないものかなあと思う。ちょうど、深いところに抽象化された部分について『Binary Hacks』が果たすであろう役割に相当するような本が。数学の楽しいところや神秘的に見えちゃうところを取り上げて『Math Hacks』とかっていう方向もあるだろうけど、それは答えじゃないと思っている。むしろ、普通の数学と同等の内容を持つ教科書をプログラマ向けに企画することが直接の答えのひとつだと思っていたし、いまでも思っている。

あるいは、ここ1〜2年くらいだけど、 "SICP" や "Concrete Mathematics" こそがそういう本に違いないという確信も持つようになった(上のハノイの塔の落とし穴も"Concrete Mathematics"の冒頭で取り上げられている例がそのまんま)。つまり、抽象化することのパワーを解説や練習問題をとおして読者に伝えるような本で、しかも直観だけでなく数学的に証明可能な抽象化の道を示しているような本(証明が書き下されている必要はない。分かっていて省略するのと結果的に省略されちゃってるのは別)。しかも、"SICP" や "Concrete Mathematics" よりもっとミニマルな内容におさえたとっつきやすい本にできるはず。←いまこのへん

まあ、本があるだけじゃだめで、手を動かして訓練しないスキルは決して身につかないんですがね。数学に限らず。

2006/11/08

部分から全体を推測することが統計の本質というより、全体がいい具合に推測できるように適切な部分を取り出したいというのが統計の本質なんだと思っていた。その際、全体については「何らかの確率分布にしたがう」という仮定を設定するので、その仮定が妥当である限り、おれカネゴンさんのような心配は不要なはず。もちろん、これは統計というものの全体についていえる話ではなくて、統計的推測といわれているものについての話です。

なんかよく分からないけど取ってきちゃった部分から全体を推測しようとする統計もある。その傾向が強くなるほど、数学とは離れたものになっていくような気がする。そういう需要もあるのでそういう分野もあり、やはり統計と名乗っているので、統計の教科書にのっているから数学により正しいことが保障されるといった妄想は妄想です。全体の傾向を分析するひとつの手段としてはありえると思うので批判したりするつもりはありません。

なんか、ちっとも確からしさのない脊髄反射的な文章になってしまい申し訳ありません。

2006/11/07

0.999...は1かっていうのは、ゆっくり慎重に考えれば解けるクイズのような問題ではないし、定義でもないと思う。もちろん哲学でもない。とはいえ、哲学っていうのがいちばんしっくりくる表現なのかもしれないやね。「哲学が何か」なんて知る由もありませんが、雰囲気として。だって、ようするにそれを納得するかどうかだけがポイントだと思うから。定義なんだから納得しろっていう話じゃないよ。それなりに数学を勉強して経験していくと、そのうち、そう考えざるを得なくなるってこと。

虚数の概念とかもそう。虚(imaginary)という字面や、一方で「実」数という概念があったりするから混乱を引き起こしやすいと思うんだけど、別に虚数は空想上のモノでもなんでもない。虚数のimaginaryっぷりは、実数のimaginaryといい勝負だと思う。逆に言うと(逆だよね)、実数とかいっても名前ほどにはrealじゃなくて、たとえばπの実在っぷりを2次元アイドルの実在っぷり以上に強烈に感じられる人はすごいと思う。もういっかい逆に言うと、いろいろな場面で必然的に虚数が現れるのを目の当たりにすれば、そのうち必要に応じた虚数のrealさを納得できるようになるのではあるまいかと。

確かに、いつまでたっても納得できない人はいる。でもそれって、頭の良し悪しとかじゃなくって、単に納得したくないだけなんじゃないだろうか。あとは、訓練が足りないか。ある概念について納得するっていうのは、その概念を提示している記号の字面と日常的な正しさの感覚だけで到達できるような態度じゃないから、ある程度の努力とか歩み寄りは必要だと思う。

2006/10/27


校正待ちですることがないので(後半はうそ)、Code Golf の "Switchboard" という問題に手をつけてみた。コードを短くすることはともかく、この問題は解法を考えるのが面白かった。いまのところ23位だけど、これが個人的なスキルの限界だと思う。

Scheme は受け付けてない。そうとはしらず最初は暢気に Scheme で書いたことはいうまでもない。しょうがないので Ruby で書き直したんだけど、"gets" だけで標準入力から1行読み取れるなんて。実用的にもほどがある。

2006/10/26


おいしいとんかつの店は三河島の「山き(きは「七」を森のように重ねた字)」だよ! このへん
どうもあんまり知られてないようなので、叫んでおく。

ヒレがびっくり。とんかつといえばロースだと信じてたのに、その常識を覆された。あと、メンチ。ヒレもメンチもそれまでどっちかっていうとバカにしていた料理だったけど、本当にごめんなさい。もちろんロースもうまい。
ただ、メニューが少ないし、キャベツに対する選択肢がソースしかないので、軟弱な人にはおすすめしない。地元ゆえのひいき目っていうのもある。それでも、普通の豚を普通のとんかつとして硬派に堪能したいなら、絶対におすすめ。普通なのに、軽くびっくりするんだよね。外食にはびっくりが必要だと思う。しみじみうまいだけなら家で食うさ。

店内の色紙によると、阿佐谷の「かつ源」という店からのれんわけしたようだ。あんまり知られてなくて、いつも暇そうにしているので、ちょと応援したい。


SICP の ex. 4.11〜4.13 をうろうろしていたら、ようやく set-car! や set-cdr!が set! と根本的に違うことが飲み込めてきた。いままでそんなこともきちんと知らなかったのかよ。

たとえば次の2つの例は、いっけんすると同じ結果になる。つまり a に (0 1 2 3) が束縛された状態になる。
(define a '(1 2 3))
(let ((current-a (list-copy a)))
(set-car! a 0)
(set-cdr! a current-a))

gosh>a
(0 1 2 3)
(define a '(1 2 3))
(set! a (cons 0 a))

gosh>a
(0 1 2 3)
set-car! と set-cdr! の場合には、もともと a が指し示す領域にあったデータが書き換わっている。それに対して set! でやっていることは、もともと a が指し示す領域にあったデータは換わってなくて、a という名前で束縛されていたものを別の場所に cons して作った (0 1 2 3) に 付け換えたにすぎない。

で、この違いを理解していないことが ex. 4.11 付近で評価器が扱う環境の定義をしたりするときにネックになるわけで、define したつもりのものが環境に登録されずに悩むことになったりするのは僕だけか……。ところで「Schemeは十分に抽象的だけどビットが透けて見えることがある」みたいなことを言ったのは誰だっけ?

この話のとってつけたような結論はお好みに合わせて随時読みかえることができます。
  • やっぱりローレベルの知識が足りないやつは帰れってことだよね。そういえばJoelさんもそんなようなことを言ってたなあ。
  • やっぱり参照透過じゃないとだめだよね。びっくりマーク?なにそれ。





どうでもいいけど、僕は、こういう基本的なことを知らなかったという「恥」を恥と承知して公にさらすことには旨味があると思っている。これは、「知らないなりに考えてみたけど間違ってたら誰か教えてね」という意味ではない。なんか、そういう恥2.0みたいなノリじゃない。恥2.0ではブログツールのコメントとかトラックバックとかはてな何とかとか巨大掲示板といったAPIによりあなたの恥を知識と経験に昇華してあわよくばWebコミュニティへのネタを提供します。よかったね。あるいは、「自分は知らないことを知らないまま放置しない向上心と努力あふれる人間であります」というアピールになるという意味でもない。そういう態度がアピールにはなるのは、ぶっちゃけ小学校の教師に対してだけだろう。努力だけはしてるように見える人と、どこで勉強してるかわかんないけどアウトプットをきちんと出している人がいたら、自分は後者と仕事することを選ぶ。

「聞くは一瞬の恥」とかいうけど、僕には、それで教えてもらった内容だけを自分のなかに保存することができない。恥体験と一緒だから内容が見に付くという側面があるように思う。この側面は、自分自身に固有の経験だけから傍証しているものなので、ほかの人にも当てはまるのかどうかは知らない。まあ、恥も外聞もなく分からないことを聞きまくっている人間にろくなスキルを見に付けていない(ように見える)のが多いとは思うけど。

ようするに独学でスキルを得るには恥の追体験が必要ってことだ。将来の自分は、今日書いた内容を恥ずかしく思い返す必要がある。紙の大学ノートに同じことを書いてもいいんだけど、それは「恥」じゃないんだよね。将来の自分は、今日書いた内容を公開したことを恥ずかしく思い返す必要がある。このノートは恥のタイムシフト装置です。

2006/10/24

temp

emacs から blogger に投稿したい。

Atom Publishing Protocol というのがあって、それをemacs から使えるようにする atom-blogger.el というのがあった。設定方法はここに丁寧に解説されている。

Using atom-blogger with emacs to post to blogger
http://phototechnic.blogspot.com/2006/03/using-atom-blogger-with-emacs-to-post.html

emacs への設定だけをしても、captcha が邪魔するらしく、まったく投稿できない。captcha をオフにする方法もよくわからない。さんざんあちこちクリックして、投稿時のcaptcha の横にある「?」マークをクリックすれば captcha を解除するメニューに入れることが気づいた。なにそれ。

で、そのメニューいわく、「Bloggerのスパム対策ロボットにより、このブログにスパム ブログの疑いがあることが検出されました」。

どうやら captcha による投稿時の認証は、ユーザが望んでオンになるものではなく、bloggerの運営者が「スパムブログ」と判断したものに勝手に設定しているらしい。さっきまでこのノートは Link Spam(Wikipedia)に使われてたらしいよ。Wikipedia によると "Search engine spammers, on the other hand, are generally aware that the content that they promote is not very useful or relevant to the ordinary internet surfer."

ぐうのねもでませんって。

2006/10/23

ツインピークスで、クーパー捜査官がこうつぶやくシーンがある(wikiquote)。


Every day, once a day, give yourself a present.
Don't plan it, don't wait for it, just… let it happen.

毎日ひとつ、自分にプレゼントを。
用意したり待ち望んだりするプレゼントじゃなくって、なにげないやつでいい。


クーパーはこのセリフを、確か一杯のコーヒーについて言っていた気がする。恋人のアニーが一緒だったような気もする。いかんせんセカンドシーズンのDVDがいつまでたってもリリースされないので、そんなようなシーンを記憶の中で作り上げていただけかもしれない。どうでもいいけど、アニーとクーパーはショーペンハウアーのネタで盛り上げれるキチガイだ。

そんなわけで、コーヒーを楽しく飲むと、もう一日の楽しみが潰えたような心地になる。

2006/10/17

同じグループの同僚が鼻歌まじりで仕事してたりすると、不思議に自分も仕事に集中できるもんなんだな。集中しようという意識が持て、しかもそれに成功する。一緒に仕事している人間が上機嫌だってことは、彼女の仕事もうまく動いてるってことだ。そんなプラスの気配がいつも充満している職場ならパーティションはかえって邪魔だろう。たぶんバランスボールのある職場にいる人達はそれを知ってる。

生産性のことさらに低い同僚が鼻歌まじりだったりすればイライラが募る。だから、生産性の低い人間を雇い続けなければいけない職場ではパーティションが必要なんだろう。パーティションより必要なものがあるような気がするので、パーティションを作ってくれとはいわない。せめて本棚をください。

2006/10/10

名前付きletをlambda式にしたい。

SICPの第4章では、Schemeの式の評価機をSchemeで書く。こう書くとやたらに抽象的で深遠でカッコよさげに聞こえるけど、まずはプロシージャをいくつかのスペシャルフォームによる表現に均さないといけないからandやorをletをlambdaにするとか、そういうどちらかというとバタ臭い作業が続く。
で、ex.4.8では、名前付きletをlambda式にしろとある。letrecがないので、たぶん正解はinternal defineを使う方法。でも、そろそろ式の表現を変換するだけの作業には飽きてきたので、不必要に解答をややこしくしてみる。つまり、要するに関数を再帰させる話だと解釈して、こういう問題設定にする。

再帰的なプロシージャを抽象化したい。

答えは分かっている。Yコンビネータだ。というわけで、以下はYコンビネータのおさらい。"The Little Schemer"の第9章の翻案ともいう。

まず、再帰を含む関数を用意する。たとえばex. 4.8のフィボナッチ名前付きlet版。
(define (fib n)
(let fib-iter ((a 1) (b 0) (count n))
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))

count≠0 のときに再帰しているので、 count > 0 のときに適当に答えを出してくれる fib-iter-1 というプロシージャが世界のどこかでよろしく定義されていると妄想する。
(define (fib n)
((lambda (a b count)
(if (= count 0)
b
(fib-iter-1 (+ a b) a (- count 1))))
1 0 n))

再帰しないですむようになったので、もうletに名前はいらない。それで、ついでにletをlambda式にしておいた。もちろん、実際には fib-iter-1 なんていう都合のいいプロシージャはないし、もしあっても fib-iter-1 の中にはきっと再帰があるだろう。fib-iter-1 の再帰を片付けるのに fib-iter-2 を妄想し、さらに fib-iter-2 の再帰を片付けるのに fib-iter-3 を妄想し、……嘘をつき続けなければならない。

そこで発想を飛ばして、「fib-iter-1を妄想する」ことを抽象化してみよう。ちょっと分かりにくいけど、妄想したいものを受け取ってfibの中身のlambdaを返してくれるようなプロシージャを作ればいい。つまりこんな感じ。
(lambda (fib-iter)
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))

ただし現実には「妄想の果て」が必要になる。また妄想なんだけど、とりあえず果てに行き付いたので無理矢理納得することにする。妄想の果てを fib-iter-omega とすると、
(define (fib n)
(((lambda (fib-iter)
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1)))))
fib-iter-omega)
1 0 n))


ここで再び発想を飛ばして、今度は「妄想の果て」を抽象化する。それには、妄想を受け取って妄想を返し続けるようなプロシージャを作ればいい。こんな禅問答のようなプロシージャが考えられる。
(lambda (fib-iter) (fib-iter fib-iter))

これってつまり「関数を自分にぶちこむ」ってことなので、「再帰する」ことを抽象化しているとも考えられる。

ところが、実はこれだけだと果てしなく続く妄想だけになっちゃて、妄想の仕様が何も分からない。仕様がないものは使いようがない。そこで、まずは妄想を整形してやって、それを「果てしなく続く妄想」に渡すようにしてやりたい。いま考えているfib-iterでは3つの引数(a,b,const)を使っているので、この「妄想の果て」も3つの引数をとるプロシージャを返すようにしないといけない。
(lambda (delusion)
((lambda (fib-iter) (fib-iter fib-iter))
(lambda (f) (delusion (lambda (x y z) ((f f) x y z))))))

妄想delusionを受け取って、それを3引数を取るプロシージャの形にして、後はひたすら妄想を続けるというノリ。これがYコンビネータ。だからYコンビネータは、妄想を使えるものにするための、どっちかっていうとテクニカルな細工なんだと思う。

以上をfibに取り込むと、こうなる。
(define (fib n)
(((lambda (delusion)
((lambda (fib-iter) (fib-iter fib-iter))
(lambda (f) (delusion (lambda (x y z) ((f f) x y z))))))
(lambda (fib-iter)
(lambda (a b count)
(if (= count 0)
b
(fib-iter (+ a b) a (- count 1))))))
1 0 n))


もうすっかり妄想が抽象化されつくしたので、これはフィボナッチ数列のn項を求めるプロシージャとしてちゃんと評価される。

gosh> (map fib (iota 20))
(0 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181)

2006/10/02

御徒町の工具屋さんにPBの六角レンチを1本買いにいったつもりが、お店の人にそそのかされてStahlwille(スタビレー)のコンビネーションレンチを5本買ってしまった。まともなスパナをもってなかったので、ちょうどいい機会だったと思うことにしよう。っていうかほしかったんです。

R0010351

スタビレーはドイツの老舗工具メーカーで、Snap-onみたいなテカテカのアメリカ工具がもてはやされる昨今ではむしろ珍しくなってしまった梨地仕上げの表面加工で有名(やっぱ工具はドイツだよなあ。ちなみにPBもドイツはスイスだった)。購入したのは、今年から製造中止になってしまったOpen-Box Type 15というコンビネーションレンチの10mm, 12mm, 13mm, 14mm, 17mm。

Stahlwilleのプレーンなコンビネーションレンチには、大きく分けるとType 13とType 14というのがあって、全長がちがう。Type 14のほうが長い。Type 15は、長いほうのType 14と同じ全長で、オープンエンドの形状が違う。Type 15のオープンエンドは側面が凸曲線に加工されていて、StahlwilleではSoftGRIPと呼んでいた。奥の形状も六角形のボルトヘッドに近いものになっている。写真左がType 15で、右はずいぶん昔にホームセンターで買った安物。

R0010346

一般にオープンエンドのレンチでボルトに強い力をかけると、6面あるうちの2面(もっというと、その2面の片方の対角線のエンド2点だけ)しか接触しないので、ボルトヘッドをなめやすい。そのためコンビネーションレンチは、オープンエンド側で仮締めや早回しをしてメガネ側で強い力をかけるのが正しい使い方。とはいえ、とくにアマチュアだと、オープンエンド側でもそれなりに力をいれたい場合がある。というわけで、Type 15のようなオープンエンドがうれしい。それに側面が凸になっているってことは、口が開いてるってことでもあるわけで、早回しの際にボルトヘッドにひっかけやすいのもうれしい。どこかの通販サイトによると、"The sculptured jaw provides an extra grip on screws and nuts with 25% more static load capacity and 40% more permanent load capacity than standard wrenches. "だって。(残念ながら公式の情報は見つからなかった。)

ところがType 14よりちょっぴり定価が高かったせいか、ドイツでは流行らなかったらしい(お店の人談)。まあ、ドイツの職人はアマチュアにうれしいツールをわざわざ高い値段で買わないってことなのかもしれない。そんなわけで、すでに入手できるのは現在流通しているもののみ。ただ、今のところ在庫処分扱いなので、どうやら安売りしてるっぽい。スタビレーのレンチ5本が9000円以下ってだけで、かなりお買い得。

2006/09/30

GaucheにもRubyみたいなARGFがほしい。
正確にいうと、ほしがっているのは僕じゃないんだけど、確かにARGFみたいな仕組みがあると使い捨てのテキストフィルタを書いたりするのは簡単になりそうだ。Gaucheのマニュアルではmainを使うことが推奨されているけど、気楽で泥臭いスクリプトを作りたいことだってある。

RubyのリファレンスマニュアルのARGFの項目には「スクリプトに指定した引数 (ARGV を参照) をファイル名とみなして、それらのファイルを連結した 1 つの仮想ファイルを表すオブジェクト」とある。その説明がARGFのすべてなら、Gaucheに用意されている仮想ポートで似たようなものが作れるかもしれない。

でっちあげてみた。引数として渡されたファイルのテキストをいったんバッファに吐き出しているので、Rubyのように*argv*のリストが変更されるわけではない。バッファが空なら標準入力を読む。
#! /usr/local/bin/gosh

(use gauche.vport)
(use srfi-13)

(define argv-str
(let R ((files *argv*) (str ""))
(if (null? files)
""
(call-with-input-file (car files)
(lambda (port)
(let ((joined-string
(string-join (list str (port->string port)) "" 'strict-infix)))
(if (not (null? (cdr files)))
(R (cdr files) joined-string)
joined-string)))))))

(define (getc str)
(cond ((> (string-length str) 0)
(let ((c (string-ref str 0)))
(set! argv-str (string-drop str 1))
c))
((= (string-length str) 0)
"")
(else
(error "Out of Range -- getc"))))

(define (argf thunk)
(if (string-null? argv-str)
(with-input-from-port (current-input-port)
thunk)
(with-input-from-port
(make <virtual-input-port>
:getc (lambda () (getc argv-str)))
thunk)))

;;; test
(argf (lambda ()
(port-for-each
(lambda (line) (print (regexp-replace #/hello/ line "damn")))
read-line)))


実行結果
$ cat test.txt
hello world
this is argf test
$ ./argf.scm test.txt test.txt
damn world
this is argf test
damn world
this is argf test
$ cat test.txt test.txt | ./argf.scm
damn world
this is argf test
damn world
this is argf test

作ってから必ず思う、すでにこんなのは誰かが作っているんではないだろうか。

2006/09/26

荒れまくっていたウィキペディアの実数の項目が素敵な解説に直されて先週復活していた。編集履歴を見ると、Makotoyさんという方の尽力らしい。

荒れる原因になったもとの解説は数直線を使ったもので、「実数は有理数を項とする無限数列の収束値として得られる」と説明していたようだ。で、そこからなぜか無限小数の表現が0をのぞいて一意に決まるとか決まらないとかの議論になって、それで紛糾していたらしい。なにか世界には「実数」という確固たるモノがあるって素朴に思いがちだけど、実際には順序と演算を適切に用意してやることで公理的に決まるだけのものにすぎない。つまり、数字を使わなくても構築できて、でもそれは結局は数字で表現するふつうの実数と同型になる。そんなわけで、数字とか数直線上の点をもって実数とは何かを議論するのは、あんまり意味がないと思うんだけど、どうして1.0000……とか0.9999……とか、数字に異常に固執する人がいるんだろう。きっとあれだ。小学校の教師が悪いんだ。

2006/09/21

行列の固有値を求めたい。
なにをいまさら感たっぷりなんだけど、理系の出版社でテクニカルレビューっぽいことをしていると、特に統計の本なんかで行列の固有値を検算したい場合がなきにしもあらず。たいていは Maxima に突っ込んじゃえばいいんだけど、Maxima では特性多項式を作ってそれを解いているらしく、うまく解が求まりやがらないことがある。実際、maxima/share/matrix/eigen.macを見ると、charpolyという関数で特定多項式を作り、それをsolveという関数で解いている。で、この solve という多項式を解く関数がうまくないといったことがMaximaのマニュアルにも書いてある。
eigenvalues calls the function solve to find the roots of the characteristic polynomial of the matrix. Sometimes solve may not be able to find the roots of the polynomial
幸い、固有値を求めたい行列は対称行列ばっかりなので、自分でJacobi法をナイーブに実装してみた。対称行列だとうれしい理由やJacobi法については『プログラミングのための線形代数』の第5章で。

jacobi.scm
gosh> 
(define A
((make-matrix 6 6)
0.68 0.65 0.8 0.11 0.01 0.14 0.65 0.88 0.89 0.02 0.19 0.01 0.8 0.89 0.91 0.02 0.04 0.1 0.11
0.02 0.02 0.81 0.82 0.77 0.01 0.19 0.04 0.82 0.81 0.64 0.14 0.01 0.1 0.77 0.64 0.66))

gosh> A
((0.68 0.65 0.8 0.11 0.01 0.14) (0.65 0.88 0.89 0.02 0.19 0.01) (0.8 0.89 0.91 0.02 0.04 0.1)
(0.11 0.02 0.02 0.81 0.82 0.77) (0.01 0.19 0.04 0.82 0.81 0.64) (0.14 0.01 0.1 0.77 0.64 0.66))

gosh> (eigenvalues-jacobi A)
(-0.010575430595377565 -0.09400171282374802 2.109504119397093 -0.08138275206455295 0.279213041557744 2.5472427345288424)


行列のデータをどういうふうに表現すべきなのか、ひどく悩んだ。Dybvig 本のようにベクトルを使うのがセオリーなんだろう。ベクトルなら行列のij要素を取り出したり変更したりするのも簡単だ。でも、行と列を順繰りになめて各要素をちこちこ掛けたり足したりする処理ばっかり書くことになりそうで、ちょとブルー。そんなわけで今回はあえてリストのリストとして定義した(行ベクトルが1つのリスト。それを要素に持つ縦ベクトルのリストが行列)。リストなので、行列の積や和なんかも高階関数だけで定義できる。
(define (matrix-transform m)
(apply zip m))
(define (matrix-product m1 m2)
(if (not (= (line-length m1) (row-length m2)))
(error "Matrix-Product Not Defined" (list m1 m2))
(apply (make-matrix (line-length m1) (row-length m2))
(map (cut fold + 0 <>)
(map (cut apply map * <>)
(cartesian-product (list m1 (matrix-transform m2))))))))
(define (matrix-sum m1 . ms)
(map (cut apply map + <>)
(apply zip m1 ms)))
ちょっと満足。ただし単位行列や回転行列を定義するのに要素を頭からなめるはめになってるんだけどね。満足しちゃだめ!

2006/09/18

ときどきむしょうにハンダ付けがしたくなる。ちょうど先週、妙に面白いキットばかり開発して秋月で販売しているトライステートからSHOUTcast形式のインターネットラジオを再生するBBシャウトというキットが発売されたので、これを作ってみた。お値段はちょっぴり張りますが。

SHOUTcastはWinAmpで有名なNullsoftが開発したストリーミング技術で、MP3などのメディアをHTTPの拡張を使ってサーバからマルチキャストするものらしい。受信と再生はWinAmpだけでなくiTunesなどでもできる。ただ、どうやら日本にはあまりサーバがない。現に、Wikipediaには「ストリームの生成にはSHOUTcastのサービスを使うのが現実的な選択」とあるのに、ウィキペディアを見ると「インターネット放送の集合体」という適当な扱いを強いられている。まあ、ジャズとクラシックを無作為に流しっぱなしにするだけなら困ることはない。ところで店舗でBGMに海外のSHOUTcastを流してても、やっぱりJASRACから破廉恥な請求を受ける危険があるのかしら。

で、このSHOUTcast形式で配信されているストリームを受信して再生する専用のボードがBBシャウト。キットは、僕のような素人でも2時間くらいで完成します。いわゆるブロードバンドルータにつないで電源とスピーカーを接続すれば、プリセットされている放送局の音源はすぐに聴ける。

bbshout-env

やっぱり箱に入れないと不便だな。

2006/09/14

個人的な理由で2日間会社を休んでいる間に Debian サーバがアップデートされていた。ありがとうございます && ごくろうさまです > hさん。ところでなんか amazon から不思議な商品が届いたんですが、これを何に使えと?

で、アップデートの結果、telnet でログインできなくなっていた。まあ、telnetd を動かさないこと自体はまったくOKっす。ただ、今まで TeraTerm から SSH2 でログインする気になれなかったので、サーバ上には公開鍵がないんです。公開鍵を登録しようにもサーバにログインできないんです。
幸い samba が利用できるようだったので、エクスプローラ上で公開鍵をコピーして ~/.ssh/authorized_keys を作った。これでつながるよね。
ところが TeraTerm(SSH2,utf-8対応版)でまったくつながらない。Cygwin からもだめ。TeraTerm のダイアログに表示されるエラーメッセージは意味不明だし、Cygwin から ssh コマンドで接続を試みても "Permission denied (publickey)."といわれるばかりだし。

結局『OpenSSHセキュリティ管理ガイド』の267ページを見てようやく解決した。~/ssh/authorized_keys のパーミッションが user 以外に書き込み可能になってたりすると、この "Permission denied (publickey)." というエラーが出るらしい(ただし、StrictModes が no ならエラーにならない)。今回のケースだと samba から authorized_keys を作ったので、そのパーミッションは 666 になっていた。しょうがないので、あきらめてコンソールからログインしてパーミッションを設定しなおす。

教訓

* 最初からコンソールに移動して作業しろ
* エラーメッセージは google する前に本で調べろ

2006/09/12

会社を休んで日本ソフトウエア科学会のPPLサマースクールを受講してきた。へとへとになって日暮里まで帰ってきて、考え事をしながら歩いてたら、道に迷った。もう天才的な方向音痴のCさんを馬鹿にできない。っていうか、最近Cさんにセクハラで訴えられかねないくらいつらくあたりすぎ。本当に反省しています。ごめんなさい。

第4回プログラミングおよびプログラミング言語サマースクール
http://www.math.nagoya-u.ac.jp/~garrigue/ppl_ss06/


圏論の諸相(講師:木下佳樹先生)

冒頭で「諸相といっても2時間で話せるのはせいぜい1相」という前フリがあったけど、本当にそうだった。そんなわけで、Haskell→圏論というノリの参加者にはつまらなかったかもしれない。
個人的には、これまで聞きかじっている知識に横糸を何本か通すことができてよかった。以下、講義中に勝手に頭の中で構成したまとめ。絶対に参考にしてほしくないわけですが(どうせこんなページに圏論について真剣に知りたい人はこない)、詳しい人に勘違いを指摘していただくのは大歓迎です。

圏論ってのは、「集合全体の集合」とか「写像全体の写像」のように、集合論だけだとパラドクスを誘発しかねない何かを扱うべく捻り出された概念なんだよね。たしか。だから、「集合全体の集合」みたいなものにやばさを感じない限り、そもそも圏論のありがたみとか面白さはわからないような気がする。講義で「"small"な集合」という言い方を強調してたり、「集合の要素を使わずに単射の定義を与えてみよう」というクイズで「集合全体の集合を認める」という但し書きをしていたのには、そういう事情があるはず。
で、この「集合の要素を使わずに単射の定義を与えてみよう」クイズがえらく自分のツボに入った。集合AからBへの単射っていうのは、ぶっちゃけると集合Aの要素と集合Bの要素が1対1に対応しますってことで、それを「要素」とか言わないで定義しろっていうのがクイズの趣旨。答えはこうなる。
f が集合 A から集合 B への単射
=def
任意の集合C と任意の h,k:C→A について f・h = f・k ⇒ h = k
つまり、単射という写す集合と写される集合の要素に関する問題を、移すほうに値域を持つ別な任意の写像(ただし定義域は固定)どおしの関係として定義すればいいってこと(ちなみに講義では、たぶんあえて、定義域とか値域うんぬんの議論をぼかしてた。当たり前っちゃ当たり前のことなんだけど、これが固定されていないと f との合成写像を取ったところで何の意味もない。そのため圏論では、定義域と値域をあわせて写像ではなく「射」という言葉を使ってる。たぶん。僕のこれまでの圏論の認識といえば「射で考えるやり方」という程度だったので、今日の講義でようやくさっぱりした)。
同じように任意の集合とそこからの任意の射を使うことで、単射に限らず数々の集合っぽい概念を再定義できる。ところで、たとえば直積がペアをあらわすように、集合の概念はデータ構造を形成できる。ってことは、圏でもやっぱりデータ構造を定式化できるよね。たぶん、これが今日の講義のメインだったんだと思う。


2時間で真似(まね)ぶ関数型言語のコンパイラ(講師:住井英二郎先生)

MinCamlの話は仕事や趣味からはいちばん近い話題で予備知識も多かったせいか、関心するところが多すぎてあまり扇動的な気分にはなれず……。実はこのサマースクールに参加した背景には、講義の内容から技術的な知見を得たいっていう以上に、精神的にアジテートされたいっていう動機があった。まあ、お前の求めてるものがおかしいって話なんですが。
余裕があったらまとめをかく。


述語抽象化によるアルゴリズムの検証 ~ シェープ解析を例として(講師:田辺良則先生)

プログラムの安全性を検証したいけどすべての状態と状態遷移を検証するのは無理だよね、それなら数学的に証明された方法で抽象化した状態とその遷移をうまく取り出して検証しましょうって話。まったく予備知識のない分野だったせいか、3時限目にもかかわらず異常に興奮した。プレゼンも面白い。
これも、余裕があったらまとめをかく。

2006/09/05

いよいよネタ切れか。とりあえず内部でプロシージャを定義するのを止めて、ついでに末尾再帰にだけしておこう。
(define (quicksort/values/cps ls k)
(if (null? ls)
(k '())
(quicksort/values/cps
(cdr ls)
(lambda (cdrls)
(receive (low high)
(partition (cut > (car ls) <>) (k cdrls))
(append low
(cons (car ls) high)))))))
昨日で一気にFPっぷりがあがった気がする。にしてもダサい名前のつけ方だ。

2006/09/04

急がないと歯医者に間に合わないけど、ひきつづきクイックソート。partitionかあ。ありがとうございます>nobsun
(define (quicksort/values ls)
(define (low-high ls)
(partition
(cut > (car ls) <>)
(cdr ls)))
(if (null? ls)
'()
(receive (low high)
(low-high ls)
(append (quicksort/values low)
(cons (car ls) (quicksort/values high))))))
気が付くと lambda がいない。

2006/09/03

Scheme Kata の続き。いちおう毎日ちょっとでも続けたいんだけど正直ネタ切れ。なんで初日に4つも作っちゃったんだろう……。
苦し紛れに昨日の多値を使ったバージョンをそのままreceiveを使って書き直す。hanataniさんに教えてもらうまでreceiveもcutも知らなかったから、苦し紛れとはいえ個人的な訓練にはなっているような気がする。Kata だからそれでいいじゃん。
(define (quicksort/values ls)
(define (low-x-high)
(values
(filter (cut > (car ls) <>) (cdr ls))
(list (car ls))
(filter (cut <= (car ls) <>) (cdr ls))))
(if (null? ls)
'()
(receive (low x high)
(low-x-high)
(append (quicksort/values low)
x
(quicksort/values high)))))

2006/09/02

Scheme Kata のつづき。多値でクイックソート。filter からは逃れられず。
(define (quicksort/values ls)
(if (null? ls)
'()
(call-with-values
(lambda ()
(values
(filter (lambda (x) (> (car ls) x)) (cdr ls))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (cdr ls))))
(lambda (low x high)
(append (quicksort/values low)
x
(quicksort/values high))))))

2006/09/01

いまさら Code Kata をやってみようと思った。といっても Kata 1 はコードを書くわけじゃないのか。というわけで Kata 2 から。うーん、二分木の探索ねえ。めんどくさいので勝手にクイックソートに問題を変更させていだきます。でも4つしか思いつきません。しかも二個目は一個目からコピペしただけのいんちき。ほかにどんな方法があるんだろう。
(use srfi-1)
(define ls '(4 9 2 5 8 7 3 1 6 4))

(define (quicksort1 ls)
(if (null? ls)
'()
(append (filter (lambda (x) (> (car ls) x)) (quicksort1 (cdr ls)))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (quicksort1 (cdr ls))))))
(quicksort1 ls)

(define (quicksort2 ls)
(call/cc
(lambda (k)
(if (null? ls)
k
(append (filter (lambda (x) (> (car ls) x)) (quicksort2 (cdr ls)))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (quicksort2 (cdr ls))))))))
(quicksort2 ls)

(define (quicksort/cps1 ls k)
(if (null? ls)
(k '())
(quicksort/cps1
(cdr ls)
(lambda (cdrls)
(append (filter (lambda (x) (> (car ls) x)) (k cdrls))
(list (car ls))
(filter (lambda (x) (<= (car ls) x)) (k cdrls)))))))
(quicksort/cps1 ls (lambda (k) k))

(define (quicksort/cps2 ls k)
(if (null? ls)
(k '())
(quicksort/cps2
(filter (lambda (x) (> (car ls) x)) (cdr ls))
(lambda (ls-lower)
(quicksort/cps2 (filter (lambda (x) (<= (car ls) x)) (cdr ls))
(lambda (ls-upper)
(k (append ls-lower
(list (car ls))
ls-upper))))))))
(quicksort/cps2 ls (lambda (k) k))
Code Kata というより Scheme Kata?
どれも基本となる部分は filter で、芸がなくって本当にがっかりだ。いろんなバリエーションを考えるのが Kata 2 の目的な気がするんだけど。なんかもうこう完全にびっくりするぐらい違うのが思いつきたい。

2006/08/31

原稿を催促する側の気持ちが分かる人間は催促される側よりも少ないと思う。

YAMDAS現更新履歴 - 原稿を催促する人、締め切りを破る人
http://d.hatena.ne.jp/yomoyomo/20060831/deadline

「困るといわれても困る」になぜかとても理解があると勝手に自負している編集者としては、職場でほかの人がひたすら「原稿ください。こっちも困るんです」みたいな電話を繰り返していると、回線交換機を叩き壊したい衝動に駆られて困る。YAMADASさんが指摘しているように、そういう編集者は実際に「優秀な編集者」ではない。これはもう、編集者失格な僕がそう感じているんだから間違いない。

かといって、まったく催促がへたくそな僕のような編集者を雇っておくのは会社としては困るはずで、だから8月も最後の今日になると、「来年には発行する予定です」って報告している企画を上司に提示されて「この企画の進捗はどうなってるんだ」と絞られたりする。どうなってるんだといわれても困る。せっかく本を書くっていう儲からない(けど楽しい)仕事を引き受けようとしてくれている人達に「困るといわれても困る」内容のメールを出すのはしのびない。

それでも最後にはメールを書く。ほぼ定型文。1行目「進捗はどうでしょうか」 2行目「多忙のところお願いばかりで申し訳ありません。よろしくお願いします」 ただし、実際にはこの行間にちょっと何か具体的なことも書く。そして、そこに何を書いたらいいか分からなくて困る。ときには3日くらい困ってる。4日かもしれない。そして書いても出さないことがある。だってブログとか読むと忙しそうなんだもん。

オチがないけど、まあ原稿があって編集ができるんだから、僕もがんばらないといけないですね。

2006/08/29

家に帰ったらヤモリがいた。ちょっとかわいい。ヤモリがいる家はいいことがあるっていうし、殺害するのは思い留まる。でも、さすがに家の中を歩き回られるのはちょっといかがなものなので、外に誘導した。古いとはいえ都内のマンションの3階なのに……と思ったら、実は都市の建物に住んでいるものらしい。なにこの生活日記。

2006/08/27

いまだゴールが見えないSICP。ようやく第3章が終わった。思い返せば第2章を終えたのが今年の3月22日で、それから5ヵ月もかかってる。おそすぎ。まあゆっくりやります。

最後の問題は、また乱数とモンテカルロだった。ところで第3章では疑似乱数を線形合同法で求める方法が紹介されているので(226ページの注6)、Gauche に用意されているメルセンヌ・ツイスターを使っちゃずるいと思う。いや、べつに誰がずるいというわけでなく、それでは自分的に勉強にならないと思う。ってな大口を叩いてたところで、Knuth本を持ってないからWikipediaに載っている係数をひろってくるだけなんだけど。
(define (monte-carlo experiment-stream passed failed)
(define (next passed failed)
(stream-cons
(/ passed (+ passed failed))
(monte-carlo
(stream-cdr experiment-stream) passed failed)))
(if (stream-car experiment-stream)
(next (+ passed 1) failed)
(next passed (+ failed 1))))

;; ex. 3.81
(define rand-init 1)
(define (rand-update x)
(modulo (* x 1664525) 1013904223))
(define (random-numbers c)
(define (rands init)
(stream-cons init
(stream-map rand-update
(stream-delay (rands init)))))
(cond ((equal? c 'generate)
(rands rand-init))
((equal? c 'reset)
(lambda (init)
(rands init)))
(else
(error "Unknown argument" c))))

;; ex. 3.82
(define (random-numbers-in-range x1 x2 rand-init)
(define (normalize x)
(+ (* x (/ (- x2 x1) 1013904223)) x1))
(stream-map normalize ((random-numbers 'reset) rand-init)))
(define (estimate-integral P x1 x2 y1 y2)
(stream-scale
(monte-carlo
(stream-map P
(random-numbers-in-range x1 x2 1)
(random-numbers-in-range y1 y2 506952111))
0 0)
(* (- x2 x1) (- y2 y1))))

(define (P x y)
(<= (+ (square (- x 5))
(square (- y 7)))
9))
(define ex-3-82
(estimate-integral P 2 8 4 10))
(define (ex-3-82-pi howfar)
(/ (stream-ref ex-3-82 howfar) 9))

gosh > (ex-3-82-pi 1000)
3.1128871128871127
最初、x軸とy軸について同じ random-numbers-in-range を使ってたら、どうにも想定している結果よりかなり小さい値しか求まらない。そりゃあ y=x 上の点しか拾ってないんだから、よく考えれば当り前の話だった。結果的に初期値として選んだ 1 と 506952111 は適当で、あまり背景はない(1013904223の約半分)。これくらいオーダーを違くすれば、そこそこバラけるような。
Paul Graham は「ハッカーと画家」のなかで、熱狂的な没頭と妥協しないことの引き合いにダ・ヴィンチの「ジネブラ・ベンチの肖像」の背景に描かれた松を取り上げていた。今年の5月、実際にナショナルギャラリーで本物を目にすることができたんだけど、なるほど彼の言いたいことはよくわかる。美術史的な価値を頭からとっぱらっても、芸の細かさと力強さが同居している不思議な印象に脳味噌が食らいつかれる感じ。でもなんか「好き」っていう絵でもなかった。描いている本人の技量と作品の凄さはわかるけど、べつに欲しいかっていうとそうでもないなと。食傷する手合いの偏執狂っぷり。

今朝、三の丸尚蔵館が所蔵している伊藤若冲の「動植綵絵」を見てきた。

花鳥−愛でる心、彩る技 <若冲を中心に>
http://www.kunaicho.go.jp/11/d11-05-06.html

比較するのはおかしい気もするけど、ナショナルギャラリーでダ・ヴィンチを見たときの 23 倍くらい鳥肌が立った。技術が凄いとか描き混みが凄いとか、そういう評価を受け付ける段階はとっくに超越していて、もうなんて言うか、小鳥がかわいい。そんなことしか言えない。まさにクールなアイデアとホットな実装。とにかくクールなアイデアとホットな実装。

ちなみに、上野の東京博物館でもプライスコレクション展として若冲が何点か来日してるけど、若冲に興奮するなら三の丸尚蔵館のほうがいい。タダだし。プライスコレクションのほうは1300円くらい取られる。それでも、若冲の一番有名な作品であるグリッドぞうさんとかが見られるので、こっちはこっちでおすすめ。さらにガラスケースなしで長沢芦雪のキチガイじみた大作を直に見られることを考えると、むしろ1300円は安いのかも。

にしても、なんで小中学校の歴史の授業で伊藤若冲という日本画家のことを教えてくれなかったですか? ぶっちゃけ、藤原なんとかが娘を天皇に嫁がせたとか、徳川なんとかが犬を大事にしたとか、あるいは、わらじを懐で温めると出世できるとか、そういう話は今になって思い起こすとすべからくどうでもいい。若冲や芦雪の作品のほうが、よっぽど歴史の授業で学びがいがあったであろうネタだ(美術の授業では絵を描くものだ)。まあ、教師が教えたいことと教えられることしか学ぶ機会がないのが小中学校だから、どうしようもないって言ってしまうとそれまでなんだけど。

2006/08/26

抜歯から3ヵ月以上たったので、いよいよインプラントの検討を始める。いつも治療してもらっている歯医者さんでは外科治療はやらないとのことで、今日からは紹介してもらった別の歯医者さんに行く。"My Job Went to India"(来月日本語版を出しますよ)でいうところの「スペシャリスト」がヘンに頭に残ってたせいか、おかしな緊張具合で初診に出向いた。でも杞憂だったみたい。

結局、まだベースになる歯茎の下の骨が十分再生していなかったので、さらに3ヵ月経過を見ることに。ふだんは大学病院に勤務していて診療が月2回だけで、再来月までしか診療日が決定していないとのことなので、あらためて来月か再来月に予約すること。

2006/08/25

僕の仕事は書籍の編集で、編集者っていうと赤ペン片手に原稿を読んで校正記号を入れたり著者の家に原稿を取りにいったりしてる人っぽいけど、実際にはそんなことはやらない。というか、できない。ただ、まあ、そうじゃない方法ではあるけど本を作ってる。だから何も後ろめたいことはないはずなのに、業界的には「校正記号を入れる人」とか「著者に原稿催促をしまくる人」みたいな項で編集者が定義されているので、僕はどこからどう見ても編集者じゃなくなっちゃって、軽い自意識のゆらぎがおきる。

自己防衛のために、編集者(とくに技術書の編集者)を定義し直してみる。まずは直感的に思いつく技能の列挙から。

* 技術に対する感覚が技術者と乖離していない
* 書籍に対する感覚が読者と乖離していない
* 日本語に対する感覚が日本人と乖離していない
* 業務に対する感覚が他業種と乖離していない
* チームに対する感覚がチームの他のメンバーと乖離していない

というわけで、勝手ながら以下の表現をもって編集者の定義とさせていただきます。
Def
任意のAについてAに対する感覚がAの担い手と乖離していない

明日からは、この定義にのっとってがんばりたいとおもいます。よろしくお願いします。


ついでに、こうはなりたくないと思う編集者(とくに技術書の編集者)の特徴も並べてみた。あくまでも僕がなりたくないというだけで、特定のモデルがいるわけではないし、今の自分がそうではないというつもりもない。

* 一次資料と報道とうわさと広告が脳内でいっしょ
* っていうか、そもそも技術に興味がない
* 日本語なので原稿の意味はわかるような気がする
* 自社ルールとオレルールを信じている
* なによりスケジュールと手続きが大事
* はんこが好き
* 声が大きい
* キモイ
* バカ
* 左
* ●●●
* ●●●●●●●

2006/08/20

先日、Gauche のストリームと MIT Scheme のストリームがじゃっかん違う?と書いたんだけど、すみません僕が Gauche のドキュメントをちゃんと読んでなかっただけでした。具体的にはこのページ。

stream-delay
http://www.shiro.dreamhost.com/scheme/gauche/man/gauche-refj_158.html#IDX2975
"As a rule of thumb, any stream-producing functions should wrap the resulting expression by stream-delay."

これまで「Streamは遅延評価で実現する」という程度の認識しかなかった。それが SICP の "3.5.4 Streams and Delayed Evaluation" まで読み進んだところ、実際にはもっと込み入ってたってことがわかった。あいかわらずこの本は教科書としてスキがなさすぎ。つい鼻息が荒くなる。

で、そういう認識であらためて Gauche のドキュメントを見返すと、生成した stream を評価する順番を調整する stream-delay がちゃんと用意されてたってわけですよ。いっしゅん Gauche のわなかと思ったけど、ドキュメントを全部読んでないのと理解が甘いのが悪かっただけ。

Ex. 3.56 に当てはめると、
(define (merge s1 s2)
(stream-delay
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< s1car s2car)
(stream-cons s1car
(merge (stream-cdr s1) s2)))
((> s1car s2car)
(stream-cons s2car
(merge s1 (stream-cdr s2))))
(else
(stream-cons s1car
(merge (stream-cdr s1)
(stream-cdr s2))))))))))

(define S (stream-cons
1
(merge (stream-scale S 2)
(merge (stream-scale S 3)
(stream-scale S 5)))))

gosh> (stream->list (stream-take S 100))
(1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 25 27 30 32 36 40 45 48 50 54
60 64 72 75 80 81 90 96 100 108 120 125 128 135 144 150 160 162 180
192 200 216 225 240 243 250 256 270 288 300 320 324 360 375 384 400
405 432 450 480 486 500 512 540 576 600 625 640 648 675 720 729 750
768 800 810 864 900 960 972 1000 1024 1080 1125 1152 1200 1215 1250
1280 1296 1350 1440 1458 1500 1536)
ちゃんと求まる。

ついでに、347ページの微分方程式を解くプロシージャは次のようにすればいい。(そのまま Gauche で試すと 「stream-map に渡す y がstreamじゃねえ」と言われて実行できない)
(define (solve f y0 dt)
(define y (integral (delay dy) y0 dt))
(define dy (stream-map f (stream-delay y)))
y)

2006/08/11

がやがや町に広まった「ハウルは女の子の心臓を食べる」といううわさは、ハウルたち自身が荒野の魔女から身を隠すために衆目を遠ざけるべく意図的に流したものだ。

「Lispはカッコが多いから超むずい」とか「Haskellはモナドとかわかんないと入出力もできないから超むずい」いううわさも、コミュニティが市場原理から身を隠すために衆目を遠ざけるべく意図的に流しているものなのかもしれない。

出版社は市場原理の一部だけど、その内部にはソフィーのように市場原理に呪われてる奴らもいるってことで。

2006/08/10

放置していた Martha Argerich の新作(フランク、ドビュッシー、シューマンのバイオリンソナタ)をようやくプレーヤーにかけたんだけどさあ、なにこれ。あいかわらず聞いてるこっちが汗出てくるよ Argerich ねえさん……フランクの4楽章の3:45付近で誰かがうなってるんですが、あなたですか? びっくりするのでやめてください。

2006/08/07

もう数年前から考えていること。

できることは基本に忠実に対処し、できないことは工夫して対処する

この態度、間違ってますから。少なくとも外国語→母国語の翻訳で望ましい態度は、まったく正反対。

できることは工夫して対処し、できないことは基本に忠実に対処する

仕事で技術文書の英→日翻訳を発注すると、最初の態度をとってくる翻訳者がとても多い。技術翻訳の場合、ほとんどの翻訳者は当該の技術分野について知識や経験がない。たいていは興味もない。そんなわけで、自分が意味のわかる英文は逐語的に訳して済ませてしまい、意味がわからない英文が出てくると意訳しようとする。意味が分からない英文の意訳って定義上不可能なんだけどね。それこそ逐語的に訳してくれればいいのに。自分が原文の意味をとれてないなら、絶対に意訳しようとしないでほしい。技術がわからなくて訳せない箇所は「訳せません」でいいし、文意に自信がないならせめて英文法に忠実な逐語訳をしてくれるとチェックが助かります。

一方、論文でもない限り技術文書にも日常的な英文は相当含まれていて、発注する側としてはそういう箇所は普通の日本語の文章のように訳してほしいんだけど、これがうまくない。例えば英語の文章には日本語の文章より指示代名詞が多いけど、それをそのまま訳してきたりする。

Becky did not hesitate to ask him it in the shop because she had wanted it.
なぜならベッキーはそれが欲しいと思っていたので、その店で彼にそれを求めることを躊躇しませんでした。

勘弁してください。「ベッキーはその店で前から欲しがっていた○○を彼にねだりました」とか、それなりに普通の日本語に意訳してもらいたいからこそ翻訳を依頼してるわけですよ。○○は、たぶん文脈からわかるでしょう? 適切に補ってよ。普通の日本語で「それ」っていうか?

もちろん、そういうのを求めるなら相応のコストを払えという主張に耳を貸さないつもりはないです。個人的には。

もちろん、すべての仕事について「できることは工夫して対処し、できないことは基本に忠実に対処する」べきだとは思ってないです。むしろ、できないなら手を付けるな、というべき仕事もあるし。とはいえ、その「手を付けない」という対応こそが、その分野での「基本」なのかもしれなくない?

もちろん、上記は特定の業務に対する愚痴ではないです。

もちろん、例に使った "Becky..." の英文は僕の作文なので英語としてへんちくりんな可能性があります。

2006/08/02

LaTeXで、ページの残りが少なかったら次に続く要素を改ページしたい。
あくまでも自分用のメモ。
% ページの残りが指定した数値より少なかったら改ページを促す
% \ifnoroomthenpagebreak{20mm} とか
\def\estimate@restpage{%
\dimen@\vsize \advance\dimen@ -\pagetotal%
\advance\dimen@ -\pageshrink%
\advance\dimen@ -\pagedepth%
\advance\dimen@ -\pagestretch
\advance\dimen@ -\pagefilstretch%
\advance\dimen@ -\pagefillstretch%
\advance\dimen@ -\pagefilllstretch}%
\newcommand{\ifnoroomthenpagebreak}[1]{%
\estimate@restpage%
\ifdim\dimen@<#1%
\ifdim\dimen@>7pt \pagebreak\fi\fi}

\estimate@restpage で「残りページのつもりの値」を見積もってるんだけど、なんかどうしても1行分だけ残っちゃうみたいで、次のページの先頭付近が「残り 6pt くらい」だと見なされてしまう(場合がある)。その補正が最後の「> 7pt」。高さが 7pt しかない行はあんまりないので、この \ifnoroomthenpagebreak コマンドで改ページされなくてもどのみちこの位置では改ページされる可能性が高い。だから実用上は意図どおりの結果が得られることになる。とはいえ、このあたりの挙動がいまいち不明なので、そのままどんな場合でも安心して使うことはできないと思う。

にしても、一連の値「\pageほにゃらら」についてのドキュメントはどこ?(そもそもLaTeXのドキュメントが……)
結局参考になったのは、TRALICSというLaTeXからXMLへのコンバータのドキュメントだった。

TRALICS : a LaTeX to XML translator (P)
http://www-sop.inria.fr/miaou/tralics/doc-p.html

どうでもいいけど、こっちはXMLからLaTeXへのコンバータを作るのに精一杯なわけで、LaTeXからXMLを吐き出すなんて気が遠くなる。

2006/07/30

こないだ会社で「集合がわかる本を教えろ」みたいな質問をされたけど、それはたぶんドモルガンとかについてわかりやすく説明してる本ってことですよね。知りません。

まあ、そういう本の必要性は否定しませんが、たぶん読んでも面白くないんじゃないかなあ。っていうのは、ようするに「数式が読めること=数学がわかること」ではないからなんですが。じゃあ「数学がわかること」とは何かってきかれても、自分は必ずしも数学をよくわかっているわけではないので、はっきりとは答えようがないです。だから以下の独り言は音量をさげてこっそり書きます。


なんだかんだいって、数学に対するイメージは、いまだに「数字とか文字式だとかの演算」なのかもしれない。そこまで極端でなくても、「数式が読めること=数学がわかること」だと漠然と思っている人は多い。傍証:おまえ数学科なのになんで計算できないんだよという誹謗中傷。

現代の数学の根っこにあるのは、数式をこねくり回すことじゃない。数学の役割は、人間が恣意的にいじくれないっぽい概念をどう整理(抽象化)すれば人間の把握下におけるか、ってとこにあると思う。具体的には、代数的な構造だとか位相的な構造だとか順序的な構造だとかを持ち出して、超越的にえいって感じで丸め込むのが現代の数学のやり方。

ところで、そんな現代数学のやり口を学ぶ本(あるいは観賞する本)って、数学専攻の学生以外にも役立つような気がするんだけど、どうだろう。読者になり得るのは『ゲーデル・エッシャー・バッハ』を買った人たち。でも、その面白さを潜在的な読者の大多数に書名とパッケージと口コミだけで伝えるのは困難だから、市場での成功は得られないだろうな。『ゲーデル・エッシャー・バッハ』だって、何で売れたのかよくわからないし。仕事でやるとなると、売れるとか売れないとか考えざるを得ない。そもそも誰に書いてもらうかっていうのがネック。数学の言葉で書いちゃダメなわけで。つーか数学の言葉で書いたら、それはただの公理的集合論の教科書なのかも。

あー、もし冒頭の質問が「公理的集合論がわかる本を教えろ」という意味だったのなら、きちんとした内容は別の本で学ぶ必要があるけど、こんな本があります。

『数学の基礎をめぐる論争―21世紀の数学と数学基礎論のあるべき姿を考える』
http://www.amazon.co.jp/gp/product/4431707972

自分が昔読んだときには翻訳がいまいちという印象だった。でも内容は激面白いっす。

2006/07/26

* 「各要素が「0または1をとる乱数」から成る長さnのリストを得よ」
http://oss.timedia.co.jp/index.fcgi/kahua-web/show/ossz/oneline/2006-07-10

「乱数」っていう用語は、とてもあいまい。たとえばこんなのは?
(use math.const)
(use util.stream)

(define so-pseudo-random
(let ((PIchop (let R1 ((x pi))
(stream-cons (floor x) (R1 (* (fmod x 1) 10))))))
(let R ((s PIchop))
(if (odd? (stream-car s))
(stream-cons 1 (R (stream-cdr s)))
(stream-cons 0 (R (stream-cdr s)))))))

gosh>(stream->list (stream-take so-pseudo-random 30))
(1 1 0 1 1 1 0 0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1 0 1 0 0 0 1 0)


ようするに円周率の各桁の偶奇に応じて 0 か 1 を出力しているだけだけど、乱数といえないことはない。ただし当たり前だけど暗号化処理のシードに使ったりするわけにはいかない。予測可能だから。(math.const で提供されている定数を使っているからそのうち 0 が続いてしまう問題には目をつぶったとしても)

以下は宣伝モード。
乱数については、発売したばかりのこちらの書籍もどうぞ。やたらに広範な話題に及んでいるので拾い読みがお勧め。

『Building Secure Software』
http://www.amazon.co.jp/gp/product/427406655X

原書は少し前に出た本なんだけど、翻訳書は適宜監訳注が入ってるので不便はないはず。


ところで出題元の"Open Source WEB"では7月10日の日付になっているけど、Bloglinesにはついさっきようやく入ってきた。どうしてこんなに遅いんだろう。
夏になって女の子たちが塗る日焼け止めの香りが好き。毎年7月ごろはそれが日焼け止めに由来することを忘れてるから、たまに電車に乗ったりすると微かに幸せなきもちになって、ちょっと戸惑う。

いいわけ1:
だいたいこういう基地外っぽいことを書いているときは心が弱っているわけで……

いいわけ2:
「夏服にそわそわ」だけにフォーカスしたIrwin Shawの小説もありますよ、と。

『夏服を着た女たち』
http://www.amazon.co.jp/gp/product/4062748207/

2006/07/25

Gauche のストリームと MIT Scheme のストリームがじゃっかん違う?
SICP の Ex. 3.56 は、「2,3,5以外の素因数を持たない整数全体の集合を以下の stream-scale と merge を使って求めろ」という問題。
(define (stream-scale stream factor)
(stream-map (lambda (x) (* x factor)) stream))

(define (merge s1 s2)
(cond ((stream-null? s1) s2)
((stream-null? s2) s1)
(else
(let ((s1car (stream-car s1))
(s2car (stream-car s2)))
(cond ((< s1car s2car)
(stream-cons s1car
(merge (stream-cdr s1) s2)))
((> s1car s2car)
(stream-cons s2car
(merge s1 (stream-cdr s2))))
(else
(stream-cons s1car
(merge (stream-cdr s1)
(stream-cdr s2)))))))))

素直に解答すると、こうなる。
(define S (stream-cons 
1
(merge (stream-scale S 2)
(merge (stream-scale S 3)
(stream-scale S 5)))))

ところが Gauche(0.8.6)だと、この S を見に行くと止まってしまうようだ。先頭の 1つしか決まっていないストリームを merge にぶちこんで再帰することに問題があるらしい。深さに応じてストリームの先頭付近を具体的にしてやると、意図したストリームに近いものを求めてくれる。
(define S (stream-cons 
1
(merge (stream-scale (stream-cons 0 S) 2)
(merge (stream-scale (stream-cons 0 (stream-cons 0 S)) 3)
(stream-scale (stream-cons 0 (stream-cons 0 S)) 5)))))

gosh> (stream->list (stream-take S 100))
(1 0 0 2 0 0 3 0 0 4 0 0 5 0 0 6 0 0 8 0 0 9 0 0 10 0 0 12 0 0 15 0
0 16 0 0 18 0 0 20 0 0 24 0 0 25 0 0 27 0 0 30 0 0 32 0 0 36 0 0 40
0 0 45 0 0 48 0 0 50 0 0 54 0 0 60 0 0 64 0 0 72 0 0 75 0 0 80 0 0
81 0 0 90 0 0 96 0 0 100)

0を無視すれば正しい集合が求まっている。
しっかし、こういうひっかけがあるときはヒントが書いてありそうなもんだ。つまりたぶんこれはなにかおかしい。そこで MIT Scheme で試してみると、あっさり普通に求まった。
1 ]=> 
(define S (cons-stream
1
(merge (stream-scale S 2)
(merge (stream-scale S 3)
(stream-scale S 5)))))

;Value: s

1 ]=> (stream-ref S 1)

;Value: 2

1 ]=> (stream-ref S 4)

;Value: 5

1 ]=> (stream-ref S 100)

;Value: 1600

なんでだろう。考えられるのは、Gauche と MIT Scheme の stream-cdr が違いそうだってことだろうなあ。また何か勘違いしている可能性もあるので、もっとよく考えること。

2006/07/23

真偽値からなるリストを持っていて、その or を知りたい。つまり、真偽値のリストに #t があるかどうか確かめたい。

最初はブール演算できると信じてた。
gosh> (fold or #f '(#f #f #t #f))
*** ERROR: invalid application: (#<syntax or> #f #f)

この期におよんでプロシージャとシンタックス形式の違いに戸惑うとは。しかし困ったな。シンタックス形式だと apply もできない。
gosh> (apply or '(#f #f #t #f))
*** ERROR: invalid application: (#<syntax or> #f #f #t #f)

常套手段。
(define (or-bool-list ls)
(if (null? ls) #f (or (car ls) (or-bool-list (cdr ls)))))
(or-bool-list '(#f #f #t #f))

いんちき。
(member #t '(#f #f #t #f))

もっとかっこいい方法がいいなあ。

2006/07/22

備忘録。set! の戻り値は R5RS では規定されていない。
Gauche では set! した引数の set! 後の値が返る。
gosh> (let ((x 1)) (set! x 3))
3

MIT Scheme では set! 前の値が返る。
1 ]=> (let ((x 1)) (set! x 3))
;Value: 1

2006/07/21

オフィスの席替えがあった。新しい席はえらい人たちで決めたらしいんだけど、一言でいって現状のベスト(ただし主観)。まあ、主観が大きいとはいえ、全体の雰囲気も先週までとは完全にいい方向へ変わったと思う。人間なんだから苦痛な環境では仕事できないって。
それにしても、ほんとうに上司には恵まれていると思う(会社には恵まれていないけど)。これで仕事をしなければ罰当たりってもんだ。

2006/07/17

キミならどう書く 2.0 - ROUND 2 - Collatz予想
http://ll.jus.or.jp/2006/blog/doukaku2

ROUND 1は素数を求める問題だったので意識的にスルーしてた。今回の問題も、この問題がCollatz予想と呼ばれているなんて知らない頃にpythonで素直に解いていたので、最初はスルーするつもりだった。Schemeで同じように解いてもつまらないし、あれから何か凄い計算の効率化のアイデアを思い付いたわけでもないので。ちなみに、効率化についてはWikipediaにも工夫のしどころが掲載されているみたい(Collatz conjecture)。

むしろ、なんでこんな問題が数学の難問になってるのかが興味深いとこだ。そこでちょっと逆向きに考えて、1に収束するまでのステップ数ごとに数字の分布を見てみようと思った。
(define (one-step-far ls)
(cond ((null? ls)
'())
((and (even? (car ls))
(> (car ls) 4)
(zero? (remainder (- (car ls) 1) 3)))
(cons (/ (- (car ls) 1) 3)
(cons (* 2 (car ls))
(one-step-far (cdr ls)))))
(else
(cons (* 2 (car ls))
(one-step-far (cdr ls))))))

(define (gs step)
(let R ((step step) (collatz '(1)))
(cond ((zero? step) collatz)
(else
(R (- step 1) (one-step-far collatz))))))

収束先である1からの距離が10までの数字たちを並べると、こんな感じ。
gosh> (gs 1)
(2)
gosh> (gs 2)
(4)
gosh> (gs 3)
(8)
gosh> (gs 4)
(16)
gosh> (gs 5)
(5 32)
gosh> (gs 6)
(10 64)
gosh> (gs 7)
(3 20 21 128)
gosh> (gs 8)
(6 40 42 256)
gosh> (gs 9)
(12 13 80 84 85 512)
gosh> (gs 10)
(24 26 160 168 170 1024)
まあ、なんてことない結果なんだけど、やたらに密度が低いことがわかる。つまり、パラパラとしか数字が出現しない。この先、1に収束するまでのステップ数がnである数字の個数は、ほぼ10n/10のスピードで急激に増えていくんだけど、どんなにnを大きくしても、いつまでたっても出現しない比較的小さな数字が残ってしまう(実際、97はn=118で始めて出現する)。
gosh> (length (gs 10))
6
gosh> (length (gs 20))
72
gosh> (length (gs 30))
732
gosh> (length (gs 40))
7628
gosh> (length (gs 50))
79255
こういうパラパラとした自然数の集まりって、素数と同じように、現在の数学(つーか代数)ではうまく扱えない構造なんだろうな。

ところで上で定義したone-step-farを使って「キミならどう書く 2.0」の関数hを書くこともできる。
(use srfi-1)

(define (h n)
(let R ((rest (iota n 1))
(collatz '(1)))
(cond ((null? (lset-difference = rest collatz))
rest)
(else
(R (lset-difference = rest collatz)
(one-step-far collatz))))))
ただしcollatzの長さが爆発するので、これだとh(30)ですら止まらない。h(20)は18と19らしいんだけど……

2006/07/16

10年ぶりに北岳に登ってきた(考えてみたら3000m級に登るのも久しぶりだ)。10年前は北岳から農鳥岳にかけての白根山系を縦歩したんだけど、今回は時間的にも体力的にも無理だろうということで、山頂付近に2つある山小屋のうち「肩の小屋」で一泊して帰ってくるだけのルートを選択。とはいえ、登山口になる広河原の標高が1600mくらいなので、約1500mをひたすら登らなければいけない。ここ数年は奥多摩とか八ヶ岳でお茶を濁してきたので、ワコールの筋力サポート下着を導入することにした。

CW-X
http://www.wacoal.co.jp/products/cw-x/menu.html

まだワコールのサイトには紹介されてないみたいだけど、この7月からトレッキング用の「スタビライクス」という新商品が登山用品店限定で出荷されていたので、それを購入。15500円。どうでもいいけど、なんか山に行くたびに物欲が発動してる気がする。Uさんがいつも「男の子の潜在的な欲望は何かを成長させることだ」と言っていて(鹿野フィルタ済)、自転車趣味のUさんの結論は「自転車趣味は身体を鍛えてスペックアップする喜びと新しいパーツを手にいれてマシンをスペックアップする喜びが同居しているから男の子的に止められない」なんだけど、登山も似たようなものだと思う。しょーじき、実際に山に登るのは辛いことばかりなわけで、それを補う感動が山頂で得られるかというと、そんなこともない。むしろ、下界で「次に登るときはこれを持って行くとうれしいかもしれない」とか「ひざが弱ってきてるから毎日エレベータを使わずに階段を使うようにしよう」みたいなことを考えているのが一番楽しい。登山の醍醐味は、山頂に到達することではなく、出発までの妄想です。

まあ、そうはいっても山頂で晴れると嬉しい。

DSC_0150

今回はちょうど高山植物が一斉に花を咲かせる時期に登ることができた。富士山のシルエットきれいすぎ。

DSC_0183

希少種のキタダケソウ。平年は山頂付近に6月下旬にしか咲かない花なんだけど、今年は雪がけっこう残っていて、そのおかげで3株だけ花を見ることができた。ちなみに、上の写真の前景に咲いているのはキタダケソウではなくハクサンイチゲ。

DSC_0107

なぜか人気の高山植物、オダマキ。

DSC_0124

2006/07/12

夏休み。i.e. 出社しないとはかどる仕事をつぶす週間。とはいえ、平日に自由な時間がとれるんだから、映画のひとつくらいは観にいくし、今晩から明後日にかけては山にいくつもり。

というわけで ミッションインポッシブル3 を観てきた。あー、なんていうか、期待は裏切られませんでした。脇役たちがかっこいいし気が利いているので前作みたくトム・クルーズのオレ映画になってないし、スパイ映画的に分かりやすいきれいなお姉さんたちも単純に美人なだけでなくかわいらしいので共感できるし、飽き飽きするような謎解きに尺を割かず火薬が多めだし、まあ、要するに素直におもしろい。あたまを空っぽにして鑑賞するには最高だと思う。考えちゃだめ。「1作目ではリストラスパイの悲哀で観客の共感を呼び、2作目でアクションオンリーのオレ映画にしちゃって叩かれたから、3作目で新婚スパイの妻への愛を軸にして深みを出そうという意図ね」とか勘ぐっちゃだめ。「新婚スパイの妻への愛を描きましたってわりに、殺される直前に回想してんのが奥さんとのベットシーンばかりかよ」とか突っ込んじゃだめ。しかし、そのほうがスクリーン上では記号として分かりやすいのかもしれないけど、マトリックスも2作目は愛を描きますっていいながら結局はベットシーンだったよなあ。なんだかなあ。それは陳腐だ、ではなく、それは違うと思う。

金曜の夜に友人とビールを飲みながら、「死ぬ前に最後に何を食べるか選択できるとしたら」という話をしていた。うまいものや好物を食べたいというのもあるけど、冷静に100メートルくらい上から考えると、おうちで奥様と普通の食事がしたいです。照れくさいはなしですが。

2006/06/25

そういえば、Ligetiが死んだっていうニュースを最近聞いた。何枚かCDを持ってるけど、ふだん聞いているのはピアノ練習曲集ばかりだし、散漫にいくつかの作品を聞いているだけだったせいか一貫した「らしさ」みたいなものをさっぱり感じられず、あまり思い入れがなかった。思い入れがないと持っているCDのライナーノーツさえ読まないので、どんな背景を持った作曲家なのかもよく知らない。まあ、それでもピアノ練習曲集だけは面白かったので、たまに思い出したように聴いていた。多少の調声が感じられる曲があるのも聴きやすかった。

死んだっていうニュースをきっかけに、ピアノ練習曲集(Naxos 8.555777)のライナーノーツとWikipedia(日本語)だけ読んでみた。けっこう面白いオヤジだったらしい。

改めてこういう記事を読むと、いろいろ府に落ちるところがある。どうやら作風はころころ変わってて、ピアノ練習曲はごく最近のライフワークだったのね。Conlon Nancarrowからの影響についてはライナーノーツでも触れられてたので、確かなんだろう。っていうか、ぼく自身、NancarrowのCDはLigetiよりもはるかによく聴いてる。つまり、ぼくはそういうの(自分では勝手に「パラパラした感じ」って言ってますが)が好きってことで、だからLigetiでもピアノ練習曲だけはよく聴いてたんだろう。

たぶん、前期の楽曲のCDはこれからも滅多に聴かないね。音楽には、作者や演奏者と時代を共有している聴者にとっては極端に有意味なものがあると思うんだけど(Free Jazzとか、Zeppelinの初期とか。それがつまらないという意味ではなく、当時のムーブメントとか気分とかいうやつを共有していなければ正直よく理解できないほどの評価をされているんじゃないか、という意味)、Ligetiの初期の楽曲にもそういうのがありそう。晩年のピアノ練習曲も同じなのかもしれないけど、少なくともぼくには共有できる何かがあるっぽい。だから聴く。ようするに趣味の問題といってしまえばそれまでなわけで。

2006/06/23

どんな分野にも売り上げランキングというのがあって、なにかしらモノを作って販売している人間にとっては気になってしかたがない情報なわけですよ。とくに競合が多い場合は。書籍もその例に漏れないんだけど、レコード業界におけるオリコンのような存在がないから、信用できるランキングというものがない(ここで「信用できる」というのは、少なくともエンドユーザやマスコミや同僚や上司や同業他社といった他者に対するアピールに活用する場合を想定している)。その結果、みんな、主に次のようないろんな意味で偏りがあるランキング情報に頼っている。
  1. 社内で発行した本の販売冊数はだいたい分かるので、そのなかでのランキング
  2. 書店によってはランキング(もしくは実売情報)を公開しているところがあるので、そこから得られる(もしくは推測される)ランキング
  3. Amazon.co.jpのランキング。各書目のページに表示される数字や、特定のキーワードで検索したときに掲載される順番
どれも母集団が限定的すぎるのが偏りの原因だと思う。そして、その偏りを無視してランキングという数字を持ち出されるとき、イラってくる。
もうどうしょうもないのは、1番目のランキングで高水準にある書目を見て、それが日本中でベストセラーになっているかのごとく勘違いしている場合。バカだろ。まあ、そんなケースは出版社の中にいない限りお目にかかれないけど、中にいるとしばしばお目にかかる。
2番目のランキングは、もう少し現実を反映している。でも、書店っていうのは、読者として意識している以上に得意分野と不得意分野の売り上げ差があるものだと思う。だから、特定の書店から報告されるランキングだけ目にして「○○の本は売れている」と言い放つ人は苦手だ。
いちばんイラってくるのは、3番目のランキングだけをもってあーだこーだ言われるケースである。つーか、あの「Amazonランキング」って何さ。1時間ごとに更新されるようだけど、Amazonランキングが1000だったら、少なくともその時間帯には日本で1000番目に売れている本なのか? とまあ、そういう感想が(出版社にいる以上)当然だと思うんだけど、これがぜんぜん当然じゃない。瞬間値にすぎないAmazonランキングをやたらに気にしたり、なんか適当なキーワードで検索して一番先頭に表示されることに意味を見出そうとする。そのような場当たり的な検証からは、その書籍が市場で評価されているかどうか判断できませんから! まあ、百歩譲って、それで個人的な満足を得るだけならいい。でも、たとえば恣意的なキーワードで検索して先頭付近に表示されることに満足するゲームを続けてたりすると、そのうち気分が麻痺してきて、まるでそれが真の市場の評価であるかのような錯覚に陥るものなので、ちゅういしてください。

で、何年か前にもAmazonランキングが取りざたされる状況のあいまいさにむかついて、それなら多少なりとも実際のところを検証できるようにしてやれと息巻き、Amazonランキングの推移を長期にわたってグラフにする実験をした。Amazonの書籍ページからAmazonランキングの数字を一時間に一回引っ張ってきて、それをMRTGに流し込んでるだけだけど、何年も続けてると下図のような結果が得られて興味ぶかい。基本的には会社で動かしているものなので、例としてちょっとだけ公開。グラフは、下に行くほどランキングが高くなっていることを表す。

flat-year
rightup-year

上側のグラフは、ときどき急峻な山(ランキングの落ち込み)があるけど、全体としては地を這うような傾向にある(特に今年の2月以降)。これは、ランキングとしては高値安定なので、そこそこ定番として市場に受け入れられていると思ってよさそうである。ちなみにこの本は、なにをかくそう『プログラミングのための線形代数』です。
一方、下側のグラフ(書名は控えさせていただきます)は、たまに売れてランキングを戻す谷間があるけど、その間はほぼ右肩上がりの傾向にあって、だんだんランキングが下がっていることを示す。つまり、発売後しばらくは売れたかもしれないけど、定番にはならず市場から忘れられちゃって、今ではぽつぽつとだけ売れている本だと思っていい。

まあ、ようするに、バカは使えないけどデータは使いようっていう話でした。

2006/06/18

パズル「数独」をSchemeによる制約プログラミングで解く

SICPは3.4節の手前で足踏み中。3.3節まで練習問題はひととおり終えたけど、ここで実装しているconstraint programingの例に釈然としないものが残る。
わかんないときは自分で例を作ってみるのがいちばん。要するに
  1. 要素間の関係を定義し、
  2. ある要素の値を更新すると、
  3. 他の要素の値も定義した関係にしたがって更新される
という具合に「関係」ドリブンなプログラムを作ってみましょう、という話なんだよね。関係ドリブンで解にたどり着くといえば数理パズルなわけで、数理パズルといえばsudokuでしょう。constraint programingでsudokuソルバとか書けないだろうか。ふつうのsudokuソルバをどのように実装するかきちんと知らないので、もしかしたら当り前すぎてバカバカしい話かもしれないし、あるいは愚かな話なのかもしれない(ちゃんと調べること→自分)。まあ、ここはあくまでもconstraint programingの練習というスタンスで。

まず決めなければならないのは、「要素を何にするか」。ここではsudokuの各セルを要素として、そのセルが「取りうる数字」を考えることにする。最初は各セルとも、1〜9の数字をどれでも取りうる。
次に関係を定義する。ここでは、「各行」「各列」「各ブロック」を関係とする。「各行」「各列」「各ブロック」などをスロットと呼ぶことにすると、どのスロットも9個のセルを含み、それぞれのセルに1〜9の要素が一つずつ入らなければならない。

例えば4x4のsudokuの場合、セルは16個、スロットは12個になる。セル1〜16とスロットA〜Lの関係はこんな感じ。

sudoku-grid4x4

この関係についてSICPちっくなconstraint network図を描くのはやっかいだけど、無理に一部分を描けばこんな感じになると思う。

sudoku-constraint4x4

上図の関係を見ながらプロシージャを書いていく。肝心の関係の定義は、とりあえず
  • 各スロットに、まったく同じ可能性を持つセルがあったら、ほかのセルからその可能性を取り除く


この関係だけでは解を求めるには不十分で、実際、これから示すコードで解けるsudokuの問題はほとんどない。
(define (make-cell init-possibilities)
(let ((possibility init-possibilities)
(slots '()))
(define (set-my-possibility new-possibility)
(set! possibility new-possibility)
(for-each-slot possibility slots))
(define (connect slot)
(set! slots
(cons slot slots)))
(define (me request)
(cond ((eq? request 'possibility) possibility)
((eq? request 'set-possibility) set-my-possibility)
((eq? request 'connect) connect)))
me))

(define (for-each-slot possibility slots)
(cond ((null? slots) 'done)
(else
((car slots) possibility)
(for-each-slot possibility (cdr slots)))))

(define (set-possibility! cell possibility)
((cell 'set-possibility) possibility))
(define (connect cell slot)
((cell 'connect) slot))
(define (get-possibility cell)
(cell 'possibility))


(define (slot . cells)
(define (one-of-cell-has-new-possibility possibility)
(cond ((= (num-of-same-possibility possibility cells)
(length possibility))
(update-cells! cells possibility))))
(define (me possibility)
(one-of-cell-has-new-possibility possibility))
(define (connect-all-cells-to-me cells me)
(cond ((null? cells)
'done)
((connect (car cells) me)
(connect-all-cells-to-me (cdr cells) me))))
(connect-all-cells-to-me cells me)
me)

(define (update-cells! cells possibility)
(cond ((null? cells)
'slot-updated)
((or (equal? (get-possibility (car cells)) possibility)
(<= (length (get-possibility (car cells)))
(length possibility)))
(update-cells! (cdr cells) possibility))
(else
(set-possibility! (car cells)
(complement (get-possibility (car cells))
possibility))
(update-cells! (cdr cells) possibility))))

(define (complement l1 l2)
(define (include? a l)
(cond ((null? l) #f)
((equal? a (car l)) #t)
(else (include? a (cdr l)))))
(cond ((null? l1) '())
((include? (car l1) l2)
(complement (cdr l1) l2))
(else
(cons (car l1) (complement (cdr l1) l2)))))

(define (num-of-same-possibility possibility cells)
(cond ((null? cells)
0)
((equal? possibility (get-possibility (car cells)))
(+ 1 (num-of-same-possibility possibility (cdr cells))))
(else
(num-of-same-possibility possibility (cdr cells)))))

実際に問題を解いてみる。まずは初期化。トップレベルでdefineを繰り返す方法がわからない……。しかたないので、各スロットのセル一覧をリストとして出力するプロシージャで我慢して、それをトップレベルに張り付けてごまかす。
(define-syntax make9x9cells
(syntax-rules ()
((_ e)
(define e (make-cell '(1 2 3 4 5 6 7 8 9))))
((_ e1 e2 ...)
(begin
(define e1 (make-cell '(1 2 3 4 5 6 7 8 9)))
(define e2 (make-cell '(1 2 3 4 5 6 7 8 9)))
...))))
(make9x9cells
c11 c12 c13 c14 c15 c16 c17 c18 c19
c21 c22 c23 c24 c25 c26 c27 c28 c29
c31 c32 c33 c34 c35 c36 c37 c38 c39
c41 c42 c43 c44 c45 c46 c47 c48 c49
c51 c52 c53 c54 c55 c56 c57 c58 c59
c61 c62 c63 c64 c65 c66 c67 c68 c69
c71 c72 c73 c74 c75 c76 c77 c78 c79
c81 c82 c83 c84 c85 c86 c87 c88 c89
c91 c92 c93 c94 c95 c96 c97 c98 c99
)

(define s1 (slot c11 c12 c13 c14 c15 c16 c17 c18 c19))
(define s2 (slot c21 c22 c23 c24 c25 c26 c27 c28 c29))
(define s3 (slot c31 c32 c33 c34 c35 c36 c37 c38 c39))
(define s4 (slot c41 c42 c43 c44 c45 c46 c47 c48 c49))
(define s5 (slot c51 c52 c53 c54 c55 c56 c57 c58 c59))
(define s6 (slot c61 c62 c63 c64 c65 c66 c67 c68 c69))
(define s7 (slot c71 c72 c73 c74 c75 c76 c77 c78 c79))
(define s8 (slot c81 c82 c83 c84 c85 c86 c87 c88 c89))
(define s9 (slot c91 c92 c93 c94 c95 c96 c97 c98 c99))
(define s10 (slot c11 c21 c31 c41 c51 c61 c71 c81 c91))
(define s11 (slot c12 c22 c32 c42 c52 c62 c72 c82 c92))
(define s12 (slot c13 c23 c33 c43 c53 c63 c73 c83 c93))
(define s13 (slot c14 c24 c34 c44 c54 c64 c74 c84 c94))
(define s14 (slot c15 c25 c35 c45 c55 c65 c75 c85 c95))
(define s15 (slot c16 c26 c36 c46 c56 c66 c76 c86 c96))
(define s16 (slot c17 c27 c37 c47 c57 c67 c77 c87 c97))
(define s17 (slot c18 c28 c38 c48 c58 c68 c78 c88 c98))
(define s18 (slot c19 c29 c39 c49 c59 c69 c79 c89 c99))
(define s19 (slot c11 c12 c13 c21 c22 c23 c31 c32 c33))
(define s20 (slot c14 c15 c16 c24 c25 c26 c34 c35 c36))
(define s21 (slot c17 c18 c19 c27 c28 c29 c37 c38 c39))
(define s22 (slot c41 c42 c43 c51 c52 c53 c61 c62 c63))
(define s23 (slot c44 c45 c46 c54 c55 c56 c64 c65 c66))
(define s24 (slot c47 c48 c49 c57 c58 c59 c67 c68 c69))
(define s25 (slot c71 c72 c73 c81 c82 c83 c91 c92 c93))
(define s26 (slot c74 c75 c76 c84 c85 c86 c94 c95 c96))
(define s27 (slot c77 c78 c79 c87 c88 c89 c97 c98 c99))
ためしに解いてみる問題としては、「数学セミナー」の2006年5月号の西川さんの記事41ページに掲載されているものを使うことにした。ちょっとみにくいけど、こんな問題。
(5)(3)( )( )(7)( )( )( )( )
(6)( )( )(1)(9)(5)( )( )( )
( )(9)(8)( )( )( )( )(6)( )
(8)( )( )( )(6)( )( )( )(3)
(4)( )( )(8)( )(3)( )( )( )
(7)( )( )( )(2)( )( )( )(6)
( )(6)( )( )( )( )(2)(8)( )
( )( )( )(4)(1)(9)( )( )(5)
( )( )( )( )(8)( )(1)(7)(9)
これらの初期値を次のように各セルに設定する。
(set-possibility! c11 '(5))
(set-possibility! c12 '(3))
(set-possibility! c15 '(7))
(set-possibility! c21 '(6))
(set-possibility! c24 '(1))
(set-possibility! c25 '(9))
(set-possibility! c26 '(5))
(set-possibility! c32 '(9))
(set-possibility! c33 '(8))
(set-possibility! c38 '(6))
(set-possibility! c41 '(8))
(set-possibility! c45 '(6))
(set-possibility! c49 '(3))
(set-possibility! c51 '(4))
(set-possibility! c54 '(8))
(set-possibility! c56 '(3))
(set-possibility! c61 '(7))
(set-possibility! c65 '(2))
(set-possibility! c69 '(6))
(set-possibility! c72 '(6))
(set-possibility! c77 '(2))
(set-possibility! c78 '(8))
(set-possibility! c84 '(4))
(set-possibility! c85 '(1))
(set-possibility! c86 '(9))
(set-possibility! c89 '(5))
(set-possibility! c95 '(8))
(set-possibility! c97 '(1))
(set-possibility! c98 '(7))
(set-possibility! c99 '(9))
この時点ですべてのセルの値が更新されちゃっているのがconstraint progamingのおもしろいところ。あとは出力だけしてやればいい。
ただし、上記に書いたように最初に与えている関係が不十分なので、解は求まりきってない。
(define (print-possibilities size . cells)
(let R ((ls cells) (cnt 1))
(cond ((null? ls)
'done)
((= 1 (remainder cnt size))
(newline)
(display (get-possibility (car ls)))
(R (cdr ls) (+ cnt 1)))
(else
(display (get-possibility (car ls)))
(R (cdr ls) (+ cnt 1))))))

(print-possibilities 9
c11 c12 c13 c14 c15 c16 c17 c18 c19
c21 c22 c23 c24 c25 c26 c27 c28 c29
c31 c32 c33 c34 c35 c36 c37 c38 c39
c41 c42 c43 c44 c45 c46 c47 c48 c49
c51 c52 c53 c54 c55 c56 c57 c58 c59
c61 c62 c63 c64 c65 c66 c67 c68 c69
c71 c72 c73 c74 c75 c76 c77 c78 c79
c81 c82 c83 c84 c85 c86 c87 c88 c89
c91 c92 c93 c94 c95 c96 c97 c98 c99
)
実行結果
gosh> print-possibilities
gosh>
(5)(3)(2 4)(6)(7)(8)(9)(1 2 4)(1 2)
(6)(7)(2 4)(1)(9)(5)(3)(2 4)(8)
(1)(9)(8)(3)(4)(2)(5)(6)(7)
(8)(2 5)(9)(7)(6)(1)(4)(2 5)(3)
(4)(1 2)(6)(8)(5)(3)(7)(9)(1 2)
(7)(1 5)(3)(9)(2)(4)(8)(1 5)(6)
(9)(6)(1)(5)(3)(7)(2)(8)(4)
(2)(8)(7)(4)(1)(9)(6)(3)(5)
(3)(4)(5)(2)(8)(6)(1)(7)(9)done
この結果を漫然と見る限り、スロット内での重複関係を検証するだけでは解に至らないみたいだ。ここから先は、とあるセルの可能性をどちらか選択してみて、整合性がある解を探索していくしかないのだろうか?

2006/06/13

歯医者。磨きすぎといわれてしまった。歯茎が弱っちゃうって。うーん。自分の認識ではちゃんと磨けてる気がしてなかったんだけど……軽く強迫神経症ぎみになってるのかもしれない。電動ハブラシにすべきなんだろうか。すべきなんだろうなあ。でも置いておく場所がない。

歯医者って一般に「気が滅入ること」リストの上位に食い込むはずの存在だと思う。ところが、むしろ楽しみにしている部分があったりもしているわけですよ。もちろん歯科医院の雰囲気がいいというのもあるけど(受け付けの女の子がけだるそうにきちんと仕事してるようすとか)、それ以上に、ここのところ、いっそう、気の滅入ることが、多すぎる……

2006/06/10

誰も読む必要がない、ザ・日記が続きます。

朝から実家のある柏へ。レイソル戦のチケットを一緒に観戦する友人Kから受け取る。彼はゴール裏の自由席で観戦するので、試合開始の5時間も前からひたすら並んでいる。僕のほうはバックグラウンド側の指定席なので、一緒に観戦するといっても、試合中はお互いに別々の場所に陣取ることになる。ゴール裏は歌をうたったりして応援しなければならないので、つらいんですよ。

そんなわけで僕には試合開始までたっぷり時間がある。まず、彼の自転車を借りて実家へ。たまに顔を出すというのが一番難しい。主にピアノや猫と遊ぶ。それから別の旧友と待ち合わせて昼食。頼まれていた古い絵本を渡す。彼女と話をしていると、いつも、人間の面白さと社会に対する生産性とは相関しないものだと不思議に思う。いや、単純に「類は友を呼ぶ」なのかもしれない。たぶん、彼女も僕も、周囲から見ると同様に計りがたい類なんだろう。

試合開始時間がせまってきたので、あわただしく別れる。彼女は現役の柏市民だけど、ほとんどの柏市民の例に洩れず、レイソルには興味がない。なんか観戦に行く人達って遠足みたいに大きいバッグ持ってぞろぞろ歩いてるよね、とか、そういう感想がせいいっぱいらしい。

試合は楽しかった。個人的には久しぶりに勝ち試合を見ることができたし。

試合後、友人Kと合流してしばらくぶらぶらしてから、新宿の別な友人たちとの飲み会に参加して実のない一日を締めくくる。実のない会話を渾々と続けられる友人がたくさんいることが休日プレイの成否を決めると思う。そして休日プレイは生きていくのに絶対に必要な時間なわけで。

2006/06/06

歯医者。ここ数週間というもの、抜歯した奥歯の跡をどうするかという問題に頭を悩ませていた。方法は4つ。
  • 放置
  • 左右の歯を柱にしてブリッジをかける
  • 部分入れ歯
  • インプラント
デフォルトの治療方法は2番目のブリッジらしい。でも、そもそもこんな状態になった原因は、10年以上前に虫歯跡にかぶせた金属のクラウンの内部で腐食が進んでいたことだと思っているので、歯磨きによる日常のメンテナンスが困難な治療方法は嫌だ。つまり、ブリッジはいや。それに、ブリッジをかけるには左右の健全な歯を削らなければならないんだって。いまのところ左右の歯にはなんの障害もないのに、それを削るのは避けたい。
ブリッジでなければ、普通は入れ歯になるらしい。うーん。この年齢で入れ歯は遠慮したい。で、いっそのこと放置するのはダメなのかと聞いたら、上下左右の歯に支えがない状態になるため、虫歯はともかく歯茎の病気になりやすいくなるらしい。
というわけで、残された治療方法はインプラントしかないっぽい。インプラントは歯茎の骨に支柱を埋め込み、それに人工の歯を設置する方法で、文字通り新しい歯を一本埋め込む。したがって左右の歯を削ることもないし、かぶせものではないので普通に磨ける。ほかの歯への影響が少なく、メンテナンスが容易ってことで、やっぱり歯の治療もモジュール化が重要だな。難点は保険がきかないこと。1本につき30万円くらいみなければならないらしい。あと、僕の場合は土台になる歯茎の骨が再生するのを待たなければならないとのことで、最悪再生しない場合はブリッジをかけるしかないという問題もある。
ものすごく長いスパンで影響を及ぼすことなので、金額の問題は飲む覚悟を決めた。まあ、ぶっちゃけラップトップ一台分だと思えばいいんでしょ。あとは骨が再生するのを願うばかり。

2006/05/28

Dexter社のWalkMocsという靴が気に入っていた。靴底がウレタンのような特殊な材質で、革も軟らかく、なにより出来がよくてはきやすい。結婚したころに恵比寿の三越で見つけて購入したもので、そのころには国内に正規代理店があったんだろう。
最近になって靴底がだめになってしまったので修理したいと思い、取扱店を探したんだけど、ない。どうやら日本での取扱がなくなってしまったようだ。ボーリングシューズだけはどっかのボーリング用品店が輸入しているっぽいけど。こんなことなら先週USにいったときに注意して探せばよかった。革はまだまだしっかりしているので、普通の靴底でもいいから何とか修理できないかなあ。
このメーカーの靴が自分の足に合うことは分かっているので、USのWebサイトから購入しちゃうか。WalkMocsというシリーズはなくなってしまったようだけど、このDiscoveryが近い製品みたい。

2006/05/27

パズル「九個の?」をSchemeで解く

かれこれ1年以上も解けていないパズルがあった。ペントミノの一種で、9個のクエスチョンマークを9×8のグリッドに詰めるというもの。以下のページでJavaアプレットが遊べる(はず)。

実は年末にも一回挑戦している。このときは結局、3日3晩かけても計算が終わらなかった。 解法として思い付くのは、グリッドにクエスチョンマークを置く組み合わせを総当たりで調べる方法のみなんだけど、各クエスチョンマークは上下左右裏表に自在におくことができるため、グリッドのどこかにクエスチョンマークを1つ配置するだけで実は208パターンにもなってしまう。そうすると、調べなければいけない組み合わせはペタオーダーになり、今のコンピュータでは一時的に保持することすら物理的に無理な大きさになる。Gaucheに用意されているcombination-for-eachを使えばいい具合に対処してくれるかもしれないと楽観したけど、やっぱりだめだった。ここまでは咋年末の話。

実際にはクエスチョンマークが安易に重なってしまうようなパターンがほとんどなので、それを無視しつつ組み合わせを求めるようにすれば計算量の爆発が抑えられそうなものだ。そのためのプロシージャは先日作った。というわけで、あらためてこの問題に対峙すべく年末のプログラムを書き直してみた。

; 9q-problem.scm
; 2006/5/26
;
; solver for the "9 questions" quize
; k16.shikano 

(use srfi-1)

(define row 9)
(define line 8)

;; question-mark
(define (face s n)
  (call/cc (lambda (break)
    (cond ((= n 1)
           (if (or (> (+ (remainder s row) 2) row) (> (+ (quotient s row) 6) line))
               (break '())
               (list s                (+ s 1)           ; **
                                      (+ s row 1)       ;  *
                     (+ s (* 2 row)) (+ s (* 2 row) 1)  ; **
                     (+ s (* 3 row))                    ; * 
                                                        ;   
                     (+ s (* 5 row)))))                 ; * 
          ((= n 2)
           (if (or (> (+ (remainder s row) 2) row) (> (+ (quotient s row) 6) line))
               (break '())
               (list s               (+ s 1)            ; **
                     (+ s row)                          ; * 
                     (+ s (* 2 row)) (+ s (* 2 row) 1)  ; **
                                     (+ s (* 3 row) 1)  ;  *
                                                        ;   
                                     (+ s (* 5 row) 1)  ;  *
                     )))
          ((= n 3)
           (if (or (> (+ (remainder s row) 2) row) (> (+ (quotient s row) 6) line))
               (break '())
               (list                 (+ s 1)            ;  *
                                                        ;   
                                     (+ s (* 2 row) 1)  ;  *
                     (+ s (* 3 row)) (+ s (* 3 row) 1)  ; **
                     (+ s (* 4 row))                    ; * 
                     (+ s (* 5 row)) (+ s (* 5 row) 1)  ; **
                     )))
          ((= n 4)
           (if (or (> (+ (remainder s row) 2) row) (> (+ (quotient s row) 6) line))
               (break '())
               (list s                                  ; * 
                                                        ;   
                     (+ s (* 2 row))                    ; * 
                     (+ s (* 3 row)) (+ s (* 3 row) 1)  ; **
                                     (+ s (* 4 row) 1)  ;  *
                     (+ s (* 5 row)) (+ s (* 5 row) 1)  ; **
                     )))
          ((= n 5)
           (if (or (> (+ (remainder s row) 6) row) (> (+ (quotient s row) 2) line))
               (break '())
               (list s (+ s 2) (+ s 3) (+ s 5)           ; * ** *
                     (+ s row) (+ s row 1) (+ s row 2)   ; ***
                     )))
          ((= n 6)
           (if (or (> (+ (remainder s row) 6) row) (> (+ (quotient s row) 2) line))
               (break '())
               (list s (+ s 2) (+ s 3) (+ s 5)           ; * ** *
                     (+ s row 3) (+ s row 4) (+ s row 5) ;    ***
                     )))
          ((= n 7)
           (if (or (> (+ (remainder s row) 6) row) (> (+ (quotient s row) 2) line))
               (break '()) 
               (list s (+ s 1) (+ s 2)                             ; ***
                     (+ s row) (+ s row 2) (+ s row 3) (+ s row 5) ; * ** * 
                     )))
          ((= n 8)
           (if (or (> (+ (remainder s row) 6) row) (> (+ (quotient s row) 2) line))
               (break '())
               (list (+ s 3) (+ s 4) (+ s 5)                       ;    ***
                     (+ s row) (+ s row 2) (+ s row 3) (+ s row 5) ; * ** *
                     )))))))

;; available question-mark faces
(define valid-face-list
  (filter (lambda (x) (not (null? x)))
    (let fs ((s 0))
      (if (> s (- (* row line) 1))
          '()
          (let fn ((n 1))
            (if (> n 8)
                (fs (+ s 1))
                (cons (face s n) (fn (+ n 1)))))))))

;; check if two lists are distinct with each other
(define (distinct? l1 l2)
  (= (length (lset-union eq? l1 l2))
     (+ (length l1) (length l2))))

(define (distinct-cdr ls)
  (let R ((tail (cdr ls)))
    (cond ((null? tail) '())
   ((not (distinct? (car ls) (car tail)))
    (R (cdr tail)))
   (else
    (cons (car tail) (R (cdr tail)))))))

(define (trim-combinations ls n proc)
  (cond ((> n (length ls))
         '())
        ((= n 1)
         (map list ls))
        ((> (- n 1) (length (proc ls)))
         (trim-combinations (cdr ls) n proc))
        (else
         (append
          (map (lambda (x) (cons (car ls) x))
               (trim-combinations (proc ls) (- n 1) proc))
          (trim-combinations (cdr ls) n proc)))))

(trim-combinations valid-face-list 9 distinct-cdr)

これを9q-problem.scmとして、シェルからtimeした結果。

[05:37:46] k16@debian:~/gauche $ time gosh 9q-problem.scm > 9q-result.txt 

real    272m22.609s
user    266m0.799s
sys     0m1.174s

約4時間半。その後、求める組み合わせについてmemoizeとかしてみたりもしたんだけど、実行時間は変わらない。おそらく何か間違ってるんだろう。

気になる結果は、互いに対称かもしれない解が全部で16通り得られた(→解答)。

2006/05/24

仕事でワシントンD.C.に行ってきた。無理やり時間をつくってスミソニアン航空宇宙博物館とナショナルギャラリーへ。どちらも市の中心部にあり、無料なので、打ち合わせのない時間に拝観することができた。ホワイトハウスとか見てませんから。興味ないのでどうでもいいんだけど。残念なのは、市内にはない航空宇宙博物館の別館にいけなかったことかなあ。

R0010059

R0010146

2006/05/15

Firefox 1.5でいつのまにか日本語の均等割り付けができるようになってるのにきがついた。

むかしは苦労したものだ。http://k16journal.blogspot.com/2005/05/htmlcss2.html

2006/05/14

LaTeX(TeX)で文字列中の文字を置換したい。

cf. Character substitution in TeX
http://hisashim.livejournal.com/276024.html

上記のページにほとんど目的の答えがあるので、これをもう少し汎用にしてみた。
\newcommand{\replacechar}[3]{{\wordbyword{#2}{#3}#1\end }}
\newcommand{\cutoff}[2]{{\relax}}
\def\wordbyword#1#2#3{\ifx#3\end \let\next=\cutoff
\else\ifx#3#1#2%
\else#3%
\fi \let\next=\wordbyword\fi \next{#1}{#2}}
\replacecharの第1引数に文字列、第2引数に置換前の文字、第3引数に置換後の文字を指定する。
いくつか制限がある。判明しているのは以下のとおり。
  • 文字列中のスペースは切り詰められる
  • ほかのコマンドの中で使うには\string\replacechar{foo}{o}{a}などとする必要がある
上記の2番目の制限は、どうやら\defの再帰がトップレベルでしか使えないためっぽい。
同じ理由で、\replacecharを入れ子にして使えない。つまり、文字列中の複数の文字を置換したかったら、同様な方法で新しいマクロを定義する必要がある。たとえば、索引の特殊文字をエスケープするコマンドは、次のようにして作れる。
追記:この例では「"」そのもののエスケープができないので注意。
\newcommand{\indexescape}[1]{{\indexwordbyword#1\end }}
\def\indexwordbyword#1{\ifx#1\end \let\next=\relax
\else\ifx#1{!}"!%
\else\ifx#1{@}"@%
\else\ifx#1{|}"|%
\else#1%
\fi\fi\fi \let\next=\indexwordbyword\fi \next}

\def\myindex#1{\index{\string\indexescape{#1}}}
\myindexの定義に\stringを使っているのも2番目の制限のため。

いちおう、実行例。

replacechar.tex
replacechar.pdf

2006/05/12

sumiiの日記 - callccによる排中律の証明
http://d.hatena.ne.jp/sumii/20060507/1147006438

さらに劣化コピー。Schemeのcall/ccで悪魔の契約書を作ってみる。型についてはまったく無知なので、排中律の証明とは関係ありません。
(昨日は会社でhisashimさんに適当な説明をした気がする。ごめんなさい。)

追記:最初のは間違ってたので差し替えました。
(define able-to-pay? #f)
(define remind-contract #f)

(define (devils-contract init-choice)
(let ((ability able-to-pay?))
((lambda (choice)
(cond ((equal? 'first-answer choice)
(display ""))
((and (equal? 'B choice) ability)
(display "Say any wish!"))
(else
(display "Devil gives you one billion dollars"))))
(call/cc
(lambda (continuation)
(cond ((equal? 'A init-choice)
(display "Devil chooses A"))
((equal? 'B init-choice)
(display "Devil chooses B")))
(set! remind-contract continuation)
(continuation 'first-answer))))))
この挿話は、悪魔にとって選択肢が(A)と(B)しかありえないことがポイントなんだと思う。つまり、(B)じゃなければ(A)。(B)でもないし(A)でもないってことはありえないドライな世界。上のコードだと、最初のcondが契約書に相当するつもり。
で、悪魔は自分が「発話した内容」なんて覚えちゃいない。上のコードでいうと、call/ccの中のcondは覚えちゃいない。あくまでも契約書オンリーなので、後から1億ドル払っても、(B)じゃなかったんだから(A)を履行するってことなんだと思う。

くだんのシナリオは、こんな感じ。
gosh> (devils-contract 'B)
Devil chooses B
gosh> (set! able-to-pay? #t)
#t
gosh> (remind-contract 'B)
Devil gives you one billion dollars

最初の(devils-contract 'B)で悪魔自身は「(B)を選びます」と言っているけど、人間が1億ドル払わなかった時点で実は(A)の契約が成立している。あとから1億円用意(set! able-to-pay? #t)してもだめ(悪魔の契約履行が10年後だったのがひっかけっぽいかも)。

1億円支払い可能な状態で契約し、悪魔が(B)を選択すれば、望みがかなえられるんでしょう。そんな人に悪魔が契約を持ち込むとは思えませんが……
gosh> (set! able-to-pay? #t)
#t
gosh> (devils-contract 'B)
Devil chooses B
gosh> (remind-contract 'B)
Say any wish!

2006/05/10

去年の秋から超朝方を心がけているのだけど、それが可能な体調の期間と困難な体調の期間(ねむ期)がある。ねむ期には生産性のピークが20:00過ぎに訪れるが、それでも非ねむ期における早朝の生産性には程遠い。
ここ一ヶ月にわたって長いねむ期が続いている。ねむ期から抜け出す方法が知りたい。ねむ期→非ねむ期の切り替えは休日の直後に訪れることが経験的にわかっていて、ということは休めばいいのか……

2006/05/08

枝刈りをしながら組み合わせを求めたい。つまり、似たような要素を同一視して、集合の総数を絞りながら組み合わせを求めていきたい。

ふつうなら集合をユニークな要素だけで構成しなおしてから組み合わせを求めればいいんだけど、「ユニーク」の意味によってはそれができない場合もある。
たとえばベクトルからなる集合で、「いずれかの項が同じであれば同一視」のような場合。次のような2次元ベクトルからなる集合Aがあるとして、
A = {(1, 2) (2, 3) (3, 4) (4, 5) (5, 6) (6, 7)}
集合Aからすべての項が異なる3つのベクトルを取り出す組み合わせは、
{(1, 2) (3, 4) (5, 6)}, 
{(1, 2) (3, 4) (6, 7)},
{(1, 2) (4, 5) (6, 7)},
{(2, 3) (4, 5) (6, 7)}
の4つになるだろう。この4つを求めるのに、すべての3要素の組み合わせを求めてから相異なる要素で構成されているものを取り出していると、集合が大きくなるにつれ厄介なことになるのが目に見えている。かといって、集合Aをあらかじめユニークな要素だけで再構成することもできない。

まず、ふつうの組み合わせを求める combinations プロシージャを次のような戦略で考える。

集合をリスト ls とみなし、その要素から n 個の組み合わせをすべて求めるプロシージャ (noraml-combinations ls n) を、次の 1.と 2.の append として作る。
  1. (car ls) と (noraml-combinations (cdr ls) (- n 1)) の cons
  2. (normal-combinations (cdr ls) n)
1.から「(car ls) を先頭の要素に持つ組み合わせ」がすべて得られ、2.で同様の操作をリスト全体にわたって行うつもり。ザ・リストの再帰処理。
(define (normal-combinations ls n)
(cond ((> n (length ls))
'())
((= n 1)
(map list ls))
((> n (+ 1 (length (cdr ls))))
(list ls))
(else
(append
(map (lambda (x) (cons (car ls) x))
(normal-combinations (cdr ls) (- n 1)))
(normal-combinations (cdr ls) n)))))
境界条件がなんか複雑で、本当にこれであってるのかよくわからないのはここだけの話。まあ、とりあえず意図通りの結果にはなるみたい。
gosh> test-set
((1 2) (2 3) (3 4) (4 5) (5 6) (6 7))
gosh> (normal-combinations test-set 3)
((#0=(1 2) #1=(2 3) #2=(3 4)) (#0# #1# #3=(4 5)) (#0# #1# #4=(5 6))
(#0# #1# #5=(6 7)) (#0# #2# #3#) (#0# #2# #4#) (#0# #2# #5#)
(#0# #3# #4#) (#0# #3# #5#) (#0# #4# #5#) (#1# #2# #3#)
(#1# #2# #4#) (#1# #2# #5#) (#1# #3# #4#) (#1# #3# #5#)
(#1# #4# #5#) (#2# #3# #4#) (#2# #3# #5#) (#2# #4# #5#)
(#3# #4# #5#))
枝刈りしながら組み合わせを求めるという本題を達成するには、枝刈りプロシージャ proc を渡して、1.の操作の cdr を proc に変えればいいだろう(2.の部分の cdr はリストの再帰的な操作のためのものなので、proc に変える必要はない)。
(define (trim-combinations ls n proc)
(cond ((> n (length ls))
'())
((= n 1)
(map list ls))
((> (- n 1) (length (proc ls)))
(trim-combinations (cdr ls) n proc))
(else
(append
(map (lambda (x) (cons (car ls) x))
(trim-combinations (proc ls) (- n 1) proc))
(trim-combinations (cdr ls) n proc)))))
枝刈りプロシージャとしては、ベクトルが相異なることを表現する distinct? と、リストとして表した集合から car と相異なる cdr を導く distinct-cdr 用意する。gauche の lset-union は、(use srfi-1) が必要だね。
(define (distinct? v1 v2)
(= (length (lset-union eq? v1 v2))
(+ (length v1) (length v2))))

(define (distinct-cdr ls)
(let R ((tail (cdr ls)))
(cond ((null? tail) '())
((not (distinct? (car ls) (car tail)))
(R (cdr tail)))
(else
(cons (car tail) (R (cdr tail)))))))
実行結果。
gosh> (trim-combinations test-set 3 distinct-cdr)
((#0=(1 2) #1=(3 4) (5 6)) (#0# #1# #2=(6 7)) (#0# #3=(4 5) #2#) ((2 3) #3# #2#))
しかしアレだな。lengthとか使いすぎなので、あまり効率よくないんじゃないか、これ。

2006/05/06

『RailsによるアジャイルWebアプリケーション開発』の制作方式

ここのところ『RailsによるアジャイルWebアプリケーション開発』の制作方式について意見を求められる機会が何回かあったので、もう半年も前のことだけどまとめてみる。

前提として、ふつうのコンピュータ書籍の制作過程には昨日定義した「後戻り困難ポイント」があり、それが原因で誰かが泣いている。誰も泣かないようにするには、昨日愚痴った「後戻り困難ポイント」を埋めてしまえばいい。それには、現在の手作業によるページレイアウトの工程(つまり組版工程)を放棄して、内容に責任を持つべき人間が印刷の直前までハンドリングできるようにすればいい。

『RailsによるアジャイルWebアプリケーション開発』の制作では、この方針を実現すべく、以下のような方法を採用した。
  • 印刷所に納品するデータはフォント埋め込みのPDF
  • そのPDFはLaTeXによる組版データから生成する
  • しかし原稿はLaTeXではないので、原稿をLaTeXに変換するスクリプトを用意する
  • 原稿はSubversionで版管理する
こうやって書き並べると単純すぎる話だけど、これらの方法を採用することによるメリットは強大だった。なにせ、著者(監訳者)や編集者がSubversionからチェックアウトした原稿(≠組版データ)を印刷の直前まで自分で修正でき、その結果が人手を介さずに印刷用の最終的な組版データになるんだから。ようするに、昨日の「後戻り困難ポイント」のうち、組版→編集→執筆の容易な還流が可能になる。あるいは、こういいかえてもいい。これまで組版の工程にかけていた数ヶ月の期間をゼロにできる!

たぶん、こんなのはソフトウェア開発では当たり前のことなんだと思う。ソースコード(原稿)を版管理し、それをデイリービルド(組版)しながら開発(制作)するってだけの話なんだから。ところが現在のコンピュータ書の制作では、コンパイルやビルドに相当する「原稿を組版にする作業」が完全に手作業なため、組版した後で判明した問題を原稿に戻って直したり、直して組版し直した結果をすぐに確認することができない†1

実現にあたっては障壁もいくつかあった。まず、原稿がLaTeXじゃない。また、仮にLaTeXであっても、それだけでは印刷所に安心してデータを渡すことはできない(印刷所の環境で同じようにコンパイルできる保障がない。そのため、印刷所の環境でコンパイルした出力を確認するという作業が不可欠になってしまう)。

印刷所に渡すデータの問題については、PDF/X-1aという業界標準があるので、それに準拠したPDFを生成できれば問題ない。これについては「Debianにotfパッケージをインストールして、dvipdfmxでOpenTypeフォントを埋め込んだPDFを吐き出すまで」を参照。

原稿がLaTeXじゃない問題については、まず原稿がどんな形式だったか示す必要があるだろう。こんな感じのテキストデータだった。
■H1■はじめに
■H2■本書の読み方
本書は初めてRailsに触れる人うんぬん……

★Rubyのコード
本書にはRubyのコードがたくさん出てきます。
しかも予約語は太字に、ダブルクォーテーション内はスラントにしなくちゃなりません。
◆→コード←◆ruby
puts "Hello World"
◆→ここまでコード←◆
ちなみに★で始まってる部分は小さな見出しつきの項目になります。

ここは、また本文に戻ってます。

● 箇条書きもあります。
こんなふうに、なんとなく箇条書きな部分がタブで示されています。
● もうひとつ箇条書き

また本文。

◆→コラム←◆Joeの疑問
枠で囲った記事もあります。「David曰く」「Joeの疑問」のほかに、何も指示のないコラムもあります。
◆→ここまでコラム←◆

1. 箇条書きとは別に
2. 連番もあります

■H3■もっと細かい本書の読み方
脚注もつけなければ◆→訳注 ←◆

■H2■終わりに
おしまい。
これは下訳をお願いした業者さんがよく使っている形式(というか編集指示)を拡張したものだけど、多かれ少なかれどこも似たような「マークアップ」を使っているようだ。見てわかるように、あくまでも人間が手作業で組版するためのコメントみたいな指示書き程度しか施されていない。コンピュータでそのまま処理するにはちょっと厄介な状態といえる(しかも、バリデータなんてないから、けっこういいかげん)。

このような「自然言語+簡易マークアップ」の構造を読み取って適切なLaTeXのスタイルに対応付けるためのフィルタを用意する必要がある。今回はゆるい規則を処理しなければいけないこともあって、後から柔軟にフィルタの仕様を変更できるようなGaucheスクリプトを正月にでっちあげた(私的に余暇を利用して作ったものなので、後日公開する予定。いま見返すと謎な処理が多いけど、なんとか目的の動作は実現している)。

上記の例の変換結果は以下のとおり。
\chapter{はじめに}%

\section{本書の読み方}%

本書は初めてRailsに触れる人うんぬん……%

%

\begin{entry}%
\item[Rubyのコード]
\item 本書にはRubyのコードがたくさん出てきます。
\item しかも予約語は太字に、ダブルクォーテーション内はスラントにしなくちゃなりません。
\begin{ruby}

puts \codesl{"Hello World"}
\end{ruby}%
\item ちなみに★で始まってる部分は小さな見出しつきの項目になります。%
\end{entry}%

%

ここは、また本文に戻ってます。%

%

\begin{myitemize}%
\item 箇条書きもあります。%
こんなふうに、なんとなく箇条書きな部分がタブで示されています。
\item もうひとつ箇条書き%%
\end{myitemize}%

%

また本文。%

%

\begin{column}{J}{の疑問}
枠で囲った記事もあります。「David曰く」「Joeの疑問」のほかに、何も指示のないコラムもあります。
\end{column}%

%

\begin{enumerate}%
\item 箇条書きとは別に%
\item 連番もあります%%
\end{enumerate}%

%

\subsection{もっと細かい本書の読み方}%

脚注もつけなければ\footnote{\kern-.5zw[訳注]}%

%

\section{終わりに}%

おしまい。
このLaTeXの出力から書籍にするには、さらに各要素についてスタイルを定義する必要がある。実はこの作業がいちばん大変なところなんだけど(LaTeXのいい加減な規則や拡張に起因)、これは会社の業務として作成したものなので今のところ公開できない。まあ、LaTeXの泥臭いところが満載なので、実際のところあまり面白くないし。

さて、ここまでは、この方法が従来の方法に比べて万能であることを意図的に強調してきたけれど、現実には適用できないプロジェクトが大半である。著者や制作業者の並々ならない協力が必要なこと、全員がアクセスできるサーバ環境が必要なこと、編集者に現状に対する問題意識が少ないこと、など原因はいろいろある。今回はとくに変換スクリプトをSchemeで作っちゃったりしたので、問題意識のある編集者であっても実際に使ってもらいにくい。

希望はある。こういった問題を解決して汎用性の高いツールにまとめあげる大仕事を身を挺して背負ってくれそうな人がいる。できる限りの協力はしようと思う。



もちろん例外はあって、最初から(商品として妥当な)レイアウトを含めて執筆された(執筆者のローカル環境以外でも同様にコンパイルが通る)LaTeXの原稿があれば、少なくとも執筆者は現在でも最後まで原稿を修正できる。ただし、編集者にLaTeXのスキルがなかったり、印刷所でコンパイルが通らなかったりして、必ずしもうまくいくとは限らない。

2006/05/05

ふつうのコンピュータ書籍がどうやってつくられているか。
  1. 企画
  2. 執筆や翻訳
  3. 編集
  4. 組版
  5. 印刷製本
おわり。

といいたいとこなんだけど、現実はこんなにシンプルじゃない。問題なのは、各ステップがほとんど分裂していること。
  • 編集してから執筆をやり直してもらうことは、よほどのことがない限りできない。
  • 組版してから編集をやり直すことは、実際には頻繁にやらざるをえないんだけど、とても手間と時間がかかる。
  • 書いてはみたけど時間が経ちすぎて市場性がいまいちになっちゃったね。でも企画からやり直すわけには……
  • 当然のことながら、印刷してから誤植が見つかっても直せない。
うー。

上にあげた4つの「後戻り困難ポイント」のうち、最後の1つは物理的にどうしょうもない。どんな製造業にも後戻りできない一歩っていうのがあって、書籍制作の場合にはそのひとつが印刷工程なんだと思う(流通するまでは本当の意味で後戻りできないわけじゃないんだけど)。

で、残りの3つの「後戻り困難ポイント」に直面した場合どうなるか。従来ありがちなのは、順に
  1. 読者が泣く
  2. 制作業者が泣く
  3. 担当者(i.e. 出版社)が泣く
  4. 著者が泣く
この順番に並ぶのは理由がある。まず、「後戻り困難ポイント」に直面するのは制作中の書籍の内容に十分な価値が認められない危惧が生じた場合なわけで、そのまま後戻りできずに流通までいたってしまった書籍の読者が泣く(このケースがほんとに多くていやになる)。
残りは読者が泣いていないケース。つまり、後戻りが不要だった(原稿が完璧で編集も完璧で組版も完璧)か、どっかの時点で困難を乗り越えて後戻りに成功した本である。「後戻りに成功」って書くと、プロジェクトX的な何かっぽくて聞こえがいいけれど、そんなわけはない。誰かがどこかで泣きながら困難な後戻りをやっている。誰がやっているかっていうと、出版社は著者に頭があがらないし、制作業者は出版社に頭があがらないから、推して知るべし。

すっかり愚痴っぽくなってるけど、ようするに現在の書籍制作は前近代的な「誰かが泣く」ソリューションに負っている。もちろん各工程で何も問題がおきなければいいんだけど、文筆のプロではない著者に本業の傍らで執筆してもらい(しかも半ば善意で)、それを一人の編集者が何本も同時にハンドリングし、安い単価でMacオペレータに手作業で組版してもらっている限り、デフォルトで誰かが泣いている。ということは、現在のやり方には何かしら問題がある。

どこに問題があるんだろう。考えられる可能性は、こんなとこ。
  • 紙の本が儲からなすぎ。何事も品質を求めれば金がかかるけど、金をかけようとしないので品質が悪くなり、読者が泣く。あるいは、何とか限られた金額で品質を高めようとして制作業者が泣く。編集者もサービス残業漬けになって泣く。
  • みんな紙が好きすぎ。とにかく紙に印刷されたものベースでしか制作が進まない。内容に責任を負うべき人間が制作にかかわる唯一の方法は、紙へ手作業で赤字を書き入れること。それをもとに、内容には関与しない人間が、やはり手作業でちまちまとデータを修正する。赤書きした本人が修正結果を確認できるのは数週間後だったりする。修正作業者が内容を理解しているわけではないので、その作業が新たな問題を生むことも少なくない。
  • 制作技術の進歩がなさすぎ。ページレイアウトを作るのに、いまだに植字工が活版を組んでいるのと原理的に同じ作業をコンピュータを使って手作業でやってる。一度組んでしまったものをスケジュールを崩さずに直すのは不可能。あとどうしょうもなくバカバカしいのは、節番号や図暗号の連番をふったり、ページ番号を参照したり、索引のページを解決したりするのが、全部手作業なこと。そんなのLaTeXやMS Wordでも自動でできるって(DTPソフトによってはできるものもあるけど、オペレータの数が限られていて一般には利用されていないというオチ。このへんも手作業な世界観が支配的で情けなくなるところ)。
というわけで、企画するまではともかく、そこから先の印刷直前までの工程は一種のバクチなのが実情。

ではどうするか。いちばんキモなのは、内容に責任を持つ人間が最終的なページレイアウトまでをハンドリングできるようにすること。紙に赤字で修正指示を出して……という他人任せな方法は極力回避する。これには2つメリットがある。
  • ありえないミスがなくなる。赤字の修正指示は字の汚い人間にとって苦痛なだけでなくリスキーでもある。それを見てデータを直す人間が内容を理解していれば対応できるけど、専門書でそんなことは期待できないわけで。とくに数式をよろしく対応してもらうのは絶望的
  • 制作期間を短縮できる。紙をやりとりするのは時間の無駄。
これを実現するには、「最終的なページレイアウト」とか、そういう夢見心地な発想をあきらめること。この発想の背景には、内容とレイアウトは別物という意識がある。たぶんこの意識はページレイアウトをする側のものだと思う。確かに本当に凝ったレイアウトを扱うにはそれだけを見る人間が必要だけど、そんなのは「伝票をチェックするためだけに人を雇う」というのと同じ発想で、それだけの規模がある業務なりプロジェクトなりでなければ無駄でしかない。(ちなみにここでレイアウトって言ってるのはデザインのことじゃない。)

で、ページレイアウトって、正直Webページ程度の表現力があれば事足りるものが多い。Webページであれば、公開する直前まで執筆してる人間が内容を修正し、それにCSSなりでスタイルを当てれば十分なコンテンツになる。しかも、執筆している人間に公開の直前まで許されている修正は、「てにおは」レベルのものじゃない。文章の階層構造はもちろん、説明の順番や図の配置まで、全部修正できる。どうして書籍の制作ではWebページのようにぎりぎりまで原稿を修正することができないのだろう。
Webブラウザと紙ではメディアとしての性格が違うという人も(DTPによる書籍制作にかかわってきた人のなかには)いるだろうけど、それは説得力がない。LaTeXとか、20年前からふつうに同じようなことができてたわけで、紙の制作に限って技術的な制限があるなんていうのはDTPソフト会社にだまされているだけだ。

2006/04/25

今日の一行 2006-04-20 [quiz] 部分木の格上げ
http://oss.timedia.co.jp/index.fcgi/kahua-web/show/ossz/oneline/2006-04-20

「述語と木を与えて,述語を満すラベルの付いた部分木をその親の直ぐの弟にする関数を書け.」という問題。またまた出遅れ気味の回答。この翌日で、逆に部分木を格下げする問題も出題されているけど、こちらはカテゴリがquizではないらしいので手をつけないことにしよう。この問題だけで力尽きたともいう。
(define (lookup subtree pred)
(let lookup-for-suns ((suns (cdr subtree)))
(cond ((null? suns) '())
((pred (caar suns)) (car suns))
(else
(lookup-for-suns (cdr suns))))))

(define (include? subtree pred)
(let check-for-suns ((suns (cdr subtree)))
(cond ((null? suns) #f)
((pred (caar suns)) #t)
(else
(check-for-suns (cdr suns))))))

(define (without-grandchild? tree)
(or (null? (cdr tree))
(let without-children? ((suns (cdr tree)))
(cond ((null? suns) #t)
((null? (cdr (car suns)))
(without-children? (cdr suns)))
(else #f)))))

(define (extract tree pred)
(cond ((null? tree) '())
((pred (caar tree))
(extract (cdr tree) pred))
(else
(cons (car tree)
(extract (cdr tree) pred)))))

(define (rankup tree pred)
(if (without-grandchild? tree)
tree
(cons (car tree)
(let rankup-for-suns ((suns (cdr tree)))
(cond ((null? suns) '())
((include? (car suns) pred)
(cons
(cons (caar suns)
(extract (cdar suns) pred))
(cons (lookup (car suns) pred)
(rankup-for-suns (cdr suns)))))
(else
(cons (rankup (car suns) pred)
(rankup-for-suns (cdr suns)))))))))

(define test-tree
(list 'A (list 'B (list 'F)
(list 'G (list 'L)
(list 'M)))
(list 'C (list 'H)
(list 'I (list 'N)
(list 'O (list 'P)
(list 'Q)))
(list 'J))
(list 'D)
(list 'E (list 'K))))

(define eq-I? (lambda (x) (eq? 'I x)))

gosh> test-tree
(A (B (F) (G (L) (M))) (C (H) (I (N) (O (P) (Q))) (J)) (D) (E (K)))
gosh> (rankup test-tree eq-I?)
(A (B (F) (G (L) (M))) (C (H) (J)) (I (N) (O (P) (Q))) (D) (E (K)))

いかにも、SICPの前半を読んでいる最中です、という雰囲気のただよう回答にみえる。きをあつかうのは大変だ。
今日も歯医者。消毒だけだと思って気を抜いていたら、また注射があった。でも、昨晩心配していたような痛みもなく、本当によかった。この後は、一ヵ月くらいそのまま歯茎が再生するのをまって、ブリッジかなにかするらしい。歯茎が再生したらこのままでもいいんだけど、それはダメなんだろうな……

2006/04/24

先週、奥様が自分の歯医者にいくというのでくっついていって検診してもらったら、レントゲンをとられて奥歯を一本抜くことになった。で、いまさっき抜いてきた。小学校のころいれた銀歯で、ずいぶん前からぐらついていたのは自分でも知ってたんだけど、こういうのってどうしても放置しちゃう。結局、長年の間にクラウンの中はすっかりぼろぼろになっていた。レントゲン写真を見て、自分から「抜いてください」とお願いしたくなるくらい。へたに周りの歯がしっかりしているものだから、かえって痛々しさが目立つ。

歯を抜くのは初めてなので、ここ一週間は夜も眠れないくらいびくついていた。だいたい、人間が痛みに耐えるときは歯をくいしばるものなのに、歯を抜くってことはそれができない。麻酔をかければ痛くないっていうけど、その麻酔の注射を歯茎に射すわけじゃん。麻酔されるまで診察台の上で終始手をきつく握り合わせていたら、先生に「そんなに心配しなくて大丈夫ですよ」といわれてしまった。実際、ほとんど痛くなかった。歯を抜く作業も手際がよくて、すーっと何かが抜けていく感覚だけ。ここ一週間、歯を抜く痛みのイメージトレーニングをひそかに繰り返していたので、脳内で大量のエンドルフィンが生成されていただけかもしれない。もちろん、先生の腕もいいんだと思う。彼の一連の作業の流れを見ていればわかる。抜いた後に再度レントゲン撮影して状態を確認するのも好感がもてる。でも、本当に痛み出すのは麻酔が切れる今晩からだっていうしなあ。幸いなのは、頼みの綱として痛み止めと化膿止めをもらったこと。しかも、ロキソニンとケフラールだった。これならうちに山ほどあるので、使い切ってもちょっと安心。