【CLドリル】11 入出力

仕事がいそがしすぎて、勉強ができない。。。
きざむぞ！

• 11.1 ストリーム
  
• 11.2 データの出力
  

のCL入門復習を完了。データの出力にて:prettyの効果がわからない。nilでもtでも出力が変わらんような。
じわじわ。

【CLドリル】10 さまざまなデータ (その2)

ストラクチャをさくっとやって10章完了。
次回は、11 入出力。あと2章！！

【CLドリル】10 さまざまなデータ

10.4 ストラクチャの前まで終わった。

CL入門を復習した後、CLドリルを20問。それにだいたい7時間かかっていたようだ。速いのか遅いのかわからないが、こつこつ前に進むのみ。

次回はストラクチャから。

【雑】hyperspec.elをACLで

ANSIの仕様を参照する機会が増えてきたので、emacsからhyperspecを引けるようにする。

これはSLIMEでは標準搭載なのだが、ACLのためのFranzのemacs ifには入っていない。いつかいれねばと考えていた。OSXでは多少作業が必要。finkが結構整備されているが、この部分はfink非依存でいたいので手でいれることにした。

インストールは次の順。

• SLIME
  
• gc lib
  
• w3m
  
• flim
  
• emacs-w3m
  
• .emacs設定
  keybindはglobalで、C-xC-hにしておいてようすをみる。
  

こういうのも細かく手順を書いておくと誰かのためになるのかなぁ、どうなんだろ。とりあえず、意味があると思えないので、略記としておく。

【CLドリル】9 宣言 (その3)

朝からこつこつやって、9章のドリルが終わった！
後半は基本事項が多かったので、さくさくだった。
今日、10章に入れるのがうれしい。10章は、「さまざまなデータ」。

【CLドリル】9 宣言 (その2)

• shallow binding。shallowって? => 浅い。
  
• 9.2.3 記号セルとshallow bindingまで完了。
  

さすがに早朝からやってるので、集中力が、、、
はやく寝て、はやく起きよう。こつこつ。

【CLドリル】9 宣言

やはり宣言は重かった。ANSI CLも随時参照する形で、CL入門の内容を復習するのに朝から12時間かかった。。。
でも、自分なりに整理できてきた。
さあ、これからドリル。

【CLドリル】8 リスト処理 (その4)

頭が悪い。かんたんなことに時間がかかる。。。

• まず、8.3.3をやるなかで、S式に含まれるSymbolを収集する関数をつくりたい。
  
• 単純にやると次のよう。
  

  
  (defun collect-rec (sexp &optional result)
    (cond
     ((null sexp) result)
     ((symbolp sexp) (cons sexp result))
     (t (append (collect-rec (car sexp) result)
               (collect-rec (cdr sexp) result)))))
  

  
  
• 次に、このとき重複がないようにしたい。
  
• これを上の拡張でやろうとするがうまくいかない。悩む。
  
• すると、これはこの「構造」では書けないことがわかる。例えば、
  

  
  (defun collect-rec (sexp &optional result)
    (cond
     ((null sexp) result)
     ((symbolp sexp)
      (if (member sexp result)
          result
          (cons sexp result)))
     (t (append (collect-rec (car sexp) result)
               (collect-rec (cdr sexp) result)))))
  

  
  としたときに、memberがみているresultというのはそれぞれの枝の状態で分離しているからだ。
  
