あどけない話

インターネットに関する技術的な話など

祝 「Scheme 手習い」復刻

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

Scheme手習い

Scheme手習い

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

今回は、"The Little Schemer" の訳です。原書も訳書も名実共に Scheme に基づいています。現在では、Lisp と言えば、Common LispScheme のことを指すようになりました。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" の解説記事も書いていますので、あわせてどうぞ。