Chapter 1 Building Abstractions with Procedures

追記：英語の文章はSICPからの引用です．

何故 lisp なのか云々．

1.1 The Elements of Programming

In programming, we deal with two kinds of elements: procedures and data. (Later we will discover that they are really not so distinct.) Informally, data is ``stuff'' that we want to manipulate, and procedures are descriptions of the rules for manipulating the data.

1.1.2 Naming and the Environment

It should be clear that the possibility of associating values with symbols and later retrieving them means that the interpreter must maintain some sort of memory that keeps track of the name-object pairs. This memory is called the environment (more precisely the global environment, since we will see later that a computation may involve a number of different environments).
この話は chapter 3 で詳しくやるそうな．

1.1.5 The Substitution Model for Procedure Application

式の評価のされ方．或いはその順序．
Applicative order versus normal order

(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

normal-order - ``fully expand and then reduce'' evaluation method
applicative-order - ``evaluate the arguments and then apply'' method

上の例は normal-order で，いったんすべての式を primitive な部分まで展開させてから評価する．一方，applicative-order では最初に arguments を評価してから展開していく．applicative-order では，

(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

となる．この場合，normal-order よりも (+ 5 1)，(* 5 2) の評価回数が少ないので効率が良い．

Exercise 1.3.

暗黙の了解として，これまでに出てきていない関数とかは使っちゃ駄目なんだよね，きっと．

(define (largest a b c)
  (cond ((or (< a b) (< a c))
         (largest b c a))
        ((= a b)
         (if (< a c) c a))
        ((= a c)
         (largest a c b))
        (else a)))

(define (secondly a b c)
  (if (= a (largest a b c))
      (if (> b c) b c)
      (secondly b c a)))

(define (sum-of-squares-of-two-larger-numbers a b c)
  (sum-of-squares (largest a b c)
                  (secondly a b c)))

何も考えずに書き下していくと非効率なコードが出来上がる．そんな典型．

Exercise 1.4.

+ と - を評価すると関数オブジェクトが返ってくるのが気になった．

gosh> +
#<subr +>
gosh> -
#<subr ->

少し疑問が湧いたので実験．

gosh> (define a 1)
a
gosh> a
1
gosh> (define a 2)
a
gosh> a
2
gosh> (equal? a 2)
#t
gosh> (define (a) 2)
a
gosh> a
#<closure a>
gosh> (a)
2
gosh> (equal? a 2)
#f

ヤダ，なにこれ，怖い．．．define が関数だろうと変数だろうと値を上書きしてる．しかも，関数と変数が同じ名前空間に定義されてる．これが scheme の流儀ということか．

Exercise 1.5.

面白かったので，elisp でもやってみた．

(defun p () (p))
(defun test (x y) (if (= x 0) 0 y))

(test 0 (p))

これを Emacs 上で評価してみると．．．

1.1.7 Example: Square Roots by Newton's Method

平方根を返す関数 sqrt を Newton's Method を使って定義．

Exercise 1.6.

lisp は applicative-order なので，「new-if を呼び出したときに先ずその引数をすべて評価しようとする．その過程で，new-if の else-clause が評価されるとき，sqrt-iter を呼び出す．sqrt-iter は当然 new-if を呼び出し，その new-if は更に sqrt-iter を呼び出す．」といった具合に無限ループに陥る．
なんか，説明文まで無限ループに陥りそうだな．違った言い方すると，applicative-order は ``evaluate the arguments and then apply'' で，new-if に当てはめると，then apply が cond 式になってる．で，実際に new-if の評価が開始されると，evaluate the arguments の時点で sqrt-iter の反復が始まってしまい，then apply が実行されないまま無限ループに陥る．

1.1.8 Procedures as Black-Box Abstractions

前半は関数を役割ごとに切り分けましょう，というお説教．後半は関数のパッケージングについて．

(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 内だけで有効なローカルな関数を定義できる．更に，sqrt の引数 x は lexical-scope になっているので，

(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))

と書ける．

1.2 Procedures and the Processes They Generate

To become experts, we must learn to visualize the processes generated by various types of procedures.

1.2.1 Linear Recursion and Iteration

n! を求める関数 factorial について考える．
線型再帰（linear recursive）の場合，

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

と書くことが出来，次のように評価される．

(factorial 6)
(* 6 (factorial 5))
(* 6 (* 5 (factorial 4)))
(* 6 (* 5 (* 4 (factorial 3))))
(* 6 (* 5 (* 4 (* 3 (factorial 2)))))
(* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1))))))
(* 6 (* 5 (* 4 (* 3 (* 2 1)))))
(* 6 (* 5 (* 4 (* 3 2))))
(* 6 (* 5 (* 4 6)))
(* 6 (* 5 24))
(* 6 120)
720

