SICP 1.1 読書メモ

はじめに

SICP を読んだ個人的メモ

hitoshi-manabe さんの訳 を使わせていただく

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

計算プロセスについて学ぶ

計算プロセス

• 抽象的な存在である
• データを操作する
• プログラミング言語によって組み立てられる

Lisp を使用する

Lisp

• 再帰方程式についての推論を定式化するものとして発明された
• 手続きが、それ自身 Lisp のデータとして表され、操作できる
  • 受動的なデータと能動的なプロセスという区別を曖昧にできるという意味で重要な特性

1.1 プログラミングの要素

プロセスについて考えをまとめる枠組みとしてのプログラミング言語

達成するためのメカニズム

• 基本式: 言語に関わる最も単純な実体を表す
• 組み合わせ方法: 複合要素をより単純なものから構築する方法
• 抽象化方法: 複合要素に名前をつけ、単体として扱うための方法

プログラミングで扱う要素

• 手続き
• データ
  • これらははっきり分かれるものではない
• データは私達が操作したい対象
• 手続きはデータを操作するための規則を記述したもの

1.1.1 式

インタプリタ

• 式を入力すると、インタプリタはその式の評価の結果を表示し、応答する

式

• 数値を表す式

486

• 複合式
  • 数値を表す式と基本的は手続きを表す式の組み合わせ
  • このような式は手続きの適用を意味し、組み合わせとよばれる

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

• 左端の要素は演算子とよばれ、ほかの要素は被演算子とよばれる
• 被演算子の値を引数と呼ぶ

前置記法

• 演算子を被演算子の左に置くという方法を前置記法という

利点

• 任意の数の引数を取る手続きにも対応できる

(+ 21 35 12 7)
(* 25 4 12)

• 組み合わせをネストできる

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

プリティプリント

• 被演算子が垂直に揃うようにそれぞれの長い組み合わせを書くというフォーマットの習慣をプリティプリントとよぶ

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

REPL

• read-eval-print loop

1.1.2 命名と環境

コンピュータ上のオブジェクトを指すために名前を利用する手段

• 上記を値がそのオブジェクトである変数を名前によって特定するという
• Lisp(Scheme)では define を使用する

define

(define size 2)

• 上記により、インタプリタは size という名前と 2 という値を関連付ける

環境

• 上記機能を実現するためには、名前とオブジェクトのペアを記録しておくために何らかのメモリを持っておく必要がある
• このメモリを環境(より正確にはグローバル環境)とよぶ

1.1.3 組み合わせの評価

組み合わせを評価するための手続き

1. 組み合わせの部分式を評価する
2. 部分式の左端(演算子)の値となっている手続きを、引数(被演算子)、つまり部分式の残り値に適用する

上記から分かる手続き一般についての重要なポイント

• 組み合わせに対する手続きを評価するには組み合わせのそれぞれの要素に対する評価手続きを先にやらないといけない

  • 評価規則は本質的に再帰的

• ある点で評価する対象が、組み合わせではなく数値や組み込み演算子やその他の名前といった基本式になる

再帰によって複合式は完結に表現できる

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

• 上記式の評価を木で表すことでイメージする

    390
 /  |    \
/   |      \
*   26      15
  / |  \   / | | \
+  2  24  +  3 5  7
     / | \
    *  4  6

• このように評価された値が上に向かって伝わっていく、という形の評価規則は木の集積として知られている

基本式の評価

• 数字の値は、それが示す値である
• 組み込み演算子の値は機械語の列で、それに対応する操作を実行する
• その他の名前の値は、現在の環境でその名前に関連付けられたオブジェクトである

評価を行う文脈を提供する存在としての環境

• (+ x 1) という式の値について考えるためには x という記号に意味を付与する環境についての情報がなければ意味がない
• + についても同様に意味を付与するのは環境である

特殊形式

• ここまで書かれた評価規則は define については扱っていない
• このような例外を特殊形式とよぶ

1.1.4 複合手続き

手続きの定義

• 二乗の計算

(define (square x) (* x x))
(square 21) ; 441
(square (+ 2 5)) ; 49
(square (square 3)); 81

