なつたん

https://twitter.com/#!/takeoka/status/154522929076506625から

http://www.archive.org/details/lisploreguidetop00bromから、Lisp Loreのpdfがダウンロード出来ます。

たしかこの本持っているなと思って調べてみたら、ダウンロード出来るのは初版、僕が持っているのは第二版でした。

「プログラミングGauche」を読んで、再びSchemeの魅力に取り憑かれる。PythonもC++も勉強したいし、勉強したいことが多すぎて困る。

SystemCやるならC++だし、変態を自重するならPythonだし、メタプロするならSchemeが良いよね。でも、メタプロなら、C++のテンプレートも最高だよね。って、あれだ。一緒に遊園地行くならゆうゆだけど、奥さんにするならまみまみだよね、くらいのノリなんだと思う。もちろん、僕は両方ゆうゆですが。分からない人は、冒険に行くならビアンカだけど、結婚するならフローラだよね、でもよい。僕は両方フローラですが。

いい加減男らしくばしっと決めたいので、言語占いで決める事にした。

言語占いってのは、雑誌で良くある奴ね。

問１：最先端の技術を使いたい。YES→問2へ　NO→じゃあ、COBOLで
問２：英語は苦手　YES→変数をローマ字で書いてもOKなCOBOLをおすすめ　NO→問3へ
問３：Webアプリを作りたい　YES→そんなナンパな気持ちは捨てて、COBOLを勉強しろ。NO→圧倒的な実績のあるCOBOLをおすすめ

こんな感じで、YES、NOを答えていくだけですぐに、あなたにおすすめの言語を選んでくれる。こりゃ楽だ。
雑誌の弱点として、いまいち僕を対象にしていないというか、不特定多数を対象にしすぎている。なければ作ってしまえば良くて、自分で占いを作る事にした。前からSICPのAMBが仕事で使えないかな～と思っていたので、題材にしてみる。やる夫は五階に住んでいません、ってやつね。

問１：AMBをPythonで書いてみる。納得いく物ができたか？
　　　YES→問2へ
　　　NO→言語レベルで継続をサポートしているGaucheおすすめ。

問２：AMBをC++で書いて見る。納得いく物ができたか？
　　　YES→C++おすすめ
　　　NO→君にはC++は10年早い。Pythonがおすすめ。

ちょっと占ってみよう。

＃　一応書いておくけど、ネタだからね＞＜

渚の『・・・・・』だろ、JK

♪（S式が）きれいね
夕日の絵の具に塗り替えられた 油絵みたいな波打ち際に （PGも油絵って言ってた）
足跡がてんててんててん （← 可変長引数）

なーぎさーのかーぎかっこ
（マクロが）ぱっとひらいたら、アッーと驚いて
なーぎさーのかーぎかっこ
（マクロが）ぱっとひらいたら、顔が近づいた
やってくれました、やってくれました、たったいま （← マクロが今評価された！）

かっこ、かっこ、かっこ、かっことじとじ

例によってHigher-order Perlから

昨日までは、同じ処理を同じアルゴリズムで書いたらC/C++が一番早いに決まっているという信念があったのですが、この本を読んで考えが変わりました。2007年11月3日はそんな記念日。

相変わらずメモ化の話なんですが、

・フィボナッチ書けたよ → 遅くね？
・メモ化したよ → 毎回メモ化の仕組み作るの面倒じゃね？
・closureがあるよ → 引数が一つの時しか使えなくね？
・joinでつなぐよ → f("x,", "y")と、f("x", ",y")でバグるよ
・正規表現でエスケープするよ → 遅くね？
・key generatorを引数で渡して、if文で切り替えたらどうよ → if文無駄じゃね？
・eval使うよ ← 今ここ

という議論を経て、evalを使う話。上の議論は全部Perlのソース付きで説明されています。
で、問題のコードがこれ。

sub memoize {
　my ($func, $keygen) = @_;
　$keygen ||= q{join ',', @_};

　my %cache;
　my $newcode = q{
　　sub { my $key = do { KEYGEN };
　　　　$cache{$key} = $func->(@_) unless exists $cache{$key};
　　　　　return $cache{$key};
　　　　}
　};
　$newcode =~ s/KEYGEN/$keygen/g;
　return eval $newcode;
}
　
引用のレベルだと思うけど、念のため。ソースはここから取得可能、ソースのライセンスはここです。

