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

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

コメント

コメントを投稿

このブログの人気の投稿

Project Euler - Problem 35

問題 原文 How many circular primes are there below one million? 日本語訳 100万未満の巡回素数は何個か? 解答 回転させた数値がすべて素数ということは、すべての桁が奇数でなければいけません(ただし2を除く)。 追記 匿名氏にコメントでご指摘頂いたのでコードを一部修正しました。 いずれかの桁に5がある場合も、回転させると必ず5の倍数が現れるので除外できます。 もっと追記 前の修正に間違いが入っているのをご指摘頂いたので修正しました。 5自体は素数なので、巻き添えで除外してはいけません。 #!/usr/bin/env perl use strict; use warnings; use feature qw/say state/; use List::MoreUtils qw/all none/; sub is_prime($) { state %memos; my $n = shift; return 0 if $n < 2; return 1 if $n == 2; return 1 if $n == 3; return $memos{$n} if exists $memos{$n}; $memos{$n} = none { $n % $_ == 0 } 2 .. sqrt $n; } sub rotate($) { my $n = shift; substr($n, 1) . substr($n, 0, 1); } sub rotations($) { my $n = shift; my %seen = ($n => 1); $seen{$n} = 1 until exists $seen{$n = rotate $n}; keys %seen; } sub is_circular_prime($) { state %memos; my $n = shift; return 0 if $n =~ /[024568]/ and $n != 2 and $n != 5; return $memos{$n} if exists $memos{$n}; my ...
4 件のコメント
続きを読む

救急外来にかかったときの記録

子どもの頃にかかった記憶はあるが自分で行ったことはなかったのでメモしておく。 先日怪我をした。より具体的に云うとランニング中に転倒し顎を地面に叩きつけた。深夜の12時ごろの話である。 その時点ては両手の擦傷が痛いとか下顎の間接が痛いとか奥歯のセラミックが割れなくて幸いだったといった程度だが、マスクを外して見るとなにやら下部に血がついている。 顎にも擦傷があるのかとうんざりしながら歩いて帰り、血の滲んだマスクを捨てて傷口を洗おうとしたところで皮膚が割けて肉が見えているのに気付いた。 一瞬顔が青くなったが単身なので倒れるわけにはいかない。幸い血は固まっていてそれほど出血していないし、先程まで運動していたからかあまり痛みもない。 この時点で明白な選択肢は3つあった。即ち: 救急車を呼ぶ 自力で病院へ行き救急外来を受診する 応急処置して朝になったら近場の医院を受診する である。まず 3 は精神的に無理だと悟った。血も完全には止まっていないし、痛みだしたら冷静に行動できなくなるだろう。 1 はいつでも可能だったが、意識明瞭で移動にも支障がない状態では憚られた。救急車が受け入れ先病院を探すのにも時間がかかると聞く。 結局とりあえず 1 をバックアップ案とし、2 の自分で連絡して病院へ向かうことにした。まずは病院探しである。このときだいたい 00:30 AM。 最初に連絡したのは最寄りの都立病院の ER だった。ここならタクシーで10分もかからない、のだが、なんと ER が現在休止しているとの回答だった。そんなことがあるのかと驚愕したがどうしようもない。 近場に形成外科の救急外来の開いている病院はないか尋ねたところ 消防庁の相談センター の電話番号を案内された。 ここで4つの病院を紹介された。余談だが相談の対応は人間だが番号の案内は自動音声に切り替わるので録音の用意をした方が良い (一応2回くり返してくれる。) いずれも若干遠くタクシーで2、30分かかるが仕方がない。最初に連絡した最寄りの病院はその日形成外科の当直医師がいなかった。二件目でトリアージの質問をされ、受け入れ可能とのことだったので受診先が決定。このとき 00:45 AM。 診察時に脱ぎ易い服に着替え (このときまでランニングウェアだった)、健康保険証を持って病院へ向かう。ガーゼがないのでマス...
コメントを投稿
続きを読む

Perl 5 to 6 - コンテキスト

