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 / ￥ 8,658 (2005-05-30)
通常24時間以内に発送
そしてMAWP
Mastering Algorithms With PerlJon Orwant,Jarkko Hietaniemi,John MacDonald
Oreilly & Associates Inc / ￥ 4,054 (1999-07)
通常3～5週間以内に発送
来年もこの調子で。あと、もっとコードを書く。
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―Advanced Techniques for Common 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使った継続だとおまじないがいらないってのもまた謎なんだよなぁ。
SICP ４章斜め読んだ
遅延評価とか継続とかambとか。
ちょっとついてけなくて、問題も解かずにとりあえずざっと読んだ感じ。一度立ち止まって色々調べてもう一度戻ってくる。あと、知ってる言語での実装も追いかけながらきちんと理解する。
あと5章の意義がいまいちわからん。レジスタ計算機を実装するとどういいんだろう?そこまでわかってないと継続とかきちんと理解できなさそうだっていうのはなんとなく感じるんだけど。
(4章とかを)わかっているから、5章を読むことでさらに理解が深まるという章なのではなかろうかと。
かぶれ気味かなと思いつつも、指が勝手にOn Lispを注文した。