リリカル☆Lisp開発日記

// "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ってどういう仕組みなんだろ…

兄に「次はマンガで分かる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は凄くよかったです。
美佐枝さんシナリオはやっぱり重要ですよね。
来週はゆきねぇシナリオのようでこちらも期待。
まあ、それも置いといて、いつしかのリリカルの続き。