リリカル☆Lisp開発日記

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))

やったね。

nishさんのコメントを受け、プログラムを書き直してみました。

#include <stdlib.h>
int main()
{
int i, sum = 0;
for (i=0; i<10000000; i++) {
int x, y;
div_t d;
x = rand()%3+3
y = rand()%3+1
d = div(x, y);
sum += d.quot;
sum += d.rem;
}
return 0;
}

#include <stdlib.h>
int main()
{
int i, sum = 0;
for (i=0; i<10000000; i++) {
int x, y;
int q, r;
x = rand()%3+3
y = rand()%3+1
q = x / y;
r = x % y;
sum += q;
sum += r;
}
return 0;
}

そして、計測結果

$ time ./use_div
real    0m0.967s
user    0m0.951s
sys     0m0.020s
$ time ./use_operator
real    0m0.946s
user    0m0.951s
sys     0m0.010s

ほぼ同じ速度になりました。
けど、普通に演算子を使っても同じ速さだったらやっぱり必要なのかどうか...
(gccが最適化をがんばってるんですかね？
けど、 -O0 をつけても同じ結果でした。)

(2011/07/13 追記)
このエントリへのスパムコメントがやたらと多いので、コメント欄を閉じます。
なにかコメントがある方は別のエントリにコメントを付けて下さい。

C言語のdiv関数というものの存在を今日知りました。
商と余りを一度に求めるそうです。

#include <stdlib.h>
int main()
{
int i, sum = 0;
for (i=0; i<100000000; i++) {
div_t d = div(5, 2); /* 5割る2の商と余りを求める */
sum += d.quot;
sum += d.rem;
}
return 0;
}

同等ものを「/」と「%」を使って書くと次のようになります。

#include <stdlib.h>
int main()
{
int i, sum = 0;
for (i=0; i<100000000; i++) {
int q, r;
q = 5 / 2;
r = 5 % 2;
sum += q;
sum += r;
}
return 0;
}

ついでに計測

$ time ./use_div
real    0m2.327s
user    0m2.313s
sys     0m0.020s
$ time ./use_operator
real    0m0.897s
user    0m0.891s
sys     0m0.000s

div遅すぎ...
予想してましたが、やっぱり遅かった。
いまいちdivの存在意義が分かりません。
ちなみにCommon Lispではtruncateという関数が商と余りを多値で返します。

