実用CommonLisp -第二章読了- - (apply-generic op . args)

PAIP2章読了しました。二日酔いで死んでいたので2日ほど空いてしまった。生活リズム崩れまくって、今日は徹夜して一気に戻す作戦なので眠い目を擦りながら朝5時くらいからPAIPってた。

2章はDSL書きましょうって内容でした。うーん面白い。

第2章簡単なLispプログラム

2.1 英語のサブセット用文法

2章では任意の英文を生成するプログラムを書く。英語のごく小さなサブセット用の簡単な文法が示される。

文 => 名詞句 + 動詞句
名詞句 => 冠詞 + 名詞
動詞句 => 動詞 + 名詞句
冠詞 => the, a, ...
名詞 => man, ball, woman, table, ...
動詞 => hit, book, saw, liked, ...

この記述は、技術的には文脈自由な句構造文法(context-free phase-structure grammar)と呼ばれる。基礎となるパラダイムは生成統語論(generative syntax)と呼ばれる。この文法は次のように理解すれば良い。文(Sentence)を生成したい場合は、名詞句(Noun-Phrase)と動詞句(Verb-Phrase)を生成できる。名詞句が特定された場合は、その代わりに冠詞(Article)と名詞句を生成する。冠詞が特定された場合はthe, a, またはその他の冠詞を生成する。取り囲んでいる単語にかかわらず、どの部分にも規則を適用するので、形式論としては「文脈自由」である。規則が全体としてある言語の分の完全な集合と、その上に非文の完全な集合を定義しているので、考え方は「生成的」である。この規則を使用して単一の文を導出してみよう。

2.2 成功法による解法

句構造文法を使用して任意の文を生成するプログラムを開発する。成功法は、各々の文法規則を別のLisp関数によって表現することである。

