リリカル☆Lisp開発日記

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 追記)
このエントリへのスパムコメントがやたらと多いので、コメント欄を閉じます。
なにかコメントがある方は別のエントリにコメントを付けて下さい。

本を読んである程度勉強したので、実際に試してみることにしました。
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は凄くよかったです。
美佐枝さんシナリオはやっぱり重要ですよね。
来週はゆきねぇシナリオのようでこちらも期待。
まあ、それも置いといて、いつしかのリリカルの続き。

うかべんの時に作った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

修正した資料。
当日使ったもやつの誤字を修正したものです。
うかべん大阪#4の話。
CLIPS少し気になった。今度調べてみる。
Prologは状態数が爆発するんじゃ…という話があったけどカット(!)があるよ。
あと、『ルールエンジン』より『推論エンジン』の方がカッコイイと思う。
懇親会。食べ放題。学生料金500円。安すぎ。ワロタ。ありがとうございます。
私の講演でLispに興味を持ってくれた人がいた。やったね。
Lisp in Box for Windows。zipじゃなくてインストーラ付きのものがあることを知った。
でもそっちの方が分かりにくかった。

11/3のうかべんの資料が完成しました。
これです。
疲れたんで寝ます。
誤字とかあったらこっそり教えてください。
あ、CLANNADは今週も面白かったです。
次回予告を見たところ、ちゃんと猫の話もやるみたいですね。
相変わらずことみの出番が多い。そして風子でてこない。
いつしかのリリカルの続き。

若干流行に乗り遅れた感じはありますが、
Cyanを触ってみました。
色々気になったけど、時間が無いから一点だけ。
関数の中で関数を作れるのか試してみたんですが、

def(reverse)^(lst):
iter:=^(lst2, acc):
say(lst2)
if (lst2.null?()):
acc
else:
iter(lst2.cdr(), [lst2.car()|acc])
iter(lst, [])
reverse([1,2,3,4,5])
# => [5, 4, 3, 2, 1]
# 出力されるのは
# [1, 2, 3, 4, 5]
# [2, 3, 4, 5]
# [3, 4, 5]
# [4, 5]
# [5]
# []

これは上手く動きますが、
次のコードだと、

def(reverse)^(lst):
iter:=^(lst, acc):
say(lst)
if (lst.null?()):
acc
else:
iter(lst.cdr(), [lst.car()|acc])
iter(lst, [])
reverse([1,2,3,4,5])
# => (無限ループで結果出ず)
# 出力されるのは
# [1, 2, 3, 4, 5]
# [2, 3, 4, 5]
# [2, 3, 4, 5]
# [2, 3, 4, 5]
# [2, 3, 4, 5]
# ...(以下同様)...

何故か無限ループに陥ってしまいます。
iterに代入される関数の参照してる「lst」が外側のlstかとも思ったんですが、
一度だけはCDRが取れてるし、そういう仕様でもなさそう。
試しにこんなコードを動かしてみたんですが、

m=100
def(f1)^():
i:=^(n):
say(n+m)
i(1)
m:=3
i(1)
m:=2
i(1)
f1()
# 出力されるのは
# 101
# 4
# 3

このように動くのを見たところ、関数内部における変数への参照があると、
定義された環境から外の環境に向かって、順番に変数を探すように思えるんですが、
引数の場合だけ何か扱いが違うんですかね。
ローカル変数の取り扱いの説明が、この記事だけだと、分からないところが多いので、
出来れば詳しい説明をお願いします。

とりあえず、OnTranslateメッセージがやってきたときに、
直前に送ったリクエスト再び送るようにしてみました。

SHIORI/3.0 200 OK
Sender: matsuri
Charset: UTF-8
Value: \0\s[0]\1\s[10]\0おはー\1らっきー\e

GET SHIORI/3.0
ID: OnTranslate
Sender: SSP
Charset: UTF-8
SecurityLevel: local
Reference0: \0\s[0]\1\s[10]\0おはダ

SHIORI/3.0 200 OK
Sender: matsuri
Charset: UTF-8
Value: \0\s[0]\1\s[10]\0おはー\1らっきー\e

とりあえず、これくらいの長さの台詞ならちゃんと喋ってくれるようになってくれました。
しかし、長い台詞を表示しようとすると結局途中で切れてしまいます。
それにCROWでは相変わらず何も喋ってくれず。
まー、それは置いといて、CLANNAD AFTER第2話が放送されました。
ほんと良かった。もう毎週木曜がたのしみでなりません。
どうやら有紀寧さんシナリオもちゃんとやりそうだし楽しみ。
ただ相変わらず風子分が足りない。
1話に続いて、本来風子の出るところにことみが出てきてます。
そして、それも置いといて昨日のリリカルの続き

相変わらず、11/3のうかべんに向けてCLでSHIORIを作っています。
けど、最近は現実逃避にゲームばかりやっていたので実は久しぶりというのは内緒です。
以前から、困っているのが、リクエストに対して長い台詞を送ると、
途中で切れたり、内容が壊れていたりするという現象。
しかし、長くない台詞に対しても起こるようになってきました。
リクエストとレスポンスを追いかけてみたところ、

SHIORI/3.0 200 OK
Charset: UTF-8
Sender: matsuri
Value: \0\s[0]\1\s[10]\0えんいー\1なんか懐かしいなそれ\w5\-

リクエストに対して、このようなレスポンスを返した際に、
次のようなリクエストがやってきました。

GET SHIORI/3.0
ID: OnTranslate
Sender: SSP
Charset: UTF-8
SecurityLevel: local
Reference0: \0\s[0]\1\s[10]\0えむ

OnTranslateとはなんぞやと調べてみたら、こちらがValue(台詞)を返すと、
その台詞を表示する前に台詞をReference0に入れて送られるリクエストだそうです。
(ログを取ったり、台詞の語尾の置き換えたりする場合に使うそうです。)
このリクエストに対するレスポンスとしてValueを返さなければ
OnTranslateのReference0が実際に表示される内容となるみたいですが、
上記の通り内容が壊れています。
結果として「えむ」という台詞が表示されてしまいました。
以上がSSPでの動作で、CROWで試してみたところ、
OnTranslateが送られてこない代わりに、なにも喋ってくれません。
こいつは困った…
全然関係ないけど10/11のリリカルの続き