SICPを読む_(3)1章_手続きによる抽象の構築(p1-13)
実際に読んだとこを振り返りながらまとめてみる
Lispによるプログラミング(p1-2)
- John McCarthyによって発見された言語(再帰方程式という計算モデルが元)
- 現代においても使われているFortranの次に古い言語
- プログラムの構成やデータの構造を学び、言語の基礎となる言語学的機能に関係付けるのに優れた媒体になる特徴を持っている。
- プロセスの手続きをLispデータとして表現、処理できる。
- Lispでプログラムを書くのは楽しいこと。
1.1プログラムの要素(p2)
強力な言語には3つの仕掛けがある。
- 基本式 (言語が関る最も単純なもの)
- 組合せ法 (単純なものから合成物をつくる)
- 抽象化法 (合成物に名前をつけ単一のものとして扱う)
1.1.1式(p3)
- 「式」を解釈系(処理系)が「評価」する。
Lispの基本的な式の1つは整数(10進法の整数を表す数字)らしい。
整数も「式」だと思うといろいろ納得できるというか面白いですね。データも手続きも「式」。
(+ 137 349) ;;=>486
括弧で囲んで手続きの作用を表現するような式を「組合せ」といって、左端の要素を「演算子」、それ以外の要素を「被演算子」という。演算子が指定する手続きを、被演算子の値である「引数」に作用させて得ると。。
いわゆる「前置記法」で書きなさいよってことですね。
勿論、「入れ子(ネスト)」もできるのでこんな風にも書けますよっと。
(+ (* 3 5) (- 10 6)) ;;=>19
- 処理系が評価し得るネストの深さや四季の複雑さに(原則として)制限はない
(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
こういう式が読みにくいのは人間だけで、処理系はすぐに答えを出します。
まぁこのままだと読みにくいので「清書系」と言われる書き方に従って書くよ。
(+ (* 3 (+ (* 2 4) (+ 3 5))) (+ (- 10 7) 6))
ここらへんはEmacsで普通にC-jとか打てばいい感じにインデントしてくれるので助かる。
1.1.2名前と環境(p4)
(define size 2) ;;=> sizeという変数に2という値が対応付けられる
もっとも単純な抽象化。
1.1.3組合せの評価(p5)
- 組合せを評価するには次のことを行なう
- 組合せの部分式を評価する
- 最左部分式の値である手続きを、残りの部分式の値である引数に作用させる
つまり評価規則が再帰的であると…。
「木構造のため込み(tree accumulation)」と言われるらしい
評価する必要のない数字列、基本演算子、それ以外の名前に関しては以下の規定に従う。
- 数字列の値は、その表す数値とする
- 基本演算子の値は、対応する演算を実行する機会命令の列とする
- それ以外の名前の値は、その環境で名前と対応付けられたオブジェクトとする
基本的な評価規則の例外を特殊形式という。(defineとかifとか)
1.1.4合成手続き(p6)
- 数と算術演算子は基本的データと手続きである
- 組合せの入れ子は演算を組み合わせる手段である
- 名前と値を対応付ける定義は中小のそこそこの手段である
更に強力な手続き定義を知ることで、合成演算に名前を対応付けることができる。
例えば二乗の表し方は以下の通り。
(define (square x) (* x x))
squareという合成手続きができた。定義ができたので使うことができるようになると。
(define (sum-of-squares x y) (+ (square x) (square y)))
といったように新たな合成手続きを作ることもできる。素敵。
当然ながらsum-of-squaresの定義を見ただけじゃ処理系に作りこまれたか、合成手続きとして定義されたか分かりませんよっと。
1.1.5手続き作用の置換えモデル(p7)
(define (f a) (sum-of-squares (+ a 1) (* a 2)))
上のように定義された手続きfを
(f 5)
として評価すると
;; まずfの本体を取り出す (sum-of-squares (+ a 1) (* a 2)) ;; 仮パラメタaを引数5に取り替える (sum-of-squares (+ 5 1) (* 5 2)) ;; sum-of-squaresの仮パラメタx,yを6,10に置き換える (+ (square 6) (square 10)) ;; squareの定義を使って (+ (* 6 6) (* 10 10)) ;; 乗算により (+ 36 100) ;; 最後に 136
となる。
これを「置き換えモデル」という。
ただ、処理系の実際の動きとは違うらしく、あくまでも手続き作用の意味を定めるモデルらしい。
(詳しくは後の章で出てくるらしいので、こんなもんだくらいで思ってたら良さそう)
- 作用的順序と正規順序
上の置き換えモデルと違って、「完全に展開して、簡約する」方法を正規順序の評価というらしい。
;; 上の置き換えモデルの一部抜粋 (sum-of-squares (+ 5 1) (* 5 2)) (+ (square (+ 5 1)) (square (* 5 2))) (+ (* (+ 5 1) (+ 5 1)) (* (* 5 2) (* 5 2)))
実際の処理系では「作用的順序の評価」を使っていて、理由としては
- 多重評価を避けることができる
- 正規順序の評価が極めて複雑になるときがあるから
1.1.6条件式と述語(p9)
- 場合分けを記述する特殊形式がある。
- cond(conditional)
こんな感じで使えるよっと。
(define (abs x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x))))
一般形がこんなん
(cond (<p1> <e1>) (<p2> <e2>) . . . (<pn> <en>))
条件式は次のように評価される。
述語
その手順を値が真である述語が見つかるまで続ける。見つけたら処理系はその節の対応する帰結式
述語(predicate)という用語は、真と偽に評価される式と同様に、真か偽を返す手続きにも使う。<,>,=は述語らしいです。それからcondの代わりに場合分けが丁度2つであるような場合に使う特殊形式ifがある。
if式の一般形は
(if <predicate> <consequent> <alternative>)
述語を評価して真なら帰結部
;; if式でのabs (difene (abs x) (if (< x 0) (- x) x))
基本的な述語<,>,=の他に、合成述語を作るための論理合成演算がある。and,or,notが良く使われる。
問題1.1-1.5(p11-12)
githubにあげてるので、そっちを参照。
問題1.4に関しては、実行してから驚いた。
;; 例えばa,bを10,-10と置き換えたら (a-plus-abs-b 10 -10) ((if (> -10 0) + -) 10 -10) (- 10 -10) 20
問題1.5はよーわからんかった…。
(define (p) (p)) (define (test x y) (if (= x 0) 0 y)) (test 0 (p))
とりあえず、処理系に突っ込んだら無限ループに陥ったので、処理系は作用的順序を採用してるんだと思う。
正規順序で処理された場合、ifが先に評価されて0が返ってくるんじゃないのかなーとか。
とりあえずvallogで答え合わせ
あってるぽい??
まぁいいや。
1.1.7例:Newton法による平方根(p12-13)
;; 二乗を求める (define (square x) (* x x)) ;; 絶対値を求める (define (abs x) (if (> x 0) x (- 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)) ;; 平方根を求める手続き,どんな数の平方根も1だと推測する (define (sqrt x) (sqrt-iter 1.0 x))
Newton法は正直知らなかったので、へぇ…と思いましたん。素敵。
ということで、ここまで特に迷うことなく進めましたよっと。。。
実際に読んでる頁はもう少し先なんですが、まとめるのに時間かかるなーと思ってたり…。
頑張って読むよ!!
