ASAHIネット(http://www.asahi-net.or.jp)のjouwa/salonからホットコーナー(http://www.asahi-net.or.jp/~ki4s-nkmr/ )に転載したものから。
---
http://iiyu.asablo.jp/blog/2006/04/08/319429
ちょっと気になる本
http://iiyu.asablo.jp/blog/2006/04/20/334280
ちょっと気になる本の続きと、SICPのことも再論
http://iiyu.asablo.jp/blog/2006/04/20/334285
Re: ちょっと気になる本
の続き。

　福岡さんから。
--- ここから ---
中村様へ

福岡と申します。

いつも、刺激的なコラムありがとうございます。
＃あ、知的な刺激という意味です

コラムで書かれている通り、こんな、大事だけど、儲からないかもしれない分
野を出してくれた著者と出版社と、普段楽しませていただいている中村様への
お礼として、ご紹介いただいた、HaskelとOSの本、早速アフィリエイトのリン
ク経由で発注させていただきました。

で、以前から中村様も紹介されていたんですが、今まで、買わずに眺めていた
魔法使い本も、年貢の納め時かと、リンクをクリックしましたが、おかしいで
す。
アマゾンには飛びますが、該当の書籍が表示されません。

ご連絡まで。
--- ここまで ---

　すみませんでした＆通知ありがとうございまいた。すでに直してありますが、
http://www.amazon.co.jp/exec/obidos/ASIN/489471163X/showshotcorne-22/ref=nosim
Harold Abelson, Gerald Jay Sussman, Julie Sussman著、和田英一訳
「計算機プログラムの構造と解釈」
です。

　この前の「Re: ちょっと気になる本」で、Common Lispでtak関数のたらい回
しをやったら、相当に速かったという話を書きましたが、
「Allegro Common Lisp(ACL)とLispworksのCommon Lispでメモ化したtak関数
をやってみたら、(time (tak 100 50 0))だと実行時間は、0でした。メモ化し
ないバージョンでも(time (tak 12 6 0))は、ぼくのマシン(Lenovoじゃないこ
ろのIBM ThinkPad T41、Pentimum 1.6GHz, メモリ512MB)では、トータル190ms
(0.19)でした」
は、ネイティブコンパイルしたものです。
　そこで、ACLのインタープリタとコンパイラでちょっと遊んでみました。
　インタープリタだと遅い。
CL-USER> (time (tarai 12 6 0))
は、数分待ったけど、戻ってこないので止めました。＼(^O^)／
　なお、関数名は、takじゃなくて、taraiのほうに統一しました。
　メモ化したtarai-memoをインタープリタで実行すると、

CL-USER> (time (tarai-memo 12 6 0))
; cpu time (non-gc) 20 msec user, 0 msec system
; cpu time (gc) 30 msec user, 0 msec system
; cpu time (total) 50 msec user, 0 msec system
; real time 330 msec
; space allocation:
; 36,752 cons cells, 436,216 other bytes, 0 static bytes

です。
　tarai-memoは、クロージャとハッシュを使って記憶しますが、ハッシュだけ
でストレートにやる方法でやってみたのがtarai-memo-hash-optです。実はこ
れはコンパイラ用の最適化ヒントがいろいろ埋め込まれているバージョンです
が、これらのヒントは、インタープリタには関係ないと思います。ハッシュキ
ーはリストよりfixnumのほうが速いので、fixnumのキーを使っています。

CL-USER> (time (tarai-memo-hash-opt 12 6 0))
; cpu time (non-gc) 10 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 10 msec user, 0 msec system
; real time 10 msec
; space allocation:
; 53,863 cons cells, 1,395,512 other bytes, 0 static bytes

　次は、tarai, tarai-memo, tarai-memo-hash-optをコンパイルして実行した
ものです。

CL-USER> (time (tarai 12 6 0))
; cpu time (non-gc) 190 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 190 msec user, 0 msec system
; real time 191 msec
; space allocation:
; 3 cons cells, 0 other bytes, 0 static bytes

CL-USER> (time (tarai-memo 12 6 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 1,014 cons cells, 5,200 other bytes, 0 static bytes

は、速すぎて計測不能です。tarai-memo-hash-optも

CL-USER> (time (tarai-memo-hash-opt 12 6 0))
; cpu time (non-gc) 0 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 0 msec user, 0 msec system
; real time 0 msec
; space allocation:
; 3 cons cells, 6,112 other bytes, 0 static bytes

のように速すぎて計測不能です。よって、以降は、メモ化した２つのバージョ
ンのみ、もっとでかいのでやってみました。

CL-USER> (time (tarai-memo 100 50 0))
; cpu time (non-gc) 40 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 40 msec user, 0 msec system
; real time 40 msec
; space allocation:
; 87,342 cons cells, 859,200 other bytes, 0 static bytes

CL-USER> (time (tarai-memo-hash-opt 100 50 0))
; cpu time (non-gc) 10 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 10 msec user, 0 msec system
; real time 10 msec
; space allocation:
; 3 cons cells, 214,832 other bytes, 0 static bytes

　tarai-memo-hash-optをインタープリタで、100 50 0でやってみると、

CL-USER> (time (tarai-memo-hash-opt 100 50 0))
; cpu time (non-gc) 902 msec user, 0 msec system
; cpu time (gc) 2,603 msec user, 10 msec system
; cpu time (total) 3,505 msec user, 10 msec system
; real time 3,595 msec
; space allocation:
; 3,158,558 cons cells, 81,974,248 other bytes, 0 static bytes

なので、ざっと350倍のスピードアップですね。まあ、これは特別な例でしょ
うけど、Lispのコンパイラはかなり優秀なことはわかってもらえるでしょうか。
　Lispは遅いという誤解がいまだに蔓延していますが、いまのマシン環境なら
インタープリタでも決して遅くないし、コンパイルするととっても速いんです
よね。インタープリタで対話的に開発しながら、ある程度まとまったらコンパ
イルしていく、それも関数毎にインクリメンタルコンパイルしたり、ファイル
まとめてバッチ的にコンパイルもできるし、そういう言語です。
　弾さんの
http://blog.livedoor.jp/dankogai/archives/50460894.html
速く動くより早く書くが重要な時代
は、もっともな主張。
　この前も書いたけど、よくあるウェブアプリのようなものは、スクリプト言
語でも十分な時代になってるんです。だって、RDBはネイティブで動いている
わけだし、ブラウザのレンダリングもネイティブだし、スクリプト言語はそれ
らをつなぐグルー(糊付け)言語として、いい道具なんです。
　ただ、元の主張を
http://www.dmtj.net/pm/archives/2006/03/_web.php
素朴な疑問 - なぜスクリプト系 Web アプリ言語がいまだ主流なのか？
を読むと、MVCのVをネイティブコンパイラのある言語で高速化しないとまずい
のではないかといってるのは、一理ありますね。でも、大した量のHTMLを吐く
わけじゃないから、負荷の高いサイト以外は大した問題じゃないとも思うけれ
ど。
　ぼくがLisp、それもCommon Lispを少しずつ勉強しているのは、やはりコン
パイラがあるからで、仕事でやってるバイオの世界は、もういくら速くても処
理できそうにないくらいデータが毎日増え続けています。
　１回全体を処理するには、１ヵ月コンピュータ回しっぱなしになる世界です。
バイオの世界は、Perlを使ったバイオインフォマティクス入門がオライリーか
ら出ていたこともあって、Perlがよく使われているんですが、でも、遅くて対
応できないという現実も明らかになってきています。
　逆にいうと、倍速くなっただけで、１ヵ月かかった処理が２週間でできるよ
うになったといって喜ばれるんです。一桁(10倍)速くなると、３日で処理でき
るようになるわけで、割と簡単に１０倍速くできる技術のひとつがコンパイラ
なんですね。
　いまのスクリプト言語が、いつごろ、どういうコンパイラを手に入れるよう
になるか、常に注目はしています。Lispは遅い遅いといわれたことに反発して、
実行スピードでCと遜色ないくらいの非常に優秀な最適化コンパイラを搭載す
るようになりました。歴史は繰り返すというから、いいコンパイラの出現を期
待して、いまは、スクリプト言語は遅い遅いといい続けようと思ってます。
　一昨日、慶応で講師の懇親会があったんですが、最近、またLispを勉強して
いるといったら、まだ、Lispなんかやってる人がいるんだとかいわれたけど
(爆笑)、いまのぼくには、ますますよさげな言語なんです。Lispハッカーのポ
ール・グレアムもいうように、Lispで書く人があまり増えないほうが競争力が
あっていいんですけどね。^^;
　
　ついでに、tarai-memo-hash-optは、もっと大きなのでやってみました。

CL-USER> (time (tarai-memo-hash-opt 1000 500 0))
; cpu time (non-gc) 121 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 121 msec user, 0 msec system
; real time 130 msec
; space allocation:
; 3 cons cells, 4,005,984 other bytes, 0 static bytes

　こういうスケーラビリティも、最適化コンパイラを使いたい大きな理由です。

　これは、この前、数理システムであったセミナーで配られたACL 8.0デモ版
でやりましたが、いま、オンラインで配られているACL 7.0でも同じだと思い
ます。
　それと、ぼく、最近知った、LispWorksのLispは、なかなかいいなと思って
います。
　Windows, Linux, Mac OS Xで同じGUIが書けるようだし、コンパイラも優秀
です。ネイティブコードではなく仮想マシンコードにコンパイルしてますが、
tarai関数の例ならネイティブコードにコンパイルするACLと遜色ないです。ラ
ンタイムも出来がいいんでしょうね。統合開発環境(IDE)は、ACLより使いやす
い感じがします。
　このIDEをポータブルなGUIライブラリCAPで書いてるんだそうです。ACLも
Common GraphicsというGUIライブラリがあるけど、WindowsとLinuxなんです
(Linuxは実験的実装の段階)。バイオ系は、Mac OS Xがビジネス系より多いの
で、Mac OS Xでも動いてくれないと困るんです。
　いまは、仕事でJavaのAWT/Swingで書いていて、実際書いてみると、ちゃん
とWindows, Linux, Mac OS Xで動くので、ちょっと感動しました。Mac OS Xだ
けは、Option Qなどのハンドラを別に書きましたが、それでも、AWT/Swingは、
一番、成熟しているマルチプラットフォームのGUIライブラリだと感じていま
す。でも、Lispでもこの３つのプラットフォームをサポートできるなら、仕事
では無理かもしれないけど、趣味では書いてみたい気もしてます。

http://jp.franz.com/index.html
Allegro Common Lisp(ACL)のフランツ社
http://www.lispworks.com/
LispWorks社

　tarai-memoは、tarai-memo-hash-optより汎用性のある方法でメモ化してい
ますが、これ、実は、プロや達人Lisperからみるとさして汎用性がありません。
プロや達人Lisperが考えることは、すごいです。
http://www.tfeb.org/lisp/hax.html#MEMOIZE
をみてください。
　局所関数のメモ化も考慮してあるし、頭のいいコンパイラが自己再帰をイン
ライン展開してしまうことまで考えているんです。tarai-memoの手法は、グロ
ーバルな関数名のテーブルを操作して、実体をクロージャ化した関数に置き換
えるので、インライン展開されて名前がなくなると、通用しません。それで、
このライブラリでは、def-memoized-functionマクロを定義して、このマクロ
を使って定義するときは、コンパイラにインライン展開しないように指示する
んです。
　局所関数のメモ化をするmemoized-labelsマクロのソースをみると何をやっ
てるんだと、Common LispというよりSchemeもCommon Lispも素人同然、初心者
のおれは頭痛くなりました。^^;
　このライブラリは今回のtaraiには大げさだと思ったので、tara-memoは、こ
のライブラリを非常に簡略化したものになってます。ソースをみると、
http://www.amazon.co.jp/exec/obidos/ASIN/1558601910/showshotcorne-22/ref=nosim
Peter Norvig著「Paradigms of Artificial Intelligence Programming: Case
Studies in Common Lisp」
を参照しています。なんと、この本、いま、読んでいる最中です。この前や
LispやPrologやAIのこと勉強しなおしているといってたのは、これです(あと
ほかにもあるんですけど)。
　いま、200ページの手前です。memoizeが出てくるのが、260ページくらいな
んですね。ああ、もう少しがんばっていれば、ばっちりだったのに、引きが弱
い！(泣)
　でも、なんか、シンクロニシティを感じました。ともかく、弾さんに感謝で
すね。
　tarai-memoのソースは、
http://www.asahi-net.or.jp/~ki4s-nkmr/tarai/tarai-memo.lisp
に
　tarai-memo-hash-optのソースは、
http://www.asahi-net.or.jp/~ki4s-nkmr/tarai/tarai-memo-hash-opt.lisp
に置きました。