Practical Common Lisp を読む

2009年1月12日月曜日

一年後

翻訳版の読んでみています。(計算機とその周辺)

原書と翻訳書の両方を読むという体験はあまりしたことがありません。また、同じ本を一年たってから通読するというもあまりありません。そういう意味で楽しんでいます。

2008年7月18日金曜日

さらに、その後

テーマ毎にわかれているのもなんだな、ということで、一箇所に集約しつつあります。

計算機とその周辺

ブログのやり方も、まだいまひとつ飲み込めていないので、そのうち考えてみようと思います。

2008年5月7日水曜日

その後

Common Lisp の習得を目指していますが、ちょっと寄り道というか回り道をしています。

まず、実際にプログラムを組もうとすると、組むための開発環境だとかパーシステンスのあり様だとかで、数理論理の基礎を勉強しなければ、と思いました。飛躍している、とつっこまないでください。一応つながっているのです。

「ソフトウエア科学のための論理学」を読む

あと業務の関係でRubyを使う必要がでてきたので、これも脇道で、ウサギ本を読んでいます。

Programming Ruby を読む

Lispは基礎を固める、ということで次の2冊をちょっとずつ読んでいます。

あと、いろいろな本を読んでいると、やはりC言語とJavaは知らないと、例とかでわからないことが多いです。そこで、C言語から勉強しようと思います。

「新版明解C言語入門編」を読む

なんか、この読書の連鎖のアルゴリズムは、無停止なような気がしてきましたが、楽しんでやっているのでいいかな、と。
そうだ、本当はアルゴリズムとデータ構造の勉強がしたいのです。それはもう少し片付いたところで。

2008年1月24日木曜日

Chapter 32 Conclusion: What's Next?

前説
Finding Lisp Libraries
Interfacing with Other Laguages
Make It Work, Make It Right, Make It Fast
Delivering Applications
Where to Go Next

特になし。

読了。

Chapter 31 Practical: An HTML Generation Library, the Compiler

前説

FOO言語においては、InterpreterとくらべてCompilerが最適化しているのは、テキストをできるだけまとめて出力するようにすること。

The Compiler

The compilerのアーキテクチャ。
html-compilerクラス。このオブジェクトにbackendの総称関数へ成されたopsを集積させる。
backendの総称関数は、前項へのops書き込み機能を持つ。
opsを最適化する関数にわたし、最適化される。
最適化されたops vectorをgenerate-code関数が受け取り、CLのコードを吐く。

compilerがhtml-compilerのときのprocessor interface(メソッド)は、html-compilerへのopsの集積処理とする。
関数sexp->opsを定義する。これは、前項を順次S式に適用してopsのvectorを作成する。
関数optimize-static-outputを導入する。これは前項のvectorについて、raw-stringを合成する。
関数generate-codeを導入する。これはopsに対して逐次総称関数op->codeを適用するだけ。
総称関数op->codeを定義する。これが、それぞれのopを対応するLisp codeに変換する。
op->codeの定義でポイントは2つ。embed-valueとembed-code。
embed-valueは、Lispの変数の埋め込みに対応する。これは(princ-to-string value)が本質である。
embed-codeは、Lispのコードの埋め込みに対応する。これは、入力のコードをそのまま使える。

FOO Special Operators

Special Operatorは、CL本体と同じように、言語の通常の評価ルールでは実現できないことを実現するためのものである。
まず、現在のembed-codeの実装(そのまま)では、(p: (random 10))などで、(random 10)の値はすてられ、出力は
となる。値が欲しいときもある。
そのために、:print、:formatを導入する。
:printは、embe-codeで検知され、そのbodyをembed-valueに渡す実装とする。
:formatは、それの引数がself-evaluatingであれば、それをemit-htmlに渡せる(Interpreterで使える)。Compilerのときは、引数はどんなLisp expressionsでもよい。

Special Operatorの実装方法。
まず、関数processの第一分岐としてprocess-special-formを呼ぶようにする。
Special formは、'html-special-operator(plist)に格納する。名前とlambdaの組で格納。
個々のSpecial formの定義はマクロdefine-html-special-operatorで簡略化する。
関数process-special-formは、plistからlambdaを取得して、formに適用するだけ。
これによって、Special Operatorの拡張をモジュール化できている。

