スキップしてメイン コンテンツに移動

Perl 5 to 6 - 遅延性

これはMoritz Lenz氏のWebサイトPerlgeek.deで公開されているブログ記事"Perl 5 to 6" Lesson 12 - Lazinessの日本語訳です。

原文はCreative Commons Attribution 3.0 Germanyに基づいて公開されています。

本エントリにはCreative Commons Attribution 3.0 Unportedを適用します。

Original text: Copyright© 2008-2010 Moritz Lenz

Japanese translation: Copyright© 2011 SATOH Koichi

NAME

"Perl 5 to 6" Lesson 12 - 遅延性

SYNOPSIS

my @integers = 0..*;
for @integers -> $i {
    say $i;
    last if $i % 17 == 0;
}

my @even := map { 2 * $_ }, 0..*;
my @stuff := gather {
    for 0 .. Inf {
        take 2 ** $_;
    }
}

DESCRIPTION

Perlプログラマは怠けがちです。彼らが使うリストも。

ここで怠惰という言葉が意味するのは、評価が可能な限り遅延されるということです。 @a := map BLOCK, @bのようなコードを書いたとき、ブロックは一切実行されません。 @aの要素にアクセスしようとしたときだけmapは実際にブロックを実行し、必要とされる分だけ@aを埋めます。

代入ではなくバインディングを使っていることに注意して下さい: 配列への代入は先行評価を強制することがあります(コンパイラがリストの無限性に気づかない限り; 無限リスト検出の詳細はまだ固まっていません)。 バインディングはそのようなことがありません。

遅延性は無限リストの取り扱いを可能にします: 引数すべてに操作を行うようなことさえしなければ、評価された要素に必要なだけのメモリしか必要としません。

しかし落とし穴があります: 長さの取得やソートは遅延性を殺します——無限リストであっても。その場合無限ループになるでしょう。

一般にスカラへの変換(例えばList.join)は先行評価です。つまり遅延評価されません。

遅延性は不必要な計算を防ぎ、それによってコードの簡潔性を保ったままパフォーマンスを上げることができます。

Perl5で一行ずつファイルを読む場合、for (<HANDLE>)はファイル全体をメモリに読み込んだ後に走査を始めるのであまり使われませんでした。 遅延性があればこれは問題になりません:

my $file = open '/etc/passwd';
for $file.lines -> $line {
    say $line;
}

$file.lineはイテレータか遅延リスト(どっちでも同じことです)なので、行は必要な分だけがディスクから物理的に読み込まれます(当然バッファリングはかませた上で)。

gather/take

遅延リストを作るのに非常に便利な構造がgather { take }です。 以下のようにして使います:

my @list := gather {
    while True {
        # 何か計算;
        take $result;
    }
}

gather BLOCKは遅延リストを返します。 @listの要素が必要になるとtakeが実行される位置までBLOCKが走ります。 takeは丁度returnのようなもので、takeされた要素はすべて@listの生成に使われます。 @listの要素がもっと必要になると、ブロックの実行がtakeの直後から再開されます。

gather/takeは動的スコープを持つので、gatherの字句的スコープの外でtakeを呼ぶことができます:

my @list = gather {
    for 1..10 {
        do_some_computation($_);
    }
}

sub do_some_computation($x) {
    take $x * ($x + 1);
}

遅延性の制御

遅延性には固有の問題があり(Haskellを学んだことがあるなら、そのIOシステムが遅延性と無副作用性のためにどれだけ妙なことになっているか気づいたでしょう)、時には遅延して欲しくないものもあります。その場合eagerを先頭に付けるだけです。

my @list = eager map { $block_with_side_effects }, @list;

逆に言うと、リストだけがデフォルトで遅延されます。ただしスカラも遅延させることができます:

my $ls = lazy { $expansive_computation };

MOTIVATION

計算機科学ではほとんどの問題は可能な組み合わせの木として記述され、その中で解が探索されます。 効率的なアルゴリズムの鍵は効率的な探索法だけではなく、木の重要な部分だけを生成することでもあります。

遅延リストを使えば、この木と探索法を再帰的に定義し、実際に使っている部分木のみを自動的に生成できます。

一般に遅延性はプログラミングを簡単にします。計算結果がすべて使われるか気にせず済むからです——遅延評価にするだけで、もし結果が使われなければ計算は実行されず、使われたなら何も損していません。

SEE ALSO

http://perlcabal.org/syn/S02.html#Lists

コメント

このブログの人気の投稿

部分継続チュートリアル

