『計算機プログラムの構造と解釈』一章一節読書メモ

1.1.1.markdown

式

普通の四則演算として考えると次のように表せる。

1 + 2 * 3 + 4 / 2

これは、下のようにまとめることが可能だ。

1 + (2 * 3) + (4 / 2)

実は、これらの四則演算も、一つの関数として見ることが可能である。どういう関数かといえば、 両隣を引数として取る関数 である。実際に、Haskellでは、下のような定義をすることによって、両隣を引数として解釈する。

vadd :: Vector->Vector->Vector
1 `vadd` v2 =3D zipWith (+) v1 v2

• http://www.haskell.org/pipermail/haskell/2003-July/012219.html

この手と比べると、確かに可変引数を前提とすることで、S式は、オペレーターを先頭に持っていくことはメリットではあるものの、しかしこれは実態的には、foldlみたいに、左に折りたたむ形になるのではないかという印象もある。つまり

(+ 1 2 3 4)

とあった場合、

(+ 3 3 4)

になり

(+ 6 4)

で、最終的に

10

となる、という印象。ようするに、可変長とは

(+ (list 1 2 3 4))

という感じ（Pythonのでは*argsや**kwargs）のようにも見えるが、どうなんだろうか。

1.1.2.markdown

名前と環境

特に無し。ここでは、「名前」と「値」を結びつける「環境」が存在している、ということを確認しておく。ただ、名前に数をバインドすることは、読みやすさに直結し、整理するという意味で重要だ。

1.1.3.markdown

組み合わせの評価

　急に出てくる「再帰」という言葉に戸惑う。この場合の「再帰」は、雑に理解するならば、次のように考えられるのだろうか？

eval -> (+ (* 1 3) (/ 6 2)) -> return

evalは「評価」するマシーンであり、returnはその結果を出力すると考える。evalは、最初のカッコを「これから出てくるものは足すものだなというように理解する。しかし、次に出てくるのが(* 1 3)のため、もう一度、「評価マシン」を呼び出す必要がある。つまり、これはいったい何なのだ、ということだ。

eval -> (* 1 3) -> return

さて、これを評価した結果、「3」という値を帰すことがわかった。従って、(* 1 3)は下のように置き換えることができる。

eval -> (+ 3 (/ 6 2)) -> return

しかし、3を足そうとしたところで、次にまた(/ 6 2)が出てきてしまう。なので、これを変換する必要がある。

eval -> (/ 6 2) -> return

すると、今度は3が引き出せた。なので、同じように置き換えられる。

eval -> (+ 3 3) -> return

こうして、最後の結果として、6が取り出される。ポイントは、これらが何かしらの値に収縮するということだと思う。さらに、ここで特殊な例としてdefineを説明している。

感想

例えば、Yaccなどの構文解析木も、文字列を規則にしたがい、トークンにしたがい、置換していくという作業を取っている。ちょっと変な例だが、次のようなものを考えてみる。

It is (This is a Pen).

例えば、文は下のようにまとまるという風に定義しよう。

STATEMENT = goal
SVO | SVC = return STATEMENT

そして、それぞれに次のような定義を与える。

It = S
is = V
a Pen = O
This is = return next
. = ignore

これらを評価するマシーンに与える。

eval -> SV (This is a Pen). -> return

さて、ここでカッコが出てきたので、一度中断し、評価を持ってくる。

eval -> This is a Pen. -> return

ここで、定義されたトークンの規則にしたがう。

eval -> return O -> return

さて、これが帰ってきて

eval -> SVO -> return

最終的に

eval -> STATEMENT -> return
eval -> return goal -> return
goal

という形になる。

1.1.4.markdown

合成的手続き

defineが、任意のモノとモノを結びつける役割を持つ、ということは、それらは別の言い方をするなら 置換 できる、ということを説明しているように思われる。実際に、1.1.5で、この過程を置換モデルとして表現している。注目するのは、むしろ日本語で書かれた部分だろう。もう少しわかりやすい表現になおすと、恐らく

xをsquareする の定義は xをxに掛ける

ということだろう。ここで着目するべきは動詞の位置である。カッコくくるなら、

(xをsquareする) の定義は (xをxに掛ける)

ということになる。あえてPythonで表現すると

def square(x):
    return x * x

であり、これは

宣言する: xをsquareする
    xにxを掛けた値を戻す

と無理矢理、日本語にできる。問題は、Lispの場合、動詞が先に来ることによって、柔軟さを得ているように感じる。これは生成文法がまず動詞を取るという考え方とほんのちょっとだけ似ているように感じる。

あと、全く無意味であるが、この手続き定義を下のように考える。

(define (invalid x) 3)

こうすると、いかなるxであれ、3を返す。xは、この場合全く利用されない。

1.1.5.markdown

作用的順序と正規順序

二つの方法、つまり 正規順序の評価 と 作用的順序の評価 という二つの方法があることを確認する。作用的順序は、評価をしながら必要な分を持っていく。恐らく、多くの言語はそのメモリの制約上、作用的順序の方法を使っているように感じる。というのはどういうことかというと、下のPythonのスクリプトを考えるとわかりやすいかもしれない。

class FoobarClass(object):

    def run(self):
        self.is_run = True
        return self.is_run

    def not_run(self):
        self.is_run = False
        return self.is_run

foobar = FoobarClass()

if foobar.run() or foobar.not_run() or foobar.undefine_method():
    print "not run!!"

if foobar.run() and foobar.not_run() and foobar.undefine_method():
    print "run"

作用的順序の評価が危険なのは、上記のように、場合によってはundefine_methodに評価が到達しない場合がある。

1.1.6.markdown

条件式と述語

始めて条件式が出てくる。これによって、ある入力に対して、別々の処理を行なうことが可能になる。

1.1.7.markdown

Newton法による平方根

ここで解説されていることは、端的に言うことができるならば、数学的アプローチと、コンピューター的アプローチの違いだと言える。