Archive for 2月, 2009

LispをCより速くする

木曜日, 2月 26th, 2009

ときどきの雑記帖経由で知った
How to make Lisp go faster than C
という論文が面白いです。
簡単な画像処理をCとCommon Lispで書いて速度を比べるというものですが、
CLの速度の劇的な変化が笑えます。
インタプリタで実行 -> Cの2300倍遅い
コンパイルして実行 -> Cの60倍遅い
型宣言と最適化を付ける -> Cと同等の速度(一部に関してはCより速い)
いくらなんでも最初より速くなりすぎだろwwww
おまけに、最初のソースと最終的なソースの差はほとんど無く、
関数一つあたり、2,3行増える程度です。これは凄い。
あと、CMUCLの型推論がACLより優秀という話も面白かったです。

(defun mult (to from val)
(declare (type (simple-array fixnum (*))
to from))
(declare (type fixnum val))
(let ((size (array-dimension to 0)))
(dotimes (i size)
(setf (aref to i) (* (aref from i) val)))))

配列fromの要素とvalの積はfixnumの範囲を超える可能性があるため、
ACLでは何も指定しない限り(*1)genericな乗算が行われるけど(*2)
CMUCLでは格納先のtoの要素の型がfixnumであるため、
fixnum用の乗算(つまりCPUのnativeな乗算命令)が行われるそうです。
手元のSBCLで試したところ、確かにIMULになってました。
(*1) 同様の命令を吐かせたければ (the fixnum (* (aref from i) val)) とすればいいそうです。
(*2) 2006年の論文なので現在のACLではどうか分かりません。

CやCLやSchemeの様にしっかりと仕様が定められている言語は、
色んなところが処理系を作って互いに競い合うため、
どんどんいいものが生まれていくのがいいですね。

マンガで分かるLisp #4

火曜日, 2月 24th, 2009

もう何がなんだか分からなくなった。
右上、左上、”真ん中”、右下、左下の順番に読むといいよ。

そもそもmismatch使ったことないし。

λ…

木曜日, 2月 19th, 2009

バッククォート怖い…
Let Over Lambdaで紹介されてる例が怖い…

