k16's note: 2008

2008/12/30

ようやく年賀状を作る。

どうみても図形言語です。

にしても今年は一年中なんだか余裕がなかった。来年はなんとかする。

2008/09/26

Scheme どう書く？的 - ひげぽん OSとか作っちゃうかMona-
http://d.hatena.ne.jp/higepon/20080925/1222326246

こんなことをしていられる状況ではないんだけど、mapAccumLを使いたい衝動を抑えられなかった。

compactNumberList :: [Int] -> [[Int]]
compactNumberList = snd . partition ([]==) . tail . snd . mapAccumL collect [-1] . (++[-1])
    where collect xx@(x:xs) y | y - x == 1 = (y:xx, [])
                              | xs ==[]    = ([y], [x])
                              | otherwise  = ([y], [last xx, head xx])

2008/09/12

IO型は、使うだけなら簡単に思える。たとえば String -> IO () という型の putStr に文字列を渡せば、それが画面に印字される。

Main >putStr "abcdef\n"
abcdef

putStr の出力は IO () 型なので、結果として印字された「abcdef」は文字列ではない。じゃあ、IO () 型の出力はどこにいったんだろう？ Show クラスのインスタンスがないということ？でも、だとしたらGHCがエラーを出力するんじゃなかったっけ？

とにかく絶対に IO () な何かが関数の結果として返ってきているはずなので、IO () -> String な関数を定義してそれに putStr をつないでみた。

vacant :: IO () -> String
vacant o = "munashii"

Main >vacant $ putStr "subarashii\n"
"munashii"

どうして「subarashii」が印字されないん？

結局、これはやっぱり副作用じゃないってことなんだろうな。Scheme でも同じことをすると、

gosh> (define (vacant o) "munashii")
vacant
gosh> (vacant (print "subarashii"))
subarashii
"munashii"

これが本物の副作用ということなのか！

2008/09/11

Haskellでプログラムを書くときは、まず関数の型を妄想してHoogleしろ

Haskellでは、型を「利用して」プログラミングができるという。つまり、「あーなんかこんな型の関数ねえかな」というところからプログラムを書き始めるものらしい。だから haskell.org では型からAPIを検索することができる。その名も Hoogle。Gauche のリファレンスマニュアルさえあれば誰にでも Scheme のプログラムが書けてしまうように、Hoogle があれば誰にでも Haskell のプログラムが書ける。気がする。ところで、Yahooみたいな名前の APIサーチエンジンもあるそうなのですが、見つかりません。
（追記）Hayooでした。ありがとうございます > nobsun（ここまで追記）

たとえば、10進の整数を各桁からなるリストだと思って map したい。

*Main> intMap (*2) 12345
[2,4,6,8,10]
*Main> foldr (+) 0 $ intMap id 123456789
45

こういうintMapをどうやって作っていくか。（以下、とりあえず正の整数の場合だけを考える。）

Scheme脳の正攻法は、各桁の再帰だろう。1の位を head、それより大きな位を tail にして再帰的にリストを作り、reverse すればよさそうだ。10進数の 1の位の数は (mod 10) だし、10で割って floor を取れば 1の位より前にある数字を並べた数になるので、型を考えずにこんなナイーブな定義が書ける。

intMap p n | n < 10 = [p n]
           | otherwise = reverse (p last : reverse front)
           where
             last = mod n 10
             front = intMap p (floor (n/10))

ちなみにこれはコンパイルに通らない。floor とか (/) とかは、そのままでは Int型に対して使えないので。コンパイルするには最後の front を次のようにする必要がある。

front = intMap p $ fromEnum $ floor $ toEnum n/10

（追記）整数の割り算がありました。front = intMap p (div n 10) でOK。（ここまで追記）

本来なら順番が逆だけど、ここで初めて intMap の型について考える。intMap は、ふつうの map のように、1引数関数とリスト代わりの整数をとってリストを返すようにしたい。つまり、こういう型だ。

intMap :: (Int -> a) -> Int -> [a]

自分が求めている型が分かったので、これをキーワードにして Hoogle で検索してみる。結果はいっぱい出るけど、その先頭には iterate という関数がひっかかるはずだ。リンクをクリックすると、GHCのドキュメントの iterate の項目にジャンプする。その説明によれば、iterate はこんな関数らしい。

iterate :: (a -> a) -> a -> [a]

iterate f x returns an infinite list of repeated applications of f to x:

 iterate f x == [x, f x, f (f x), ...]

見るからに intMap の定義に使えそうだ。f として先ほどの定義の front に相当するものを与えてやれば、iterate f 1234 -> [1234, 123, 12, 1, 0, ...] といった具合にリストが得られるので、あとは各要素から mod 10 で 1の位を抜き出せばいい。
（追記）f の定義を fromEnum $ floor $ toEnum m/10 から div m 10 に修正（ここまで追記）

intMap :: (Int -> a) -> Int -> [a]
intMap p n = map (p . lastDigit) $ reverse $ takeWhile (> 0) $ iterate f n
              where
                f m = div m 10
                lastDigit m = mod m 10

