06022009 lisp
memoizeというのを使ってみた。
(asdf:oos 'asdf:load-op 'memoize)
(defun fib (n)
(if (<= n 1)
1
(+ (fib (- n 1))
(fib (- n 2)))))
(memoize:def-memoized-function fibm (n) (if (<= n 1)
1
(+ (fibm (- n 1))
(fibm (- n 2)))))
実行
* (fib 40) ; 結構待たされる
165580141
* (fibm 40) ; 一瞬
165580141
SBCLでベンチマークの取り方がわからん。
05022009 lisp
aserveのクライアントを使ってlast.fmの自分のベストトラックのXMLをとってくる。
Common Lisp と 日本語 と 文字コードによるとバイナリでゲットしてエンコードすべしとのことだったのでそうした。
(asdf:oos 'asdf:load-op 'aserve)
(setq result (net.aserve.client:do-http-request
"http://ws.audioscrobbler.com/2.0/user/kzfm/toptracks.xml"
:format :binary))
(sb-ext:octets-to-string result :external-format :utf8)
結果。
"<?xml version=\"1.0\" encoding=\"UTF-8\"?>
<toptracks user=\"kzfm\" type=\"overall\">
<track rank=\"1\">
<name>Imaginary Folklore</name>
<playcount>169</playcount>
<mbid></mbid>
<url>http://www.last.fm/music/Clammbon+By+Nujabes/_/Imaginary+Folklore</url>
<streamable fulltrack=\"0\">0</streamable>
<artist>
<name>Clammbon By Nujabes</name>
<mbid></mbid>
<url>http://www.last.fm/music/Clammbon+By+Nujabes</url>
</artist>
</track>
<track rank=\"2\">
<name>アンパンマンのマーチ</name>
<playcount>77</playcount>
こんな感じで、割と簡単にできた。あとはパースすればよいですな。
27012009 lisp
macbook+sbcl+aserve(asdfで入れた)で起動するとSB-THREADがないというエラー。
* (net.aserve:start :port 8888)
debugger invoked on a SIMPLE-ERROR:
PROCESS-PRESET: Calling a multiprocessing function on a single-threaded sbcl build
Type HELP for debugger help, or (SB-EXT:QUIT) to exit from SBCL.
restarts (invokable by number or by possibly-abbreviated name):
0: [ABORT] Exit debugger, returning to top level.
SB-THREAD付きでコンパイルしろということらしい。ソースのINSTALLに書いてある通りに customize-target-features.lispってファイルを作って、中に以下のように書いておく
(lambda (features)
(flet ((enable (x)
(pushnew x features))
(disable (x)
(setf features (remove x features))))
;; Threading support, available only on x86/x86-64 Linux, x86 Solaris
;; and x86 Mac OS X (experimental).
(enable :sb-thread)))
で、インストール。これでOK。
さて、Common Lisp と AllegroServe(Aserve) で作る Web アプリケーションのサンプルを実行してみた。
* (net.aserve:start :port 8888)
#<NET.ASERVE:WSERVER port 8888 {12085CC9}>
* (net.aserve:publish
:path "/"
:content-type "text/html; charset=euc-jp"
:function
#'(lambda (req ent)
(net.aserve:with-http-response
(req ent)
(net.aserve:with-http-body
(req ent)
(net.html.generator:html
(:html
(:head (:title "Hello World!"))
(:body "Hello World!"
:br "こんにちは!")))))))
#<NET.ASERVE:COMPUTED-ENTITY {12E5B679}>
* aserve-accept-6: 01/26/09 - 20:44:57 - accept: error 0 on accept invalid \
keyword argument: :AUTO-CLOSE (valid keys are
:INPUT, :OUTPUT, :ELEMENT-TYPE, :EXTERNAL-FORMAT,
:BUFFERING, :TIMEOUT).
なにがinvalid keyword argumentなのかわからん。linuxに入れたsbclだと快適に動いている(日本語は表示されないけど)。
これが動かないと実践Common Lispが先に進まないんだよなぁ。
Gaucheだとこんな感じに設定しておけば、C-cSでウィンドウを2つに分け、一方でgoshインタプリタを実行するコマンドを定義する。
これをSlimeでもやりたかったので調べてみたところ、
(global-set-key "\C-cs" 'slime-selector)
と.emacsに書いておけばC-cs[?cdeilt]でバッファを切り替えられるらしい。
?: Selector help buffer. c: SLIME connections buffer. d: *sldb* buffer for the current connection. e: most recently visited emacs-lisp-mode buffer. i: *inferior-lisp* buffer. l: most recently visited lisp-mode buffer. t: SLIME threads buffer. v: *slime-events* buffer.
とりあえずこれでいいかな。
27012009 lisp
On Lisp 22章
まずはschemeでの非決定性計算のコードを解説してから、マクロ使って実装していくという流れで、継続の時と同じ構成。schemeは継続をサポートしているのでコードが分かりやすくていい。
マクロの写経。継続マクロは前書いたヤツを使う。
(defparameter *paths* nil)
(defconstant failsym '@)
(defmacro choose (&rest choices)
(if choices
`(progn
,@(mapcar #'(lambda (c)
`(push #'(lambda () ,c) *paths*))
(reverse (cdr choices)))
,(car choices))
'(fail)))
(defmacro choose-bind (var choices &body body)
`(cb #'(lambda (,var) ,@body) ,choices ))
(defun cb (fn choices)
(if choices
(progn
(if (cdr choices)
(push #'(lambda () (cb fn (cdr choices)))
*paths*))
(funcall fn (car choices)))
(fail)))
(defun fail ()
(if *paths*
(funcall (pop *paths*))
failsym))
これを使って二つの数の和が与えられた数になるような組み合わせを見つける
(=defun two-nubers ()
(choose-bind n1 '(0 1 2 3 4 5 6 7 8 9)
(choose-bind n2 '(0 1 2 3 4 5 6 7 8 9)
(=values n1 n2))))
(=defun parlor-trick (sum)
(=bind (n1 n2) (two-nubers)
(if (= (+ n1 n2) sum)
`(the sum of ,n1 ,n2)
(fail))))
実行
* (parlor-trick 5)
(THE SUM OF 0 5)
* (parlor-trick 15)
(THE SUM OF 6 9)
ちゃんと動いている。
尚、後半にカットの説明があった。要するにやらなくてもよい計算をカットする仕組みってことね。これも継続を使っている。
chooseはどのnならば引き続く計算処理が失敗しないかを、推定できるかのように機能しなければならない
25012009 lisp
バイナリファイルのパースがあまり面白さを感じられないのでちょっと遠のいていたのだけど、週末でまとまった時間が取れたのでやってみた。バイナリファイルのパーサーを買いて、その流れでMP3のID3タグを読み書きしていくという。
バイナリファイルの読み書きのあたりは面白かったのだけど、途中からついていけなくなってしまい、いい加減に読み進めてしまった。さらに後の章でこれを使ってMP3ストリーミングサーバーを実装するらしいので、また読みなおすことになりそうだ。
この本ちょっと気になってきた
Programming Clojure (Pragmatic Programmers)どうなんだろうか？
22012009 lisp
Common Lispで継続(On Lisp20章)。
On Lisp
実践Common Lisp(setq *cont* #'values)
(defmacro =lambda (parms &body body)
`#'(lambda (*cont* ,@parms) ,@body))
(defmacro =defun (name parms &body body)
(let ((f (intern (concatenate 'string
"=" (symbol-name name)))))
`(progn
(defmacro ,name ,parms
`(,',f *cont* ,,@parms))
(defun ,f (*cont* ,@parms) ,@body))))
(defmacro =bind (parms expr &body body)
`(let ((*cont* #'(lambda ,parms ,@body))) ,expr))
(defmacro =values (&rest retvals)
`(funcall *cont* ,@retvals))
(defmacro =funcall (fn &rest args)
`(funcall ,fn *cont* ,@args))
(defmacro =apply (fn &rest args)
`(apply ,fn *cont* ,@args))
大事なのは、今や私たちは独自に制御できる関数呼び出しとreturnを手にしており、その気になれば他のいろいろなことができるということだ。
21012009 lisp
On Lisp15章。マクロで遅延評価を実装
(defconstant unforced (gensym))
(defstruct delay forced closure)
(defmacro delay (expr)
(let ((self (gensym)))
`(let ((,self (make-delay :forced unforced)))
(setf (delay-closure ,self)
#'(lambda () (setf (delay-forced ,self) ,expr))) ,self)))
(defun force(x)
(if (delay-p x)
(if (eq (delay-forced x) unforced)
(funcall (delay-closure x))
(delay-forced x))
x))
これを使う場合
(let ((x 2))
(setq d (delay (1+ x))))
そのままでは評価されない
d
#S(DELAY :FORCED #:G748 :CLOSURE #<CLOSURE (LAMBDA #) {12234AF5}>)
forceしてやる
(force d)
3
19012009 lisp
あまりのわからなさに一年以上放ってあったOn Lispを再開。マクロの章を出張の新幹線の中で読む。
新幹線のなかだと集中できてよいが、内容の半分も理解できないなぁ。まぁ、何度か読みなおせばいいからとりあえずざっと一通り読むつもり。
今の仕事の流れだとinductive logic programmingを理解してないとまずかろうと思うことがあったので、24章のlispによるPrologの実装まではなんとか進みたい。
On Lisp