ぱたへね

はてなダイアリーはrustの色分けができないのでこっちに来た

Land of Lisp

lisp book

漫画が独特の味を出しているCommon Lispの本、Land of Lispを読みました。とても面白かったので紹介します。

本の内容

ゲームを作りながら、Common Lispや関数型プログラミングについて学べる本です。他の「ゲームで学ぶ・・・」系の本と違うのは、既存のゲームをCommon Lispで実装していくので、できあがったゲームがそれなりに面白い事です。ゲームのI/Fは基本CUIですが、一部の出力に関してはgraphvizやsvgを使ってグラフィカルに出力されていて面白くなっています。Common Lispの基本的な文法以外にも、Functional programming、ゲーム用AI、Webサーバー、Lazy Programmingと扱っているトピックは広いです。

基本的なスタンスが「Lispｻｲｺｰ」なので、そういうのが好きな人も十分楽しめると思います。

ゲームの紹介

いくつかゲームを紹介します。

Wizard Adventure Game

zorkタイプのテキストアドベンチャーゲームです。

起動するとこんな感じでゲームが始まります。

CL-USER 3 > (game-repl)
look
You are in the living-room. A wizard is snoring loudly on the couch. There is a door going west from here. There is a ladder going upstairs from here. You see a bucket on the floor.

出来ることは少ないですが、ゲーム専用のREPLを作ったり、graphvizを使ってリスト構造を可視化したり、いろんなテクニックが紹介されています。

graphvizを使った出力の例
http://www.evernote.com/shard/s25/sh/ab360b5b-52a0-488b-9081-e7d77461a0ed/93c58bc6726e294951d471fa1005e1a9

Wumpus

街を移動しながら、泥棒のWumpusを狩るゲームです。


ゲームを起動すると、状況がこのように画像ファイルとして出力されます。*が自分で、最初は自分の近くの状況しか分かりません。


ゲームを勧めていくと、血痕を見つけたり、パトカーのサイレンを聞いたり、はてさて上手くWumpusをやっつけることができるでしょうか。

Orc Battle

RPGの戦闘シーンを抜き出したようなゲームです。
Knightとなって、群がるモンスターに勝利することができるでしょうか。

CL-USER 23 > (orc-battle)
You are a valiant knight with a health of 30, an agility of 30, and a strength of 30
Your foes:
   1. (Health=6) A malicious hydra with 6 heads.
   2. (Health=1) A slime mold with a sliminess of 2
   3. (Health=7) A fierce BRIGAND
   4. (Health=4) A slime mold with a sliminess of 3
   5. (Health=3) A malicious hydra with 3 heads.
   6. (Health=7) A malicious hydra with 7 heads.
   7. (Health=10) A fierce BRIGAND
   8. (Health=8) A malicious hydra with 8 heads.
   9. (Health=4) A wicked or with a level 8 club
   10. (Health=10) A malicious hydra with 10 heads.
   11. (Health=9) A slime mold with a sliminess of 3
   12. (Health=5) A malicious hydra with 5 heads.
Attack style: [s]tab [d]ouble [r]oundhouse:

Attack styleを選びながら、モンスターを倒していきます。ちなみに僕はこのゲームで一回も勝ったことがありません。

Dice of Doom

サイコロを使った陣取りゲームです。
最初はコンソールでゲームを作っていきますが、最終的にはSVGを使ってこんな綺麗な画面を作ります。

このゲームから Functional Programming が出てきて、少し難易度が上がります。簡単なAIの実装、ゲームエンジンとAIの分離、遅延評価等面白そうなトピックが満載です。

例えば構造体

Land of Lispではゲームを作りながら、Common Lispの文法も説明してあります。僕がなるほどと思ったのは構造体のinclude機能です。他の本で構造体の機能を勉強したときには、いまいちincludeの使い道が分かりませんでした。それが、この本だと上手く説明してあります。

Orc Battleに出てくるモンスターの定義です。

(defstruct monster (health (randval 10)))

モンスター生成時に、healthの値がランダムにきまります。

オークやスライムといった他のモンスターは、このmonsterをincludeして定義します。

(defstruct (orc (:include monster)) (club-level (randval 8)))
(defstruct (slime-mold (:include monster)) (sliminess (randval 5)))

オークには棍棒のレベル、スライムにはsliminessという謎のパラメータが追加されています。

後はモンスター毎に攻撃の関数を用意してやると、(monster-attack m)で、そのモンスター固有の攻撃をします。

(defmethod monster-attack ((m orc))
  (let ((x (randval (orc-club-level m))))
    (princ "An orc swings hit club at you and knocks off ")
    (princ x)
    (princ " of your health points. ")
    (decf *player-health* x)))

(defmethod monster-attack ((m slime-mold))
  (let ((x (randval (slime-mold-sliminess m))))
    (princ "A slime mold wraps around your legs and decreases your agility by ")
    (princ x)
    (princ "! ")
    (decf *player-agility* x)
    (when (zerop (random 2))
      (princ "It also squirts in your face, taking away a health point! ")
      (decf *player-health*))))

これらの機能は他のCommon Lispの本でも当然出てくるわけですが、ゲームで使い方を示されれてようやく便利だなと気がつきました。

例えば遅延評価

Dice of Doomでは、遅延評価を使います。Common Lisp自体には遅延評価の機能が無いので、マクロを使って実装します。ソースの一部はこんな感じです。

