2008年1月22日火曜日

Chapter 28 Practical: A Shoutcast Server

前説
The Shoutcast Protocol

特になし。


Song Sources

うーん。やっぱりこの著者は、ドメインの説明が下手かな。
参考情報。


Implementing Shoutcast

特になし。

この章も楽しめました。
CLならではかな、と思えるところを振り返ってみると、

  • いろんなtypeのソースに総称関数で備えるところ。
  • 関数名とデータ名とアクセサなどが括弧の中で入り乱れつつ、アルゴリズムや意味を形成しているところ。

    • これっていいのか悪いのか、というのはありました。例えば、

      (index source)
      は、sourceオブジェクトに対するindex slotのリーダーを使っているのですが、CLではこれがそういう行為だという意味をこの表現は運んでいません。意図的なのですが。でも、source.getIndex()だったら、そういう行為だということは一目瞭然ではあるんですよね。


でしょうか。

Chapter 27 Practical: An MP3 Database

前説

特になし。


The Database

おいおい、テーブルから始めるんですか。。。

  • クラスtable は rowsとschemaというslotsを持つ。rowsは関数make-rowsによって初期化される。
  • rowsは a vectorに格納されるようにする。
  • make-rowsはmake-arrayの単純なラッパーになる。
  • クラスcolumnはschemaの構成要素である。
  • クラスcolumnは次のslotsからなる。

    • name
    • equality-predicate
    • comparator
    • default-value 初期値はnil
    • value-normalizer ここのinitformに何故このようなlambdaを置いているのか理解できない。(↓で解決)