再帰がなくなり、標準関数をごにょごにょするだけで求める関数を作ることができた。

まとめ
「Haskellでプログラムを書くときは、まず関数の型を妄想して Hoogle しろ」

おまけ
ナベアツ問題とか。

nabeatsu = [p i | i <- [1..]]
           where has3 n = or $ intMap (== 3) n
                 p i | has3 i || mod i 3 == 0 = "aho"
                     | otherwise = intMap intToDigit i

2008/08/03

Panasonic CF-R4JにDebianを入れるまとめ

正月に液晶を割ってしまった Panasonic CF-R4J のパーツを入手できたので、修理ついでに Debian GNU/Linux を入れることにした。いままでは購入時にプリインストールされていた Windows XP 上で VMware を使って Ubuntu を利用していたが、やっぱりたまにいらりってくる。
最近は Debian も簡単にインストールできるけど、CF-R4J には光学ドライブがないし、内蔵の無線LANのように使えないと困る機能もある。あと、いままで使っていた Windows XP の環境をそのまま使い続けられるようにしたい。そこで備忘録として作業のまとめ。

目標

プリインストールされている Windows XP はそのままにして、Debian を追加でインストールしたい。

戦略

USBメモリから KNOPPIX を起動し、ntfsresize と cfdisk を使って、Windows XP がプリインストールされた HDD の後半に Debian 用の新しいパーティションを作る。
別のUSBメモリから Debian のインストーラを起動し、新しいパーティションにインストールする。
内蔵されている無線LAN を有効にする。

用意するもの

1GバイトのUSBメモリ
128MバイトのUSBメモリ
syslinux（Windows用）
KNOPPIXのisoイメージ
boot.img.gz
Debianのネットインストーラ（名刺サイズCD用。ここの debian-40r4etchnhalf-i386-netinst.iso ）
Intel PRO/Wireless 2200BG ドライバのファームウェア（v3.0）

USBメモリから起動するKNOPPIXのイメージを作る

この作業は、プリインストールされた Windows XP 上で行う。以下のサイトの手順に従っただけ。

[USBメモリでKNOPPIXを起動する]
http://ryusai.hp.infoseek.co.jp/KNOPPIX_on_USB-01.htm

まとめると以下の通り。

KNOPPIX の iso イメージを入手して DAEMON tools でマウント
1Gバイトの USBメモリを FAT32 でフォーマット
DAEMON tools でマウントした KNOPPIX をエクスプローラで開き、KNOPPIX フォルダ全体と /boot/isolinux 以下のファイルを、フォーマットした USB メモリの直下にコピー
/isolinux.cfg を /syslinux.cfg にリネーム
syslinux -a :f

USBメモリから起動する Debian のインストーラを作る

この作業は、上で作った KNOPPIX で行う。これも以下のページの手順に従っただけ。

[USB メモリでの起動用ファイルの準備]
http://www.jp.debian.org/releases/stable/i386/ch04s04

まとめると以下の通り。デバイス名とかは適宜。

（ここだけ Windows XP でやっておく）128Mバイトの USBメモリを FAT32 でフォーマット
boot.img.gz を入手し、zcat boot.img.gz > /dev/sdb
sudo mount /dev/sdb /mnt/sdb
cp debian-40r4etchnhalf-i386-netinst.iso /mnt/sdb/

HDD のパーティションを切り直す

この作業は、KNOPPIX 上で行う。

（ここだけ Windows XP でやっておく）Cドライブのデフラグ
ntfsresize -i /dev/hda1 で、リサイズできる HDD 領域の大きさを調べる
ntfsresize -s 30000M /dev/hda1 （30000M のところは、上で調べた大きさを参考に適宜）

この時点で Windows XP からは、C ドライブの大きさが指定した大きさに縮小されて見える（この場合だと30Gバイトしか見えなくなる）。ただしパーティションが変わったわけではないので、管理ツールからローカルディスクを見れば、やはり元の大きさのHDDがCというドライブ名の1つのパーティションに占有されているように見える。ちょっとへんな状態。
実際にパーティションを切るには fdisk をするしかない。そこで cfdisk /dev/hda1 を実行する。

ntfsresize 後の cfdisk でやること

ここからが危険なところ。

もともと Windows XP がプリインストールされていたパーティションを削除する。最初に cfdisk を実行すると、HDD の末尾に 3G くらいの空き領域があるように見える。これは CF-R4 のリカバリ領域。Windows XP が入っているパーティションを削除することで全体が1つの空き領域になるため、空き領域として見えていたリカバリ領域が cfdisk からは識別できなくなってしまう。この領域は BIOS レベルで fdisk などでは削除できないようになっているらしいが、それを確かめる勇気はないので、本当のことは知らない。個人的には用心しておいたほうがいいと思う。実際、あとでパーティションの設定を誤って Windows XP が起動しなくなったとき、KNOPPIX からは /dev/hda4 としておもいっきり見える状態になっていた。たぶんこの領域を隠蔽するのに、プリンストールされた Windows XP の機能を使っているんだろう。
全体が1つの空き領域になっているところに、まずはプリインストールされている Windows 用のパーティションを作る。先に ntfsresize で縮小したサイズ以上の大きさのパーティションにすること。ぴったり同じバイト数で指定すると、ntfsresize で縮小したサイズよりもfdiskで作ったパーティションのほうが小さくなってしまうようだ。そうすると Windows XP が起動しなくなる。もし後続の空き領域に Debian 用のパーティションを作ってフォーマットしようものなら、あふれた部分が失われてしまって Windows XP の環境が復旧できなくなってしまうはず。大きい分には問題ないので、1Gバイトくらい多めの大きさのパーティションにしたほうがいいと思う。
この時点でパーティションテーブルを書き込み、Debian のインストールに使う領域の設定はインストーラにまかせてしまってもいいが、リカバリ領域を失うのは怖いので、この時点で最後に 5G くらい残るようにして、スワップ用とルート用のパーティションを切ってしまう。
書き込む。もう戻れない。

