A Straightforward Solution

フレーズ構築文法によるランダムセンテンスの生成プログラムを開発しましょう。もっとも直接的な方法はそれぞれの文法を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)))

それぞれの関数の定義は空の()というparameter listになります。これは引数をとらないという意味です。厳密に言えば、何も引数をとらない関数は同じ結果をいつも期待されるわけで、定数をつかうのですが、そこが通常の場合とは違います。しかしながら、今回作成しているのはrandom functionなので、引数がなくても異なる結果を返します。数学的な関数を返すのではなく、ここでは値を返すものを関数と呼びます。
残りはone-ofの定義です。これは一つのリストをとり、その中からランダムに一つ選び、listから選ばれたエレメントを一つ返します。最終的に文法上のすべての関数がwordのlistを返します。どのカテゴリから返ってきてもappendを自由に適用することができます。

(defun one-of (set)
  "setから一つ選び、リストにして返す"
  (list (random-elt set)))

(defun random-elt (choices)
  "listからrandomに一つの要素を選ぶ"
  (elf choices (random (length choices))))

eltとrandomという二つの関数があります。eltはlistから要素を拾いあげるものです。最初の引数はlistで2つめの引数はlistの位置です。混乱しがちなのは最初は0からはじまるところで、(elt choices 0)がlistが先頭の位置で、(elt choices 1)が2番目になります。positionの数値は0からn-1なので、それゆえ(random 4)は0,1,2,3のいずれかを返します。
ではnoun phraseとverb phraseからどんなランダムなセンテンスが生成されるかテストしてみましょう。

(sentence) => ...

...

(trace sentece noun-phrase verb-phrase article noun verb)

...
...(p 37)

プログラムは正しく動き、上記のtraceもサンプルのようにはなりましたが、オリジナルの文法ルールから考えるとLispでの定義は少々読みづらいようです。より複雑なルールを考えると問題になるでしょう。noun-phraseなどにいくつもの形容詞と前置詞がつくことを許すように変更したいものです。文法表現としては以下のようになります。

Noun-Phrase => Article + Adj* + Noun + PP*
Adj* => 0, Adj + Adj*
PP* => 0, PP + PP*
PP => Prep + Noun-phrase
Adj => big, little, blue, green...
Prep => to, in, by, with,...

この表現においては、0は選択されなかったことを示し、カンマはいくつかの別の選択肢で、アスタリスクはのnothing special、Lispにおけるシンボルの一部になります。しかしここでは便宜的に名前の最後のアスタリスクは0以上の回数の連続ということにします。PP*は0かそれ以上のPPの繰り返しです。これは数学者Stephan Cole Kleeneの名をとってKleene Star(あるいはclean-E)という表現で知られています。
問題はこのAdj*やPP*を含む状態をLispでどのように表現するかということです。例えば、

(defun Adj* ()
   (if (= (random 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)))

Adj*とPP*がそれぞれ別の実装になっています。しかしここは注意すればそんな必要はありません

(defun Adj* ()
   "注意、これは間違った形容詞の実装です"
   (one-of '(nil (append (Adj) (Adj*)))))
(defun Adj* ()
   "注意、これは間違った形容詞の実装です"
  (one-of (list (append (Adj) (Adj*)))))

最初の定義は( (append (Adj) (Adj*)))というリテラル表現のlistを返してるところが間違っています。2つ目の定義はAdj*はAdj*を含んでいるため、無限再帰の原因になります。シンプルな関数が、いまや複雑になってしまったということです。理解するためには、より多くのLispの道具(defun () case if quote)と実行時の順序のルール、ときには文法ルールの実装に理想的な言語的な道具を利用するべきである、ということになります。より大きな文法を開発しようとするなら、Lispにより深く依存していくことになるので問題はさらに悪化していきます。