evalを使う前ののソースが、my $key = $keygen ? $keygen->(_@) : join ',' , @_; と、引数$keygenがあるかないかで、joinを使うか、引数で与えられた$keygen関数を使うかを切り分けていたのが、上のやり方で三項演算子が一つ消えている。つまり、自分で最適化されたソースを作り出し(KEYGEN部分の置換)、evalしてそのまま利用することで条件分岐を減らしているわけだ。これはC言語では難しい。条件分岐をnopでつぶすとか、DLL作り直して再ロードとかできなくはないが、明らかにCの範囲を超えている。これCommon Lispでできたらすごい事になる事に気がついた。

状況としては、良く呼ばれてボトルネックになっている関数があるとする。その関数が、起動時のオプションや実行時の状態によって、ちょっとずつ動きを変える必要があるとする。Cで書くと、どうしても動きを変えるためにif文が必要になる。Common Lispだと動きを変えたS式を作り出し、最適化を書けてコンパイルして使い続けることができる。Lispについてのよくある誤解と、その中にあるちょっとした真実にあるように、もともとCommon Lispのコンパイル能力は高いらしいので、「いろいろ変わる条件」が複雑になればなるほど、Common Lispの方が速い可能性が出てくる。Cでも、考えられる組み合わせにはそれぞれ別の関数を作るってやり方もあるけど「100回以上呼ばれたら、自動的に最適化されたS式を作り出して、再コンパイル」みたいな芸当はCにはできない。

結論：Lispすげー！

メモ化の話としては、内容的にも、ページ数的にも、ここで折り返し
後は、特殊な状況下での考察がソース付きで続く。Higher-Orderはあまり関係ない。

キーワードだけ列挙
・f(A=>32, C=>99)と、A(C=>99, A=>32)を同じに扱うべきかどうか
・デフォルト引数的な動きをする関数をどう扱うか。
・オブジェクトのメソッドをメモ化するときの注意点
・オブジェクト(のアドレス)をキーにしてはいけない理由
・メモ化の結果をDiskに残して、後で再利用する
・時刻を取得する関数をメモ化が有効な時
・sort関数でのメモ化
・Orcish Maneuver
・Semipredicate problem
・"0e0"問題
・100回呼ばれたら自動的にメモ化する

100ページを読んでまだまだ絶賛ベタ褒め中。

Higher-Order Perl、chap3から。

メモ化の話
少し前に流行った、fib関数をメモ化して速度を上げる話。
普通にいろんな実装方法を説明した後、どうやって一般化するかでMemoize.pmの紹介がある。

Perlだと メモ化を個人で実装する必要はなくて、
use Memoize;
memoize 'fib';
で関数fibをメモ化できる。この本では、紹介だけでなくMemoize.pmの動きをちゃんと説明している。Memoize.pmはPerlの内部テーブルを書き換える話をした後に、closureが来る。

どうみても、Lispです。
Padというのは、ローカル変数のbindingを行うデータ構造で、StubはPerlのjargonではCV(code,value)と呼ばれる。carが手続き(code)をさして、cdrがpad(ローカル変数のbinding)を指すと説明が入る。Perlでclosureが作られるとその数だけCVが作られる。普通にbindとか、lexical closureとか単語が飛び出し、ここだけ読んだらPerlの本とは思えない。SICP実践編って感じだ。銀行口座よりも、メモ化で高速にする方が面白い。

気がついたんだけど、Pythonとかanonymousなんちゃらの概念がある言語って同じ仕組みになっている気がする。ということは、gccもPerlもRubyもPythonも中はLispでできているんじゃね？Lispはあまり普及していないっていうけど、見えないところにLispの根ってのががっちり蔓延っていて、僕たちは毎日Lispを無意識に使っているんですよ。

あとは、将来言語設計に進みたい人はLispってのが避けて通れないと思った。

This page is a followup of this.

form http://paste.lisp.org/display/48776.

Our goal is this.
(define result 1)
(cond ((assoc 'b '((b 2))) => (lambda (x) (+ result (cadr x))))
(else false))
;; evaluates to 3

My evaluator expands the expression to this.
(let ((result (assoc 'b '((b 2))))) (if result ((lambda (x) (+ result (cadr x))) result) false))

When the environment has a variable named result, it encounts a name collision.

I can escape the problem easily like this.
(let ((result_ (assoc 'b '((b 2))))) ; change result to result_
(if result
((lambda (x) (+ result (cadr x))) result_)
false))
It runs correctly only in the situation. However this is not the solution that he want.

The GYNSYM system is a good idea.

My solution is this.
I introduce a reserved word like *COND->IF_RESULT* in my system.

ひげぽんさんの所をパクってテンプレートにして書いてみました。