Defining a Schema


  • equality-predicateとcomparatorの組は、型を定義することと同義である。
  • column objectsをmake-instanceで直に作るより、型を指定して生成するインターフェイスの方が便利。
  • ここでは総称関数を使う方法をとる。
    (defgeneric make-column (name type &optional default-value))
  • stringとnumberについてeql-specialized methodを定義する。
  • stringのvalue-normalizerは#'not-nullableという関数。nilだとsignalを上げる。
  • numberはvalue-normalizerは指定しない。すなわちinitformのもの。
  • interned-string向けにはまずcolumnのサブクラスを定義する。
    (defclass interned-values-column (column) ...)
  • これにはinterned-valuesというa slotを追加する。これはhash。
  • value-normalizerで、intern処理をする。関数名はintern-for-column。
  • interned-string用のmake-columnも定義。
  • これで、make-columnは、string,number,interned-stringについて定義できた。
  • make-schemaを次のように定義。

    (defun make-schema (spec)
    (mapcar #'(lambda (column-spec) (apply #'make-column column-spec)) spec))

  • specの例は次のとおり。

    (defparameter *mp3-schema*
    (make-schema
    '((:file string)
    (:genre interned-string "Unknown")
    (:artist interned-string "Unknown")
    (:album interned-string "Unknown")
    (:song string)
    (:track number 0)
    (:year number 0)
    (:id3-size number))))




Inserting Values

  • insert-rowはtableにa rowを挿入する関数である。
  • normalize-rowというヘルパー関数を作る。
  • names-and-valuesという引数を用意する。これはa plist。
  • normalize-for-columnというヘルパー関数を用意する。これはcolumn毎のvalue-normalizerを呼ぶ。


  • 関数file-rowは、MP3ファイルからID3情報をread-id3で抽出した上で、それをrowとして*mp3s*に格納するためのplistを作成する。



Querying the Database

うう、別にRDBを作りたくはないのだが。。。どこに連れていく気なんだ。。。


Matching Functions
Getting at the Results
Other Database Operations

特になし。


チュートリアルとしてはいろいろ参考になったのですが、作っているのがRDBなので、それは既存のRDBを使えばいいんじゃないの、とついつい思ってしまいます。バイナリデータのときとかは、あまりそう思わなかったのですが、なんででしょうね。

2008年1月21日月曜日

Chapter 26 Practical: Web Programming with AllegroServe

前説
A 30-Second Intro to Server-Side Web Programming

特になし。


AllegroServe

(defpackage :com.gigamonkyes.web
(:use :cl :net.aserve :com.gigamonkeys.html))

する前に、com.gigamonkeys.htmlのasdfによる読み込みが必要。


Generating Dynamic Content with AllegroServe

特になし。


Generating HTML

"The macro version will be quite a bit more efficient than the emit-html version. Not only do you never have to generate an s-expression representing the whole page, also much of the work that emit-html does at runtime to interpret the s-expression will be done once, when the macro is expanded, rather than every time the code is run."
が大事なことをいっていると思うのだが、理解できない。とりあえずノートしておく。

;; 追記
ああ、なぜ理解できないかはわかった。ここでいっていることの真偽は、結局htmlマクロってどうかかれているの? ということによるからだ。で、それは示されていないと。ここではそういう風にhtmlマクロは作られている、とだけ理解しておけばいいと解釈。


HTML Macro

特になし。


Query Parameters

simple-formが、なぜか出力がREPLに表示されて、WEBブラウザに出ない。
ここ、まず::typeは誤植かな。
あと、let ((*html-output* ...としているところは、(with-html-output ...でしょうか。とりあえず、そうしたら動きました。random-numberも同じです。errataをみると、、、出てない。著者に送っとこうかな。


Cookeis

特になし。


A Small Application Framewok

特になし。


CLを使ったWebアプリ開発の可能性を感じることができました。

Chapter 25 Practical: An ID3 Parser

前説

  • ID3v2.2とID3v2.3を実装対象とする。



Structure of an ID3v2 Tag

うーん。こういうところも、図表も付けてくれた方がわかりやすいと思うのだが。意図あるのかな?
メモ。

  • A tag は、a headerではじまる。
  • そのheaderは、そのtagの概要情報を含む。a headerとは次の整列ルールをもっている。

    • 3B : 文字列"ID3"。(ISO-8859-1 characters, 73,68,51)
    • 2B : ID3のメジャーバージョンとリビジョン。ただしメジャーバージョンは実はマイナーバージョンの格納に使われている。なので、ID3v2.3の場合、メジャーバージョンには3が入る。リビジョンは、現状は0しか運用されていない。
    • 1B : ビットフラグ。このビットフラグの意味はID3のバージョンによって異なる。このビットフラグは、これ以降の構造の切り替えフラグにもなっている。
    • 4B : an integer。ただし、それぞれのByteのうち7bitsしかつかわない。これはタグのサイズを表す(headerは除く)。

  • v2.3では、この後に several extended headerが来ることができる。
  • その後は、framesがくる。framesにはいくつか種類があり様々な情報を格納できる。a frameの構造は、

    • a header から始まる。
    • a header は a string identifierとa sizeを含む。v2.3では、それに続き2Bのフラグがあり、はじめの1Bの値によっては、2つめの1Bは暗号方式の指定であり、the frameの残りの部分の復号に使用される。



あと、framesがいくつ含まれるかは読まないと分からないということ。framesの中身はnull bytesを含むことがあり、搬送している情報のサイズと同じとは限らないこと。などなど。

なるほど。Practicalな題材だ。


Defining a Package

この本、パッケージを利用するときは、エクポートするシンボルを初めから一覧にしちゃってるんですね。そこを足したり引いたりしながら作っていくようなプロセスも見せてもらえれば参考になるんですが。まあ自分でやれってことでしょう。


Integer Types

define-binary-typeの復習。

  • マクロ。
  • read-value methodとwrite-value methodを生成する。
  • それらはCLの組み込みclassesに対するもの。define-binary-classに対するものではない。
  • 次のものを入力として受けとる。

    • the name of the type
    • the &key parameters (the read-valueとthe write-valueメソッドが受け取る情報)
    • the code for reading from a stream
    • the code for writing to a stream

  • これらを受け取ったマクロは、総称関数であるread-value,write-valueにそれらを入力型とするメソッドを登録する。
  • もうひとつ、short formsというのもこのマクロは対応している。
  • それは、すでに定義済みのread-valueメソッドをもとに、より特定化されたread-valueを作るためのもの。
  • 例えば、(define-binary-type u1 () (unsigned-integer :bytes 1))とか。


このまんまで、u1〜u4は定義可能。しかし、ID3タグサイズは4Byteだが、それぞれのByteでは下位7bitsしか使わず、それによって、28bitsをあらわしている。これはLDBのsizeで対応すると。それを&keyで受けとるように調整して、u1〜u4とid3-tag-sizeを統一的に記述できると。なるほど、やっと前章の意味が理解できてきた。


String Types

特になし。


ID3 Tag Header

う、MP3のファイルをまったく持ってない。落とす。
奏サウンド
Foot Loose
日本語のものの曲名がiTunes上で文字化けしている。大丈夫なのかな。

ううむ。show-tag-headerは動くが、show-tag-headersが動かない。とりあえず放置。


ID3 Frames

もんもんとしてるだけで、頭に入らない。。。メモ。


  • id3-frameの定義にdefine-tagged-binary-classを使う。dispatch関数は、find-frame-classとする。

    (define-tagged-binary-class id3-frame ()
    ((id (iso-8859-1-string :length 3))
    (size u3))
    (:dispatch (find-frame-class id)))

  • framesの種類は、24はある。
  • そこでまずgeneric frame classから作る。
  • これで取り敢えずframeを読めるようになる。24種類あるけど実際に使われているのは数種類と予測されるのでそれを調べる。
  • generic frameはid3-frameのサブクラスとする。

    (define-binary-class generic-frame (id3-frame)
    ((data (raw-bytes :size size))))

  • raw-bytesは新しい型。単にan array of bytesとして情報を保持するだけ。定義する。

    (define-binary-type raw-bytes (size)
    (:reader (in)
    (let ((buf (make-array size :element-type '(unsigned-byte 8))))
    (read-sequence buf in)
    buf))
    (:writer (out buf)
    (write-sequence buf out)))

  • find-frame-classはとりあえず'generic-frameのみ返すようにしておく。

    (defun find-frame-class (id)
    (declare (ignore id))
    'generic-frame)

  • ここまで整備できたので、id3-tagにid3-framesというbinary typeを追加したい。
  • これにはframe領域にあらわれるpadding bytesの処理の実装が必要。
  • id3-framesは、paddingは読みとばし、frame objectsをみつけたら生成するという役割を担う。

    (define-binary-type id3-frames (tag-size)
    (:reader (in)
    (loop with to-read = tag-size
    while (plusp to-read)
    for frame = (read-frame in)
    while frame
    do (decf to-read (+ 6 (size frame)))
    collect frame
    finally (loop repeat (1- to-read) do (read-byte in))))
    (:writer (out frames)
    (loop with to-write = tag-size
    for frame in frames
    do (write-value 'id3-frame out frame)
    (decf to-write (+ 6 (size frame)))
    finally (loop repeat to-write do (write-byte 0 out)))))

    ※(size frame)はアクセサーによるアクセス。


Detecting Tag Padding

read-frameを作る。ここで、condition systemを使う。これはunwindさせるので、exceptionと同じですね。


Supporting Multiple Versions of ID3
Versioned Frame Base Classes
Versioned Concrete Frame Classes
What Frames Do You Actually Need?
Text Information Frames
Comment Frames
Extracting Information from an ID3 Tag

後半は、特になし。前半を理解するのに時間がかかりました。前半は、前章を復習しながらナントカでした。
tagged binaryってどの程度使われているのでしょうか。名前からしてTIFFとかはそうかもしれません。

2008年1月19日土曜日

Chapter 24 Practical: Parsing Binary Files

前説

特になし。


Binary Files

バイナリは、コンパクトさと効率が利点とされている。この利点を実現するには、on-disk structuresが簡易にメモリ上のlisp objectsにマッピング可能でなければならない。逆もしかり。


Binary Formats Basics

LDBの説明がわからない。HyperSpecで調べると、byte specifiersは、(byte s p)で、sがbyteのsizeをbitで定義、pがbitポジションの値だそうな。テスト。

CL-USER> (ldb (byte 1 0) #b01)
1
CL-USER> (ldb (byte 1 1) #b01)
0
CL-USER> (ldb (byte 1 2) #b1001)
0
CL-USER> (ldb (byte 1 3) #b1001)
1
CL-USER> (ldb (byte 2 0) #b1001)
1
CL-USER> (ldb (byte 2 1) #b1001)
0
CL-USER> (ldb (byte 2 2) #b1001)
2
CL-USER>

なる。bitポジションに移動して、そこの値をsizeに従って読むのか。


Strings in Binary Files

メモ。

  • character code : positive integers と characters の マッピングを定義。マッピングの中のそれぞれのpositive integerのことをa code point と呼ぶ。
  • character encoding : code pointsをバイト列で表現する方法を定義する。


Composite Structure
Designing the Macros
Making the Dream Reality

特になし。


Reading Binary Objects

そうか、generic functionsはマクロで関数の名前が衝突しないためにも有効なんだ。


Writing Binary Objects

特になし。


Adding Inheritance and Tagged Structures
Keeping Track of Inherited Slots
Tagged Structures
Primitive Binary Types
The Current Object Stack

特になし。

この章も楽しめました。マクロとCLOSがあいまって、汎用コードを構築していく様が圧巻でした。しかし、CLプログラミングがこういうことだとすると、CLOSとマクロについて本当に理解して使いこなしていないと、CLならではのプログラミングはできんですね。。。

Chapter 23 Practical: A Spam Filter

著者が配布しているソースは、asdfでパッケージ管理されている。
asdfの簡単なメモ。



ここにきて、ひとつ疑問。
CLのプログラムの起動方式ってどういう種類があるんだろう。ACLでは、例えばSLIMEで開発をして、"Application"としてまとめるようだ(含むランタイム)。ということは、日頃はSLIMEに住むということなのだな。

著者提供のソースを動かしてみる。

  • ソースDL。展開。
  • /.../systemsをasdf:*central-registry*に登録。
  • 全てのasdのシンボリックリンクを/.../systems/に作成。
  • REPLで、(asdf:operate 'asdf:load-op :spam)
  • うまくいったようだ。
  • REPLで、(in-package :com.gigamonkeys.spam)しておく。



前説

特になし。


The Heart of a Spam Filter

  • internって言葉、アプリ書くときにも、こんな風に使う感じなんだ。



Training the Filter

特になし。


Per-Word Statistics

メモ。この本この部分の説明はかなり雑というか、ヘタクソではないか。ちょっとイライラする。


  • 基本方針は次のとおり。メッセージを、それが含むfeaturesにしたがって分類する。そのとき、個別のfeatureについて、それを含むメッセージがspamである確率を算出し、それら全てを結合したものをそのメッセージのスコアとする。
  • では、あるfeatureを含むメッセージがspamである確率をどう計算するか。
  • 第一案:

    (defun spam-probability (feature)
    (with-slots (spam-count ham-count) feature
    (/ spam-count (+ spam-count ham-count))))

  • 問題あり。これだと、そのfeatureのspam-countとham-countだけに依存している。例えば、spam-countが1で、ham-countが9であっても、次の2つの状況によって、その確率は異なるべきだ。

    状況1
    *total-spams* 100
    *total-hams* 100

    状況2
    *total-spams* 10
    *total-hams* 1000

    spam-countについてくらべると、同じ1であっても、状況1よりも状況2の方がspamである確率は高いはず。また、ham-countでいえば、同じ9であっても状況1よりも状況2の方がhamである確率は低いはず。そこで、、
  • 第二案:

    (defun spam-probability (feature)
    (with-slots (spam-count ham-count) feature
    (let ((spam-frequency (/ spam-count (max 1 *total-spams*)))
    (ham-frequency (/ ham-count (max 1 *total-hams*))))
    (/ spam-frequency (+ spam-frequency ham-frequency)))))

  • 第二案ではfrequency(頻度)という形で総数の影響を組み入れた。
  • しかし、問題あり。2000メッセージを取り扱った結果、spamとhamが半々だったとする。あるfeatureはspam-count = 1000かつham-count = 0だったとする。別のfeatureは、spam-count = 1 かつ ham-count = 0だったとする。するとそれぞれのspam-probabilityは、どちらも1である。後者の方がspamである可能性は低くあるべきだ。そこで、これを補正する方法を考える。第三案ではなく補正。
  • 補正:

    (defun bayesian-spam-probability (feature &optional
    (assumed-probability 1/2)
    (weight 1))
    (let ((basic-probability (spam-probability feature))
    (data-points (+ (spam-count feature) (ham-count feature))))
    (/ (+ (* weight assumed-probability)
    (* data-points basic-probability))
    (+ weight data-points))))



Combining Probabilities
Inverse Chi Square

統計学のお話。読むだけ。


Training the Filter
Testing the Filter
A Couple of Utility Functions
Analyzing the Results
What's Next

特になし。

うーん。平日はほとんど進められなかった。。。

2008年1月15日火曜日

後半戦 Practicalな章に進むにあたって

まず、残念ながら? 平日になってしまったので、仕事優先、よくて一日一章になるかもだが気にしないこと。そこはあせらないようにすること。

次に、Practicalになるとそれぞれが取り扱っているドメインの情報をどれだけ知っているかで、理解のスピードも深さもまったく違ってくると予想される。本当はそれらのドメインを勉強しながらじっくりやりたいのですが、さすがにそれでは時間がかかりすぎるので、CLの書きぶりとして著者がいいたいことが理解できればよしとすることにします。

ID3とかMP3ってまったく知らないので、そこが恐怖です。