1.3.3 一般的方法としての手続き
http://sicp.iijlab.net/fulltext/x133.html
区間二分法(half-interval method)は連続関数fに対し, 方程式f(x)=0の根を探す単純かつ強力な技法である
(define (search f neg-point pos-point) (let ((midpoint (average neg-point pos-point))) (if (close-enough? neg-point pos-point) midpoint (let ((test-value (f midpoint))) (cond ((positive? test-value) (search f neg-point midpoint)) ((negative? test-value) (search f midpoint pos-point)) (else midpoint))))))
(define (half-interval-method f a b) (let ((a-value (f a)) (b-value (f b))) (cond ((and (negative? a-value) (positive? b-value)) (search f a b)) ((and (negative? b-value) (positive? a-value)) (search f b a)) (else (error "Values are not of opposite sign" a b)))))
解への逐次近似を平均化する方法を 平均緩和法(average damping)
1.3.4 値として返される手続き
引数として手続きが渡せるとプログラム言語の表現力が格段に広がる
すみません、読み間違えました。。急に難しくなった。。
1.1.3 組合せの評価
組合せを評価するには次のことを行う:
- 組合せの部分式を評価する
最左部分式の値である手続き(演算子)を, 残りの部分式の値である引数(被演算子)に作用させる
評価の規則は, 本質的に 再帰的
- 木構造のため込み
- 数字列の値は, その表す数値とする.
- 基本演算子の値は, 対応する演算を実行する機械命令の列とする.
それ以外の名前の値は, その環境で名前と対応づけられたオブジェクトとする.
一般的評価規則の例外を特殊形式
- +や*のような記号は大域環境に含まれていて, その「値」である機械命令の列に対応づけられていると規定すれば, 第二の規則は第三の規則の特例と見てもよい.
1.1.4 合成手続き
強力なプログラム言語に備わっているべき要素がLispにもある
- 数と算術演算子は基本的データと手続きである
- 組合せの入れ子は演算を組み合せる手段である
- 名前と値を対応づける定義は抽象のそこそこの手段である
gosh> (square 10) 100
- 合成手続き 何かにそれ自身を掛ける演算
(define (⟨name⟩ ⟨formal parameters⟩) ⟨body⟩)
1.1.5 手続き作用の置換えモデル
合成手続きについて, 作用のプロセス
合成手続きを引数に作用させるには, 各仮パラメタを対応する引数で取り替え, 手続きの本体を評価する.
(define (sum-of-squares x y) (+ (square x) (square y))) sum-of-squares gosh> (sum-of-squares 3 4) 25 gosh> (sum-of-squares (+ 5 1) (* 5 2)) 136
これが、(+ (square 6) (square 10))に帰着する. squareの定義を使えば(+ ( 6 6) ( 10 10))に帰着し, 乗算により(+ 36 100)そして最後に136になる.今述べたプロセスを手続き作用の置換えモデル(substitution model)という。
「完全に展開し, 簡約する」評価方法は 正規順序の評価 (normal-order evaluation)という. それに対し解釈系が実際に使っている「引数を評価し, 作用させる」方法を 作用的順序の評価(applicative-order evaluation)という.
1.1.6 条件式と述語
の規則に従って別の行動をとることで, 値の 絶対値を計算する手続きを定義することは出来ない. このための構文を 場合分け(case analysis)といい, Lispには場合分けを記述する特殊形式がある. それを cond(conditional(条件つき)を意味する)といい, 次のように使う:
(define (abs x) (cond ((> x 0) x) ((= x 0) 0) ((< x 0) (- x)))) abs gosh> (abs -10) 10 gosh> (abs 0) 0
その一般式
(cond (⟨p1⟩ ⟨e1⟩) (⟨p2⟩ ⟨e2⟩) (⟨pn⟩ ⟨en⟩))
- 節(condのあと)
- 述語(対の最初の式)
- 帰結式(解釈系は, その節の対応する 帰結式(consequent expression)⟨e⟩の値をこの条件式の値として返す)
1.1.7 例: Newton法による平方根
これまでに紹介した手続きは, 通常の数学の関数によく似ている. つまり一個か複数のパラメタから決る値を規定する. しかし数学の関数と計算機の手続きの間には, 重要な違いがある. 手続きは実効的でなければならない.
実効的であることが重要なので、数学的な式をそのままコードに当てはめても意味がない。
(define (sqrt x) (the y (and (>= y 0) (= (square y) x))))
この手順を手続きを使って形式化
(define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) sqrt-iter (define (improve guess x) (average guess (/ x guess))) improve gosh> (define (average x y) (/ (+ x y) 2)) average (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) good-enough? (define (sqrt x) (sqrt-iter 1.0 x)) sqrt gosh> (sqrt 9) 3.00009155413138
平叙文的記述と命令文的記述は, 数学と計算機科学のように, 密接に関係している. 例えばプログラムの出した答が 「正しい」というのは, プログラムについての平叙文的声明である. プログラムが正しいということを証明する技術を確立しようとした膨大な研究があり, この問題の技術的な困難の多くは, (それでプログラムが作られている)命令文的声明と(ことを簡約化するのに使われる)平叙文的声明の間の変換を取り決めるところにあった. この系統の, プログラム言語設計の最近の主要な分野は, それにより平叙文的声明を使ってプログラムをしようとする, いわゆる超高レベル言語の探索である. その考え方は, 解釈系を十分技巧的にし, プログラムが指定した「何である」の知識があれば, 自動的に「どうする」の知識が生成出来るようにしようというのである.
1.1.8 ブラックボックス抽象としての手続き
sqrtは相互に定義する手続きの組として定義したプロセスの最初の例である. sqrt-iterの定義が 再帰的(recursive)であることに注意して欲しい: つまり手続きはそれ自身を使って定義してある
分割戦略は単にプログラムを部分に分けることより重要である. 大きなプログラムがあれば, 最初の10行, 次の10行, 次の10行のように分けることは出来る. そうではなく, 各手続きは, 他の手続きを定義する時, その部品として使え, まとまった仕事が出来ることが重要だ
手続き定義は細部を隠すことが出来る
手続きの仮パラメタには, 手続き定義の中で, 仮パラメタがどんな名前を持っていても構わないという, 特別な役目がある. そういう名前を 束縛変数(bound variable)といい, 手続き定義は仮パラメタを 束縛する(bind)という. 定義の中で束縛変数名を統一的につけ替えても, 手続き定義の意味は変らない.26 変数が束縛されていなければ, 自由である(free)という. 名前が束縛されている式の範囲を 有効範囲(scope)という. 手続き定義の中では, その手続きの仮パラメタとして宣言された束縛変数の有効範囲は, その手続きの本体である
(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))
定義の入れ子をブロック構造(block structure) xを内部定義で 自由変数にする. そうすればxは外側の手続きsqrtが呼び出された時の引数から値をとる. このやり方を 静的有効範囲(lexical scoping)という
ブロック構造を出来るだけ使い, 巨大問題を, 扱える部品に分割しよう
![計算機プログラムの構造と解釈[第2版]](http://ecx.images-amazon.com/images/I/511qf4jdYjL._SL160_.jpg "計算機プログラムの構造と解釈[第2版]")
- 作者: ハロルドエイブルソン,ジュリーサスマン,ジェラルド・ジェイサスマン,Harold Abelson,Julie Sussman,Gerald Jay Sussman,和田英一
- 出版社/メーカー: 翔泳社
- 発売日: 2014/05/17
- メディア: 大型本
- この商品を含むブログ (2件) を見る