(defun sentence () "文" (append (noun-phrase) (verb-phrase)))
(defun noun-phrase () "名詞句" (append (Article) (Noun)))
(defun verb-phrase ()  "動詞句" (append (Verb) (noun-phrase)))
(defun Article () "冠詞" (one-of '(the a)))
(defun Noun () "名詞" (one-of '(man ball woman table)))
(defun Verb () "動詞" (one-of '(hit took saw liked)))

(defun one-of (set)
  "Pick one element of set, and make a list of it."
  (list (random-elt set)))

(defun random-elt (choices)
  "Choose an element from a list at rondom."
  (elt choices (random (length choices))))

プログラムは問題なく実行される。しかしLispによる定義はオリジナルの文法規則よりも読みづらい。さらに複雑な文法規則を扱う場合に、この問題が自体を悪化させる

名詞句 => 冠詞 + Adj* + 名詞 + PP*
Adj* => Φ, Adj + Adj*
PP* => Φ, PP + PP*
PP(前置詞句) => Prep + 名詞句
Adj(形容詞)  => big, little, blue, green, ...
Prep => to, in, by, with, ...

この表記法で、Φ は空の選択を示す。カンマはいくつかの選択肢があることを示す。アスタリスクは特異なものではなく、Lispで紹介したものと同様にシンボル名の一部である。 PP*はPPが0回以上繰り返すことを示す。これは数学者Stephen Cole Kleeneの名をとって「Kleen star」(clean-Eと発音する)表記法と呼ばれる。アスタリスクで終わる名前は、アスタリスクが付かない元の名前が0回以上繰り返されることを表している。

(defun Adj* ()
  (if (= (random 2) 0)
    nil
    (append (Adj) (Adj*))))

(defun PP* ()
  (if (random-elt '(t nil))
    (append (PP) (PP*))
    nil))

(defun noun-phrase () (append (Article) (Adj*) (Noun) (PP*)))
(defun PP () (append (Prep) (noun-phrase)))
(defun Adj () (one-of '(big little blue green adiabatic)))
(defun Prep () (one-of '(to in by with on)))

重要な点は、最初は単純な関数だったものが、今ではかなり複雑になっていることである。理解するためにはdefun,(),case,if,quote,評価の順序などのLispの規則を知る必要がある。文法規則の実装は、理想的には言語学の規則だけを使うべきだ。大きな文法を開発する場合は、問題はさらに悪化して、文法を記述する人はますますLispに依存しなくてはならない。

2.3 ルールベースによる解法

プログラムを実装する上での代替え案は、文法規則を書きやすくすることに集中して、それらを処理する方法は後で考えることである。オリジナルの規則を見てみよう。

文 => 名詞句 + 動詞句
名詞句 => 冠詞 + 名詞
動詞句 => 動詞 + 名詞句
冠詞 => the, a, ...
名詞 => man, ball, woman, table, ...
動詞 => hit, book, saw, liked, ...

各規則は、左辺部の1つのシンボル、矢印、右辺部から構成される。面倒なことには、右辺部が2種類あることである。すなわり、名詞句 → 冠詞+名詞のように連結されたリストの場合と、名詞 → mann, ball, ...のように選択可能な単語のリストの場合である。これに対応するには、全ての規則が右辺部に可能性のあるもののリストを持てば良い。例えば、連結されたリスト「冠詞+名詞」は(Article Noun)のようなLispのリストで表せる。したがって、規則のリストは次のように表せ、ルールベースによる関数はこうなる。

(defparameter *simple-grammar*
  '((sentence -> (noun-phrase verb-phrase))
    (noun-phrase -> (Article Noun))
    (verb-phrase -> (Verb noun-phrase))
    (Article -> the a)
    (Noun -> man ball woman table)
    (Verb -> hit took saw liked))
  "grammar:文法 / A grammar for a trivial subset of English.")

(defvar *grammar* *simple-grammar*
  "The grammar userd by generate. Initially, this is *simple-grammar*, but we can switch to other grammars.")

(defun rule-lhs (rule)
  "規則の左辺部を取得する"
  (first rule))

(defun rule-rhs (rule)
  "規則の右辺部を取得する"
  (rest (rest rule)))

(defun rewrites (category)
  "ある文法カテゴリに対する書き換え（右辺部）の全てを調べる"
  (rule-rhs (assoc category *grammar*)))

(defun mappend (fn the-list)
  "Apply fn to each element of list add append the results."
  (apply #'append (mapcar fn the-list)))

(defun generate (phrase)
  "Generate a random sentence or phrase."
  (cond ((listp phrase)
         (mappend #'generate phrase))
        ((rewrites phrase)
         (generate (random-elt (rewrites phrase))))
        (t (list phrase))))

2.4 進むべき2つの道

結論としてはルールベース（今風でいうとDSL)のほうがいいよ。

ルールベースの考え方は、余分なステップを踏むので小さい問題に対しては仕事量が大きくなるけれど、多くの場合、修正や拡張が容易になる。 AIの問題のほとんどはこの記述が適している。

この章の感想

この章では英文の生成プログラムを2つの方法で作成し、DSLは小さい問題では仕事量は増えるが、拡張性・修正容易性・ドメインの規則だけを使ってプログラムを記述できる、などの良さを伝えている。

この章で特に印象的だったのは2.2節の

重要な点は、最初は単純な関数だったものが、今ではかなり複雑になっていることである。
理解するためにはdefun,(),case,if,quote,評価の順序などのLispの規則を知る必要がある。
文法規則の実装は、理想的には言語学の規則だけを使うべきだ。
大きな文法を開発する場合は、問題はさらに悪化して、文法を記述する人はますますLispに依存しなくてはならない。

という部分です。プログラミングやソフトウェア開発を学ぶ本で、「その言語に依存することは問題である」と言い切っている本は中々ないのではないでしょうか？

AIという分野が題材とはいえ、これは最近の「特定の言語を深く知っている俺って凄い」みたいな（一部の人達の）風潮に疑問を感じていた僕にとっては、なんだかとっても賛同したくなる一文でした.

第2章 簡単なLispプログラム