• $x^2+y^2$

(define (sum-of-squares x y)
  (+ (square x) (square y)))
(sum-of-squares 3 4) ; 25

• sum-of-squares を利用した手続き

(define (f a)
  (sum-of-squares (+ a 1) (* a 2)))
(f 5) ; 136

• square や sum-of-squares、f を複合手続きとよぶ

1.1.5 手続き適用の置換モデル

複合手続の適用手順

• 複合手続きを引数に適用するには手続きの本体に出てくる仮引数を対応する引数で置き変えて、それを評価する

例

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)
(+ (square 6) (square 10))
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

置換モデル

• 上記手順を、手続き適用の置換モデルとよぶ

適用順序と正規順序

• 引数を評価してから簡約するという評価方法を適用順序評価とよぶ
• 完全に展開してから簡約するという評価方法を正規順序評価とよぶ

例

• 適用順序評価の例は先の f の評価手順
• 正規順序評価の例は以下

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+ (square (+ 5 1))    (square (* 5 2)))
(+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
(+ (* 6 6) (* 10 10))
(+ 36      100)
136

注意

• 置換によってモデル化でき、かつ政党な値を返す手続き適用については、正規順序評価と適用順序評価は同じ値になることが証明されている
• Lisp では適用順序評価を使用している
  • 上記例からわかるように同一のものを複数回評価することをさけるため
  • 置換によってモデル化できない手続きについて、正規順序評価が複雑になるため

1.1.6 条件式と述語

cond

• 場合分けを記述するための特殊な形式

(define (abs x)
  (cond ((> x 0) x)
        ((= x 0) 0)
        ((< x 0) (-x))))

• (> x 0) x) のような部分を節とよぶ
• (> x 0) のような値が真か偽のどちらかとして解釈される式や > といった手続き自体を述語とよぶ
• 値が真になる述語が見つかるまで、述語を上から順に評価して、真となった述語の直後に記載された結果式の値を返す
• 述語が全て偽である場合は cond の値は未定義となる
• Lisp(Scheme) では真は #t 偽は #f として表される

if

• 場合分けが丁度二つの場合らなる場合につかえる特殊形式

(define (abs x)
  (if (< x 0)
      (- x)
      x))

• 述語を評価して、その結果が真であれば最初の式を返し、偽であれば二つ目の式を返す
• cond は結果式は式の列であってもよいが、if は一つの式でなければならない

複合述語

• 基本述語(<, =, >)を組み合わせて構築される述語を複合述語とよぶ
• 複合述語を構築するために論理複合演算が用意されている

論理複合演算

• and, or, not
• and と or は全ての式を評価しないので特殊形式である
• not は通常の手続き

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

関数と手続きの違い

• 双方ひとつ移譲の引数によって決定される値を規定する
• しかし、手続きは実効的なものでなければならない

$$
\sqrt{x} = y \geq 0 , かつ , y^2 = x , であるような , y
$$

• 上記は $x$ の関数であるが、手続きを記述するものではない
• 数学では宣言的な記述が関心の対象
• コンピュータサイエンスでは命令的な記述が関心の対象

平方根の計算方法

• ニュートンの逐次近似法を使うのが一般的
• 数値 $x$ の平方根の推定値 $y$ があるとき $y$ と $x/y$ の平均をとる操作を繰りかえすことで $\sqrt{x}$ を近似する

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (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 (sqrt x)
  (sqrt-iter 1.0 x))

• 上記はループを組み込んでいなくとも、手続きの呼び出しにより実装できることの実例にもなっている

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

• sqrt は自然にいくつかの部分問題に分割されている
  • sqrt-iter、improve、good-enough?...
• 分割された手続きがそれぞれ特定のタスクをなしとげる、ブラックボックスとみなせる
  • 分解された手続きを使用する側ではどうやって結果を計算するかは関心がない
  • 手続き抽象となっている

局所名

• 手続きを利用する側はその手続きの仮引数の名前に関心を持たないでよい

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

