Archive for 3月, 2009

スペシャル変数とLET

日曜日, 3月 29th, 2009

Common Lispではdefvarを使ってグローバル変数を作ると、
その変数はスペシャル変数となり、無限スコープと動的エクステントを持つようになります。

(defvar *special* 99)
(defun f ()
(let ((*special* 1))
(g *special*)))
(defun g (x)
(+ x *special*))

上のプログラムから分かるように、*special*はどこからでも参照できます(無限スコープ)。
関数fのletにて、*special*に新たな値を設定すると、そのletを抜けるまでの間、
*special*の値は1に変わります(動的エクステント)。
よって、fのletがgにも影響して、 (f) => 2 となります。
しかし、これが正しく動作するのは*special*がスペシャル変数であるということを
処理系が知っているからです。関数fの定義だけを取り出してみると、
letで束縛している変数*special*が通常の変数なのかスペシャル変数なのか分かりません。
と、いうことでプログラムを次の様に書き換えてみました。

;;; test.lisp
(defun f ()
(let ((v 1))  ; この時点ではvがスペシャル変数であることが分からない
(g v)))
(defun f1 ()
(let ((v 1))
(declare (special v))  ; vはスペシャル変数だと明示的に宣言
(g v)))
(defvar v 99)  ; ここでvがスペシャル変数であることが分かる
(defun g (x)
(+ x v))  ; このvはスペシャル変数である
(defun h ()
(let ((v 1))  ; このvはスペシャル変数である
(g v)))

このプログラムをREPLで次の様に読み込ませて実行させます。

> (load "test.lisp") => T
> (f) => ???
> (f1) => ???
> (h) => ???

CLISP, CMUCL, SBCLでの結果は以下の通りでした。

(f) (f1) (h)
CLISP 2 2 2
CMUCL 2 2 2
SBCL 100 2 2

SBCLの (f) だけ値が他と違います。
これは、SCBLがロードとともに式をコンパイルするため、
関数fをコンパイルする時点で最適化により、vという名前が消失してしまうからでしょう。
(すると、fは単にgに1を適用することになり、gはスペシャル変数vに1を足し、結果は100となります)
CLISP, CMUCLでもcompile-fileしたものをロードすると (f)の値は100となりました。
ちなみに、変数の名前を*special*からvに変更しましたが、
*special*のままにして、SBCLでプログラムをロードすると次のような警告がでます。

; caught STYLE-WARNING:
;   using the lexical binding of the symbol (*SPECIAL*), not the
;   dynamic binding, even though the name follows
;   the usual naming convention (names like *FOO*) for special variables

「レキシカル変数のくせして、目立つんじゃねーよ!」ということですね。
このメッセージを読むと、スペシャル変数を誤ってレキシカル変数として扱う可能性は減るでしょう。
Let Over Lambdaではスペシャル変数をアスタリスクで囲わない方針をとっていますが、
誤ってdefvarの登場場所より前でその変数を使ってしまうことを考えると、
スペシャル変数はアスタリスクで囲ったほうがいいとおもいます。

Bivalent Stream

水曜日, 3月 25th, 2009

Common Lispのストリームは扱う型を指定する必要があり、
:element-typeにcharacterを指定してやると文字のみしか扱えず、
(unsigned-byte 8)を指定するとバイナリデータしか扱えません。
しかし、例えばHTTPの通信を行うプログラムを書いたりするときは、
ヘッダ部分を処理するときは文字列としてデータをやりとりしたいし、
データ本体を処理するときはバイナリデータをやりとりしたいので困ります。
CLISPではストリームが扱う型を動的に変更出きるので、
扱う型を変えたくなった時点で変更してやれば済みます。

#+clisp (setf (stream-element-type stream) '(unsigned-byte 8))

公式の説明
使い方
で、ここまでは知っていたんですが、これと同じことをSCBLではどうやるんだろうと調べてみたら、
Bivalent Streamというものがあり、これを使えば文字とバイナリの両方が使えるそうです。
作り方は:element-typeに:defaultを指定するだけ。

#+sbcl
(socket-make-stream
(socket-accept sock)
:input t :output t
:element-type :default
:buffering :full)

公式の説明
こりゃ便利です。
もう全部Bivalent Streamでいいと思いましたが、普通のストリームより遅いみたいです。

SBCLとか色々

日曜日, 3月 22nd, 2009

