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時間以内に発送

無限ストリームは楽しい