FOO Macros

Special Operatorの実装方法と類似。
'html-macro plistにマクロ名と処理lambdaを登録する。
ただし、ユーザはそのlambdaを直接書くのではなく、そのlambdaを作るための関数generate-macro-with-attributesなど(define-html-macroから呼ばれる構造とする。
generate-macro...は、ユーザから受け取ったマクロ定義(args and body)を、DISTRUCTURING-BINDに渡して、argsの置換をおこなうようにする。
関数processの第二分岐にexpand-macor-form関数を登録する。これがマクロ展開を実行する。

The Public API

あり? なぜここで急にXHTML? *xhtml*がnil or t。
マクロin-html-styleを定義。
マクロhtmlを導入。
マクロhtmlはそれ自身ネスト可能であるし、その中身は*pretty*の値によって振舞が違うので、コード分岐を含んでもいる。すなわち単純な実装だとネストによって指数関数的にコードが増大してしまう。
それはmacroletで回避可能。

The End of the Line

JavaScriptのS式表現をつくる元気はありません。。。

Chapter 30 Practical: An HTML Generation Library, the Interpreter

気をとりなおして。
30章と31章については、各節のエッセンスをメモしていく形にします。

前説

Interpreter : FOOプログラムを受け取って、HTMLを生成する。
Compiler : FOOプログラム(CL埋め込みあり)を受け取って、CLのコードを生成する。

Designing a Domain-Specific Language

DSL設計は2段階。

DSLの構文というか書きぶりを決める。
それの処理系を実装する。

DSLの設計のポイントは、DSLによっていかに表現が「圧縮」されるかということ。

The FOO Language

Lisp objectsを基礎におく。
self-evaluating lisp objectsは、PRINC-TO-STRINGで変換したものをFOOでは出力する。このとき<>などのエスケープも行う。
HTMLの要素名をキーワードシンボルとする。キーワードシンボルを第一要素とするリストを、HTMLの要素に対応させる。
属性は次の2つの表現が可能とする。
表現1 (:p :id "x" "Foo")
表現2 ((:p :id "x") "Foo")

Character Escaping

要素と属性でエスケープ対象文字が異なる。
対象文字を、*element-escape*, *attribute-escape*に格納する。
*escape*に場所場所でどちらかを割り当てるなどの運用をする。

Indenting Printer

indenting-printerというクラスに情報を格納してindentを制御する。
ただし、indenting-printerのindentation slotに入っている値に対応してindentするというだけの機構。

文字列をindentして出力するための基本関数を定義。


(defun emit (ip string) ...)
(defun emit/no-newlines (ip string &key (start 0) end) ...)
(defun indent-if-necessary (ip) ...)
(defun emit-newline (ip) ...)
(defun emit-freshline (ip) ...)

HTML Processor Interface

HTML Processorのインターフェイスは総称関数で定義する。
これはInterpreterとCompilerの両方に対応するため。

総称関数は次の8つ。


(defgeneric raw-string (processor string &optional newlines-p))
(defgeneric newline (processor))
(defgeneric freshline (processor))
(defgeneric indent (processor))
(defgeneric unindent (processor))
(defgeneric toggle-indenting (processor))
(defgeneric embed-value (processor value))
(defgeneric embed-code (processor code))

The Pretty Printer Backend

html-pretty-printerというクラスを導入する。これは、slotにindenting-printerとtab-widthをもつ。
前章の総称関数に対するメソッドの定義をする。そのとき、Indenting-printer節で定義した基本関数が使える。
embed-valueとembed-codeとは、Compilerのみで使用する。Interpreterではerrorとなるようにする。

The Basic Evaluation Rule

評価としては、まずself-evaluatingならば、raw-string関数にわたす。
そうでなければ、それはFOO言語のcons-sexp形式となる。
process-cons-sexp-html関数を導入する。
この関数は、HTMLタグ出力、その中身の出力、インデントの管理、改行の管理を担当する。

これの振舞の観点から、HTML要素は3つに分類できる。


(defparameter *block-elements* '(:body :colgroup ...))
(defparameter *paragraph-elements* '(:area :base :blockquote ...))
(defparameter *inline-elements* '(:a :abbr ...))

この他に2つの補足的分類がある。


(defparameter *empty-elements* '(:area :base :br ...))
(defparameter *preserve-whitespace-elements* '(:pre :script ...))

この分類を利用して、process-cons-sexp-htmlを実装する。
process関数を直に呼ぶのでは手間なので、emit-html関数を導入して省く。
*html-ouput*自身をAPIとして公開したくはないので、with-html-ouputマクロを導入して隠蔽する。

What's Next?

特になし。

2008年1月23日水曜日

Chapter 29 Practical: An MP3 Browser

前説

特になし。

Playlists

SHOUTcastの情報がなかなかみつからない。IcecastはSHOUTcastから派生したものらしい。

Icecast Documentation

あとPlaylistの情報。

Unofficial M3U and PLS Specification

Playlists As Song Sources

著者がちゃんと説明しないので、私家版整理。

MP3をストリーム配信する場合、提供の仕方は2種類ある。ラジオ的なエンドレスなものと、アーカイブス的に指定した曲を提供するものである。
いずれにしても、SHOUTcastの仕組みとPlaylistは関係ない。MP3プレーヤに直にラジオ(チャンネル)や曲のURLを直に入力してもよい。
PlaylistはSHOUTcastを使ったサービスを便利にするための補完的なものである。
MP3 client(の一部)は(Nullsoftの)Playlistを読み込むことができる。
ラジオの場合は、Playlistの中のLengthが-1となっている。
曲の場合は、その曲の秒数がLengthに入る。
ラジオの場合は、通常Playlistは単にそのチャンネルの聴取する入口の機能のみを担い、Playlistをユーザが編集するなどの機能はない。
曲の場合は、Playlistからユーザが曲を選択して聴取することができるので、サーバ側がPlaylistの編集機能などを提供することによって便利になることもある。ただし、一度ダウンロードしたPlaylistをclient側でカスタマイズするというのもありなので、それしかやりようがないわけではない。
この本では、次の設計方針としている。
- ラジオではなくアーカイブスとするが、曲毎のURLはもたない。
- ユーザをIPアドレスで識別する。
- それと相俟って、IPアドレスひとつにつきPlaylistをひとつサーバ上にもてるようにする。このPlaylistはNullsoftのPlaylistではない。
- サーバ上のPlaylistをユーザがWebブラウザからカスタマイズできるようにする。
- MP3 clientは単一のURL(ストリーミングフィード)にアクセスし、そのフィードから出る曲をWebブラウザからPlaylistという形で操作する。

Manipulating the Playlist
Query Parameter Types
Boilerplate HTML
The Browse Page
The Playlist
Finding a Playlist
Running the App

特になし。

この章楽しめませんでした。
CLの本ですから、作るアプリのドメイン情報やアーキテクチャについて、詳細に触れる必要はありませんが、説明がいいかげんに思えます。また、題材となっているSHOUTcastやPlaylistはNullsoftの勝手仕様なものであり、その仕様を自助努力で調べようにも入手可能な情報自体が不足しています。著者のCLのコードをみて仕様を想像するのでは、それが正しい実装なのか判断できません。

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の簡単なメモ。

asdfのページ
makeみたいなものかな。
ACLには独自のdefsystemがある。Defsystem

ここにきて、ひとつ疑問。
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ってまったく知らないので、そこが恐怖です。

Chapter 22 LOOP for Black Belts

LOOPが好きになれるかどうか、が読みどころ。
CLの言語コアよりも上の部分の各種機構って、とどのつまりはミニ言語というかDSLだと思うのですね。ミニ言語やDSL自体を否定していたら、常に言語コアのみで書かないといかんとなってしまう。なので、DOとかはS式っぽいDSLで、拡張LOOPはS式っぽくないということだけだと思うのです。でも何故か、LOOPを見てると不安になるんですよね。それがどこからきてるのか。

前説

特になし。

The Parts of a LOOP

お、さすがに箇条書きをはじめた。この著者が箇条書きにするってことは、LOOPってやっぱりそういうものなんですね。

Iteration Control
Counting Loops
Looping Over Collections and Packages

特になし。

Equals-Then Iteration

この章かなりごつい。。。とにかく例をやってみて理解していくことにする。


CL-USER> (loop repeat 5
               for x = 0 then y
               for y = 1 then (+ x y)
               collect y)
(1 2 4 8 16)
CL-USER> (loop repeat 5
               for y = 1 then (+ x y)
               for x = 0 then y
               collect y)
(1 1 2 4 8)
CL-USER> (loop repeat 5
               for x = 0 then y
               and y = 1 then (+ x y)
               collect y)
(1 1 2 3 5)
CL-USER>

この違いは? ああそうか、どの時点のx,yを参照するかの違いなのか。forの評価はそれぞれ独立して逐次なので、後ろのforの中は前のforの評価結果(今回ループ)を参照可能。andはそれを揃えるときに使うと。

Local Variables

withの例がない。うーむ。
説明を読む限り、補助変数として名前をもった方が記述が楽なときに使用するもの。

Destructing Variables


CL-USER> (defun hoge (list)
           (loop for cons on list
                 do (format t "~a" (car cons))
                 when (cdr cons) do (format t ", ")))
HOGE
CL-USER> (hoge '(1 2 3 4 5))
1, 2, 3, 4, 5
NIL
CL-USER> (defun piyo (list)
           (loop for (item . rest) on list
                 do (format t "~a" item)
                 when rest do (format t ", ")))
PIYO
CL-USER> (piyo '(1 2 3 4 5))
1, 2, 3, 4, 5
NIL
CL-USER>

これはたしかにhandy。
読みやすいし、書きやすい。

Value Accumulation

う。なんか便利すぎてくやしい。

Unconditional Execution

-esqueって、〜風とか、〜っぽいって意味なんですね。

Conditional Execution


CL-USER> (loop for i from 1 to 100
               if (evenp i)
                 minimize i into min-even and
                 maximize i into max-even and
                 unless (zerop (mod i 4))
                   sum i into even-not-fours-total
                 end
                 and sum i into even-total
               else
                 minimize i into min-odd and
                 maximize i into max-odd and
                 when (zerop (mod i 5))
                   sum i into fives-total
                 end
                 and sum i into odd-total
               do (format t "~{~a; ~}~%" (list
                                          min-even
                                          max-even
                                          min-odd
                                          max-odd
                                          even-total
                                          odd-total
                                          fives-total
                                          even-not-fours-total)))
0; 0; 1; 1; 0; 1; 0; 0;
2; 2; 1; 1; 2; 1; 0; 2;
2; 2; 1; 3; 2; 4; 0; 2;
2; 4; 1; 3; 6; 4; 0; 2;
2; 4; 1; 5; 6; 9; 5; 2;
2; 6; 1; 5; 12; 9; 5; 8;
2; 6; 1; 7; 12; 16; 5; 8;
2; 8; 1; 7; 20; 16; 5; 8;
...

改造版。さすがにSLIMEの自動インデントは対応してなかった。

Setting Up and Tearing Down

う、Perl難しい。。。

Termination Tests

特になし。

Putting It All Together

特になし。

著者が言っている「繰り返しにはパターンがあり、それはDSL構築に値する」というのはその通りだと思います。あと、通常の英語っぽくすることが、拡張LOOP設計者の狙いだったとのことです。読んでみて、私の整理はこんな感じです。

繰り返しを表現する英語の語彙や構文は、自然言語にしては、なかなかアルゴリズムの表現に適したものであり、
だったらそれをそのまま文法にしてDSLをつくるのがいいじゃん。というノリか。それはアリだと思う。
これが日本語ではたぶん無理。
しかし自然言語の語彙と構文をもってきてるから、そっちの知識も頭にあるので慣れるまではノイズがでる。
これが不安感。
たぶん、ノイズの度合いは、英語が日常の言語の人と、私のように日本語が日常の言語の人ではずいぶん違うはず。
個人的には繰り返しを再帰で書くのは嫌いではない。
しかし、再帰の実戦的なメリットは、繰り返しが書けるということではなくて、関数を宣言的に書けるということの場合が多いと思う。

2008年1月14日月曜日

Chapter 21 Programming in the Large: Packages and Symbols

前説

名前の衝突の問題は、CLでは、the readerの振舞の問題となる。テキスト上の名前をsymbolsに変換するのは、the readerの役目。そのときに、同じ名前を同じsymbolにするか違うsymbolにするか、ということ。

How the Reader Uses Packages

メモ。

packagesはそれぞれ名前を持つ。
FIND-PACKAGEで、packagesの名前検索ができる。
*PACKAGE*はa packageの名前をもち、それをthe current packageと呼ぶ。
FIND-SYMBOLは、a name と a package nameを引数にとり、そのnameに対応したsymbolが存在する場合はそれを返し、存在しない場合はNILを返す。
INTERNは、FIND-SYMBOLと似たようなものだが、存在しないときには、そのnameに対応したsymbolをそのpackageに生成する。
プログラマが使用する名前のほとんどは、unqualified(無資格? 無修飾? 無制限?)である。具体的には、コロンをひとつも含んでいない。
その場合、the readerが「テキストの a name を読む」とは、それのエスケープ文字を変換して、全体を大文字にして、INTERNに渡すということだ。
コロンを含んでいる名前を a package-qualified name と呼ぶ。(修飾/制限だ）
the readerは、a package-qualified name を読むと、それをコロンを区切りとして分解する。それぞれの部分をa package nameやa nameと解釈する。
１コロンは、an external symbolを指すものであり、externalであるということは、元packageがそれをexportsしているということ。存在しなかったり、externalでなかったりすると、the readerがエラーを上げる。
２連続コロンは、おお！強制介入。externalであるかにかかわらず、そのsymbolがそのpackageに存在するなら返却される。
keyword symbolsとは、コロンから始まるもののこと。これらは、KEYWORDという名前のpackageにINTERNされて、自動的にexportされる。さらに、同時に、そのsymbolと同じ名前と値のa constant variableを定義する。
uninterned symbolsは、頭に#:をつけたもの。どのpakageにもINTERNされない。それを読むたびにthe readerは異なるsymbolを生成する。

A Bit of Package and Symbol Vocabulary

メモ。

FIND-SYMBOLを使ってあるpackageについて取得可能なsymbolsを、"accesible in that package"と言う。これは、対象としているpackageが current packageであるときに、unqualified nameで参照可能なものということ。
この内訳は2つになる。
ひとつは、the readerがそのpackageのname-to-symbolテーブルにinternしたもの。それは、"present in the package"と言う。
もうひとつは、そのpackageが他のpackageのsymbolsをinheritsしたもの。inheritsするということは、"using the other package"と言う。ただし、the used package自身がexportsしているsymbolsだけがinheritsされる。このようにexportsには2つの効果がある。inheritsされるということと、package-qurlified names(コロン1つ型)で参照可能になるということ。
このinheritanceにおいて名前衝突がおこった場合は、そのうちのひとつを a shdowing symbolにすることによって、name-to-symbolの対応を単一にして解消できる。
useとは別にimportがある? (頭がクラクラしてきた。。。)
だめだ、概念を文章だけで説明されてもなんだかわからない。この後の節の例をみて理解しよう。
a present symbolはuninternできる。uninterned symbolのPRINTは#:記法となる。

Three Standard Packages
Defining Your Own Packages
Packaging Reusable Libraries

特になし。

Importing Individual Names

importは個々のsymbolに対してなんですね。

Packaging Mechanics
Package Gotchas

特になし。

この章も楽しめました。

Chapter 20 The Special Operator

前説

特になし。
しかし、この章、ごつそうだ。

Controlling Evaluation

1. QUOTE
2. IF
3. PROGN

特になし。

Manipulating the Lexical Environment

4. LET
5. LET*
6. SETQ
7. FLET
8. LABELS
9. MACROLET
10. SYMBOL-MACROLET
11. FUNCTION

ためしにWITH-SLOTSを展開してみると、、、


CL-USER> (macroexpand-1 '(with-slots (x y z) foo (list x y z)))
(LET ((#:G163 FOO))
  (DECLARE (SYSTEM::VARIABLE-REBINDING FOO #:G163))
  #:G163
  (LIST (SLOT-VALUE #:G163 'X) (SLOT-VALUE #:G163 'Y)
        (SLOT-VALUE #:G163 'Z)))
T
CL-USER>

本と違う。SYMBOL-MACROLETまで展開されてるのかな。ま、mightだし、いいや。
SYMBOL-MACROLETの説明がよくわからん。HypeSpecのはわかりやすい。(HyperSpec)

Local Flow of Control

12. BLOCK
13. RETURN-FROM
14. TAGBODY
15. GO

特になし。

Unwinding the Stack

16. CATCH
17. THROW
18. UNWIND-PROTECT

特になし。

Multiple Values

19. MULTIPLE-VALUE-CALL

誰が何する人か整理。

VALUES : function : 複数の値を引数に取り、多値として返す。
VALUES-LIST : function : 単一のリストを引数に取り、多値として返す。
MULTIPLE-VALUE-CALL : special operator : subformをそれぞれ全て評価した上で、多値含めてそれらを全部引数としてfunctionに渡す。
MULTIPLE-VALUE-BIND : macro : 多値を変数に格納する。
MULTIPLE-VALUE-LIST : macro : 多値をリストにする。

EVAL-WHEN

20. EVAL-WHEN

頭にすっと入らない。思うに、英語力が低いからすっと入らないだけで、この本の記述自体は簡明なのだろう。
いずれにしても、メモを取りながら。。。

LOADは、ファイルをloadして、それのtop-level formsを全て評価する。
COMPILE-FILEは、a source fileをa FASL fileにコンパイルする。
(load "foo.lisp")と(load "foo.fasl")は等価である。
LOADは、ファイルの前の方にあるformsは、後ろの方のformsの評価に影響を与える。
COMPILE-FILEは、通常は、formsを評価しない。評価が発生するのは、FASLがLOADされるときである。
しかし、一部のformsは、COMPILE-FILEの処理のときに評価しないと、(load "foo.lisp")と(load "foo.fasl")の等価性を確立できない。
それは、例えば、IN-PACKAGEやDEFMACROである。
EVAL-WHENを使うと、specific bits of codeが何時評価されるかを指定できる。

Other Special Operators

21. LOCALLY
22. THE
23. LOAD-TIME-VALUE
24. PROGV

一個足りない。。。と思ったら脚注に。

25. MULTIPLE-VALUE-PROG1

特になし。

Chapter 19 Beyond Exception Handling: Conditions and Restarts

前説

high,medium,lowの対処のところがわからない。メモしながら。

low失敗そしてmediumがリカバーできず、だと、ボールはhighに。highはどうする?
作戦1:mediumを使わずにやるべきことをやる。
作戦2:成功するようにmediumの使いかたを変える。
作戦1はクリーン。だけど、コーディングが増える。
作戦2はいかがなものか。それができるということは、highがmediumとlowの内部処理について知っているということであり、callerからみてcalleeはブラックボックスになっているという関数抽象化の基本とバッティングしている。

The Lisp Way

ああ、たぶん、REPLでエラったときに、SLIMEがどうしますか〜と聞いてくるメニューの仕組みなんだな。

Conditions

この、Condition classes と通常のクラスの間の微妙な違い、嫌だなぁ。覚えることが無用に増える。

Condition Handlers

condition handlerのところメモ。

malformed-log-entry-errorが投げられたときに、何が起きるかは、call stack 上で、そのparse-log-entryより上にいるものによる。
deguggerに行くのをさけるには、その上にいるもののどれかで、a condition handlerを確立しなければならない。
a condition が発信されたとき、シグナル機構はa list of active condition handlersを調べる。
a condition handler は、それが取扱うconditionのspecifierと、そのconditionを唯一の引数とする関数からなる。
確立されたcondition handlersが複数ある場合、シグナル機構は、確立したのが直近の順に選択する。
handlersの関数が何もせずにリターンすれば、それは拒否をあらわし、制御はSIGNALに返る。
a handlerが処理を担当する場合は、nonlocal exitによって、制御をSIGNALからthe handlerに移す。
たいていの場合は、call stackを自分のところまで巻き戻すだけ。
HANDLER-CASEマクロはこの類のcondition handlerを作る。

あり? これでは普通のExecption機構とほとんど同じでは??
ああ、"JAVA-STYLE EXCEPTON HANDLING"というところにそう書いてあった。orz
このEXCEPTONは脱字。errataに出てなかったので送っといた。:)

Restarts

ここで看板通りの機構になった。
しかし、よくできてる。他の言語はなんで採用しないんだろう？

Providing Multiple Restarts
Other Uses for Conditions

特になし。

2008年1月13日日曜日

Chapter 18 A Few FORMAT Recipes

あせらず、じっくりやりたいのですが、ちょっとじれてきてもいます。一日一章で一ヶ月。やっぱり長いです。ちょっと加速してみようと思います。加速しても理解の深さは今までと同レベルをキープします。もしかしたら、ペースを崩して墓穴を掘るかもしれません。。。

前説

LOOP利用例をFORMAT利用例で焼き直しても。。。嫌われものどうしで比較してどうする。

試す。


CL-USER> (defun hoge (list)
           (loop for cons on list
                 do (format t "~a" (car cons))
                 when (cdr cons) do (format t ", ")))
HOGE                                                                                                                         
CL-USER> (hoge '(1 2 3 4))
1, 2, 3, 4
NIL
CL-USER> (defun piyo (list)
           (format t "~{~a~^,~}" list))
PIYO
CL-USER> (piyo '(1 2 3 4))
1,2,3,4
NIL
CL-USER> (defun puyo (list)
           (do ((rest list (cdr rest)))
               ((null rest) t)
             (if (cdr rest)
                 (format t "~a, " (car rest))
                 (format t "~a" (car rest)))))
PUYO
CL-USER> (puyo '(1 2 3 4))
1, 2, 3, 4
T
CL-USER>

まあ、出力したいだけなんだから、それをFORMATにまとめちゃうというのは私的にはありです。LOOPは、まだ気持ち悪いのですが。

The FORMAT Function

特になし。

FORMAT Directives

この本、語り部口調が売りだと思うのですが、この際箇条書きで書いてもらった方がわかりやすいと思うところもあるんだよね。。。

メモをとりながら。

全てのdirectivesは次の形となる。
~(prefix parameters)(a character)
- (a character)がdirectivesの本体というか名前。
- (prefix parameters)は無いこともある。
- (prefix parameters)は複数のパラメータの場合もある。その場合は、それらをカンマで区切る。
- (prefix parameters)のパラメータは、具体的な数でもよいし、外から渡してもよいし、#のようにdirectiveの形から算出されるものもあるし、:や@のように出力形式を指定するものもある。
- :と@の場合は、:@とすると両方の出力形式が採用される。形式としてバッティングする場合は、新しい出力形式が定義されている場合もあるし、何が出力されるかわからん場合もある。

Basic Formatting
Character and Integer Directives
English-Language Directives
Conditional Formatting

特になし。

Iteration

おお、~^は脱出なんだ。
"~{~#[~;~a~;~a and ~a~:;~@{~a~#[~;, and ~:;, ~]~}~]~}"。ウォーー

Hop, Skip, Jump
And More ...

特になし。

2008年1月12日土曜日

Chapter 17 Object Reorientation: Classes

前説

built-in classes には、subclassをつくることができない。

DEFCLASS

DEFSTRUCTは、backward compatibilityのためにあるといってよい。

Slot Specifiers

slotsがだぶっていた場合は、unionになるんだ。その合併ルールはなんだろ。

Object Initialization

特になし。

Accessor Functions

SETFのところが、すっと入らないのでメモ。

a SETF function は、SETF(macro)を拡張するひとつの方法。
"The name of a SETF function is a two-item list ...)" ここが理解できない。。。
SETF functionはDEFUNで定義するもんなんだから、その作りをどうしようが作り手の勝手ではないか?
後段ででてくるDEFCLASSが自動的に作るものの説明とごっちゃになっているような気がする。

WITH-SLOTS and WITH-ACCESSORS
Class-Allocated Slots
Slots and Inheritance

特になし。

Multiple Inheritance

ここもメモをとりながら。

複数のdirect superclassesをもてることは、the effective methodの構築とslot specifiersのマージを複雑にする。
DEFCLASSのdirect superclass listにて、左側のsuperclass程、more specificであるというルール。
それにしたがって、a linear class precedence listをつくる。class precedence listは、そのclassから見たとき、というものである。classの統一的な系統図ではない。あくまでそのclassから見た優先リストということ。
the same generic functionについて、複数のsuperclassで定義されているときにclass precedence listは役に立つ。

例えば、


(defclass money-market-account (checking-account savings-account) ())
(money-market-account
 checking-account
 savings-account
 bank-account
 standard-object
 t)

という状況にて、print-statementというジェネリック関数がcheck...とsaiving...の双方に定義されている場合。

何もしないと、money-market-accountのprint-statementは、check...のものになる。ここれ class precedence listが使われている。
money-market-accountのprint-statementの振舞を変更するにはいろいろなやり方がある。
ひとつめ。money-markege-account用に、print-statementを書く。
この方法の場合、check...はCALL-NEXT-METHODで呼べるが、saving...のとかを呼ぶ方法はない。そのコードを使おうと思ったら、saving...の内容を別関数にしておかねばならない。
ふたつめ。print-statementは全部CALL-NEXT-METHODにしておく。そうすると、money-market-accoutから見たclass precedence listでは、check...とsaving...が上のように並ぶので、両方呼ばれる。ただし、これはCALL-NEXT-METHODを書いときましょう、というコーディング規約の遵守が必要となる。
みっつめ。補助メソッドを使う。bank-account に対して、print-statementをprimaryとして定義する。check...とsaving...については、auxiliary(:after)としてそれぞれの処理を定義しておく。すると、money...に対するとprint-statementの呼び出しは、これら全てを実行する。

Good Object-Oriented Design

そうか、OO設計を学ぶには6ヶ月は覚悟が必要、なのか。
ただ、OOの本ってJavaで書かれているものが多いから、そのまえにJavaを読めるくらいになっとかないといけないかも。それも数ヶ月はかかりそう。無理かも。

登録: 投稿 (Atom)

Practical Common Lisp を読む

2009年1月12日月曜日

一年後

2008年7月18日金曜日

さらに、その後

2008年5月7日水曜日

その後

2008年1月24日木曜日

Chapter 32 Conclusion: What's Next?

Chapter 31 Practical: An HTML Generation Library, the Compiler

Chapter 30 Practical: An HTML Generation Library, the Interpreter

2008年1月23日水曜日

Chapter 29 Practical: An MP3 Browser

2008年1月22日火曜日

Chapter 28 Practical: A Shoutcast Server

Chapter 27 Practical: An MP3 Database

2008年1月21日月曜日

Chapter 26 Practical: Web Programming with AllegroServe

Chapter 25 Practical: An ID3 Parser

2008年1月19日土曜日

Chapter 24 Practical: Parsing Binary Files

Chapter 23 Practical: A Spam Filter

2008年1月15日火曜日

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

Chapter 22 LOOP for Black Belts

2008年1月14日月曜日

Chapter 21 Programming in the Large: Packages and Symbols

Chapter 20 The Special Operator

Chapter 19 Beyond Exception Handling: Conditions and Restarts

2008年1月13日日曜日

Chapter 18 A Few FORMAT Recipes

2008年1月12日土曜日

Chapter 17 Object Reorientation: Classes

ブログアーカイブ

自己紹介

2009年1月12日月曜日

2008年7月18日金曜日

2008年5月7日水曜日

2008年1月24日木曜日

2008年1月23日水曜日

2008年1月22日火曜日

2008年1月21日月曜日

2008年1月19日土曜日

2008年1月15日火曜日

2008年1月14日月曜日

2008年1月13日日曜日

2008年1月12日土曜日

ブログ アーカイブ

自己紹介

ブログアーカイブ