Document

作用型計算とその並列処理
米澤明憲
２００７ fall
式の参照透明性
•
•
作用型の式は値を表示(denote)するもので、値の計算の方法
を指定しているものではない。
作用型の言語（ラムダ計算、ML,Scheme,….）おける式、また
はその部分式は、参照透明性(referential transparency)を持
つ。
– 式の値は、その式に現れる部分式の値のみ依存す
 合成性(compositionality) をもつ  複雑系でない！！
– 同じ形(字面）を持つ式は、常に同じ値を持つ
– 系：同じ変数は常に同じ値を持つ  単一代入型言語
(single assignment)
– 式は同じ値を持つ別の式で置き換えても、全体の値は変わ
らない。
Program
x
x
どのxも同
x
じ値を持つ
参照透明性をもたない式・言語
• 命令型の言語(C, Fortran, Java, Pascal...)
–
x := x + 1 における x には参照透明性はない。
• ある種に様相論理：
P、 Q
– E.g., Pという述語が示す命題を「知っている」という様相
命題をknow(P)という記法で表する。
するとknow(１＝１) が真であるからといって、
参照透明性を用いてknow(明けの明星＝金星)
が真であることは証明できない。なぜなら、
１=１は真、かつ明けの明星＝金星も真、真である後者の
命題をknow(…)の中に持ちこくと、必ずしも正しくない。
式のLazy/Eager Evaluation法
•
•
•
•
•
Lazy評価＝式の部分や関数の引数を実際に必要に
なるまで、できるだけ評価しない。(逆がeager評価）
Lazy評価Outermost/normal order reduction in λ計算
Lazy評価のほうが評価力が強い：
first(x,y) = x, loop = tail loop
answer = first(42, loop)  42 ｂｙ lazy評価
 未定義 by non-lazy評価
Strict関数：引数の一つでも未定義になると未定義！
Strict Analysis: 関数がstrictかどうか定義プログラム
を解析する。
クロージャの静的・動的束縛
• 関数 F x y = <body… x … z …x …y ..> 環境
• Fのクロージャ [F x y = <body… x … z …x …y ..>, ε]
z=6
z=4
F x y = < ..x.. y..z…>
F x y = < ..x.. y..z…>
z=8
F 2 3 => ##
zを６としてFを評価す
るのが静的評価
F 2 3 => ??
zを8としてFを評価
するのが動的評価
どの時点の環境を埋め込んだクロージャ
を用いて関数を評価するかの違い
遅延評価法(Delayed Evaluation)
• 関数評価の際に、指定された引数の評価を
遅延して、その引数値が必要になるまで評
価しない、ことを遅延評価と呼ぶ。
• 目的：不必要な評価を避ける。
• 記法：例えば, del 記法で遅延評価する引
数で指定に付す。
f (g a) (del (h a))
• 実現法： del (h a) を評価するときhのクロー
ジャを評価値とする。
call-by-name と call-by-need
• call-by-nameは全ての関数呼び出しにおい
てその全ての実引数が遅延評価される。
• call-by-needは一度評価した実引数の値は、
記録しておき、(call-by-nameにおいて）再
び本体現れた実引数の評価は、記録した
値しかしない。
無限リスト・・・遅延評価の応用
• int-list n = [n] ++ (int-list n+1)
例えばint-list[10]をeager評価すれば、直ぐ発散！そこで、
•
d-int-list n = [n] ++ del (d-int-list n+1)
とすると、必要なだけ長い整数のリストが得られる。実際、
• (d-int-list 1) ! 100  100
• (d-int-list 1) ! 1000  1000
となるはず。
“Cons should not evaluate its args”.
• LISP, Scheme等にある関数 cons e1 e2 の
定義をはじめから con (del e1) (del e2) とみ
なして実装すると、無限リストが扱える言語
ができる。
• 一般にデータ構造を新たに作る操作の実引
数の評価をすべて遅延評価にすると約束し
ておくと、他の言語でも同様なことが可能に
なる。これによって、無限に大きいデータ構
造が扱える。
• 課題： Schemeのinterpreterを改造し、無限リ
ストが扱えるようにせよ。
作用型表現における並列処理
1.
2.
3.
4.
5.
全ての引数を並列に評価
Future構文を使う
データフローによる並列処理
ペトリネット
通信するプロセスにネットワーク
future構文-1•
•
•
•
•
作用型言語に並列処理構文を導入する一例
遅延評価の代りに並列評価: del からfutureへ
cons (future (f a)) b において future (f a) の
評価値として即座にトークンを一つ発行する
と同時に新しいプロセスを作り (f a) ,の評価を
開始させる。
(f a)の値が必要になり、かつまだ計算が終了
していなければ、必要とするプロセスは待機
状態にはいる。
(f a)の値が得られると、トークンとその値をす
りかえ、待機していたプロセスは再開する。
future構文２
let x = cons (future e1) e2
in
let y = (future e)
in
.
.
(f y)
car x
.
end
アクセスするプ
ロセスは待機状
態に入る。
end
課題：Schemeにfuture機能を導入する実装せよ。
データフロー(Data Flow)計算モデル
•
•
•
•
1973, MIT のJ. Dennisによる。
プログラムは命令（インストラクション）の集合
各命令には入力データ（群）と出力データ（群）
命令は入力データ群がすべて揃うと発火・実行
• 入力データ群と出力データ群は結合し、リンクをなし、命令群は
ノードとなって、全体としてグラフ構造をなす。
• 関数型の言語から、データフローグラフに変換されて実行する
ことを想定されている。
ペトリネットモデル
• データフローにおいて、データでなくトークンが流
れると見なすとわかりやすい。（歴史的にはデー
タフローより古い。1960年台ドイツのPetriが使い
はじめる。）
• データの流れより、命令・行動群の同期の表現・
解析に適している（使われことがある）。
• 有限・有向グラフで表現されサイクルがあってよ
い。
• グラフのノードは2種類：
1. place －－条件に対応し
で表現。
2. transition －－事象に対応し
で表現



グラフ上の任意のパス上にはplaceとtransitionが必ず交互
の出現する。
系内のPlace上にどのようにトークンが配置されているかであ
系（システム）の状態をあらわす。
発火条件：１つのtransitionの入力側アークにつながるす
べてのplacesにトークンが存在するとき、そのtransitionは発
火し、入力側のplacesにある全てのトークンは、出力側の全
てのplacesに流れでる。
P-op開始
P-op終了
V-op開始
V-op終了
Semaphorによる同期
（有限長バッファの同期記述）
Non-empty ⊃buffer
contains empty slots
Producer ready
Consumer ready
S1
M
Buffer slot
allocated
Message placed
in buffer slot
S2
Message removed
from buffer slot
Buffer slot
returned
Non-empty ⊂buffer
contains messages
2.2 Petri Net solution to the Message Buffer Problem
Network of communicating processes
-- stream-based programming -☆ cons の arg は全て lazy evaluation すると仮定
addl x = ((car x) + 1) : addl(cdr( x))
x : list
(addl(x) ≡ cons(car(x) + 1, addl(cdr(x))))
“:”はcons operation
x = [e1, e2, e3…….]
addl x = [e1+l, e2+l, e3+l……]
☆ integers = l : (addl integers)
l
integers
[1,2,3…]
cons
add1
x
→はstream,
はprocessと考えられる
y
cons(x.y)
このnetworkの動作は次の２つの解釈ができる。
① demand mode / demand-driven (要求駆動型)
② availability mode / data-driven （データ駆動型）
① lazy evaluation に対応
“integers”の場合 : integer ~ output stream から要求があるとまず、
consが出る。次に要求が来るとconsへ要求がゆき、これによって
add1に要求が届き、から分かれた1がadd1への要求に応じて流れ
出る。
◎このようなdemand-droverはData-flow graphの解釈に適用して
もよい。 <“coroutine”とも解釈できる>
②addlもconsもindependentなプロセスでinputがあれば、どんどん
値を生成し考える。
addlist x y = ((hd x) + (hd y)); (addlist + (tl x)(tl y))
(addlist(x, y) ≡ cons(car(x) + car(y), addlist(cdr(x), cdr(y)))
Hamming Problem
次のような性質を満たす数列を作り出す。
① 1はその列に入っている。
② もしxが列の中にあれば、その2x,3x,5xも列の中に入っている。
③ ① ②以外の数は入っていない。
④ 大きさの順になっている。(ascending order)
これのためにmerger(x,y)を定義する。但しx,yｔもに無限listの必要あり。
sums = 1 : (addlist integers sums)
integers
addlist
1
merger x y = if (car x) = (car y)
then merger (car x) y
else if (car x) < (car y)
then (car x) : (merger (cdr x) y)
else (car y) : (merger x (cdr y))
sums
Merger
x3
merger
x2
x5
Hamming 問題の解法
l
cons
エラトセネス(Eratosthenes)のふるい
* non trivial, 自明でない、なぜなら自分自身のcopyがnestingする。
* プロセスネットワークの図にかけない。
基本的方法
(1) 2よりはじまるintegersのlist : integer-from-2を用意
(2) integerのリストに対して小さい方から順にみてゆく。最初のマーク
されていない要素は素数である。それをpと呼ぶ。
(3) それ以降のp番目ごとの数をマークする。(既にマークがあれば、無
視して)
(4) (2)へ戻る
filter(p,y) ≡ if(car (y) rem p) = 0
但しyはlist of int
then filter(p,cdr(y))
else cons(car(y), filter(p,cdr(y)))
Eratothenes篩
primes = sieve(integer-from-2)
sieve (x ) = cons(car(x), sieve(filter((car x), cdr(x)))
car(x)
x
cdr(x)
filter
car
integer-from-2
cdr
sieve
primes

Download Report