• なので、まずS式をトラバースしてsymbolをみつけるたびに処理する関数をかいて、
  

  
  (defun do-symbols-in-sexp (fun sexp)
    (cond
     ((null sexp) nil)
     ((symbolp sexp)
      (funcall fun sexp))
     (t (progn (do-symbols-in-sexp fun (car sexp))
               (do-symbols-in-sexp fun (cdr sexp))))))
  

  
  そこで、関数の「外」に集積することにした。
  

  
  (setq result nil)
  (do-symbols-in-sexp #'(lambda (x)
                          (if (not (member x result)) (push x result))) '((x j) (a d) ((x y b) . (c a))))
  result ; => (C B Y X D A)
  

  
  こういうことが、すんなりできないのがくやしいなぁ。で、演算子を除外するなら、
  

  
  (do-symbols-in-sexp #'(lambda (x)
                          (if (and (not (member x '(not and or =>)))
                                   (not (member x result)))
                              (push x result)))
    '((not j) (a and) ((=> y b) . (c a)))) 
  result ;  => (C B Y A J)
  

  
  あとは命題論理のインタプリタと恒真判定を総当たりで。
  

  
  (defun validate-wff (form)
    (let ((symbols nil))
      (do-symbols-in-sexp #'(lambda (x)
                          (if (and (not (member x '(not and or =>)))
                                   (not (member x symbols)))
                              (push x symbols))) form)
      (dolist (ttable (make-truth-tables (length symbols)) t)
        (if (not (eval-wff form (pairlis symbols ttable)))
            (return (pairlis symbols ttable))))))
  
  (defun eval-wff (form table)
    (cond
     ((symbolp form) (cdr (assoc form table)))
     ((consp form)
      (case (car form)
        ('not
         (null (eval-wff (second form) table)))
        ('and
         (and (eval-wff (second form) table)
              (eval-wff (third form) table)))
        ('or
         (or (eval-wff (second form) table)
             (eval-wff (third form) table)))
        ('=>
         (eval-wff `(or (not ,(second form)) ,(third form)) table))))))
  
  (defun make-truth-tables (n)
    (do ((i 0 (1+ i))
         (num (make-list n) (addt num))
         (result))
        ((> i (1- (expt 2 n))) result)
      (push num result)))
  
  (defun addt (num)
    (cond
     ((eq nil (car num))
      (cons t (cdr num)))
     ((eq t (car num))
      (cons nil (addt (cdr num))))))
  

  
  
• 解答をみてみると、、、う、andで分岐して再帰していく、というアイデアがきれい。。。
  
  
• 8.3.5 命題論理 (3)
  
  
  
  • 8.3.4で自分がつくった方が、もともと対応していたからそのまま。
    
  • 8.3.4の解答をベースにすると大域脱出でいける。
    
  
  
• 8.4.1 一般化変数(2)と8.4.2インタプリタ(3)はさくさくと。
  
• しかし、やはりSymbolっていうのはでっかいObjectだなぁ。
  

おお、やっと8章がおわった！
途中、大域脱出したい誘惑に駆られた、が、ふんばった。
次回は、9 宣言。ここは主題自体がごついところなのでちょっと警戒。
こつこつ。

【CLドリル】8 リスト処理 (その3)

• 8.3.2 インタプリタ (2)
  
  
  
  • 8.3.1 インタプリタ (1) の復習から。
    
  • 疲れているときは、デバッガに入ることがおおい。
    
  • 答合わせ、書きぶりは違うが、やろうとしていることは同じだった。
    
  
  

こつこつ。

【CLドリル】8 リスト処理 (その2)

• 8.2.6 ミニマックス手続き
  
  
  
  • これ、問題文の意味すらわからないのでメモ。。。
    
  • 不完全なゲーム木にて、考えられるすべての次の局面から最良の次の手を決める、というお話。
    
  • 局面の評価関数f(x)というものを用意する。
    
  • その局面の手番のプレイヤーが勝つ確立を見積るための関数。
    
  • 二人の対戦者をAとBと呼ぶ。
    
  • Aの手番である局面xにて、Aが勝つ勝率p(x)は、f(x)。よってBが勝つ勝率は1-f(x)。
    
  • これらを前提としてミニマックス手続き、というのを導入する。
    
    
  • ミニマックス手続き
    
  • 局面xに対して、後続可能な局面をy1,...,ynとする。
    
  • Aの手番である局面xにおいては、勝つように最良の手を選択するので、p(y1),...,p(yn)の最大値をp(x)とする。
    
  • かわって、Bの手番である局面xにおいては、Bは負けないように、p(y1),...,p(yn)の最小値の局面を選択するものとし、それがp(x)となる。
    
    
  • お題は、
    「評価関数と(不完全な)ゲーム木を与えられ、ミニマックス手続きを使ってA(ゲーム・プログラム)の手番で初めた場合とB(対戦者)の手番で初めた場合のAの勝率をそれぞれ求めるestimate-my-turnとestimate-his-turnという関数を定義せよ」
    ということ。
    
    
  • ゲーム木は、( 《局面》《次の局面1》...《次の局面n》)の形のリストによって表現すること。
    
  • 末葉は(《局面》)とする。
    
  • 不完全なゲーム木は、それが先読み深さというか、探索範囲であるのだと理解する。(問題文はちょっと曖昧なので)
    
  • すると、末葉に評価関数を適用して、それが属する枝がAの手番かBの手番かによって、その枝に属する葉の中から選択すべき葉を選び(ミニマックス)、その選んだ評価をその枝の評価とする、ということを再帰的に繰返していくのだろう。
    
    
  • なんとなくわかった。
    
  • ついでなんで、自分なりのプログラムを載せておく。
    

    
    (defun estimate-my-turn (eval-fun tree)
      (if (null (second tree))
          (funcall eval-fun (car tree))
        (apply #'max (mapcar #'(lambda (x)
                                 (estimate-his-turn eval-fun x))
                             (cdr tree)))))
    
    
    (defun estimate-his-turn (eval-fun tree)
      (if (null (second tree))
          (funcall eval-fun (car tree))
        (apply #'min (mapcar #'(lambda (x)
                                 (estimate-my-turn eval-fun x))
                             (cdr tree)))))
    
    (defun nim (n)
      (case n
       (0 '(0))
       (1 '(1 (0)))
       (2 '(2 (1 (0))
            (0)))
       (t (list n
                (nim (- n 1))
                (nim (- n 2))
                (nim (- n 3))))))
    
    (defun estimate-my-turn-for-nim (n)
      (estimate-my-turn #'(lambda (x) 1) (nim n)))
    
    (defun estimate-his-turn-for-nim (n)
      (estimate-his-turn #'(lambda (x) 1) (nim n)))
    

    
    
  • 解答をみると、、、だいたい一緒だった!
    
  
  

ミニマックスの理解に時間がかかった。。。
こつこつ。

値渡し?

ぼやぼや考えていたら、さらにわかっているようでわかっていないことがわかった。
CLの場合、他の言語の値渡しとか参照渡しとかと同列に考えるのは危険な気がする。Symbolがいるから。

さて、関数はeagerなので、とにかくその引数は一回評価された上で関数の処理対象となる。評価された状態が何なのか、ということだ。先日の例では、Symbol hogeが値として指しているObjectがそれにあたる。そしてその後に起こるのは、バインディングだ。そのObjectがそのときに生成された環境内の変数xにバインドされる。このxはシンボルではない。Static (Lexical) Environmentに属するものであり、ANSIの範囲ではSymbolのようにxそれ自体にアクセスすることはできない。

CL-USER(15): (setq hoge 1)
1
CL-USER(16): (defun s-name (x)
               (symbol-name x))
S-NAME
CL-USER(17): (s-name hoge)
Error: Attempt to access the name field of 1 which is not a symbol.
  [condition type: TYPE-ERROR]

Restart actions (select using :continue):
 0: Return to Top Level (an "abort" restart).
 1: Abort entirely from this (lisp) process.
[1] CL-USER(18): :pop
CL-USER(19):

ところで、この関数を意図通りに動かしたいなら、Symbol Objectを渡せばいいだけだ。

CL-USER(19): (s-name 'hoge)
"HOGE"

C言語でいう、値渡しや参照渡しとはどうも違うような気がする。Lisp Object渡しというか何というか。そう思わせるのはSymbol自体がユーザがさわれるLisp Objectだからかな。
しかし、C言語の用語で言えば、やはりCLの関数は参照渡しなのだろう。バインドされるだけで、コピーは作られないから。

で、マクロが何かというと、こちらはlazyなので、そのままSymbol(より一般的にはS式)として評価されずに渡される。(ただし単純にlazyというのは乱暴かもしれない。より正確にはMacro expansion timeに、その時点の環境に準拠しつつ展開されるということ)

なので、こういう芸当ができる。

CL-USER(34): (defmacro s-name (s)
               `(symbol-name (quote ,s)))
S-NAME
CL-USER(35): (s-name hoge)
"HOGE"
CL-USER(36):

これは関数にはできない。

こつこつ。

【CLドリル】8 リスト処理

この章ごつい。。。
8.2.5 数式処理までなんとかやった。
8.2.5の数式処理はテキストに誤植が多少あった。

まだ下手糞な部分はあるが、一応解けているので地力はあがっているのかな。

次回は8.2.6 ミニマックス手続き。なんとか体調を復活させてシプサに復帰したい。こつこつ。

【CLドリル】7 マクロ

• (setf place value)にて、place用のS-expを別のところで作って渡してあげるというのができないのが、あたりまえなのだが、ちょっとびっくり。
  

  
  (defmacro my-setf (place value)
         `(setf ,(symbol-value place) ,value))
  

  
  とかしてあげないといけないようだ。
  
• あと、今さらだが、関数は値渡しであり、ラムダリストを通った後は元のシンボル情報にアクセスできないことを再認識した。
  

  
  (setq hoge 1)
  (defun s-name (x)
    (symbol-name x))
  (s-name hoge) -> error
  

  
  
• わかっているようで、わかっていないということが、よくわかった。
  

次回は、8 リスト処理。こつこつ。

【CLドリル】6 関数

• ラムダリストのバリエーションや、局所関数など、基本事項についてよい練習になった。
  
• CLのlambdaについて理解はできていると思うが、どうもふわふわする。おそらく「システム」というのが何なのか?という疑問があるからだろう。これはCLtL2では解消されている可能性があるなぁ、と思った。将来確認しよう。
  

次回は、7 マクロ。こつこつ。

【CLドリル】5 リスト構造 (その2)

• 5.3 等号
  
• 5.4 ごみ集め
  

を完了。すんなり。
次回は、6 関数。こつこつ。

【CLドリル】5 リスト構造

こつこつ。

• お、5章の演習、内容豊富。
  
• CL入門で触れなかったことを補っている感じ。
  
• とりあえず、5.2 破壊的なリスト操作まで完了。
  

次回は、5.3 等号から。

【CLドリル】4 記号とパッケージ

体調を崩していたが、今日から復活。

• 記号とパッケージは、もやもやしていたので、ANSI仕様を読み解く。
  
• ANSI仕様がずいぶんすんなり読めるようになってきた。多少地力がついてきた模様。
  

こつこつ。

【CLドリル】3 関数の定義

こつこつ。

• 「3.3 プログラム構造」笑った。
  
• 再帰は何年か前にThe little schemerで遊んだときにさんざんやったから楽ちん。
  
• でもボリュームがあったので、時間かかった。。。
  

次回は 4 記号とパッケージ。

【シプサ】7 時間の複雑さ (その4)

リハビリかねて、こつこつ、というより、ちょいちょい。

• Φ=(¬x∧y)∨(x∧¬z)を0,1,0が充足するか?
  
  
  
  • (¬0∧1)∨(0∧¬0)
    
  • (1∧1)∨(0∧1)
    
  • 1∨0
    
  • 1
    
  • お、充足。
    
  
  
  
• Cook-Levinの定理の紹介。
  
• 多項式時間帰着可能性の導入。
  
• conjunctive : 結合する; 合同の, 共同の;
  
• 定理7.32 3SAT <=P CLIQUEの確認。
  
  
• 「定理7.36 BがNP完全であり、かつNPに属するCに対してB <=P Cならば、CはNP完全である。」
  
  
  
  • 自分なりに考える。
    
  • BはNP完全だから、B∈NPであり、NPに属するすべてのAが、A <=P Bである。
    
  • B <=P Cだから、たぶん、上のAについて A <=P Cである。
    
  • 前項の後半は、NP完全の定義そのものなので、CはNP完全である。
    
  
  
  
• SATのNP完全性を示すのはごつそうだ。
  
• 今回は、玉砕覚悟で自分なりに考えてみる。
  
  
• 「定理3.37 SATはNP完全である。」
  
  
  
  • SATはNPに属するか?
    
    
    
    • brute-forceで非決定でいけばいいのではないか。
      
    • 入力がn個のリテラルを含むとする。
      
    • すると入力の全体長はたかだかnの定数倍だ。なので、このnで考える。
      
    • n個のリテラルはそれぞれ0または1でありえる。
      
    • その割り当てを非決定的に実施する。
      
    • 矛盾した割当てとなったらその枝は拒否する。
      
    • すべてのリテラルに割当てが完了したところでその割当ての論理演算を実施する。
      
    • 前項が真になるならこのTMは受理する。
      
    • 受理の枝がひとつもなければこのTMは拒否する。
      
    • 各枝は、まあ、多項式時間のようだ。
      
    • というわけで、このTMは非決定性多項式時間機械である。
      
    • ゆえにSATはNPに属する。
      
    
    
    
  • 次に任意のA∈NPについて、A <=P SATが成り立つといえるかどうか。
    
  • A∈NPなので、Aを判定する非決定性多項式時間TM Nが存在する。その多項式時間をn^kとする。
    
  • 計算状況を並べた(n^k) * (n^k)の表をタブロー(tableau)と呼ぶ。各状況の頭とお尻は'#'とする。
    
  • tableau: (小説などの)絵画的な描写
    
  • 1つのタブローがひとつの計算の枝に対応する。
    
    
  • AからSATへの多項式帰着写像fを構成する。
    
    
    
    • 入力wから論理式Φを生成する。
      
    • wがNに受理されるなら、ΦはSATに属する。
      
    • wがNに受理されないなら、ΦはSATに属さない。
      
    • Nの仕様として、状態：Q、テープアルファベット：Γとする。
      
    • C=Q∪Γ∪{#}とする。
      
      
    • う、これ以降、しんどい。次回へ。
      
    
    
  
  

次回は、SATのNP完全確認の途中から。

【CLドリル】2 関数の定義

やっと勉強復活!
CLドリル、日本語版が手に入ったので、2章から日本語で。

• CL入門の復習をしてからドリルへ。
  
• CL入門、ほとんど覚えていない、という事実。。。
  
• 問題を解くのはやっぱり楽しい。
  

ふたたび、こつこつ。

今日を乗り切れば

なかなか厳しい業務分量だが、なんとか今日を乗り切れれば、明日から勉強再開！と思ってがんばる。
古本屋さんからCommon Lisp ドリル (日本語版)が見つかったよと連絡がはいった。ちょっと嬉しい。なるべく日本語でやりたい。