この文書についてこれはCommunity Scheme Wikiで公開されているcomposable-continuations-tutorial(2010年09月30日版)の日本語訳です。誤字脱字・誤訳などがありましたらコメントあるいはメールで御指摘いただけると幸いです。本訳は原文のライセンスに基づきCreative Commons Attribution-ShareAlike 2.0 Genericの下で公開されます。Original text: Copyright© 2006-2010 Community Scheme WikiJapanese translation: Copyright© 2011 SATOH Koichi本文部分継続(Composable continuation)は継続区間を具象化することで制御を逆転させるものです。 ウンザリするほど複雑な概念を表す長ったらしいジャーゴンのように聞こえますが、実際はそうではありません。今からそれを説明します。resetとshiftという2つのスペシャルフォームを導入するところから始めましょう[1]。 (reset expression)は特別な継続を作るなりスタックに目印を付けるなりしてからexpressionを評価します。簡単に言えば、expressionが評価されるとき、あとから参照できる評価中の情報が存在するということです。 実際にはshiftがこの情報を参照します。(shift variable expression)は目印のついた場所、つまりresetを使った場所にジャンプし、その場所からshiftを呼び出した場所までのプログラムの断片を保存します; これはプログラムの区間を「部分継続」として知られる組み合わせ可能な手続きに具象化し、この手続きにvariableを束縛してからexpressionを評価します。組み合わせ可能(Composable)という語はその手続きが呼び出し元に戻ってくるため、他の手続きと組み合わせられることから来ています。 Composable continuationの別名として例えば限定継続(Delimited continuation)や部分継続(Partial continuation)もありますが、ここでは一貫して「組み合わせ可能」という用語を使います(訳注: …

多分週刊チラシの裏 (Sep 14-20, 2020)

自分にとってのニュースは自らまとめるしかないと思い至ったので興味深かったものをまとめる。Moment.js 開発終了JavaScript における日時処理の定番であった Moment.js の開発がメンテナンスモードへの移行を宣言した。歴史のあるライブラリであり、オブジェクトが可変で flux アーキテクチャと相性が悪いとか、自前の国際化リソースが全部バンドルされているので昨今の Dead Code Elimination (a.k.a. Tree-Shaking) を伴うバンドラでもサイズが縮まらないといった問題が指摘されていた。 互換性を保ったまま問題を解決できる見込みがなく、非互換な新バージョンをリリースして移行の混乱を生むよりは設計段階で問題を解決している別ライブラリに移行せよとのこと。参考に個人的な見解を述べると、代替候補として挙げられている dayjs はお勧めしない。タイムゾーンのサポートなど多くの場合に必要な機能がプラグインで実現されており、それらプラグインは dayjs オブジェクトにメソッドを実行時に追加したり差し替えたりするので TypeScript や flow の型定義と一致しなくなるためである。結局利用するプラグインを適用したバージョンの型定義ファイルを自分で作る羽目になるのだ。dayjs に限らず TypeScript や flow はプラグイン機構を持った JavaScript ライブラリと相性が悪いので、オールインワンなモジュールを採用する方が良い。代替候補の中では最初に挙がっている Luxon が無難である。20年来の銀英伝ファンからみた今回の揉め事「銀河英雄伝説」という古いスペースオペラ小説を原作とするアニメについて以下のツイートが炎上した件: 銀河英雄伝説のリメイク。3期以降も続くのかな。もしそうなら、男女役割分業の描き方は変更せざるをえない気がする。旧アニメのままだと、さすがに時代にそぐわない。作品として大変に面白いのは踏まえたうえで。…なんてことを書いたら炎上するかな。 — Shotaro TSUDA (@brighthelmer) September 11, 2020どう読んでもただの感想だが、話題がジェンダーかつ発言者の津田正太郎教授の所属が「社会学部」ということで表現の自由戦士の標的にされたもの。「社会学者1が『…

多分週刊チラシの裏 (Sep 21-27, 2020)

Killed by MozillaMozilla がディスコンにした製品およびサービスのリスト。COVID-19 パンデミックで収入が激減し全社の四分の一にあたる従業員の解雇と収益を得られる製品への集中に踏み切った Mozilla Corp. の最初の犠牲はノートアプリ Firefox Notes とファイル送信サービス Firefox Send となった。過去には第三のモバイル OS を目指した Firefox OS とか Mac ネイティブな Gecko ベースブラウザ Camino など懐かしい名前も見られる。ちなみに元ネタは Google が終了したサービスをリストしている Killed by Google で、こちらは 2020 年 9 月 26 日現在 205 個の製品とサービスが挙がっている。Firefox 81.0 リリースノートMozilla Firefox 81.0 が Release チャンネルに公開された。最大の新機能はメディア再生のキーボードないしヘッドセットからの制御である。要はバックグランドで再生している YouTube タブを AirPods から一時停止できるようになった。Developer Tools における色覚異常シミュレーションの改善やブラウザ標準 audio/video 要素のアクセシビリティ改善なども含まれている。Facebook が自社プラットフォーム上での複数国による組織的政治工作を認識しながら放置していたFacebook が大量の偽アカウントを動員した政治工作を認識していながら、特に小国のそれに対して対策を放棄していたという内部告発。元 Facebook のデータ科学者である Sophie Zhang 氏の告発によれば、ホンジュラスで大統領派の工作が行われていることを氏が報告してから実際に対策が為されるまでに 9 ヶ月、アゼルバイジャンでの与党の工作を同様に報告してから組織的な調査が始まるまでに実に 1 年を要したという。本来この手の濫用に対応するはずの専任チームは濫用の圧倒的な割合を占めるスパム対応にかかりきりで、政治工作については対象が合衆国か西欧である場合を除いて積極的に行動せず、小国の民主主義は Zhang 氏の空き時間を利用した片手間の対応にかかっていたとのこと。Rust じゃダメな理由近年人気が出てい…