エンジニアをリングする

プログラをミングしたり。

my web site twitter

数学・情報系を専攻してないWebエンジニアがSICPを読んだメモ (1.1)

先日、minghaiさんによる非公式PDF版SICPの全訳を公開しましたというブログを見かけました。
SICPは以前に話を聞いて、難しそうだけどプログラミングの基礎体力的なものがつきそうでいいなあと思っていたところ、ちょうど日本語訳PDFが公開されたということでありがたくやってみることに。
全訳して公開って、素晴らしいですよね。minghaiさんありがとうございます。

私はプログラミングが好きなのですが数学や情報系を専攻していた経験がないので(関数型言語の経験もなし)、はたしてSICP理解できるのか?って感じですが・・

読んでみて思ったことやメモ書きを残しておきたいと思います。
印象深いところをピックアップしてあとから読み返せるように、引用を多めにさせてもらってます。
ちなみに非公式PDF版SICPminghaiさんによる全訳のライセンスはCC BY-NC-SAです。

Scheme実行環境の準備

まずmacで課題コードを動かせるようにschemeの実行環境をセットアップ。
こちらの記事を参考に、Gauche(Scheme処理系) + vim_goshrepl(vimからSchemeを対話形式で実行するプラグイン) を入れました。

Gauche(ゴーシュ)

brew install gauche

vim_goshrepl

.vimrcに追記

NeoBundle 'aharisu/vim_goshrepl'
" neocomplete用の設定
let g:neocomplete#keyword_patterns = {}
let g:neocomplete#keyword_patterns['gosh-repl'] = "[[:alpha:]+*/@$_=.!?-][[:alnum:]+*/@$_:=.!?-]*"
" 実行したいコードを選択してenterで実行
vmap <CR> <Plug>(gosh_repl_send_block)

で、:NeoBundleinstall

めっちゃ簡単。。

環境が整ったところで、さっそく頭から読み始めました。

献辞・前書き・序文

なかなか難しい内容のお話が続きます。。(1章の本文より難しかった)
いきなりめげそうになりましたがまだ本文じゃないのでとりあえず気にしない。

序文から、個人的に心打たれた部分を2箇所抜粋。

数学は “何であるか” の概念を正確に扱うためのフレームワークを提供します。計算機の使用は “行い方” の概念を正確に扱うためのフレームワークを提供します。

私達のこの計算機科学の入門科目の設計は 2 つの主な関心事を反映しています。1 つは、コンピュータ言語はコンピュータに命令を実行させるための単なる方法等ではなく、新しい種類の方法論に関する考えを表現するための公式なメディアであるという考えを証明することです。従ってプログラムは人々が読むために書かれねばならず、そしてただ偶然に機械にとって実行する物でなければなりません。

自分の言葉を交えて反復すると、プログラムは「ある人の考え方(アルゴリズム)を的確に表現するための公式なメディア」であるから、人間が読むために書かれるべきだ。そのことの重要性に比べれば、そのプログラムを機械が実行できることというのは偶然おきた副産物程度のものだ、ということですよね。
(機械で実行できることの重要性が低いということではなく、前者の価値がそれほど大きいということでしょう)

プログラムは考え方を伝える媒体、ということで、リーダブルコードの序文を思い出しました。
以下引用。

美しいコードを見ると感動する。優れたコードは見た瞬間に何をしているかが伝わってくる。

また、CodeIQ MAGAZINEで読んだ以下の文。

そのコードに美しさが見えるとき、おそらくそれはコード自体が美しいというより、アルゴリズムの美しさが自然にコードで表現されているのだと思います。

この辺りの言葉を思い出しました。

美しいプログラムとは、美しい考え方が明確にソースコードへ落とし込まれたものだという考えにはとても共感します。
美しいコードを生み出す大元の考え方の美しさに憧れるので、そういう考えができる頭にちょっとでも近づきたいなあという気持ちでSICPを読んでいます。

1章 手続を用いた抽象化の構築

LISP(Scheme)書くのも初めてなので、LISPについての説明もメモりたくなってしまうのですが量が多くなるのでそこは割愛。

- 1.1 プログラミングの要素 より

言語を記述する時、簡単なアイデアを組み合わせてより複雑なアイデアを形成するという手段をその言語が提供することには特に注意を払わねばなりません。強力な言語全てがこれを達成するために3つのメカニズムを持っています。

  • プリミティブな式: 言語に関わる最も単純な要素を表現する
  • 合成化の手段: これにより、より単純なものより複合要素が構築される
  • 抽象化の手段: これにより複合要素は名前を付けて個体として扱える

なるほど。
Schemeのコードで単純な例をあげると、

  • プリミティブな式: 1
  • 合成化の手段: (+ 1 2)
  • 抽象化の手段: (define (add a b) (+ a b)) ; a + b にaddという名前をつける

