$BJB9T%W%m%0%i%_%s%08@8l(B(2)/Concurrent Programming Languages(2)

$BJB9T%7%9%F%`(B

                               $B%7%9%F%`>pJs7O>pJs9)3X0h(B,
			       $B%7%9%F%`>pJs9)3X8&5f2J%3%s%T%e!<%?%5%$%(%s%9@l96(B
                               $B?7>k(B $BLw(B
                               <yas@cs.tsukuba.ac.jp>

$B$3$N%Z!<%8$O!" http://www.cs.tsukuba.ac.jp/~yas/cs/csys-2018/2018-08-03
$B$"$k$$$O!" http://www.cs.tsukuba.ac.jp/~yas/cs/
http://www.cs.tsukuba.ac.jp/~yas/

$B"#O"Mm;v9`(B

$B"#:#F|$N=EMW$JOC(B

$B"#JB9T%*%V%8%'%/%H;X8~%b%G%k(B/Concurrent object-oriented models.

$B%*%V%8%'%/%H;X8~$N0l
  • $B!JC` $BJB9T%*%V%8%'%/%H$O!"G=F0E*(B(active)$B$J%*%V%8%'%/%H$7$+$J$$!#?M4V$N$h(B $B$&$K!"Aj8_$K%a%C%;!<%8$rAw

    $B"!%"%/%?%b%G%k(B/The Actor models

    1977$BG/(B C.Hewitt $B$i$K$h$C$FDs>'$5$l$?JB9T7W;;%b%G%k!#(B $B%"%/%?$H8F$P$l$k7W;;

    $B8@8l$H$7$F$O!"2?

    $B%

    $B?^(B? $B%"%/%?$N4pK\35G0(B/Basic concepts of the Actor model

    $B%"%/%?$O!"%a%C%;!<%8$r

  • $B%a%C%;!<%8$r!"<+J,<+?H!"$^$?$O!"B>$N%"%/%?$KAw?.$9$k!#(B
  • $B%"%/%?$r@8@.$9$k!#(B
  • $B $B%"%/%?$O!"%a%C%;!<%8$r@\FO$/$H$$$&$h$j$O!"%a!<%k%\%C%/%9$K4V@\E*$KFO(B $B$/!#%a!<%k%\%C%/%9$O!"%P%C%U%!%j%s%0$N5!G=$,$"$k!#%a!<%k%\%C%/%9$K$"$k(B $B%a%C%;!<%8$O!"(BFIFO $B$K=hM}$5$l$k$H$O8B$i$J$$!#(B

    $B%"%/%?$,%a%C%;!<%8$r

    $BMWAG(B

    • $B%W%j%_%F%#%V!&%"%/%?(B(primitive actor)$B!#%G!<%?$H $BHs%W%j%_%F%#%V%_%#%V%"%/%?(B
      • $B=guBVJQ?t$r;}$D!#(B
      • $BHs=g
      $B%"%/%?$O!"%a%C%;!<%8$rAw

      $B"!%"%/%?$N7QB3(B/Continuations in Actor

      $B7QB3(B(continuation$B!"7QB3E@$H$b$$$&(B)$B$rMQ$$$k!#(B $B5f6K$N(B goto $BJ8!#(BC $B8@8l$N4X?t$G(B
          goto f(1, 2, 3);
      
      $B$N$h$&$J$b$N!#(B

      $BDL>o$N3,>h(B(in Scheme)

      (define (fact n)
          (if (= n 0) 1
              (* n (fact (- n 1)))))
      
      $B7QB3$rh(B
      (define (fact-c n c)
        (if (= n 0)
            (c 1)
            (let ((c2 (lambda (x) (c (* n x)))))
              (fact-c (- n 1) c2))))
      

      $B > (fact 3)[$B 6 > (fact 4)[$B 24 > (fact-c 3 print) 6> (fact-c 4 print)[$B 24> []

      $B"!3,>h(B/Factorial in Actor

      [Hewitt 77a]
      factorial$B-q&K(Bm.
        match m <n c>
          if n = 1 then
            (send c <1>)
          else if n > 1 then
            (send factorial <(n-1) ($B&K(Bk.(send c <n * K>))>)
      
      3$B$N3,>h$r7W;;$7$F!"7QB3(Bprint_answer$B$KAw$j$?$$;~$K$O!"(B $B (send factorial <3 print_answer>)

      $B"!3,>h(B/Factorial in Actor

      (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))))
      
      • 2$B$D$N%Q%i%a%?$r;}$D%a%C%;!<%8(B ((with customer x) (with number n)) $B$r (become Factorial) $B$G!"<+J,<+?H$r:F@8@.!#$=$&$G$J$$$H!"(B1$B8D$N(B Factorial $B$r7W;;$7$?$@$1$G%"%/%?$,>CLG$7$F$7$^$&!#(B
      • $B?7$7$$%"%/%?(B FactCust $B$r@8@.$7$F$$$k!#(B
      $B?6$kIq$$5-=R(B
          (define ($BL>A0(B (with id $B%Q%?%s(B))
            $BDL?.%O%s%I%i$NJB$S(B)
      
      $BDL?.%O%s%I%i(B
          (Is-Communication $B%Q%?%s(B do $B%3%^%s%I(B)
      
      let$B%3%^%s%I(B
          (let ($BJQ?tL>(B = $B<0(B) do $B%3%^%s%I(B)
      
      $B>r7o%3%^%s%I(B
          (if $B<0(B (then do $B%3%^%s%I$NJB$S(B) (else do $B%3%^%s%I$NJB$S(B))
      
      $B%a%C%;!<%8Aw?.%3%^%s%I(B
          (send $B%a!<%k%\%C%/%9(B $BCM(B)
      
      becom$B%3%^%s%I(B
          (become $B<0(B)
      
      $B?7$7$$%"%/%?$N@8@.(B
        (new $B<0(B)
      
      

      $B"!6d9T8}:B(B/A bank account in Actor

      (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)))))))
      
      • Is-Request $B$O!"(Bclient-server $B7?$N%a%C%;!<%8(B $B$N reply $B$O!"(BIs-Request $B$KBP$9$kDL>o$N1~Ez$rJV$9!#(B
      • complain $B$O!"(BIs-Request $B$KBP$9$kNc30$N1~Ez$rJV$9!#(B
      • become $B$H(B reply $B$O!"F1;~$K=hM}$G$-$k!#(B

      $B"!%+%&%s%?(B(Scala)/Counter actor in Scala

      Ted Neward: "$BB?K;$J(B Java $B3+H/https://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. https://www.ibm.com/developerworks/java/library/j-scala04109.html

      $B%j%9%H(B 9. Counter $B$NNc(B ($B%"%/%?!<$K$h$kJ}K!(B) $B$h$j!#(B

      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) }    
        }
      }
      
      • $B!V(B!$B!W$G!"%a%C%;!<%8$rAw?.$9$k!#(B
      • receive $B$G $B%/%i%$%"%s%HB&$O(B send $B$7$F(B receive$B!"(B $B%5!<%PB&$O!"(Breceive $B$7$F(B reply $B$G!"(BRPC $BE*$JF0$-$r$5$;$i$l$k!#(B

      $B"#JB9TO@M}7?%W%m%0%i%_%s%08@8l(B/Concurrent logic programming languages

      $B"!(BProlog

      Prolog (Programming in Logic) $B$O!"%U%i%s%9%^%k%;%$%fBg3X$N(B Alain Colmerauer $B$i$K$h$C$F3+H/$5$l$?8@8l!#(B $B#13,=R8lO@M}(B(first-order predicate logic)$B$K4p$E$$$F$$$k!#(B

      $B"!#13,=R8lO@M}(B/first-order predicate logic

      $B=R8lO@M}$G$O!"
    • $B=R8l(B P(t 1, t 2, ..., t )
    • ($B"O(Bx)P(x)$B!#A4$F$N(Bx$B$K$D$$$F(BP(x)$B$,@.$jN)$D!#(B
    • ($B"P(Bx)P(x)$B!#(B $B$"$k(Bx$B$K$D$$$F(BP(x)$B$,@.$jN)$D!#(B
    • P$B"J(BQ$B!"(BP$B"K(BQ$B!"!A(BP$B!#(B and, or, not
    • P$B"+(BQ$B!#(BQ$B$,??$J$i$P(BP$B$b??!#(B

    $B#13,=R8lO@M}$NO@M}<0$O!"

    P 1 $B"K(B P 2 $B"K(B ... $B"K(B P n $B"+(B Q 1 $B"J(B Q 2 $B"J(B ... $B"J(B Q n.

    $B!V"+!W$N:8$,$?$+$@$+(B1$B8D$N$b$N$,%[!<%s@a(B(Horn clause)$B!#(B(OR$B$,J#?t=q$-$?$/(B $B$J$C$?$i!"J#?t9T$K$o$?$C$F=q$/(B)$B!#%[!<%s@a$K$O(B3$B

  • $BI=L@(B: P$B"+(B.
  • $B8xM}(B: P$B"+(B Q 1 $B"J(B Q 2 $B"J(B ... $B"J(B Q n.
  • $BL\I8(B: $B"+(B Q 1 $B"J(B Q 2 $B"J(B ... $B"J(B Q n.

    $B"!C1=c$J%b%G%k(B($B;v

    fatherof(isaac,abraham).  -- isaac $B$NIc$O(B abraham $B$G$"$k(B
    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 $B$NJl$O(B sarah $B$G$"$k!#(B
    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).
    
    • "_" $B$O!"L5L>JQ?t!#CM$O;D$i$J$$!#(B
    • "motherof(isaac,_)?" $B$N"motherof(isaac,sarha)" $B$@$1$,%^%C%A$9$k!#(B
    • "fatherof(_,_)" $B$N"fatherof" $B$,%^%C(B $B%A$9$k!#(B
    • "fatherof(joseph,X)" $B$N"X=jacob" $B$N;~$K(B $B%^%C%A$9$k!#$3$N;~$KJQ?t(B "X" $B$O!"(B"jacob" $B$KB+G{(B(bind)$B$5$l$F$$$k!#(B
    • Prolog $B$NJQ?t$O!"F1$8%3%s%F%-%9%H$G$OC10lBeF~(B(single assignment)$B$G!"(B C $B8@8l$N(B x = x + 1 $B$N$h$&$J0UL#$G=q$-49$($i$l$k$3$H$O$J$$!#(B
    • "motherof(C,leah)?" $B$N"C=reuben" $B$H$$$&B+G{$,5/$-$?8e$K!"(B $B%P%C%/%H%i%C%/$,9T$o$l$F!"!VJL$N%3%s%F%-%9%H$G!W(B "C=dinah" $B$H$$$&B+G{$,5/$-$k$3$H$,$"$k!#(B
    • $BJQ?t$r4^$`%Q%?%s%^%C%A$O!"C10l2=(B(unification)$B$H8F$P$l$k!#(B

    $B"!5,B'(B/Rules

    parentof(C,P) :- motherof(C, P). -- P $B$,(B C $B$NJl$J$i!"(B P $B$O(B C $B$N?F$G$"$k!#(B
    parentof(C,P) :- fatherof(C, P). -- P $B$,(B C $B$NIc$J$i!"(B P $B$O(B C $B$N?F$G$"$k!#(B
    
    grandparentof(C,GP) :- parentof(C,P), parentof(P,GP).
                             -- C $B$N?F$,(B P $B$G!"$+$D!"(BP $B$N?F$,(B GP $B$J$i!"(BGP $B$O(B C $B$NADIcJl$G$"$k!#(B
    ancestor(C,A) :- parentof(C,A).
    ancestor(C,A) :- parentof(C,P), ancestor(P,A).
                             -- C $B$N?F$,(B P $B$G!"$+$D!"(BP $B$NAD@h$,(B A $B$J$i$P!"(BA $B$O(B C $B$NAD@h$G$"$k!#(B
    

    $B"!%?%W%k(B/Tuples

    teaches(name(shinjo,yasushi),01CH303,time(fri,3)).
    

    $B"!%j%9%H(B/Lists

    append([],Y,Y).
    append([A|B],Y,[A|B1]) :- append(B,Y,B1).  
    

    A$B!

    $B?^(B? Prolog $B$N(B append

    $B"!(BAND$BJBNs$H(BOR$BJBNs(B/and-parallelism and or-parallelism

    $BO@M}<0$NI>2A$K=gHV$N9M$(J}$O$J$$$N$G!"JBNs$K=hM}$r9T$C$F$b$h$$!#(B