2008年11月30日日曜日

【PAIP】6 Building Software Tools (その2)

引き続き、6.2 A pattern-matching tool。

  • 6.2 A pattern-matching tool
  • おお、pattern/actionペアをテーブルにいれて拡張性を担保するプログラミングスタイルを、data-driven programmingと言うのか。正直知らんかった。
  • "In this case, the keys to the table will be symbols (like ?*), and it is fine if the representation of the table is distributed across memory. Thus, property lists are an appropriate choice." なるほど。こういう風に判断するのか。
  • あとはソースを追う。例によって日本語のコメントは私、その他はNorvig。

    ;;; 6.2 A Pattern-Matching Tool

    ;;; これらはgeneralized single patの例
    #+test
    (pat-match '(x = (?is ?n numberp)) '(x = 34)) ; => ((?n . 34))

    #+test
    (pat-match '(x = (?is ?n numberp)) '(x = x)) ; => nil

    #+test
    (pat-match '(?x (?or < = >) ?y) '(3 < 4)) ; => ((?Y . 4) (?X . 3))

    #+test
    (pat-match '(x = (?and (?is ?n numberp) (?is ?n oddp)))
    '(x = 3)) ; => ((?N . 3))

    #+test
    (pat-match '(?x /= (?not ?x)) '(3 /= 4)) ; => ((?X . 3))

    #+test
    (pat-match '(?x > ?y (?if (> ?x ?y))) '(4 > 3)) ; => ((?Y . 3) (?X . 4))


    (defun pat-match (pattern input &optional (bindings no-bindings))
    "Match pattern against input in the context of the bindings"
    (cond ((eq bindings fail) fail)
    ((variable-p pattern)
    (match-variable pattern input bindings))
    ((eql pattern input) bindings)
    ((segment-pattern-p pattern)
    (segment-matcher pattern input bindings)) ; segment-match -> segment-matcher
    ((single-pattern-p pattern) ; ***
    (single-matcher pattern input bindings)) ; ***
    ((and (consp pattern) (consp input))
    (pat-match (rest pattern) (rest input)
    (pat-match (first pattern) (first input)
    bindings)))
    (t fail)))
    ;; pat-match ver.6
    ;; *** の節を追加。


    (defconstant fail nil "Indicates pat-match failure")

    (defconstant no-bindings '((t . t))
    "Indicates pat-match success, with no variables.")

    (defun variable-p (x)
    "Is x a variable (a symbol beginning with '?')?"
    (and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

    (defun get-binding (var bindings)
    "Find a (variable . value) pair in a binding list."
    (assoc var bindings))

    (defun binding-var (binding)
    "Get the variable part of a single binding."
    (car binding))

    (defun binding-val (binding)
    "Get the value part of a single binding."
    (cdr binding))

    (defun make-binding (var val) (cons var val))

    (defun lookup (var bindings)
    "Get the value part (for var) from a binding list."
    (binding-val (get-binding var bindings)))

    (defun extend-bindings (var val bindings)
    "Add a (var . value) pair to a binding list."
    (cons (cons var val)
    ;; Once we add a "real" binding,
    ;; we can get rid of the dummy no-bindings
    (if (eq bindings no-bindings)
    nil
    bindings)))

    (defun match-variable (var input bindings)
    "Does VAR match input? Uses (or updates) and returns bindings."
    (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
    ((equal input (binding-val binding)) bindings)
    (t fail))))

    (setf (get '?is 'single-match) 'match-is)
    (setf (get '?or 'single-match) 'match-or)
    (setf (get '?and 'single-match) 'match-and)
    (setf (get '?not 'single-match) 'match-not)
    (setf (get '?* 'segment-match) 'segment-match)
    (setf (get '?+ 'segment-match) 'segment-match+)
    (setf (get '?? 'segment-match) 'segment-match?)
    (setf (get '?if 'segment-match) 'match-if)

    (defun segment-pattern-p (pattern)
    "Is this a segment-matching pattern like ((?* var) . pat)?"
    (and (consp pattern) (consp (first pattern))
    (symbolp (first (first pattern)))
    (segment-match-fn (first (first pattern)))))

    (defun single-pattern-p (pattern)
    "Is this a single-matching pattern?
    E.g. (?is x predicate) (?and . patterns) (?or . patterns)."
    (and (consp pattern)
    (single-match-fn (first pattern))))

    (defun segment-matcher (pattern input bindings)
    "Call the right function for this kind of segment pattern."
    (funcall (segment-match-fn (first (first pattern)))
    pattern input bindings))

    (defun single-matcher (pattern input bindings)
    "Call the right function for this kind of single pattern."
    (funcall (single-match-fn (first pattern))
    (rest pattern) input bindings))

    (defun segment-match-fn (x)
    "Get the segment-match function for x,
    if it is a symbol that has one."
    (when (symbolp x) (get x 'segment-match)))

    (defun single-match-fn (x)
    "Get the single-match function for x,
    if it is a symbol that has one."
    (when (symbolp x) (get x 'single-match)))

    (defun match-is (var-and-pred input bindings)
    "Succeed and bind var if the input satisfies pred,
    where var-and-pred is the list (var pred)."
    (let* ((var (first var-and-pred))
    (pred (second var-and-pred))
    (new-bindings (pat-match var input bindings))) ; =1=
    (if (or (eq new-bindings fail)
    (not (funcall pred input))) ; =2=
    fail
    new-bindings)))
    ;; =1= : まず、varでpat-matchしちゃう。
    ;; =2= : =1=がfailするか、inputがpredでないならば、もともとのbindingsを返却。
    ;; ここで、なぜpredの対象がinputでいいんだろ???
    ;; =3= : =1=が成功したら、new-bindingsを返却。


    (defun match-and (patterns input bindings)
    "Succeed if all the patterns match the input."
    (cond ((eq bindings fail) fail)
    ((null patterns) bindings) ; =1=
    (t (match-and (rest patterns) input ; =2=
    (pat-match (first patterns) input
    bindings)))))
    ;; =1= : 再帰の終了条件。patternsがnilならbindingsを返して終了。
    ;; =2= : patternsのfirstでpat-matchしたbindingsでpatternsのrestをpatternsとして再帰。

    (defun match-or (patterns input bindings)
    "Succeed if any one of the patterns match the input."
    (if (null patterns)
    fail ; =1=
    (let ((new-bindings (pat-match (first patterns) ; =2=
    input bindings)))
    (if (eq new-bindings fail)
    (match-or (rest patterns) input bindings) ; =3=
    new-bindings)))) ; =4=
    ;; =1= : 再帰の終了条件。pattensがnilならfail。
    ;; =2= : patternsのfirstがpat-matchするかをnew-bindingsへ。
    ;; =3= : =2=がfailしたらpatternsのrestで再帰。
    ;; =4= : =2=が成功なら、new-bindingsを返却。


    (defun match-not (patterns input bindings)
    "Succeed if none of the patterns match the input.
    This will never bind any variables."
    (if (match-or patterns input bindings)
    fail
    bindings))

    (defun segment-match (pattern input bindings &optional (start 0))
    "Match the segment pattern ((?* var) . pat) against input."
    (let ((var (second (first pattern)))
    (pat (rest pattern)))
    (if (null pat)
    (match-variable var input bindings)
    ;; We assume that pat starts with a constant
    ;; In other words, a pattern can't have 2 consecutive vars
    (let ((pos (first-match-pos (first pat) input start))) ; =3.1=
    (if (null pos)
    fail
    (let ((b2 (pat-match pat (subseq input pos)
    (match-variable var (subseq input 0 pos)
    bindings))))
    ;; If this match failed, try another longer one
    (if (eq b2 fail)
    (segment-match pattern input bindings (+ pos 1))
    b2)))))))
    ;; segment-match ver.3
    ;; 変更点のみ記載。
    ;; =3.1= position -> first-match-pos

    (defun first-match-pos (pat1 input start)
    "Find the first position that pat1 could possibly match input,
    starting at position start. If pat1 is non-constant, then just
    return start."
    (cond ((and (atom pat1) (not (variable-p pat1))) ; =1=
    (position pat1 input :start start :test #'equal))
    ((< start (length input)) start) ; =2=
    (t nil))) ; =3=
    ;; =1= : 以前のsegment-matchと同じ処理
    ;; =2= : =1=の条件が合致しない場合は何らかの変数的なものなので、startがinputより長くなってなければstartをそのまま返す。
    ;; =3= : startがinputより長いのでこれはposは無い。よってnil。

    (defun segment-match+ (pattern input bindings)
    "Match one or more elements of input."
    (segment-match pattern input bindings 1))

    (defun segment-match? (pattern input bindings)
    "Match zero or one element of input."
    (let ((var (second (first pattern)))
    (pat (rest pattern)))
    (or (pat-match (cons var pat) input bindings) ; =1=
    (pat-match pat input bindings)))) ; =2=
    ;; =1= : 1つマッチする場合の処理。??を外したvarを、残余なpatにconsしたpatternにてマッチするか。
    ;; =2= : 0個マッチする場合の処理。残余なpatをpatternにしててマッチするか。
    ;; =1=, =2= いずれも失敗したらnil。


    (defun match-if (pattern input bindings)
    "Test an arbitrary expression involving variables.
    The pattern looks like ((?if code) . rest)."
    (and (progv (mapcar #'car bindings) ; =1=
    (mapcar #'cdr bindings)
    (eval (second (first pattern))))
    (pat-match (rest pattern) input bindings))) ; =2=
    ;; =1= : おお! progvだ!
    ;; そうかprogvだとこういう形で変数と値の束縛構成もlisp formでできるんだ。そこがletとの大きな違いだったのか。
    ;; ここでprogvを使うのは、evalに束縛を効かせるためかな。
    ;; そしてそれがevalの結果、tかnilかと。
    ;; =2= : それがtなら(rest patterns)についてpat-matchする、と。

    #+test
    (pat-match '(?x ?op ?y is ?z (?if (eql (?op ?x ?y) ?z)))
    '(3 + 4 is 7)) ; => error
    ;; これは間違いじゃないか???

    #+test
    (pat-match '(?x ?op ?y is ?z (?if (eql (funcall ?op ?x ?y) ?z)))
    '(3 + 4 is 7))
    ;; 正しくはこうじゃないといけないのでは?
    ;; Norvigのerrataをみてみると、、、やはり!!
    ;; http://norvig.com/paip-errata.html

    #+test
    (pat-match '(?x ?op ?y (?if (funcall ?op ?x ?y)))
    '(3 > 4))

    (defun pat-match-abbrev (symbol expansion)
    "Define symbol as a macro standing for a pat-match pattern."
    (setf (get symbol 'expand-pat-match-abbrev)
    (expand-pat-match-abbrev expansion)))

    (defun expand-pat-match-abbrev (pat)
    "Expand out all pattern matching abbreviations in pat."
    (cond ((and (symbolp pat) (get pat 'expand-pat-match-abbrev)))
    ((atom pat) pat)
    (t (cons (expand-pat-match-abbrev (first pat))
    (expand-pat-match-abbrev (rest pat))))))

    #+test
    (pat-match-abbrev '?x* '(?* ?x)) ; => (?* ?X)

    #+test
    (pat-match-abbrev '?y* '(?* ?y)) ; => (?* ?Y)

    #+test
    (setf axyd (expand-pat-match-abbrev '(a ?x* ?y* d))) ; => (A (?* ?X) (?* ?Y) D)

    #+test
    (pat-match axyd '(a b c d)) ; => ((?Y B C) (?X))


今回はここまで。おもしろかった!
やっぱり流し読みよりも、ちゃんとやった方がおもしろい。
こつこつ。

2008年11月29日土曜日

【PAIP】6 Building Software Tools

今週はビジネススキルアップセミナーのようなものにごりごり出席しなければならなかった。これはこれでためになる。が!プログラミングの勉強は停滞した。でも総合力は前進できたと思うのでポジティブにとらえたい。さて、PAIP。

  • 6.1 An Interactive Interpreter Tool
  • REPL構造をツール化

  • 6.2 A Pattern-Matching Tool
  • Elizaのpat-matchをツール化
  • ツール化にあたってかなりの機能追加。こうなるとlistの正規表現マッチャという範囲をこえてるな。というのは、字面だけではなく、numberpだとかoddpだとか、objectとしての意味を問うているから。

  • ここはちょっと丁寧にやりたい気分。ソースとコメントでやる。ソースはPeter Norvigのもの、日本語のコメントは私のもの。
  • まずElizaのpat-matchを復習。

    (defun pat-match (pattern input)
    "Does pattern match input? Any variable can match anything."
    (if (variable-p pattern)
    t
    (if (or (atom pattern) (atom input))
    (eql pattern input)
    (and (pat-match (first pattern) (first input))
    (pat-match (rest pattern) (rest input))))))
    ;; pat-match ver.1
    ;; マッチしたかどうかをT/NILで返すだけ。
    ;; ツリー再帰的

    (defun variable-p (x)
    "Is x a variable (a symbol beginning with '?')?"
    (and (symbolp x) (equal (char (symbol-name x) 0) #\?)))

    #+test
    (pat-match '(I need a ?X) '(I need a vacation)) ; => T
    #+test
    (pat-match '(I need a ?X) '(I really need a vacation)) ; => NIL

    (sublis '((?X . vacation))
    '(what would it mean to you if you got a ?X ?))
    ; => (WHAT WOULD IT MEAN TO YOU IF YOU GOT A VACATION ?)

    ;; sublisは、パターンマッチとして得られた変数と値の
    ;; 組みをつかって別のリストを変換するのに使える。

    (defun pat-match (pattern input)
    "Does pattern match input? WARNING: buggy version."
    (if (variable-p pattern)
    (list (cons pattern input))
    (if (or (atom pattern) (atom input))
    (eql pattern input) ; =1=
    (append (pat-match (first pattern) (first input))
    (pat-match (rest pattern) (rest input))))))
    ;; pat-match ver.2 buggy version
    ;; '((?X . vacation))のような、マッチ結果のa-listを返すようにしようとしている。
    ;; しかし、
    #+test
    (pat-match '(I need a ?X) '(I need a vacation))
    ;; とするとエラーとなる。=1=のところTを返すだけで、それがappendの引数になるから。

    (defconstant fail nil "Indicates pat-match failure")

    (defconstant no-bindings '((t . t))
    "Indicates pat-match success, with no variables.")

    (defun get-binding (var bindings)
    "Find a (variable . value) pair in a binding list."
    (assoc var bindings))

    (defun binding-val (binding)
    "Get the value part of a single binding."
    (cdr binding))

    (defun lookup (var bindings)
    "Get the value part (for var) from a binding list."
    (binding-val (get-binding var bindings)))

    (defun extend-bindings (var val bindings)
    "Add a (var . value) pair to a binding list."
    (cons (cons var val) bindings))

    (defun pat-match (pattern input &optional (bindings no-bindings))
    "Match pattern against input in the context of the bindings"
    (cond ((eq bindings fail) fail) ; =1=
    ((variable-p pattern) ; =2=
    (match-variable pattern input bindings))
    ((eql pattern input) bindings) ; =3=
    ((and (consp pattern) (consp input)) ; =4=
    (pat-match (rest pattern) (rest input)
    (pat-match (first pattern) (first input)
    bindings)))
    (t fail))) ; =5=
    ;; pat-match ver.3
    ;; bindingsを返す。
    ;; bindingsは、マッチした場合は、変数と値のalist。マッチに失敗した場合はFAIL。マッチしたけど変数がないときはNO-BINDINGS。
    ;;
    ;; =1= : bindingsがfail(nil) -> とにかくfailを返す。fail確定。
    ;; =2= : variable -> match-variableへ
    ;; =3= : variableじゃなくて、eqlで等価なもの -> それはそれでよくて継続していく。
    ;; =4= : 以上にあてはまらなく両者ともconsp -> 再帰。ただしfirstをさきにやって、そのbindingsをrestで使う。
    ;; =5= : ここまできたらもうfail。


    (defun match-variable (var input bindings)
    "Does VAR match input? Uses (or updates) and returns bindings."
    (let ((binding (get-binding var bindings)))
    (cond ((not binding) (extend-bindings var input bindings))
    ((equal input (binding-val binding)) bindings)
    (t fail))))
    ;; pat-matchの副関数
    ;; manage-bindingsとかの名前の方がしっくりくるような?

    (defun extend-bindings (var val bindings)
    "Add a (var . value) pair to a binding list."
    (cons (cons var val)
    ;; Once we add a "real" binding,
    ;; we can get rid of the dummy no-bindings
    (if (eq bindings no-bindings)
    nil
    bindings)))

    #+test
    (pat-match '(i need a ?x) '(i need a vacation)) ; => ((?X . VACATION))

    #+test
    (sublis (pat-match '(i need a ?X) '(i need a vacation))
    '(what would it mean to you if you got a ?X ?))
    ; => (WHAT WOULD IT MEAN TO YOU IF YOU GOT A VACATION ?)

    #+test
    (pat-match '(i need a ?X) '(i really need a vacation)) ; => NIL

    #+test
    (pat-match '(this is easy) '(this is easy)) ; => ((T . T))

    #+test
    (pat-match '(?X is ?X) '((2 + 2) is 4)) ; => NIL

    #+test
    (pat-match '(?X is ?X) '((2 + 2) is (2 + 2))) ; => ((?X 2 + 2))

    #+test
    (pat-match '(?P need . ?X) '(i need a long vacation)) ; => ((?X A LONG VACATION) (?P . I))
    ;; これの動作分析。
    ;; pat-matchの=4=はfirst restなので、dotted-pairでももちろん動作する。
    ;; ただし、patternに関しては、それが最後の要素となる。
    ;; inputが同様のdotted-listなら、通常の動作と変わらない。
    ;; inputが通常のリストの場合、その要素のマッチ対象はリストになるのでその要素は変数じゃないとマッチしない。
    ;; 変数だった場合は、その変数の値はリストとなる。


    ;;; 5.3 Segment Pattern Matching

    (defun pat-match (pattern input &optional (bindings no-bindings))
    "Match pattern against input in the context of the bindings"
    (cond ((eq bindings fail) fail) ; =1=
    ((variable-p pattern) ; =2=
    (match-variable pattern input bindings))
    ((eql pattern input) bindings) ; =3=
    ((segment-pattern-p pattern) ; =6=
    (segment-match pattern input bindings))
    ((and (consp pattern) (consp input)) ;= 4=
    (pat-match (rest pattern) (rest input)
    (pat-match (first pattern) (first input)
    bindings)))
    (t fail))) ; =5=
    ;; pat-match ver.4
    ;; ?*を導入して0を含む任意個の要素の連続とマッチすることを可能とする。
    ;; =1= : 無変更。
    ;; =2= : 無変更。
    ;; =3= : 無変更。
    ;; =6= : 新設。patternがsegment-patternの場合 -> segment-matchへ
    ;; =4= : 無変更。
    ;; =5= : 無変更。

    #+test
    (pat-match '((?* ?p) need (?* ?x))
    '(Mr Hulot and I need a vacation)) ; => ((?P MR HULOT AND I) (?X A VACATION))

    #+test
    (pat-match '((?* ?p) need (?* ?x))
    '(need a vacation)) ; => ((?P) (?X A VACATION))

    #+test
    (pat-match '((?* ?x) is a (?* ?y)) '(what he is is a fool)) ; => ((?X WHAT HE IS) (?Y FOOL))

    #+test
    (pat-match '((?* ?x) a b (?* ?x)) '(1 2 a b a b 1 2 a b)) ; => NIL
    ;; なぜこれがNILになるか。
    ;; pat-match :
    ;; まず第一のセグメントについて、=6=でsegment-matchに入る
    ;; segment-match :
    ;; ?x (1 2) でいけるか、となる。
    ;; そのとき、問題はsegment-matchの=5=によって、(pat-match pat (subseq input pos) bindings)となる。
    ;; すなわちpat (a b (?* ?x)) input (a b a b 1 2 a b)がマッチしますか?ということ。これはマッチする。
    ;; なので、=7=にいくが、しかしそのときの?Xのbindingsは(a b 1 2 a b)なので=7=がfailしておしまい。
    ;; 問題は=7=をどうするか、だ。


    (defun segment-match (pattern input bindings &optional (start 0))
    "Match the segment pattern ((?* var) . pat) against input."
    (let ((var (second (first pattern)))
    (pat (rest pattern)))
    (if (null pat)
    (match-variable var input bindings)
    ;; We assume that pat starts with a constant
    ;; In other words, a pattern can't have 2 consecutive vars
    (let ((pos (position (first pat) input
    :start start :test #'equal)))
    (if (null pos)
    fail
    (let ((b2 (pat-match pat (subseq input pos)
    (match-variable var (subseq input 0 pos)
    bindings)))) ; =8=
    ;; If this match failed, try another longer one
    (if (eq b2 fail)
    (segment-match pattern input bindings (+ pos 1)) ; =9=
    b2))))))) ; =10=
    ;; segment-match ver.2
    ;; 変更点のみ記載。
    ;; =8= : b2をしらべる際のbindingsに、varの現状のbinding案をいれてしまう。なので、先の例で=7=でunmatchしていたのはこの時点でfailする。
    ;; =9= : b2が失敗した場合。varのマッチ範囲を広げて再帰。
    ;; =10= : b2が成功した場合。これが答なので返すのみ。

    #+test
    (pat-match '((?* ?x) a b (?* ?x)) '(1 2 a b a b 1 2 a b)) ; => ((?X 1 2 A B))

  • ここまではちゃんと理解できたと思う。

とりあえず一区切り。次は、6.2節を丁寧にやる。
こつこつ。

2008年11月25日火曜日

【PAIP】5 ELIZA: Dialog with a Machine (その2)

5.3 Segment Pattern Matchingから。

  • 5.3 Segment Pattern Matching
  • リストを処理していく関数というのは、なんというか、リストの要素を語とする有限オートマトンを処理していくみたいな感じなんだな。
  • で、condなどによる分岐は非決定性みたいだったり。
  • これでパターンマッチャーができた。リストの正規表現機構を自前でつくったような感じだな。

  • 5.4 The ELIZA Program: A Rule-Based Translator
  • パターンマッチ、という手法と、ルールベーストランスレータ、という手法。この章はこれらの説明につきる感じ。
  • これ、かっこいいなぁ。

    (defun use-eliza-rules (input)
    "Find some rule with which to transform the input."
    (some #'(lambda (rule)
    (let ((result (pat-match (rule-pattern rule) input)))
    (if (not (eq result fail))
    (sublis (switch-viewpoint result)
    (random-elt (rule-responses rule))))))
    *eliza-rule*))


おお、これで5章まで終わった。現在174P。めざせ200P越え。
次回は、Chapter 6 Building Software tools。

2008年11月24日月曜日

頭だけじゃなくて、体も鍛える

業務繁忙にてなかなかCLの勉強が進まない。時間管理を向上させていくのが大事とは思うが、そもそも、もっと体力をつけたほうがよいように思えてきた。そこで、この3連休を利用して、多少運動を始めてみた。いきなり筋肉痛だが、やはり体調がよくなるし、頭もよく動くように思う。

今週一週間、仕事しながらどういう風に運動を折り込めるかをちょこちょこ試してみようと思う。それでいい形があれば継続していきたい。

Time Machine 復活

Macの外付けストレージであまりいい思い出がない。

最近でいうと、Mac Proを購入したときに、Lacieの2TBを2台入れた。2台入れたのは信用してないからだ。ひとつは2ヶ月くらいで壊れた。もうひとつは、6ヶ月くらいで壊れた。。。

その後、バックアップを3ヶ月くらい取ってなくて、実は不安があった。本体がRAID5なので、まあそう簡単には破綻しないと思うのだがバックアップが無いというのはやはり。

で、しょうがなくWestern DigitalのMy Book Studio Edition II (2TB)を購入してきて、今Time Machineがバックアップ中。本当はこれ、RAID1で動かしたかったが、本体が700GBちょいあるので、Time Machineの履歴が薄くなるのが心配になり、RAID0で走らせることにした。後日もう一台追加すれば万全か。

バックアップがあるとやっぱり安心。

【PAIP】5 ELIZA: Dialog with a Machine

ELIZA。名前は聞いたことはあるが、自分でつくったことはなかった。歴史的一品を作ってみるのもまた一興。

  • Part I はパターンマッチングの多芸多才ぶりとその限界をしめすのも目的であるよ。
  • Eliza(イライザ)の名前はPygmalionから。 (Pygmalion:wikipedia)
  • 最初の開発者はMITのJoseph Weizenbaum。(1966)
  • ELIZAはRogerian 精神分析家をエミュレートしている。(Rogerian:wikipedia)

  • 5.1 Describing and Specifying ELIZA
  • 5.2 Pattern Matching
  • ふむ。パターンマッチには、変数という概念があり、変数を管理しようとすると、bindingsという概念が有効になる。symbolとa-listがあるので、CLではbindingsの実装が簡単、という道筋なのかな。

次回は、5.3 Segment Pattern Matchingから。こつこつ。

2008年11月23日日曜日

【PAIP】4 GPS: The General Problem Solver (その4)


  • 4.14 Blocks World Domain
  • 4.15 Stage 5 Repeated: Analysis of Version 2
  • 4.16 The Not Looking after You Don't Leap Problem
  • 4.17 The Lack of Descriptive Power Problem
  • 4.18 The Perfect Information Problem
  • 4.19 The Interacting Goals Problem
  • 4.20 The Ends of GPS
  • 4.21 History and References

4.14以降は、CLというよりGPS中心のお話。たくさん節があるが、それぞれ短いのでページ数としては少い。昨日まで仕事で多忙を極め、リハビリ的にゆるく写経した。GPSをもう一回自分なりに整理した方がいいかなぁ、と考えたが、まずは通読として、先へ進むことにする。

2008年11月19日水曜日

【PAIP】4 GPS: The General Problem Solver (その3)

うひ〜 仕事が忙しい!

  • 4.12 The New Domain Problem: Monkey and Bananas
  • これがAI?という気持もするが、たしかにmeans-ends analysisな問題を解いてるよなぁ、とも思う。

  • 4.13 The Maze Searching Domain
  • う、make-maze-opがエラーになる。調べてみると、GPS Ver.2の写経ミスだった。昨日の投稿を修正しなきゃ。

こつこつ。

2008年11月18日火曜日

【PAIP】4 GPS: The General Problem Solver (その2)

4.11 のVersion 2の写経まで終わっている。Version 2のポイントを自分なりにメモしながら理解する。
Norvig.orgをみると、コードのライツが定義してあって、条件さえまもれば改変公開が可能なようだ。なので、コードも載せちゃう。


;;;; お断り:日本語を含むコメントはakaがつけたものです。debugとundebugの名前をそれぞれmy-debugとmy-undebugに改変しました。


;;; GPS Version 2

(defvar *ops* nil "A list of available operators.")
;; Version 1 からそのまま
;; メモ:
;; 問題領域で使用できるoperatorのリスト。例は次のとおり。
;;(#S(OP :ACTION ASK-PHONE-NUMBER
;; :PRECONDS (IN-COMMUNICATION-WITH-SHOP)
;; :ADD-LIST ((EXECUTING ASK-PHONE-NUMBER) KNOW-PHONE-NUMBER)
;; :DEL-LIST NIL)
;; #S(OP :ACTION DRIVE-SON-TO-SCHOOL
;; :PRECONDS (SON-AT-HOME CAR-WORKS)
;; :ADD-LIST ((EXECUTING DRIVE-SON-TO-SCHOOL) SON-AT-SCHOOL)
;; :DEL-LIST (SON-AT-HOME))
;; #S(OP :ACTION SHOP-INSTALLS-BATTERY
;; :PRECONDS (CAR-NEEDS-BATTERY SHOP-KNOWS-PROBLEM SHOP-HAS-MONEY)
;; :ADD-LIST ((EXECUTING SHOP-INSTALLS-BATTERY) CAR-WORKS)
;; :DEL-LIST NIL)
;; #S(OP :ACTION TELL-SHOP-PROBLEM
;; :PRECONDS (IN-COMMUNICATION-WITH-SHOP)
;; :ADD-LIST ((EXECUTING TELL-SHOP-PROBLEM) SHOP-KNOWS-PROBLEM)
;; :DEL-LIST NIL)
;; #S(OP :ACTION TELEPHONE-SHOP :PRECONDS (KNOW-PHONE-NUMBER) :ADD-LIST ((EXECUTING TELEPHONE-SHOP) IN-COMMUNICATION-WITH-SHOP) :DEL-LIST NIL)
;; #S(OP :ACTION LOOK-UP-NUMBER :PRECONDS (HAVE-PHONE-BOOK) :ADD-LIST ((EXECUTING LOOK-UP-NUMBER) KNOW-PHONE-NUMBER) :DEL-LIST NIL)
;; #S(OP :ACTION GIVE-SHOP-MONEY :PRECONDS (HAVE-MONEY) :ADD-LIST ((EXECUTING GIVE-SHOP-MONEY) SHOP-HAS-MONEY) :DEL-LIST (HAVE-MONEY)))

;; (defvar *state* nil "The current state: a list of conditions.")
;; Version 2では廃止。
;; stateはspecial variableではなくlexical variableとして関数の引数で渡されていく。


(defstruct op "An operation"
(action nil)
(preconds nil)
(add-list nil)
(del-list nil))
;; Version 1 からそのまま
;; ただし、Version 1では単にmake-opしたのがstructure opだったが、
;; Version 2ではconvert-opされたものがstructure opである。
;; 例は
;; #S(OP :ACTION DRIVE-SON-TO-SCHOOL
;; :PRECONDS (SON-AT-HOME CAR-WORKS)
;; :ADD-LIST ((EXECUTING DRIVE-SON-TO-SCHOOL) SON-AT-SCHOOL)
;; :DEL-LIST (SON-AT-HOME))

(defun executing-p (x)
"Is x of the form: (executing ...) ?"
(starts-with x 'executing))
;; Version 2 で新設

(defun starts-with (list x)
"Is this a list whose first element is x?"
(and (consp list) (eql (first list))))
;; Version 2 で新設

(defun convert-op (op)
"Make op conform to the (EXECUTING op) convention."
(unless (some #'executing-p (op-add-list op))
(push (list 'executing (op-action op)) (op-add-list op)))
op)
;; Version 2 で新設
;; convert-op理解のためのメモ
;; someの値はt or nil。(some #'oddp '(1 2)) => T, (some #'oddp '(2 4)) => NIL
;; executing-pのものがひとつもなければ、opに副作用してopを返す。
;; ひとつもなければ、という条件があるので、convert-opを複数回実行しても大丈夫。
;; (op-add-list op)はもともとは、'(KNOW-PHONE-NUMBER)とか。
;; この関数によって、それが'((EXECUTING ASK-PHONE-NUMBER) KNOW-PHONE-NUMBER)となる。
;; #S(OP :ACTION ASK-PHONE-NUMBER
;; :PRECONDS (IN-COMMUNICATION-WITH-SHOP)
;; :ADD-LIST (KNOW-PHONE-NUMBER)
;; :DEL-LIST NIL)
;; #S(OP :ACTION ASK-PHONE-NUMBER
;; :PRECONDS (IN-COMMUNICATION-WITH-SHOP)
;; :ADD-LIST ((EXECUTING ASK-PHONE-NUMBER) KNOW-PHONE-NUMBER)
;; :DEL-LIST NIL)
;; という変換ということ。


(defun op (action &key preconds add-list del-list)
"Make a new operator that obeys the (EXECUTION op) convention."
(convert-op
(make-op :action action :preconds preconds
:add-list add-list :del-list del-list)))
;; Version 2 で新設
;; structure op の生成関数

(defun GPS (state goals &optional (*ops* *ops*))
"General Problem Solover: from state, achieve goals using *ops*."
(remove-if #'atom (achive-all (cons '(start) state) goals nil)))
;; Version 2で変更
;; special variables版。こちらの方が簡明。
;; goal-stack: ここでnilとして開始する。

(defun GPS (state goals &optional (ops *ops*))
"General Problem Solover: from state, achieve goals using *ops*."
(let ((old-ops *ops*))
(setf *ops* ops)
(let ((result (remove-if #'atom
(achive-all (cons '(start) state) goals nil))))
(setf *ops* old-ops)
result)))
;; Version 2で変更
;; special variablesを使わずに同様の効果を自分で作った版。
;; goal-stack: ここでnilとして開始する。
;; '(start)をconsしているのはstateがnilで入った場合の防御。

(defun apply-op (state goal op goal-stack)
"Return a new, transformed state if op is applicable."
(dbg-indent :gps (length goal-stack) "Consider: ~a" (op-action op))
(let ((state2 (achive-all state (op-preconds op)
(cons goal goal-stack)))) ; =1=
(unless (null state2)
;; Return an updated state
(dbg-indent :gps (length goal-stack) "Action: ~a" (op-action op))
(append (remove-if #'(lambda (x)
(member-equal x (op-del-list op)))
state2)
(op-add-list op)))))
;; Version 2で変更
;; state goal goal-stack がgivenな状態で、指定されたopを適用する。
;; このopはこのひとつのgoalを満たす(add-listにふくむ)ものであることをこの関数は想定している。
;; 適用不可能であれば、NILを返し、適用可能であれば適用後のstateを返す。
;; 動作:
;; state2について
;; そのopのprecondsをgoalとして、achive-allしたもの。
;; ここでachive-allはachiveを呼び、achiveはapply-opを呼ぶので再帰になっている。
;; state2がNILならおしまい。
;; NILじゃなければ、そのときgoalをgoal-stackにいれてよい。なので、=1=のconsがある。
;;
;; unless内部について
;; remove-ifでopのdel-listに含まれるconditionsをstate2から削除。
;; 前行のものとopのadd-listに含まれるconditionsをappendしたものが新しいstate。


(defun appropriate-p (goal op)
"An op is appropriate to a goal if it is in its add list."
(member-equal goal (op-add-list op)))
;; Version 2で変更

(defun achive-all (state goals goal-stack)
"Achive each goal, and make sure they still hold at the end."
(let ((current-state state))
(if (and (every #'(lambda (g)
(setf current-state
(achive current-state g goal-stack)))
goals)
(subsetp goals current-state :test #'equal))
current-state)))
;; Version 2 で新設
;; current-stateまたはNILを返す。
;; goal-stack: ここではachiveに渡すだけ。
;; 動作:
;; stateを局所current-stateにする理由がわからない。
;; goalsに含まれるgoalを順番にachiveにかける。achiveが返す


(defun achive (state goal goal-stack)
"A goal is achived if it already holds,
or if there is an appropriate op for it that is applicable."
(dbg-indent :gps (length goal-stack) "Goal:~a" goal)
(cond ((member-equal goal state) state) ; =1=
((member-equal goal goal-stack) nil) ;=2=
(t (some #'(lambda (op) (apply-op state goal op goal-stack)) ; =3=
(find-all goal *ops* :test #'appropriate-p)))))
;; Version 2で変更
;; 動作:
;; =1=: goalがすでにstateにあるなら、何もしなくてよい。stateを返す。
;; =2=: goalがすでにgoal-stackにあるなら、ループしている。NILを返す(終了)。
;; =3=:
;; goalを含むopをfind-allでlistにする。
;; そのlistの要素にlambdaを適用する。
;; このlambdaの中身は、apply-opなので、そのgoalを達成できる場合、新しいstatusを返す。そうでなければnilを返す。
;; someなので、goalを達成できるopがあればT、なければNILをachiveの値として返す。

(defun member-equal (item list)
(member item list :test #'equal))
;; Version 2 で新設

(defun use (oplist)
"Use oplist as the default list of operators."
;; Return something useful, but not too verbose:
;; the number fo operators.
(length (setf *ops* oplist)))
;; Version 2 で新設



;;; Test

;; ops作成
(defparameter *school-ops*
(list
(make-op :action 'drive-son-to-school
:preconds '(son-at-home car-works)
:add-list '(son-at-school)
:del-list '(son-at-home))
(make-op :action 'shop-installs-battery
:preconds '(car-needs-battery shop-knows-problem shop-has-money)
:add-list '(car-works))
(make-op :action 'tell-shop-problem
:preconds '(in-communication-with-shop)
:add-list '(shop-knows-problem))
(make-op :action 'telephone-shop
:preconds '(know-phone-number)
:add-list '(in-communication-with-shop))
(make-op :action 'look-up-number
:preconds '(have-phone-book)
:add-list '(know-phone-number))
(make-op :action 'give-shop-money
:preconds '(have-money)
:add-list '(shop-has-money)
:del-list '(have-money))))

;; 既存のデータをVersion 2用に変換
(mapc #'convert-op *school-ops*)

;; 関数opも使ってみる。
(push (op 'ask-phone-number
:preconds '(in-communication-with-shop)
:add-list '(know-phone-number))
*school-ops*)

(use *school-ops*)
*ops*

(gps '(son-at-home car-needs-battery have-money have-phone-book)
'(son-at-school))
;;->
;;((START) (EXECUTING LOOK-UP-NUMBER) (EXECUTING TELEPHONE-SHOP) (EXECUTING TELL-SHOP-PROBLEM) (EXECUTING GIVE-SHOP-MONEY)
;; (EXECUTING SHOP-INSTALLS-BATTERY) (EXECUTING DRIVE-SON-TO-SCHOOL))

(my-debug :gps)

(gps '(son-at-home car-needs-battery have-money have-phone-book)
'(son-at-school))
;;->
;;Goal:SON-AT-SCHOOL
;;Consider: DRIVE-SON-TO-SCHOOL
;; Goal:SON-AT-HOME
;; Goal:CAR-WORKS
;; Consider: SHOP-INSTALLS-BATTERY
;; Goal:CAR-NEEDS-BATTERY
;; Goal:SHOP-KNOWS-PROBLEM
;; Consider: TELL-SHOP-PROBLEM
;; Goal:IN-COMMUNICATION-WITH-SHOP
;; Consider: TELEPHONE-SHOP
;; Goal:KNOW-PHONE-NUMBER
;; Consider: ASK-PHONE-NUMBER
;; Goal:IN-COMMUNICATION-WITH-SHOP
;; Consider: LOOK-UP-NUMBER
;; Goal:HAVE-PHONE-BOOK
;; Action: LOOK-UP-NUMBER
;; Action: TELEPHONE-SHOP
;; Action: TELL-SHOP-PROBLEM
;; Goal:SHOP-HAS-MONEY
;; Consider: GIVE-SHOP-MONEY
;; Goal:HAVE-MONEY
;; Action: GIVE-SHOP-MONEY
;; Action: SHOP-INSTALLS-BATTERY
;;Action: DRIVE-SON-TO-SCHOOL
;;((START) (EXECUTING LOOK-UP-NUMBER) (EXECUTING TELEPHONE-SHOP) (EXECUTING TELL-SHOP-PROBLEM) (EXECUTING GIVE-SHOP-MONEY)
;; (EXECUTING SHOP-INSTALLS-BATTERY) (EXECUTING DRIVE-SON-TO-SCHOOL))

(my-undebug)

(gps '(son-at-home car-needs-battery have-money have-phone-book)
'(have-money son-at-school))
;;-> NIL

(gps '(son-at-home car-needs-battery have-money have-phone-book)
'(son-at-school have-money))
;; -> NIL

(gps '(son-at-home car-needs-battery have-money)
'(son-at-school))
;; -> NIL

(gps '(son-at-home) '(son-at-home))
;; -> ((START))


うーむ。まだもやもやしているな。とりあえずこの後の展開はGPSをいろいろな問題に適用していくようなので、もやもやを抱えたまま進んでみる。
こつこつ。

2008年11月17日月曜日

【PAIP】4 GPS: The General Problem Solver

4章の趣旨は、

"Chapter 4 presents the reconstruction of GPS, the General Problem Solver. The Implementation follows the STRIPS approach."

とのこと。ざっとみてみると、AIプロジェクトの進め方の例となっているみたい。そういう意味で、後続の章の基礎となりそうだから、丁寧にやろう。


  • IPL (wikipedia)

  • AIプログラミングの5ステップ(境界は流動的)

    • Describe
    • Specify
    • Implement
    • Test
    • Debug and analyze

  • ふむ。今でいうと、プロセス構成としては平凡かな。いや、TestのいくつかはSpecifyの際に書いとくというのが、最近か。

  • 4.1 Stage 1: Description
  • means-ends analysis (wikipedia)。

  • 4.2 Stage 2: Specification
  • 特になし。

  • 4.3 Stage 3: Implementation
  • アルゴリズムが集合論とマッチしているときは、CLでもListをSetとして扱ってそのまま実装しちゃうのがいい感じ。
  • シンボルのハイフンネーミングはよくない。son-at-homeは(son at home)のほうがよい。なぜかというと、語彙が増えたとき、ハイフンネーミングだとシンボル数が無用に増えるから。なるほど。

  • 4.4 Stage 4: Test
  • 特になし。

  • 4.5 Stage 5: Analysis, or "We Lied about the G"
  • 昔ながらのプログラミングは、仕様を満たすというのが目的だが、AIプログラミングは、新しい問題領域を開拓することが目的なこともある。なので仕様は曖昧であり、バグの概念も曖昧である。
  • AIプログラミングはそもそもアジャイル、ということか。
  • ここからの節はStage 5。

  • 4.6 The Running Around the Block Problem
  • "driving from home to school"というオペレータは表現が簡単。ここで簡単、というのはprecondsやadd-listやdel-listを構成できるということ。
  • では、"running around the block"というようなのはどうだろう。これはdrivingと同じようには表現できない。drivingのときは、どこに居る、とかをprecondsとかにできたがrunningはできない。そうするとそれを表現するために"got some exercise"とかを考えなければいけない。
  • この問題は後程扱う。

  • 4.7 The Clobbered Sibling Goal Problem
  • 「身内のgoalを使っちゃう」問題。
  • 先程作ったGPSでは、goalが複数あるときにうまく機能しないことがある。goalsについて検査を進めていくときに、pass済みのgoal条件であるシンボルを、後続のgoalの実現のために消費してしまうケースがあるということ。
  • この問題の発見者?はGerald Sussman。SICPの人だな。いろいろ繋っているなぁ。
  • achieve-allで解決できる。

  • 4.8 The Leaping before You Look Problem
  • 「見るまえに飛べ」問題。
  • 複数goalがある場合。例えば一つ目のgoalは達成できるが、二つ目はnilの場合。今のGPSのつくりだと、一つ目を達成する行動をしてしまって、二つ目を調べたところでnilとなる。
  • 目的全体が達成できないならば、行動しない方がよい。計画してから行動する、というように変更しなければならない。

  • 4.9 The Recursive Subgoal Problem
  • 「どうどうめぐり」問題。
  • subgoalsの組み合わせによっては無限ループが発生しうる。
  • GPSにはループ検知機構が必要。

  • 4.10 The Lack of Intermediate Information Problem
  • nilになった場合の過程がわからない。デバッグ出力が無いのがよろしくない、という問題。
  • dbgという関数をつくり、出力先として*debug-io*を使う。

  • 4.11 GPS Version 2: A More General Problem Solver
  • (mapc #'convert-op *school-ops*) でデータを一発で書き換えるという進め方、すごい。こういうことができるように使い熟していかねば。
  • とりあえず、Version 2の写経まで。

シプサを途中までやってあるので、なんとか、GPSを計算理論上の文脈で捉えつつ読み進めることができている。
こつこつ。

2008年11月16日日曜日

【PAIP】3 Overview of Lisp

体を壊しては元も子もないので、調子をみながら。リハビリ。

さて、第三章の趣旨は、

"Chapter 3 provides an overview of the Lisp primitives. It can be skimmed on first reading and used as a reference whenever an unfamiliar function is mentioned in the text."

とのこと。なのでリラックスしていく。ただ、CL入門とANSI-CLの復習の意味もこめて写経はしっかりやる。


  • 3.1 A Guide to Lisp Style
  • lispでは同じ関数であっても多様な書きぶりが可能である。
  • どれを選ぶべきかについて、6つの指針がある。それの説明。
  • 指針が衝突した場合の判断について。

  • 3.2 Special Forms
  • andやorを条件分岐で多様するのはBad styleであると。するとPGのANSI-CLはBad style連発だったな。。。ひとそれぞれ?
  • Norvigも拡張loop否定派っぽい。
  • listをみるのに二つの視点あり。first and restとsequence。この本では後者をよく使う。なぜかというと、first and restでとらえると、listがconsでできているというlispの言語仕様にひっぱられすぎることがおおいから。最後の要素について何かしたいときとかは、sequenceととらえていた方が直接的である。
  • progn利用規制を明示。厳しいな。。。
  • 「As C.A.R. Hoare put it, "One thing the language designer should not do is to include untried ideas of his own"」これがMacro心構えだよと。なるほど。

  • 3.3 Functions on Lists
  • 3.4 Equality and Internal Representation
  • 3.5 Functions on Sequence
  • この3つ、新しい知見は特になし。

  • 3.6 Functions for Maintaining Tables
  • 属性リストはあまり使わない。hash tableを使うのが主流。理由は、

    • 属性リストは常にglobal。二つのプログラムを同時に利用したりすると衝突の回避がやっかい。
    • clrhashに対応する機能が無いなど、管理用の機能が整備されていない。


  • 3.7 Functions on Trees
  • 3.8 Functions on Numbers
  • この2つ、新しい知見はなし。

  • 3.9 Functions on Sets
  • CLにおけるbit-vector。これは初めて見たかな。PCLで見ていたが、わすれている、という可能性もある。

  • 3.10 Destructive Functions
  • そうか、Lisp以外の言語では、副作用をもたらすものをfunctionではなくprocedureと呼んでいるのか。それはそれで合理的。

  • 3.11 Overview of Data Types
  • 3.12 Input/Output
  • この2つ、新しい知見はなし。

  • 3.13 Debugging Tools
  • "..., but it also offers a third: (3) add annotations that are not part of the program but have the effect of automatically altering the running program." これが何を指しているのかが今ひとつわからない。

  • 3.14 Antibugging Tools
  • バグ警報のためにコーディング作業をあらかじめ費すのは、それなしでデバグ作業する羽目になるより安くつくよ。
  • 複雑なデータ構造を扱うときは、一貫性チェッカをつくっとくべし。
  • めんどくさいテストケースについては、何時でも実施できるよう手元においておくべし。(regression testing)
  • それは複雑なもんじゃなくてもよくて、assertをdefunでまとめておくだけでも十分。

  • 3.15 Evaluation
  • ああ、そうなのか、funcall,applyとevalというのは「評価する」という意味では同種なのか。REPLな観点からevalを特別視していたけれども、プログラマの観点で、コードの中で評価対象を作成してそれを評価するための機構としては、これらは同列にとらえられるものなのだ。
  • そして、コードの中の評価対象って何だっけ? というと、まあ「関数」と「引数」だ。なので、funcall,applyはそれらを引数にできる、と。
  • そしてその引数たる「関数」をコード中で作れますよ、というのがlambdaでありclosureということだ。
  • なので、昔のLispでは、コードの動的取り扱いにevalを多用していたが、今はfuncall,applyとlambdaを使う、と。
  • 大したことではないが、視点がすっきり整理できた。

  • 3.16 Closure
  • free lexical variablesを補足するのがclosure、という説明だけ。
  • とてもコンパクトに説明していてよいのだが、closureがわからない人が、これでわかるようになるのは無理だろう。

  • 3.17 Special Variables
  • うぉ。この節、コンパクトにlexical variablesとspecial variableの要点を説明している。
  • これはこれですっきり。
  • でも触れてないことも多いし、この説明だけでわからない人が理解するのは無理。
  • わかっている人のためのものだろう。
  • Norvigの説明を自分なりにアレンジしつつまとめる。

    • CLはデフォルトはlexical variables。
    • lexical variablesのスコープは、レキシカル。すなわちコードで範囲を抜けると、そのvariablesに名前でアクセスすることはできない。ここまでは他の言語と一緒。
    • ただし、CLのlexical variablesはclosureに捕捉され得るので、捕捉されている場合は、プログラムの実行がスコープを抜けた後も、存在することはできる。もちろんスコープは抜けているので名前ではアクセスはできない。しかし存在しているので、closureがそれを操作する機能をもっていれば、closureが無くなるまでそれは存在し操作できる。これがエクステント。closureが存在しない言語では、スコープとエクステントはlexical variablesにおいても同じとなる。ここが他の言語と違うところ。

    • special variablesのスコープはグローバルである。なので、プログラム中のどこからでも参照できる。ここまでは他の言語のglobal variablesと一緒。
    • ただし、CLのspecial variablesは、letなどによって局所的に動的にshadowingできる。なので、special variablesのスコープは、グローバルだがlocal (dynamic) shadowing付きであるといえる。ここが他の言語と違うところ。
    • そしてこのshadowingのextentはスコープと同じである。コードのゾーンを抜ければ、shadowingは無効になる。それゆえspecial variablesのextentは動的(dynamic)であるという。
    • まとめると

      lexical variables : scope = lexical, extent = indefinite (as closure)
      special variables : scope = global , extent = dynamic (as shadowing)



  • 3.18 Multiple Values
  • 複数の値を返したいときってあるよね。-> Listとかstructureで返せばいいよね。->でも、そうするとそれらの構造を定義したり、それらを関数の中で生成しなきゃいけないよね。-> I'm lisper. めんどくさいのはイヤ。-> 多値発祥。
    なるほど。。。

  • 3.19 More about Parameters
  • &optional, &keyなど自身のことをlambda-list keywordsと呼ぶよ。
  • complement、便利だな。

  • 3.20 The Rest of Lisp
  • ま、基本は自分でやるべしだよ、この本はAIの本だし、という感じ。


うむ。とりえあず、最初の100ページはクリアした。
PART II Early AI PROGRAMS に進もう。

2008年11月13日木曜日

結局病院へ。。。

過労により病院へ。とりあえず点滴。
MOPセミナには行けず。
予約してたのに、いけなかった。数理システムさんに申し訳ない。
また、とても残念。

今日はMOPセミナ

今日は黒田さんのMOPセミナ。
業務繁忙で、ほぼ二徹状態。
とほほ。

2008年11月11日火曜日

【PAIP】2 A Simple Lisp Program

二章の趣旨は、

"Chapter 2 is a more extended example showing how the Lisp primitives can be put together to form a program. It should be studied carefully by the novice, and even the experienced programmer will want to look through it to get a feel for my programming style."

とのこと。私はnorviceなので、しっかりやらなければいけないし、Norvigが、これがおれ様のプログラミングスタイルだ、というなら興味深いのでしっかりやりたい。


  • 2.1 A Grammar for a Subset of English
  • シプサでもやったな、これ。文脈自由文法。
  • あっさり。

  • 2.2 A Straightforward Solution
  • "a function with no arguments would always return the same thing" ごもっとも。関数は関数。
  • "..., but they are still called functions in Lisp, because they return a value" なるほど。
  • 関数による実装。できるといえばできる。
  • しかし文法が複雑になると、文法を記述するためにLispをごちゃごちゃかかねばならん。それをなんとかしたい。

  • 2.3 A Rule-Based Solution
  • で、文法を記述する、ということと、その文法に従って文を生成するということを分解して考えるのはどうか、ということ。
  • defparameterで定義したものを変更するのは人手であり、defvarで定義したものを変更するのはプログラムのrun-timeにおいてプログラムによって行われる。変更の頻度でいえば、defvarのほうが遥に高い。なるほど。

  • 2.4 Two Paths to Follow
  • 問題の解決をLisp codeとしてそのまま書き下すか、それとも、問題のできるだけ自然な表現をまず確立して、それのインタプリタを書く形で問題を解決するか。
  • AIプログラミングでは後者が有効な場合が多い。
  • Lispは後者が得意である。
  • 問題自身の言葉で記述できる限り記述して、直接Lispで書く部分を最小化せよ。なるほど。

  • 2.5 Changing the Grammar without Changing the Program
  • インタプリタ方式だと簡単に文法を変えられるよ。

  • 2.6 Using the Same Data for Several Programs
  • インタプリタ方式だと、作成済みの文法を別のプログラムの入力としても使えるよ。


Lispはやっぱ、LISt Processor なんだ、という実感。こういう具体的な問題への適用をイメージした形でリストの取り扱いに習熟するのが大事に感じた。これは実はPGのANSI-CLでも感じた。

はじめ、ちょろちょろ。

2008年11月10日月曜日

【PAIP】1 Introduction to Lisp

一章の趣旨は、

"Chapter 1 gives a quick introduction by way of small examples that demonstrate the novel features of Lisp. It can be safely skipped or skimmed by the experienced programmer."

とのこと。私はan experienced programmerではないので、ここからやっていくことにする。

以下、メモ。

  • この章が難しく感じるなら入門書をやってから来てね、という関門的な章らしい。いきなり玉砕するかも。

  • はじめにObjectsをさくっと定義しているところがよい。このObjectsの捉え方は、手短だが、計算理論における正しい捉え方だ。そこでは、datumもoperationもObjectsである、と。
  • LispシステムのことをLispと呼んでいる。これ、米国のLisperとやりとりすると結構でてくる表現。If your lisp has some trouble with gc ...とか。
  • 実践CLのときにも書いたと思うけど、expressionを式と和訳上結びつけたのは日本の数学や計算機科学の最大の損失ではないか。expressionは和訳するなら「表現」でばっちりだと思うのだが。

  • 1.1 Symbolic Computation
  • もしかしてエディタxyzzyの名前のネタもとは、このP7なのか?
  • quoteの説明は、readアルゴリズムには踏み込まず、evaluate回避という視点のみ。ANSI-CLと似た感じかな。

  • 1.2 Variables
  • symbolがobjectsの名前付けにつかえる、という書きぶりがうまい。
  • 名前づけの対象になるObjectsは、variablesとfunctions。
  • ここでのvariablesは、他の言語の変数よりも、数理論理学の変項のニュアンス。まあvariablesを変数という言葉と和訳上の対応を決めたのも、かなりセンス悪いと思いますが。もう「可変」でよかったのではないかと。


  • 1.3 Special Form
  • (setf x 3)の総体がa special form。setfは、special syntaxで、compilerに対する指示マーカー。という理解が現代的、とな。
  • 用語の混乱の危険があるときは、(setf x 3)をa special form expression、setfをa special form operatorと呼ぼう、とな。

  • 1.4 Lists
  • あっさり。

  • 1.5 Defining New Functions
  • lambda listじゃなくてparameter listと呼ぶ。
  • 関数の名前は、その関数の役割りを明示すべき。そのために、単に名前を明示するためだけであっても関数定義せよ。

  • 1.6 Using Functions
  • "a function must return a value, and it must not return any incorrect values." これが関数の設計観点であると。なるほど。

  • 1.7 Higher-Order Functions
  • lambdaのbetter nameはmake-functionだろう、と。
  • λ発祥は、Churchのタイポグラフィの工夫だったのか。。。(^ -> Λ -> λ)
  • (lambda (x) ...)と#'(lambda (x) ...)の違いはちょっとやる、と。
  • CLのlambdaを考えるときは、鯛焼が頭に浮かぶ。これは竹内先生の呪いだ。。。
  • run-timeに関数を生成できるのがlambda表現のメリットである(それはわかる)。そういう関数をclosureと呼ぶ(あり?そういうことだっけ?)。3.16で説明する(待ちます。。。)。

  • 1.8 Other Data Types
  • CLでは25種のObjectが定義されている。
  • 文字列紹介。

  • 1.9 Summary: The Lisp Evaluation Rule
  • 評価機構の簡単な説明。環境については触れず。
  • lispではreadとevaluationが別プロセスであることの説明。

  • 1.10 What Makes Lisp Different?
  • AIアプリケーションにとってLispが重要である7つの主因を掲示。
  • そしてそれらをひとつひとつ分析する。
  • 分析の内容が具体的でわかりやすい。

そういえば、昔、この一章を眺めたことがあった(それも忘れてた)。そのときは、言っていることはまあわかるが、それらが自分が確信をもって身につけているものとは到底思えなかった(lambdaのくだりとか)。なので、その先を読むのをやめた。

今回はさすがに準備してきたので、自分でも先に進んでよいと思える。
こつこつ。

2008年11月9日日曜日

【PAIP】Preface

うーん。Prefaceを読んだだけで、Norvigが如何に明晰な人なのかが良くわかる。

Prefaceは、プログラミングをいかに学ぶべきか、Lispがどういう点で優れているか、ということでいろいろ言われていることを簡明に整理している(PGのような煽りはなし)。またLispとAIプログラミングの関係、通常のプログラミングとAIプログラミングの関係、それらを簡単に整理した上で、本書がどのようなスタンスでそれらに臨んでいるかを記述している。

また、この本をどのように使うべきかという指針が述べられている。そのうちのひとつが、

"For the Professional Lisp Programmer: Read as much of the book as possible, and refer back to it often. ..."

とのこと。「プロのLispプログラマなら、この本をしゃぶりつくせ」ということですね。

こつこつ。。。

Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp を覗いてみることにする

少々考えて、ついにPAIPを覗いてみることにした。PAIPはCL「勉強」のひとつの目標としていたので、感慨深い。

PAIPについて少し書いてみる。著者はPeter Norvig。現在はGoogleの技術をひっぱる一人だ。もともとAI方面であり、その著書のひとつがPAIPである。現在はPythonistaであるという。Rubyならわかるが、Pythonへ、というのがどういう考えなのかは私は理解できていない。PAIPはCLと古典的AIについて書かれた本というのが世の中の位置付けだが、特にそのCLの書きぶりがキレイでありCLをやらない人でも読んで得るもの多し、と言われている。

CLの書きぶりについては、キレイという評価とともに、筋が良いというか基本に忠実という評判だ。なので、職人的というか先進的というかなんというかのプログラミングスキルではないらしい。なので、上級者向け、というものではなく、本来敷居は低い本らしい。

敷居を高く感じさせるのは、CLのイントロは付いているけど、それは本格的には別のところでやっといてね、ということだろう。導入部に推奨書籍がいくつか挙げられている。なので、CLの基礎はまあ身についていることを前提としているということ。で、CLの基礎を身につけるって、すっごく簡単というほど簡単ではないということじゃないか。

後は、題材がAIプログラミングなので、そもそも扱っている問題がいろいろ考えさせる部分が多いということもあるかと思う。

PAIPを読み込めば、CL入門者からCL初級者に格上げしてもいいように思う。さらにその上で、Norvigのもうひとつの著書であるAIMAを読み込めばCL中級者と言えるのではないか。(AIMAはCLソースが公開されている)

私自身としては計算理論というか計算機科学の訓練がまだ弱いので(シプサも中断中)、時期尚早かもしれない。

しかし、ここで一度背伸びして、当面の目標の高さを確かめてみてもいいかな、と考えた。学習プロセスには、深く掘ってみるタイミングと、幅広く視野を広げて鳥瞰するというタイミングがあるように思う。それがいい形でスパイラルしていくのが効果があると思える。今は視野を広げるタイミングという判断だ。

というわけで、PAIPを覗いてみる。いつまでにどうこうという目標は立てない。なんだかよくわからなくなって、読んでいる意味がなくなったらいつでも撤退しようと思う。

【ANSI-CL】付録A デバッグ

PGによるCLでよくあるバグパターン。そうそう、あるある、という感じ。CLは言語仕様の規格なので、ANSI Common Lispについて語るときはどうしてもデバッグについてはこういう感じになる。これ以上の詳細は処理系のマニュアルをどうぞ、ということで。

さて、なんとか一週間でPGのANSI Common Lispを通読できた。

通読完了直後の感想をいくつか。

  • CL入門でCLtL1というかCLの基本をやっていたので、それをベースとしてANSI CLのポイントをつかむにはとてもよかった。
  • ただし例えば、setqやsetの説明はなく、setf一本でいっているところなど割り切りがある。
  • また、labels, flet, macroletとかの説明がなかったりとかの割り切りもある。
  • なるほどCLの書きぶりってこういうものなんだ、と、はっとさせられる部分がいくつかあるのがいい感じ。
  • なので、入門書というよりは、PG的なポイント集と思った方がよいかな。(Amazon.co.jpのレビューと同意見)


さあ、この次どうするか。ちょっと考えたい。

【ANSI-CL】17 例:オブジェクト指向言語 (その2)


  • 完全には習得していないが、写経しつつ、イメージはわかった。自分なりに少しまとめてみる。

  • ある特定の問題を解くプログラムではなく、言語内言語のようなものを作る作業である。Fowler風に言えば内部DSL。
  • 同じものをC言語でつくることを想像してみる。

    • ちょっとうまく想像できない。。。
    • まずLisp的マクロはないので、関数が書きぶりのメインになるのだろう。
    • データ構造的な部分は、基本型、配列、構造体などの基本的なものとポインタで大抵いけるだろう。
    • methodcall (&obj &method &method_params) 的な呼び出し構造があふれそうな。
    • これ、先々やってみると面白いかも。


これにて最終章完了。付録は「付録A デバッグ」のみやることにする。

【emacs】なんとなく欲しい機能

すでに実現されているものもあるかと思いますが、こんなのが欲しいなぁ、というリスト。

  • あるS式の外側のS式をコピーする機能。C-M-kのOuter版のようなもの。

    (hoge (piyo (poyo puyo)))
    だとして、poyoの前の括弧にポインタがあるときに発効すると
    (hoge (piyo ...))
    がコピされて、それを例えば
    (moge muge)
    のところでyankすると
    (hoge (piyo (moge muge)))
    となる。


  • C-M-kのコピー版。

    • C-M-kはkillなんで。コピーしたいときにいちいちkill-yank move yank とするのがいやなので。


  • コントロール可能なC-;。

    • ;の個数
    • ;の後に空白文字をいれるかどうか。


  • 括弧が対応していなくても動くC-cC-e。

    • S式書きかけのときに末尾にいく方法がない。
    • C-cC-eは、括弧対応異常と言うだけなので。


  • 拡張loopのまともな整形機能。

    • 特に、C-jしたときもまともに動くこと。


  • CL用flyspell-prog-modeみたいなの。

    • 現在のパッケージのシンボルリストをemacs内にもコピーしておき、文字入力時に、readにとって新しいシンボルになる文字列には色付けしてくれる。

【雑】プログラミングを学ぶことについて

子供のときに、コンピュータにちょっと興味をもったことがあって、コンピュータに詳しいというおじさんに、プログラミングできるようになるにはどうしたらいいの? と聞いたことがあった。プログラミング言語っていろいろあるし何やったらいいか、わかんない、という子供心だったと思う。

そのおじさんは、多分真剣に考えてくれて答は次のようなものだった。

  • プログラミング言語は何でもいいので、まずひとつの言語に定めて、それをちゃんとマスターしなさい。
  • マスターするためには、よい問題集を一冊やること。それを繰り返し何度もやることが大事。

結局、子供のときはプログラミング言語に手を出すことはなかったが、今、おじさんの言葉に従ってCommon Lispに絞って、ちゃんとマスターしようとしている。

しかし、このおじさんのアドバイスを拡張しなければいけない、という思いが強くなってきた。このおじさんのアドバイス通りにやるとしたら、C言語しかないのではないか? というのは、プログラミングがちゃんとできるようになるには、基盤として、

  1. あるプログラミング言語とアルゴリズム能力の習得
  2. OSの知識
  3. 効率的にプログラムを書くための環境の知識

が必要に思う。これが例えば1がCommon Lispだとすると、まあ、

  1. Common Lisp
  2. Unix
  3. Emacs

というのが順当になる。2をちゃんと理解するには、C言語は必須であるし、3をちゃんと理解するにはEmacs Lispの理解は必須である。なので、3言語をマスターしなければならない。

これがC言語ならば、

  1. C言語
  2. Unix
  3. Vi

という組み合わせがあって、これはC言語ひとつが言語としては必須と考えてもよいと思えるからだ。

ということで、この際腹をきめる必要がある。破戒して、CL、ELisp、Unix/Cをみつどもえで習得していく必要があるということだ。

【ANSI-CL】17 例:オブジェクト指向言語

最終章。

  • 17.2 多重継承

    • 優先リストを作るところのmapcanがすごいな。どうしたらこういうのがほいほい書けるようになるか。。。

      (defun precedence (obj)
      (labels ((traverse (x)
      (cons x
      (mapcan #'traverse
      (gethash :parents x)))))
      (delete-duplicates (traverse obj))))



残念ながら力尽きて、17.4 関数構文までとなった。今日中に残りをやれば、なんとか目標は達成できるからよしとして寝ることにする。おやすみなさい。

2008年11月8日土曜日

【ANSI-CL】16 例:HTML生成


  • 16.2 HTMLユーティリティ

    • ここのマクロは、マクロとはコードを代わりに書いてくれるもの、という感覚を捉えやすい。

  • 16.3 反復ユーティリティ

    • ユーティリティmap3は頭いいなぁ。こういうのがすいすいかけるようになるとCL使いこなしてるという感じがする。

      (defun map3 (fn lst)
      (labels ((rec (curr prev next left)
      (funcall fn curr prev next)
      (when left
      (rec (car left)
      curr
      (cadr left)
      (cdr left)))))
      (when lst
      (rec (car lst) nil (cadr lst) (cdr lst)))))

      (map3 #'(lambda (&rest args) (princ args))
      '(a b c d))
      ;; (A NIL B)(B A C)(C B D)(D C NIL)
      ;; => NIL

      (map3 #'(lambda (c p n)
      (princ c)
      (if n (princ " | ")))
      '(a b c d))
      ;; A | B | C | D
      ;; => NIL


  • 実践CLでのHTMLの取り扱いは、HTMLタグを表すのにキーワードシンボルを使いつつ、HTML自身をS式で表した上でそれの操作をやっていた。ANSI-CLでの取り扱いは、HTMLタグを書き出す関数やマクロを用意して、それらを使えば何を出力するかはCLで述できるから柔軟でしょ、という方式だ。ANSI-CLの方がライトにいろいろ使える感じで、本腰いれるなら実践CL的な感じかな。

こつこつ。

【ANSI-CL】15 例:推論

写経しつつ、雰囲気はわかった。詳細を理解するには結構ごりごり調べる必要があるな。それは二周目。
こつこつ。

【ANSI-CL】14 進んだ話題から


  • 14.4 パッケージ

    • 「パッケージが分かりにくいとしたら、主な理由はこれである。パッケージは、オブジェクトではなく名前に基づいて作られているのである」 なるほど。自分としてはパッケージの理解に困難はないが、このようにコンパクトに表現されているとためになる。

  • 14.5 loopの機能

    • PGは拡張loop否定派なのですね。
    • 拡張loopの整形についてemacsがちょっと変。C-jで書いていくときに整形が奇妙だ。C-M-qまたはC-]ではそこそこきれい。ただし、意図通りになっていないこともある。拡張loopの構文の複雑さからかな。これ実践CLを写経したときと同じことを考えているような。進歩なし?
    • 拡張loopに括弧がないから嫌だ、というのではなくて、仕様が曖昧だからやめとけ、というPGの意見はまっとうに感じる。


  • この「進んだ話題から」にてPGは、「これらの機能はユーザはほとんど使わないが」というようなコメントをつけつつ説明している。実践CLは、PGのこの姿勢に対するアンチテーゼとして書かれたと思える。

次回からチュートリアルな章へ。まずは「15 例:推論」。
こつこつ。

【ANSI-CL】13 スピード


  • ACLでは型指定しないほうがコンパイルしてもしなくても若干速かった。ほぼ変わらない、かな。型指定なしでも最適化がされているのか、型指定ありでも最適化がされていないのか。二周目にしらべるかなぁ。
  • そうか。CLでの関数の多さというのは、柔軟性と高速性の両立のための選択肢として、なのか。このような取組みはSchemeではないな。しかし、それらの一部は、処理系が成熟していくにあたって不要になりつつあるものもある。なので、V8とかがでてきている状況ではCLのようなケアは不要になりつつあるのかもしれない。
  • 「仕様があいまいでないとしたら、それは仕様ではない」 おおきく同意。

こつこつ。

【ANSI-CL】12 データの構造

さすがに疲れてきたが、がんばってみる。めったに使わないが、気合というのを入れてみよう。

  • 定数的データ構造を保全せよ、というのは目から鱗。ひとつ賢くなった。
  • この章おもしろいな。二周目でごりごりいじってみるのが楽しみ。

こつこつ。

2008年11月7日金曜日

【ANSI-CL】11 CLOS

要点を押えたいい感じの説明。新しい話題はないのでさくっと完了。

【ANSI-CL】10 マクロ


  • 10.5 マクロ設計

    • 「コンパイラに渡る内容に変更を加えられるというのは、コンパイラを書き換えられるのとほとんど一緒である。」なるほど。

  • define-modify-macro、初めて知ったか失念していたか。ひとつ賢くなった。

こつこつ。

【ANSI-CL】9 数値


  • 数値計算はCL入門で結構やったので食傷ぎみ。。。
  • レイトレーサも二周目おくりに。

今日どこまでいけるかな?

【ANSI-CL】8 シンボル


  • 前の方で心配したシンボルと変数の関係の説明が、「8.7 シンボルと変数」でちゃんと書いてあった。
  • シンボルとパッケージはあっさり、だな。
  • 例をあじわうのは2周目ということで写経。

こつこつ。

【ANSI-CL】7 入出力


  • ストリング置換を完全には理解できていない。Cでアルゴリズムやったときに出てきたやつなのはわかるのだが。これは二周目にちゃんと理解することにする。
  • read macroはえらいあっさりだな。

こつこつ。

2008年11月6日木曜日

【ANSI-CL】6 関数

昨日は昼間はセミナーに強制参加。セミナー自体は簡単なものだったので、暇な時間は有効活用しようとANSI-CLのコピーをもっていった。しかし、手を動かしながらじゃないと、まったく頭に入ってこないことに気付いた。進化しているのか、退化しているのか。

  • Dylanの関数ビルダっておもしろい。

次回は、7 入出力。こつこつ。

2008年11月4日火曜日

【ANSI-CL】5 制御構造

ANSI-CLくらいの難易度ならば、仕事の合間にちょこちょこできる。インターリーブ。

最後の「5.7 例:日付計算」が多少ぐだぐだになったが、なんとか5章がおわった。今日、一章進めたのは大きい。こつこつ。

【ANSI-CL】4 特別なデータ構造 (その2)

仕事の休憩時間に。

  • CLでのBST、勉強になるなぁ。さきざき時間があったらCのBSTとかとじっくり比較検討したいなぁ。

というわけで、次回は5 制御構造。こつこつ。

【ANSI-CL】4 特別なデータ構造


  • ここまでで、CL入門とくらべると、紹介されている関数の数が倍くらい多い感じ。そういや実践CLでやったなぁ、と思い出すものも多い。CLtL1とANSIとの差なのかな? CL入門が入門書として配慮したたのかな? いずれにしても、CL入門はその分本質に集中できてよかったな、という感慨。ANSI-CLは、そういう意味でCL入門とかぶらないところがけっこうあるので、続いて読んでお得な感じ。
  • 二分探索木だけ残して完了。なぜか今日はBSTの気分じゃない。不思議なもんだ。

今日は連休明けで仕事がパンパン。しかし今週一週間で、なんとかANSI-CLの通読をおえたいなぁ。

とりあえず、寝よう!

2008年11月3日月曜日

【ANSI-CL】3 リスト


  • なんとなくPG調、というのがわかってきた。これはこれで軽快な感じでいいなぁ。

  • 3.3 なぜLispにはポインタがないか

    • ここの変数とポインタの説明はちょとあやうい。まちがいではないが。
    • 例では大域環境(の中の動的環境)を使っているので、symbolがその環境で変数として機能するとして、その値たるオブジェクトへの参照をsymbol objectが保持しているという意味ではそうなんだけど、それはレキシカルではまた話が違うので。

  • 広さ優先探索のコードを追うのにちょっと手間どったが、traceがいい感じにやくだった。

【ANSI-CL】2 Lispの世界へようこそ


  • うーん。説明が粗い。。。
  • これで初心者が理解できるのかなぁ。少なくとも私はCL入門をやったから、ひとつひとつ読み替えて理解できる。この本から入った人は入った人で、これで理解できのかも?
  • 「関数プログラミングの最も重要なメリットは、対話的テストができることである。」そうだったんだ。
  • lambdaなんぞや? というところの説明がいまいち理解できない。これは後の関数の章で考えよう。


悩んだが、初回は問題をやらずに通読することにしてみよう。

【ANSI-CL】1 導入

はじめちょろちょろ。

  • 「マクロとクロージャと、データ型の実行時指定とによって、Lispはオブジェクト指向プログラミングを超える」 うーん。わからない。。。
  • 「どの言語を使ってもプログラムはボトムアップに書けるが、Lispはこのスタイルに対して最も自然な媒体となる」 これもわからん。。。

  • この章は、初心者への口説き文句の章だな。

ANSI Common Lispを覗いてみようかと

Common Lisp 入門とCommon Lisp ドリルをとりあえず読了した。

CLドリルをやるときにCL入門を復習したので、入門2回、ドリル1回。

これ、まだ回数が少なくて、この2つに書かれていることを頭と体にしみこませるために何度もやったほうがいいと思う。

が、、、少し気分転換もしたい。。。そこで考えた。


  • CL入門からさらにつっこんで言語仕様よりを攻めるなら、ANSI仕様を読み込むのがよさそうだなぁ。あれ、丁寧に書かれているし。
  • でも、今は、CLを使った書き振りになれることを先に進めたい気分。
  • 実践CLをもう一度やる(今度は日本語)というのもありだなぁ。
  • しかし、もうちょっと書き振りの基本をやりたいなぁ。CLによるアルゴリズム入門みたいなのがあればほんとはいいだけど。
  • Paul GrahamのANSI Common Lispって実はそこらへんだったり???
  • ちょっと覗いてみよう。

というわけで初PGです。

【CLドリル】12 プログラミング

じわじわ。

  • compiler-letはCLtL1のみでありANSIでは廃止。aclでは、:ctlt1モジュールで互換性のための対応をしている。
  • う、あとちょっとでゴールというところで、なぜかキーボードがおかしい。Kinesisで、なぜかC-sがきかないようだ。s単体はきくんだけど。なんとかやりきった。

おお!ついにCLドリル 225問を完了した!!!
とりあえず、寝よう!

【CLドリル】12 プログラミング

じわじわ。12 プログラミング。まずCL入門の復習から。
モジュールの説明が簡易なのでよくわからないが、とりあえず完了。

【CLドリル】11 入出力 (その5)

じわじわ。11.6 文字列に対する入出力 から。

  • 11.6.1 append-stringsの作成
  • 11.6.2 count-words, count-words-in-stringの作成
  • 11.6.3 count-words-in-fileの作成
  • 11.7.1 NOT入力マクロ(~)の作成
  • 11.7.2 システムのマクロ文字の調査
  • 11.8.1 ベクタシャープマクロ(#v)の作成
  • 11.9.1 display-shipの作成
  • 11.9.2 11.5.2のformat版作成
  • 11.9.3 backup-fileの改良
  • 11.9.4 convertの改良
  • 11.9.5 convertの改良 (warn)
  • 11.9.6 dateの作成
  • 11.9.7 インタープリタ (5)

4時間くらいかかったが、なんとか完了。おおきなひっかかりはなかった。
次回は、ついに最終章。12 プログラミング。

2008年11月2日日曜日

【CLドリル】11 入出力 (その4)

11.4 文字の入出力から。

  • 11.4.1 calc

    • 簡単な計算機をつくる問題。
    • *terminal-io*の振舞いの理解に自身がもてなくて、てまどったがなんとか完了。

  • 11.4.2 エイト・クイーン (2)
  • 11.5.1 *trace-output*の取扱い
  • 11.5.2 with-open-fileの練習
  • 11.5.3 with-open-fileの練習
  • 11.5.4 copy-fileの作成
  • 11.5.5 count-linesの作成
  • 11.5.6 backup-fileの作成
  • 11.5.7 show-fileの作成

calc以降はさくさく。とりあえず、いったん休憩。じわじわ。

2008年11月1日土曜日

【CLドリル】11 入出力 (その3)

11.3 データの入力まで終了。
体調の悪さから、後半集中力がだめだった。
休んで体調を戻すのを優先する。。。
じわじわ。

【CLドリル】11 入出力 (その2)

じわじわ。

  • 11.3 データの入力
  • 11.4 文字の入出力

    • unread-charの振舞がちょっとわからない。CL入門でもHyperSpecでもunread-charするときは引数に直前にread-charした文字を指定する、とある。しかし、別の文字を指定してもunread-charは動くようだ。なんかおかしい。

  • 11.5 ファイル・システム
  • 11.6 文字列に対する入出力
  • 11.7 入力マクロ
  • 11.8 シャープ・マクロ
  • 11.9 フォーマット出力

後半はサクっとできた。しかしこれ、まだCL入門の復習にすぎない。
これからCLドリルへ。