リリカル☆Lisp開発日記

突然4コママンガになった。

内容はともかく、かなり教育マンガっぽくなった。

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

兄に「次はマンガで分かるLispだな。」
と、冗談で言ったらこんな画像が送られてきた。

これは酷い…