"with" loss of generality

23:48 04/04/07

これ考えたヤツは天才だと思う。

六法

譲ってもらった。まだ本棚を買っていないので、 入手量に気をつけないとすぐに部屋に書物の山が形成されてしまいそう…。 そういえばSBには、3年前に暗号化関係の本を貸すと宣言して それっきりになっていたような気がするっていうか忘れてたすみません。

20:47 04/04/06

Windowsに付属してくるスパイダソリティアというゲームがありまして。 暇つぶしに遊び始めてしまって、気がついたらあっという間に一時間も過ぎていた、 なんて経験をされた人も少なくないと思います。 さてそんなスパイダソリティアの「初級」、 100発100中で解けてつまならいとお考えの方に新しい遊び方を提案いたしましょう。

まずはゲームスタート。

まず開始

オーケイ、スタートだ。そして

全部配る

そしてまず全部配る。さあ解いてみよう!

難易度

上級と同程度以上には難しくなる気がします。 ただ、計算してないので確かなことは言えないですが、 あまりにも運に左右されすぎるゲームになってしまってるかもしれません。

…という遊び方は結構メジャーかと思っていたら、 「そんなことやるのはオマイだけじゃ」と言われてしまったので、 ここで書いてみました。だれか同士はおらんかー。

17:21 04/04/04

傘が家のどこにも見つからないのでどっかに忘れたんだと思うのだけど、 いつどこで忘れたかとかを全く思い出せないのであった。

のであったっていうか、最近雨の日はずっと折り畳み傘で暮らしてたので、 ふつーの傘は押入に突っ込んだまんまだった記憶しかないんだけどなぁ…。 謎だ。

ぎゃー、あったー!(19:41 04/04/04 追記)

19:36 04/03/30

D 0.82の翻訳はちょっとお待ちをー。早く gdc on Zeta なども試してみたいのだけどマジで時間が無い。

移転

転出届と転入届を出してきたので、これにて一応、引っ越し完了。新居住地は この辺 なので、お近くにお立ち寄りの際はピンポンダッシュでもしてって下さい。 歩いて2分で上野動物園ってことで、今度キリンでも見てこよう。

そういえば、mapfanのリンク用URLが大変ユーザーフレンドリーに変わってて素敵。

20:21 04/03/27

ノートPCのバッテリが切れそう

暫定のメール環境からnPOPで手動でゴミメールを消しまくるのは 無理があることに気づき始めたのでPOPFileを入れてみたけれども使い方わかんねー! 状態な今日この頃です。POPFileのプロキシは通ってるみたいなんだけど、 分類もされないし履歴にもでてこないし…。

boost

今考えるとだいぶ前に書いたMPLの例は、 4行もあれば十分だな…。

using namespace boost::mpl;
template<class P, class F>
  struct app : apply<typename lambda<F>::type, P> {};
template<class Base, class Impls>
  struct LinearInherit : fold< Impls, Base, app<_,_> >::type {};

21:11 04/03/22

あんまり復活してないけど復活。コピー転送してるからメールは読めるんだけど、 Firewallのせいで直接POPサーバにアクセスできないので削除が不可能…。 早よ消しにいかないと満杯になってしまう。。。

二個下のやつに致命的な間違いがあったのでチト修正 (list<3*ttree> → list<3*ttree*ttree>)。 「そもそも穴 [] ってのが何なのかがよくわからない」 という感想をもらったので、うまい説明ができないか再思考中…。

RHG読書会でどんな風に話題になったんだろ?

20:59 04/03/20

明日引っ越しをするため、環境が整うまでしばらく更新停止するかもしれません。 しないかもしれません。とりあえず引っ越し先でのネット接続をどーするか考えねば。

有限と微小のパン

去年1冊目を借りてからチビチビと続きを読んでまして、今日、 森博嗣のS&Mシリーズの十作目を読み終えました。 全編通してもっとも印象に残った文を以下に示します。

思いつく言葉はことごとくシミュレートされ、自分が何を言うのかがわかった瞬間に、 彼女がどう答えるのかがわかった。
電気がショートするほど明るく、強く、速い。
不思議にその連鎖が見える。
一瞬にして理解できた。

有限と微小のパン

書かれているのは、たぶん何か別の言葉で表現すればどうってことのないシーン。 けれど、その状況に自分を置いたときに自分の思考ルーチンがはじきだすであろう… "シミュレートされ"、"不思議に"、"見える" というまさにその感覚が綴られている正確さが魅力なのではないかと思いました。 世間で「理系ミステリィ」と呼ばれているということは、 通称「理系」とされている人達の中にはそういう思考ルーチンを持った人が多く、 共感を呼んでいるのでしょうか。

よし、次はVシリーズというやつを読んでみよう。

04:01 04/03/19

卒論ではZipperというデータ構造の改良について研究してたんですけど、 それ繋がりで "The Derivative of a Regular Type is its Type of One-Hole Contexts" (ps) という論文を教えていただきました。 これが個人的に大ヒット。やば、面白すぎる。 有名なテーマなのかもしれんけど、ともかく私は初めて知って大興奮であります。

