第16回Ruby勉強会とAMB

第16回Ruby勉強会にいってきました。数少ない、うちがRubyistになる瞬間です。でも今回は割とPerlも書いてました。ごめんなさい。

だいぶメンバーも見慣れた感じになってきましたね。いろいろと情報交換や議論が行われるだけでなく、いろんなイベントもここのメンバーの中から行われるようになってきました。関西でLLといえばRuby勉強会はかなりいい環境ですね。運営スタッフのみなさんありがとー。

といっても、もちろんRubyメインなので、Perlの形見は狭いのです。Perl方面もがんばらないと!

今回は、yharaさんの発表である「30分で分かる継続の使い方」におもしろくてハマりました。継続はかなりすごいけど、かなりきもいですね。

そのyharaさんの発表の中でRubyの継続を使った具体例としてAMBというモジュールというのが出てきたのですが、これが中々クールだったのでPerlで実装できないかやってみました。

AMBモジュールは非決定性計算を楽に行うためのモジュールらしく、内部で継続を使っています。くわしくは、非決定性計算で述べられています。この記事では、SICPの載っている以下の問題を解いてるみたいですね。

Baker,Cooper,Fletcher,MillerとSmithは五階建てアパートの相異なる階に住んでいる。
・Backerは最上階に住んでいない。
・Cooperは最下階に住んでいない。
・Fletcherは最上階にも最下階にも住んでいない。
・MillerはCooperよりも上の階に住んでいる。
・SmithはFletcherの隣の階に住んでいない。
・FletcherはCooperの隣の階に住んでいない。
それぞれの住んでいる階は?

このAMBをPerlで作るのですが、CPANにはRubyのContinuationのようなものがぱっと見当たらなかったので、継続は使わないでやることにしました。
うーん、継続のように環境を保存するにはやっぱりクロージャーかなぁ、ってことでクロージャを使ってみることに。完成したモジュールは以下のようになります。

package AMB;
use strict;
use warnings;

sub new {
    my ($class) = @_;
    return bless {chooses => []}, $class;
}

sub choose {
    my ($self, @values) = @_;

    my $index = 0;
    my $parent
        = @{$self->{chooses}} ? $self->{chooses}->[-1] : sub { () };
    my @result;

    push @{$self->{chooses}}, sub {
        @result = $parent->() unless @result;
        return (@result, $values[$index++]) if @values > $index;

        $index = 0;
        @result = $parent->();
        return unless @result;
        return (@result, $values[$index++]);
    };
}

sub combination {
    return unless @{$_[0]->{chooses}};
    return $_[0]->{chooses}->[-1]->();
}

1;

そこそこシンプルに書けたかな?chooseというサブルーチンが、これまでに選択された値の配列と、自分の持つデータと、そのインデックスの情報を持つクロージャを$self->choosesにセットします。とか、書いてもわかりにくいですね。なので、とりあえず使い方を。

use AMB;
use Perl6::Say;

my $amb = AMB->new;

$amb->choose(1,2,3);
$amb->choose(1,2,3);

while (my @digits = $amb->combination) {
    say @digits;
}

これで、(1,2,3)という集合と(1,2,3)の集合のすべての順列の組み合わせが表示されます。

$ perl run_amd_blog.pl
11
12
13
21
22
23
31
32
33

0と1だけにすると2進数カウンターのできあがりです。呼ぶたびにインクリメントされます。

use AMB;
use Perl6::Say;
use List::MoreUtils qw(uniq);

my $amb = AMB->new;

$amb->choose(0,1);
$amb->choose(0,1);
$amb->choose(0,1);
$amb->choose(0,1);

while (my @digits = $amb->combination) {
    say @digits;
}
$ perl run_amd_blog.pl
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111

条件をwhileの中に書き込めばSICPの非決定性計算の問題も解くことができます。

use strict;
use warnings;
use lib './lib';
use AMB;
use Perl6::Say;
use List::MoreUtils qw(uniq);

my $amb = AMB->new;

$amb->choose(1,2,3,4,5); #baker
$amb->choose(1,2,3,4,5); #cooper
$amb->choose(1,2,3,4,5); #fletcher
$amb->choose(1,2,3,4,5); #miller
$amb->choose(1,2,3,4,5); #smith

while ( my ($baker, $cooper, $fletcher, $miller, $smith) = $amb->combination) {
    next unless uniq($baker, $cooper, $fletcher, $miller, $smith) ==  5;
    next unless $baker != 5;
    next unless $cooper != 1;
    next unless $fletcher != 1 && $fletcher != 5;
    next unless $miller > $cooper;
    next unless abs($smith - $fletcher) != 1;
    next unless abs($fletcher - $cooper) != 1;

    say $baker, $cooper, $fletcher, $miller, $smith;
} 

結構APIは違いますが、RubyのAMBとぱっと見似たようなものができました。しかし、どっちかというと、ただの順列の組み合わせジェネレータという感じ。継続のパワーに対抗できたというほどではないかもですね。さがせばこんなCPANモジュールも見つかるかも。