練習問題をスキップしつつ、私も約半年でで読み終えました。とても楽しい日々を過ごすことができました。

SICPを読む過程で得たもの
・遅延評価とstream
・制約プログラミング、ロジックプログラミング、amb
・Emacs(Meadow)＋gauche＋Quackの組み合わせ便利
・同じ事を表現するのに、抽象度を上げたり、下げたりできること。
・手加減してあればLispのソースも追えるようになった。手加減していないのは駄目。
・Lisp特有の、手続きを評価する→S式ができる→また評価する→S式ができる、という気持ち悪い再帰の存在。
・SICP読み仲間ではないけどいろんなblogつながり。組み込みとFPGAだけでない、いろんな世界がある事をあらためて感じた。

SICPを読みはじめたときの動機を振り返る
・関数型言語について
　Lispは関数型言語では無い事が分かった。C++と同じで、関数型言語として書くことも出来るし、ループと破壊操作の組み合わせでも書ける。ただ、特別変わった言語という意識は無くなった。
・悟りについて
例のあれ
> LISP is worth learning for a different reason - the profound enlightenment experience you will have when you finally get it.
> That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.
この経験が役に立つかは、これから僕がどうするかだ。新しい概念は勉強できたけど、悟りを開いたかどうか微妙。
・Lispについて その1
　とりあえず、S式の世界に引きこもっているならLispが最強だと思った。SICP一冊読んだらLispについて語れるようになるかと思っていたけど、ただの入り口にしかすぎなかった。むしろ、読み終わってからLispの開始。Welcome to the Lisp world。
・Lispについて その2
C言語のプロトタイプ宣言程度の型チェックが欲しい。変数や関数に適切に名前を付ける能力が無いとLispは使いこなせない。自動GCは便利。Typoに弱い。デバッグ中に自分の想像と違う部分のコードが走っていてはまった。それぞれ良い方法があるんだろうけど。
・Paul Grahamについて
　Paul Grahamの言うところのLispの力は少しだけ分かった。Lispの力の一つは「S式引きこもり」。マクロも勉強しよう。もう一度、普通のやつらの上を行けを今読むと、Paul Grahamが丁寧に言葉を選んでいるように見える。

駄目だ。全然パクリ切れてない。普通に書こう。

SICPを勉強するのは、ハイソなお嬢さんと一夏を一緒に過ごしたような感じ。（ハイソって死語か）

3章まではいままでとは違う世界を丁寧に順番に紹介してもらい、住んでいる世界が違うことを実感。4章で初めての共同作業、世間しらずのお嬢様と思っていたけど、芯は太くてしっかりしている事を確認。5章は最後に一緒に映画を見に行った甘い思い出。このまま、美しい思い出のままで終わっても良い気がする。

思い返しても4章はきつい。ここから日本語の情報が激減する。できる一部の人たちは別の言語で処理系を作り始めるからあまり参考にならず、それ以外の人たちはここで脱落しているのでは無いかと思う。もしくは、大学の授業がその手前で終わってしまうとか。4章のきつさは、説明読む→打ち込む→動かして確認 のループが大きすぎる事。練習問題を解いてもそこだけは動かないからあっているかどうか分からない、Streamとか、put/getとか、今までに学んだことが当たり前のようにでてきて、飛ばした人間を容赦なく絶望させていく。

The老害のアドバイスとしては
・20代で読め！
　10年前とは言わなくても5年前にSICPを読んでいたら、と何回も悔やんだ僕がいうんだから間違いない。他の言語での実務経験はあった方がより楽しめる。
・半年くらい勉強する時間を作ろう。
　本文だけ読むよりは実際に手を動かした方が楽しい。ある程度時間がかかるという覚悟は必要。
・4章で迷い始めたら。
(1)とりあえずそのセクションは写経する。
(2)手続き毎に、教科書本文の説明をソースに付け加える。この手続きは○○を引数に××を返す等。
(3)一部でも動きが理解できたら、そこだけの単体試験を行う。
(4)納得するまで(2)に戻る
で、なんとか動きました。必要に応じて3章以前に戻るのも大事です。4章は特別難しい。
4章を理解すると、5章はボーナスステージのように面白いから頑張ろう。

