SICP / Drkcore

みえないラムダが見えてきたヨ（あと括弧）。

Tue, 12 Jan 2010 11:06:55 +0919

SICPのおともにpythonインタプリタとかperlshとかmochikitのインタプリタなんかを併用すんだけど。

mapで遊んでみるわけだ、

perlだと

main[118]$ @numbers = (1,2,3,4,5)
main[120]$ map $_+5 , @numbers
6
...
10

なわけで、pythonだと

>>> numbers = [1,2,3,4,5]
>>> map(lambda (x): x +5 , numbers)
[6, 7, 8, 9, 10]

さて、SICPでググルとすぐに目に飛び込んでくる『計算機プログラムの構造と解釈』についてに引用されている、あのフレーズを思い浮かべる。

弟子が尋ねた。「先生、私は先生がカッコをまるで魔術師のように扱っているのを常々敬服しています。どうすれば先生のようになれるのでしょうか?」師「えっ? カッコ? あ、そうか。そんなものもあったな。いやあ、すっかり忘れておったわ」

perlだと忘れてるどころか、そもそも括弧もないしラムダもないわけだ。でさらに、YAPC2006でのバベルの話が頭をよぎった。

つまり最近lispが楽しいのはperlのせいに違いないと。

計算機プログラムの構造と解釈
ジェラルド・ジェイサスマン,ジュリーサスマン,ハロルドエイブルソン
ピアソンエデュケーション / ￥ 4,830 ()
在庫あり。

しかし、SICP in other languagesにperlがないですな。

pythonでY-combinator(Z-combinator?)

Tue, 12 Jan 2010 11:06:16 +0919

SICPも2章に入り、お約束らしいchurch数のあたりでプチ詰まり。

とか参考にしながら、後者のほうはperlのコードがあるから理解しやすいなぁとかいいながら読み進めるが、途中からさっぱりわからん。というより、Y-combinatorを理解しないと先に進めなさそうなので、Y CombinatorとTuringとChurchの狭間でを行ったりきたりしながらくらいつく。

一通り理解した気がしたところで、perlのZ-combinatorをpythonで書いてみた。

まず階乗のpython2.5から導入されたという、3項演算子を使ってみた。

>>> def f(n):
...     return 1 if n < 2 else n * f(n-1)

こんな感じで書けるがなんか、、、perlの三項演算子のほうが好き。

で、早速Z-combinator

Z = lambda f: (lambda x : lambda y : f(x(x)))(lambda x : lambda y : f(x(x)))
fact = lambda f : lambda n :  1 if n < 2 else n * f(FORCE)(n-1)
FORCE = lambda a : a

実行

>>> Z(fact)(FORCE)(7)
5040

pythonはラムダ式が書けるのでperlよりはすっきりと書ける感じ。

一応pythonでもY-combinatorの形で実行したけどこれは無限ループした。

Z = lambda f: (lambda x : f(x(x)))(lambda x : f(x(x)))

perlやpythonのばあい、クロージャにして無理やり遅延させるので

our $FORCE = sub { my $a = shift; $a };

評価が先送りになんのはわかるんだけど、schemeで

(f 5)

を

((lambda (x) (f x)) 5)

にすると遅延するのがよくわからんかった。書き方変えてるだけにしか見えないんだけど。これはクロージャと同じものなのだろうかそれとも評価の順番が違うからなのか?

pythonのジェネレータがちょっと分かった

Tue, 12 Jan 2010 10:59:55 +0919

なつたん: Python でSICP4.3　Nondeterministic Computingを読んだら、非決定計算が割りとすんなり理解できた。去年はambわかんねと思ったが、分かってみるとあー非決定計算ねと思えた。

あとジェネレータが便利じゃないかと。それにしても遅延評価みたいなもんかなと思ったら、似たようなシチュエーションでも使えるのね。

再帰とジェネレータ

が面白く読めた。

そういえば非決定計算を使った構造活性相関解析例なんかはあるのだろうか？prologなんかを使った例は見たことあるけど、実用例じゃなかったからな。pythonでかけるなら書いてみたいなぁ。

リストってもんがちょっと分かった気がする

Wed, 16 Dec 2009 20:35:42 +0919

SICPの2.2.1章の「並びの表現」っていうところを読んで、carとかcdrのでリストを表現の仕方を学んだ。

これ読んでhaskellのアレが理解できた。アレってばhaskellの:演算子のこと。

[1,2,3]
= 1 : [2,3]
= 1 : 2 : [3]
= 1 : 2 : 3 : []

最初普通のhaskellプログラミングを読んだときにはよくわからなかったけど、carとcdrが理解できた今ならこれって凄く自然に思えてくるのが不思議。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / ￥ 2,940 ()
在庫あり。

それにしても、SICPおもしろいなぁ。なかなか進まないけど。

リストの覚書き

Wed, 16 Dec 2009 20:35:18 +0919

お盆なんでU隊長の実家にいったんやけど、やることないのでSICP読みながら遊び中。

haskellの

[1,2,3]
= 1 : [2,3]
= 1 : 2 : [3]
= 1 : 2 : 3 : []

は、gaucheで

