3.2 Special Forms

p.50-53

3.1, 3.2は、Norvig先生からLispの書き方を教わっている感じですね。

とてもためになります。

Lispで構造体。

(defstrruct name
    first
  (middle nil)
  last)

(setf b (make-name :first 'Paul :last 'Graham))

(name-first b)
#=> PAUL

(name-middle b)
#=> NIL

(name-last b)
#=> GRAHAM

(name-p b)
#=> T

(name-p 'Paul)
#=> NIL

(setf (name-middle b) 'Q)
#=> Q

b
#=> #S(NAME :FIRST PAUL :MIDDLE Q :LAST GRAHAM)

(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で試したけど。なんか間違っている？

(defun cross-product (fn xlist ylist)
  (mappend #'(lambda (y)
	       (mapcar #'(lambda (x) (funcall fn x y))
		       xlist))
	   ylist))

(defun combine-all2 (xlist ylist)
  (cross-product #'append xlist ylist))

#|
CL-USER> (cross-product #'+ '(1 2 3) '(10 20 30))
(11 12 13 21 22 23 31 32 33)
CL-USER> (cross-product #'* '(1 2 3) '(10 20 30))
(10 20 30 20 40 60 30 60 90)
CL-USER> (cross-product #'- '(1 2 3) '(10 20 30))
(-9 -8 -7 -19 -18 -17 -29 -28 -27)
CL-USER> (cross-product #'list '(a b c d e f g h)
			'(1 2 3 4 5 6 7 8))

((A 1) (B 1) (C 1) (D 1) (E 1) (F 1) (G 1) (H 1) (A 2) (B 2) (C 2) (D 2) (E 2)
 (F 2) (G 2) (H 2) (A 3) (B 3) (C 3) (D 3) (E 3) (F 3) (G 3) (H 3) (A 4) (B 4)
 (C 4) (D 4) (E 4) (F 4) (G 4) (H 4) (A 5) (B 5) (C 5) (D 5) (E 5) (F 5) (G 5)
 (H 5) (A 6) (B 6) (C 6) (D 6) (E 6) (F 6) (G 6) (H 6) (A 7) (B 7) (C 7) (D 7)
 (E 7) (F 7) (G 7) (H 7) (A 8) (B 8) (C 8) (D 8) (E 8) (F 8) (G 8) (H 8))
|#

3.1 A Guide to Lisp Style

p.48-50

明確に書くこと。
抽象化しろ。
簡潔に書くこと。
すでにあるLisp関数を使うこと。
一貫性。

まだAIまでたどり着いてないですが、

この本は、Common Lispを学ぶには良いですよ。

(英文も多分やさしい方だと思います)

前の関数generateは、(rewrites phrase) を2回使用していて冗長なため、

次のように変更。

ちなみに let を使用しますよ。

(defun generate (phrase)
  "Generate a random sentence or phrase"
  (if (listp phrase)
      (mappend #'generate phrase)
      (let ((choices (rewrites phrase)))
	(if (null choices)
	    (list phrase)
	    (generate (random-elt choices))))))
#|
CL-USER> (generate 'sentence)
(A MAN LIKED THE TABLE)
CL-USER> (generate 'sentence)
(THE WOMAN TOOK THE BALL)
CL-USER> (generate 'sentence)
(A WOMAN SAW THE TABLE)
|#

setf を使用して代入なんかしちゃだめ。

generate を cond を使用して書きます。

;; Exercise 2.1

(defun generate (phrase)
  (let ((choices nil))
    (cond ((listp phrase)
	   (mappend #'generate phrase))
	  ((setf choices (rewrites phrase))
	   (generate (random-elt choices)))
	  (t
	   (list phrase)))))
#|
CL-USER> (generate 'sentence)
(THE WOMAN HIT A TABLE)
CL-USER> (generate 'sentence)
(THE TABLE LIKED A MAN)
|#

いきなり意味がわからなかったため答えを見る。

あぁ、明示的に終端と非終端を区別せよか。

答えは以下。

(defun generate (phrase)
  (cond ((listp phrase)
	 (mappend #'generate phrase))
	((non-terminal-p phrase)
	 (generate (random-elt (rewrites phrase))))
	(t
	 (list phrase))))

(defun non-terminal-p (category)
  (not (null (rewrites category))))

#|
CL-USER> (generate 'sentence)
(THE WOMAN TOOK A WOMAN)
CL-USER> (generate 'sentence)
(A WOMAN HIT THE TABLE)
|#

grammar を増やしますよ。

(defparameter *bigger-grammar*
  '((sentence -> (noun-phrase verb-phrase))
    (noun-phrase -> (Article Adj* Noun PP*) (Name) (Pronoun))
    (verb-phrase -> (Verb noun-phrase PP*))
    (PP* -> () (PP PP*))
    (Adj* -> () (Adj Adj*))
    (PP -> (Prep noun-phrase))
    (Prep -> to in by with on)
    (Adj -> big little bule green adiabatic)
    (Article -> the a)
    (Name -> Peter Paul Seibel Guy Steel)
    (Noun -> man ball woman table)
    (Verb -> hit took saw liked)
    (Pronoun -> he she it these those that)))

(setf *grammar* *bigger-grammar*)

#|
CL-USER> (generate 'sentence)
(THE ADIABATIC LITTLE GREEN WOMAN SAW THE MAN ON HE)
CL-USER> (generate 'sentence)
(THE MAN TO A GREEN TABLE WITH STEEL ON A LITTLE MAN TO THE TABLE BY SEIBEL IN
     THAT TOOK THE ADIABATIC LITTLE TABLE IN SHE WITH A BULE GREEN WOMAN TO GUY
     BY PAUL ON STEEL)
CL-USER> (generate 'sentence)
(PETER TOOK SHE)
|#

英文の結果がまだ変ですね。

でもこれがAIへの入り口？

PAIPをちょっぴり予習?

Chapter1-3:INTRODUCTION TO COMMON LISP

Chapter4-8:EARLY AI PROGRAMS この章からAIに突入。

Chapter9-14:TOOLS AND TECHNIQUES

Chapter15-21:ADVANCED AI PROGRAMS

Chapter22-25:THE REST OF LISP

全900ページ!!

ソースはすべて公開されています。

http://norvig.com/paip/README.html

とりあえず、写経しながら進めていく予定です。

(ここは書きかけです。間違っているかもしれません)

Chapter1は、Common Lisp初心者用らしいですので、とりあえず飛ばしていきます。

英文生成

こんなルール

Sentence => Noun-Phrase + Verb-Phrase

Noun-Phrase => Article + Noun

Verb-Phrase => Verb + Noun-Phrase

Article => the, a, ...

Noun => man, ball, ...

Verb => hit, took, saw, ...

(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 random."
  (elt choices (random (length choices))))

ちなみに環境は、CarbonEmacs + SLIME + SBCL です。

CL-USER> (sentence)
(THE BALL TOOK A BALL)
CL-USER> (sentence)
(THE BALL HIT THE MAN)
CL-USER> (sentence)
(THE MAN LIKED THE WOMAN)
CL-USER> (sentence)
(A BALL HIT THE MAN)
CL-USER> (noun-phrase)
(THE MAN)
CL-USER> (verb-phrase)
(SAW THE TABLE)

traceにかけてみる。

CL-USER> (trace sentence noun-phrase verb-phrase article noun verb)
(SENTENCE NOUN-PHRASE VERB-PHRASE ARTICLE NOUN VERB)
CL-USER> (sentence)
  0: (SENTENCE)
    1: (NOUN-PHRASE)
      2: (ARTICLE)
      2: ARTICLE returned (THE)
      2: (NOUN)
      2: NOUN returned (BALL)
    1: NOUN-PHRASE returned (THE BALL)
    1: (VERB-PHRASE)
      2: (VERB)
      2: VERB returned (SAW)
      2: (NOUN-PHRASE)
        3: (ARTICLE)
        3: ARTICLE returned (THE)
        3: (NOUN)
        3: NOUN returned (BALL)
      2: NOUN-PHRASE returned (THE BALL)
    1: VERB-PHRASE returned (SAW THE BALL)
  0: SENTENCE returned (THE BALL SAW THE BALL)
(THE BALL SAW THE BALL)

ルールを追加。

Noun-Phrase => Article+Adj*+Noun+PP*

Adj* => 0,Adj+Adj*

PP* => 0,PP+PP*

PP => Prep+Noun-Phrase

Adj => big,litle,red, ...

Prep => to,in,on,by, ...

(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)))

CL-USER> (untrace sentence noun-phrase verb-phrase article noun verb)
T
CL-USER> (sentence)
(A LITTLE BLUE MAN HIT A TABLE IN A WOMAN BY A TABLE WITH A MAN ON THE BIG
 ADIABATIC MAN IN THE MAN)

adiabatic:断熱の

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

上記を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))
  "A grammar for a trivial subset of English.")

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

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

(defun rule-lhs (rule)
  "The left-hand side of a rule."
  (first rule))
(defun rule-rhs (rule)
  "The right-hand side of a rule."
  (rest (rest rule)))
(defun rewrites (category)
  "Return a list of the possible rewrites for this category."
  (rule-rhs (assoc category *grammar*)))
(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))))
CL-USER> (generate 'sentence)
(THE MAN TOOK A WOMAN)
CL-USER> (generate 'sentence)
(THE MAN SAW THE MAN)

carbon emacs + simple-hatena-mode なんですが、

文字化けするなぁ。

utf-8m-dos

にするとうまくできた。