Debian のインストール

いつもどおりなので省略。ネットインストールに無線LAN が使えないので、有線をつないで実行する必要がある。

無線LANを有効にする

ラップトップ向けのインストールをすれば wlan-tools はインストールされる。CF-R4J の内蔵無線LAN は Intel PRO/Wireless 2200BG で、そのドライバは ipw2200-source というパッケージでインストールすることができる。lenny ならパッケージのインストールは不要。ただし lenny であってもファームウェアは入らないので、別途 ipw2200-fw-3.0.tgz をダウンロードして /lib/firmware に手動で置いておく必要がある。
あとは /etc/network/interfaces をこんな感じに設定しておけば、有線LAN との使い分けも適当にできると思う。

# The loopback network interface
auto lo
iface lo inet loopback

# The primary network interface
allow-hotplug eth0
iface eth0 inet dhcp

# Wireless LAN
auto eth1
iface eth1 inet dhcp
wireless-essid ******
wireless-key **************************

2008/07/27

金曜日、帰り際にうっかりメールを見ると、確率クイズが出題されていた。

x_i ≧ 0 かつ Σ x_i = 1 となるような乱数 
x₁, ..., x₁₀ がほしい。

そこで、区間 [0,1] 上の独立な一様乱数を 9 個作ってソートし、
得られた r₁ ≦ … ≦ r₉ を使って、
x_i = r_i - r_i-1 としてみた。
（ただし r₀ = 0, r₁₀ = 1）

これは平等か？
たとえば x₁ の分布と x₅ の分布は等しいか？
（数式に頼らずうまく説明せよ）

ようするに、数直線の0～1の間に均等な確率で弾を9発撃ち込むという行為を繰り返したとき、毎回の隣り合う各弾の間隔は同じような幅になると期待していいか、ということでしょう？

 0            r_i-1   r_i            1
-+--- …… ---+------+--- …… ---+-
              `--x_i--'

たとえば撃ち込む弾の数が毎回1発だったら、

 0       r₁        1
-+-------+---------+-
  `--x₁--'`---x₂---'

いかにも x₁ と x₂ が同じ分布になりそうだ。撃ち込むのが9発でも同じことだよね。というわけで、この方法で平等な乱数を10個作ることができる。

こう返信しようとしたけど、思いとどまって（というか時間がなかったので）その日は帰宅した。

でも今日、紙と鉛筆を使ってもうちょと考えてみることにした。

追記：以下にはしょうもない間違いがあるので、あとで訂正します。

任意のλ∈[0,1] について、x_i がλになる確率 P(x_i = λ) を考えよう。 r_i より左側に i-1 個の乱数があって、r_i＋λ より右側に 9-i 個の乱数があるということなので、以下のように書ける。

P(x_i = λ) = r_i^i-1 × (1 - r_i - λ)^9-i

いくつか具体的に計算してみると、x₁ がλになる確率は以下のとおり。

P(x₁ = λ) = r₁⁰ × (1 - r₁ - λ)⁸
           = (1 - r₁ - λ)⁸

同様に x₂ がλになる確率は、

P(x₂ = λ) = r₂¹ × (1 - r₂ - λ)⁷
           = r₂ (1 - r₂ - λ)⁷

おや、なんだか P(x₁ = λ) = P(x₂ = λ) とも言えなそうだ。そこでおおざっぱに評価してみる。

   P(x₂ = λ) / P(x₁ = λ)
 = r₂ (1 - r₂ - λ)⁷ / (1 - r₁ - λ)⁸
 = (r₂ / (1 - r₁ - λ)) × ((1 - r₂ - λ)⁷ / (1 - r₁ - λ)⁷)
≦ (r₂ / (1 - r₁ - λ))     ← r₁ ≦ r₂ なので
 = r₂ / (1 - r₂)            ← λ = r₂ - r₁

最後の式は、r₂ = 1/2 なら 1 になる。しかも、もし r₁ = r₂ だったら、途中の不等号が統合になるので、P(x₁ = λ) = P(x₂ = λ) になる。撃ち込む弾の数が毎回1発のケースは、この場合に相当していたのか。

というわけで、実は平等じゃない、というのがクイズの答えっぽい。数式を使わない説明としては、1に近づくほど確保しうる x_i の大きさが小さくなってしまう確率が高まるから、というのでどうでしょう。