Common Lispで作っているWIkiエンジンですが、
今までCLISP専用だったものをSBCLでも動くようにしました。
変更することになったのは主に以下の三つです。
1. 文字コードまわり
2. ディレクトリ操作まわり
3. ネットワークまわり
文字コードまわりはCommon Lisp と 日本語 と 文字コード(LISPUSER)を参考にしました。
基本的にはcharset:utf-8を:utf-8に変えるのと、
ext:convert-string-from-bytesをsb-ext:octets-to-stringに変えるだけでした。
ディレクトリからファイル一覧を取得するための方法はPractical Common Lispの
15. Practical: A Portable Pathname Library
を参考にしました。処理系毎にちょっとずつ違うのは正直やっかい。
あと、ディレクトリの作成、削除にsb-posixパッケージののmkdirとrmdirを使用するように変更。
SBCLのネットワークまわりはある意味わかりやすく、そして面倒でした。
サーバの役割をするためには、まずinet-socketのインスタンスを作って、
sb-bsd-socktesパッケージのsocket-bind, socket-listen, socket-acceptを呼ぶだけ。
いくらわかりやすいとはいえ、少々面倒なのでもう少し楽な関数も欲しかったです。
sb-posixやsb-bsd-socketsパッケージを使うために、
requireを書かないといけないみたいですが、
これってどこに書くものなんでしょう。自分のパッケージを定義するファイル?
何はともあれ、これでSBCLでも動くようになりました。
CLISPで動かしてたときより速く動いた…ような気がします。
気がするだけかもしれません。

昨日、「Prologで大阪さんの事を論理的に考える集い」に参加してきました。
いろんなプログラミング言語についてわいわい話し合ってかなり楽しかったです。
ただ、大阪さんの話はほとんど出てきませんでした。
ちゃんとあずまんが大王を全巻読み直して準備してきたのに/(^o^)\

勝利の鍵はwrite-string

金曜日, 3月 20th, 2009

*前回のあらすじ*
文字列を一回なぞって単純な置換をするだけのプログラムの速度が
正規表現エンジンCL-PPCREを使って適当に書いた置換の速度に負けた。
*流石にこれは恥ずかしいので*
CL-PPCREのソースを少し眺めてみることにしました。
気になったのは新たな文字列をどうやって生成しているか。
探してみると、
1. with-output-to-stringでストリームを作成 (先に配列を作ったりはしない)
2. write-stringでストリームに書き込み
という感じになっていました。
*勝利の鍵はwrite-string*
write-stringがどんな関数だったか覚えていなかったので、HyperSpecで調べてみると、
ストリームに文字列を書き出すというのはprincと同じですが、文字列専用な上に、
キーワード引数:startと:endをとり、部分文字列を書き出せるようになってました。
これはどう考えてもprincにsubseqで切り出した文字列を書き出させるより速いはず。
ということで、自作プログラムを書き直して再度速度を比較。

;; 自作プログラム
Evaluation took:
0.005 seconds of real time
0.004562 seconds of total run time (0.004562 user, 0.000000 system)
100.00% CPU
6,969,080 processor cycles
560,584 bytes consed
;; CL-PPCRE
Evaluation took:
0.025 seconds of real time
0.025393 seconds of total run time (0.025393 user, 0.000000 system)
100.00% CPU
38,050,333 processor cycles
2,368,328 bytes consed

やりました。今度は見事に勝利しました。
もっとも、簡単な置換しかできないプログラムが、
正規表現エンジンに負けてたら洒落にならないんですけど(笑)
(と言いながら、CL-PPCREを上手く使ったプログラムに負けたらどうしよう…)
*おまけ*
inner-line-convertはこんな関数です。
マクロdef-inner-convertがどうなっているかは、
各自ご想像にお任せします。

