Archive for 12月, 2008

マンガで分かるLisp #3

月曜日, 12月 22nd, 2008

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

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

Cの末尾再帰

水曜日, 12月 17th, 2008

最近の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で日本語

土曜日, 12月 13th, 2008

SLIMEで日本語を扱う方法をnathkiに教えてもらったので、忘れないうちにメモ。
文字コードを.emacsで指定すればいいらしいです。

;;; .emacs
(set-language-environment "UTF-8") 
;;; (中略)
(setq slime-net-coding-system 'utf-8-unix)
(require 'slime)
(slime-setup)

こうしたら日本語がちゃんと扱えるようになりましたとさ。
めでたしめでたし。

マンガで分かるLisp #2

木曜日, 12月 11th, 2008

まさかの続編。

どのコマから読めばいいのかもはや分からない

CLでCのプログラムを動かす画期的な方法を思いついた

火曜日, 12月 9th, 2008
               ,. ‐””:::::::::::::;::::`’-、
             /::::::::::::::;;:::::/ ヽ:::::::::ヽ  
       _      /:::::::::::::///  `、::r、:::゙,     Common Lispの処理系を使って
───  .l ヽ    ,’::::::::::::i゙  ○    `’ i::::i       Cで書いたプログラムを動かす
         \ \   !::::::::::::|       ○ l::::|  / 〉 画期的な方法を思いついたでー
───    ゙/ \!::::::::::::!   ,.._      !:::!/\/ 
        ヽ/  \::::::::!   ! ``”7    !::| \/
────   ヽ    |::::::|   l,   /   ノ::i  /
            `、   i:::::l、ヽ.,_ `”””  _,..イ:::::i  /
─────    ゙、  ヽ;i \ヽ,.二l ̄_,l  |:::/ /  
            ゙、     ヽ`、 | /  レ’ /
──────    ゙、 /     `ロ””  i.  /
             /      ||    |/
───────  /         ||    |
// "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;
}
          /::::::::::::::::::::::::
         /:::::::/::/::ヽ::i:::::::
         /::::/::/l:/  |::|_!::i:
        l::::レl/``   ‘´l:! |::|    このソース、前半はCLのプログラムに見えるけど、
        |::::|  ┃  ┃  ゙i:!    後半はCのプログラムに見えるんや。
          |:::j.  ┃  ┃
       |::/
       |〈    __    ∪|    でも、CLの部分は全部コメントアウトされてるし、
       |:::ヽ.  L…__)    |:  何よりも冒頭に “hello-world.c” って書いてあるから、
       |:::::::::゙ヽ、    _,、-‘゙|:  多くの人はCのソースと思ってコンパイルするやろ…
       |:::::::::|i::::i::フ|”´   |::
       |:::::::::||:/ /|    |::
       .!:i::::::|  /__—/|::::
        〉ト、::| /   /   |::::
       r’ | ヾ! / /  ト//
$ 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       
                 ∩  /::::::::::::::::::::|      ,、 
      -―-、        |⌒ヽ/::::::::::::::::::::::|    _/|ノ
   /´Y    (´ヽ  ,、    l: : : i::::::::::::::::::::::::|-―’´: :丿
 ,、 _し’ l     lヽJ/|ノ   \: |∧/l/|ノレ : : : :/   
 Y: : `ー`ー-―’´一’: : |     /: : : : : : : : : : ::i-‐’′   
  \: : : : : : : : : : : : /      /: : : : : : : : : : : |    
   Y: : : : : : : : :r’´      /: : : : : : : : : : : :|
   /: : : : : : : : : :|       /: : : : : : : : : : : : |
  /:: : : : : : : : : ::|      / : : : : : : : : : : : : |
  /: : : : : : : : : : : |      /: ::_: : : : : : : : : :|
  `77ー–┬r一’       ̄/ / ̄`ー-┬r-‘
  l’´)   ├|           l’´)     |~|
  し’    (ニ⊃        し’      (ニ⊃
        ,、-‐””” ````”””::::``丶、
     .,、 ‘´           ` 、::::::`:,、
    ,、’_                ゝ、‐’`、
    /  ” ”” ‐‐ ‐ ‐‐,、‐‐__”,,”,,’,,,”_´_    ‘、
   ,’‐ ,‐ -,‐ ””.ィ'”/ l’、 ヽ.. \   ```::::.、’,
   ! {  :/l ..::/i’../  |\:..’、::. \    :::::::::i
   .i  ! .::〔_!:::;’ i’:/.   ’、 \ヽ\ヽヘ |   ::::::::|
   .| .l ::/ !,ヘ,l/_   ヽ _,,>;<,;ヽ\|    :::::::|     ソースの中に “gcc” って
    ! |::/ ,r”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’     ;、 //       ::::::}

CLで末尾呼び出し

土曜日, 12月 6th, 2008

逆引き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]

こいつはびっくりだ。

MeadowでSLIME

金曜日, 12月 5th, 2008


以前から、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 #1

木曜日, 12月 4th, 2008

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

これは酷い…