top recent

FP:LazyEvaluation

関連ページ

FP

目次

  1. Lazy Evaluation...
  2. 遅延評価とパイプ...
  3. もう一箇所引用...
  4. いや、Threadとかは関係ないと思います。...
  5. 遅延評価について...
  6. 遅延評価もまたFPの専売ではない、ということで(^^;。...
  7. うーん...
  8. Lazy であることのメリット...
  9. 実際の処理系は...
  10. 擬リストと無限リスト...
  11. delayとmacro...

Lazy Evaluation

評価の遅延機構

１．call by need
値が必要になったときはじめて評価が行なわれる機構。
評価の順序によって結果が変わるような副作用をもたない非正格純粋関数型言語が採用している。

２．call by name
〔空欄を埋めよ〕（ぉ

[[id:1289]] 2002-09-24 18:54:24

遅延評価とパイプ

数メガバイトにおよぶログファイルを cut して grep して sort して uniq -c しようと思うと、DOS ではいちいち中間ファイルが作られるうえにひとつひとつのコマンドが終らないと次のコマンドをはじめることができないという、時間的にもスペース的にも非常な無駄が生じてしまうが、真のパイプをサポートしてくれる OS でこれを実行すると、中間ファイルは必要ないし処理もできたものから次に渡されるため早い。

また単にシェルから一行野郎で、
% perl -e 'for ($i=0;;$i++) {print "$i\n";}' | less

とやると、一瞬にして less が起動し、 0 から始まるテキストの列を(仮想記憶の許すかぎり)ブラウズし続けることができる。

パイプという機構が調停してくれるおかげで、各コマンドは相手が吐き出し続けるデータを自分のペースで入手し処理することができる。プログラマは単に "read()", "write()" と書き、ユーザーは更に簡単に "|" と書くだけだ。
（苦労したのはカーネルの担当者？）

Lazyな評価を行う処理系の持つ記述力の高さも、それに通じるものがあるような気がする。

[[id:944]] 2002-08-15 16:29:08

もう一箇所引用

なぜ関数プログラミングは重要か(FP) から
『この論文では、モジュール性がプログラミング成功の鍵であることを主張した。生産性の向上を目的とした言語はモジュラプログラミングをよくよくサポートしなければならない。しかし、新しいスコープ規則や分割コンパイルの機能では不十分である。モジュール性はモジュール以上の意味がある。問題を部分に分解する能力は解を貼り合せる能力に直接に依存している。モジュラプログラミングを支援するには、言語は良い糊を用意しなければならない。

関数型プログラミング言語は二つの新しいタイプの糊を供給する。すなわち、高階関数と遅延評価である。これらの糊を用いて新しいわくわくするような方法でプログラムを簡単にモジュール化できる。その例をいくつも示した。より小さく、より汎用的なモジュールは、その後のプログラミングでより広く再利用することができる。このことは、なぜ関数プログラムが従来のものよりもずっと簡単に小さく書けることの説明になる。そして、関数プログラマが狙うべき目標を用意することになる。もしプログラムの部分のどこかがごちゃごちゃで複雑なものであるなら、プログラマはそれをモジュール化し、その部品を汎用化しなければならない。これを実現するためのツールとして高階関数と遅延評価が使えることを期待するはずだ。』

----
ここでいっている遅延評価のもつ効能は、手続き型言語だとコルーチンやスレッドなどを使わないと実現できないような仕組みを自然に（静的に＝わずか数行の式として）記述できるってことじゃないだろうか。
- Y Combinator (λ算法) 参照。

[[id:939]] 2002-08-12 14:07:50

いや、Threadとかは関係ないと思います。

遅延評価もまたFPの専売ではない、ということで(^^;。(#6) に書いたようにOOP(Threadを前提とせず)でも普通にやれることだし。-戯

「糊」ってのがこの文の味噌だと思います。モジュール「分割」だけじゃなく「合体」も楽に出来る仕組みが必要だ
という主張だと思うのです。さもないと分割は出来ても統治(どこかでまとめる)が困難だという。
----
関数Aから呼ばれる関数Bは、OnDemandでPassiveな他人(A)のペースで動く、ということかと。
それはSingleThreadな手続き言語でも一般的な"関数呼び出し"のやり方であって、珍しくない。

あとは関数(や手続き)を他の関数に渡せるかどうかですが、単にその問題だけならCでも解決済みです。
これが「糊」の1つ目の性質。
----
あとは、FPでは、関数そのものを「その場で」作れるってのが大きいんじゃないかな。
手続きブロックという意味では非FP言語でもそれをサポートしてるものは多いかも知れませんが、
関数インスタンス(つまり状態すら抱えられる)を作れたり、引数の数自体もいじれる
(自由変数とかの話を見てると、こっちの語彙(^^;では、「ある関数から、デフォルト引数つきVersionの関数を、導出」
してるかのように見えます。)とか。

つまり、他の関数との「親和性」を、Cの関数宣言なんかより遥かに柔軟性と適時性が高い形で、操作できる。
そういうあたりがFPの糊の2つ目の性質だと思えます。
----
で、こう考えると、手続きObjectを(実行時に)作れるようなOOP言語だと、同じことが出来るよなあ、という話になるのは、
なるほど当然かも(^^;。あとは記述がきれいに出来るかとか、余計な機能が抱き合わせ(^^;になってないかとか、そいう面だけ。

[[id:1287]] 2002-09-24 18:33:14

遅延評価について

Re: もう一箇所引用(#3)
> いや、Threadとかは関係ないと思います。遅延評価もまたFPの専売ではない、ということで(^^;。(#6) に書いたようにOOP(Threadを前提とせず)でも普通にやれることだし。-戯
> 関数Aから呼ばれる関数Bは、OnDemandでPassiveな他人(A)のペースで動く、ということかと。それはSingleThreadな手続き言語でも一般的な"関数呼び出し"のやり方であって、珍しくない。

引用元の本文を読めば分かりますが、違います。--SHIMADA
-そうなの？少なくとも「読んだ」けど「判らなかった(そうは捉えられなかった)」ですが…

- 数ヵ所出て来ますが、下記のような部分です。--SHIMADA
『…さらに重要なことは、遅延評価によりevaluateを上のようにモジュール化できるということである。gametreeは潜在的に無限の結果をもつので、このプログラムは遅延評価でなければ停止しないことになる。遅延評価がなければ、
prune 5 . gametree
と書く代りに、この二つの関数を一つに畳み込んで当該ツリーの最初の五つのリーフだけを構築するようにする必要があるだろう。
:
:
この効率のよさは、 maximise(合成の鎖の最後にある関数)と gametree(合成の鎖の最初にある関数)との相互作用に依存するものであるから、遅延評価なしで実現するなら鎖のなかの関数全てを一つの大きな関数に畳み込まなければならない。これは激烈なモジュール性の低下であるが、日常に起っていることである。…』

-そうじゃなく、「遅延評価」と「Threadとか」とは無関係、じゃないかという話をしたかったのですが。遅延評価の必要の有無に言及した積もりは無く。-戯
--で、たしかに生Cじゃ足りない面も有りますが、それについては別Paragraphにて。>>遅延評価とパイプ(#2)

[[id:973]] 2002-08-12 21:40:17

遅延評価もまたFPの専売ではない、ということで(^^;。

→ これってパイプラインモデルだ! (ポーランド記法モドキの言語) 参照

こういうのは分野によってはStreamと呼びますね。あとRDB用語だとFetchかな。
OOP屋がStreamに出会うと、何(どのStreamObject)「から」読み書き出来るのだろうか？という捉え方をします。要するにObjectに蛇口がついていれば良いわけで。

-あの言語の仕様案のなかに評価の遅延機構はまったく含まれていません。パラメータ渡しと値返しが対称的にが多値になっているだけです。念のため。--SHIMADA

----
Unixコマンドにおける遅延評価ですが、標準入出力はそうなるんですが、困るのがコマンド引数が遅延評価できないこと。
-xargs や``やechoを使うことで、標準入出力と引数とは、相互乗り入れが出来る。(にも関わらず上記の非互換性が有るので、厄介。)
-いっそ引数を無くしてしまったらどうだろう。shellに引数ならぬ標準入出力の編集機能(^^;;が有れば済むのでは？

----
Streamは比喩のためにひきあいに出しただけです。(^^;
遅延評価というのは例えば、１万個の値を計算して長さ１万のリストにして返す関数を呼び出しても、呼び出し元で受け取ったリストの最初の５個しかアクセスしなければ、５個のケースしか実際に計算が起こらず、計算機のリソースもその分しか消費されない、というような機構のことです。--SHIMADA
- (補足) 評価の遅延は関数コールの単位で行われるので、長さ１万のリストを計算するのに再帰などを使っていることが前提なはず、です。--SHIMADA

----
というよりむしろ、Streamが「有れば」遅延評価を実現できる、という感じじゃないですかね。
入出力をStreamに依存するように「すれば」いいんじゃないかと。出力はキュー(?)が空きにならない限り「詰まって」しまって、そのせいで処理が先に進まない、という仕組みに「なっていれば」いいわけで。
-言い換えれば、遅延評価なるものの仕組みの正体はStreamである、と。
-出力Streamを関数から関数へ「引き渡す」ということは、普通に行われるわけですし。
-- 手続き型ではコルーチンやマルチスレッドなどの特別の仕組みを使わなければ実現できないような処理というのはそれのことです。送り手と受け手が別のコンテキストで並行に走っていなければそういう処理は書けません。--SHIMADA
--- うーん。OOPはどう位置付けりゃいいんでしょ？OOPならコンテキスト(のように見えるもの)もObject「として」ポポイノポイだし。しかしアレがコルーチンとかほどの大げさなものにも見えないし。
---「走る」必要が無いってのがね。古典的(?)手続き指向ではコンテキスト(の役をするもの)が「走る」の副作用でしか作る/使うことが出来ないけど…
- Parlog，GHC，KL/1 あたりのどれかを使ったことあると，感覚的にわかるかも．unification が起こらない限り変数は変数のまま受渡されていく....

-で、どうやらFPでは、引数が最初から「Stream渡し」になっているということらしい、と。
-- そんな新語を発明しなくても、「call by need」という言葉があるから使ってやって下さい。--SHIMADA
-- っていうか，たとえば ML は strict だし．関数型であるのと lazy であることは独立です．
-- SICP-3.5 を読むと、遅延評価をつかったStreamという技法もあるにはあるのですが、上のは勘違いが偶然一致しているのかも。

[[id:1288]] 2002-09-24 18:44:09

うーん

Re: 遅延評価もまたFPの専売ではない、ということで(^^;。(#6)
> というよりむしろ、Streamが「有れば」遅延評価を実現できる、という感じじゃないですかね。入出力をStreamに依存するように「すれば」いいんじゃないかと。出力はキュー(?)が空きにならない限り「詰まって」しまって、そのせいで処理が先に進まない、という仕組みに「なっていれば」いいわけで。

OOPでそういうことをするにはどういうオブジェクトを使うんでしょう。僕のイメージでは一通り計算が終らないとそもそも呼び出し元には返って来ないような気がするんですが。
もしかして呼び出される側が自分で「状態を保存しておいて１ステップだけ計算して返す」という仕組みを「書けば」できる、という意味？

----
今朝起きたら気づきました(ぉ)が、Callbackとゴッチャになってたようです。撤回。-戯

でも、ここでいう「1ステップ」は、結局OOPでは(1回の)メソッド呼び出しに相当するんですよね。
-1:ClientがStreamに出力を要求する
-2:StreamがFunc(?)Objectの該当Methodを呼ぶ
-3:Funcは「1ステップ分の」計算をして(ここで、これといった仕掛けが必要なわけでもない)、答えをStreamに返す。
--計算の副作用(?)として、Funcはステップの進行を自分で記憶しておく
-4:StreamはClientに答えを返す(等)

「計算が終わる」と「呼び出し元にReturnしてくる」のとは、同じなんでしょうか？
同じであるベキだと考えて、その世界観に対して邪魔となる部分を隠蔽したら、FPになった、という感じ？(結果返し指向、とでもいうか…)

[[id:974]] 2002-09-24 18:30:18

Lazy であることのメリット

Re: うーん(#7)
1〜4 にあるようなことを1サイクルとしてそれを必要回数ループしてやっとすべての計算が求まるのより(これで数行〜十数行消費しますよね)

some_function( arg )

と一回関数を呼び出せばいいだけというほうが楽だし簡潔だ、ということです。
----
Streamと言っているのはきっと(外部)イテレータだと思うんですが、メソッド呼び出しに対して巨大なコレクションを返すのが空間的にも時間的にも効率悪いのでイテレータというパターンが考案されたと思うんです。
それがメソッドが巨大なコレクションをそのままぽんと渡しても(巨大どころか無限大だったとしても)、時間も空間も必要な分しか喰わずに済む、というのが遅延評価のよいところです。
結果としてイテレータを構成するために書かれるべきコードがまるまる必要無くなる、という利点があります。コードの量が減るです。
もちろんそうした利点を受けられるのは再帰的な式で計算できるものに限るとは思いますが。
# SHIMADA

[[id:1291]] 2002-09-24 22:33:49

実際の処理系は

Haskellみたいな遅延評価を言語機能として持っている言語は、OOPLか関数型言語かどうかに限らずあまりないのではないでしょうか。
（よく知らないですけど。）
遅延評価をエミュレートするオブジェクト、とか作れるかなぁ。

SHIMADAさんがパイプに期待しているものは、遅延評価と言うよりは、
関数抽象と適用のかわりに関数合成を主体にしたPN系関数型言語
という辺りではないかと愚考いたします。
寄り道してFPについて調べていますが (ポーランド記法モドキの言語)
もうちょっと考えがまとまったら (ポーランド記法モドキの言語)
というか書いてありますね。↑
パイプを使うことで引数に変数を割り当てなくても良い。
→いつでもどこでもカリー化した形で記述できる。
‥‥つーことではないかと。

あまり主題と関係ない感想なのでsage(?)
- ばしを
----
あんまりないみたいですね。

> 遅延評価をエミュレートするオブジェクト、とか作れるかなぁ。

Schemeのdelayのように部分的・明示的に遅延させるだけなら、式を評価せずにクロージャに入れてしまうことで可能ですよ。
遅延評価による無限リスト (FP:inRuby) のRubyの例では、引数に渡す代わりにブロックをくっつけるという不細工なやりかたで誤魔化していますが、引数を評価せずに扱えるLispのmacroとか、ワード自身が自力でパースできるForthならもっときれいに書けると思います。

#SHIMADA

----

儀リスト(リストのようでリストじゃない？)、無限リスト(Listの要素数が無限)をプログラムに使うとき遅延実行が強力な武器になることは間違いないことです。しかしStreamと遅延実行は関係ないと思います。

後、Lispのmacroは事前実行なのでちがうのでは？delayの間違い？私が間違っている？

Standard ML(Meta Language)の遅延実行は良い作りに成っているとおもいます。

----
「Lispのmacro」というのはこんな使い方を想定していたのでは：

(define-macro (lcons a b)
`(delay (cons (delay ,a) (delay ,b))))

こうすると、

(lcons (foo x) (bar y))

と書いとけば普通の関数のように見えるにもかかわらず、fooやbarの呼び出しは実際にその値が必要とされるまで起きないと。 --Schemer

----
すみませーん。このパラグラフは整理のために うーん(#7) から切り出したものなんです。前後関係からいうと delayとmacro (#11) に続いてます。--SHIMADA

[[id:1286]] 2002-09-25 01:39:37

擬リストと無限リスト

擬リスト
1:2:3:⊥
-次の値が求まらない＝条件に当てはまる値が存在しない

無限リスト
1:2:3:.....
-無限に続く＝停止条件がない

[[id:988]] 2002-08-15 18:18:05

delayとmacro

Re: うーん(#7)
> 後、Lispのmacroは事前実行なのでちがうのでは？delayの間違い？私が間違っている？

SICPの delay の説明で、delayの実装としてナイーブなものは
(delay <a>) ==> (lambda () <a>)
となるようなシンタックスシュガーである、とありましたので、
(defmacro delay (body)
`(lambda () ,body))
でいいんじゃないでしょうか。--SHIMADA
-(補足) xyzzy などのCommon Lispでは (defmacro delay (body) `(function (lambda () ,body))) ですね。--SHIMADA

force は、
(defun force (promise) (funcall promise))
かな。
----
あと、Standard ML の遅延実行の仕組みってまだよく知らないのですが、どんなものですか？
さわりだけでも教えて頂ければ幸いです。 -- プログラミング言語Standard ML入門 (本棚)持ってるのに読了してないSHIMADA

-プログラミング言語Standard ML入門 (本棚)の本のp103の「7.6 無限なデータ構造の定義と利用」を呼んでください。この遅延実行の構造を見てもMLが実用的な言語ということが判ると思います。
-読みました。SICPのSchemeの例とほとんど同じですね。しかし関数式を直接書くのもありなんだ…。シンタックスシュガーで隠蔽しなきゃと思い込んでました。(^^; --SHIMADA

[[id:976]] 2002-08-15 22:24:25

top recent

HashedWiki version 3 beta
SHIMADA Keiki