(defmacro lazy (&body body)
  (let ((forced (gensym))
        (value (gensym)))
    `(let ((,forced nil)
           (,value nil))
       (lambda ()
         (unless ,forced
           (setf ,value (progn ,@body))
           (setf ,forced t))
         ,value))))

(defun force (lazy-value)
  (funcall lazy-value))

(defmacro lazy-cons (a d)
  `(lazy (cons ,a ,d)))

(defun lazy-car (x)
  (car (force x)))

(defun lazy-cdr (x)
  (cdr (force x)))

(defun lazy-mapcar (fun lst)
  (lazy (unless (lazy-null lst)
          (cons (funcall fun (lazy-car lst))
                (lazy-mapcar fun (lazy-cdr lst))))))

SICPに比べてわかりやすくないですか？SICPで挫折した人も、このコードなら追えそうな気がします。

ちなみにSICPで出てくるforceはこれです。
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-27.html#%_sec_4.2

(define (force-it obj)
  (cond ((thunk? obj)
         (let ((result (actual-value
                        (thunk-exp obj)
                        (thunk-env obj))))
           (set-car! obj 'evaluated-thunk)
           (set-car! (cdr obj) result)  ; replace exp with its value
           (set-cdr! (cdr obj) '())     ; forget unneeded env
           result))
        ((evaluated-thunk? obj)
         (thunk-value obj))
        (else obj)))

SICPの為のフォローを入れておくと、Land of Lispの場合はゲームで使う遅延評価が出来れば良いのに対して、SICPの場合は遅延評価が出来る処理系を作っているので、実装のレイヤーが違います。またSICPはマクロを使わないという縛りもあります。

LispWorksへの変更点

LispWorksではいくつか動かないところがあったので修正しました。LispWorkのバージョンは、LispWorks Professinal 5.1 (32bit Windows)です。

dot->png

graphvizでdot.exeを起動するところです。sys:call-system-showing-outputを使う事でコマンドプロンプトを表示させずにdot.exeを実行しています。

(defun dot->png (fname thunk)
  (with-open-file (*standard-output*
                   fname
                   :direction :output
                   :if-exists :supersede)
    (funcall thunk))
    (or 
     #+CLISP  (ext:shell (concatenate 'string "dot -Tpng -O " fname))
     #+LISPWORKS (sys:call-system-showing-output  (concatenate 'string  "dot -Tpng -O " fname))
     nil))
find-empty-node

これは不具合ではないのですが、空ノードを見つけるための関数の実装が酷かったのでちょっと手を入れました。元々のアルゴリズムは、ランダムにノードを選んで、空でなかったらもう一度ランダムにノードを選び、空ノードが見つかるまでループします。*congestion-city-nodes*に変なデータが入っていると、簡単に無限ループします。LispWorksの場合、動かしているプログラムが無限ループに入ると、エディタも巻き込んで何も出来なくなってしまいます。そこで、検索回数に上限をつけて、見つからなかったらメッセージを表示して検索を終了させています。今思うと、remove-ifで空ノードだけ集めて、そこからランダムに選べば一発ですね。

(defun find-empty-node (&optional (depth 0))
  (if (> depth 20)
    (format t "find no empty nodes")
    (let ((x (random-node)))
      (if (cdr (assoc x *congestion-city-nodes*))
        (find-empty-node (1+ depth))
        x))))
pick-monster

Orc Battleにでてくるモンスター選択の関数です。LispWorksですと、readだけでは、"Cannot find that; regexp is too unconstrained"と表示され動かないので、read-lineで読んでからparse-integerで整数に変換しています。

(defun pick-monster ()
  (fresh-line)
  (princ "Monster #:")
  (let ((x (parse-integer (read-line) :junk-allowed T)))
    (if (not (and (integerp x)
		  (>= x 1)
		  (<= x *monster-num*)))
	(progn (princ "That is no a valid monster number.")
	       (pick-monster))
	(let ((m (aref *monsters* (1- x))))
          (if (monster-dead m)
            (progn (princ "That monster is alread dead.")
              (pick-monster))
            m)))))

あとHTTP serverを動かす所もLispWorksでは動きません。少し挑戦してみましたが、僕には難易度が高くて挫折しました。

感想

ゲームを作っていくのが楽しくて、なんだかんだ言いながら楽しく最後まで読むことが出来ました。とはいえ、途中のFunctional Programmingが出てくるところから、ソースコードが難解になって、なかなか思った通りに動かなかったです。せっかくFunctional Programmingにしたのに、ミニマムで動かす単位が上手く作れなかったり、プログラムの第一歩から乱数が入ってきてエラーが再現できなかったりしました。labelsも多くなってきていて、LispWorksのstep実行が無かったら途方に暮れていたと思います・この辺りのデバッグ方法が、もう少し詳しく書いてあった方が良かったです。あと、caddrとかも多くて、対象となるデータ構造が頭に入ってないと、何をしているのか良く分からない所も多かったです。ちなみに、SICPなんかは(define (thunk-env thunk) (caddr thunk))のように、単なるListへのアクセスに対しても意味を当ててあって、流石教科書だなと感じます。

さて、Chaton Common Lispで翻訳の話が出ています。興味を持った人は首を長くして待ちましょう。待てない人は原書買いましょう。