![リ の単一化
スト
?
リ
スト
任意の長さ
を持つデータ
構造
? ex) [1, 2, 3] [] [H|T]
?
?
リ の単一化
スト
長さ
が同じ スト
リ は単一化でき
る
? 同じ
位置の要素同士が単一化さ
れる
?
[1, 2, 3] = [X, Y, Z]
Xは1,Yは2,Zは3
[A, 2, 3] = [1, B|C]
Aは1,Bは2,Cは[3]](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-6-320.jpg)
![ジェネレータ
?
From～Toまでの数列 (リ ) を生成
スト
gen(From, To, X) :- From =< To |
X = [From|Xs],
Next is From + 1,
gen(Next, To, Xs).
gen(From, To, X) :- From > To |
X = [].](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-36-320.jpg)
![ジェネレータ
gen(1, 2, X)
gen(2, 2, X)
X = [1 | Xs]
X = [2 | Xs]
gen(3, 2, X)
結果
X = []
X = [1, 2]](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-37-320.jpg)
![フィ
ルタ
?
入力リ の要素を2倍にし スト
スト
たリ を出力
twice([X|Xs], Y) :- true |
Y1 is X * 2,
Y = [Y1|Ys],
twice(Xs, Ys).
twice([], Y) :- true |
Y = [].](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-38-320.jpg)
![フィ
ルタ
twice([1,2], Y)
Y = [2 | Ys]
twice([2], Y)
Y = [4 | Ys]
twice([], Y)
Y = []
結果
Y = [2, 4]](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-39-320.jpg)
![パイ
プ&フィ
ルタ
X = [1 | Xs]
gen(1, 2, X)
Y = [2 | Ys]
twice(X, Y)
X = [2 | Xs]
gen(2, 2, X)
Y = [4 | Ys]
twice(X, Y)
X = []
gen(3, 2, X)
Y = []
twice(X, Y)
X = [1, 2]
結果
Y = [2, 4]](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-41-320.jpg)
![動的なプロ
セスネッ ワーク
ト
?
エラ テネスのふる
スト
いによ 素数の生成
る
primes(N, J) :- true |
gen(2, N, I), sift(I, J).
sift([P|I], J) :- true |
J = [P|L], filter(I, P, K), sift(K, L).
filter([N|I], P, K) :- N mod P =:= 0 |
filter(I, P, K).
filter([N|I], P, K) :- N mod P =?= 0 |
K =[N|K1], filter(I, P, K1).](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-42-320.jpg)
![ク ッ ソ
イ ク ート
?
並列に適し
たアルゴリ
ズム
quicksort(X, Y) :- true | qsort(X, Y, []).
qsort([X|Xs], Y, Z) :- true |
partition(Xs, X, S, L),
qsort(S, Y, [X|Ys]), qsort(L, Ys, Z).
qsort([], Y, Z) :- true | Y = Z.
partition([H|R], X, S, L) :S = [H|S1], partition(R,
partition([H|R], X, S, L) :L = [H|L1], partition(R,
H =< X |
X, S1, L).
H > X |
X, S, L1).](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-51-320.jpg)
![アク ープロ ミ
タ
グラ ング
pingpong(N) :- true |
ping(N, [hello(X)|_]), pong([X|_]).
ping(N, [hello(Resp)|Msgs]) :- N > 0 |
Resp = [world(Msgs)|_],
N1 is N - 1, ping(N1, Msgs).
ping(0, [hello(Resp)|_]) :- true |
Resp = [].
pong([world(Resp)|Msgs]) :- true |
Resp = [hello(Msgs)|_],
pong(Msgs).
pong([]).](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-56-320.jpg)
![要求駆動
?
必要と れた時に数列を生成
さ
gen(From, [X|Xs]) :true |
X = From,
Next is From + 1
gen(Next, Xs).
gen(_, []).
gen(1, X),
...
X = [N1|X1],
...
X1 = [N2|X2],
...
X2 = [],
...
初期化
N1 = 1
N2 = 2
終了](https://image.slidesharecdn.com/ghc2-131027085228-phpapp01/85/An-Introduction-to-Guarded-Horn-Clauses-57-320.jpg)
An Introduction to Guarded Horn Clauses
- 1. An Introduction to 並行論理型言語GHCの紹介 小林浩一 (koichik) 【 ます】 あり 【 見覚え】
- 4. 変数と 定数 ? 変数 英大文字または_で始まる ? _のみだと 無名変数 ? ex) A, B, Foo ? ? 数値 ? ? ex) 1, 2, 3 文字列(シンボル) 英小文字で始まる またはシングルク オート で囲む ? ex) a, bbb, hoge, 'XYZ' ?
- 5. 単一化 ? A=B 変数Aと 変数Bが「 である こ を示す 同じ 」と ? 値が未定義の変数は一度だけ具体化でき る ? A = B AとBは単一 (どちらも未定義) A = 5 Aと5は単一(Aは5に具体化) Bも5と単一 (Bも5に具体化) B = 5 Bは5と単一 (既に具体化済み)
- 6. リ の単一化 スト ? リ スト 任意の長さ を持つデータ 構造 ? ex) [1, 2, 3] [] [H|T] ? ? リ の単一化 スト 長さ が同じ スト リ は単一化でき る ? 同じ 位置の要素同士が単一化さ れる ? [1, 2, 3] = [X, Y, Z] Xは1,Yは2,Zは3 [A, 2, 3] = [1, B|C] Aは1,Bは2,Cは[3]
- 7. 複合項の単一化 ? 複合項 名前と 数の決まった引数を持つデータ 構造 ? ex) point(10, 20) ? ? 複合項の単一化 名前と 引数の数が同じ 複合項は単一化でき る ? 同じ 位置の引数同士が単一化さ れる ? model(N, M) = model('EbiYuri', 'CanCam')
- 8. Prologプロ ム グラ ? ? 述語の集合 述語 ? ? ホーン節の集合 ホーン節 ヘッ と ド ボディ を持つ (ボディ は省略可) ? ボディ はゴールの集合 ? H :- B1, B2, ???, Bn.
- 9. Prologプロ ムの例 グラ sum(1, 1). sum(N, S) :N1 is N - 1, sum(N1, S2), S is S2 + N. 節1(事実) 述語 節2(規則)
- 10. 実行イ ージ(1) メ 処理系に質問する ?- sum(2, S). 1番目の節 単一化できない sum(1, 1).
- 11. 実行イ ージ(2) メ 処理系に質問する ?- sum(2, S). 2番目の節 単一化できる sum(N, S). Nは2に単一化 SとSは単一化
- 12. 実行イ ージ(3) メ 2番目の節 sum(N, S) :N1 is N - 1, sum(N1, S2), 1番目の節 単一化できる sum(1, 1). N=2 N1は1に単一化 S2は1に単一化
- 13. 実行イ ージ(4) メ 2番目の節 sum(N, S) :- Nは2に単一化 N1 is N - 1, N1は1に単一化 sum(N1, S2), S2は1に単一化 S is S2 + N Sは3に単一化
- 14. 実行イ ージ(5) メ 処理系に質問する ?- sum(2, S). 2番目の節 Sは3に単一化 単一化できる sum(N, S). N=2,S=3
- 15. Prologの逐次性 ? ボディ のゴール ? 記述順に実行する H :- B1, B2, ???, Bn. ? 述語が複数の節を持つ場合 ? 記述順に試行する sum(1, 1). sum(N, S) :-
- 16. Prologまと め ? Prologプロ ムは述語の集合 グラ ? ? ? 述語は節の集合 節は一つのヘッ と ド 任意のボディ を持つ 単一化 ? A=B ? ? ? Aと Bは「 単一である 」 述語の呼び出し 単一化で決まる も 逐次性がある ? ? ボディ のゴールは記述順に実行さ れる 述語の節は記述順に試行さ れる
- 18. GHC概要 ? ? ? Guarded Horn Clausesの略 上田和紀氏が考案 第五世代プロ ジェク ト ? ? 並列推論マシンPIMのOS (PIMOS) の 記述言語KL1の土台と なった Prologがベース ? 逐次性を排除 i.e. Prolog － 逐次性 ?「 Prolog ＋ 並行性」 ではない！ ?
- 19. 逐次性の排除(1) ? ボディ の複数のゴール 並列に実行さ れる ? AND並列 ? H :- B1, B2, ???, Bn. 並列に実行
- 21. AND並列 E = A * B + C * D ex(A, X Y E B, is is is C, D, E) :A * B, C * D, X + Y. 3つのゴールは 並列実行される ex(A, E X Y B, is is is C, D, E) :X + Y, A * B, C * D. 記述順に意味なし 並べ替えても同じ
- 22. OR並列 Out = !In not(0, Out) :Out = 1. not(1, Out) :Out = 0. 2つの節は並列に 単一化を試みる not(1, Out) :Out = 0. not(0, Out) :Out = 1. 記述順に意味なし 並べ替えても同じ
- 23. 曖昧な節 ?- sum(1, S). sum(1, 1). ？ sum(N, S) :どちらの節も 選択可能 N1 is N - 1, sum(N1, S2), S is S2 + N. (これはProlog)
- 24. 非決定性 ? 選択可能な節が複数ある 場合 ? どの節が選択さ れる かは非決定的 Non-determinism ? Non-deterministic OR-parallel ? ? 選択し た節が失敗(偽)し た場合 ? やり ない 直さ Committed Choice ? Don't care non-determinism ?
- 25. ガード (1) H :- G1, G2, …Gm | B1, B2, …Bn. コミット演算子 ヘッド ガード ガード付きホーン節 ボディ
- 26. ガード (2) ? ? ガード が真と 節のみ選択さ なる れる 複数の節のガード が真と 場合は？ なる ? 一つの節だけが選択さ れる ? ? 選択は非決定的 ? ? ボディ が実行さ れる 節は一つだけ 節が排他的になる う よ ガード を書く べき Falt GHC ? ? ガード ゴールでは一部の組み込み述語し か 利用でき ないGHCのサブセッ ト KL1のベース
- 27. ガード (3) ?- sum(1, S). sum(1, S) :- true | S = 1. 1番目の節が選択 (記述順に依存しない) sum(N, S) :- N>1 | N1 is N - 1, sum(N1, S2), S is S2 + N.
- 28. AND並列の同期 sum2(N, S) :sum(N, N1), sum(N1, S). 2つのゴールは並列に 実行していいが… sum2(N, S) AND並列 sum(N1, S) sum(N, N1) 依存関係
- 29. OR並列の同期 sum(1, S) :- true | ... sum(N, S) :- N>1 | ... 2つの節は並列に 試行していいが… sum(N1, S) OR並列 sum(N, S) sum(1, S) 不確定
- 30. GHCの同期メ カニズム ? ガード る によ 同期 ? ガード は呼び出し 側の変数を具体化でき ない ボディ では可能 ? 自分の変数は具体化でき る ? ? ガード の実行に必要な変数が具体化さ れる まで 待機 (同期化) する 「 単一化でき 」 単一化でき る or「 ない」 が確定する まで 待機 (サスペンド する ) ? 他の節が選択さ れる まで待機 (サスペンド する ) ?
- 31. GHCの同期(1) N1は具体化 されてない sum(N1, S) OR並列 sum(1, S) :- true | ... 呼び出し側の N1を具体化 できない sum(N, S) :- N>1 | ... N1が具体化 されるまで 待機 N(=N1)が具体化 されないと 評価できない
- 32. GHCの同期(2) N1 = 2 sum(N1, S) OR並列 sum(1, S) :- true | ... 呼び出し側の N1(=2)と1は 具体化できない sum(N, S) :- N>1 | ... 右の節が 選択され ボディ実行 N(=N1=2)は 1より大きい
- 33. GHCの出力引数 Prolog sum(1, 1). ヘッドで出力 (第2引数)を 単一化する GHC sum(1, S) :- true | S = 1. ボディで出力 (第2引数)を 単一化する
- 34. GHCまと め ? 逐次性の排除 ? ? ? ? ガード る によ 同期 ? ? ? AND並列： ボディ のゴールを並列に実行 OR並列 ： 複数の節を並列に試行 細粒度の並行性 ガード では呼び出し 側の変数を具体化でき ない 必要なら 具体化さ れる まで待機 処理系 (KL1) ? KLIC ? http://www.klic.org/index.ja.html
- 36. ジェネレータ ? From～Toまでの数列 (リ ) を生成 スト gen(From, To, X) :- From =< To | X = [From|Xs], Next is From + 1, gen(Next, To, Xs). gen(From, To, X) :- From > To | X = [].
- 37. ジェネレータ gen(1, 2, X) gen(2, 2, X) X = [1 | Xs] X = [2 | Xs] gen(3, 2, X) 結果 X = [] X = [1, 2]
- 38. フィ ルタ ? 入力リ の要素を2倍にし スト スト たリ を出力 twice([X|Xs], Y) :- true | Y1 is X * 2, Y = [Y1|Ys], twice(Xs, Ys). twice([], Y) :- true | Y = [].
- 39. フィ ルタ twice([1,2], Y) Y = [2 | Ys] twice([2], Y) Y = [4 | Ys] twice([], Y) Y = [] 結果 Y = [2, 4]
- 40. パイ プ&フィ ルタ ? ジェネレータ フィ を共有変数で連結 と ルタ ? パイ イ プラ ン並列 or スト ーム並列 リ pipe(From, To, Y) :- true | gen(From, To, X), twice(X, Y).
- 41. パイ プ&フィ ルタ X = [1 | Xs] gen(1, 2, X) Y = [2 | Ys] twice(X, Y) X = [2 | Xs] gen(2, 2, X) Y = [4 | Ys] twice(X, Y) X = [] gen(3, 2, X) Y = [] twice(X, Y) X = [1, 2] 結果 Y = [2, 4]
- 42. 動的なプロ セスネッ ワーク ト ? エラ テネスのふる スト いによ 素数の生成 る primes(N, J) :- true | gen(2, N, I), sift(I, J). sift([P|I], J) :- true | J = [P|L], filter(I, P, K), sift(K, L). filter([N|I], P, K) :- N mod P =:= 0 | filter(I, P, K). filter([N|I], P, K) :- N mod P =?= 0 | K =[N|K1], filter(I, P, K1).
- 51. ク ッ ソ イ ク ート ? 並列に適し たアルゴリ ズム quicksort(X, Y) :- true | qsort(X, Y, []). qsort([X|Xs], Y, Z) :- true | partition(Xs, X, S, L), qsort(S, Y, [X|Ys]), qsort(L, Ys, Z). qsort([], Y, Z) :- true | Y = Z. partition([H|R], X, S, L) :S = [H|S1], partition(R, partition([H|R], X, S, L) :L = [H|L1], partition(R, H =< X | X, S1, L). H > X | X, S, L1).
- 52. ク ッ ソ イ ク ート quicksort qsort qsort qsort partition qsort partition 高い 独立性 partition qsort qsort qsort
- 53. アク ープロ ミ タ グラ ング ? アク ー？ タ ? ? ? 任意の数のメ セージを受け取る と ッ こ ができ る 任意の数のメ セージを送る と ッ こ ができ る GHCによ アク ープロ ミ る タ グラ ング ? アク ー タ ? ? メ セージの列 ッ ? ? メ セージの列を受け取る ッ 述語 リ スト メ セージ ッ ? リ の要素 スト
- 54. アク ープロ ミ タ グラ ング ? 概念 メッセージの列 (リスト) アクター アクター Msg Msg Msg アクター (本当はmerger必要) アクター
- 55. アク ープロ ミ タ グラ ング ? サンプル pingpong hello pong ping world
- 56. アク ープロ ミ タ グラ ング pingpong(N) :- true | ping(N, [hello(X)|_]), pong([X|_]). ping(N, [hello(Resp)|Msgs]) :- N > 0 | Resp = [world(Msgs)|_], N1 is N - 1, ping(N1, Msgs). ping(0, [hello(Resp)|_]) :- true | Resp = []. pong([world(Resp)|Msgs]) :- true | Resp = [hello(Msgs)|_], pong(Msgs). pong([]).
- 57. 要求駆動 ? 必要と れた時に数列を生成 さ gen(From, [X|Xs]) :true | X = From, Next is From + 1 gen(Next, Xs). gen(_, []). gen(1, X), ... X = [N1|X1], ... X1 = [N2|X2], ... X2 = [], ... 初期化 N1 = 1 N2 = 2 終了
- 58. GHCによ 並行プロ ミ る グラ ングまと め ? プロ セスネッ ワーク ト の構築 ? ? ? パイ プ＆フィ ルタ 動的な構築が可能 多様なプロ ミ グラ ングスタ ル イ ? アク ープロ ミ タ グラ ングはスタ ルに過ぎない イ ? ? 遅延評価はスタ ルに過ぎない イ ? ? ? オブジェク 指向も イ ト スタ ルに過ぎない データ 駆動 (先行評価的) 要求駆動 (遅延評価的) 実は低水準なプロ ミ グラ ング言語
- 59. 参考文献 ? 並列論理型言語GHCと その応用 淵一博監修 ? 古川康一? 溝口文雄 共編 ? ISBN4-320-02266-1 ? ? 並行論理プロ ミ グラ ング言語 GHC/KL1 上田和紀 ? http://www.ueda.info.waseda.ac.jp/~ueda/readin gs/GHC-intro.pdf ?