今、次の本を決める至福の一時を満喫中。EoPLも良いんだけど、HTDPも興味あり。
思いて学ばざれば則ち殆うしのコメント欄が気になっていて、SICPよりもわかりやすくて、同じように楽しめる書籍があるなら、そっちの方が良いと思うんですよ。CPUの設計で言えば、Computer Architecture ← パタヘネ ← CPUの創りかた の関係が好きで、内容もボリュームもSICPはパタヘネに相当する。パタヘネが終わった後に、次はヘネパタだとか、Intelのデータシート読めとか、いやいや論文ですよ、みたいに言うのは簡単で、むしろパタヘネが難しいって人に何を薦められるかって事の方が難しい。とくに社内でLisp仲間を増やしたいなら、SICPでふるいをかけるよりはもうちょっと難易度の低い本が欲しい。The Little Schemerはちょっと違った。

そんなこんなで一夏の思い出を胸にしまい、FPGAの世界に戻ってこよう。 ♪終わらない、なつやすみ～

こういう計算機の説明の仕方もあるんだと、普通に感心した。
bit幅やアドレッシングが出てこないCPUの教科書って想像できますか？

それでいて、ALU、スタック、関数呼び出し、スタックといった基本構造だけでなく、コンパイラの最適化とリンカーまで、抽象度を上げたまま説明している。もちろんGCも簡単に説明してある。ネタとしか思えないんだけど、綺麗にLispの世界で説明しきっている。5章全部でfetchという単語が2回しかでてこない。計算機にとって、命令は取ってくる(fetch)するものではなく、単に実行(execute)する対象でしかないんだなとあらためて気がついた。そういえば、チューリングマシンにも命令フェッチって概念は無い。

プロセッサ、コンパイラ、リンカ、実行ファイルを抽象度を上げて考えるということを、今までしたことがなかったので夢中になって読めた。4章でさんざん苦労してきた事が、最後に綺麗にまとまったという感じを受けた。Webでも読めるけど、5章だけ読んでも面白くないと思う。

興奮が伝えきれない自分の国語力にorz

5章ヤバイ。エロい例えしか出てこないくらいヤバイ。
初めて憧れの女の子の手握ったら、やわらかくて、あったかくてびっくりしたくらいヤバイ。

イケメンPaul Grahamが、嫌がるStroustrupを華麗なマクロで翻弄し、生（ポインター）でアッー。

錯乱中

一つでもわかると、そこが取っかかりになってなんとか追えるようになってきた。

データベースの初期化ができていそうなので、Simple queryに挑戦。
(job ?x (computer programmer)

入力されたqueryは、?が分解される。

(query-syntax-process '(job ?x (computer programmer)))
=> (job (? x) (computer programmer))

これを忘れていて、迷宮にさまよい込んでしまった。

streamも少し修正して、ここまで動いた。

;;; Query input:
(job ?x (computer wizard))
;;; Query results:
(job (Bitdiddle Ben) (computer wizard))

;;; Query input:
(salary (Bitdiddle Ben) ?x)
;;; Query results:
(salary (Bitdiddle Ben) 60000)

2つめ以降の問い合わせができていない。
;;; Query input:
(job ?x (computer programmer))
;;; Query results:

とりあえず、効率を犠牲にして、fetch-assertionsを全てのassertionを返す事で対応した。
(define (fetch-assertions pattern frame)
　(get-all-assertions))

;;; Query input:
(job ?x (computer wizard))
;;; Query results:
(job (Bitdiddle Ben) (computer wizard))

;;; Query input:
(salary (Bitdiddle Ben) ?x)
;;; Query results:
(salary (Bitdiddle Ben) 60000)

;;; Query input:
(job ?x (computer programmer))
;;; Query results:
(job (Fect Cy D) (computer programmer))
(job (Hacker Alyssa P) (computer programmer))

;;; Query input:

ktkr！

Exercise 4.55.
a. all people supervised by Ben Bitdiddle;
(supervisor ?x (Bitdiddle Ben))

;;; Query results:
(supervisor (Tweakit Lem E) (Bitdiddle Ben))
(supervisor (Fect Cy D) (Bitdiddle Ben))
(supervisor (Hacker Alyssa P) (Bitdiddle Ben))

b. the names and jobs of all people in the accounting division;
(job ?x (accounting . ?y))
;;; Query results:
(job (Cratchet Robert) (accounting scrivener))
(job (Scrooge Eben) (accounting chief accountant))

c. the names and addresses of all people who live in Slumerville.
(address ?x (Slumerville ?y ?z))
;;; Query results:
(address (Aull DeWitt) (Slumerville (Onion Square) 5))
(address (Reasoner Louis) (Slumerville (Pine Tree Road) 80))
(address (Bitdiddle Ben) (Slumerville (Ridge Road) 10))

ここまで動くソースはここ
put-get.scmは拾い物ですが、どこから入手したのかすっかり忘れてしまったので、as-isで配布します。