はむはむエンジニアぶろぐ

365日エンジニアリング

SICP 1.1章読んでみた

f:id:secret_hamuhamu:20150524211758j:plain

SICPを読んで学んだことをまとめていこうと思う。
SICPってなんだぜ?
* コンピュータサイエンスのバイブル的な位置づけ。
* MIT大学のコンピュータサイエンスの講義に使われていた。

日本語訳で、計算機プログラムの構造と解釈です。
とても有名な本です。
分厚いし、難しいので実際に手を動かしてみてアウトプットしないと身につかないので読んだまとめを定期的にブログにアップしていこうと思う。
1.1章読むだけで、1週間かかった。。。

SICPを学ぶことで

  • コンピュータの原理・原則が分かる
  • ベースとなる基礎力がアップするので、知識の横展開ができる

SICPを読めば、エンジニアとして成長できることは間違いない。
しかし、SICPに挫折したひとも多いと聞く。

何故、SICPが辛いのか?

  • 分厚くて、文字が小さいので、根気と時間がいる
  • 内容が、難解であるにもかかわらず言い回しが回りくどい
  • 変なジョーダンや比喩の多用
  • 数学の知識がいる

SICP辛い場合、コチラの本がオススメらしい
ポストSICPと呼ばれている
プログラミングの基礎

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)

あとこれ
アンダースタンディングコンピュテーション

1 手続きによる抽象の構築

1章は、抽象がテーマ。

1.1 プログラムの要素

強力なプログラム言語は、計算機に仕事のやり方を指示する手段以上のものである。

ここでいう強力なプログラム言語とは、高級言語(LispJava)のことを指しているのかな?

強力な言語には3つの仕掛けがある。

  • 基本式 言語が関る最も単純なものを表す.
  • 組合せ法 より単純なものから合成物を作る.
  • 抽象化法 合成物に名をつけ, 単一のものとして扱う.


プログラムをする時、2つの要素: 手続きとデータを扱う。 データは処理したい「もの」であり、手続きはデータの処理法の記述である。 強力なプログラム言語は基本的データと基本的手続きが記述出来、手続きとデータを組み合わせたり、抽象化したりする手段を持たなければならない

ここでいう手続きは、演算や関数(function)と認識していいと思う。処理と呼ばれるもの。
抽象化したりする手段とは、変数宣言であったり関数名である。
sum = 100; とすることで、100は何かの合計値と表現できるし、 function count() { … } であれば、何かをカウントしている手続きと表現できる。

1.1.1 式

LispScheme方言でコードを書いていきます。
SICPが、それで書かれてるので合わせてやります。
私は、Lisp初心者なので詳しいことは、分からないので特に解説なしでいきます。
でも触ったことのない言語に触れるのは勉強になりますね。


まずは、Hello Woldしてみる。

(print "Hello Wold!")
; Hello Wold!

OKですね。では、本題に入ります。


式を入力すると解釈系(インタプリタ)は、応答してその式を 評価した 結果を返します。
整数も基本的な式の一つとされている。

wikipedia参照 : 式 (プログラミング)

式(しき、expression)とは、プログラミングにおいて、言語によって定められた優先順位や結びつきの規定に則って 評価される値、変数、演算子、関数の組み合わせである。数学における式と同様、式は評価された値を持つ。

演算子( +-*/ )などが含まれているものが、式だと思っていました。なるほど。
何かしら評価した結果を返すことが出来るのが、式でありLispにおいては、 + などの演算子は式である。

gosh> (+)
0

その他言語では、 + は組み込まれていたりします。

Lispに整数を与えると解釈系は式を評価して結果を返します。

gosh> 486
486

数を表現する式は基本的な手続き(+や*など)を表現する式と組み合わせて合成式として、数に対してそれらの手続きの作用を表現することが出来る。

; 合成式:(基本的な手続き '+' 基本式 '137' 基本式 '349')
gosh> (+ 137 349)
486

gosh> (- 1000 334)
666
gosh>(* 5 99)
495
gosh> (/ 10 5)
2
gosh> (+ 2.7 10)
12.7

用語

演算子(operator)は、 +-*/
演算子(operand)は、 137 + 349でいうところの137や349のこと。
前置記法(ポーランド記法)は、演算子を被演算子の左に置く記法である。

前置記法になれない方がほとんどでは無いかなと思います。
普段、我々が扱っているのは中置記法です。137 + 349など

ちなみに前置記法ではこのような記述ができる。

gosh> (+ 21 35 12 7)
75
; 演算子を省略できる
; 21 + 35 + 12 + 7

gosh> (* 25 4 12)
1200
; 25 * 4 * 12