2008/06/14

今日は7ヶ月の妊婦さんが遊びに来て、彼女たちが帰ったら2ヶ月の妊婦さんの夫から電話がきた。うちは去年のあいだ妊娠生活だったわけだけど、けっこう楽しく乗り切れたと思う。

妊娠生活に限らず、日常と違う生活を楽しむにはまともな情報が必要だ。いろいろあさったけど、雑誌の情報（この場合はベネッセの何か）は2ちゃんねるのようなもので、その他大勢の声を確認するには悪くない。しかしそれはまた、意義のある情報を得るには取捨選択が必要なことも意味している。ところが取捨選択するには、そのドメインに対する基本的で正しい認識が欠かせない。そういうときに役立つのが本物の実用書というものだ。文句なしにお勧めするのはこれ。

Arlene Eisenberg, Heidi Eisenberg Murkoff, Sandee E. Hathaway "What to Expect When You're Expecting"(Workman Pub Co, 2002)
http://www.amazon.co.jp/dp/0761121323/

翻訳も出ている。自分は翻訳版を読んだことはないけど、上記をすすめて翻訳を買った妊婦さん（鬼編集者で出版物の出来には人一倍うるさい）によればいい本とのこと。

森田由美、竹内正人訳『すべてがわかる妊娠と出産の本』（アスペクト、2004年）
http://www.amazon.co.jp/dp/4757210795

この本のすごいところは、妊娠にかかわるいろんなトピックを、できるだけ全部できるだけ詳細に説明しようとしていることだ。それも平易な言葉と妊婦の視線で。実際、オリジナルの作者はそのへんの元妊婦さんで、自分が妊娠中に不安だったのに本に書いてなかったことを全部まとめて本にしてやると思い立ち、産婦人科医や研究者なんかに徹底的にリサーチして出版したらしい。

自分はこの本がなかったら、予定日2週間前の午前2時に実家に戻っていた奥様から「破水した」という電話をもらったとき、これから何が起きて、自分が何をすればいいのか、さっぱりわからなかったはずだ。陣痛室から分娩台の脇で臍の緒を切るまで、すべては本に書いてあるとおりのあらすじで進み、要所で迫られる選択にも十分な理解をした上でのぞむことができた。アメリカ人の実用書の作り込みっぷりに改めて脅威を感じた。

もちろん日本にもすごい本はある。

定本育児の百科上 5ヵ月まで
http://www.amazon.co.jp/dp/4003811119/

この本は「育児」を扱った古典だが、冒頭でかなりのページを割いて出産前の心得や注意事項に触れられている。書かれたのは古いが、インターネットやベネッセから出産育児に関する情報を取捨選択するためのリテラシーを培うにはとてもお勧めだし、内容も今でも役に立つ話ばかりだ（文庫化にあたって、そういうふうに編集されている）。何よりも普通におもしろい。当たり前だが出産後も役に立つので、買っておいて損はないと思う。

ベネッセやインターネットの情報を利用するのは、少なくともこの2冊の後でいいはずだ。もちろん、すべてを鵜呑みにしたりしなければ、いつどんなリソースに触れてもいいんだけど。

2008/06/04

朝一でときどきの雑記帖を見ていてクイズの存在に気が付いた。

与えられた木から、子→親への対応を作る

脊髄反射で回答を思いついたので仕事を始める前に書いてみた。都合15分弱。

(use srfi-1)

;; [name [tree ...]] -> [(tree-head . name)]
(define (child-parent ls)
  (if (null? (cdr ls))
      '()
      (append-map
       (lambda (l)
         (cons (cons (car l) (car ls))
               (child-parent l)))
       (cdr ls))))

にしても、「10分で中級、30分で初級」というshiroさんによるレベル設定が絶妙すぎると思う。

ところでむしろ気になるのは、他人が回答に至るプロセスだ。自分はこんな感じの思考過程で上記の定義に至った。

リストのcarと、リストのcdrたちのcarとを、逆順にconsして集めるのね
↓
とりあえずcdrたちに対してmap-appendか
↓
そしてconsで再帰すればいいから、必然的に終了判定はnull?
↓
"(if (null? (cdr ls))"あたりから書き始める

この場合は再帰も単純なので一発で書いちゃうけど、もうちょっと複雑な場合はテスト用のトリビアルな入力データをREPLで評価しながら関数に仕上げていく。あるいは、一発で関数を書いちゃってからテスト用のトリビアルな入力データを使ってREPLで評価し、意図していない結果であれば修正して（再帰の終了条件を修正する場合が多い）、これを繰り返して関数に仕上げていく。だいたいいつもこんな感じ。必要なら最後にCtrl-c tしてテストを作りますよ。gca.el最高！

ところがこのごろ、テストファーストという呪縛に悩んでいる。最初にテストを書け。問題にある「結果の例」とequal?になるテストケースを書けばいいのかな？でも結果のリストの順番はどうでもいいから、equal?になるテストケースをパスするコードを書くのは一苦労だぞ。そういえばGaucheにはリストを集合として同じだと見なす関数があったよな。しかし元の木に循環があったら集合としても同じにならないし……ってなことを考えているうちに、平気で30分は経過してしまう。

