Hatena::Groupcadr

bulbのLisp日記 RSSフィード

2008-01-06

[] 19:20 
 - bulbのLisp日記 を含むブックマーク

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


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

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

[][]英文生成Lisp 19:41 英文生成Lisp - bulbのLisp日記 を含むブックマーク はてなブックマーク - 英文生成Lisp - bulbのLisp日記

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:断熱の


[][]A Rule-Based Solution 20:36 A Rule-Based Solution - bulbのLisp日記 を含むブックマーク はてなブックマーク - A Rule-Based Solution - bulbのLisp日記

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)



文字化け 19:20 文字化け - bulbのLisp日記 を含むブックマーク はてなブックマーク - 文字化け - bulbのLisp日記

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

文字化けするなぁ。

utf-8m-dos

にするとうまくできた。