ということでしょうか。

- 1.1.4 複合手続 より

他の強力なプログラミング言語に必ず存在する要素をいくつか Lisp でも確認しました。

  • 数値と算術命令はプリミティブなデータと手続です。
  • 組み合わせのネストは演算の結合手法を提供します。
  • 名前と値を関連付けする定義は抽象化の限定された手法を与えます。

プログラミング言語というものが好きなので、汎用的で根本的な説明は興味深くて面白いです。

課題1.1~1.5をやりました。
課題1.5で(define (p) (p))と定義した(p)を実行してしまいMBAが興奮してあせりました。

LISPやっぱりカッコ多いけど、思ったよりとっつきやすい。
とはいえまだ簡単な数値の操作しかしてないですが。

- 1.1.7 例: ニュートン法による平方根

手続は効果的である必要があります。
その一例として、平方根の演算問題について考えましょう。square-root 関数を以下のように定義できます。
x = the y such that y ≧ 0 and y2 = x.
これは完全に正しい数学の関数です。これを用いてある数値が他の数値の平方根であるか分かりますし、平方根の一般的な事実を導出可能です。しかし一方でこの定義は手続の記述ではありません。与えられた数値から実際どのようにして平方根を求めるのか、これはほとんど何も教えてくれません。この定義を疑似 Lisp にて言い換えようとも問題の何の手助けにもなりません。これはただ問題を提起するだけです。

数学では通常宣言的 (what is) 記述を用い、コンピュータサイエンスでは通常手続的 (how to) 記述を用います。

数学的な関数とプログラミングの手続の役割の違い、言語化されるとなるほどという感じで腑に落ちます。

課題1.6~1.7をやりました。
1.6: なぜcondだけでなく特別形式としてifが必要なのか。ちゃんと考えたら理解できたので嬉しい。
1.7: 平方根を求めるsquare-iterの改良版square-rootの実装。abs使わずに引き算の順序でやろうとしたら詰まった。abs使ったらできた
1.8: 立方根を求めるcube-rootの実装。考えて書くの楽しい。
この辺りから、いつもと違う手応えを感じ始める。
なんというか、「あれ?変数ひとつも定義してなくね?」という感じ。定義した関数の引数だけで回していく感じ。
でもこの程度の計算だったら他の言語でも引数だけでできるか。

というわけで1.8をRubyでも書いてみた。計算結果は同じ。
やっぱり別に新しい変数定義はいらなかった。
数値クラスを拡張しているので数値からメソッドとして呼び出せてスマートな感じ。

はやくLISPならではみたいな処理を書いてみたい。

- 1.1.8 ブラックボックス抽象化としての手続

例えば good-enough? 手続を square の語を用いて定義する時、square手続を “ブラックボックス” として考えることが可能です。その時、その手続がどのように結果を計算するのか気にしていません。それが二乗を計算するという事実のみです。

いろんなsquareの実装が考えられるけど、squareを使うときには、ちゃんと二乗の値を返してくれる限り中身の実装方法については考えなくてよいということですね。

ユーザはその手続がどのように実装されているのかそれを使用するためには知る必要が無いのです。

この辺り好きな話です。

あとパラメータ名(引数名)とスコープについて。

  • 手続の意味はその作者が使用したパラメタの名前から独立すべきである

(define (double x) (+ x x))(define (double num) (+ num num))は引数名が違うけど手続の意味は同じということですね。振る舞いは引数名に左右されない(名前の衝突がない限り)。
ここから導き出される結論が以下

  • 手続のパラメタ名はその手続のボディに対してローカルであるべき

ある関数の引数名と別の関数の引数名が同じだったとしても、別のものとして扱われなければいけないということですね。

もしパラメタがそれらが関連する手続のボディに対してローカルでない場合、square のパラメタ x は good-enough? のパラメタ x と混同される可能性があります。そして good-enough? の挙動はどのバージョンの square を利用するかに依存するでしょう。従って square は私達が望んだブラックボックスではなくなるでしょう。

このへん基本なのですが納得感のある説明が続くので全部引用したくなってしまう・・・
なのであえて引用せずに、自分の言葉で要約してみます。

関数名の衝突を避けるために、手続の中に手続を定義することが有効である。これをブロック構造という。
手続を入れ子にして定義した場合、内側の関数は外側の関数の引数を使用することができる。(内側の関数の引数名で上書きされない限り)
このような規律をレキシカルスコープと呼ぶ。

JavaScriptを思い出しますね。

やっと、1.1が終わりました。。
まだまだ序の口ですが、今のところ面白いと感じているのでよかった。
1章は残り2と3、それが終わると2・3・4・5章があります。
4・5章が本番という声をよく聞くのでなんとかついていきたいです。