LMNtalプログラミングの基礎を紹介します。
ルール †
LMNtal の書き換え規則をルールと言います。ルールは
(左辺) :- (右辺)
という形をしていて、「左辺の形の物があったら右辺の形に書き換える」という意味になります。
a. b. c. d. a. b. a. c. a. a :- z.
↓↓↓ アトム a を全て z に置き換える
z. b. c. d. z. b. z. c. z.
a. b. c. d. a. b. a. c. a. a :- z. b :- z.
↓↓↓ アトム a と b を全て z に置き換える
z. z. c. d. z. z. z. c. z.
さらに
(左辺) :- (ガード) | (右辺)
という形でガード(条件文)を書くことができます。
n(-2). n(-1). n(0). n(1). n(2). n(3). n(N) :- N<0 | n(0).
↓↓↓ 負の数ならば0にする
n(0). n(0). n(0). n(1). n(2). n(3).
ガード(条件文)一覧
int(N) (Nがintなら) float(N) (Nがfloatなら) string(N) (Nがstringなら) unary(N) (Nが1つのアトムなら) ground(N) (Nより先が膜を含まないアトム集団なら)
= (groundの比較: = ) /= (groundの比較: ≠ )
=:= (intの比較: = ) =/= (intの比較: ≠ ) < =< > >= (intの比較: < ≦ > ≧ )
=:=. (floatの比較: = ) =/=. (floatの比較: ≠ ) <. =<. >. >=. (floatの比較: < ≦ > ≧ )
LMNtalは非決定に実行が行われるのが特徴です。(どれが実行されるかわからないともいえます。)
SLIMのモデルチェック機能を使えばどのような状態が存在するか確認することができます。
a. a :- b. a :- c.
というプログラムを実行すると
b または c
となります。
SLIMにオプション『--nd』を付けるとこの全状態遷移を見ることができます。
States 0::a. @5 1::b. @5 2::c. @5 Transitions init:0 0::1(_ab),2(_ac) 1:: 2:: # of States = 3
整数アトム †
整数アトムは
n(1).
のように書きます。
1(n).
も同じ意味になります。
四則演算もできて
n(1),n(2),n(3). n(A),n(B) :- N=A+B | n(N).
↓↓↓
n(6).
となります。
for文のようにしたいならば
i(0). i(I) :- J=I+1,J<10 | n(I),i(J).
↓↓↓
n(0), n(1), n(2), n(3), n(4), n(5), n(6), n(7), n(8), i(9)
とすることによって0~9までの数を生成することができます。
これらを応用して、階乗を求めるプログラムを書くと
fact(5). fact(N) :- N>1, M=N-1 | n(N), fact(M). fact(N) :- N=1 | . n(X), n(Y) :- N=X*Y | n(N).
↓↓↓
n(120).
となります。
膜 †
膜は計算を局所化します。
{ n(1), n(2), n(3). n(A), n(B) :- N=A+B | n(N). }. { n(4), n(5), n(6). n(A), n(B) :- N=A+B | n(N). }.
↓↓↓
{ n(6), @601 }, { n(15), @602 }
膜の中でルールの適用ができなくなると実行される、というルールも書くことができます。
{ $p,@p }/ :- $p.
$p は膜の中にあるすべてのアトム、 @p は膜の中にあるすべてのルール、を表すので
それぞれの膜で計算が進み、最後にルールが適用できなくなったらアトムだけ外に出すことを表しています。
よってこれを入れると
{ n(1), n(2), n(3). n(A), n(B) :- N=A+B | n(N). }. { n(4), n(5), n(6). n(A), n(B) :- N=A+B | n(N). }. { $p,@p }/ :- $p.
↓↓↓
n(6), n(15), @603
となります。
さらに膜の外でも計算を行えば
{ n(1), n(2), n(3). n(A), n(B) :- N=A+B | n(N). }. { n(4), n(5), n(6). n(A), n(B) :- N=A+B | n(N). }. { n(7), n(8), n(9). n(A), n(B) :- N=A+B | n(N). }. { $p,@p }/ :- $p. // 計算が止まったら実行 n(A),n(B) :- N=A+B | n(N).
↓↓↓
n(45), @604
と、並列計算のようにさせることができます。
リスト †
リストは
list = [1,2,3,4].
のように書くことができます。(シンタックスシュガーなので実状態をunyoで見ることをお勧めします。)
また、ここから
list = [1,2,3,4]. list = [N|T] :- n(N), list = T.
↓↓↓
n(1), n(2), n(3), n(4), list([]), @601
と、順番に先頭から数字を取り出すことができます。
また途中からアトムをとる事もできて
list = [1,2,3,4]. L = [N|T] :- n(N), L=T.
↓↓↓
n(4), n(1), n(2), n(3), list([]), @601
となります。unyoで見るとわかりますが、先頭から順にアトムを取り出してはいません。
リストに値を追加するときは
n(1),n(2),n(3). res = []. res = T, n(N) :- res = [N|T].
↓↓↓
res([2,3,1]), @601
とすることで、値を先頭へ追加していくことができます。
順に先頭へ追加されていったので、
1を追加 3を追加 2を追加
が行われたことになります。 (この例ではn(N)がどれにマッチするかわからないのでこのような追加の順番になっています。)
応用としてソートを書くと
L=[A,B|T] :- A>B | L=[B,A|T]. list([1, 3, 4, 6, 2, 5, 8, 7, 0]).
↓↓↓
list([0, 1, 2, 3, 4, 5, 6, 7, 8]).
となります。
さらに詳しい解説 †
簡単な演習があります。
論文等を参照してください。
(ローカルページから一部抜粋してayanoが再構成しました。)