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

(defun generate (phrase)
  "Generate a random sentence or phrase"
  (format t "~A " phrase)
  (cond ((listp phrase)
     (progn
       (format t "mappend")
       (mappend #'generate phrase)))
    ((rewrites phrase)
     (progn
       (format t "generate")
       (generate (random-elt (rewrites phrase)))))
    (t
     (progn
       (format t "terminal")
       (list phrase)))))

#+nil
CL-USER> (generate 'sentence)
  0: (GENERATE SENTENCE)
SENTENCE generate    1: (GENERATE (NOUN-PHRASE VERB-PHRASE))
(NOUN-PHRASE VERB-PHRASE) mappend      2: (GENERATE NOUN-PHRASE)
NOUN-PHRASE generate        3: (GENERATE (ARTICLE NOUN))
(ARTICLE NOUN) mappend          4: (GENERATE ARTICLE)
ARTICLE generate            5: (GENERATE A)
A terminal            5: GENERATE returned (A)
          4: GENERATE returned (A)
          4: (GENERATE NOUN)
NOUN generate            5: (GENERATE WOMAN)
WOMAN terminal            5: GENERATE returned (WOMAN)
          4: GENERATE returned (WOMAN)
        3: GENERATE returned (A WOMAN)
      2: GENERATE returned (A WOMAN)
      2: (GENERATE VERB-PHRASE)
VERB-PHRASE generate        3: (GENERATE (VERB NOUN-PHRASE))
(VERB NOUN-PHRASE) mappend          4: (GENERATE VERB)
VERB generate            5: (GENERATE LIKED)
LIKED terminal            5: GENERATE returned (LIKED)
          4: GENERATE returned (LIKED)
          4: (GENERATE NOUN-PHRASE)
NOUN-PHRASE generate            5: (GENERATE (ARTICLE NOUN))
(ARTICLE NOUN) mappend              6: (GENERATE ARTICLE)
ARTICLE generate                7: (GENERATE THE)
THE terminal                7: GENERATE returned (THE)
              6: GENERATE returned (THE)
              6: (GENERATE NOUN)
NOUN generate                7: (GENERATE MAN)
MAN terminal                7: GENERATE returned (MAN)
              6: GENERATE returned (MAN)
            5: GENERATE returned (THE MAN)
          4: GENERATE returned (THE MAN)
        3: GENERATE returned (LIKED THE MAN)
      2: GENERATE returned (LIKED THE MAN)
    1: GENERATE returned (A WOMAN LIKED THE MAN)
  0: GENERATE returned (A WOMAN LIKED THE MAN)
(A WOMAN LIKED THE MAN)