(list 1 2 3)
= (cons 1 (list 2 3))
= (cons 1 (cons 2 (list 3)))
= (cons 1 (cons 2 (cons 3 '())))

カッコがないほうがわかりやすいナァ(ボソッと)。

モナド(副作用の意思を伝える?)

Wed, 16 Dec 2009 20:35:01 +0919

非決定性計算とかambでどんづまり。なんか色々みているうちにうっかりモナドに迷い込んでしまった。

世界で一番か二番くらいにやさしい「モナド入門」

我々の課題を思い出してください：「副作用付き計算を、純関数で表現せよ」でした。カウンター（大域変数count）に触ることは副作用ですから、これをやめましょう。んじゃ、カウントアップできないじゃないか！って？はい、そのとおり。でも、「カウントアップしたい」という意志を伝えることはできます。

Perlの駱駝のこぶにはMonadも入ってる

結局Monadを実装するためには、値と副作用を別々に保持し、値に関しては参照等価性を保ちさえすればいい。

    $op0->{value} = eval{
        $coderef->($op0->{value}, $op1->{value});
    };
    if ($@){
        $op0->{state} = $@;
        $op0->{value} = undef;
    }

evalで「失敗するかもしれない演算」を包んで「より大きな失敗するかもしれない演算」を作るって解釈すればよいのかな。

ふつうのHaskellプログラミングふつうのプログラマのための関数型言語入門
青木峰郎
ソフトバンククリエイティブ / ￥ 2,940 ()
在庫あり。

あとでふつうのHaskellプログラミング読み返そう。

SICP5章　schemeでレジスタ計算機を模倣する

Thu, 02 Apr 2009 06:22:26 +0919

ずっと5章に興味が持てなくてほったらかしにしていたのだけど、読み始めた。5章は毛色が違うように感じてたのと、単に関数型言語が知りたいだけだったら3章までで満足できて、計算機の話って何が面白いんだろうか？なんて思ってたのだけど、（僕の場合）以下のような道のりを経て5章にたどり着いた。

EsoteicでVMとかエミュレータみたいなもんに興味がわいた。あと中間言語

Bolicとか。そういえばゲノム言語とかつくったみたな。

Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~
原悠
毎日コミュニケーションズ / ￥ 2,814 ()

プログラミングの力を生み出す本

Cのプログラムをアセンブリから眺めてみる。レジスタとかメモリとか意識できるようになった。

プログラミングの力を生み出す本―インテルCPUのGNUユーザへ
橋本洋志,松永俊雄,冨永和人,石井千春
オーム社 / ￥ 2,625 ()

CPUの創りかた

4bitCPUつくる。半加算器とか全加算器が論理回路でつくれるとかそういう話は楽しい。

CPUの創りかた
渡波郁
毎日コミュニケーションズ / ￥ 2,940 ()
在庫あり。

SICP5章

という長い道のりを経て、やっとSICP5章。

数日かけてバグとって、実際にGCDマシンが動いた時にはかなり感動。

gosh> (set-register-contents! gcd-machine 'a 206)
done
gosh> (set-register-contents! gcd-machine 'b 40)
done
gosh> (start gcd-machine)
done
gosh> (get-register-contents gcd-machine 'a)
2

デバッグしながら中身の動きが理解できた。

相変わらず継続

Sun, 18 Jan 2009 22:39:14 +0919

継続のあたりをうろうろしてますが、先週末に到着したOn Lispの継続の章をつまみ読みしてまたちょっと理解がすすんだような気がしたようなしないような。

On Lisp
ポールグレアム
オーム社 / 3990円 ( 2007-03 )

最後の方で、

継続

CPS変換を覚えればcall/ccを書くのは簡単だ． CPS変換を経たプログラムでは，全体に対する現在の継続が常に存在し， call/ccはその引数として何らかの関数を呼び出す単純なマクロとして実装できる．

と書いてあるのだが、perl - to goto or not to goto, that's the continuationの先にどうやればperlでcall/ccが実装できるのかわからん。

rubyにはcall/ccがあるらしいですね

そもそもCall/CCがrubyに実装されている理由はただ一つで、「実装できてしまったから」である。

今年は本をよく読んだ気がする

Sat, 20 Dec 2008 09:46:23 +0919

SICPからHOPへのコンボがperlを扱う上でとても役立った。

計算機プログラムの構造と解釈
ジェラルド・ジェイサスマン
ピアソンエデュケーション / 4830円 ( 2000-02 )

特にHOPは値段以上の価値があったと思ってるので満足。

Higher-Order Perl: Transforming Programs with Programs
Mark Jason Dominus
Morgan Kaufmann / 5976円 ( 2005-03-28 )

そしてMAWP

Mastering Algorithms With Perl
Jon Orwant
Oreilly & Associates Inc / 2716円 ( 1999-07 )

来年もこの調子で。あと、もっとコードを書く。

HOP 8.8はバックトラッキング

Fri, 19 Oct 2007 22:03:53 +0919

継続(8.8.1)使ってやる方法と、パーサ自体に押し込む(8.8.2)方法がある。 SICPのambのところを後でもう一度読んでおく。