計算機プログラムの構造と解釈(SICP) 勉強メモ

普段からしている勉強内容をブログに貼り付けてみようと思った。
3日分。
9Pまで。

;\r => now file load REPL

;;;1.手続きによる抽象の構築
; 計算プロセス(computational process)とは計算機の中に住む抽象的な存在である。
;データとは(data)もう一つの抽象的な存在である。
;プログラム(program)とは規則のパターンである。
;プロセスは進行しながらデータを操作し、プログラムの指示に従う。

;;Lispによるプログラム
; 解釈系(interpreter)
; Lispは昔の絶望的に非効率という評判を克服できずにいる
;特徴の最も著しいのはプロセスの手続き(procedures)というLispによる記述自体がLispデータとして表現、処理出来ることである。
;Lispは手続きをデータとして扱える柔軟さを持つ。
; Lispでプログラムを書くのは大いに楽しいことだ。

;;1.1 プログラムの要素
; 強力なプログラミング言語は、計算機に仕事のやり方を指示する手段以上の物である。
;言語について語るとき、単純な概念を結合して複雑な概念を構成するのに言語が用意している手段に特に注意しよう。
; =>プログラミング言語は複雑な概念を構成するために、単純な概念を幾つか用意している。
;
;・基本式　言語が関わる最も単純なものを表す。
;・組合せ法　より単純なものから合成物を作る。　=>より単純な物とは基本式かな？
;・抽象化法　合成物に名を付け、単一の物として扱う。
;
; プログラムする時に二つの要素を扱う。手続きとデータだ。そしてそれらは実はそれ程違わない。
;データは処理したい「もの」である。
;手続きはデータの処理法の記述である。
;強力なプログラミング言語は、基本的データと基本的手続きを記述することが出来、
;手続きとデータを組み合わせたり、抽象化したりする手段を持たなければならない。

;;1.1.1　式
;式(expression)
;評価(evaluating)

(+ 137 349)
(- 1000 334)
(* 5 99)
(/ 10 5)
(+ 2.7 10)

;　上では式の並びかっこで囲んで、手続きの作用を表現している。
;これを組合せ(combinations)という。
;並びの左端の要素を演算子(operator),他の要素を非演算子(operands)という。　この例でだけだよね？
;組合せの値（組合せ法による合成物？）は演算子が指定する手続きを、非演算子の値である引数(arguments)に作用させて得る。 ;　演算子を非演算子の左に置く書き方を前置記法(prefix notation)という。
;前置記法には多くの利点がある。その一つは次の例のように任意個の引数をとる手続きを許すことである。

(+ 21 35 12 7)
(* 25 4 12);これよく言われるけど、少し複雑な数式は普通に書きたいよねー。。。

;第二の利点は組合せを入れ子にする(nested)ことを許すことだ。

(+ (* 3 5) (- 10 6))

;以下のような書き方をして混乱するのは人間で、Lisp解釈系は混乱しない。

(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))

;我々は長い組合せの非演算子が縦に整列するような清書系(pretty print)という書き方に従い

(+ 
  (* 3
     (+ (* 2 4)
        (+ 3 5)))
  (+ (- 10 7)
     6))

;この様にかく。
;　どの様な複雑な式に対しても、解釈系は常に同じ基本動作を繰り返す。
;端末から式を読み込み、その式を評価し、結果を印字する。
;このような動作のことを解釈系は、読み込み-評価-印字ループ(read-eval-print loop)を回るということがある。

;;1.1.2 名前と環境
;オブジェクトを値(value)とする変数(variable)を識別する物が名前である。
;LISPのScheme方言ではdefineを使って名前を付ける。

(define size 2)
(define pi 3.14159)
(define radius 10)

(display (* pi (* radius radius)))
(display "\n")

(define circumference (* 2 pi radius))
(display circumference)
(display "\n")

;　値と記号を対応づけ、後にそれを取り出す為には、解釈系は名前とオブジェクトの対を見失わないための、何か記憶を保持していることになる。
;この記憶を環境(environment)(より正確には、後になって計算は多くの異なる環境に関わることが解る故に大域環境(global environment))という。

;;1.1.3 組合せの評価
;本書の目的の一つは、手続き的な考え方に注目することである。
;組合せを評価するのに、解釈系自身も手続きに従っていると考えよう。
;組合せを評価するのには次のことを行う。
; 1.組合せの部分式を評価する。
; 2.最左部分式の値である手続き（演算子）を、残りの部分式の値である引数（非演算子）に作用させる。
;組合せの評価プロセスを達成するには、組合せの各要素の評価プロセスを実行しなければならない。
;すなわち評価の規則は本質的に、再帰的(recursive)である。
;つまり、手順の一部に規則自身を呼び起こす必要がある。
;
;　深く入れ子になった組合せの場合、再帰的な考え方を用いなければかなり複雑なる。
;しかし、それを用いれば簡潔に表現できる。

(* (+ 2 (* 4 6))
   (+ 3 5 7))

;の評価では、評価規則(* * + +)を個々の組合せ（カッコッカ）に対して4回行う必要がある。
;評価規則の「値が上方へわき出す」形は木構造の溜め込み(tree accumulation)として知られている。

