bulbのLisp日記

■ [PAIP][Chapter2]2.6 16:01

(defun generate-tree (phrase)
  "Generate a random sentence or phrase,
with a complete parse tree."
  (cond ((listp phrase)
	 (mapcar #'generate-tree phrase))
	((rewrites phrase)
	 (cons phrase
	       (generate-tree (random-elt (rewrites phrase)))))
	(t
	 (list phrase))))
#|
CL-USER> (generate-tree 'Sentence)
(SENTENCE (NOUN-PHRASE (NAME GUY))
          (VERB-PHRASE (VERB LIKED) (NOUN-PHRASE (PRONOUN SHE)) (PP*)))
CL-USER> (generate-tree 'Sentence)
(SENTENCE (NOUN-PHRASE (PRONOUN HE))
          (VERB-PHRASE (VERB HIT) (NOUN-PHRASE (PRONOUN SHE)) (PP*)))
|#

(defun generate-all (phrase)
  "Generate a list of all possible expansions of this phrase."
  (cond ((null phrase) (list nil))
	((listp phrase)
	 (combine-all (generate-all (first phrase))
		      (generate-all (rest phrase))))
	((rewrites phrase)
	 (mappend #'generate-all (rewrites phrase)))
	(t (list (list phrase)))
	))

(defun combine-all (xlist ylist)
  "Return a list of lists formed by appending a y to an x.
E.g., (combine-all '((a) (b)) '((1) (2)))
-> ((A 1) (B 1) (A 2) (B 2))."
  (mappend #'(lambda (y)
	       (mapcar #'(lambda (x) (append x y)) xlist))
	   ylist))

(generate-all 'sentence)

generate-allはスタックが溢れてしまう。sbclとxyzzyで試したけど。なんか間違っている？