2011-02-27: コメント欄で既に改訂された仕様の指摘がありました ので一部補足しました。 id:uasi に感謝します。 これはMoritz Lenz氏のWebサイト Perlgeek.de で公開されているブログ記事 "Perl 5 to 6" Lesson 06 - Contexts の日本語訳です。 原文は 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 06 - コンテキスト SYNOPSIS my @a = <a b c> my $x = @a; say $x[2]; # c say (~2).WHAT # Str() say +@a; # 3 if @a < 10 { say "short array"; } DESCRIPTION 次のように書いたとき、 $x = @a Perl5では $x は @a より少ない情報—— @a の要素数だけ——しか持ちません。 すべての情報を保存しておくためには明示的にリファレンスを取る必要があります: $x = \@a Perl6ではこれらは反対になります: デフォルトでは何も失うことなく、スカラ変数は配列を単に格納します。 これは一般要素コンテキスト(Perl5で scalar と呼ばれていたもの)及びより特化された数値、整数、文字列コンテキストの導入によって可能となりました。無効コンテキストとリストコンテキストは変更されていません。 特別な構文でコンテキストを強制できます。 構文 コンテキスト ~stuff 文字列 ?stuff 真理値 +stuff ...
2 件のコメント
続きを読む

Perl 5.42 が出たので perldelta を読んだ

去る2025年7月2日に Perl 5.42 がリリースされた。ので例によって perldelta を一通り眺めた。 このバージョンは実験的機能である組込みのクラス構文の実装が進展した。 他にもパフォーマンスの改良、組み込み関数・演算子・C レベル API の追加、多数のバグ修正があるが劇的な変化ではなく、発見・修正された脆弱性もかなり限定的な問題なので刺さる機能がなければ急いで移行する必要はあまりないように思われる。 以下主だった新機能の抜粋。 source::encoding プラグマ ソースコードが特定の文字エンコーディングで記述されていることを宣言するプラグマ。サポートされているエンコーディングは ASCII と UTF-8 のみである。 use source::encoding 'ascii' が宣言された字句的スコープにおいて非 ASCII 文字を記述するとコンパイル時エラーが発生するようになる。 use source::encoding 'utf8' は単に use utf8 のシノニムである。 Perl 5 は 2000 年にリリースされたバージョン 5.6 から UTF-8 によるソースコード記述をサポートしているが、後方互換性のため既定では ASCII を前提としており、 utf8 プラグマを使わない限り文字列リテラルや RegExp リテラルはバイト列として解釈されるし、識別子にも英数字および '_' しか使うことができない。 識別子はともかく「リテラルは既定でバイト列である」という意味論は極めて誤用しやすい。Unicode 文字列のつもりで渡した値が意図せずバイト列であったために実行時警告・エラーを得た経験は非英語圏のプログラマなら一度ならずあるだろう。 このプラグマはそのような初歩的なバグをコンパイル時に検出することで、Perl プログラムの最も頻出するエラーの一つを実質的に解消しようとしている。 ちなみに use v5.42 すると自動で use source::encoding 'ascii' も有効になるので、今まさに警告を吐いているようなアプリケーションをアップグレードする際は注意が必要である。 any / all 演算子 実験的...
コメントを投稿
続きを読む

js_of_ocaml の使い方

js_of_ocaml (jsoo) は Ocsigen が提供しているコンパイラである。その名の通り OCaml バイトコードから JavaScript コードを生成する。 これを使うことで OCaml で書いたプログラムを Web ブラウザや node.js で実行することができる。 インストール 単に OPAM を使えば良い: $ opam install js_of_ocaml js_of_ocaml-ocamlbuild js_of_ocaml-ppx バージョン 3.0 から OPAM パッケージが分割されたので、必要なライブラリやプリプロセッサは個別にインストールする必要がある。 とりあえず使うだけなら js_of_ocaml と js_of_ocaml-ppx の二つで十分。後述するように OCamlBuild でアプリケーションをビルドするなら js_of_ocaml-ocamlbuild も入れると良い。 これで js_of_ocaml コマンドがインストールされ、OCamlFind に js_of_ocaml 及びサブパッケージが登録される。 コンパイルの仕方 以下ソースファイル名は app.ml とし、ワーキングディレクトリにあるものとする。 手動でやる場合 一番安直な方法は、直接 js_of_ocaml コマンドを実行することである: $ # バイトコードにコンパイルする。js_of_ocaml.ppx は JavaScript オブジェクトの作成や操作の構文糖衣を使う場合に必要 $ ocamlfind ocamlc -package js_of_ocaml,js_of_ocaml.ppx -linkpkg -o app.byte app.ml $ # 得られたバイトコードを JavaScript にコンパイルする $ js_of_ocaml -o app.js app.byte OCamlBuild を使う場合 OCamlBuild を使う場合、.js 用のビルドルールを定義したディスパッチャが付属しているので myocamlbuild.ml でこれを使う: let () = Ocamlbuild_plugin . dispatch Ocamlbuild_js_of_ocaml . dispatcher $ # app.ml -...
コメントを投稿
続きを読む