SICP5章 schemeでレジスタ計算機を模倣する
ずっと5章に興味が持てなくてほったらかしにしていたのだけど、読み始めた。5章は毛色が違うように感じてたのと、単に関数型言語が知りたいだけだったら3章までで満足できて、計算機の話って何が面白いんだろうか？なんて思ってたのだけど、（僕の場合）以下のような道のりを経て5章にたどり着いた。
EsoteicでVMとかエミュレータみたいなもんに興味がわいた。あと中間言語
Rubyで作る奇妙なプログラミング言語 ~Esoteric Language~プログラミングの力を生み出す本
Cのプログラムをアセンブリから眺めてみる。レジスタとかメモリとか意識できるようになった。
プログラミングの力を生み出す本―インテルCPUのGNUユーザへCPUの創りかた
4bitCPUつくる。半加算器とか全加算器が論理回路でつくれるとかそういう話は楽しい。
CPUの創りかた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
デバッグしながら中身の動きが理解できた。
pythonのジェネレータがちょっと分かった
なつたん: Python でSICP4.3 Nondeterministic Computingを読んだら、非決定計算が割りとすんなり理解できた。去年はambわかんねと思ったが、分かってみるとあー非決定計算ねと思えた。
あとジェネレータが便利じゃないかと。それにしても遅延評価みたいなもんかなと思ったら、似たようなシチュエーションでも使えるのね。
が面白く読めた。
そういえば非決定計算を使った構造活性相関解析例なんかはあるのだろうか？prologなんかを使った例は見たことあるけど、実用例じゃなかったからな。pythonでかけるなら書いてみたいなぁ。
今年は本をよく読んだ気がする
SICPからHOPへのコンボがperlを扱う上でとても役立った。
特にHOPは値段以上の価値があったと思ってるので満足。
Higher-order Perl: A Guide To Program TransformationMark Jason Dominus
Morgan Kaufmann Pub / ￥ 6,152 ()
通常1～3週間以内に発送
そしてMAWP
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 3,431 ()
通常11～13日以内に発送
来年もこの調子で。あと、もっとコードを書く。
HOP 8.8はバックトラッキング
継続(8.8.1)使ってやる方法と、パーサ自体に押し込む(8.8.2)方法がある。 SICPのambのところを後でもう一度読んでおく。
計算機プログラムの構造と解釈なんていうかまだ継続をきちんと理解していないことが理解できた。
Higher-order Perl: A Guide To Program TransformationMark Jason Dominus
Morgan Kaufmann Pub / ￥ 7,588 (2005-05-30)
通常24時間以内に発送
エラトステネスの篩のストリーム
HOPの6章は無限ストリームを扱っているのだけれど、SICPの無限ストリームの章にあるエラトステネスの篩が出てこないので書いてみた。
HOPだとcar,cdr,consがそれぞれhead,tail,nodeとなってるのでそれにあわせてある。promiseは計算を遅延させるためのクロージャ。
use strict;
use warnings;
no warnings 'recursion';
sub promise (&) { $_[0] }
sub node{
my ($h, $t) = @_;
[$h, $t];
}
sub head {
my ($ls) = @_;
$ls->[0];
}
sub tail {
my ($ls) = @_;
if(is_promise($ls->[1])){
$ls->[1] = $ls->[1]->();
}
$ls->[1];
}
sub is_promise {
UNIVERSAL::isa($_[0],'CODE');
}
sub drop {
my $h = head($_[0]);
$_[0] = tail($_[0]);
return $h;
}
sub filter (&$) {
my $f = shift;
my $s = shift;
until(! $s || $f->(head($s))){
drop($s);
}
return if ! $s;
node(head($s),promise {filter($f, tail($s))});
}
sub sieve {
my $s = shift;
node(head($s),
promise {sieve(filter {$_[0] % head($s)} tail($s))});
}
sub upfrom {
my ($m) = @_;
node($m, promise{ upfrom($m+1)});
}
sub show {
my ($s,$n) = @_;
while($s && (! defined $n || $n-- > 0)){
print head($s), $";
$s = tail($s);
}
print $/;
}
my $primes = sieve(upfrom(2));
show($primes,300);
これで、素数のストリームが生成される。
計算機プログラムの構造と解釈
Higher-order Perl: A Guide To Program TransformationMark Jason Dominus
Morgan Kaufmann Pub / ￥ 7,608 (2005-05-30)
通常24時間以内に発送
無限ストリームは楽しい
SICPの訳
Amazonに訳が悪いと散々書かれていて、ちょっと躊躇したのだけど、実際買って読んでみたら特に訳がひどいと思うことはなかった。
あと、原著読めばとか書いてあるのは、原著読めばって書く前に原著読むだろうから、そもそも訳が悪いとかすらいわんだろう。結局何であんなに訳が悪いというコメント気にしたのか今となってはさっぱりわからん。日本語訳より原著で読んだほうがよくわかって良いというレビューがなかったのもいまとなってはフーンとか思う。Amazonの訳が悪いってのは何の裏返しなのかよく考えないといけないのかもと、いまさら学んだ。
訳が良かったらもっと早く飲み込めるかというと、そういうもんではない気もするし。
僕的には買って良かったと思える本の一つ。
モナド(副作用の意思を伝える?)
非決定性計算とかambでどんづまり。なんか色々みているうちにうっかりモナドに迷い込んでしまった。
我々の課題を思い出してください：「副作用付き計算を、純関数で表現せよ」でした。カウンター（大域変数count）に触ることは副作用ですから、これをやめましょう。んじゃ、カウントアップできないじゃないか！ って？はい、そのとおり。でも、「カウントアップしたい」という意志を伝えることはできます。
結局Monadを実装するためには、値と副作用を別々に保持し、値に関しては参照等価性を保ちさえすればいい。
$op0->{value} = eval{
$coderef->($op0->{value}, $op1->{value});
};
if ($@){
$op0->{state} = $@;
$op0->{value} = undef;
}
evalで「失敗するかもしれない演算」を包んで「より大きな失敗するかもしれない演算」を作るって解釈すればよいのかな。
ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門あとでふつうのHaskellプログラミング読み返そう。
相変わらず継続
継続のあたりをうろうろしてますが、先週末に到着したOn Lispの継続の章をつまみ読みしてまたちょっと理解がすすんだような気がしたようなしないような。
On Lisp最後の方で、
CPS変換を覚えればcall/ccを書くのは簡単だ． CPS変換を経たプログラムでは，全体に対する現在の継続が常に存在し， call/ccはその引数として何らかの関数を呼び出す単純なマクロとして実装できる．
と書いてあるのだが、perl - to goto or not to goto, that's the continuationの先にどうやればperlでcall/ccが実装できるのかわからん。
そもそもCall/CCがrubyに実装されている理由はただ一つで、「実装できてしまったから」である。
perlでcall-with-procedure
参考にしたサイト
継続渡しスタイルに載ってたcall-with-procedureをperlで。
sub call_with_procedure {
my ($exp,$proc) = @_;
$proc->($exp);
}
sub fact {
my $n = shift;
$n == 1 ? 1 : $n * fact($n-1);
}
print call_with_procedure(sub {2 * $_[0]}, sub {$_[0]->(fact(10))});
実行すると
$ perl curpr.pl
7257600
継続ってのはgaucheだと外に向いているようなものを内側にひっくり返す感があってなんか奇妙な感じがするが、いくつか書いてみてから継続の説明を読むと、なんかフムフム感が得られる。だけど、それをperlでやろうとするとひどく混乱するのはなぜだろうか？
sub {$_[0]->(fact(10))}->(sub {2 * $_[0]})
= {2 * $_[0]}->(fact(10))
= 2 * fact(10)
書き下してみるとこんな感じか、、、、
最初のsub{}->()ってコードはautoboxを使えば動きそうな気がするが、、、
実際にやってみることにした。
use autobox;
use autobox::Core;
sub fact {
my $n = shift;
$n == 1 ? 1 : $n * fact($n-1);
}
print sub {$_[0]->(fact(10))}->(sub {2 * $_[0]});
無名サブルーチンが第一引数に無名サブルーチンを取ってこれが引数にfact10の結果を取ってそれを二倍するっていう処理が実行される（はず）
$ perl abtest.pl
7257600
動いた!
call/ccの勉強してたのに、キモコードを動かすというあらぬ方向に行ってしまったが、ファーストクラスオブジェクトってのがなんだかわかったようなわからんようなホンワカした何かを得た感があったのでよしとしよう。
perlの継続の謎のおまじないがやたらと気になる
継続ブーム到来中。なんでも継続読みましたよ、何度も何度も読みまくりなのでなんども継続
もちろんperlでもやってみたくなるので、なんでも継続、Perl で。とか継続は力なり読みながら手を動かしてみた。
が、perlだと、クロージャの中の
my $dummy = $cont; # なぜか必要みたい。
ってのが何故必要なのかわからないし、なんでそんなへんなのがそこにあるのかが、凄い気になるのでデバッガで追いかけた。
該当行を
#my $dummy = $cont; # なぜか必要みたい。
として perl -dで起動してみるといつまでたっても終わらない。なんか無限ループしてるっぽい。mとnの値がどんどんでかくなっていってるみたいだし、、、、。デバッガじゃなくて何が渡されてるのかprintしてみる。
sub {
my ($n) = @_;
my $dummy = $cont; # なぜか必要みたい。
print "n: $n\n";
&leaf_count_cps ($tree->[1],
sub {
my ($m) = @_;
print "m: $m\n";
$cont->($n + $m);
});
});
とやってnとmを追いかけると、おまじない入りは
$ perl cont.pl # [["a", "b"], [["c", "d"], "e"]];
n: 1
m: 1
n: 2
n: 1
m: 1
n: 2
m: 1
m: 3
5
予想通りの挙動。
で、my $dummy = $contが評価されないようにしてみると
$ perl cont.pl# [["a", "b"], [["c", "d"], "e"]];
n: 1
m: 1
n: 2
m: 1
m: 3
n: 4
m: 1
m: 5
m: 7
...ずっと続く...
よくわからん。別に代入じゃなくて$contをprintしてもrefしても正常に実行されるので、クロージャの中に評価する式があることが重要みたいなんだけど、、、
4:実体をそのまま覚えるためには、サブルーチン内でもそのレキシカル変数が使われていなくてはならない。 (サブルーチン内にその変数がなければ、実質サブルーチンはその変数を知らないのと同じコトになる)
これとか関係あるのだろうか?
goto使った継続だとおまじないがいらないってのもまた謎なんだよなぁ。