以前、g000001さんに教えていただいた、
『LISPマシン・プログラミング技法』
という本を京大の図書館で借りてきました。
(学外の学生でも普通に借りれました。すごく親切。)
まだ途中までしか読んでいませんが、なかなか面白いです。
「クリック」に対する説明が書いてあるのが時代を感じます。
それにしても、最後に借りられていたのが92年のようなので、
実に17年ぶりの貸し出しのようです。
なんてもったいない・・・
Common Lispにはdisplaced arrayと呼ばれるものがあります。
これは他の配列へのポインタのようなもので、CLHSでは以下のように定義されています。
displaced array n. an array which has no storage of its own, but which is instead indirected to the storage of another array, called its target, at a specified offset, in such a way that any attempt to access the displaced array implicitly references the target array.
(CLHS: Glossary-Section D)
試しに使ってみるとこんな感じです。
CL-USER> (defvar *a1* (make-array 5 :initial-contents '(a b c d e))) *A1* ; まずは普通の配列を作ります CL-USER> *a1* #(A B C D E) CL-USER> (defvar *a2* (make-array 3 :displaced-to *a1* :displaced-index-offset 1)) *A2* ; 続いて、*a1*をターゲットにしたdisplaced arrayを作ります CL-USER> *a2* #(B C D) ; *a2*の中身は*a1*の部分配列と同じです CL-USER> (setf (aref *a2* 1) 2009) 2009 ; *a*2の要素を一つ変更してみます CL-USER> *a2* #(B 2009 D) ; 確かに変更されました CL-USER> *a1* #(A B 2009 D E) ; *a1*の方にも影響がでます
これはなかなか面白いですね。
使用する領域も少なそうだし、部分配列を沢山作るような場面では、
displaced arrayを使うと大幅に使用領域を減らせるんじゃないかと思い、試してみました。
(defun s1 (str &optional (n 1)) (let (acc) (dotimes (i (- (length str) (1- n)) (nreverse acc)) (push (subseq str i (+ n i)) acc)))) (defun s2 (str &optional (n 1)) (let (acc) (dotimes (i (- (length str) (1- n)) (nreverse acc)) (push (make-array n :displaced-to str :displaced-index-offset i :element-type (array-element-type str)) acc))))
という訳で、意味はありませんが、とにかく部分配列を沢山作る関数を二つ用意しました。
引数は作成する配列の一つあたりのサイズです。
s1はsubseqを使い、配列のコピーを作るのに対して、
s2はdisplaced arrayを作るようにしています。
で、CLISPで両者を動かしてみました。
CL-USER> (time (progn (s1 *long-long-text* 1) nil)) Real time: 0.0200288 sec. Run time: 0.0200288 sec. Space: 112420 Bytes NIL CL-USER> (time (progn (s2 *long-long-text* 1) nil)) Real time: 0.0100144 sec. Run time: 0.0100144 sec. Space: 179872 Bytes NIL CL-USER> (length *long-long-text*) 5621 CL-USER> (time (progn (s1 *long-long-text* 100) nil)) Real time: 0.0 sec. Run time: 0.0 sec. Space: 640552 Bytes NIL CL-USER> (time (progn (s2 *long-long-text* 100) nil)) Real time: 0.0 sec. Run time: 0.0 sec. Space: 176704 Bytes NIL CL-USER> (time (progn (s1 *long-long-text* 1000) nil)) Real time: 0.0901296 sec. Run time: 0.0901296 sec. Space: 4695952 Bytes GC: 4, GC time: 0.0600864 sec. NIL CL-USER> (time (progn (s2 *long-long-text* 1000) nil)) Real time: 0.0 sec. Run time: 0.0 sec. Space: 147904 Bytes NIL
サイズ1の配列を作る場合はsubseqの方が使用領域が少ないですが、
サイズが大きな配列を作る場合はdisplaced arrayの方が圧倒的に少なくなりました。
Common Lispは(純粋)関数型言語のように副作用をあまり使わないプログラムが書ける一方で、
領域を共有するようなメモリを節約するプログラムも書けるのがいいですね。
あけましておめでとうございます。今日から2009年ですね。
ところで、今から10年前の1999年はポケステが発売した年です。
という訳で、ポケステ発売から10年(*1)を記念して、
プログラムの書初めとして、ポケステ用Lispインタプリタを作りました。
(*1) ちなみに、生産は2002年で終了しています。
電池がすぐに切れることで有名になったハードだからそんなもんですかね(笑)
私も2回ほど電池交換をした後に面倒になり、ただのメモリーカードとして使いました。
メモリーカードとしてはいまだに現役ですが、ゲーム機としては使っていません(笑)
残念ながら書き込み装置がないので実機ではなくエミュレータです。
実機で動くかは残念ながら不明です。
画面は小さいですが、256文字までの式を入力可能です。
RAMが非常に小さいため、使用できるセルの数は少ないですが、
GCをちゃんと付けたので、ちょっとした再帰なら耐えれます。
この画像からは分かりにくいですが、リストを反転させる関数を定義して呼び出しています。
末尾再帰的に書いていますが、残念ながら末尾再帰の最適化までは付いていません。
そんなこんなで今年最初のLispインタプリタでした。
ポケステ向けプログラミングというのは10程年前には結構流行っていたらしいですよ。
残念ながら当時小学生だった私はまだプログラミングはしていませんでした。
ポケステは32bitのARMを搭載しており、GCCでプログラムを作ることが出来ます。
1999年当時資料を載せていたWebサイトの多くは閉鎖してしまったようですが、
今も簡単な資料や自作プログラムのソースを公開しているサイトが残っているため、
そちらを参考になんとかLispインタプリタを作り上げることが出来ました。
でも、実はこれ去年中につくるつもりだったんですよね…
30日にインタプリタの核の部分が出来上がり、31日の午前中にはGCが完成しました。
で、ここからARM用のGCCを使ってエミュレータでテストを始めたんですが、
どうしてもインタプリタ一部の処理が上手く動きませんでした。
半日かけて原因を探したんですが、結局分からず今年に持ち込んでしまいました。
で、原因はというと、(恐らく)GCCかエミュレータのどちらかのバグでした。
符号無し整数と符号無し整数の剰余を求めたのに何故か元より大きな数になることがあり、
除算と剰余の代わりにシフトとアンドを使ったところ上手いきました。
無事動作して安心すると同時になんだか悲しい気分を味わえました。
最近のCコンパイラは末尾再帰の最適化を行ってくれるそうです。
しかし、Cにはポインタがある以上、上手く最適化できない場合もあるよなー
みたいなことを一年ほど前に思いついたんですが、試すのが面倒で放置してました。
それが、今さらになって気になってきたので試してみることにしました。
コンパイラには『gcc (GCC) 4.2.1 20070719 [FreeBSD]』を使用。
まずは、最適化されそうな関数。
int f(int n, int acc) {
if (n <= 0) {
return acc;
}
return f(n-1, acc+nanika(n));
}
これを『gcc -c -S -O2』でコンパイルしたところ、以下のようになりました。
f: pushl %ebp movl %esp, %ebp pushl %esi pushl %ebx subl $16, %esp movl 8(%ebp), %ebx movl 12(%ebp), %esi testl %ebx, %ebx jle .L8 .p2align 4,,7 .L11: movl %ebx, (%esp) call nanika addl %eax, %esi subl $1, %ebx jne .L11 .L8: addl $16, %esp movl %esi, %eax popl %ebx popl %esi popl %ebp ret
再帰がジャンプになってます。さすがGCC。
で、次は去年思いついてた最適化されなさそうなコード。
int g(int x, int *p, int count)
{
x = 0;
x = *p + 1;
if (count <= 0) {
return x;
}
return g(x, &x, count -1);
}
もし、これがループに置き換われば、一つ前のxがx=0により消されてしまうため、
その後で*pで参照するときにおかしなことになってしまいます。
上と同様のオプションでコンパイルしたところ、以下のようになりました。
g: pushl %ebp movl %esp, %ebp subl $12, %esp movl 12(%ebp), %eax movl 16(%ebp), %ecx movl $0, 8(%ebp) movl (%eax), %edx addl $1, %edx testl %ecx, %ecx jle .L2 leal -1(%ecx), %eax movl %eax, 8(%esp) leal 8(%ebp), %eax movl %edx, 8(%ebp) movl %edx, (%esp) movl %eax, 4(%esp) call g movl %eax, %edx .L2: leave movl %edx, %eax ret
想像通り、最適化は行われずにcallになっていました。
Cにはポインタがある以上、末尾再帰の最適化は完全には行えないよなー、
という夢のないお話でした。
SLIMEで日本語を扱う方法をnathkiに教えてもらったので、忘れないうちにメモ。
文字コードを.emacsで指定すればいいらしいです。
;;; .emacs (set-language-environment "UTF-8") ;;; (中略) (setq slime-net-coding-system 'utf-8-unix) (require 'slime) (slime-setup)
こうしたら日本語がちゃんと扱えるようになりましたとさ。
めでたしめでたし。
// "hello-world.c"
// (defvar /* nil)
/*
(set-macro-character #\*
#'(lambda (stream char)
(declare (ignore char))
(read-char stream)
(with-open-file (fs "koreha-hidoi.c"
:direction :output
:if-exists :error)
(do ((line (read-line stream nil :eof)
(read-line stream nil :eof)))
((eq line :eof))
(write-line line fs)))
#+clisp(ext:run-shell-command "gcc koreha-hidoi.c -o koreha-hidoi" :output nil)
#+clisp(ext:run-shell-command "koreha-hidoi")
))
(values)
*/
#include <stdio.h>
int main()
{
printf("hello, world\n");
return 0;
}
$ gcc hello-world.c -o hello-world $ ./hello-world hello, world $,. -───-: ､
／::::::::::::::::::::::::::::::::＼
/ ”:::::::::::::::::::::::::::::::””’ ヽ
!::::::::::ｨ::ハ:::;::::::::::::::::::::::::::!
i::|:::i::/l/ i;::ﾄ､:､:::i:::::::::::::::i でも、これで終わらんと、
|::i/ﾚ’-i” ‘ヽi-ヾ,ヽ!:::::::::::::l
|::ﾊ -‐- -─- i::::::::::::::l CLの処理系でもちゃんと動かして欲しいんや
|::::::l| | | | |::::::::::::::!
|::::::ヽ | r—､! l,.!::::::::::::::l
l::::::::::::`;’-‘=,‐,=’r”i~!:::::::::::::::|
!:::::::l､::r'”´’. ‘ l ’ i::::::::iヽ:::l
i:l､:::|./､_＿＿＿_,l::::;l:/‐’ヽ!
‘!ヽ;i’>l_＿＿＿,./／-‐”'”ヽ
!/ |.VVVVVVVV.lV＼!. i
| | | l$ clisp -norc -q hello-world.c hello, world $わ ,..-―-､ 動いたでー
| /:::::::::::::::::l
∩ /::::::::::::::::::::| ,､
-―-､ |⌒ヽ/::::::::::::::::::::::| _／|ノ
/´Ｙ （´ヽ ,､ l: : : ｉ::::::::::::::::::::::::|-―’´: :丿
,､ _し’ l lヽJ／|ノ ＼: |∧／l／|ノﾚ : : : :／
Ｙ: : ｀ｰ｀ｰ-―’´一’: : | /: : : : : : : : : : ::i-‐’′
＼: : : : : : : : : : : : ／ /: : : : : : : : : : : |
Ｙ: : : : : : : : :r’´ /: : : : : : : : : : : :|
/: : : : : : : : : :| /: : : : : : : : : : : : |
/:: : : : : : : : : ::| / : : : : : : : : : : : : |
/: : : : : : : : : : : | /: ::＿: : : : : : : : : :|
｀７７ｰ–┬r一’ ￣/ /￣｀ｰ-┬r-‘
l’´） ├| l’´） |~|
し’ (ﾆ⊃ し’ (ﾆ⊃,､-‐””” ｀｀｀｀”””::::｀`丶､
.,､ ‘´ ｀ ､::::::`:,､
,､’_ ゝ､‐’`､
/ ” ”” ‐‐ ‐ ‐‐,､‐‐__”,,”,,’,,,”_´_ ‘､
,’‐ ,‐ -,‐ ””.ｨ'”／ l’､ ヽ.. ＼ ｀｀｀::::.､’,
! { :/l ..::/i’../ |＼:..’､::. ＼ :::::::::i
.i ! .::〔_!:::;’ i’:/. ’､ ＼ヽ＼ヽﾍ | ::::::::|
.| .l ::/ !,ヘ,l/_ ヽ _,,>;＜,;ヽ＼| :::::::| ソースの中に “gcc” って
! |::/ ,r”r’´´ヾ ””ｒ'”｀ヾ`､ i ::::::::| 書いてあるのを
| ;/i, ii’ {､ { {､ .{ }i:| ::::::::l 気にしたらあかんからな
i ‘. {‘i!, ‘､ ソ0} ;丶 ﾉ0} ﾉ!:| :::::::|
l i ,,,,ゞ,､､’,;;;;;;;;;;;;::::;,,,,ゞ -､’､.:| ::::::::i
i l ”””´´´｀゛゛゛´´ ..::| ::::::::|
l ’. ` .::､_| :::::::::!
}. `.､ ､–‐,丶 .:::;､’::i’ ::::::::::!
| ::::`..､ `”'” ,､‐”l:::::i ..::::::::::!
.| ::::::::::::`:‐.､,,,,,,,,､ – ”´:::::::::l:::i : :::::::::::::!
! :. ::::::::::::::::::::::::i::::::::::::::::::::;::::::ヽi ::;.::::::::::::::!
l :::. :::::::::::::::::::::::::l ::::::::::: ‘”,’:::::::::i’ .:::::::::::::::::::l
i ::::. :::::::::;､:::::::::,､’! ,:’::::::::,､i .:::::::::::::::::::::}
! ::::::. ::::::::ヽ／|,,､i ,;;;;;;;;;;;;;;／ｲ .::::::ﾉﾉ＼::::::}
’､ ､::::. :::::,イ i’i’ `”´ .//´i .::::::y”ｿ⌒｀`ヾ.
ヽヾ､.. :::i i’ i’_‐_-_-_-_- .// i ..::::／ :::::’,
ヽ､ヽ:::〈 i’i’r;; i’i’ ｀｀” ﾉイ’/ ::::::’,
` /ヽヽ i’i’ `’ i’i’ ;､ // ::::::}
逆引きCommon Lisp経由でCLikiのTail Recursionの説明を見て知ったんですが、
Common Lispも処理系によっては末尾呼び出しの最適化を行ってくれるんですね。
で、試しにこんなコードをコンパイルしてみました。
(defun tcall1 () (declare (optimize (space 0) (speed 0) (safety 0))) (print "test") (nanika)) (defun tcall2 () (declare (optimize (space 3) (speed 3) (safety 0))) (print "test") (nanika))
CLISPでは残念ながら最適化されませんでしたが、
SBCLを使ってみたところ、見事に最適化されました。
(出力されているコードは重要な箇所だけ切り抜いています)
* (disassemble 'tcall1) ; EF2: 8B05881EB061 MOV EAX, [#x61B01E88] ; #<NANIKA> ; EF8: 31C9 XOR ECX, ECX ; EFA: 896AFC MOV [EDX-4], EBP ; EFD: 8BEA MOV EBP, EDX ; EFF: FF5005 CALL DWORD PTR [EAX+5] * (disassemble 'tcall2) ; 64: L0: 8B0518476361 MOV EAX, [#x61634718] ; #<NANIKA> ; 6A: 31C9 XOR ECX, ECX ; 6C: FF75F8 PUSH DWORD PTR [EBP-8] ; 6F: FF6005 JMP DWORD PTR [EAX+5]
こいつはびっくりだ。
以前から、WindowsでCLのプログラムを書く際に、
Meadowの上でSLIMEを動かしたかったんですが、
.emacsにSLIMEの設定を書いただけではエラーが出て困っていました。
が、Windowsの上でCLのプログラムを書く機会がなかったので放置してました。
で、今度大学の後輩にCLを教えることになったんですが、
皆Windowsを使っているので非常に困ったことになりました。
Lispboxを使ってもいいけど、これは日本語が使えないらしい。
で、MeadowでSLIMEを動かす方法をnathkiに調べてもらったらんですが、
解決法は意外と簡単でした。
Cygwinを起動して、以下のコマンドを入力するだけ。
$ cd / $ mkdir c $ touch /c/NOT_MOUNTED $ mount c:\\ /c
なんでこれで上手くいくのか良く分からないけど上手くいきました。
Cygwinのmountってどういう仕組みなんだろ…
odzさんのコメントを受け、さらに改造。
#include <stdlib.h>
#include <time.h>
#define N 10000000
static int xs[N], ys[N];
int main()
{
int i, sum = 0;
srand(time(NULL));
for (i=0; i<N; i++) {
xs[i]= rand()%3+3;
ys[i] = rand()%3+1;
}
for (i=0; i<N; i++) {
#ifdef OPERATOR
int q, r;
q = xs[i] / ys[i];
r = xs[i] % ys[i];
sum += q;
sum += r;
#endif
#ifdef DIV
div_t d;
d = div(xs[i], ys[i]);
sum += d.quot;
sum += d.rem;
#endif
}
return 0;
}
そして計測
$ gcc test.c # 計算を行わない $ time ./a real 0m0.789s user 0m0.751s sys 0m0.040s $ gcc -DDIV test.c # div関数を使用 $ time ./a real 0m0.983s user 0m0.941s (差分: 0.190s) sys 0m0.040s $ gcc -DOPERATOR test.c # 演算子を使用 $ time ./a real 0m0.933s user 0m0.911s (差分: 0.160s) sys 0m0.030s
divの方が遅い。けど、あんまり差が出てない気もします。
「-O0」オプションをつけても結果はそれほど変わらなかったけど、
「-O5」オプションを付けてみたら両者の差は大きくなりました。
(2011/07/13 追記)
このエントリへのスパムコメントがやたらと多いので、コメント欄を閉じます。
なにかコメントがある方は別のエントリにコメントを付けて下さい。
EusLispのmathtran.lにも中置記法をlispで書くためのコードがあると聞きました。
しかし、こちらは私のものと違い、配列なども扱えるそうです。
という訳で、対抗してみました。
色々拡張できるように書いたので、マクロの定義は一切変えずに済みました。
(def-op-parser test-parser (input stack acc)
()
(((#\+ 2 :left)
(let ((x (pop acc)) (y (pop acc)))
(push `(+ ,y ,x) acc)))
((#\- 2 :left)
(let ((x (pop acc)) (y (pop acc)))
(push `(- ,y ,x) acc)))
((#\= 1 :right)
(let ((x (pop acc)) (y (pop acc)))
(push `(setf ,y ,x) acc)))
((#\* 3 :left)
(let ((x (pop acc)) (y (pop acc)))
(push `(* ,y ,x) acc))))
((( #\( #\) ) )
(( #\[ #\] )
(let ((x (pop acc)) (y (pop acc)))
(push `(aref ,y ,x) acc))))
#\})
(set-dispatch-macro-character #\# #\{ #'test-parser)
で、このように準備しておけば上手くいきます。
#{a[2*3] = 5-4} --> (SETF (AREF A (* 2 3)) (- 5 4))
やったね。