Qiitaには以前からお世話になってますが、投稿をしたことはありませんでした。が、勤務先から『事務所総出でやります』という指令が下り、さてどうしたものか？と考えた末、思いついたのが『ひとりSICP読書会』です。一度は読んでおきたい (どんな内容か知りたい) 『計算機プログラムの構造と解釈』(Structure and Interpretation of Computer Programs) を一人もくもくと読んでいくというエントリです。
先人たちの情報によると『真面目にやると一年かかる』『本丸は4章5章、それをやらないと意味がない』と、始める前に挫折しそうですが、
- 表明した以上は止められない、完走しなきゃという気持ちになる。
- 親切な人が間違いの指摘やアドバイスをくれるかも。（←重要）
- 読んでみたいけど、、で踏み出せてない同輩諸氏の一助になるかも。（←これも重要）
という『三方良し』で乗り切りたいと思ってます。（三方？
※ここで書いていく内容は『参考になりそうなこと』や『こう考えた』とかで、直接的な書籍の内容や解答は避けるようにしています。が、もし差し障りありましたらご指摘ください。
ちなみに筆者は Emacs Lisp, Common Lisp の (永遠の) 初級者で、Scheme は全くの初学者です。なので本稿のタイトルを Scheme のS式で書こうとして「えぇーっ、Scheme には setq がないのかい？」と動揺しつつも野生の勘で書いてみたところ、
Welcome to Racket v8.6 [cs].
> (define ひとりSICP読書会#01 '("準備" "1.1.7"))
> ひとりSICP読書会#01
(mcons "準備" (mcons "1.1.7" '()))
> (car ひとりSICP読書会#01)
"準備"
> (cadr ひとりSICP読書会#01)
"1.1.7"
>
期待通りの動作はしてると思うのですが、、おしえて、えらいひと！
準備
紙の書籍として ピアソン版 をずっと前に買ってあり、また html版 も公開されていますが、今回は 真鍋氏による翻訳 を主に読んでいきます。
エディタは普段の環境と統一したいと思い IntelliJ IDEA + schemeプラグイン を試したのですが、インデントが好みでなかったため見送りました。
当面は Emacs の Scheme モードで進めることにします。
また実行環境は、MacOSを使用しているので homebrew で Racket をインストールしました。続いてSICPサポートのパッケージもインストールしましょう。手順に沿って DrRacket の Package Manager でインストールします。
これで inc 関数 1 も使用でき、SICP Picture Language で einstein の画像も表示できました！
いずれ Picture Language やデバッガを使用することになると思いますが、Emacs を使用していることですし、当面は Emacs 上で shell を起動して racket を実行する、というオールドスクールな構成で進めることにします。
これで準備完了です！
始めよう
では早速読み始めましょう。個人的な好みでは和田氏の堅い文体が「らしく」てアガるのですが、やはり真鍋訳が読みやすいです。そして読んでいくと見慣れない用語が出てきます。
環境 (environment) :
SICP ではいきなり出てきますが、「 初めての人のためのLISP (以降『竹内本』)」では最初は『"書いてあるS式を返し、出てなければエラーにする" 辞書』や『メモ用紙』と説明され2、『環境』という言葉が出てくるのは後半です。
未だ具体的なイメージが掴めてないのですが、スコープと呼ばれるものに近いでしょうか？異なる言語を同じ概念で括るのは危険なので、いずれは『環境』という概念の理解が必要ですが、いまは「スコープのようなもの」と考えて進めます。
述語 (predicate) :
これは「値が真か偽のどちらかとして解釈される式」ということで、SQL の述語と同じと考えて良さそうです。余談ですが Scheme では t / nil が出てこないのが、ちょっと寂しかったりします。。
論理複合演算 :
一般的に 論理演算子 と呼ばれるものと同じでしょう。なお、恥ずかしながら最近まで『論理演算子は真偽値を返す』と誤解してました。本書でも、
• (and ⟨e1⟩ . . . ⟨en⟩)
インタプリタは式 ⟨e⟩ を左から右にひとつずつ評価します。(略)すべての ⟨e⟩ が真と評価されると、and 式の値は最後の式の値になります。• (or ⟨e1⟩ ... ⟨en⟩)
インタプリタは式 ⟨e⟩ を左から右にひとつずつ評価します。⟨e⟩ のどれかが真と評価されると、その値が or 式の値として返され、(略)
ということで、実際に動作を確認すると、
> (and 1 2 3)
3
> (or "one" "two" "three")
"one"
>
と、Python や JavaScript などの論理演算子と同じ動作です。前項の "述語" から『SQLのように入出力とも真偽値のみ扱うのでは？』と推測したのですが、それは誤りでした。やはり思い込みは危険ですね！
練習問題 1.1 ~ 1.5
"1.1.6 条件式と述語" まで読み進めたところで、練習問題が出てきます。最初のうちは問題なかったのですが、1.5 でちょっと引っかかりました。
(define (p) (p))
何を言ってるのかわからなかったんですが3、順に読み解いていくと、
- これは
pという関数 (手続き) の定義 - 引数は無し
- 実行すると
pを実行する
ですね。Common Lisp で書くと、
(defun p () (p))
で、個人的にはこっちの方が理解しやすい気がします。ちなみに Racket だと実行しっぱなしで結果が返ってきませんが、同様のコードを Common Lisp で実行すると、
[1]> (defun p () (p))
P
[2]> (defun test (x y)
(if (= x 0) 0 y))
TEST
[3]> (test 0 (p))
*** - Lisp stack overflow. RESET
[4]>
と、即座に stack overflow になりました。
練習問題 1.6
更に読み進めていると、練習問題 1.6 でまた止まってしまいました。コードを何度読み返してもわからない。
Alyssa が平方根の計算するのにこれを使おうとすると、何が起こるだろうか。
ということなので、Alyssa になったつもりで実行してみると、これも前問 1.5 と同じく結果が返ってきません (DrRacket だと out of memory エラー)。sqrt-iter にデバッグ用の出力を書き加えて、
(define (sqrt-iter guess x)
(display (string-append (number->string guess) " "
(number->string x) " "
(if (good-enough? guess x) "#t" "#f") "\n"
))
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
で実行してみると、
> (sqrt 2)
1.0 2 #f
1.5 2 #f
1.4166666666666665 2 #f
1.4142156862745097 2 #t
1.4142135623746899 2 #t
1.414213562373095 2 #t
1.414213562373095 2 #t
1.414213562373095 2 #t
:
:
good-enough? が #t となっても処理が続いています。設問の冒頭に、
練習問題 1.6: Alyssa P. Hacker は、なぜ if が特殊形式として提供される必要があるのか理解できなかった。
と書かれているので、これがヒントだろうと if の仕様について調べようとしたのですが、、Scheme の言語仕様って、一体どこを見ればいいのやら。
ちょっと攻め方を変えて、 Common Lisp に書き直して実行してみると、
[1]> (defun square (x) (* x x))
SQUARE
[2]> (defun new-if (predicate then-clause else-clause)
(cond (predicate then-clause)
(t else-clause)))
NEW-IF
[3]> (defun sqrt-iter (guess x)
;(if (good-enough? guess x)
(new-if (good-enough? guess x)
guess
(sqrt-iter (improve guess x) x)))
SQRT-ITER
[4]> (defun improve (guess x)
(average guess (/ x guess)))
IMPROVE
[5]> (defun average (x y)
(/ (+ x y) 2))
AVERAGE
[6]> (defun good-enough? (guess x)
(< (abs (- (square guess) x)) 0.001))
GOOD-ENOUGH?
[7]> (defun new-sqrt (x)
(sqrt-iter 1.0 x))
NEW-SQRT
[8]> (new-sqrt 2)
*** - Lisp stack overflow. RESET
[9]>
同じ結果なので、Scheme 特有の仕様ではなさそう。じゃあ Common Lisp から攻めるか、と竹内本を見ても
cond は if よりもほんの少し一般的だ。なぜなら, if は条件に応じて 2 方向分岐をするが, cond は何方向にも分岐できるからじゃ。
と "なぜ if が特殊形式として提供される必要があるのか" に関する記述は見つかりませんでした。
こうなったら Guy L. Steele, Jr. 先生、こんなこともあろうかと用意しておいた4「Common Lisp」を紐解いてみると5、
Lisp における伝統的な条件付き実行のための構文要素は cond である。しかしながら, if というものがあり, これはより簡単で, また他のプログラミング言語における条件付き実行のための構文要素と直接比較できるものである。だから, if が Common Lisp におけるプリミティブとされた。(略)
if test then [else] 《特殊形式》
if 特殊形式は多くの算法プログラミング言語で見られるような if-then-else 構文要素に対応している。最初に形式 test が評価される。もしその結果が nil でなければ, 形式 then が選択される。そうでなければ, 形式 else が選択される。どちらの形式が選択されても, それが次に評価される。そして, if は選択された形式の評価が返すものを返す。
(if test then else) ≡ (cond (test then) (t else)
しかし if はいくつかの状況において, より読みやすいと考えられる。
...mjsk?
Alyssa P. Hacker は、なぜ if が特殊形式として提供される必要があるのか理解できなかった。
Alyssa P. Hacker は、なぜ if が特殊形式として提供される必要があるのか理解できなかった。
Alyssa P. Hacker は、なぜ if が特殊形式として提供される必要があるのか理解できなかった。
俺ちゃんもだ！！！
もしかして？
これ、new-if を作らなくても、直接 if を cond に書き換えられるんじゃないか？ とやってみたら。。。
Welcome to Racket v8.6 [cs].
> (define (square x) (* x x))
> (define (sqrt-iter guess x)
(display (string-append (number->string guess) " "
(number->string x) " "
(if (good-enough? guess x) "#t" "#f") "\n"
))
(cond ((good-enough? guess x) guess)
(else (sqrt-iter (improve guess x) x))))
> (define (improve guess x)
(average guess (/ x guess)))
> (define (average x y)
(/ (+ x y) 2))
> (define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
> (define (square x) (* x x))
> (define (sqrt x)
(sqrt-iter 1.0 x))
> (sqrt 2)
1.0 2 #f
1.5 2 #f
1.4166666666666665 2 #f
1.4142156862745097 2 #t
1.4142156862745097
>
えぇーっ！？ if が特殊形式として提供される必要 はなかったのかい？
問題は if 固有の挙動じゃなくて、if や cond といった特殊形式と new-if という関数 (複合手続き) の違いってこと？
言われてみると、if や cond は『条件が真であれば対応する式が評価される(他は評価されない)』のに対し、手続きの評価は、
インタプリタが実際に使っている “引数を評価してから適用する” という方法は、 適用順序評価 (applicative-order evaluation) と呼ばれます。6
なので、new-if の適用前に、第三引数 (sqrt-iter (improve guess x) x) が評価されると、確かにこのような挙動になると思うのですが。。
練習問題 1.6: Alyssa P. Hacker は、なぜ if が特殊形式として提供される必要があるのか理解できなかった。“cond を使って普通の手続きとして定義したらいいんじゃないの” と彼女は質問した。
いや、if を使いたくないなら、直接 cond で書けよ！ ←というのが正解？
解答集を見るのは悔しいのでもう少し考えてみますが、初回はここまで。
いきなり迷走してて、先は長いです。。。
※ 本稿で使用した画像 Cover of the book Structure and Interpretation of Computer Programs (second edition). Harold Abelson and Gerald Jay Sussman with Julie Sussman — MIT Press は CC 表示-継承 4.0 で公開されています。
-
SICP は『関数』と『手続き』を分けていますので、ここでは『手続き』と呼ぶべきでしょうか？ ↩
-
しかも「（タラリと一汗）ウム、では言いましょう。実はこれには哲学的に深ーい問題があるので私のような若輩にとっては荷の重い問題なのです。」という前置きから始まります。 ↩
-
なんか「見た目の対象性があって、シンプルだけどパッと見には内容がわからない」という感じから、K&Rの
while (*s++ = *t++)を連想しました。 ↩ -
正確には『図書館のリサイクル資料で見つけて、ホクホクとせしめた』です。 ↩
-
せしめたのはもう10年以上前ですが、初めて開きました。ちなみに初版なので古くなってる内容があるかも。 ↩