リリカル☆Lisp開発日記

あるとき、emacs上でSLIMEを動かしながらCLのコードを書いてると、
突然HDDアクセスが多発して、ほとんどフリーズに近い状態になりました。
調べてみたら、Lispプロセスが一人でメモリを500MB以上も使っていました。

図1. メモリを食いつくすLispプロセス
一度プロセスを殺して再起動したら直りましたが、時々同じ現象に遭遇します。
メモリを512MBしか積んでいない私のPCにはこれはかなり致命的なのですが、
たまにしか起こらないので原因がよく分からず非常に困りました。
分かっているのは、この現象が起こると同時にemacsとSLIMEのコネクションが切れるということだけ。
そういや、CLISPは使用するメモリの量をあらかじめ制限できたような出来なかったような…
それができたらどうにかなるかも。…根本的な解決策じゃない気もしますが(笑)

CLには特定の文字をマクロ文字に昇格(?)させてreaderの動作を変化させる、
set-macro-characterという関数が用意されていますが、
逆にマクロ文字を普通の文字に降格させる関数(unset-macro-characterと命名)がありません。
readtableをいじり回したいお年頃の私にはこれがなかなかつらいです。
で、無いものを嘆いても仕方ないので作ってみました。

(defmacro unset-macro-character (char)
`(set-macro-character ,char
#'(lambda (s c)
(declare (ignore c))
(let ((next1 (peek-char nil s nil (code-char 0) t))
(next2 (peek-char t s nil (code-char 0) t)))
(multiple-value-bind (mc nt)
(get-macro-character next1)
(if (or (char= next1 (code-char 0))
(not (char= next1 next2))
(and mc (not nt)))
(values (intern (string ,char)))
(values
(intern
(format nil "~A~S" (string ,char) (read s nil nil t))))))))
t))

基本方針として、
—
1. 指定した文字(char)に新たな関数を割り当てる
(その際に、set-macro-characterの第3引数にtを与え、区切り文字でなくす。)
2. その関数は次の文字が
　A. 空白文字の場合、文字charのみからなるシンボルを返す
　B. マクロ文字で区切り文字の場合、Aと同様
　C. 文字の終端の場合、Aと同様
　D. それ以外の場合、文字charと次にreadしたもの(おそらく数かシンボル)をつなげたシンボルを返す
—
というものです。
面倒だったので、大文字、小文字の区別に付いては特に考えていません。
valuesは戻り値を1つにするために使っています。
(internは値を2つ返しますが、リーダマクロ関数は戻り値の数は0か1と決まっているためです)
(code-char 0)はちょっとまずいかも…
で、動かしてみました。

CL-USER> (let ((*readtable* (copy-readtable)))
(unset-macro-character #\,)
(read-from-string "(a,b, c,(d) ,e)"))
(|A,B,| |C,| (D) |,E|)

なんか知らんけど、上手く動いたぞ。
わーい。

気分はこんな感じ
ただ、あまり考えてないので、ちょっと複雑なものがやってくると、
正しく動作しないかもしれません。
(直後にディスパッチング文字なんかがやってくるとまずいかも…)

時の人tazantさんのブログ「Lispのひび」にて最近書かれているquoteについて、
いくつが疑問が溜まってきたのでまとめて書き散らしています。
***全ての始まり***

独自の仕様については、バッククォートもクォートも同じクォートして扱う。
バッククォートはクォートの進化系だから。
リストを作るときも「’」を使い、consの代わりにも、appendの代わりにもなる。
(2008-09-20 マクロ)

「クォートとバッククォートの同一視」をして大丈夫なのかが最大の論点。
私はこれに対しては懐疑的。
CL等の

(defmacro my-search (key)
`(assoc ',key *a-list*))

や

(defmacro abbrev (shot long)
`(defmacro ,short (&rest args)
`(,',longlame ,@args)))

はどうやって表現するのか気になります。
(2つ目のプログラム片はOn Lisp 16.1節「省略」より)。
***’,foo or ‘(,foo)***

,x = (comma x)です。’(comma foo) = ‘(,foo)となるようになっています。
これはある程度独自な仕様ですから、そこら辺はご了承ください。
***中略***
‘(comma foo)と’,fooの区別は付きませんね。
(2008-09-20 マクロの世界へ)

[疑問1]
‘(comma foo) は結局 ‘(,foo) なのか ‘,foo なのかどっち？
私としては ‘(,foo) に展開されると少々やりにくい気がしますが…
***quoteはcommaが無くても特別?***

基本的に評価基準は一致しています。重大なことに気が付きました。
quoteは「,」をつけない限り、そのままです。次の例でどうでしょうか。
***中略***
よって、’(‘bar baz)というリストを作りたいなら、こうなります。

'('quote (('quote bar) baz))
;=> (quote ((quote quote) (((quote quote) bar) baz)))
;=> (quote (quote (((quote quote) bar) baz)))
;=> (quote (quote ((quote bar) baz)))
;=> (quote ((quote bar) baz))
=> '('bar baz)

(2008-09-20 マクロの世界へ – 2)

shiro 2008/09/21 03:27 ふーむ。クオートされた式中において、
1. (quote quote) は quote に置換
2. (quote comma) は comma に置換
3. (comma expr) は exprを評価して置き換え
4. 置換の結果生成されたquote, commaはその効力を失う
とすれば良いのかな。
(上同記事コメント欄)

[疑問2]
『quoteは「,」をつけない限り、そのまま』とのことですが、
実際には(quote quote) の動作が特別扱いされるんですよね。
(quote ((quote quote) a)) を評価すると (quote a)でしょうか？
***,@的な動作の例が見たい***

commaの仕様は、
* ,@みたいなもの。アトムならそのまま付け加える。
* リストなら外の()を外す。もし付けたいなら,(…)でいい
(2008-09-21 マクロの仕様)

[疑問3]
「もし付けたいなら,(…)でいい」とはどういうことでしょうか。
,(func arg)は関数呼び出しとなってしまうため、
括弧を付けたい、取りたいとは別問題になってしまう気がします。
[疑問4]
古い記事に戻りますが、

(= filter (macro (func arg) '(,func ,arg)))
=> (macro (func arg) '(,func ,arg))
(filter reverse '(1 2 3))
; 内部での状態=> (quote ((comma func) (comma arg)))
; quote評価後=> (reverse '(1 2 3))
; もう一度、マクロの最後を評価=> (3 2 1)
=> (3 2 1)

(2008-09-20 マクロ2)

commaがCLの,@のようにリストの外の()を消してしまうなら、
(quote ((comma func) (comma arg)))
は
(reverse 1 2 3)
となってしまうのではないでしょうか。
***マクロ引数の展開***

fujita-y 2008/09/21 12:14
もしかして、

(= func (lambda (x) (+ x x))
(= hoge (macro (x) '(x ,(x 1))))
(hoge func)
=> (quote (func ,(func 1)))
=> (quote (func 2))
=> (func 2)

ってことなのかな？

tazant 2008/09/21 13:16
マクロ引数(x)は展開時には評価されずに、
マクロとして再評価すると呼び出し元+引数の環境下で
普通の他の関数などの変数として評価されます。
(2008-09-21 マクロに挑戦！ コメント欄)

[疑問5]
マクロ引数xが展開時にコンテキストに関わらず展開されないのであれば、
‘(x ,(x 1))
の最初のxはxというシンボルがそのまま残り、
,(x 1)
は展開時に『xという関数に1を付けて呼び出したもの』の値に置換されると思います。
つまり、
(x 未定義値)
というリストが出来上がるのではないかと。
これがfujita-yさんが仰るように
(quote (func ,(func 1)))
に変形されるのであれば、これは展開時にxが展開されるということではないのでしょうか？

うかべんに向けて色々模索中。
私をうかべんに誘って頂いたさとーさんに
「里々がLispに近いシンタックスを持つ」
というアドバイスを頂いたので、
Lispと里々の類似点、相違点について話そうかと考えたのですが、
私がだらだらと30分も話してもただ眠くなるだけなので、
何か一つものを作って持っていくことにしました。
里々は

＊終了
：えんいー
：なんか懐かしいなそれ

の様な、いかにも文字列の出力が主体のスクリプト言語らしい文法を持っていて、
これだけを見たらLispとは似ても似つかないのですが、
その一方で、変数の代入や条件分岐のシンタックスを見ると、

（set,[変数名],[値]）
（if,[条件式],[真の場合に返す文字列],[偽の場合に返す文字列]）

とのように、これはまあLispそっくりになっています。
そこで思いついたのが、
—
1. リーダマクロを書き、里々のスクリプトをS式として読めるようにする
(ちょっとしたパースをするだけだからきっと簡単なはず)
2. 読み込んだS式をCLのプログラムに展開するマクロを書く
(きっと、ちょっとしたマクロで書けると思う。根拠はないけど。)
3. ここまで出来たら、里々のスクリプトをCLのプログラムとしてコンパイルできるぞ！
(そしたら、バイトコード or ネイティブコード or Cのソースコードになる。)
4.きっと楽に書いた割には高速に動作するに違いない！
(特にCのソースコードを吐き出せたらちょと手を加えてDLLにしてSHIORIにできるはず)
—
という妄想をしてみました。
で、コードを書いてみたところ、それらしく見えるものができました。

＃dic01.txt
＊終了
：えんいー
：なんか懐かしいなそれ

このプログラムをリードすると、次のように変換されます。

(DEFTALK 終了 :TRUE
(話し手交代)
"えんいー"
(話し手交代)
"なんか懐かしいなそれ")

本当はこれを伺かと通信できる様にdeftalkマクロ展開する必要があるのですが、
今は面倒なので標準出力に文字を出すように展開。

(PUSH
(LAMBDA ()
(FORMAT T "~&~A:~A" "さくら" "えんいー")
(FORMAT T "~&~A:~A" "うにゅう" "なんか懐かしいなそれ"))
(GETHASH '終了 *TALK-TABLE*))

実際に、里々のスクリプトを書いたファイルをコンパイルして、
実行する流れはこんな感じです。

MATSURI> (matsuri-compile-file "dic01.txt")
;; Compiling file /usr/home/zick/dic01.txt ...
;; Wrote file /usr/home/zick/dic01.fas
0 errors, 0 warnings
#P"/usr/home/zick/dic01.fas" ;
NIL ;
NIL
MATSURI> (load "dic01.fas")
;; Loading file dic01.fas ...
;; Loaded file dic01.fas
T
MATSURI> (call-talk '終了)
さくら:えんいー
うにゅう:なんか懐かしいなそれ
NIL

なかなかいい感じに動いています。
しかし、今になってLispと一見似ている括弧を使ったシンタックスが厄介だと気づきました。
括弧の内側から評価されるというのはLispと同じですが、
内側を評価して得られた値を使って外側の括弧をリードし直す
という恐ろしい仕様が里々では使われているそうです。

（（今の季節）の味覚）

この式を評価するとき、
まず、内側の （今の季節） が評価され 秋 になりますが、
その次には (秋の味覚） が評価されることになります。
(詳しくはこちらを参照してください)
これは思った以上に手強そうです..

突然ですが、11/3の「伺的ソフトウェア勉強会 大阪#4」で講演をすることになりました。
一人で30分も話すのは初めて。うまくいくのかどうか…
とりあえず、空気読まずにLispの話をしてきます。

なにやらShibuya.lispというものが発足したらしいです。
一体どんなものなのかというと、

Shibuya.lisp は東京地区、特に渋谷周辺半径2万キロの Lisp 系プログラマによる非営利団体です。
各個人のプログラミングスキルの向上を目的に、勉強会ならびにカンファレンスの開催やインターネット上での啓蒙活動や情報交換などを行うコミュニティを目指しています。
Shibuya.lisp は Lisp系言語 を利用し、スキル向上を望む方であればどなたでも無料で参加できます。
※Lisp 系言語とは、Common Lisp, Scheme, Emacs Lisp, Arc, Clojure などを指します。
(Shibuya.lisp About)

だそうです。
半径2万Km以内には入ってるけど、関東は遠い…

http://code.google.com/p/t216-lisp/にT216 release-1を公開しました。
ダウンロードのzipにすべてが収まっています。ちなみに開発環境はWinXPとBCCです。
(T216 release-1)

ソースが公開されたので、とりあえず簡単に目を通してみました。
気になったところを何点か。
* 関数の評価規則
関数の名前は大域環境からしか探していないようですね。
funcallやapplyのような関数も提供していないようなので、
これでは高階関数が作れなくて不便かも。
* 構造体のパディング

struct cell {
char id;
struct cell *car, *cdr;
};
struct atom {
char id;
char *name, ftype;
struct cell *val;
};
struct num {
char id;
struct num *num;
double val;
};

char型の変数が1～2個入って構造体の大きさが中途半端な大きさになっていますが、
これでは結構無駄な領域が生まれてしまうことになります。
例えば構造体cellは一見9bytesしか必要なさそうですが、実際には12bytes使っている可能性があります。
(詳しくは「構造体 パディング」とか「構造体 アライメント」などでググってください。)
気にしないのあれば、それで問題ありませんが、気にしてみるのも結構楽しいです。
例えば、上記構造体からchar型の変数を取り除くとそれぞれのサイズは、
8bytes, 8bytes, 12bytesとなり、すべて4の倍数となります。
これらの配列の開始地点のアドレスが4の倍数であると仮定すると、
ポインタの持つ値の下位2bitは必ず0になると分かるため、
この箇所に別の情報を持たせることが可能となります。
そうすると、cell, atom, numはそれぞれ4bit, 4bit, 2bitの領域を確保できます。
この領域にうまくデータを詰め込めたら、使用容量を大幅に抑えることが出来ます。
(ただし、その分速度は落ちますがw)
* コンスセルに持たせる情報
上記の構造体の定義から分かるように、
それぞれのオブジェクト自身がその種類を表す情報(id)を持っているようですが、
コンスセルに「参照先の」オブジェクトの種類を持たすという手もあります。
その方がメモリ参照回数が減るなど色々と都合がよくなりますが、
今から修正するのは少々面倒かもしれません。

回答 (Lispのひび)
早速回答をもらえました。
ありがとうございます。

> でも、Cで書くなら、再帰呼び出しに頼らず、自分でスタックを持った方がいいかもしれません。
これはどういう意味なのでしょうか。うーん、ちょっと分かりません。

私のcygwin上での動作ですが

$ cat test.c
#include <stdio.h>
#include <stdlib.h>
void muda_rec(int n)
{
if (n > 0) {
muda_rec(n - 1);
}
}
int main(int argc, char **argv)
{
if (argc != 2) {
printf("Usage: %s number\n", argv[0]);
return 1;
}
muda_rec(atoi(argv[1]));
printf("hello world\n");
return 0;
}
$ gcc test.c
$ ./a 100000
hello world
$ ./a 1000000
$

再帰呼び出しをやりすぎると動作がおかしくなるのがわかります。
(本来表示されるはずの”hello world”が表示されずにプログラムが終了してます)
mallocなどで大きな配列を確保し、それをスタックとして利用すれば再帰呼び出しを使わずに
ループとしてプログラムを書けるのでこの問題を回避できます。
(もっとも、上のプログラムの場合はスタックを使う必要もありませんが…)
もちろん、配列を使い切るという可能性もありますが、配列のサイズは自分で分かっているため、
使い切った場合はエラーメッセージを出したり、reallocで領域を追加で確保できます。

neg、+-*/関数の実装を終えた。引数列から数値のみ取り出す関数などに分離したら簡潔に書けた。
関数宣言の部分をそのまま引用します。どんな関数が実装されているか分かると思うので。

add_func("quit",	quit,		type_subr);
add_func("car",		func_car,	type_subr);
add_func("cdr",		func_cdr,	type_subr);
add_func("cons",	func_cons,	type_subr);
add_func("eq",		func_eq,	type_subr);
add_func("?atom",	func_isatom,	type_subr);
add_func("==",		func_iseq,	type_subr);
add_func("=",		func_set,	type_fsubr);
add_func("define",	func_define,	type_fsubr);
add_func("neg",		func_neg,	type_subr);
add_func("+",		func_add,	type_subr);
add_func("-",		func_sub,	type_subr);
add_func("*",		func_mul,	type_subr);
add_func("/",		func_div,	type_subr);

(T216の関数)

type_subrとtype_fsubrのあたりに感動しました。結婚してください(笑)
それにしても関数の名前がなんだか独特ですね。
?atom という名前は少し変な気がします。?をつけるなら普通は atom? でしょう。
(ただ、そうするのであれば、 eq も eq? にすべきでしょう。)

関数導入は(define A (B) C)ならアトムAに関数ポインタとして(lambda (B) C)を代入します。タイプはexpr（引数評価型）です。
==関数は内部までしっかり等しいかをチェックします。eqのようにアドレスが同じだけで判断しません。
(T216関数追加)

上の説明を読む限り、defineは関数定義専用なんでしょうか。
それなら普通はdefunという名前を使います(上の引数の使い方もdefunと一致しますし)。
変数と関数の名前空間が同一であれば、Schemeのdefineと同様に、
関数と変数両方の定義に使えると面白いかと思います。
それから、==に関しては、
(== ‘(a b c) ‘(a b c)) => t
ということなんでしょうか。
それならequalという名前を使うのが一般的かと思います。

(eq 'a 'a) => t
(eq 1 1) => 未定義
(eql 1 1) => t
(eql '(a b c) '(a b c)) => 未定義
(equal '(a b c) '(a b c)) => t

といったように、名前が長くなるにつれてチェックが細かくなります。
とにかく、ひとまず完成したようで何よりです。
これからも頑張って下さい。応援してます。

昨日言っていたスペシャル関数を実際に作ってみました。

(defmacro desun (name args &body body)
(let ((a (gensym)))
`(progn
(defparameter ,name #'(lambda ,args ,@body))
(defun ,name (&rest ,a) (apply ,name ,a)))))
(defmacro slet (l-list &body body)
`(let ,(mapcar #'(lambda (x) `(,(car x) #'(lambda ,(cadr x) ,@(cddr x)))) l-list)
,@body))

まずは、スペシャル関数を作る、desun(define special function)と、
fletのスペシャル関数版であるsletを作ります。

(desun =hoge= (n)
(when (> n 0)
(print n)
(=hoge= (1- n))))
(defun foo (n)
(=hoge= n))

スペシャル関数=hoge=と、普通の関数fooを作ります。
関数と変数の両方の名前空間を使うのは少々かっこ悪いですが、どうかお許し下さい。

CL-USER> (foo 3)
3
2
1
NIL
CL-USER > (flet ((=hoge= (x) x)) (foo 3))
3
2
1
NIL
CL-USER > (slet ((=hoge= (x) x)) (foo 3))
3

こりゃダイナミックだ！