リソースの探索と変換
規則は、各条件式にマッチするリソースを見つけるために、リソースキューを探索します。
このドキュメントでは、規則がどのようにリソースを探索し、出力変換を行うかについて説明します。
計算量
リソースキューに含まれるリソースの数を N、条件式の数を M とすると、リソース探索の計算量は以下の通りです。
- 最悪計算量:
O(N * M) - 平均計算量:
O(N * M) - 最良計算量:
O(N)
探索アルゴリズム
例 1：単一条件式
リソースキューを先頭から探索し、各リソースを以下の手順で判定します。
- リソースの型が求めているものではないなら、スキップ
- リソースが条件式を満足しないなら、スキップ
- そうでなければ、出力式に変換
例えば、以下の規則は、
. $%2=0 # $/2, $*2
以下のように探索を行います。
[3, 4, "foo", 6, "bar"]
^
3%2=0 は偽なのでスキップ
[3, 4, "foo", 6, "bar"]
^
4%2=0 は真なので出力式に変換
[3, 2, 8, "foo", 6, "bar"]
^^^^^
型が合わないのでスキップ
[3, 2, 8, "foo", 6, "bar"]
^
6%2=0 は真なので出力式に変換
[3, 2, 8, "foo", 3, 12, "bar"]
^^^^^
型が合わないのでスキップ
[3, 2, 8, "foo", 3, 12, "bar"]
例 2：複数条件式
複数の条件式がある場合は、少し手順が複雑になります。
- 既に他の条件式でマッチ済みのリソースは、スキップ
- リソースの型が求めているものではないなら、スキップ
- リソースが条件式を満足しないなら、スキップ
- そうでなければ、"マッチ済みの印" をつけて、次の条件式に進む
例えば、以下の規則は、
. $a:str, $b:int # $b*10, 0
以下のように探索を行います。- は "マッチ済みの印" を表します。
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ^スキップ
$b:
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ^^スキップ
$b:
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ^^^^^マッチ
$b:
[3, 'a, "foo", "bar", 4, "hoge"]
$a: -----
$b: ^マッチ
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ----- ^^^^^マッチ
$b: -
注: 探索再開時には、最後にその条件式でマッチしたリソースの
次のリソースから探索を再開します。
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ----- ^^^^^
$b: - ^^スキップ
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ----- ^^^^^
$b: - ^マッチ
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ----- ----- ^^^^^^マッチ
$b: - -
注: $bの条件式の探索が終端に達するので、これで終了です。
[3, 'a, "foo", "bar", 4, "hoge"]
$a: ----- ----- ------
$b: - -
マッチしたリソースを出力式に変換
['a, 30, 0, 40, 0, "hoge"]
注: 1 つ目の条件式がマッチした位置に、出力式が挿入されます。
例 3：連続条件式
ここでは、複数の条件式を内包する連続条件式が行う探索について説明します。
複数の条件式があることから、例 2：複数条件式 と同じように探索を行いますが、連続条件式の 2 つ目以降の条件式の探索位置が、1 つ前の条件式のマッチ位置に限定されます。
例えば、以下の規則は、
. ['a, $:str], $x # 0
以下のように探索を行います。
['a, 3, 'a, "foo"]
'a: ^^マッチ
$:
$x:
['a, 3, 'a, "foo"]
'a: ^^
$: ^スキップ
$x:
['a, 3, 'a, "foo"]
'a: ^スキップ
$:
$x:
['a, 3, 'a, "foo"]
'a: ^^マッチ
$:
$x:
['a, 3, 'a, "foo"]
'a: ^^
$: ^^^^^マッチ
$x:
['a, 3, 'a, "foo"]
'a: --
$: -----
$x: ^^マッチ
注: 'aの探索が終端に達するので、これで終了です。
['a, 3, 'a, "foo"]
'a: --
$: -----
$x: --
マッチしたリソースを出力式に変換
[3, 0]
並列規則
複数の並列された規則がある場合、同じリソースに対して複数の規則がマッチして変換を行う場合があります。その場合、どのような結果が得られるかについて説明します。
例 4：単一条件式の規則のみの場合
単一条件式を持つ規則は、一緒に探索を行います。
例えば、以下の並列規則は、
. $>0 # $+1 // 規則 A
| $>10 # $+2 // 規則 B
以下のように探索を行います。
[3, 14, -5]
^
規則 A にマッチ -> 4 を出力
規則 B にはマッチしない
変換元のリソース 3 は削除される
[4, 14, -5]
^^
規則 A にマッチ -> 15 を出力
規則 B にマッチ -> 16 を出力
変換元のリソース 14 は削除される
[4, 15, 16, -5]
^^
規則 A にはマッチしない
規則 B にはマッチしない
変換は行われなかった
[4, 15, 16, -5]
例 5：複数条件式の規則を含む場合
複数条件式を持つ規則は、先に探索が行われます。
例えば、以下の並列規則は、
. ['a, $] # $+10 // 規則 A
| $>3 # $+1 // 規則 B
| $>3 # $+2 // 規則 C
| $a>3, $b # $a+$b // 規則 D
以下のように探索を行います。
[3, 'a, 4]
'a: --
$: -
(規則 A の探索が完了)
[3, 'a, 4]
$a: -
$b: -
(規則 D の探索が完了)
[3, 'a, 4]
^
規則 A -> 出力なし
規則 D -> 出力なし
規則 B にはマッチしない
規則 C にはマッチしない
規則 D でマッチしているので削除される
['a, 4]
^^
規則 A -> 14 を出力
規則 D -> 出力なし
規則 B にはマッチしない
規則 C にはマッチしない
規則 A でマッチしているので削除される
[14, 4]
^
規則 A -> 出力なし
規則 D -> 7 を出力
規則 B にマッチ -> 5 を出力
規則 C にマッチ -> 6 を出力
規則 D, B, C にマッチしているので削除される
[14, 7, 5, 6]
単一条件式の規則のみの並列規則では、記述した規則順に出力式が出力されていましたが、複数条件式の規則が存在する場合、それらが優先して出力式を出力する点に注意が必要です。
[14, 7, 5, 6]
- - -規則 C からの出力
| 規則 B からの出力
規則 D からの出力
リソースの送信
規則の出力先にコロニー名を指定した場合、その規則の出力リソースは出力先コロニーに送信されます。コロニーはリソースを受信すると、そのリソースを自身のリソースキューの末尾に追加します。
受信のタイミング
送信されたリソースは、送信を行ったコロニーの規則の実行が全て終わってから受信されます。
例えば、以下のプログラムでは、Hello が print コロニーに送信されることはありません。
*sample
Hello
. $ #sample $ // 規則 A
. $ #print $ // 規則 B
%print
なぜなら、Hello は規則 A で sample コロニーに送信されますが、それを sample コロニーが受信するのは規則 B が終了した後だからです。つまり、規則 B が実行されるタイミングには、sample コロニーのリソースキューは必ず空になっているということです。
送信の順序
受信する側のコロニーは、送信された順にリソースを受信します。
送信される順序は、通常の出力式の出力順と同じです。並列規則で送信を行う場合には、例 5：複数条件式の規則を含む場合 で説明した通り、複数条件式の規則での送信の実行が優先されることに注意してください。