CL-USER> (let ((let '`(let ((let ',let))
,let)))
`(let ((let ',let)) ,let))
(LET ((LET '`(LET ((LET ',LET))
,LET)))
`(LET ((LET ',LET)) ,LET))
CL-USER> (equal + *)
T

確かに処理を追っていけば式とその値が等しいことが分かるけど、
どうやってこんなものを思いついたんだろう…
とりあえずインスパイヤしてみた。

((lambda (lambda)
`((lambda (lambda) ,lambda)
',lambda))
'`((lambda (lambda) ,lambda)
',lambda))

さらに、次の式を評価し、
『(set-macro-character #\λ #'(lambda (stream c) ‘lambda))』
lambdaの代わりにλを使えるようにするとますます気持ち悪い書き方ができる。

((λ (λ)
`((λ (λ) ,λ)
',λ))
'`((λ (λ) ,λ)
',λ))

意味不明すぎてかっこよく見えてきた。

defmacro!

火曜日, 2月 17th, 2009

土曜になつたんさんとあろはさんとお会いして、飲んできました。
お二人とも楽しい話をありがとうございました。
今、なつたんさんにお借りしたLet Over Lambdaを読んでいるのですが、
噂どおり非常に濃い内容でした。
最初の方に登場するマクロでさえ恐ろしい。
Paul GrahamがOn Lispで書いたマクロnifが

(defmacro nif expr pos zero neg)
(let ((g (gensym))
`(let ((,g ,expr))
(cond ((plusp ,g) ,pos)
((zerop ,g) ,zero)
(t,neg)))))

Let Over LambdaのDoug hoyteの手によって、

(defmacro/g! nif (expr pos zero neg)
`(let ((,g!result ,expor))
(cond ((plusp ,g!result) ,pos)
((zerop ,g!result) ,zero)
(t ,neg))))

物凄い勢いで改造されていく。

(defmacro! nif (o!expr pos zero neg)
`(cond ((plusp ,g!expr) ,pos)
((zero ,g!expr) ,zero)
(t ,neg)))

なんてこった。
ネストがどんどん浅くなっていって、
どんどん訳が分からなくなっていく。
defmacro!はwith-gensymsとonly-onceを隠蔽したようなマクロで、
慣れたらかなり便利そうです。
(with-gensymsとonly-onceについてはそれぞれ”On Lisp“と”実践Common Lisp“を参照してください(笑))
この辺りはWebで無料で読めるので、
defmacro/g!やdefmacro!の定義が気になる方はこちらをどうぞ。

Lispは未来に生きている

火曜日, 2月 10th, 2009

Lispは常に未来を先取りしてきました。
GCがJavaやLL等により一般に浸透するよりも遥か昔からGCを備えていたし、
「クロージャ! クロージャ!」と騒がれる遥か昔よりクロージャを備えてました。
Lispは”現在”ではなく”未来”に生きているんです。
Lispが未来に生きていることは簡単なプログラムを書くことですぐに分かります。
もうすぐ、UNIX timeが「1234567890」になると騒がれていますが、
Lispの中ではそんな時間は既に通り過ぎているのです。

CL-USER> (decode-universal-time 1234567890)
30 ;
31 ;
8 ;
15 ;
2 ;
1939 ;
2 ;
NIL ;
-9

Common Lispの中での時間が「1234567890」を迎えたのは、
日本時間で1939年2月15日8時31分30秒です。
UNIX timeの「1234567890」が日本時間の2009年2月14日8時31分30秒ですから、
約70年も未来を行っているということになります。
ところで、Lispが出来たのって何年だっけ…
ちなみに、Common Lispでのuniversal time「3456789012」を
日本時間で2009年7月17日12時10分12秒に迎えます。
誰か祝ってあげてください。


これを書いてるときに気づいたけど、、Windows版CLISPでのencode-universal-timeの挙動がおかしい。
手元のFreeBSD版では問題なく動くコードが、

[1]> (encode-universal-time 0 0 0 1 1 1970)
2208956400

Windows版では動作しない上にプロセスが死んでしまう。

[1]> (encode-universal-time 0 0 0 1 1 1970)
*** - handle_fault error2 ! address = 0x0 not in [0x19d70000,0x19ef2efc) !
SIGSEGV cannot be cured. Fault address = 0x0.
GC count: 3
Space collected by GC: 0 1311528
Run time: 0 2103024
Real time: 0 197283680
GC time: 0 200288
Permanently allocated: 92384 bytes.
Currently in use: 2626228 bytes.
Free space: 385581 bytes.

CLISPバージョン2.45でこの現象を確認して、その後バージョンを最新の2.47に上げても同様の動作だった。
Windows版CLISPのバグ?

総称関数の先行実行

日曜日, 2月 8th, 2009

並列記号処理という本を読んだんですが、なかなか面白いです。
タイトルからはあまり想像が付きませんが、
高級言語マシンについての話がほとんどで、
Lispマシンなどが好きな人にはお勧めできます。
その中で一箇所印象に残ったものを取り上げます。
Symbolics 3600の後継マシンであるIvoryは、
総称関数の呼び出しの際に、高頻度で使用される命令を先行処理し、
それ以外の命令の実行が必要だった場合は、
割り込みによって処理を切り替えるそうです。
残念ながら、あまり詳しく書いてありませんでしたが、
次のような感じかと思います。

(defmethod m1 ((num number))  ;;m1-1
(1+ num))
(defmethod m1 ((numlis list))  ;;m1-2
(1+ (reduce #'+ numlis)))

上記のような総称関数があり(便宜上、m1-1, m1-2と呼び分けます)、
もし、m1-1(引数の型がnumber)の方が高頻度で呼ばれるならば、
m1が呼ばれた際に、型チェックに先行してm1-1を呼び出し、
後で、引数の型がリストだとわかったら、割り込みを用いて、
途中まで行った処理を無効化し、m1-2に処理を切り替えるという感じでしょうか。
これは、今時のCPUなら必ず付いている分岐予測の一種だとは思いますが、
『総称関数の呼び出し』という大きな単位についてこれが行われるのは
いかにも専用マシンっぽくてかっこいいですよね。

ESP – Prologでオブジェクト指向

月曜日, 2月 2nd, 2009

その昔、ESP(Extended Sequential Prolog)という
Prologにオブジェクト指向を加えたような言語があったそうです。
このESPはFlavorsを参考にして作られており、なかなか面白いです。
ESPについての資料第五世代コンピュータプロジェクト・アーカイブスにおいてあります。
T. Chikayama, “Unique Features of ESP”
ここから分かるように、ESPではクラスの多重継承が可能で、
beforeデモン、afterデモンなんてものがあります。

class with_a_lock has
instance
component lock is lock;
before:open(Obj) :- unlocked(Obj!lock);
...
end.
class door has
instance
component state := closed;
:open(Door) :- Door!state := open;
...
end.
class door_with_a_lock has
nature door, with_a_lock;
end.

クラスwith_a_lockは成分lockを持ち、その初期値値はlock(これはアトム)です。
また、beforeデモン述語openを持ち、これは引数のunlock(ここでは定義されていない)を行います。
クラスdoorは成分stateを持ち、その初期値はclosedです。
また、述語openを持ち、これは引数のlockスロットの値をopenに設定します。
クラスdoor_with_a_lockはdoorとwith_a_lockを継承しています。
ここで次のように、door_with_a_lockのインスタンスを作り、
openを呼ぶと、まずbeforeデモンによりwith_a_lockのopenが呼ばれ、
その後にdoorのopenが呼ばれるという仕組みです。

:new(#door_with_a_lock, DWL),
:open(DWL),

これをCommon LispでCLOSを使って書くと次のような感じでしょうか。

(defclass with_a_lock ()
((lock :accessor with_a_lock-lock
:initform 'lock)))
(defclass door ()
((state :accessor door-state
:initform 'closed)))
(defclass door_with_a_lock (with_a_lock door) ())
(defmethod my-open :before ((obj with_a_lock))
(format t "with_a_lock open~%")
(setf (with_a_lock-lock obj) 'unlock))
(defmethod my-open ((obj door))
(format t "door open~%")
(setf (door-state Obj) 'open))

実行してみると、with_a_lockのopenが呼ばれてからdoorのopenが呼ばれているのが分かります。

CL-USER> (setf *dwl* (make-instance 'door_with_a_lock))
#<DOOR_WITH_A_LOCK #x19FAE3A9>
CL-USER> (my-open *dwl*)
with_a_lock open
door open
OPEN

Flavorsが出来た時期を考えてみたら、
影響を受けた言語が沢山あってもおかしくはないのに、
なかなか見かけないのはなんでだろ…