(defun div-test (n)
(let ((ret 0))
(dotimes (i n ret)
(setf ret (multiple-value-call #'+ ret (truncate 5 2))))))

(2011/07/13 追記)
このエントリへのスパムコメントがやたらと多いので、コメント欄を閉じます。
なにかコメントがある方は別のエントリにコメントを付けて下さい。

ほんとうにしょうもない話ばかりなので小さい文字でいくよー。

*エディタの話*
大学に入ってからviとEmacsの存在を知りました。
周りをみると、Emacs派閥の方が多かったので、
ひねくれものの私はviを使うことに決めました。
その時はCしか書くことがなかったので、問題なかったんですが、
LispやPrologの様な言語を使っていると、どうしても対話環境が欲しくなり、
泣く泣くEmacsを使うことになってしまいました。
両方のエディタを使うようになって改めて思ったんですが、
viって変なエディタですよね。
タイプミスをしてその場で気づいて一文字消そうと思ったら、
ESCキーを押してxキーを押す。そして再び挿入モードに移るためにaキー。
なんと、普通のエディタではBackspace一回で済むことをするために、
3つのキーを押さなければいけないんです^(*1)。
viを使い始めたときはこれに泣かされました。

(*1) 一文字の入力ミスなら気にせずタイプを続け、後でrを使って一文字修正をする方が速かったりします。
あと、vimだとBackspaceが使えるので、これに頼るというのもありかもしれません。

それから、カーソルを移動させて挿入という動作を繰り返す際にも、
Escとi(またはa)キーを毎回押す必要があるため、
どうしてもタイプ数が増えてしまいます。
しかし、viを使ってしばらくしてくるとこういったことが気にならなくなってきました。
viの色んな機能を覚えてきたというのもあります。
でもそれ以上に、
– タイプミスが減った
– プログラムを上から一気に書くようになり、カーソル移動が減った
私の中でこんな変化が起こった(ような気がした)んです。
結果としてプログラムを書く速度が上がったと思います。
ひょっとしたらviはプログラマ養成ギブスの役割を果たすのかもしれません。
でもまあ、Lispのように対話をしながらプログラムを書いていく場合は、
いやでもカーソル移動が増えてしまうので素直にEmacsを使うのがいいかもしれません。
ちなみに、Emacsを使うようになってからは
– 小指が強くなった
これに尽きます。Emacsは小指強化ギブスです間違いありません。
CtrlとCapsLockを入れ替えたところで小指は結局酷使されるんです。
今でも時々左手の小指が痛くなることがあります。
正直どうにかしてほしいです。

あ、ちなみにこの文章はEmacsで書きました。
viで日本語打つのはめんどくさいです。

*大学の課題のプログラムの話*
大学の課題でLL(1)構文解析器を書きました。
LALR構文解析器(の生成系)、演算子順位構文解析器は既に書いたことがあったので、
これで代表的な構文解析の手法3つ全てを制覇したことに成りました。
やったね。
それにしても、LL構文解析の簡単さに思わず笑いそうになってしまいました。
効率よく作ろうとすると何か工夫がありそれなりに大変…と思うのですが、
素直に作るとBNFにあわせた関数呼び出すだけなのであまりにも簡単です。
でも新たに言語を作る場合は、それをLL(1)文法にするのが面倒な気がするんですよね。
大学の課題でパースする対象の言語はPascalライクな独自の言語で、
名前を検索しても出てこないことを考えると先生が作った言語のようです。
先生が「学生でも簡単にパース出来る用にしないとな…」とか思いながら、
LL(1)文法の言語を作っている姿を想像するとなんだか微笑ましく思えてきました。
*手の抜き方*
これまた大学の課題の話。
「前の課題のプログラムどんな風に作った？」
『面倒だったから最低限作れって言われた関数しか作らなかったよ』
「そっちの方が面倒じゃない？」
『だって、関数の入出力一覧をレポートに書けってあったやろ。
最初はdoxygenを使おうかとも思ったんだけど、それも面倒やったから、
作る関数の数を抑えて手を抜くことにした』
…大学の課題の手の抜き方は奥が深いと思いました。
*自転車の話*
昨日、自転車のチェーンが切れました。
半年ほど前にもチェーンが切れたことがあるし、
普通に自転車をこいでる最中に後輪が大破(ギアと連動しなくなった)して、
後輪を丸々取り替えたこともあるし、とにかくよく壊れている気がします。
毎日1時間以上乗っていた高校時代と比べたら全然酷使していないというのに、
なんでこんなにも壊れるのやら…買い換えようかとも考えたんですが、
一緒に琵琶湖一周をした愛機であることを考えるとそれも躊躇われてしまいます。
それにしても、自転車屋って料金が安いところほどサービスが良くて、
料金が高いところに限ってサービスが悪いのは気のせいなんでしょうか…
*そら*
カラスを飼っている家を見つけました。
一瞬、観鈴ちんの家かと思ったけど、
ここは和歌山じゃなくて京都でした。残念。
いつしかのリリカルの続き。

本を読んである程度勉強したので、実際に試してみることにしました。
B4Freeというツールが無料で使えるようなので、試してみることに。
Webサイトがフランス語で面食らいましたが、
右上のイギリス国旗の画像を押すと英語で読めます。
しかし、DownloadページにLinux版はあるもののFreeBSD版が存在しませんでした。
まあ、きっと大丈夫だろと信じてLinux版をダウンロード。
そして、B4Freeインストールの手引きに従い無事インストールを済ますことができました。
Click’n’Proveというツールを入れると、対話的に証明が出来るらしいのですが、
使い方がよく分かりませんでした。なんてこったい。
演算子を入力すると対応する数学記号になって表示されるのは面白かったのですが、
Bのソースを元にCのコードを生成する方法がなさそうだったので、
コマンドライン上で動作するbbatchを使って開発をしてみることに。
資料が見当たらなかったのでヘルプを見ながら直感に頼って試してみました。
なにかおかしなことやってたら誰か教えて。

$ cd ~/B4Free-3.2
$ mkdir switch
$ cd switch
$ mkdir pdb  # プロジェクトのデータを格納
$ mkdir lang  # トランスレートにより生成されるファイルを格納
$ mkdir src
$ cd src
$ vi switch1.mch  # 内容はCommenCのサンプルを参照
$ vi switch1_i.imp  # 内容はCommenCのサンプルを参照
$ cd ~/B4Free-3.2
$ ./bbatch -r=./B4free.rc
Beginning interpretation ...
bbatch>
crp switch switch/pdb switch/lang  # プロジェクトの作成
bbatch>
op switch  # プロジェクトを開く
bbatch>
af switch/src/switch1.mch  # ファイル(Abstract Machine)の追加
bbatch>
af switch/src/switch1_i.imp  # ファイル(Implementation)の追加
bbatch>
t switch1  # 型チェック
bbatch>
pr switch1 0  # 自動証明
bbatch>
t switch1_i # 型チェック
bbatch>
pr switch1_i  # 自動証明
bbatch>
b2c switch1_i  # Cへトランスレート

ちゃんとCのソースが生成されました。やったね。
今度は自分でプログラム(というより仕様)を書いてコード生成をしてみようと思ったのですが、
簡単なものは作れたものの、少し複雑なものを作ろうとすると、
自動証明では証明できないものが生まれてきて、詰まってしまいました。
対話的な証明を行う方法がよくわからないうえに、対話的でない証明をする方法も分からず。
ASSERTIONS節に適切な表明を書けばほとんど自動証明だけで済むらしいのですが、
結局証明できない箇所(しかもそれが何処か分からない)が残ってしまい断念。
それはさておき、今週もCLANNAD ASは凄くよかったです。
美佐枝さんシナリオはやっぱり重要ですよね。
来週はゆきねぇシナリオのようでこちらも期待。
まあ、それも置いといて、いつしかのリリカルの続き。

もっとevalされるべきとは、「もっと評価されるべき」のLISP方言である。
eval関数は、プログラムを評価する関数で、詳細については、Wikipediaのevalの記事を参照。
(もっとevalされるべきとは (モットイーバルサレルベキとは) – ニコニコ大百科)

ねーよｗｗｗｗｗ

KOFに行ってきました。
ニコニコ技術部のMZ-700の実演とか楽しかったです。
KOFの後はK*BUGの打ち上げに参加させていただきました。
他に学生がいなかったためか、学生価格「0円」という驚異的な事態に。
ありがとうございます。本当にありがとうございます。
本当は何かBSDのプロジェクトに貢献することにより恩返しをするべきなのでしょうが、
私にはそんな力量は無いのでK*BUGの宣伝でどうかお許し下さい。
—
K*BUG
– Kansai *BSD Users Group の略
– 日本語名は、「関西 *BSD ユーザ会」
– BSDに限らず、Squeakなど色んな楽しい話が出てくる
– 主に、大阪と京都で研究会が開かれる
– 酒豪が多い
—
こんな集まりです。
興味がある方は是非ご参加下さい。

うかべんの時に作ったCLISP用のプログラムを、SBCLでも動くようにしてみました。
そして、動かそうとしてみたら、

> ; note: *INLINE-EXPANSION-LIMIT* (200) was exceeded, probably trying to
> ;   inline a recursive function.

こんなメッセージが出たまま固まってしまいました。
どうも、マクロ展開で生成される関数が長すぎるのが悪いみたいです。
コンパイルしたら動くんじゃないかと思い、試してみると、
メモリが足りなくなり、ハードディスクがガリガリなり始めました。
今度はもっとスペックの高いマシンの上でコンパイルしてみると、無事コンパイルできました。
(それでも、展開系が長くなりすぎるとコンパイル中にエラーが発生しました。)
で、計測してみました(このときに前のエントリーの通り、スライドの重大な誤りに気づきました)。

[計算]
SBCL    CLISP    里々
215us   1269us   55646us
[括弧]
SBCL         CLISP    里々
47860usec    22760us   13295us

計算速っ！！！！
あまりの速さに驚きました。
コンパイルに異常にリソースを食われたのも納得。
しかし、括弧の処理(主に文字列処理)は案外遅かったです。
汚いコードだったから上手く最適化できなかったんでしょうかね。

どうも、gettimeofdayの精度が悪いようなので、
QueryPerformanceCounterを使うようにして、計測をやり直してみたんですよ。
ブラウザ等を立ち上げたまま計測したためか、前に計測したときよりも、全体的に遅かったんですが、

***
[計算]                   (前回)        (今回)
- オリジナル里々：       3700usec ---> 55646usec (前回の約15倍)
- Lisp（コンパイル済）：  800usec --->  1269usec (前回の約1.5倍)
[括弧]                   (前回)        (今回)
- オリジナル里々：       7600usec  ---> 13295usec (前回の1.7倍)
- Lisp（コンパイル済）：16300usec  ---> 22760usec (前回の1.4倍)
***

…いくらなんでも、里々の計算式の処理があきらかに遅すぎる。
しかし、gettimeofdayに戻して計測しても同じくらいの時間に。
そんな馬鹿なと思い、スライドを作ったときの計測データを見直してみたら、
***
400回: 75.2
200回: 38.2
差分: 37
(単位はms)
***
0が一つ抜けてました。 orz
とんでもないミスをしていました。本当にすみません。
計測データを改めて全て見直してみましたが、間違いはここだけのようです。
一応、スライドを作るときに使った生データを置いておきます。
計測はそれぞれを10回ずつ行い、その平均(行頭が@で始まるもの)の差を取っています。
単位はms(cygwinのgettimeofdayはミリ秒単位でしか時間を取得できないため)、
calcは計算式、kakkoは括弧の計測を表しています。

——————————–
// satori-calc400
78
76
75
76
74
75
77
75
75
75
@75.2
// lisp-calc400
8
8
9
8
8
9
8
9
8
9
@8.4
// lisp(c)-calc400
4
4
4
4
4
4
4
4
4
4
@4
// satori-calc200
38
38
39
38
39
38
38
38
38
38
@38.2
// lisp-calc200
5
5
5
5
5
5
5
5
5
5
@5
// lisp(c)-calc200
4
3
3
4
3
3
3
3
3
3
3
@3.2
—-
// satori-kakko50
18
17
16
17
17
17
17
17
17
16
@16.9
// lisp-kakko50
113
112
112
111
112
115
113
111
112
111
@112.2
// lisp(c)-kakko50
39
37
37
37
37
38
38
38
38
38
@37.7
// satori-kakko50
9
9
8
9
8
9
8
8
8
8
9
@9.3
// lisp-kakko50
51
50
50
51
50
50
51
50
50
51
@50.4
// lisp(c)-kakko50
21
22
22
22
22
21
21
21
21
21
@21.4