Lispの解釈系が評価し得る入れ子の深さや式の全体としての複雑さには原則として制限はない。

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

; 入れ子になりすぎて分かりにくいので整形
gosh> (+ (* 3
      (+ (* 2 4)
         (+ 3 5)))
   (+ (- 10 7)
      6))
57

このように複雑な式であっても解釈系は、解釈系は常に同じ基本動作を繰り返す。
式を読み込み、式を評価し、結果を印字する。


1.1.2 名前と環境

プログラム言語は、名前を使って計算オブジェクトを指す手段として変数がある。
LispScheme方言では、defineを使って変数宣言を行。

gosh> (define size 2)
size
; 変数宣言
; 解釈系は、値2と名前sizeとを結びつけている
gosh> size
2
; 変数を評価して返す
gosh> (* 5 size)
10


円周の計算

gosh> (define pi 3.14159)
pi
gosh> (define radius 10)
radius
gosh> (* pi (* radius radius))
314.159
gosh> (define circumference (* 2 pi radius))
circumference
gosh> circumference
62.8318


defineは、 circumference のような、合成演算の結果を格納することができるのでプログラム言語において最も簡単な抽象手段である。
この抽象手段があるお陰で、複雑な構造を持つ計算オブジェクトを覚えなくて良い。
変数というものがなければ、何度も計算を行って算出しないといけないので、大変なのが分かる。
解釈系では、名前とオブジェクト(値)の対応付けが、処理が進む度に次々と出来上がっていくので、プログラムの構成が便利になっていく。

名前とオブジェクトを対応付け、後で取り出して使用するためには解釈系は、対応付けを記憶しておかなければならない。
この記憶を 環境(大域環境) というらしい。

