Smalltalk 風 while

6 日に引き続き、筆者の趣味に偏った水増し記事です。

末端呼び出しの最適化

Scheme という純度の高い Lisp の方言では、ループはプリミティブではありません。条件分岐と再帰でループを定義します。無限ループは無限再帰になるので、普通ならスタックがあふれてしまいますが、末端呼び出しの最適化が行われれば、そういう事態は避けられます。

Smalltalk ではどうなっているかというと、以下の謎コードが書かれています。詳細は述べませんが、筆者の頭ではどう考えてもループ(再帰)が止まりません。

BlockClosure>>whileTrue: aBlock
    "Ordinarily compiled in-line, and therefore not overridable.
    This is in case the message is sent to other than a literal block.
    Evaluate the argument, aBlock, as long as the value of the receiver is true."

    ^ [self value] whileTrue: [aBlock value]

末端呼び出しは、実は Perl 5 でも最適化できます。要所で goto を使うことで、再帰を使った無限ループが実現できます。

ところが Perl 5 の goto にあたるものが Perl 6 では何になるのか、わかっていません。そこで今回は、6 日に定義したプリミティブを使って、Perl 6 で擬似的なループの制御構造を定義します。この制御構造は無限に繰り返すことはできません。無限に繰り返すことのできる制御構造は Perl 5 で書いて、付録にします。

繰り返しの原理 (面倒なのでテストごと)

a.tail-call.t6

#!/usr/bin/env perl6

# 念のため Unix 版の rakudo-star-2012.11 を使ってください。

use v6;
use Test;
plan *;

my ($x, $y);

sub _do_(:&test, :&todo)
{
    return unless &test();
    &todo();
    _do_ :&test, :&todo;
}

sub test()
{
    0 < $x;
}

sub _todo_()
{
    $y += $x;
    $x--;
}

# say $*ERR: 'it takes a while.';
$*ERR.say('it takes a while.');

($x, $y) = (10, 0);
_do_(:&test, :todo(&_todo_));
is $y, 55;

($x, $y) = (100000, 0);
try { _do_(:&test, :todo(&_todo_)); }
is $!, 'maximum recursion depth exceeded';
isnt $y, 5000050000;

_do_ という制御構造風の関数を定義しています。何も考えずに再帰するので、$x の値が大きくなるとスタックがあふれます ('maximum recursion depth exceeded')。

$ ./a.tail-call.t6
it takes a while.
ok 1 - 
ok 2 - 
ok 3 - 

6 日に作った真偽値クラスを使う

_do_ を、6 日に作った真偽値クラスを使って書き換えます。

複雑なので WhileTrue モジュール/ロールを作る

WhileTrue.pm6

use v6;

role WhileTrue;

method _do_(&todo)
{
    my &tail = sub () {
        my &cont = sub () {
            &todo();
            &tail();
        };
        my &break = sub () { };
        my $b = (self)();
        $b._if_(:t(&cont), :f(&break));
    };
    &tail();
}

テスト

b.while-true.t6

#!/usr/bin/env perl6

# 念のため Unix 版の rakudo-star-2012.11 を使ってください。

use v6;
use B;
use I;
use WhileTrue;
use Test;
plan *;

my ($x, $y);

($x, $y) = (I.new(10), I.new(0));
WhileTrue.new(&test)._do_(&_todo_);
is $y.equals(I.new(55)), T._;

($x, $y) = (I.new(100000), I.new(0));
try { WhileTrue.new(&test)._do_(&_todo_); }
is $!, 'maximum recursion depth exceeded';
isnt $y.equals(I.new(5000050000)), T._;

sub test
{
    $x.equals(0).not;
}

sub _todo_ # `todo` という名前は `Test` と干渉する。
{
    $y = $y.add($x);
    $x = $x.pred;
}

$ perl6 -I../d.st-if -I. b.while-true.t6
it takes a while.
ok 1 - 
ok 2 - 
ok 3 - 

Perl 5 では

カレンダーの趣旨に反するのでここにコードは貼りませんが、下記の github リポジトリには、perl5/ というサブディレクトリがあって、今回の話に対応する Perl 5 による無限に繰り返せるバージョンの WhileTrue の実装とテストが置いてあります。これを読むと Perl 5 の goto が、その名にかかわらず画期的な機能であることが理解できると思います。筆者は Perl 6 でこの goto がどのように昇華されるのかを楽しみにしています。