解説

誰かに語りたくてしかたがないので、てけとーにここで語ってみるテスト。 以下はスペースの都合上思いっきり大雑把な説明しかできてないので、 論理に飛躍があったり、実はあまり正しくない言明をしてる部分があります。 気持ちの部分だけ伝われば…。詳細は参照先の論文やいろいろな書籍をどうぞ。

まず、プログラミング言語の「型」って概念のとらえ方の一つとして、 「代数的データ型」なるものがあります。型の足し算(union)と掛け算(pair) によって複合型を定義するシステム。ML や Haskell を使う人ならなじみ深いはず…こんな感じのものです。 C言語の構造体と共用体を想像してもOK。

// 型と型のpairやtupleは、掛け算で表記する。
type point2D  = int * int         // x,y
type birthday = int * int * int   // year,month,day
type person   = string * int      // name,age

// 型と型のunionというかorは、足し算で表記する。
type variant = int + string + double

// 要素が有限個の型は、要素数の整数で表記する。
type bool = 2

// 再帰的な型(例:二分木)
type tree = μtree . int + tree*tree  // μtreeは、tree型で再帰してます印

// 多相型。α型のリスト
type list<α> = μlist<α>.  1 + α*list<α>

これら代数的データ型について、One-hole-context というものを考えます。 その名の通り、型にぴったり一つ"穴"をあけたもの。

// point2dのint型部分に一個穴を空けた型。
//   int*intの左に穴を空ける場合と右の場合の二通りあるのでunion。
type point2D[:int]  = []*int + int*[]

// variantのstring部分にちょうど一個穴を空けた型。
//   穴があるのはstring部分だとわかっているので、一個穴があることが確定なら、
//   intやdoubleの場合は考える必要がない
type variant[:string] = []

// treeのtree部分にちょうど一個穴を空けた型。
//   穴があるのが葉なのか左の子なのか右の子なのかで3通りに分かれる
//   穴付きtreeも再帰的な定義になる
type tree[:tree] = μtree[:tree]. ([] + tree[:tree]*tree + tree*tree[:tree])

穴空けてどーするんだ、という意見もあるかと思いますが、 point2dやvariantはともかくとして、穴あき二分木を表現できると、 「二分木中の部分木の位置」を表すとか、 「あとで中身を差し込むのだがとりあえず空欄にしといた所のある木」 を表すとかできて便利…かなぁ? 理論ではone-hole-contextはよく使います。

ところで穴を表す型 [] は、穴という状態一種類しか型の要素がないので、 数字の 1 で置き換えてよいでしょう。あとは交換法則とか結合法則で式変形。

type point2D[:int]  = []*int + int*[] = 1*int + int*1 = 2*int

type variant[:string] = [] = 1

type tree[:tree] = μtree[:tree]. ([] + tree[:tree]*tree + tree*tree[:tree])
                 = μtree[:tree]. (1 + 2*tree*tree[:tree])
                 = list< 2*tree >
  // μX. 1+(2*tree)*X の形なのでlistとみなしてしまえる(詳細略)

そんな変形して大丈夫なのか?という疑問は残るかと思いますが、 その不安は棚に上げて結果の型を見てみると、one-hole-context を表現するのに十分な情報は残っていることが確認できると思います。 (2*int の2の方で左右のどっちに穴が空いているかを表し、intの方で、 穴じゃない方のintを表す)(treeのルートから穴にぶつかるまで下に降りていくパスを listで表す。1ステップ1ステップは左右の選択なので、2*treeで表せる) なのでよしとしましょう。

もう一度変形結果を見てみましょう。

// point2d[:int]
(int^2) [:int] = 2*int

// variant[:string]
(int+string+double) [:string] = 1

わかりやすく、型の名前を一文字にしてみると…

x^2 [:x] = 2x

x+y+z [:y] = 1

…なんかこれ、微分してない!?

再帰

μで再帰するなんて操作は微分の方には出てこないので、 対応関係が見て取りにくいんですけど、二分木の場合もこんな風になってます。

μtree.int + tree*tree  [:tree] = list< 2*tree >

まとめ

と、こんな感じで、「型Tの中の型Sの部分に一つ穴を空ける」という操作と 「TをSで偏微分」という、 全くかけらも関係のなさそうな操作が見事に対応することが判明しました。 μの辺りもきっちり定義を追っていくと、 中身の微分をlistで囲った物が結果となることが証明できるようです。

これでもう、三分木 (μttree. int + ttree*ttree*ttree) に穴を空けろといわれても、何か複雑な型 int + int*int + (string*int) にintの穴を空けろと言われても、 機械的に微分すれば一発で求まっちゃいます。答えはそれぞれ、 list< 3*ttree*ttree >1+2*int+string

ついでに、「じゃあ二個穴をあけると?」 と問われたらどうしましょう。 もちろん簡単です。二階微分。

おまけ

μ周りについてもうちょい。x型のリストのone-hole-contextについて考えてみます。 listのx型の場所に穴を空ける場合、穴の右にある要素のリストと、 穴の左にある要素のリストを合わせればone-hole-context が表現できます。なので、

