Index > プログラム言語とその他のメモ


SchemeとActor理論

この言語は、MITの二人の聰明な人間がしていた大きな論争にはじまります。 それは、私がMITに学生として来るちょっと前のことでした。 この論争というのは、Carl Hewittと、 新しく学生として入ったGerry Sussmanの間に起こったものです。
Guy L. Steele Jr.「Scheme 過去・現在・未来 前編」 (bit vol.28,No.4 1996 4月号)

あれは玉突きだね。.....いや、というよりはキャッチボールだ
北村薫「六の宮の姫君」


Actorに基づく言語

メッセージ送信

アクターにメッセージを送る。 メッセージを受け取ったアクターは、別のアクターにメッセージを送る。 以下同様。

例えば「1と2と3からなるメッセージをアクターaに送る」という事を

  [a 1 2 3]

と書く事にする。 アクターaはメッセージを受け取ると、別のアクターにメッセージを送る。 ここで、どのアクターにメッセージを送るかというのは、 決まっているアクターもあれば決まっていないアクターもある。

もしアクターaがどのアクターにメッセージを送るか決まっていないなら、 「メッセージをどのアクターに送るか」という情報もaへのメッセージに含める。 なのでaからcにメッセージを送らせたいなら

  [a 1 2 3 c]

のようにする(このcは継続アクターと呼ばれる)。

加算アクター「+」に、1,2,cというメッセージを送るとする。

  [+ 1 2 c]

すると加算アクター「+」は1と2を足してその結果3をアクターcに送る。

