среда, 8 июля 2009 г.

Tailcall оптимизация в Perl5

Еду вчера вечером домой и с интересом наблюдаю за хаотичным блужданием мыслей в своей голове. Так забавно! И вдруг, в мгновение ока все замирает и тут же исчезает - остается лишь одна единственная мысль. Мысль о том, что "все-таки она вертится". То есть - существует. Это я о tailcall оптимизации в Perl5.

B одной заметке из цикла "Сегодня без..." было упомянуто, что в Per5, в отличии от Perl6, нет tailcall оптимизации. Так вот, это утверждение не совсем корректное. Да, в Perl5 нет автоматической tailcall оптимизации, но ее можно сделать вручную при помощи выражения "goto &NAME".

В качестве примера узнаем чему равен факториал десяти тысяч:

sub fact {
my ($i) = @_;
if ($i) {
return $i * fact($i - 1);
} else {
return 1;
}
}

Хотя, зачем мне знать это большое число? Да и кто на практике считать факториал рекурсией, если можно циклом. Но пример есть пример. И так, запускаем код на выполнение - Perl выводит предупреждение о слишком глубокой рекурсии и начинает "пухнуть", пытаясь вычислить факториал. Ой, память закончилась...

Перепишем подпрограмму для tailcall оптимизации:

sub fact { _fact(1, $_[0]) }
sub _fact {
my ($r, $i) = @_;
if ($i) {
return _fact($r * $i, $i - 1);
} else {
return $r;
}
}

Результат вычисления, как и следовало ожидать, такой же - нехватка памяти.

А теперь воспользуемся магией "goto &NAME" и сделаем tailcall:

sub _fact {
my ($r, $i) = @_;
if ($i) {
@_ = ($r * $i, $i - 1);
goto &_fact;
} else {
return $r;
}
}

Да... Большое число вышло: 35 с половиной тысяч знаков (использовалась прагма bigint).

Вывод. Не перестаю удивляться возможностям Perl в умелых руках.

2 комментария:

Fedor Soreks комментирует...

Клево, думал даже перевести на английский, но догадался отгуглить — ничто не ново под русской луной.

Nick комментирует...

А я догадался отгуглить только после того.
:-)