1.1.3 組み合わせの評価 {#sec1}

ここでいう組み合わせとは、いくつもの式が組み合わさったものである。

; 組み合わせでない
100

; 組み合わせである
(+ 1 5)

; 組み合わせである
(* (+ 2 (* 4 6))
   (+ 3 5 7))

組み合わせ評価のために、解釈系自身も手続きに従っている。

組み合わせの評価

  • 1. 組み合わせの部分式を評価する
  • 2.最左部分式の値である手続き(演算子)を、残りの部分式である引数(被演算子)に作用させる

組み合わせの評価プロセスを満たすためには、組み合わせの各要素の評価プロセスを実行しなければならない。
評価の規則は、本質的に再帰的(recursive)である。

入れ子になった組み合わせを用いて評価手順をだしてみる。

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

; ① (* 4 6)
(* (+ 2 24)
   (+ 3 5 7))

; ② (+ 2 24)
(* 26
   (+ 3 5 7))

; ③ (+ 3 5 7)
(* 26 15)

; ④ (* 26 15)
390

上記の組み合わせであれば、評価規則を個々の組み合わせに対して四回行う必要性があるのが分かる。

(+ x 1)

x に意味を与える環境がなければ、成立しない。

環境は、評価が行われる文脈を提供するものだという考え方は、プログラムの実行を理解する上で重要な役割を果たしている。


例えばこういうものは組み合わせではない。

(define x 3)

代入をしているので組み合わせではい。
こういう一般評価規則の例外を 特殊形式 という。
特殊形式は他にもたくさんあり、各特殊形式はそれぞれで評価規則を持っている。
こういった一般評価式や特殊形式といった色々な種類の式でプログラム言語の構文規則ができている。

式の評価規則は、単純な一般規則と、少数の特殊形式に特化した規則で出来ている。

補足

結果は一緒であるが、書き方が違う。
こういうものを シンタックスシュガー という。

// インクリメント
i = i + 1;

i += 1;

1.1.4 合成手続き

高級言語に備わっているべき要素。

  • 数と算術演算子は基本的データと手続きである
  • 組み合わせの入れ子は演算を組み合わせる手段である
  • 名前と値を対応付ける定義は抽象のそこそこの手段である

変数は、抽象技法である。
さらに強力な抽象技法として手続き定義がある。いわゆる関数のこと。
これによって、合成演算に名前を対応付けて扱うことが出来る。

二乗する関数

「何かを二乗するには、それにそれ自身をかける」

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

; (define… には
; (square x) 二乗する 何かを
; (* x x) 掛ける それに それ自身を

これで、squareという合成手続きができた。 この手続は、何かにそれ自身を掛ける演算を表す。 掛けられるものは局所的な名前xを持つ。 定義を評価すると、この合成手続きがつくられsquareという名前が対応付けられる

演算は、手続きなので合成演算である関数は、合成手続きである。

手続き定義の一般的形
Lispでなくてもほとんどの言語がこうだと思います。

(define (<name> <formal parameters>) <body>)

名前は、環境でこの手続適宜に対応づける名前である。 仮パラメタは、手続き本体の中で、手続きの対応する引数を指すための名前である。 本体は、仮パラメタが、手続きを作用させる実引数で取り替えられて手続き作用の値を計算する式である。

squareの使用例

gosh> (square 21)
441
gosh> (square (+ 2 5))
49
gosh> (square (square 3))
81

squareを他の手続き(下の数式だと+)と組み合わせてつくことが出来る。

例えば、 f:id:secret_hamuhamu:20150524211052p:plain

(+ (square x) (square y))

このように表せる。

合成手続き(square)の組み合わせを行ってみる。
引数に2つの数値を受け取って、受け取った2つの引数の二乗の和を作る合成手続き sum-of-squares

(define (sum-of-squares x y)
  (+ (square x) (square y)))

gosh> (sum-of-squares 3 4)
25
; (3 * 3) + (4 * 4) = 25


もちろん、sum-of-squares使って別の手続きを作ることが出来る。

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

gosh> (f 5)
136

合成手続きは、基本手続と全く同様に使うことが出来る。 実際、上のsum-of-squaresの定義を見ただけでは、squareが+や*のように解釈系に作りこまれたか、合成手続きとして定義されたのか分からない。

+や*は、定義しなくても使えるように組み込まれている。
squareは、定義されていないがsum-of-squaresを扱う側からすれば、squareが組み込まれているかのように扱うことが出来るということかな。

1.1.5 手続き作用の置き換えモデル

演算子が合成手続きの組み合わせを評価するのには、解釈系は1.1.3節で行った基本的手続きの評価とほとんど同じプロセスを踏む。
評価のプロセスは、合成手続きであっても基本手続きであっても変わらないということ。

  • 合成手続きを引数に作用させるには、各仮パラメタを対応する引数で取替、手続きの本体を評価する

合成手続きの評価プロセスを確認してみる。
1.1.4節で定義したfを使って、組み合わせ (f 5) を評価してみる。

(f 5)

; まず、fの本体を取り出す
(sum-of-squares (+ a 1) (* a 2))

; 仮パラメタaを引数5で取り替える
(sum-of-squares (+ 5 1) (* 5 2))
(sum-of-squares 6 10)

; sum-of-squaresを取り出す
(+ (square 6) (square 10))

; squareを取り出す
(+ (* 6 6) (* 10 10))
(+ 36 100)
136

このようなプロセスを手続き作用の 置き換えモデル という。
ただし、置き換えモデルは注意する点が2点ある。

  • 置き換えの目的は、我々が手続き作用を考えるための補助であって、解釈系の実際の動きを述べるものではない。
  • 置き換えモデルは、評価プロセスを形式的に考える第一歩
    「可変データ」を持つ手続きを使うと、置き換えモデルは破綻し、手続き作用のより複雑なモデルで取り替えなければならない事がわかる。

あくまで、手続き作用というものをイメージする為のモノである。
もっと複雑なモデルなどは、この後の章に登場するらしい。


作用的順序と正規順序

1.1.3節の評価モデルと異なる評価モデルは、被演算子が必要になるまで、被演算子を評価しないモデルもある。

基本的演算子だけを持つ式が出てくるまで、パラメタへの被演算子の式の置き換えを繰り返し、それから評価を行う。

実際に先ほどの合成手続きの組み合わせ (f 5) でやってみる。

(f 5)
(sum-of-squares (+ 5 1) (* 5 2))
(+    (square (+ 5 1))      (square (* 5 2))  )

; (+ 5 1)と(* 5 2)の評価は二度づつ行われている
; これを式の多重評価という
(+    (* (+ 5 1) (+ 5 1))   (* (* 5 2) (* 5 2)))

(+         (* 6 6)             (* 10 10))
(+           36                   100)
136

置き換えモデルと同じ結果であるが、プロセスが異なっているのが分かる。


今回の評価方法(完全に展開し、簡約する)は 正規順序の評価 という。
それに対し解釈系が実際に使っている評価方法(引数を評価し、作用させる)方法を 作用的順序の評価 という。

置き換えを使ってモデル化出来、正しい値が得られる手続き作用については、正規順序と作用的順序の評価は同じ値になることが示される。

Lispは、作用的順序の評価を使っている。
理由は、式の多重評価を避ける事で、効率が良くなるから ということと
置き換えでモデル化出来る手続きの範囲を抜けた途端に正規順序の評価が極めて複雑になるからである。

正規順序の評価が悪ということではなく、使い方によっては有効となる。
これは、3章と4章で解説されるみたい。


1.1.6 条件式と述語

ここまで学んだ手続きの表現力では、以下の様な絶対値を計算する手続きを表現できません。

数値が、正か負か零かを調べ規則に従って、値を計算する手続き。

  • x > 0の時 xを返す
  • x = 0の時 0を返す
  • x < 0の時 -xを返す

このような手続きを表現するための構文を、 場合分け という。
Lispには、場合分けを記述する特殊形式がある。
それを cond(conditional:条件付き) といい、次のように使う。


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

gosh> (abs 100)
100
gosh> (abs 0)
0
gosh> (abs -100)
100
(cond (<p1> <e1>)
      (<p2> <e2>)
      ・
      ・
      ・
      (<pn> <en>))

condに続けて、節というかっこに入った式の対(

)を並べてものである。 対の最初の式は述語(predicate) 値を真か偽と解釈する式である。

if文やcase文を書いたことがあるのならば、わかると思いますが、まず述語 <p1> を評価し、その値が偽なら <p2> を評価する。
<p2> が偽なら <p3> を評価するといったように、値が真である述語が見つかるまでその手順を繰り返す。
真を見つけたら解釈系は、その節に対応する帰結式(consequent expression)の値をこの条件式の値として返す。


述語という用語は、真と偽に評価される式と同様、真か偽を返す手続きのも使う。


先ほどの絶対値の手続きを書く他の方法。

(define (abs x)
  (cond ((< x 0) (- x))
        (else x)))

「xが0より小さければ-xを返す。それ以外は、xを返す。」

特殊形式 if を使った絶対との手続きを書く方法。

(define (abs x)
  (if (< x 0) ; predicate
      (- x)   ; consequent
      x))     ; alternative

if式の一般形
(if <predicate> <consequent> <alternative>)

if式を評価するには、解釈系は式の述語>部分を評価する。
の評価の結果が真なら、解釈系は帰結部を評価し、その値を返す。
そうでなければ、代替部を評価し、その値を返す。

< , > , = のような基本的述語の他に、合成述語を作るための論理合成演算があり、代表的なのが以下の3つ

  • (and <e1> ... <en> ) 解釈系は、式 <e> を左から右へ一つづつ評価する。
    ある、 <e> の評価が偽ならand式の値は偽で、残りの <e> は評価しない。

  • (or <e1> ... <en> ) 解釈系は、式 <e> を左から右へ一つづつ評価する。
    ある <e> の評価の結果が真なら、その値をor式の値として返し、残りの <e> は評価しない。

  • (not <e> ) not式の値は、式 <e> の評価の結果が偽なら真、真ならば偽である。


andとorは、必ずしも評価されるのではないから、手続きではなく、特殊形式である。
notは通常の手続きである。

1.1.6節で最も大事なのは個人的にこれ。
述語というのは、真か偽を返すものである

問題

問題 1.4

問題1.4が面白かったので紹介。

(define (a-plus-abs-b a b)
   ((if (> b 0) + -) a b))

gosh> (a-plus-abs-b 2 3)
5
gosh> (a-plus-abs-b 2 -3)
5

if文の結果に +- を返している。
これは、Lispだから出来る事で、例えばPHPでは同様のことは行えません。
+- は、標準で提供されている組み込み関数であって言語構造に組み込まれていないらしいです。
PHPだと +- は演算子であって、関数(式)ではない。

1.1.7 Newton法による平方根

これまでに扱った手続き(関数)は、数学の世界の関数とよく似ている。
一個か複数のパラメタから決まる値をきていする。
しかし、数学の世界の関数と計算機の世界の手続きの間には重要な違いがある。

数学の世界の関数というのは、手続きを述べていない。
与えられたパラメタを使いどうするか?という記述をするのが、計算機の手続きである。

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

大きいプログラムであれば、手続きの束と見ることができ、一連の手続きで分割することが重要である。
最初の10行、次の10行のようにまとめるのではなく、分割する単位の手続きは部品として使えてまとまった仕事ができるかといった視点で分ける。
squareという手続きが定義されているとして、square手続きがどのように実装されているかは「ブラックボックス」と見ることが出来る。
squareがどうやって計算するかは関心を持たず、関心があるのは、squareが二乗を計算して返すという結果である。

square手続きを扱う側からすれば、squareは手続きの抽象化(手続き抽象)である。

最近読んだ本

計算機プログラムの構造と解釈[第2版]

計算機プログラムの構造と解釈[第2版]

  • 作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一
  • 出版社/メーカー: 翔泳社
  • 発売日: 2014/05/17
  • メディア: 大型本
  • この商品を含むブログ (2件) を見る

プログラミングの基礎 (Computer Science Library)

プログラミングの基礎 (Computer Science Library)

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで

アンダースタンディング コンピュテーション―単純な機械から不可能なプログラムまで