list<x> [:x] = list<x> * list<x>

となるはず。ここで、list<x>とはどういう型か再考。

type list<x> = μx. 1+x*list<x>
             = 1 + x + x*x + x*x*x + ...

x型のリストとは、何も要素がない状態(1)か、xが一個の状態(x)か、 xが二個の状態(x*x)か、xが三個の状態(x*x*x)か…という無限個の型の union で表現できます。ですから、上の定義は納得できるのではないかと。

ところで、微分の方の話ですが、テイラー展開をご存じでしょうか? これによれば、1 + x + x*x + x*x*x + ... という無限和は、 簡単な分数で表現できます。

list<x> = 1 + x + x*x + x*x*x + ... = 1/(1-x)

さあでは、list<x> に x型の穴を空けてみましょう。微分!

list<x> [:x] = 1/(1-x) を x で微分
               = 1/((1-x)^2)
             = 1/(1-x) * 1/(1-x)
             = list<x> * list<x>

04:04 04/03/17

前々からソースレベルデバッガについて感じている点なんですけど、

ptr->method0( arg1.method1(), arg2->method2() );

例えば↑という行の直前で実行が止まっているときに、 ステップオーバー(行全体を実行して、次の行のところで止まる) という方式と ステップイン(行内の最初の関数呼び出しを実行して、呼んだ関数の先頭で止まる) という方式の2種類のステップ実行は大抵用意されています。 これに加えて、「行の最の関数呼び出しまでを実行して、 呼んだ関数の先頭で止まる」って方式が見当たらないのが不便だなぁ、と。 上の例だと、method1の先頭じゃなくて、 method0の先頭まで動作を進めてくれる方法が欲しい。

ptrがスマートポインタだったり、arg1.method1() がただの getter だったり、 arg2->method2() の返値から引数への暗黙の変換が実は入ってたり、 ということは非常によくあるので、その都度取るに足らない補助関数に 出たり入ったりを繰り返すのはなんだか面倒なのです。

# 私はVisualStudioのデバッガとgdbを非常に浅く使っているくらいなので、 既にこういう機能は普通に存在する可能性は大。 デバッグシンボルの表現形式などを全く知らないで適当に発言してるので、 もしかしたらかなり無茶な要求をしてる、という可能性も大。

<pre>

w.l.o.g.にプログラムのコードを書かない縛り、そろそろ解禁。

00:58 04/03/15

そういえば、昨日の書き忘れ… PPL の帰りに柏の本屋によったら イベントスペースで天野喜孝やらラッセンやらの絵が展示されていたので、 なんとなく眺めていました。で、そこに並んでいた 平凡&陳淑芬 という二人の描いた絵に遭遇。わりと有名な方っぽいんですけど、 私はこれまで全然知らなかったので衝撃的でした。 うわゎ、綺麗だ。綺麗すぎ。魅入られた。 自然を切り取る技法で自然以外の何かを描き出そうとするとこうなるのか、というか。 自分でも何が言いたいのかよくわからんけどすげー!

00:18 04/03/14

三日間、PPL2004 に参加してました。こういう研究者の集まり的なものって初めてだったのですが、 なんだかとても楽しかった&やる気が出た&自信がついたでした。 いや午前3時に SKK ⇒ I などなどの話が出来るのは素晴らしい。 発表では、長谷川真人氏の "Recursive Programs in the Abstract" (PDF) というのが個人的に一番面白かったです。あと印象として、 継続(Continuation)って流行なのかなぁ、とか。

同じ部屋だった方に "Binary Decision Diagram"( 論理式の表現方法で、二分決定木の共通部分木を潰してDAGにしたもの。 andやらorやらの論理演算もDAG同士の演算として無駄なく簡単に書ける ) というのを教えてもらったり 「Model Checking」 という本を見せてもらったり勉強にもなりました。頑張ろう。

orkut

メールチェックしたら、強敵と書いてともと読む人から orkut に招待されてたのでとりあえず登録。 定番の反応ですけど危うくSPAM扱いして見過ごすところでした。 …っていうか、これまでに他の方からのお誘いが あったとしても思いっきり見過ごしていましたがドンマイ。

で感想ですけど、プロフィールの項目多っ!これ無理。 2ページ目に入った時点で入力に飽きてしまいました。 Googleの技術でこのサイトから適当に単語拾って自動入力してくれないかしらん。

08:25 04/03/11

Niceという名前のナイスな言語の言語仕様を読んでます。 JavaにハイパワーなGenericsとnamed conformanceぽい機能と無名関数とローカル関数とマルチメソッドとタプルと名前付き引数とOptional引数とExact型引数とブロック引数と値による関数定義の分岐と契約とを入れたもの。(長い)

どの機能も、それをJavaに入れるとすればこうか、 と真っ先に考えるような予想通りの構文で実装されていて、 なんだか思わず微笑んでしまいました。かなりわかりやすい。 int->boolean f;で関数型変数の宣言とかキター!って感じ。 あと、公開サイトがちゃんとデザインされてて読み安いのが嬉しい。 帰ってきたらgbetaそっちのけでいじってみようかな。

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