一方，線型反復（linear iterative）の場合，

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product counter max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

と書くことが出来，次のように評価される．

(factorial 6)
((fact-iter   1 1 6))
(((fact-iter   1 2 6)))
((((fact-iter   2 3 6))))
(((((fact-iter   6 4 6)))))
((((((fact-iter  24 5 6))))))
(((((((fact-iter 120 6 6)))))))
((((((((fact-iter 720 7 6))))))))
(((((((720)))))))
((((((720))))))
(((((720)))))
((((720))))
(((720)))
((720))
(720)
720

ここで，fact-iter は末尾再帰（評価の一番最後に自分自身を呼び出す）になっているので，末尾再帰の最適化が行われ，実際には次のように評価される（参考）．

(factorial 6)
(fact-iter   1 1 6)
(fact-iter   1 2 6)
(fact-iter   2 3 6)
(fact-iter   6 4 6)
(fact-iter  24 5 6)
(fact-iter 120 6 6)
(fact-iter 720 7 6)
720

1.2.2 Tree Recursion

木構造再帰は重複する計算が出てくるので，反復よりも遅くなるが，再帰でないと書けないような手続きもあるよ，ということで，コインの両替の話が出てくる．

1.2.3 Orders of Growth

ある手続きがどの程度のオーダーで評価されていくかをランダウ記法を使って考える．
線型再帰（linear recursive）な factorial の場合，

Θ(n) ; order of growth of the number of steps
Θ(n) ; order of growth of the space

線型反復（linear iterative）な factorial の場合，

Θ(n) ; order of growth of the number of steps
Θ(1) ; order of growth of the space

ここではΘを使っているけど，O で表現するほうが一般的かもしれない．

1.3 Formulating Abstractions with Higher-Order Procedures

高階関数

Exercise 1.29.

シンプソンの公式
$\int_a^bf\left(x\right)dx\simeq\frac{h}{3}\sum_{k=0}^{\frac{n}{2}-1}\left(y_{2k}+4y_{2k+1}+y_{2k+2}\right)$

gosh> (define (integral f a b n)
        (define h (/ (- b a) n))
        (define (y k) (f (+ a (* k h))))
        (define (integral-term x)
          (+ (y (* 2 x))
             (* 4 (y (inc (* 2 x))))
             (y (+ (* 2 x) 2))))
        (/ (* h (sum integral-term 0 inc (dec (/ n 2)))) 3))
integral
gosh> (integral cube 0 1 100)
1/4
gosh> (integral cube 0 1 1000)
1/4

分数出てきちゃったし．．．

gosh> (define (integral f a b n)
        (define h (/ (- b a) n))
        (define (y k) (f (+ a (* k h))))
        (define (integral-term x)
          (+ (y (* 2 x))
             (* 4 (y (inc (* 2 x))))
             (y (+ (* 2 x) 2))))
        (/ (* h (sum integral-term 0 inc (dec (/ n 2)))) 3.0))
integral
gosh> (integral cube 0 1 100)
0.25
gosh> (integral cube 0 1 1000)
0.25

そこじゃないのか．

