LISPUSER

S 式ベース DSL の思い出とか Prolog の思い出とか

前に FizzBuzz ネタやったときに、なぜか懐しい事を思い出したので。

ふと Lisp の応用例（？）といえそうなネタを思い出した。Microsoft の Age of Empire II というゲームを御存知だろうか？ 私が学生時代にとても流行したゲームなんですが、これって AI をプログラミングする機能がありましてね。 AI Scripters (http://www.aiscripters.com/index.php ) というサイトで解説されてます。 誰もこれを Lisp とは呼びませんでしたが、皆でハックして AI War とかやって遊べたんですね。

(defrule
  (current-age == dark-age)
  (building-type-count mill < 2)
  (sheep-and-forage-too-far)
  (or
    (players-unit-type-count my-player-number 122 > 0)
    (players-unit-type-count my-player-number 216 > 0)
  )
  (can-build mill)
=>
  (chat-local-to-self "Found some hunting, building a mill.")
  (build mill)
  (disable-self)
)

前置記法じゃないけど S 式ですね。しかも宣言的。LISA の推論ルールみたいな形式。 ルールを定義して、マッチするとアクションが動作する。ゲームの状態 (Fact) をベースに ルールとアクションを定義する。いやーいいですね。

(defrule 条件 => アクション)

;; 例： エリート侍ユニットの人数に応じて不気味な笑い
(defconstant villager-goal 1)
(defrule (unit-type-count elite-samurai == 5) => (set-goals samurai-goal 5))
(defrule (unit-type-count elite-samurai == 10) => (set-goals samurai-goal 10))
(defrule (samurai-goal == 5) => (chat-to-all "fufufu ..."))
(defrule (samurai-goal == 10) => (chat-to-all "hehehehe ..."))

今から思えば Norvig の教科書にでてくる宣言的スタイルです。 私の中では結構理想的なわかりやすさでしたね。S 式ベースの DSL の好例というか。 破城槌 + ナイトの数が揃ったら敵の城を破壊に!! とかルールを書いてくわけです。

S 式だから読み難いんだ、S 式は皆に嫌われている、というのはプログラマだけなんじゃないですかねー。 あんまりこの AI スクリプトの仕様に文句つけたりする人はいなかったように思います。 言語仕様等の詳細は AI Scripters のページをどうぞ。あるいは製品の CD にドキュメントが入っていたと思います。 ¹ _ 用語は Lisp とかなり異なっていますが、ほぼ困る事はないでしょう。 というかエンジンが Lisp ということはないだろうから、これは「Lisp 以外で S 式を利用した例」なんだろうなー。 S 式はだめだめだという主張を良く聞きますが、いや、そんなことはない!! 実は某超人気ゲームでも採用されていた!! かつ、ユーザーコミュニティにも受け入れられていた!! なんつって反論できますね。さすがにちょっと古すぎか :-)

製品 CD-ROM の DOCS フォルダ以下の CPSB.DOC (Computer Player Strategy Builder Guide) ですね。今見直してもいいですね〜。やっぱ製品はしっかりしてるなー。

で、本題ですが Prolog は楽しい。なんというか、昔教わっていたときに

factorial(0,1).
factorial(N,X) :-
        factorial(N1, X1),
        N is N1 + 1,
        X is N * X1.

という定義を打ちこんで、動作を試していたら…

?- factorial(3, X).

X = 6 

Yes
?- factorial(6, X).

X = 720 

Yes
?- factorial(X, 6).

X = 3 

当時は最後のでびっくりした。え、なんで？みたいな。 Prolog の挙動は独特なんですが、当時は あんまりわかってなかったですからね。手元の junk ディレクトリから時代を追っていくといろいろあっておもしろい。

% まっとうなやつ
factorial(0,1).
factorial(N,X) :-
        N > 0,
        N1 is N - 1,
        factorial(N1, X1),
        X is N * X1.

:

% 末尾再帰を意識していた模様
factorial(0,X,X).
factorial(N,A,X) :-
        N > 0,
        N1 is N - 1,
        A1 is N * A,
        factorial(N1, A1, X).

この辺は定義順から逆向きができないころですねー。 で、最終的には逆向きも計算したくなって↓のようになると。

% atomic 覚えて双方向別々に作ってる時期
factorial(N,X) :- atomic(N), fact_fwd(N, 1, X).
factorial(N,X) :- atomic(X), fact_rev(1, X, N).

fact_fwd(0, X, X).
fact_fwd(N, A, X) :-
        N > 0,
        N1 is N - 1,
        A1 is A * N,
        fact_fwd(N1, A1, X).

fact_rev(N, 1, N).
fact_rev(N, A, X) :-
        A > 1,
        N1 is N + 1,
        A mod N1 =:= 0,
        A1 is A // N1,
        fact_rev(N1, A1, X).

わはは。ぐたぐたになってきてる。

FizzBuzz も副作用なしでリストを作る人が多いところを見ると、こんな定義をして

fizzbuzz(N, X) :-
       N > 0,
       N mod 15 =:= 0 -> X = 'FizzBuzz';
       N mod 3 =:= 0 -> X = 'Fizz';
       N mod 5 =:= 0 -> X = 'Buzz';
       X = N.

aux(0, []).
aux(N, L) :-
       aux(N1, L1),
       N is N1 + 1,
       fizzbuzz(N, X),
       L = [ X | L1 ].

list_of_fizzbuzz(N, L) :- 
       aux(N, X),
       reverse(X, L).

テスト中にあやまって

?- list_of_fizzbuzz(5, X).

X = [1, 2, 'Fizz', 4, 'Buzz'] 
    
Yes
?- list_of_fizzbuzz(X, [1, 2, 'Fizz', 4, 'Buzz']).

X = 5 

うぉ、こ、これは…？よもやリストから逆算？ Prolog 頭イイ!! などと感動して Prolog に興味を持つ人がでてくるかもしれないと 秘かに期待したり。まぁ、ネタをしったらがっかりするかもしれませんが。

檜山正幸のキマイラ飼育記 にて Prolog と Erlang ネタが。うーん、やっぱ Erlang は進化してますねぇ。 greeting の例題っぽいものを SWI-Prolog で書いてみました。ちょっと似てるけど、receive 相当の処理でタイムアウト指定が 簡単にできないなぁ。ついでに Prolog のマルチスレッドでお荷物扱いの assert や record もきっちり廃止されているそうですし。 Erlang って構文は似てるけど、かなり違うんですね。あー軽量プロセスうらやましいなぁ。

greeting_main :-
        thread_self(Id),
        format("[~a]>>> start greeting thread\n", Id),
        thread_get_message(Msg),
        (
            Msg = start  -> greeting_loop;
            Msg = finish -> format("exit from main.\n");
            greeting_main
        ).

greeting_loop :-
        thread_self(Id),
        format("[~a]>>> hello, world!!\n", Id),
        sleep(1),
        thread_peek_message(pause) -> thread_get_message(_), greeting_wait;
        thread_peek_message(finish) -> format("exit from loop.\n");
        greeting_loop.

greeting_wait :-
        thread_self(Id),
        format("[~a]>>> wait\n", Id),
        thread_get_message(Msg),
        (
            Msg = restart -> greeting_loop;
            Msg = finish -> write(Msg), format("ext form wait.\n");
            greeting_wait
        ).

greeting(Id) :-
        thread_create(greeting_main, Id, []).

Erlan は Prolog をベースにしているだけあって似てますねぇ。手を出してみようかな。