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);

これで、素数のストリームが生成される。

計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン,ジュリー サスマン,ハロルド エイブルソン
ピアソンエデュケーション / ￥ 4,830 (2000-02)
通常24時間以内に発送

Higher-order Perl: A Guide To Program Transformation
Mark Jason Dominus
Morgan Kaufmann Pub / ￥ 7,608 (2005-05-30)
通常24時間以内に発送

無限ストリームは楽しい

Amazonに訳が悪いと散々書かれていて、ちょっと躊躇したのだけど、実際買って読んでみたら特に訳がひどいと思うことはなかった。

あと、原著読めばとか書いてあるのは、原著読めばって書く前に原著読むだろうから、そもそも訳が悪いとかすらいわんだろう。結局何であんなに訳が悪いというコメント気にしたのか今となってはさっぱりわからん。日本語訳より原著で読んだほうがよくわかって良いというレビューがなかったのもいまとなってはフーンとか思う。Amazonの訳が悪いってのは何の裏返しなのかよく考えないといけないのかもと、いまさら学んだ。

訳が良かったらもっと早く飲み込めるかというと、そういうもんではない気もするし。

計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン,ジュリー サスマン,ハロルド エイブルソン
ピアソンエデュケーション / ￥ 4,830 (2000-02)
通常24時間以内に発送

僕的には買って良かったと思える本の一つ。

参考にしたサイト

• 継続渡しスタイル
• Appendix 3. 継続についてもう少し

継続渡しスタイルに載ってた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だと、クロージャの中の

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しても正常に実行されるので、クロージャの中に評価する式があることが重要みたいなんだけど、、、

山口家の逆襲->perl-解説->クロージャ

4:実体をそのまま覚えるためには、サブルーチン内でもそのレキシカル変数が使われていなくてはならない。 (サブルーチン内にその変数がなければ、実質サブルーチンはその変数を知らないのと同じコトになる)

これとか関係あるのだろうか?

goto使った継続だとおまじないがいらないってのもまた謎なんだよなぁ。

遅延評価とか継続とかambとか。

ちょっとついてけなくて、問題も解かずにとりあえずざっと読んだ感じ。一度立ち止まって色々調べてもう一度戻ってくる。あと、知ってる言語での実装も追いかけながらきちんと理解する。

あと5章の意義がいまいちわからん。レジスタ計算機を実装するとどういいんだろう?そこまでわかってないと継続とかきちんと理解できなさそうだっていうのはなんとなく感じるんだけど。

(4章とかを)わかっているから、5章を読むことでさらに理解が深まるという章なのではなかろうかと。

かぶれ気味かなと思いつつも、指が勝手にOn Lispを注文した。

On Lisp―Advanced Techniques for Common Lisp
Paul Graham
オーム社 / ￥ 3,990 (2007-03)
通常24時間以内に発送

サケダメ宣言が出されたので、夜な夜なお茶を飲みながらSICP。あと、最近また電車通勤しているので毎朝SICP。

そんなわけで、3章も順調に消化。というか最後のほうはわかんない問題が多くて端折ったけど(3.60くらいから華麗にスルーした)。

特に無限ストリームと遅延評価のところを読み終えてクロージャってものに対する認識がちょっと変わったかも。

いままでは、オブジェクトは関数を保持したデータ、クロージャはデータを保持した関数なんて理解してたんだけど、今はクロージャは環境を隔離して時を止めたものみたいな感覚で接している。

そんな今ではλ萌え - たらいを後回しが面白く読めた。

yesコマンドみたいにひたすらyが出力される無限ストリーム

(define yes (cons-stream 'y yes))

SICPの3.5面白いけど、本の写経だとcons-streamが実装できないので手を動かす時に魅力が半減するよな。というか、ここまでくるとどうしても動かしてみたいでしょう。

ググって、真の写経(マクロ分からんが)、実行してみる。

gosh> (define yes (cons-stream 'y yes))
yes
gosh> (car yes)
y
gosh> (car yes)
y
gosh> (car yes)
y
gosh> (car yes)
y
gosh> (car yes)
y

位置を指定するとその位置のパスカル三角形の値を返す。再帰で。

sub pascal{
 my ($n,$r) = @_;
 $n<2?1:$r==0?1:$n==$r?1:pascal($n-1,$r-1)+pascal($n-1,$r);
}

print pascal(0,0);
print "\n";
print pascal(1,0);
print pascal(1,1);
print "\n";
print pascal(2,0);
... 
print pascal(4,3);
print pascal(4,4);
print "\n";

三角形

$ perl pascal.pl 
1
11
121
1331
14641

この関数を利用して、最小完全ハッシュ関数を。

sub cn {
 my @table = @_;
 my ($hash,$n,$r) = (0,5,2);
 for (my $i=0;$n>$r && $r>0;$i++){
   $n--;
   $hash += pascal($n,$r--) if ($table[$i]);
 }
 return $hash;
}

が、「組合せ型の最小完全ハッシュ関数」の逆関数に持っていけなかった。再帰でパスカル三角形を右斜め下から左斜め方向に足していく組み合わせをつくっていって問い合わせの数値になったところのリストを返せばよいと思うんだけど、うまい書き方がみつからなかった。

リストの問題

(define (make-cycle x)
  (set-cdr! (last-pair x) x)
  x)

という定義に対し

gosh> (define z (make-cycle (list 'a 'b 'c)))
z
gosh> z
#0=(a b c . #0#)

これに(last-pair z)は無限ループ

今週は朝も夜も週末も集中して読めたため、2章を読み終えた。最後の2.5はなんかいい加減に読んだので後々読み返すことになりそうな気もするが。

計算機プログラムの構造と解釈
ジェラルド・ジェイ サスマン,ジュリー サスマン,ハロルド エイブルソン
ピアソンエデュケーション / ￥ 4,830 (2000-02)
通常24時間以内に発送

p.109のメッセージパッシングとOOPって関連するよな。と思って調べてみたけどいまいちうまい表現が見つからなかった。

あとperlでOOPやるときのblessとmy $self = shift;みたいに第一引数が自分自身なのとperlのオブジェクトがblessされたハッシュリファレンスなこととか、もうすこしでちゃんと理解できそうな感じなんだけど、Perl におけるオブジェクト指向を読んでちょっと前進。

おもしろいですな、SICP