【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 プログラミング。

【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以降はさくさく。とりあえず、いったん休憩。じわじわ。

【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ドリルへ。

【CLドリル】11 入出力

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

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

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

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

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

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

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

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

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

【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 関数。こつこつ。