A Rule-Based Solution

このプログラムの別の実装に文法記述に集中し、開発の進行についてはあとで心配するという方法があります。もう一度オリジナルの文法ルールを見てみましょう

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 ...

それぞれのルールはArrowの左側のシンボルと右がわに分かれます。右側は"Noun-Phrase => Article + Noun"のうちの"Article + Noun"のようなシンボルのlistか"Noun => man,ball..."のようにwordのlistになります。すべてのルールは連結リストで表現された右辺であるとし、"Article + Noun"を"(Article Noun)"のようにLispのlistで表現するというふうにしてみましょう。このルールのリストは以下のようになります。

(defparameter *simple-grammar*
   '((sentence -> (noun-phrase verb-phrase))
     (noun-phrase -> (Article Noun))
     (Article -> the a)
     (Noun -> man ball woman table)
     (Verb -> hit took saw liked)
    "ちっちゃな英文法")
(defvar *grammar* *simple-grammar*)

Lisp versionのrulesはオリジナルルールのまねです。事実、"->"というシンボルを含んでいますが、これは実際にはなにもしないただの飾りです。
special formのdefvarとdefparameterは共に値を特殊変数に結びつけます。違いは*grammar*のような値はプログラムの実行中にその内容を変更することができます。*simple-grammar*のようなparameterは通常は定数となります。parameterを変えるのがprogramが変更するのか、programによって変更されないのかを考慮されます。
一旦ルールのlistが定義されると、与えられたカテゴリシンボルによって書きかえることがおこるでしょう。assoc関数はこういった仕事にたいしてデザインされています。assocは二つの引数、keyとlistのlistをとり、listのlistの最初の要素がkeyとマッチしたlistを返します。もしみつからなければnilがかえります。例をあげておきます

 -> (assoc 'noun *grammar*) => (NOUN -> MAN BALL WOMAN TABLE)

ルールがlistだとかなり実装は簡単ですし、ルールを操作する関数定義による抽象化というのもいい考えです。3つの関数を用意する必要があります。ひとつは右辺を取得する関数。もうひとつは左辺を取得する関数。最後に書き換え可能なカテゴリを発見する関数です。

(defun rule-lhs (rule)
   "ルールの左辺"
   (first rule))
(defun right-lhs (rule)
   "ルールの右辺"
   (rest (rest rule)))
(defun rewrites (category)
   "このカテゴリの書き換え可能なlistを返す"
  (rule-rhs (assoc category *grammar*)))

これらの関数定義はプログラムを簡単に読めるようにし、簡単にかけるようにし、さらにルールの変更を用意にするので、これを使うようにすべきです。
さて、主要な問題までの準備がととのいました。関数定義によってsentence(あるいはnoun-phraseやその他のカテゴリ)を生成するようになりました。この関数をgenerateと呼ぶことにしましょう。3つのケースについて議論してみましょう。(1)もっとも単純なケース、generateが関連した書きかえ可能なルールのセットをもつシンボルにパスした場合。それらの中から一つをランダムに選択し、そこから生成します。(2)もし、シンボルが書きかえ可能なルールをもつセットだった場合、それは終端のシンボル(wordのような文法カテゴリ)であり、そこから離れなければなりません。実際には、入力wordのリストを返し、以前のプログラムと同じようにwordのlistにして返します。(3)同じ場合に
書き換えシンボルがあった場合には、symbolのlistの一つをひろいあげ、そこから生成します。そして、generateはlistの入力をうけとり、それぞれのlistを生成し、すべてを連結します。下記のとおり、generateの最初のclauseはこれを扱い、2番目のclauseが(1)を3番目が(2)を扱います。ここでは1.7でつかったmappend関数を使っています。

(defun generate (phrase)
   "ランダムセンテンスやフレーズを生成する"
   (cpmd ((listp phrase)
              (mappend #'generate phrase))
             ((rewrites phrase)
              (generate (random-elt (rewries phrase))))
             (t (list phrase))))

この本の多くのプログラムにおいて、この関数は短いですが、情報がつまっています。つまり、プログラムの技芸とは何を書き、何を書かないかを知ることだ、ということです。
こういったプログラミングのスタイルをdata driven programmingと呼びます。なぜなら、data(categoryに関連した書き換えlist)がプログラムが次に何をすべきかをdriveするからです。Lispでは簡単で自然であり、dataに新しく情報を追加したり取り除いたりするだけなので、プログラムを正しく拡張しやすくするのです。
いくつか例をつくってみましょう

(generate 'sentence) => ...

(省略)

generateにはいくつか書きかたがあります。以下のものはcondのかわりにifをつかったversionです

(defun generate (phrase)
   "ランダムなセンテンスやフレーズを生成する"
   (if (listp phrase)
      (mappend #'generate phrase)
      (let ((choices (rewrites phrase))
         (if (null choices)
             (list phrase)
             (generate (random-elt choices))))))

このversionではspecial formのletを使用しています。新たな変数を導き(この場合はchoices)変数に値をむすびつけます。この場合では変数を導き、保存するのにrewrites関数が2回呼ばれ、cond versionのgenerateとかわりません。letの構文はつぎのものです

(let ((var value) ...)
  body-containings-vars)

letは変数を導くのにもっともありふれた方法ですが、関数のパラメータではありません。letで導かずに一時変数を使用することはできません

(defun generate (phrase)
  (setf choices ...)  ;;wrong
    choices ...)

これの悪い点はchoicesシンボルがspecialにもglobalからも参照され、他の関数に共有され変更されたりするのです。それゆえ、generate関数には信頼性がなく、一度choicesに値をセットしたあとで、参照しても同じ値を参照するという保証がないのです。letは自分だけがアクセスすることができる新しい変数を導くので、正確な値を維持できるのです。

Exercise 2.1 [m] condを使用するがrewritesを2回呼ばないようなgenerateを書きなさい

Exercise 2.2 [m] 終端シンボルと非終端シンボルがはっきり区別できるようなgenerateを書きなさい