檜山正幸のキマイラ飼育記 メモ編 このページをアンテナに追加 RSSフィード

キマイラ・サイト
キマイラ飼育記 本編
メモ編のアーカイブ
檜山の公開プライベート(なんじゃそりゃ?)メモ
檜山本人以外の読者を考慮しておりません。あしからず。

hiyama{at}chimaira{dot}org

2009-03-31(火)

ミーリー/メイヤー・モデル

| 13:45

僕はメイヤー先生のファン

それはいいとして、メイヤー流のクエリー/コマンド・スタイルでプログラムを書いても何も不便はない。クエリーでもコマンドでもない関数/メソッドが必要なら便利関数として書けばいいだけ。

それで、Erlangに対してメイヤー方式を定義したい。

ミーリー機械

モデルとしてミーリー機械(Mealy machine)を採用する。ミーリー機械の状態遷移を

  • (s, a) -> (s', b)

の形で書く。aが入力、s, s'が状態、bが出力。遷移は S×A×S×B = A×(S×S)×B = S×(A×B)×S の部分集合となる。

Vを値(と呼ばれる何か)の集合として、{val(x) | x∈V} の形の記号を出力Bに入れておく。また、εを無音記号とする。すると:

  • クエリーは (s, q) -> (s, val(x)) の形の遷移
  • コマンドは (s, c) -> (s', ε) の形の遷移

ということになる。メイヤーによれば、たいていの便利関数は (s, c) -> (s', ε); (s', q) -> (s', val(x)) として実現できる。せいぜい、cの前後の状態 s, s' から計算できる程度に限定すべき。

Erlangのメッセージ生成関数は、(s, g) -> (s', m) の形になる。これもコマンドとみなしてよいが、出力が無音ではないので、ジェネレータと呼ぶことにする。

ミーリー/メイヤー・モデル

ミーリー機械(初期状態集合を持つ)Mをモデルとする。

Mのクエリーは、遷移ではなくて、状態空間上の関数だとする。コマンドは (s, c) -> (s', ε) の形の遷移、ジェネレータは (s, c) -> (s', m) の形の遷移だとする。

クエリー、コマンド、ジェネレータを関数で表現すると:

  1. クエリー:引数に状態を渡す、戻り値は値(value)
  2. コマンド:引数に状態を渡す、戻り値は状態(state)
  3. ジェネレータ:引数に状態を渡す、戻り値は状態(state)、副作用が生成メッセージ列。

クエリーとコマンドは単なる関数で、何も細工する必要がない。ジェネレータでは、?send(To, Term) というマクロを必ず使うことにして、sendマクロが例えばプロセス辞書に書きこむ。戻り値である状態とメッセージ列を組にして返すラップを作ればよい。

関数が例外を出したときは、それを記録するので、次のようなデータを持つことになる。

  1. Value = {value, term()} | no_value
  2. State = term()
  3. Message = [{To, term()}]
  4. Exception = {Class, term(), Stacktrace} | no_exception

http://erlang.g.hatena.ne.jp/m-hiyama/20090331/1238463293 も参照。

msakaimsakai 2009/04/01 08:46 順序集合のイデアル完備化はベキ等ではなかったはずです。
完備化という名前なのに……

例:
N = {0<1<…}
Idl(N) = {0<1<…<∞}
Idl(Idl(N)) = {0<1<…<∞'<∞}

http://www.tom.sfc.keio.ac.jp/~sakai/d/?date=20070506#p02

m-hiyamam-hiyama 2009/04/01 09:34 > 順序集合のイデアル完備化はベキ等ではなかったはずです。
ああーー、確かに。名前から早とちりしました。
うーむ、べき等ではない「完備化」もあるのか。
ご指摘、ありがとうございます。