並行システム システム情報系情報工学域, システム情報工学研究科コンピュータサイエンス専攻 新城 靖 <yas@cs.tsukuba.ac.jp>
このページは、次の URL にあります。
http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2013/2013-12-03
あるいは、次のページから手繰っていくこともできます。
http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/
aがTrueの時: (ab)c→ (True b)c→ (λx.(λy.x)b)c→ (λy.b)c→ b aがFalseの時: (ab)c→ (False b)c→ (λx.(λy.y)b)c→ (λy.y)c→ c
F≡λx.(((=0 x)1)(*x(F(- x 1))))ただし、=0 という関数は、0 と等しい時に True、そうでない時に False を返 す。
例 2 の階乗 F2 → λx.(((=0 x)1)(*x(F(- x 1))))2 → -- Fの定義。Definition of F. (((=0 2)1)(*2(F(- 2 1)))) → -- β-簡約。Beta reduction. ((False 1)(*2(F(- 2 1)))) → -- (=0 2) の値。The value of (=0 2). ((λx.(λy.y) 1)(*2(F(- 2 1)))) → -- Falseの定義。Definition of False. ((λy.y)(*2(F(- 2 1)))) → -- β-簡約。Beta reduction. (*2(F(- 2 1))) → -- β-簡約。Beta reduction. (*2(F 1)) → -- (- 2 1)の値。The value of (- 2 1). (*2(λx.(((=0 x)1)(*x(F(- x 1))))1)) → -- Fの定義。Definition of F. (*2(((=0 1)1)(*x(F(- 1 1))))) → -- β-簡約。Beta reduction. (*2((False 1)(*x(F(- 1 1))))) → -- (=0 1) の値。The value of (=0 1). (*2((λx.(λy.y) 1)(*1(F(- 1 1))))) → -- Falseの定義。Definition of False. (*2((λy.y))(*1(F(- 1 1)))) → -- β-簡約。Beta reduction. (*2(*1(F(- 1 1)))) → -- β-簡約。Beta reduction. (*2(*1(F 0))) → -- (- 1 1)の値。The value of (- 1 1). (*2(*1(λx.(((=0 x)1)(*x(F(- x 1)))) 0))) → --Fの定義。Definition of F. (*2(*1(((=0 0)1)(*0(F(- 0 1)))) )) → -- β-簡約。Beta reduction. (*2(*1((True 1)(*0(F(- 0 1)))) )) → -- (=0 0) の値。The value of (=0 0) (*2(*1((λx.(λy.x) 1)(*0(F(- 0 1)))) )) → -- Trueの定義。Definition of True. (*2(*1((λy.1)(*0(F(- 0 1)))) )) → -- β-簡約。Beta reduction. (*2(*1 1)) → -- β-簡約。Beta reduction. (*2 1) → -- (*1 1)の値。The value of (*1 1). 2 -- (*2 1)の値。The value of (*2 1).
> (define add1 (lambda (x) (+ x 1))) > (add1 2) 3 > ((lambda (x) (+ x 1)) 2) 3 > > (define sum-square (lambda (x) (lambda (y) (+ (* x x) (* y y))))) > sum-square #<procedure:sum-square> > (sum-square 1) #<procedure:349> > ((sum-square 1)2) 5 > > (lambda (x) (lambda (y) (+ (* x x) (* y y)))) #<procedure:429> > ((lambda (x) (lambda (y) (+ (* x x) (* y y))))1) #<procedure:488> > (((lambda (x) (lambda (y) (+ (* x x) (* y y))))1)2) 5 >
(define F (lambda (n) (if (= n 0) 1 (* n (F (- n 1))))))if は関数ではなくて、special form。 "if" is not a function. "if" is a special form.
言語としては、何種類か(Plasma、Act-1、Act-2、Act-3、Omega、Ether)ある。 各言語で見かけがけっこうちがう。
図? アクタの基本概念/Basic concepts of the Actor model
アクタは、メッセージを受け取り、それに対して行為を行うような、通信を行う エージェントである。行為の種類には、次のようなものがある。
アクタがメッセージを受け取ると、いったんロックされる。ロックされるとメッ セージは処理されない。次のアクタに become したら、新しい後継のアクタが 同じメールボックスからメッセージを読み出して処理を続ける。
要素
goto f(1, 2, 3);のようなもの。
通常の階乗(in Scheme)
(define (fact n) (if (= n 0) 1 (* n (fact (- n 1)))))継続を取るような階乗
(define (fact-c n c) (if (= n 0) (c 1) (let ((c2 (lambda (x) (c (* n x))))) (fact-c (- n 1) c2))))
実行例
> (fact 3)
6
> (fact 4)
24
> (fact-c 3 print)
6> (fact-c 4 print)
24>
factorial≡λm. match m <n c> if n = 1 then (send c <1>) else if n > 1 then (send factorial <(n-1) (λk.(send c <n * K>))>)3の階乗を計算して、継続print_answerに送りたい時には、 次のように書く。
(send factorial <3 print_answer>)
(define (Factorial( )) (Is-Communication (a doit (with customer =m) (with number =n)) do (become Factorial) (if (NOT (= n 0)) (then (send m 1)) (else (let (x = (new FactCust (with customer m) (with number n))) (send Factorial (a do (with customer x) (with number (- n 1))))))))) (define (FactCust (with customer =m) (with number =n)) (Is-Communicaton (a number k) do (send m (* n k))))
振る舞い記述 (define (名前 (with id パタン)) 通信ハンドラの並び) 通信ハンドラ (Is-Communication パタン do コマンド) letコマンド (let (変数名 = 式) do コマンド) 条件コマンド (if 式 (then do コマンドの並び) (else do コマンドの並び)) メッセージ送信コマンド (send メールボックス 値) becomコマンド (become 式) 新しいアクタの生成 (new 式)
(define (Account (with Balance =b)) (Is-Request (a Balance) do (become (Account (with Balance b))) (reply b)) (Is-Request (a Deposit (with Amount =a)) do (become (Account (with Balance (+ b a)))) (reply (a Deposit-Receipt (with Amount a)))) (Is-Request (a Withdrawal (with Amount =a)) do (if (> a b) (then do (become (Account (with Balnce b))) (complain (an Overdraft))) (else do (become (Account (with Balnce(- b a)))) (reply (a Withdrawal-Receipt (with Amount n)))))))
http://www.ibm.com/developerworks/jp/java/library/j-scala04109.html
Ted Neward: "The busy Java developer's guide to Scala: Dive
deeper into Scala concurrency", IBM DeveloperWorks, 10 Apr 2009.
http://www.ibm.com/developerworks/java/library/j-scala04109.html
リスト 9. Counter の例 (アクターによる方法) より。
object CountingSample { case class Incr case class Value(sender : Actor) case class Lock(sender : Actor) case class UnLock(value : Int) class Counter extends Actor { override def act(): Unit = loop(0) def loop(value: int): Unit = { receive { case Incr() => loop(value + 1) case Value(a) => a ! value; loop(value) case Lock(a) => a ! value receive { case UnLock(v) => loop(v) } case _ => loop(value) } } } def main(args : Array[String]) : Unit = { val counter = new Counter counter.start() counter ! Incr() counter ! Incr() counter ! Incr() counter ! Value(self) receive { case cvalue => Console.println(cvalue) } counter ! Incr() counter ! Incr() counter ! Value(self) receive { case cvalue => Console.println(cvalue) } } }
1階述語論理の論理式は、次の形式で書ける。
P 1 ∨ P 2 ∨ ... ∨ P n ← Q 1 ∧ Q 2 ∧ ... ∧ Q n.
「←」の左がたかだか1個のものがホーン節(Horn clause)。(ORが複数書きたく なったら、複数行にわたって書く)。ホーン節には3種類ある。
fatherof(isaac,abraham). -- isaac の父は abraham である fatherof(ishmail,abraham). fatherof(shuah,abraham). fatherof(jacob,isaac). fatherof(esau,isaac). fatherof(reuben,jacob). fatherof(dinah,jacob). fatherof(dan,jacob). fatherof(asher,jacob). fatherof(joseph,jacob). motherof(isaac,sarah). -- isaac の母は sarah である。 motherof(ishmail,hagar). motherof(shuah,ketura). motherof(jacob,rebeccah). motherof(easu,rebeccah). motherof(reuben,leah). motherof(dinah,leah). motherof(dan,bilhah). motherof(asher,zilpah). motherof(joseph,rachel).
"_"
は、無名変数。値は残らない。
"motherof(isaac,_)?"
の質問には、
"motherof(isaac,sarha)"
だけがマッチする。
"fatherof(_,_)"
の質問には、全ての"fatherof"
がマッ
チする。
"fatherof(joseph,X)"
の質問には、"X=jacob"
の時に
マッチする。この時に変数 "X"
は、"jacob"
に束縛(bind)されている。
"motherof(C,leah)?"
の質問には、
"C=reuben"
という束縛が起きた後に、
バックトラックが行われて、「別のコンテキストで」
"C=dinah"
という束縛が起きることがある。
parentof(C,P) :- motherof(C, P). -- P が C の母なら、 P は C の親である。 parentof(C,P) :- fatherof(C, P). -- P が C の父なら、 P は C の親である。 grandparentof(C,GP) :- parentof(C,P), parentof(P,GP). -- C の親が P で、かつ、P の親が GP なら、GP は C の祖父母である。 ancestor(C,A) :- parentof(C,A). ancestor(C,A) :- parentof(C,P), ancestor(P,A). -- C の親が P で、かつ、P の祖先が A ならば、A は C の祖先である。
teaches(name(shinjo,yasushi),01CH303,time(fri,3)).
append([],Y,Y). append([A|B],Y,[A|B1]) :- append(B,Y,B1).
図? Prolog の append
quicksort(List,Sorted) :- qsort(List, Sorted, []). qsort([],H,H). qsort([A|B],H,T) :- partition(B,A,S,L), qsort(S,H,[A|T1]), qsort(L,T1,T). partition([],X,[],[]). partition([A|B],X,[A|S],L) :- A<X, partition(B,X,S,L). partition([A|B],X,S,[A|L]) :- A>=X, partition(B,X,S,L).
図? Prolog によるクイックソート
quicksort にある並列性。Parallelism in quicksort.H :- G 1, G 2,...,G n | B 1, B 2, ..., B m.
「|」は、コミット演算子。 G 1, G 2,...,G n はガード部。 B 1, B 2, ..., B m は、ボディ部。append([A|X1],Y,Z) :- true | Z = [A|Z1], append(X1,Y,Z1). append([],Y,Z) :- true | Z=Y.Prolog ならこうなる
append([A|X1],Y,[A|Z1]) :- append(X1,Y,Z1). append([],Y,Y).H 1 :- G 11, G 12,...,G 1n | B 11, B 12, ..., B 1m. H 2 :- G 21, G 22,...,G 2n | B 21, B 22, ..., B 2m.
:- append(U,[4,5],W),U=[1,2,3].なら、append の処理は最初は中断する。U が具体化された後で再開する。
quicksort(Xs,Ys) :- true | qsort(Xs, Ys-[]). qsort([X|Xs],Ys0-Ys3) :- true | partition(Xs,X,S,L), qsort(S,Ys0-Ys1), Ys1=[X|Ys2], qsort(L,Ys2-Ys3). qsort([],Ys0-Ys1) :- true | Ys0 = Ys1. partition([X|Xs],A,S,L0) :- A<X | L0=[X|L1], partition(Xs,A,S,L1). partition([X|Xs],A,S0,L) :- A>=X | S0=[X|S1], partition(Xs,A,S1,L). partition([],A,S,L) := true | S=[], L=[].
1999年に、サン・マイクロシステムズ社のビル・ジョイらによって開発され発 表された。
Jini の目標は、ネットワークで Plug & Play を実現すること。 機器をネットワークに接続しただけで、特別な設定 をしなくてもすぐに利用可能になること。
目標
JavaSpaces は、内部的に Jini のルックアップ・サービスの実現で使われて いる。JavaSpaces も、Jini でアクセス可能なサービスの1つと考えることも できる。
Jini のクラスライブラリは、 JavaSpaces の回 で紹介した Apache River が利用できる。
Microsoft の、Jini に対抗した技術。
サービスの登録と検索
ルックアップ・サービス自身も、最初から知られている必要はない。 ネットワーク上で自動的に探される。 Discovery と Join。
Java のオブジェクトが Lease。
リース期間は、延長することができる。 延長されなかった lease は、ルックアップ・サービスから削除される。 登録されているサービスを明示的に削除する仕組みは、存在しない。
サービスが削除された時には、分散型イベント配送サービスにより関係してい る所に知らされる。
トランザクションのインタフェースは定められているが、具体的な実現は各サー ビスにまかされている。
サービスの提供者とサービスの利用者の間は、最終的にはに RMI で接続される。
ServiceIDLister インタフェースを implements する。
package com.sun.jini.lookup; public interface ServiceIDListener extends java.util.EventListener { void serviceIDNotify(net.jini.core.lookup.ServiceID serviceID); }ルックアップ・サービスからコールバックされる。
Discovery の実現方法
図1 マルチキャストによる Discovery/Discovery by multicast
図2 Join
グループは、名前(文字列)で区別される。
Jini パッケージは、JoinManager という参照クラスを含む。
public JoinManager(Object obj, Entry[] attrSets, ServiceIDListener callback, LeaseRenewalManager leaseMgr) throws IOException public JoinManager(Object obj, Entry[] attrSets, String[] groups, LookupLocator[] locators, ServiceIDListener callback, LeaseRenewalManager leaseMgr ) throws IOException
import java.rmi.*; public interface RemoteBall extends Remote { public void hit() throws java.rmi.RemoteException; }
import java.rmi.*; import java.rmi.server.*; import net.jini.core.lookup.*; import com.sun.jini.lookup.*; public class Ball extends UnicastRemoteObject implements RemoteBall, ServiceIDListener { public Ball() throws RemoteException { super(); } public void serviceIDNotify(ServiceID id) { System.out.println("ServiceId is "+id); } public void hit() { System.out.println("Ball has been hit"); } }
import java.rmi.*; import net.jini.core.entry.*; import net.jini.lookup.entry.*; import com.sun.jini.lookup.*; import com.sun.jini.lease.*; public class BallStarter { public static void main(String[] args) { try { System.setSecurityManager(new RMISecurityManager()); RemoteBall ball = (RemoteBall) new Ball(); LeaseRenewalManager renewal = new LeaseRenewalManager(); Entry[] attributes = new Entry [] { new Name("Jini enabled ball")}; JoinManager join = new JoinManager( ball, attributes, (Ball) ball, renewal ); System.out.println("Ball started and registered at Lookup-Server"); } catch (Exception e) { e.printStackTrace(); } } }
図3 Lookup
サービスは、次の3つで区別される。public ServiceTemplate(ServiceID serviceID, Class[] serviceTypes, Entry[] attrSetTemplates)サービス(オブジェクト)の探し方
import java.rmi.*; import net.jini.core.discovery.*; import net.jini.core.lookup.*; public class Bat { public Ball ball; public void play(RemoteBall ball) { try { ball.hit(); System.out.println("I hit the ball"); } catch (RemoteException e) { System.out.println(e); } } public static void main (String[] args) { Bat bat = new Bat(); try { System.setSecurityManager(new RMISecurityManager()); LookupLocator locator = new LookupLocator("jini://localhost"); ServiceRegistrar registrar = locator.getRegistrar(); Class[] classes = new Class[] { RemoteBall.class }; ServiceTemplate template = new ServiceTemplate( null, classes, null); RemoteBall remoteBall = (RemoteBall) registrar.lookup(template); bat.play(remoteBall); } catch (Exception e) { e.printStackTrace(); } } }
信頼性が低いネットワークと、どう戦う方法の1つ。
lease には、期限がある。
期限の長さは、交渉可能。 期限が短い(1分以下、数秒)というのは、あまり想定されていない。
リースの利点
Jini のサービスを提供しているオブジェクトは、Lease インタフェースを実 装している。
public interface Lease { long FOREVER = Long.MAX_VALUE; ... long getExpiration(); void renew(long duration) throws LeaseDeniedException, UnknownLeaseException, RemoteException; void cancel() throws UnknownLeaseException, RemoteException; ... }getExpiration() で、リースの残り時間がわかる。ミリ秒単位。
renew() で延長する。 延長できない時には、LeaseDeniedException が返される。
もう使わなくなった時には、cancel() できる。 期限切れと同じことになる。
リースの管理には、LeaseRenewalManager を使う。
Reduce the following expression. Show the intermediate steps as in the example in factorial.
((λx.λy.(+ x y))1)10
How does the Actor model express concurrency? Explain it briefly.
While a language processing system of Prolog executes a program sequentially, we can consider that we run the program in parallel. In the example quicksort, point out places that we can execute in parallel. Explain the places briefly.
Jini uses some techniques to support unreliable networks, such as wireless LAN. Choose one of these techniques, and explain it briefly.