• 上記手続きは判別不可能であるべき
• その手続きの中で名前が何であってもかまわない変数を束縛変数とよぶ
  • 手続きの仮引数はこの性質を持つ
  • 手続き定義は仮引数を束縛する、と言う
• 束縛されていない変数は自由であるという
• 束縛により名前が定義される式のセットは、その名前のスコープと呼ばれる
  • 手続き定義では、仮引数はその手続き本体をスコープとしてもつ

例

good-enough? において

• 束縛変数: guess x
• 自由変数: < - abs square
• guess を abs と改名してはいけない
• guess x は自由変数と違うものとして区別可能な名前であればどのような名前でもよい
• abs は cos に変えてしまうと違う関数を計算することになる

内部定義とブロック構造

(define (sqrt x)
  (define (good-enough? guess x)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess x) (average guess (/x guess)))
  (define (sqrt-iter guess x)
    (if (good-enough? guess x)
        guess
        (sqrt-iter (improve guess x) x)))
  (sqrt-iter 1.0 x))

• 上記のように内部定義をすることで sqrt-iter などの手続きを局所化できる
• このような定義のネストをブロック構造とよぶ
• さらに、good-enough? などは x のスコープ内に存在するので自由変数にすることができる

(define (sqrt x)
  (define (good-enough? guess)
    (< (abs (- (square guess) x)) 0.001))
  (define (improve guess) (average guess (/x guess)))
  (define (sqrt-iter guess)
    (if (good-enough? guess)
        guess
        (sqrt-iter (improve guess))))
  (sqrt-iter 1.0))

• このようにすると x の値は sqrt の引数からとることができる
  • この規定をレキシカルスコーピングとよばれる
    • 手続きの自由変数はその手続きを包む手続き定義の束縛を参照する

練習問題

1.1

10 ; 10
(+ 5 3 4) ; 12
(- 9 1) ; 8
(/ 6 2) ; 3
(+ (* 2 4) (- 4 6)) ; 6
(define a 3)
(define b (+ a 1))
(+ a b (* a b)) ; 19
(= a b) ; #f
(if (and (> b a) (< b (* a b)))
    b
    a) ; 4
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25)) ; 16
(+ 2 (if (> b a) b a)) ; 6
(* (cond (( > a b) a)
         (( < a b) b)
         (else -1))
   (+ a 1)) ; 16

1.2

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

1.3

(define (ex1_3 x y z)
  (cond ((and (> x y) (> y z)) (sum-of-squares x y))
        ((and (> x y) (< y z)) (sum-of-squares x z))
        (else (sum-of-squares y z)))

1.4

$b > 0$ であれば、演算子は + となり、そうでなければ - となる。これにより b の絶対値を a に足し合わせる挙動となる

1.5

• 正規順序評価

(test 0 (p))
(if (= 0 0) 0 (p)))
0

• 適用順序評価

(test 0 (p))
(test 0 (p))
(test 0 (p))
...

1.6

(sqrt-iter 1.0 2)
(new-if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))
(new-if (good-enough? guess x) guess (new-if (good-enough? ((improve guess x) x) (improve guess x) (sqrt-iter (improve (improve guess x) x))
...

となり Scheme の評価規則である適用順序評価によると評価が終了しない

1.7

(sqrt 0.000000001) ; 0.03125001065624928
(sqrt 100000000000000000) ; 計算が終わらなかった

(define (sqrt x)
  (sqrt-iter 1.0 0.0 x))
(define (sqrt-iter guess guess-old x)
  (if (good-enough? guess guess-old)
      guess
      (sqrt-iter (improve guess x) guess x)))
(define (improve guess x)
  (average guess (/ x guess)))
(define (average x y)
  (/ (+ x y) 2))
(define (good-enough? guess guess-old)
  (< (abs (- (square guess) guess-old)) 0.001))

1.8

(define (cbrt x)
  (cbrt-iter 1.0 0.0 x))
(define (cbrt-iter guess guess-old x)
  (if (good-enough? guess guess-old)
      (guess
      (cbrt-iter (improve guess x) guess x)))
(define (improve guess x)
  (/ (+ (/ x 
           (* y y))
        (* 2 y))
     3))