gosh> (define (integral f a b n)
        (define h (/ (- b a) n))
        (define (y k) (f (+ a (* k h 1.0))))
        (define (integral-term x)
          (+ (y (* 2 x))
             (* 4 (y (inc (* 2 x))))
             (y (+ (* 2 x) 2))))
        (/ (* h (sum integral-term 0 inc (dec (/ n 2)))) 3))
integral
gosh> (integral cube 0 1 100)
0.2500000000000001
gosh> (integral cube 0 1 1000)
0.2500000000000001

これでいいのか．．．？

Exercise 1.31.

総乗
a. 取り敢えず反復で．

(define (product term a next b)
  (define (iter a res)
    (if (> a b)
        res
        (iter (next a) (* (term a) res))))
  (iter a 1))

product を使えば factorial も瞬殺．

(define (factorial n)
  (product identity 1 inc n))

円周率の近似式
$\pi=4\cdot\frac{2\cdot4\cdot4\cdot6\cdot6\cdot8\cdots}{3\cdot3\cdot5\cdot5\cdot7\cdot7\cdots}\simeq4\prod_{k=1}^{n/2}\frac{2k\left(2k+2\right)}{\left(2k+1\right)^2}$

(define (pi n)
  (define (term k)
    (/ (* 4 k (inc k)) (square (inc (* 2 k)))))
  (* 4 (product term 1 inc (/ n 2))))

シンプソンの公式の時もだけど，内部で (/ n 2) してるのは行儀が悪いのかもしれない．どちらも近似式なので，割る必要はないんだろうね．
b. product を再帰で．

(define (product term a next b)
  (if (> a b)
      1
      (* (term a)
         (product term (next a) next b))))

1.3.2 Constructing Procedures Using Lambda

無名関数 lambda とそのシンタックスシュガーである let の説明．
某三週間によれば，

(define (func arg)
  arg)

は，λを使って，

(define func
  (lambda (arg)
  arg))

とも書ける．また，fluid-let という dynamic-scope の変数束縛もある（処理系依存）．

Exercise 1.34.

gosh> (define (f g)
        (g 2))
f
gosh> (f f)
*** ERROR: invalid application: (2 2)
Stack Trace:
_______________________________________

(f f)
-> g = f と解釈して (g 2) を呼び出す
-> (f 2)
-> g = 2 と解釈して (g 2) を呼び出す
-> (2 2)
-> 2 は関数じゃないよ

1.3.3 Procedures as General Methods

x |-> y

は，x を写像（関数）を通して y にするって意味だったはず．
Finding fixed points of functions
不動点の性質を利用して sqrt を定義する（Newton's Method とは異なるアプローチ）．

;; without average damping
(define (sqrt x)
  (fixed-point (lambda (y) (/ x y))
               1.0))

;; with average damping
(define (sqrt x)
  (fixed-point (lambda (y) (average y (/ x y)))
               1.0))

1.3.4 Procedures as Returned Values

Experienced programmers know how to choose procedural formulations that are particularly perspicuous, and where useful elements of the process are exposed as separate entities that can be reused in other applications.
Newton's method
derivative（導関数），average damping, fixed-point などのアプローチを考慮して，Newton's method を再定義．

Abstractions and first-class procedures

高階関数を使ってプログラムを適度に抽象化させることは大事だよね．
This is not to say that one should always write programs in the most abstract way possible; expert programmers know how to choose the level of abstraction appropriate to their task.

Exercise 1.46.

(define (iterative-improve guess-func improve-func)
  (lambda (x)
    (if (guess-func x)
        x
        ((iterative-improve guess-func improve-func) (improve-func x)))))

(define (sqrt x)
  ((iterative-improve (lambda (guess)
                        (< (abs (- (* guess guess) x)) 0.001))
                      (lambda (guess)
                        ((lambda (a b) (/ (+ a b) 2)) guess (/ x guess))))
   1.0))

(define (fixed-point f first-guess)
  ((iterative-improve (lambda (guess)
                        (< (abs (- guess (f guess))) 0.00001))
                      f)
   first-guess))

λ使い過ぎて可読性が下がってるな．