祝 「Scheme 手習い」復刻

めでたい！ 「Scheme 手習い」が復刻しました。正確に言うと、復刻ではなく、新しい版に基づいた新しい訳です。

Scheme手習い

以前、マグロウヒル出版から出版されていた「Scheme手習い―直感で学ぶLisp」は、"The Little Lisper" の訳です。内容が、Common Lisp でもなく、Scheme でもない Lisp の方言によって書かれているのに、邦題に Scheme が入っていたのは、この本の唯一の欠点だと僕は感じていました。

今回は、"The Little Schemer" の訳です。原書も訳書も名実共に Scheme に基づいています。現在では、Lisp と言えば、Common Lisp か Scheme のことを指すようになりました。Scheme の実装も簡単に手に入ります。また、Lisp の価値も見直されています。よい時代に、よい翻訳書が現れました！

学ぶのは再帰

この本で学ぶのは「再帰プログラミング」です。

世界的に有名な Joel Spolsky 氏のエッセイの一つに「Java スクールの危険」があります。一部を引用します。

私のささやかな経験から言わせてもらうと、伝統的に大学のコンピュータサイエンスのカリキュラムで教えられているもので、多くの人がうまく理解できないものが2つあった: ポインタと再帰だ。

優秀なプログラマーとそうでないプログラマーを分ける指標の一つが、再帰を理解しているか否かです。優秀なプログラマーを目指すなら、再帰的な考え方を学ぶ必要があります。本書は、再帰を学ぶための最高の入門書です。

解説

Scheme 手習いは、習うより慣れろという感じで書かれているので、パズルを解くような楽しさがあるのですが、一方で、その背景や目的を理解しないまま読んでしまう恐れがあります。そこで、各章を少し解説しておきます。何をやっているのか分からなければ、以下を読んでみて下さい。

第1章

Scheme の基本的な関数 car、cdr、cons、null?、atom?、および eq? を学びます。Lisp を知らない人は、新鮮な感じで読めるでしょう。注意していただきたいのは、Lisp を中途半端に知っている人です。第1章を立ち読みして「なんだ知っていることばかりで、つまらない」と思って買うのを止めないで下さい。再帰が出てくるのは2章以降です。

分かっている人から見れば、これらの基本関数と(さらに cond と quote と)関数を定義する環境があれば、ピュアな Lisp が作れるという厳選された関数ばかりです。10章で、Scheme のインタープリターを作る際は、第1章に立ち返ってみて下さい。これらが珠玉のプリミティブだということが分かるでしょう。

第2章

いよいよ再帰を学びます。再帰は、基底部(null?)と再帰部(自分自身を呼び出す)から構成されることを理解しましょう。

第3章

入力のリストから出力として新しいリストを生成します。入力のリストは破壊されません。これが関数プログラミングの流儀です。リストを生成するには cons を使います。cons は、オブジェクト指向言語でいう new、C 言語でいう malloc() にあたります。大切なので、も一度言います。新しい値が作り出されるので、古い値は破壊されないのです。(不要になった古い値は、ゴミとして自動的に回収されます。)

第4章

自然数の演算を再帰で扱います。自然数が再帰で扱えるのは、自然数が帰納的(再帰的)に定義されているからです。

第5章

リストのリストに対して、深く再帰します。見方を変えれば、これは木構造に対する再帰です。リストは、木構造も表現できるのです。

第6章

影法師とは、補助関数のことです。補助関数というインターフェイスを定義して、データを抽象化します。(プログラムは理解しやすくなりますが、Scheme にはアクセス制御がないので、安全にはなりません。)

第7章

リストで集合を表現して、集合演算を実装します。

第8章

ついに、引数として関数が指定されるようになります。関数型言語では、関数が第一級の値であり、その素晴らしさが実感できるでしょう。継続も登場します。

第9章

とても難しい内容です。前半は、未解決問題である Collatz の関数、原始帰納的関数でない帰納的関数の代表例である Ackermann 関数、チューリングマシンの停止性問題がさりげなく登場します。

後半では、Yコンビネータを作ります。Yコンビネータとは、関数名を使わずに再帰を可能にする補助関数のことです。Yコンビネータ自体も、名前を使って再帰していないことに注意して下さい。(この Y コンビネータが BML であることが、いつか分かるかもしれません。)

第10章

Scheme のインタープリターを Scheme で実装します。このインタープリターはかなり優秀で、第9章で作った Y コンビネータを動かすこともできます。

あわせて読みたい

原書 "The Little Schemer" の解説記事も書いていますので、あわせてどうぞ。