この問題はただのクイズだから気にしなくていい、というわけにもいかない。shiroさん自身も「仕事で扱った小ネタ」と書いているように、Schemeでプログラムを書いているときには、こういう小さな関数を大量にスクラッチしている。そのほとんどを書くときは、まず上記のような思考をまとめて、REPLで即興データの評価を繰り返しながら、徐々に関数としてまとめていく。その過程で関数のキワがはっきりしてくるから、そのきわどい条件を含むように即興データをどんどん変更していく。（場合によっては最後にCtrl-c t。）

テストファーストじゃなくてもメンテナンスのためにテストを残してけ、という意見もあるが、これもいまいち納得しきれていない（もちろん理解はできる）。gca.elを使って開発していれば、コードを書いちゃった後でテストを「残す」のは簡単だ。それでも、例えばプログラムの一部としてこの関数を使っていて、後で効率のいいコードにリファクタリングする場合、作り直したコードによって生成されるリストは現在の結果と同順になるとは限らない（その必要もない）。そうなったらユニットテストとして残しておいたテストケースの意味って、ゼロとは言わないけどあまりなくない？リファクタリングのときもテストデータをREPLで評価しながら作業するわけだけど、そのときにユニットテストとして残っているコードがテスト用として適切とは限らないんだよな。

自分は最近、入力と結果の型（っぽいもの）を関数にコメントしておくようにしている。リファクタリングするときは、この型（っぽいもの）の入力にそったデータをでっちあげて、それをREPLで評価するためのテストデータとして使う。そのでっちあげたテストデータは、やはり新しい関数のキワを突くようにどんどん変更していくだろう。人のコードを見るときも、まずはその情報を探す（コメントとしてであれ、コードとしてであれ）。

関数的なプログラミングにおけるテストの意味合いが、純粋によくわからない。なんども言うけど、テストそのものはCtrl-c tすれば作れるので、テストを残しておくことは面倒でもなんでもない。心にひっかかるのは、それって正しいの？という純粋な疑問だ。神様を毎朝拝むのは、一瞬なら面倒ではないかもしれないけど、自分にはそれが正しいことであると納得できないからしない。考えすぎかもしれないけど、何かを習慣として取り入れるなら、それなりに納得（理解ではなく）した上で取り入れたいということです。

2008/05/13

今年の連休の成果はスターウォーズを全編通して見たことだ（アニメ『クローン大戦』を含む）。それでちょっと思ったんだけど、Lisperにとって自分でLispを作ることは、ジェダイにとって自分でライトセイバーを作ることに似ている。おもちゃのLispなんて、少なくともSICPを読めば誰にでも書ける。とくにLispを使ってLispを書くなら、ベースにするLispのreadやシンボルのインターンが使える。今回、はじめてCでひととおりLispっぽいものを書いてみたわけだけど、やっぱり大変だったのはreadとシンボルのインターンだった。だからこんなのがきちんと実行できたのがうれしかった。

es0> (eq? (quote a) (quote a))
#tt
es1> (eq? (cons (quote a)) (cons (quote a)))
#ff

で、ジェダイならライトセイバーを自分で作るわけだ。奪ったライトセーバーを振り回すだけのグリーバス将軍とは、その点が決定的に違う。グリーバス将軍は強いけど、フォースの加護はない。フォースの加護もなしにライトセーバのような前時代の武器を使うのは、回顧趣味にほかならない。ようするにカッコつけてるわけだ。ラムダの加護もなしにLispを使うようなものだ。ポインタの加護もなしにCを使うようなものだ。ところでいまさらCのポインタの話だけど、みんな藤原博文著『Cプログラミング専門課程』を読めばいいと思う。僕がかろうじてCを全然使えないというわけでもないのはこの本があったからだ。けっこう版を重ねているのに柱（ページ番号とかある部分）に誤記が残ってるとか、編集については微妙なとこもあるけど、本当にいい本なので、曙橋界隈で藤原さんを見かけるとこっそりうれしい。

2008/05/06

オレリスプでYコンビネータ

やっぱりリストの再帰ができないとリスプとはいえない。Yコンビネータが定義できるかやってみよう。Yコンビネータを使うと、関数に名前を付けずに再帰ができる。まあ、なんというか、「ラムダだけでここまでできる」みたいなのがうれしい。

これがYコンビネータ（"The Little Schemer"より）。

es20> (define Y 
        (lambda (le)
          ((lambda (f) (f f))
           (lambda (f) (le (lambda (x) ((f f) x)))))))

（この「Y」という名前は再帰に使うための名前じゃない。）

たとえばリストの長さを計算する関数なら、こんなふうに実現できる。ちっとも再帰関数には見えないかもだけど、Yコンビネータのなかで「再帰する」ことが抽象化されている感じ。

es24> ((Y (lambda (len)
            (lambda (l)
             (if (null? l)
                 0
                 (+ 1 (len (cdr l)))))))
       (quote (beans beans we need jelly beans)))
