Dependable Agent関係

移動コードのための言語機構
Code Mobility Support for Stock Programming Languages
渡部卓雄
JAIST
9/12/1998
SMAF Workshop
1
バックグラウンド
• オブジェクト，高階関数や再帰記述とも直
交できる移動コード機構
– reasoning可能な記述を支援
– 現在の計算状態を含めて移動させる
– 既存の(逐次的な）プログラムに入れるだけで
移動コードにできる，簡単な機構
9/12/1998
SMAF Workshop
2
“go”によるマイグレーション
• スレッドの全状態（＝継続）の転送
• 通常，移動する範囲は制限された範囲で
十分では？ → 部分継続
9/12/1998
SMAF Workshop
3
call/ppc
（call-with-placed-partial-continuation）
• (call/ppc place function)
– 現時点における部分継続を place に置き，そ
れに function を適用する．
– function の適用自体は call/ppc の呼び出しと
同じ場所において行われる．
9/12/1998
SMAF Workshop
4
% ：同期プロンプト
g
(f (g a))
f
(f (% (g (call/ppc p
(lambda (k) (k a))))))
a
g
f
9/12/1998
SMAF Workshop
5
& : 非同期プロンプト
(f (& (g (call/ppc p
(lambda (k) (k a))))))
dummy
a
g
f
9/12/1998
SMAF Workshop
6
go
(define (go place)
(call/ppc place
(lambda (k) (k (current-place)))))
• (% (begin A (go p1) B (go p2) C))
• (& (begin A (go p1) B (go p2) C))
9/12/1998
SMAF Workshop
7
A : (f (% (g (call/ppc B
(lambda (k1)
(& (k1 (h (call/ppc C
(lambda (k2)
(k2 a))))))))))
B
A
C
h
g
f
9/12/1998
SMAF Workshop
8
(f (g (h a)))
(% (f (call/ppc A
(lambda (k)
(& (k (g (call/ppc B
(lambda (k)
(& (k (h (call/ppc C
(lambda (k)
(& (k a)))))
)))))))))))
9/12/1998
SMAF Workshop
9
@マクロ
(@ p e)
|||
(call/ppc p (lambda (k) (& (k e)))))
(f (g (h a)))
↓
(% (f (@ p1 (g (@ p2 (h (@ p3 a)))))))
∥
(% (f@p1 (g@p2 (h@p3 a))))
9/12/1998
SMAF Workshop
10
(% (f@A (g@B (h@C a))))
(% (begin
(set! tmp a)
(go C)
(set! tmp (h tmp))
(go B)
(set! tmp (g tmp))
(go A)
(f tmp)))
(% (f (prog1
(g (prog1
(h (prog1
a
(go C)))
(go B)))
(go A)))
上のような go の使い方との違いは？
9/12/1998
SMAF Workshop
11
goの場合
B
A
C
h
g
f
9/12/1998
SMAF Workshop
12
@の場合
B
A
C
h
g
f
9/12/1998
SMAF Workshop
13
(# (f@A (g@B (h
(call/ppc C
(lambda (k) (ntimes n k a)))))))
(define (ntimes n f a)
(if (= n 0)
a
(ntimes (- n 1) f (f a))))
9/12/1998
SMAF Workshop
14
9/12/1998
SMAF Workshop
15
9/12/1998
SMAF Workshop
16
9/12/1998
SMAF Workshop
17
9/12/1998
SMAF Workshop
18
実装!?
• λクロージャのある言語
– 引数フレームは無限エクステントを持つ．
– 制御スタックの増減と同期しない．
– Java の場合，inner classで代用できる．
• call/cc (call/pc)
– 制御フレームも無限エクステントを持つので，
setjmpなどでは代用できない．
– プログラム変換によって消去可能
9/12/1998
SMAF Workshop
19
実装!?
• 制御フレーム・引数フレーム
– オブジェクトとして実現 → Actor
• 制御フレームから辿れるオブジェクトをシリ
アライズして転送(HORB)
• CPS変換もどきで Java のクラスを生成
– 高階関数 → 無名クラス
– 関数呼び出し → メッセージ送信
9/12/1998
SMAF Workshop
20
CPS変換
f(x) = x+1
→ f’(x,k) = k(x+1)
f(x,y) = g(h(x),y)
→ f’(x,y,k) = h’(x, λv.g’(v,y,k))
f(x) = begin g(x); h(x) end
→ f’(x,k) = g(x,λv.h(x,k))
9/12/1998
SMAF Workshop
21
プロトタイプ
• Java -> Java のソースコード変換
– 継続・部分継続をオブジェクトにする
• serializeして転送
– 現在は手で変換
– 自動化：
• 素直にCPS変換を行うと変換後のコードが莫大に
なる．そこでFriedman, Haynes, Danvyらによる最適
化手法を用いる．
9/12/1998
SMAF Workshop
22
継続・部分継続オブジェクト
interface Continuation {
public void fire (Object value);
}
interface PartialContinuation {
public Continuation compose (Continuation cont);
}
class FinalCont implements Continuation {
public void fire (Object value) {
System.out.println("value = " + value);
}
}
9/12/1998
SMAF Workshop
23
(define (fact n k)
(if (< n 1)
(k 1)
(fact (- n 1) (lambda (value) (k (* n value))))))
public void fact (int n, Continuation k) {
if (n < 1)
k.fire(new Integer(1));
else
this.fact (n-1, new Continuation () {
public void fire (Object value) {
k.fire(n * (int)value);
}});
}
9/12/1998
SMAF Workshop
24
public void fact (int n, Continuation k) {
if (n < 1)
k.fire(new Integer(1));
else {
final int nn = n;
final Continuation kk = k;
this.fact (n-1, new Continuation () {
public void fire (Object value) {
kk.fire(new Integer(nn * ((Integer)value).intValue()));
}});
}
}
9/12/1998
SMAF Workshop
25
(+ 1 #(* 2 (call/pc (lambda (k) (k (k 3))))))
= (+ 1 (* 2 (* 2 3)))
=> ((k (k c0)) 3)
where c0 = (lambda (v) (+ 1 v))
k = (lambda (c) (lambda (v) (c (* 2 v))))
9/12/1998
SMAF Workshop
26
PartialContinuation k = new PartialContinuation () {
public Continuation compose (Continuation cont) {
final Continuation _cont = cont;
return (new Continuation () {
public void fire (Object value) {
_cont.fire(new Integer(2 * ((Integer)value).intValue()));
}});
}
};
final Continuation _cont0 = cont0;
Continuation c0 = new Continuation () {
public void fire (Object value) {
_cont0.fire(new Integer(1 + ((Integer)value).intValue()));
}
};
(k.compose(k.compose(c0))).fire(new Integer(3));
9/12/1998
SMAF Workshop
27
動的な名前空間の実現
• 一級環境オブジェクト（クロージャ）
– ライブラリ・位置に依存するコード
– 疑似静的スコープ(Lee & Friedman)，動的環
境(Queinnec)，一級文脈(Lee,橋本）
• 移動先で未定義
– 代用品（disconnected operation)
– 移動元に要求
9/12/1998
SMAF Workshop
28
関連研究
• Sekiguchi & Yonezawa (semantics)
• Communication Passing Style (CmPS)
– Jagganathan (NEC Research) 1997
– Linda 風の Cooordination Language
• put/read/get するたびにスレッドが移動
• 移動の範囲をプロンプトで指定
• Facile (ECRC) 1995
9/12/1998
SMAF Workshop
29
他の研究テーマ
• 移動コードの形式的仕様
• フォールトトレランスのためのアブストラク
ション
– エージェントを監視するレベル（デーモン）の導
入
– AgentSpace上に実装（しようとしている）
• 動的コード生成による高速化
9/12/1998
SMAF Workshop
30

Download Report