;　第一の法則（組合せの〜）を繰り返して使っていると、評価する必要のない数字列、基本演算子、またはそれ以外の名前のような、
;組合せでない基本的な式の地点へ至る。（この場合390？）基本的な場合を扱うのに次を規定する。
;　・数字列の値は、その表す数値とする（1は1ってこと？）
;　・基本演算子の値は、対応する演算を実行する機会命令の列とする(+だと+を実行するための機会命令か？)
;　・それ以外の名前の値は、その環境で名前と対応づけられたオブジェクトとする（シンボル？）
;+や*のような記号は大域環境に含まれていて、その値である機会命令の列に対応づけられている。
;そう規定すると、第2の規則は第3の規則の特例とみてもよい。
;注意すべきは式での記号の意味の確定における環境の役割である。
;=>式の中である記号に値が紐づけられる際に、環境がどのような役割を果たすかである。
;環境は評価が行われる文脈を提供する物。

; 今までの評価規則は定義は扱わない。(define x 3)はdefineを二つの引数に作用させるのではない。
;　このような一般的評価規則の例外を特殊形式(special forms)という。

;;1.1.4 合成手続き
;　強力なプログラム言語に備わっているべき予想がLispにもあることを見てきた。
;　・数と算術演算子は基本的データと手続きである。
;　・組合せの入れ子は演算を組み合わせる手段である
;　・名前と値を対応づける定義は抽象のそこそこの手段である
;さらに強力な抽象化技法である手続き定義(procedure definitions)を学ぼう。
;これは合成演算(合成物?)に名前を対応づけ、一体として指すことが出来る。

;　手始めに自乗に表し方を調べる。「何かを二乗するには、それにそれ自身を掛ける」ということだ。
;われわれの言語では次のように表す。

(define (square x) (* x x))

;これでsquareという名前の合成手続き(compound procedure)ができた。

(define (sum-of-squares x y)
  (+ (square x) (square y)))
(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))

;;1.1.5 手続き作用の置き換えモデル
; ・合成手続きを引数に作用させるには、各仮パラメタを対応する引数で取り替え、手続きの本体を評価する。
; このプロセスを説明するのにfを1.1.4で定義した手続きとして、組合せ
;(f 5)
;を評価してみよう。まずfの本体を取り出す。
;(sum-of-squares (+ a 1) (* a 2))
;次に仮パラメタaを5で取り替える
;(sum-of-squares (+ 5 1) (* 5 2))
;これで問題は二つの被演算子と演算子sum-of-squaresを組み合わせの評価に帰着した。
;(+ 5 1)は6に、(* 5 2)は10になるのでsum-of-squaresを6と10に作用させることになる。
;この値はsum-of-squaresの本体の仮パラメタxとyに置き変えられ、式は
;(+ (square 6) (square 10))
;に帰着する。
;squareの定義を使えば
;(+ (* 6 6) (* 10 10))
;に帰着し、乗算により
;(+ 36 100)
;そして最後に
;136
;となる。
;
;　今述べたプロセスを手続き作用の置き換えモデル(substitution model)という。
;これは、この章の手続きに関する限り、手続き作用の「意味」を定めるモデルと考えてよい。しかし、注意する点が二つある。
;・置き換えの目的は、われわれが手続き作用を考える時の補助であって、解釈系の実際の働きを述べる物ではない。
;　解釈系は仮パラメタに値を置き換えて、手続きの字面を操作しつつ手続き作用を評価するのではない。
;　実際には、「置き換え」は、仮パラメタの局所環境を使って実現している。
;・本書の中では解釈系の働きについては、5章の解釈系と翻訳系の完全な実装に向かい、次々と精巧なモデルを提示していく。
;　一般に理工学の現象をモデル化する場合、単純で不完全なモデルから始める。
;　さらに洗練されたモデルで取り替わっていく、置き換えも出るも例外ではない。
;
;　1.1.3節に示した評価の記述によれば、解釈系はまず演算子と被演算子を評価し、次に結果の手続きを結果の引数に作用させる。
;しかし、これだけが評価を行う方法ではない。別の評価モデルでは、その値が必要になるまで、被演算子を評価しない（遅延評価？）。
;基本的演算子だけを持つ式が出てくるまで、パラメタへの被演算子の式の置き換えを繰り返し、それから評価を行う。
;この方法を例えば、
;(f 5)
;の評価は次の式の様に進行する。
;
;(sum-of-squares (+ 5 1)                  (* 5 2)                 )
;(+              (square (+ 5 1))         (sqare (* 5 2))         )
;(+              (*      (+ 5 1) (+ 5 1)) (*     (* 5 2) (* 5 2)) )
;さらに次のようになる
;(+              (* 6 6)                  (* 10 10)               )
;(+              36                       100                     )
;136
;
;このもう一つの「完全に展開し、簡約する」評価方法は正規順序の評価(normal-order evaluation)という。
;それに対し、解釈系が実際に使っている「引数を評価し、作用させる」方法を作用的順序の評価(applicative-order evalution)という。
;
;　Lispは作用的順序の評価を使っているが、それは上の (+ 5 1) と (* 5 2) で示したような式の多重評価を避けて得られる効率の為と、
;更に重要なことに置き換えでモデル化出来る手続きの範囲を抜けた途端に正規順序の評価がきわめて複雑になるからである。