6.000000

なんかちゃんと動いてる！

にしても、もともと「アトムか、ドットペアか」というだけのルールでS式をパーズしようという企画だったので、いまから「'」記法を導入するのはやっかいだなあ。

あと、この例ではnull?を使っているけど、null?は組み込んではいない。null?とか自分のなかで定義するのがリスプなんだと思う。

es0> (define null? 
       (lambda (ls)
         (if (eq? (quote ()) ls)
             #t #f)))

2008/05/05

Cによるはじめてのオレリスプ

できたよできた！とりあえず階乗の関数を定義して計算できるようになった。

k16@miffy:~/myproj/es$ ./es

es0> (define fact
        (lambda (n)
          (if (eq? n 1)
              1
              (* n (fact (- n 1))))))
fact
es1> fact    
#<closure ( n )>
es2> (fact 10)
3628800.000000
es3>

ソースはこれ。メモリリークしまくっている状態だけど。あとで時間がとれたら感想とか書く。

2008/03/30

S式パーサからリスプへ

先週はS式パーザ（つまりread）をつくったので、今週はcarとcdrとconsをつくった。そのときにevalとapplyをつくったので、ついでに四則演算にも対応した。途中なので結果だけ。

es0> (* 1 2)
2.000000
es1> (+ 42 23)
65.000000
es2> (cons answer (cons is (cons 42 ())))
(answer . (is . (42.000000 . null)))
es3> (cdr (cons mouse (cons dolphin human)))
(dolphin . human)
es4>

はやくSchemeになりたいよう。のこり必要なもの。

環境（クロージャー）
インターン
プリティプリント
ガーベジコレクション
末尾最適化
call/cc

2まではSICPの知識だけで十分か。3はまあ、できているといえばできている。4から6はきびしいかな。やり方は理解できると思うけど、Cで書けるかどうかは別問題だ。

2008/03/23

「S式はアトムまたはドットペア」を真に受けてyaccでパースする話

「おまいらはS式が好きすぐる。」という感想にぐっときたので、S式について考え直してみることにした。具体的にはパーザを書くよ。

S式そのものはとてもシンプル。アトムか、ドットペアか。つまり、

S式 : アトム
    | ( S式 . S式 )
    ;

おなじみの (apple orange pizza) みたいなリストは、実際には null で終わっているドットペアの簡略表記にすぎない。この例であれば、その本当のすがたは (apple . (orange . (pizza . null))) という入れ子になったドットペア。そういえば null って本当は何のことなんだろう？いつも()って書いてるから、空っぽなリストぐらいにしかみなしてなかったけど、よく考えるとよくわからん。

まあとにかく、この「アトムか、ドットペアか」という単純な構文ルールだけをパーザジェネレータに与えてS式パーザを作りたい。

YACCを使ってやってみよう。試行錯誤のすえ、構文解析の部分はこんな感じにした。

%{
  #define YYSTYPE Sexp*
  %}
%token ATOM
%token DOT
%token LPAREN
%token RPAREN
%%
list:             { prompt(lineno); }
| list '\n'
| list sexp '\n'  { prints($2); prompt(lineno); }
;

sexp: ATOM
| LPAREN sexp DOT sexp RPAREN  { $$ = mk_oblist($2, $4); }
;

ここで Sexp はS式をあらわす構造体で、直感的にAtomとPairの共用体として定義した。

typedef struct Sexp {
  short type;
  union {
    struct Atom *atom;
    struct Pair *pair;
  } u;
} Sexp;

Atomは浮動小数点数か文字列とする。Pairはもちろんcarとcdrで構成される。

typedef struct Atom{
  short type;
  union {
    double num; /* type = 0 */
    char  *sym; /* type = 1 */
  } u;
} Atom;

typedef struct Pair {
  struct Sexp *car;
  struct Sexp *cdr;
} Pair;

そしてこの Pair を作る関数が mk_oblist。

基本的には以上でおしまい。なんだけど、これだけではリスト表記をパーズできないのでつまらない。リスト表記のための構文規則を付け足せばいい話なんだけど、「アトムか、ドットペア」というS式のシンプルさに無駄にこだわることにして、字句解析のほうで対応したった！もしかしたらちょっとしたプッシュダウンオートマトンの勉強をしたことになったのかもしれないけど、めんどくさいし面白くないので説明は省略。とりあえず自宅のDebian Lenny上ではこんなふうに動くものができた。

$ ./es

es0> (((((42)))))
(((((42.000000 . null) . null) . null) . null) . null)
es1> (the answer is 42)
(the . (answer . (is . (42.000000 . null))))
es2> (() ())
(null . (null . null))

浮動小数点数だと、42という答えがなんだかうそっぽい。

Expand S-expression にちなんで es という名前にしています。ソースはこちら。

es.tar.gz

2008/03/15

Sence of Mathmatics

昨日の夜、なんとなくラジオを聞いていたら、文系にも数学のセンスは備わっていると誰が主張していた。（文系とか数学のセンスといった用語についての質問はうけつけません。そもそも途中でうちのこが泣き出したので、僕の聞き違いだったかもしれない。どうでもいいけど、うちのことツチノコは似ている。見ためが。）

いわく、「マイナスかけるマイナスがプラスになるのは「反対の反対は賛成」と同じことで、そういうふうに言えば文系の人にだってすっきりするんだからね」みたいな話だったんだけど、それは数学のセンスじゃないと思う。

どうしてもこの話から数学のセンスという何かについて語りたいなら、「マイナスかけるマイナス」が「反対の反対」だと小学校の教師に言われたときに、「反対の反対」を「マイナスたすマイナス」と考えなかった理由を問い返すのが数学のセンスだと思う。

で、そんなセンスをもっていても小学校の教師から屁理屈をいうなと罵られるだけなので、数学のセンスに夢や希望を抱くのはやめたほうがいいと思う。

2008/03/11

Gaucheで本を作るのFAQ

Gaucheで本を作る
http://www.slideshare.net/guest7a66b8/gauche/

gauche.night2008の発表後に個別に受けた質問に答えます。

Q. 原稿をXMLで書かせられるってこと？
A. XMLでなくてもいいんだけど、XMLでお願いすることが多いです。

歯切れの悪い答えですみません。ちょっと背景と理由を説明します。

まずは「XMLでなくてもいい」についてですが、実例がいくつかあるので、それらを紹介。

1つめの実例は、『RailsによるアジャイルWebアプリケーション開発』の旧版。このときは、原書のデータはXMLだったんだけど、下訳の時点でプレーンなテキストデータになってしまったため、XMLの原稿ではありませんでした。ただし、あとでDTPソフトを使ってページレイアウトをするオペレータさん向け、つまり人間向けのメタ情報は付いていました。人間向けのメタ情報っていうのは、たとえば箇条書きの行頭に「●」が付いているとか、サンプルコードの始まりと終わりにマークが付いているとか、補足説明の文はタブでインデントされてるとか、そういうやつです。で、どうしたかというと、そんな人間向けメタ情報をなんとなくパーズしてLaTeXに変換するスクリプトをGaucheで書きました。といっても、機械的な判断が可能なように、人間向けメタ情報のエディタでの編集は必要でした。原稿そのものは最後までプレーンなテキストデータを使いましたが（i.e. XMLに加工したりはしていない）、著者がいじれる原稿からmakeいっぱつで印刷用データを生成していたのは一緒です。このときの顛末は過去にまとめたことがあるので、そちらも見てみてください。

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

2つめの実例は『マスタリングTCP/IP ルーティング編』です。このときは、とくに最終工程を意識したメタ情報がないテキストの原稿に、僕のほうでXMLタグを付けて、編集用の原稿にしました。著者の方々の校正では、初校や再校といったタイミングでPDFを印刷した校正紙に赤書きしてもらう、従来の方法をとりました（編集部内ではほぼデイリーでPDFを生成していたけど）。もっとも、この本の場合は図版がとても多く、その校正は紙に赤書きというスタイルがいちばん現実的だったというのもあります。編集者がいじれる原稿からmakeいっぱつで印刷用データを生成していたのは一緒です。

3つめの実例は『プログラミングのための線形代数』です。この本は、著者の2人の原稿がまっとうなLaTeXだったので、そのままLaTeXで組んでしまいました。LaTeXの編集では三美印刷さんにお手伝いしてもらっています。なお一般には、著者独自マクロが入り乱れたLaTeXの原稿はうれしくありません。そのまま印刷所には入稿できないからです。LaTeX原稿は最終工程ではポータビリティが低いのです。

「XMLでお願いすることが多い」理由については、次の質問ともかぶるので、ここではパス。

Q. Wikiとか使って原稿書きたいんだけど……
A. おすすめしません。

いや、Wikiを否定しているのではなく、Wikiは技術書の原稿執筆には向かないと思う、という話です。初期的なアイデア出しや、アイデアの相互レビュー、一時的な原稿のプールなんかに使うぶんには、Wikiは技術書の執筆においてもとても優れたメディアです。

でもWikiに依存して書いていると、最終的な本の構造が意識できない。

技術書って、拾い読みしてもいいけど、やっぱり多くは頭から読むものなわけです。そのとき、構造があいまいな本は、とても読みにくい。ここで「構造」というのは、「目次」に近いけれど、もうちょっと体系的な本の姿のことです。新しい概念がいつ説明されるか、どのブロック（章や項）の下に書かれているか、前にどこで言及されていたか、その前後の文脈。こういった本を構成する要素の縦横のつながり方は、その本のわかりやすさにもろに影響します。構造があいまいで見通しが悪い技術書は、初心者の目線で読んでいるとつらい。Wikiで書く原稿はジグソーパズルすぎて、あらかじめ全体像を知っている人（本を書く人）には気持ちがいいけど、その一片ずつを順番に渡されて読むことになる人（本を読む人）にはちんぷんかんぷんだったりするわけです。Webであれば縦横にはったリンクが読んでいる人にとっても十分な手がかりになるのですが、頭から読む本の場合は読んでいる途中で迷子になった感を抱かせないだけのしっかりした構造が必要です。

で、そういう技術書の原稿を書くのにWikiでやれる人っていうのは、限られるわけです（ゼロじゃないですもちろん）。その点では、構造化を強要されるXMLのほうに、書籍の原稿執筆のための形式としての分があると思います。繰り返しになりますが、アイデア出しやアイデアのまとめにはWikiが優れていると思います。でもそれを本にしようとおもったら、頭から読まれることを強く意識して、体系的に再構築する必要があります。

そして、それは技術書の編集者が手伝える仕事でもありますね（むしろ得意なはず）。

2008/03/09

gauche.night2008で発表しました

gauche.night2008のgauche.gongで発表した。プレゼンはこちら。

Gaucheで本を作る
http://www.slideshare.net/guest7a66b8/gauche/

このプレゼンそのものが、下書きのテキストに気ままにXMLっぽいタグを付けて、それからXML→LaTeXへの変換ルールを定義して、そのルールを使ってxml2tex.scmで変換して作ったもの。（実際にルールを使って変換してるのは、latex.scmとcnvr.scm。）

仕様の定かでないタグ付けテキストから、いかにちょっとのコードでLaTeXへの変換ルールを作れるかってところを最後にデモで見てほしかったんだったんだけど、時間が足りなかったのでここで補足。

たとえば、1ページ目のPDFはこんな感じで、

原稿はこんなだったんだけど、

<page>
 <p0>Gaucheで本を作る</p0>
 <p3 vskip="4zh" hskip="12zw">株式会社オーム社開発部</p3>
 <p3 hskip="12zw">鹿野 桂一郎</p3>
 <p3 hskip="12zw">kshikano@ohmsha.co.jp</p3>
</page>

ちょっとタイトルにワクでも付けたいなと思ったら、こんなふうに適当なタグでくるんでみて、

<page>
 <p0><box>Gaucheで本を作る</box></p0>
 <p3 vskip="4zh" hskip="12zw">株式会社オーム社開発部</p3>
 <p3 hskip="12zw">鹿野 桂一郎</p3>
 <p3 hskip="12zw">kshikano@ohmsha.co.jp</p3>
</page>

rules.scmにこんな2行を足すだけで（LaTeXの\fboxはワク付の箱でテキストを囲むコマンド）、

(define-tag box
  (make-latex-cmd 'fbox))

こんなふうになる。

実際の書籍の原稿だとこんなに単純ではないし、社内で使っているコードはここで公開しているのとは違うけれど、それでもやっていることはほぼ同じです。

謝辞

勢いで申し込んでしまって後悔もしたけれど、Gaucheを実際の商品（書店に並んでいる本）の製作で全面的に使っていることを話せる機会がもらえてよかったです。えんどうさんはじめ、gauche.nightの企画と実現に尽力されているみなさん、本当にお疲れさまでした。デモへの参加を後押ししてくれたhisashimさん、角谷さんと、shiroさんにも感謝です。ありがとうございました。っていうか、shiroさんには、それ以前にGaucheを開発されたことに感謝しないといけないわけですが。shiroさんだけでなく、日々Gaucheの開発とメンテナンスを続けているたくさんの方々にもあらためて感謝です。あと、こんなやり方の本作りに付き合っていただいている著者、訳者、トップスタジオのみなさん、会社のひと、とくにctakaoさんの家の方角には足を向けて寝られないと思ってるんですが、あにいく毎晩その向きで寝るしかない感じです。すみません。

2008/03/06

SICPは、口語では「しっくぴー」と読まれているらしい。
ただし、「あべるそんあんどさすまん」とか「すとらくちゃーあんどいんたーぷりてーしょんおぶこんぴゅーたーぷろぐらむす」といったフォーマルな呼び方を好む人が多いようだ。

SICP - comp.lang.scheme
I wonder what is the correct spelling for SICP abbreviation.

あまり返信が伸びてないなので、英語圏の人たちにとってはどうでもいい話なのかも。いずれにせよ「えすあいしーぴー」という言い方は、あまりしないみたい。

2008/01/19

あまりに憤ったので脊髄反射的に書くけど、そもそもこんなふうにゲラに赤書きしてもらうという本の作り方は悲しすぎます。そして、2月発行予定の書籍に1/11の時点でこれだけの赤字が入っていて、DTPソフトを使って修正する人の作業が間に合うのかとても心配です。おそらくはかなりテクニカルでセンシティブな内容の赤字が入っていると思うので、必ずしも本書の内容を理解しているわけではない人が手作業で各ページごとに絵として修正するには、著者や編集者による修正漏れ確認の手間も含めてとても時間がかかるものだからです。一般に技術書の制作なんてそんなもんだろと言われたら、内情を知る立場ではぐうのねも出ないわけですが、少なくとも僕のチームには「それじゃやばい」という空気がいっぱいだし、そうしない努力もしているつもり。こんな写真が公開されるのは、来月にきちんとしたものが発行されるからこそだという見方もできるのかもしれませんが、この本については読者としてとても楽しみなので、あまり不安にさせるような写真は出さないでほしい。

登録: 投稿 (Atom)

k16's note