(もし「数アクター「1」に「足す」というメッセージを送る」と考えるなら

  [1 '+ 2 c]

となる。)

alpha式

新しくアクターを作る事もできる。 そのためにはalpha構文を使う。 例えば

  (alpha (u k) [+ u u k])

という構文によって作られたアクターは、 メッセージを受け取ると加算アクターにメッセージを送る。

  [(alpha (u k) [+ u u k]) 10 c]

とすると、最終的に20がアクターcに送られる。

次に

  [+ 1 2
    (alpha (u)           ; c
      [* 5 u display])]

という文を考える。 この文のメッセージの流れは次のようになる。 まず加算アクター「+」に、 1,2,alpha式で作られたアクター(cと呼んでおく)からなるメッセージが送られる。 メッセージを受け取った「+」は、1と2の和を計算して、その答えをアクターcに送る。 メッセージを受け取ったcは、 乗算アクター「*」に、5,3,displayというメッセージを送る。 メッセージを受け取った「*」は、 5と3の積を計算して答を表示アクター「display」に送る。 メッセージを受け取った「display」は、15を表示する。

message flow

結局この式で5*(1+2)を計算している。

(5+7)-(2*3)の結果を表示させたいなら次のようになるだろう。

  [+ 5 7
    (alpha (u)                  ; c
      [* 2 3
        (alpha (v)             ; d
          [- u v display])])]

(アクターに関して、レキシカル(字句)スコープルールを使う。 なので例えばアクターdのメッセージ送信式中でuを参照できる)

message flow

普通、部分式がどのような順番で評価されていくかは暗黙的に制御されている。 上の式ではアクターを使って明示的に制御を行なっている。

ifとdefine

if構文を追加する。

  (if x m1 m2)

はxが真(#f以外の値)の時m1式を実行し、 xが偽(#f)の時m2式を実行する。 例えば

  [>= a b
    (alpha (u)
      (if u
          [* 2 a display]
          [* 2 b display]))]

という式でaとbの大きい方を2倍して表示する。

アクターに名前を付けるにはdefine構文を使う。

  (define abs
    (alpha (x k)
      [>= x 0
        (alpha (u)       ; c
          (if u
              [k x]
              [- 0 x k]))]))

で定義されるアクターabsは、xの絶対値をアクターkに送る。

message flow of abs

関数

このままだと簡単な数式の計算のためにも いくつものアクターで制御を行なわなければならない。 それはあんまりなので関数も用意する。 関数呼出しは

  (f arg1 arg2 arg3)

みたいに書く。

メッセージ送信の場合、メッセージを受け取ったアクターは 結果を別のアクターに送る。 一方、関数呼出しでは、結果を関数を呼び出した側に返す。

以後、アクターと関数で名前が重なる場合、 アクターの方はアンダーバーから始まる名前を付けておく事にする。 例えば加算関数は「+」で加算アクターは「_+」、 絶対値関数は「abs」で絶対値アクターは「_abs」となる。

絶対値アクターは

  (define _abs
    (alpha (x k)
      (if (>= x 0)
          [k x]
          [k (- 0 x)])))

と定義する事ができる。

再帰的定義

アクターの再帰的定義を行なってみる。 例として定番の階乗関数を使う。

  [_fact n k]

で、n!(nの階乗)がアクターkに渡されれば良い。 n!を計算するには、まず(n-1)!を計算してそれにnを掛ければ良い。 それは

  [_fact (- n 1)
         (alpha (u) [k (* n u)])]

と表現できる。 後はnが0の場合を付け加えれば完成する (比較のために関数版のfactも定義する)。

  (define _fact
    (alpha (n k)
      (if (= n 0)
          [k 1]
          [_fact (- n 1)
                 (alpha (u)        ; c
                   [k (* n u)])])))
  
  (define fact
    (lambda (n)
      (if (= n 0)
          1
          (* n (fact (- n 1))))))

普通の関数呼出しでは、 再帰呼出しごとに制御情報がスタックにつまれる。

_factではその代わりに、 再帰呼出しごとに新しいアクターを生成している(cの部分)。

例えば

  [_fact 3 display]

では、displayで答が表示されるまでに3つのアクターが生成される。

message flow of recursive fact

上の_factは再帰の底まで進んでそこから戻りながらかけ算を進めていく。 これを、先にかけ算を行ないそれから再帰を行なうように変更する。 そのために引数を1つ増やして、次のように書く。

  (define _fact_t
    (alpha (n acc k)
      (if (= n 0)
          [k acc]
          [_fact_t (- n 1)
                   (* n acc)
                   (alpha (u)   ; c
                     [k u])])))

でも良く見るとcで生成されたアクターは 値uをアクターkに転送しているだけ。 そこで次のように書換えられる。

  (define _fact-t
    (alpha (n acc k)
      (if (= n 0)
          [k acc]
          [_fact-t (- n 1) (* n acc) k])))

つまりこの_fact-tの場合、 渡されたkをそのまま次の再帰呼出しで渡しているので 再帰ごとに新しいアクターを生成する必要が無い。

message flow of tail recursive fact

またこのことから、 対応する関数版のfact-t

  (define fact-t
    (lambda (n acc)
      (if (= n 0)
          acc
          (fact-t (- n 1) (* n acc)))))

でも、再帰ごとにスタックを消費しなくても良い事がわかる(末尾再帰の最適化)。

_factをアクターだけで書いてみる

上の_factの定義では、_fact以外は関数を使っている。 もし足し算その他もアクターを使って定義すると次のように書ける。

  (define _fact                    ;; 以前の定義
    (alpha (n k)
      (if (= n 0)
          [k 1]
          [_fact (- n 1)
                 (alpha (u)
                   [k (* n u)])])))
  
  (define _fact
    (alpha (n k)
      [_= n 0
        (alpha (u)   ; c
          (if u
              [k 1]
              [_- n 1
                (alpha (v)   ; d
                  [_fact v
                         (alpha (w)   ; e
                           [_* n w k])])]))]))

わかりにくくなっているけど、 その代わりに関数呼出しで暗黙的に行なわれていた制御を アクターc、d、eが明示的に行なっている。

message flow of actor fact


Schemeで書いてみる

Sussmanと私は関数とアクタは同一だと認めました。 どんなことになるのでしょう? 関数は値を返すものと考えられています。 アクタはそうではありません。 かわりにアクタはメッセージを送ります。 この質問に対する正しい答えは 「それがどうした。」「なんでも、いいじゃないか。」です。
Guy L. Steele Jr.「Scheme 過去・現在・未来 後編」 (bit vol.28,No.5 1996 5月号)

いままで書いたプログラムは、 CPS(Continuation Passing Style)で書いたSchemeプログラムと 全く同じものになっている (alphaをlambdaにして、四角カッコを丸カッコに変えるだけ)。

Schemeで_factを書くと次のようになる。

  (define _fact
    (lambda (n k)
      (if (= n 0)
          (k 1)
          (_fact (- n 1)
                 (lambda (u)
                   (k (* n u)))))))
  
  実行例
  (_fact 10 (labmda (x) x))
  → 3628800

可変引数の事を考えると、 継続は最後の引数にするより第1引数にしたほうが良いかもしれない。 でも、見ためは解りにくくなる (map関数とかでも、見ためから関数引数を最後に持っていきたくなる事がある)。

  (define _fact
    (lambda (k n)
      (if (= n 0)
          (k 1)
          (_fact (lambda (u)
                   (k (* n u)))
                 (- n 1)))))
  
  実行例
  (_fact (labmda (x) x) 10)
  → 3628800

_+とかその他のアクターも使うなら次のようになる。

  (define _+
    (lambda (x y k)
      (k (+ x y))))
  
  (define _-
    (lambda (x y k)
      (k (- x y))))
  
  (define _*
    (lambda (x y k)
      (k (* x y))))
  
  (define _=
    (lambda (x y k)
      (k (= x y))))
  
  (define _fact
    (lambda (n k)
      (_= n 0
        (lambda (u)
          (if u
              (k 1)
              (_- n 1
                (lambda (v)
                  (_fact v
                         (lambda (w)
                           (_* n w k))))))))))
  
  実行例
  (_fact 10 (labmda (x) x))
  → 3628800

Index > プログラム言語とその他のメモ