(defun inner-line-convert (line)
(declare (optimize (speed 3) (safety 0) (space 0)))
(declare (string line))
(def-inner-convert (line)
("<" "&lt;")
(">" "&gt;")
("''" "<b>" "''" "</b>")
("'''" "<i>" "'''" "</i>")
("[[" "]]" #'inner-link)))

cl-ppcre使ってみた

火曜日, 3月 17th, 2009

ytakenakaさんに薦めて頂いたCL-PPCREを使ってみました。
あと、インストールの為にASDFも初めて使ってみることに。

;;; 最初からASDFが入っているSBCLで試しました
* (require 'asdf-install)
* (require 'asdf)
* (asdf-install:install :cl-ppcre)
;; 個人向けインストールかPC全体へのインストールか選択
;; ダウンロード先を信頼していいのか選択
* (asdf:oos 'asdf:load-op :clppcre)
;; これでCL-PPCREを使う準備が完了したみたいです

インストール時の質問が、デバッガを利用して作られており、なかなか面白かったです。
で、使い方もよくわからないままに、とりあえず自分のプログラムと速度を比べてみました。

(defvar *rep-text* "This is ''bold'' and '''italic''' test.")
(defun bench%% ()
(declare (optimize (speed 3) (safety 0) (space 0)))
(time
(dotimes (_ 1000)
(inner-line-convert (the string *rep-text*))))
(time
(dotimes (_ 1000)
(cl-ppcre:regex-replace-all
"''(.+)''"
(cl-ppcre:regex-replace-all "'''(.+)'''"
(the string *rep-text*)
(list "<i>" 0 "</i>"))
(list "<b>" 0 "</b>")))))
* (bench%%)
;; 自作プログラム
Evaluation took:
0.054 seconds of real time
0.054610 seconds of total run time (0.054610 user, 0.000000 system)
[ Run times consist of 0.004 seconds GC time, and 0.051 seconds non-GC time. ]
101.85% CPU
81,858,953 processor cycles
16,181,024 bytes consed
;; CL-PPCRE
Evaluation took:
0.026 seconds of real time
0.025287 seconds of total run time (0.025287 user, 0.000000 system)
96.15% CPU
37,694,210 processor cycles
2,367,952 bytes consed

見事に負けました。
それから、CL-PPCREかなり適当に書いたので、おそらくもっと頑張れそうです。
ボロ負け \(^o^)/

CLで文字列を扱う

火曜日, 3月 17th, 2009

それなりに速い文字列探索は書けましたが、
これを使って文字列の置換を行うプログラムを書いたら、
GCが頻繁に動きあまり速くありませんでした \(^o^)/
make-arrayで作った配列に、with-output-to-stringを使って
princで書き込むといった感じのプログラムを書いたんですが、
配列の大きさが足りなくなるのを恐れて:adjustableをtにしたのが速度を低下させてるかも。
けど、nilにしたところで、自分で境界のチェックとかした方が遅いかもしれません。
文字列の一部をコピーする際にsubseqしたものをprincで書き込んでるけど、
これは文字列のコピーが一旦作られるからGC発生の原因の一つになってそうです。
Cのmemcpyみたいな関数があればい\いんですけどね。
subseqの代わりにdisplaced-arrayでも\使えばいいのか?
CLで高速な文字列操作を行うのは色々とコツがいりそうです。
*恐怖! 処理系組み込みのsearchは遅かった!?*
(追記)SBCLは一工夫でかなり速くなりました。最後まで読んでね。
なんだか悲しい事実を知ってしまいました。

(defmacro! dfa-search (str1 str2 &key start2 end2)
`(dfa-multi-search (,str2 ,g!pos :start ,start2 :end ,end2)
,str1 ,g!pos))

dfa-searchは見ての通り、dfa-multi-searchのラッパーです。
dfa-multi-searchは複数の候補をDFAを使って探索しますが、
候補が一つしかない場合は、単に文字列を先頭から1文字ずつ見るだけなので、
決して特別速いコードは生成されません。

(defvar *text*
"Function SEARCH
...(全体で1490文字)...
matching subsequence is returned.")
(defun bench% ()
(declare (optimize (speed 3) (safety 0) (space 0)))
(time (progn (dotimes (i 1000) (search "Syntax" *text*))
(dotimes (i 1000) (search "Arguments" *text*))
(dotimes (i 1000) (search "Description" *text*))
(dotimes (i 1000) (search "\\(^o^)/" *text*))))
(time (progn (dotimes (i 1000) (dfa-search "Syntax" *text*))
(dotimes (i 1000) (dfa-search "Arguments" *text*))
(dotimes (i 1000) (dfa-search "Description" *text*))
(dotimes (i 1000) (dfa-search "\\(^o^)/" *text*)))))

HyperSpecのsearchの説明(の一部)から4種類の文字列を
searchとdfa-searchで検索してみました。
結果は次の通りです。

;;; CLISP
;; search
Real time: 1.104947 sec.
Run time: 1.085989 sec.
Space: 0 Bytes
;; dfa-search
Real time: 0.768655 sec.
Run time: 0.746108 sec.
Space: 0 Bytes
;;; SBCL
;; search
Evaluation took:
0.139 seconds of real time
0.138718 seconds of total run time (0.138718 user, 0.000000 system)
100.00% CPU
208,102,940 processor cycles
0 bytes consed
;; dfa-search
Evaluation took:
0.048 seconds of real time
0.048145 seconds of total run time (0.048145 user, 0.000000 system)
100.00% CPU
72,104,234 processor cycles
0 bytes consed
;;; CMUCL
;; search
; Evaluation took:
;   0.33 seconds of real time
;   0.31113 seconds of user run time
;   0.0 seconds of system run time
;   488,008,050 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; dfa-search
; Evaluation took:
;   0.09 seconds of real time
;   0.071036 seconds of user run time
;   0.0 seconds of system run time
;   125,955,056 CPU cycles
;   0 page faults and
;   0 bytes consed.

search遅い!!!
自分の書いたプログラムの方が速かったのに、全然嬉しくない…
基本的な関数なんだからしっかりと最適化してほしいです。
(それとも、ひょっとすると本物のLisperはあまりsearchを使わないのか?)

CLでCと速度を競ってみた

日曜日, 3月 15th, 2009

前のエントリーで書いたdfa-multi-searchの展開形がメモリを食う原因は、
labelsで作った関数を呼んでいたことみたいです。
インライン化して、ついでに型宣言と最適化オプションもつけたところ、
だいぶ速くなってきました。

;;; CLISP
Real time: 0.427904 sec.
Run time: 0.416979 sec.
Space: 0 Bytes
;;; SBCL
Evaluation took:
0.025 seconds of real time
0.024786 seconds of total run time (0.024786 user, 0.000000 system)
100.00% CPU
37,124,872 processor cycles
0 bytes consed

このあたりまできたら、Cとも張り合えるんじゃないかと思い、
似たようなソースをCで書いてみました。

#include <stdio.h>
#include <string.h>
#include <sys/time.h>
char test_data[4][64] = {"This ''text'' is bold sample.",
"This '''text''' is italic sample.",
"This %%text%% is torikeshi sample.",
"This ((text)) is footnote sample."};
int aho_search (char *str)
{
if (strstr(str, "'''")) {
return 0;
}
else if (strstr(str, "''")) {
return 1;
}
else if (strstr(str, "%%")) {
return 2;
}
else if (strstr(str, "((")) {
return 3;
}
return -1;
}
int baka_search(char *str)
{
int state = 0;
for (;;) {
if (*str == '\'') {
if (state == 1) state = 2;
else if (state == 2) return 0;
else state = 1;
}
else if (state == 2) {
return 1;
}
else if (*str == '%') {
if (state == 11) return 2;
else state = 11;
}
else if (*str == '(') {
if (state == 21) return 3;
else state = 21;
}
else {
state = 0;
}
if (*str == '\0') {
break;
}
str++;
}
return -1;
}

strstrを使ったアホな検索をするaho_search、
出来の悪い状態遷移を使ったbaka_search、
この二つをCLの時と同様に10000回ずつ呼んでみました。
処理系はGCC4.2.1で最適化オプションは無しです。

0.038932sec (aho_search)
0.011319sec (baka_search)

SBCLとならかなりいい勝負になってます。
「いい勝負とか言いながら、2倍以上差がついとるで!」
という意見ももちろんあるでしょうが、
baka_searchみたいな関数を、あまり手書きで書きたくないことも考慮に入れれば、
CLの方が勝っていると言えるだろうという私の独断と偏見を書いておきます(笑)
それにしてもstrstrは速いですね。どうなってるんだろ…
*追記*
CMUCLでも試したら、その速さに驚きました。
ただ、searchはSBCLより遅いみたいです。

;;; CMUCL
* (bench)
;; aho-search
; Evaluation took:
;   0.77 seconds of real time
;   0.756969 seconds of user run time
;   0.0 seconds of system run time
;   1,154,705,100 CPU cycles
;   0 page faults and
;   0 bytes consed.
;; use-dfa
; Evaluation took:
;   0.02 seconds of real time
;   0.017071 seconds of user run time
;   0.0 seconds of system run time
;   29,234,741 CPU cycles
;   0 page faults and
;   0 bytes consed.

複数の文字列を1passで検索

土曜日, 3月 14th, 2009

無駄に長くなりそうなので先に結論から。
バカな文字列検索と比べると速い文字列の検索のコードを書きました。
オートマトンとか使ってるからちょっと格好良くなった気分です。

(defvar *test-data* #("This ''text'' is bold sample."
"This '''text''' is italic sample."
"This %%text%% is torikeshi sample."
"This ((text)) is footnote sample."))
(defun aho-search (str)
(cond ((search "'''" str) 'italic)
((search "''" str) 'bold)
((search "%%" str) 'torikeshi)
((search "((" str) 'footnote)))
(defun use-dfa (str)
(dfa-multi-search (str)
"''"  'bold
"'''" 'italic
"%%"  'torikeshi
"(("  'footnote))
(defun bench ()
(time (dotimes (i 100000) (aho-search (aref *test-data* (mod i 4)))))
(time (dotimes (i 100000) (use-dfa (aref *test-data* (mod i 4))))))

aho-searchが「バカな文字列検索」。
use-dfaが「今回作った文字列検索」。
CLISPとSBCLでbenchを呼んで2つの関数の速度を比べてみました。

;;;CLISP
> (bench)
;; aho-search
Real time: 2.924899 sec.
Run time: 2.813147 sec.
Space: 0 Bytes
;; use-dfa
Real time: 0.822901 sec.
Run time: 0.779974 sec.
Space: 11600000 Bytes
GC: 17, GC time: 0.177573 sec.
NIL
;;;SBCL
* (bench)
;; aho-search
Evaluation took:
0.391 seconds of real time
0.367416 seconds of total run time (0.367416 user, 0.000000 system)
93.86% CPU
584,719,558 processor cycles
0 bytes consed
;; use-dfa
Evaluation took:
0.079 seconds of real time
0.057791 seconds of total run time (0.057791 user, 0.000000 system)
73.42% CPU
118,089,578 processor cycles
1,601,536 bytes consed

めちゃくちゃ速くなった反面、メモリを使いすぎてます。
原因は不明。どうやってメモリ使用量を減らせれるかが今後の課題です。
(ここまで結論でした。)


ちょっとずつですが、Common LispでWikiをつくってます。
で、Wiki文法からHTMLへの変換の際の文字列処理の話を少し。
Wiki文法からHTMLへの変換規則の一例として、
– 「”bold”」と出会ったら「<b>bold</b>」に変換
– 「”’italic”’」と出会ったら「<i>italic</i>」に変換
といったものがあります。
で、私が「とりあえず動けばいいや」で最初に書いたコードはというと、
searchで文字列から「”’」を探して変換して、「”」を探して変換して…
と言ったものでした。非常にばかばかしくて素晴らしいです。
「じゃあ、正規表現を使えばええやん」
という意見が飛んできそうですが、それじゃあ面白くない
正規表現を使っても以下のような問題がありそうです。
1) 変換規則の数だけ文字列全体を走査しないといけない
2) 「”」の前に「”’」を探さないといけないといった制約がある
(拡張された正規表現をガリガリ書ける人は上手く書けるのかもしれませんが…)
「単純な文字列の変換処理くらい1passで終わらせたいよね」という考えを前提にして、
「検索候補が複数書けるsearchがあればいいんじゃないか」という結論にたどり着きました。

(multi-search "''" "'''" "%%" "((" target)
=> (最初に)どの文字列にtargetの何文字目でヒットしたか

どの文字列にヒットしたかであとで条件分岐するのはほぼ確実なんだから
ということで、

(multi-search (target pos)
"''"  `(bold at ,pos)
"'''" `(italic at ,pos)
"%%"  `(torikeshi at ,pos)
"(("   `(footnote at ,pos))

こんな風に書けるようにしよう。
と、目標を定めたところで作り始めました。
「探す文字列は先に決まっているんだから、効率のよいコードを生成しよう。」
ということで、決定性有限オートマトンを作って探索をすることに。
だいたいこんな感じです。
文字列のリスト -> NFA -> DFA -> Lispコード
(NFA : 非決定性オートマトン, DFA : 決定性オートマトン)
「NFAはすぐに作れるし、DFAに変換するのも教科書的なやり方で充分だろう」
と最初は思ったんですが、よくよく考えてみると少々厄介でした。
pat1 = aa
pat2 = baaab
pat3 = aaac
文字列の中から上記pat1, pat2, pat3を検索する場合、入力が
「baaab」の場合 => 0文字目でpat2にヒット
「baaac」の場合 => 1文字目でpat3にヒット
「baaad」の場合 => 1文字目でpat1にヒット
こんな風に動作して欲しいんですが、ただただDFAを作るだけではこれが実現出来ません。
ヒットするものの候補が複数ある場合、
A) より手前でヒットしたものが優先
B)同じ時点でヒットしたものがあれば長い物を優先
という規則で動作して欲しいので、これを考慮してDFAを構築することにしました。
規則Aは、NFAにおいて「初期状態から何回で遷移可能か」という情報から、
「何文字手前からヒットし始めたか」という情報が得られるので、
これを使ってDFAの遷移から不要なものを消すことによって達成出来ました。
規則Bは、規則Aさえ満たしていれば、「最後に到達した受理状態」を覚えておき、
遷移できなくなれば、それを使うという風にすればすぐに出来ました。
そんなこんなでエントリー冒頭の結論に辿り着きました。
なんであんなにメモリを食うのか、現状ではまったく分かりません。
マクロの展開形を載せておくので、原因が分かった人はこっそり教えてください(笑)

CL-USER> (macroexpand-1
'(dfa-multi-search (str)
"''"  'bold
"'''" 'italic
"%%"  'torikeshi
"(("  'footnote))
(LET ((#:STR131488 STR))
(LET (#:LAST-POS131490 #:LAST-STATE131491)
(BLOCK #:BLOCK131484
(LABELS
((#:TRANS131486 (#:STATE131487 #:CHAR131483 #:POS131489)
(CASE #:STATE131487
((T)
(CASE #:CHAR131483 (#\( '#:G131507) (#\% '#:G131506) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131507)
(CASE #:CHAR131483 (#\( '#:G131508) (#\% '#:G131506) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131508) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131502)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131506)
(CASE #:CHAR131483 (#\% '#:G131509) (#\( '#:G131507) (#\' '#:G131505)
(OTHERWISE T)))
((#:G131509) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131499)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131505)
(CASE #:CHAR131483 (#\' '#:G131510) (#\( '#:G131507) (#\% '#:G131506)
(OTHERWISE T)))
((#:G131510) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131492)
(CASE #:CHAR131483 (#\' '#:G131511)
(OTHERWISE (RETURN-FROM #:BLOCK131484 T))))
((#:G131511) (SETF #:LAST-POS131490 #:POS131489)
(SETF #:LAST-STATE131491 '#:G131495)
(CASE #:CHAR131483 (OTHERWISE (RETURN-FROM #:BLOCK131484 T)))))))
(DO
((#:STATE131487 T) (#:POS131489 0 (1+ #:POS131489))
(#:LEN131485 (LENGTH #:STR131488)))
((>= #:POS131489 #:LEN131485)
(#:TRANS131486 #:STATE131487 #\Null #:POS131489) NIL)
(SETF #:STATE131487
(#:TRANS131486 #:STATE131487 (AREF #:STR131488 #:POS131489)
#:POS131489)))))
(CASE #:LAST-STATE131491 ((#:G131502) (LET NIL 'FOOTNOTE))
((#:G131499) (LET NIL 'TORIKESHI)) ((#:G131492) (LET NIL 'BOLD))
((#:G131495) (LET NIL 'ITALIC)))))
T

sharp-backquoteとsharp-lambda

月曜日, 3月 2nd, 2009

Let Over Lambdaの6章に『#`』というリーダマクロが出てきます。
バッククォートされたものを返す関数を作るためのもので、以下のように定義されています。

(defun |#`-reader| (stream sub-char numarg)
  (declare (ignore sub-char))
  (unless numarg (setq numarg 1))
  `(lambda ,(loop for i from 1 to numarg collect (symb 'a i))
    ,(funcall (get-macro-character #\`) stream nil)))

これをset-dispatch-macro-characterで登録してやれば、
次のような感じに使えます。
CL-USER> ‘#`(car ,a1)
(LAMBDA (A1) `(CAR ,A1))
CL-USER> (mapcar #`(,a1 (gensym)) ‘(x y z))
((X (GENSYM)) (Y (GENSYM)) (Z (GENSYM)))
ちょっと便利そうだけど、そこまで使うのか?
と少し疑問に思いましたが、今までに自分が書いたソースを見直してみると、
(lambda (x) `(…簡単な式…))
というパターンが結構ありました。これを使うとかなり簡潔に書けそうです。
しかし、バッククォートで囲わないで、生のlambda式を作るリーダマクロの方が
むしろ便利ではないのかと思い、作ってみました。

(defun |#^-reader| (stream sub-char numarg)
  (declare (ignore sub-char))
  (unless numarg (setq numarg 1))
  `(lambda ,(loop for i from 1 to numarg collect (symb '$ i))
    ,(read stream t nil t)))

lambda式のsyntax sugarということで、『#^』(sharp-lambda)と命名しました。
引数がa1, a2, …となるのは個人的に気に入らなかったので、
$1, $2, …という名前に変えました。この方が所見の人もきっと分かりやすいはず。多分。

CL-USER> '#^(car $1)
(LAMBDA ($1) (CAR $1))
CL-USER> (mapcar #^(car $1) '((a b) (c d) (e f)))
(A C E)

$0でその関数自身をさせるようにしてもいいかも知れません。
(lambdaの代わりにlabelsを使えばすぐにできますし。)
#^を使ってlambda式を書き直していくと、ソースがかなり簡潔になりました。
これはかなり便利かも。ただ、他人が読みにくくなるという問題がありますね。
私は、lambdaと入力するのはさほど手間に思っていません。
‘l’をタイプすると自然に指が残りの文字をタイプしてくれますし、
どうしても面倒ならエディタの補完機能を使えば全く手間がかかりません。
私が面倒に思うのはlambdaに伴う括弧です。
lambda自身を囲む括弧に、引数を囲む括弧。
「括弧は友達、怖くないよ」とはいえ、何度も打ってると面倒になってきます。
ちょうど一年前、フムフムヌクヌクアプアア本でcut(srfi-26)をはじめて知ったときは、
かなり気持ち悪く見えたのに、今ではこういったものが必要不可欠にみえてきます。
この悲惨なキーボードを修理もせずに使い続けた結果、
括弧を減らせるマクロを求めるようになってきたのかもしれませんが(笑)

続・defmacro!

月曜日, 3月 2nd, 2009

defmacro!を知って以来、defmacro!なしにマクロを書けない体になってしまいました。
Let Over Lambdaは体に毒です。注意しましょう。
実際にdefmacro!を使うようになって気になったことを二つほど。
*なぜprogn*
Let Over Lambdaでのdefmacro!の定義は次のようになっています。

(defmacro defmacro! (name args &rest body)
(let* ((os (remove-if-not #'o!-symbol-p args))
(gs (mapcar #'o!-symbol-to-g!-symbol os)))
`(defmacro/g! ,name ,args
`(let ,(mapcar #'list (list ,@gs) (list ,@os))
,(progn ,@body)))))

この定義を見て気になったのが最後の行のprognです。
続くのが ,@body だけなら、わざわざprognで囲まなくても、
,,@body
とだけ書けば充分じゃないのかと思い、そう書き換えてみました。
書き換えて使ってもまったく問題が無かったのでそのままにしていたんですが、
ある時にそのprognの意味を知らされました。

(defmacro! hoge (&rest args)
(unless (= (mod (length args) 2) 0)
(error "odd number of arguments"))
...))

prognがない場合、unlessが返すNILが取り残され、
(hoge 1 2 3 4) などの展開形が次のようになってしまいます。

(let (...)
NIL
...)

何の説明もなく、おまけのように付属しているprognが、
実は意味を持っていたというのはやられました。
*引数の分配に対応してない*
勝手に取り外したprognを付けなおし、
定義どおりのdefmacro!を使っていたら、
今度は次のようなコードを書いた際にコンパイルエラーが発生しました。

(defmacro! foo ((o!bar &optional ...) &rest rest)
...)

defmacro!の定義を見直してみれば一目瞭然。
(remove-if-not #’o!-symbol-p args)
と、argsが平らであるのが前提なコードが書いてあるので、
(flatten args) という風にリストを平坦化することで対応しました。

ああ、それから去年の夏頃に「CLでwikiをつくってるよー」と言ってましたが、
最近もちょびちょび触っています。夏の時点で一通りの機能を持っていたんですが、
その頃のCommon Lispの知識が余りに乏しかったため、
汚いコードや無意味なコード(もともとある関数を自分で書いてたり)が多数あり、
書き直しばかりで、なかなか新しい機能を作れないです(笑)