新潟 SICP読書会第一回 手続きによる抽象の構築
優れたプログラミング言語は
- 基本式、つまり言語内でもっとも単純なもの(数字1とか)
- それらを合成する組み合わせ法 ((+ 1 1) とか)
- そうやって組み合わせたものに名前をつけて単一のものとして扱う抽象化法 (define a (+ 1 1)とか)
をもつよ。
プログラムは「データ」(処理したいもの)と「手続き」(処理するやりかた)をもってて、それらを基本式の組み合わせ、さらにそれを抽象化したもので作れるのが強力なプログラミング言語だよ。Lispとかマジそれ
式ってのを解釈系(処理系)に食わせると、処理系は式を評価するよ。基本的な手続き(*,+,-./)と括弧を使って、組み合わせすることができるよ
(* 1 2) ; => 2
(+ 1 2 3 4) ; => 10
nestもできるよ
(* (+ 1 2 3) (- 3 1)) ; => 12
define 使うと、作ったものに名前作れるよ
(define height 2)
(define width 4)
(define size (* height width))
size ; => 8
名前がつけられて後から参照できるってことは、処理系がどっかにこの対応関係を記録してるってことだね、この記録を「環境」っていうよ。
上でもなんかいろいろ組み合わたけどこれはまず
- 部分を評価する
- 一番ひだりに書かれてる演算子を残りに適用する
って形で評価されていくよ
そうやっていくと、最後には評価する必要ない単純なものにぶちあたるよ(例 : (+ (+ 3 4) (+ 1 2))の場合、この式の部分は + と (+ 3 4) と (+ 1 2)だよ。後者ふたつはまだ評価する必要があるよ。ここで(+ 1 2)を評価するとき、この式の「部分」となるのは + と 1 と 2 だよ。これらは単純な数値なので評価する必要なしだよ)
さて、上記のとおり Lisp は 基本式、組み合わせ法、抽象化法がちゃんと備わってるよ。ではここで、さらに高度な抽象化を見て行くよ。それは手続き定義だよ。define で手続きの組み合わせに名前をつけて抽象化できるよ
(define (square x) (* x x))
いわゆる関数定義だね！
定義した手続きはほかの手続きでも利用できるよ
(define (sum-of-squares a b) (+ (square a) (square b))
(sum-of-squares 1 2) => 5
便利だね！
さっきの sum_of_squares の動きを理解するには、定義を逆に展開して置き換えてみるといいよ！
sum-of-squares の定義は (define (sum-of-squares a b) (+ (square a) (square b))) だったから、(sum_of_squares 1 2) は (+ (square 1) (square 2))に置き換えられるね
(sum-of-square 1 2)
(+ (square 1) (square 2))
さらに、square の定義は (define (square x) (* x x))だったから、 (square 1) と (square 2) は それぞれ (* 1 1) と (* 2 2) に置き換えられるね
(+ (square 1) (square 2))
(+ (* 1 1) (* 2 2))
これ、実際に処理系がそういうふうに評価してるってわけじゃないからね！あくまで人間が理解するためのモデルだよ！しかもこれだけじゃ理解しきれないことが出てくるからね！いいかい、もう一度言うよ、「実際にこういう計算をしてる」ってことじゃなくて、「式の意味を人間が理解するためのモデルとしてこういう考えかたができるよ」ってだけだからね！
今まで出てきた話だと、場合によって処理分けるみたいなことができない。condとかifとか使うとできるよ。真偽値を返す式は述語って呼ぶよ
(if (述語) (真のとき評価) (偽のとき評価))
(cond ((述語) (真のときここ評価))
((述語) (真のときここ評価))
((述語) (真のときここ評価))
(else (それ以外のときここ評価)))
and とか not とか or もできるよ
(and (述語) (述語))
(or (述語) (述語))
(not (述語))
xの平方根の定義は、y >= 0 かつ y**2 = x であるような y だけれど、これは「yの値の見つけ方」についての情報はない。コンピューターに計算させるためにはこういう「平叙文(なにである)」的な形ではなくて「命令文(こうしろ)」って形にしないとだめだよ。平方根を求める例はNewton法っていうやりかたあるよ。これだと「どうやって求めるか」だからこれを使って xの平方根を求める手続き sqrt x が定義できるね
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess))
(define (sqrt-itr guess x)
(if (good-enough? guess x)
guess
(sqrt-itr (improve guess x) x)))
(define (sqrt x)
(sqrt-itr 1.0 x))
上の例で言うと、sqrt-itr の中で good-enough? とか improve とか は、ブラックボックスになってる。それが「どうやって」十分いいかどうかを判断したり「どうやって」より良い値を求めるかはわからないし、そのおかげでその実装の中のことは気にしなくていいね！うれしいね！
あと、仮引数はこの関数内にしか影響しないから、仮引数が外の世界に影響しなくていいね！これも一種のブラックボックスだね！こういう外と関係ない、内側だけの変数を「束縛変数」って言うよ、つまり、この変数はこの中の環境に「束縛されてる」んだね！束縛されてなくて外側から影響受けたり外に影響及ぼす変数は束縛されてない「自由変数」って呼ぶよ
あと、今この improve とか good-enoughとかがグローバルな環境に束縛されちゃってるけど、これってあんまりよくないよね、どうせsqrtのなかでしか使わないんだから、sqrtの中に束縛したいよね。それできるよ！！
(define (sqrt x)
(define (good-enough? guess x)
(< (abs (- (square guess) x)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess x)
(average guess (/ x guess))
(define (sqrt-itr guess x)
(if (good-enough? guess x)
guess
(sqrt-itr (improve guess x) x)))
(sqrt-itr 1.0 x))
で、いま good-enoughの内部に束縛されてるxとその外のxって同じものだから、そういうときは good-enough?の中ではxを自由変数にしてあげてもいいんだよ
(define (sqrt x)
(define (good-enough? guess)
(< (abs (- (square guess) x)) 0.001))
(define (average x y)
(/ (+ x y) 2))
(define (improve guess)
(average guess (/ x guess))
(define (sqrt-itr guess)
(if (good-enough? guess x)
guess
(sqrt-itr (improve guess) x)))
(sqrt-itr 1.0 x))
こういう、自由変数だったら一個上の環境の束縛変数探して行くみたいなのを「レキシカルスコープ」って言うよ！
今まで単純な手続きとその組み合わせ方とその抽象化の仕方を見てきたけど、じゃあこれらについてもうちょっといろいろ見て行くね
階乗を求める手続きを2パターン考えて見ようね。
(define (fact n)
(if (= n 0)
1
(* n fact(- n 1))))
(define (fact n)
(define (fact-itr current counter max-count)
(if (> counter max_count)
current
(fact-itr (* current counter) (+ counter 1) max-count))))
(fact-itr 1 1 n)
上のやつは、
(fact 10)
(* 10 (fact 9))
(* 10 (* 9 (fact 8))
(* 10 (* 9 (* 8 (fact 7)))
下のやつは
fact 5
fact-itr 1 1 5
fact-itr 1 2 5
fact-itr 2 3 5
fact-itr 6 4 5
fact-itr 24 5 5
fact-itr 120 6 5
120
みたいに展開されるね！上みたいな、進めば進むほど処理系が覚えておかないといけない情報が増える形のやつを線形再帰、下みたいな、情報を書き換えつつ進んでいくやつを線形反復と言うよ。線形再帰は覚えておかないといけない情報が増えるから空間効率が悪いね。でも線形反復は空間効率いいよ！ちなみに scheme は賢いから、線形再帰で書いてても処理系が線形反復の形でやってくれてうれしいよ。すごいね！
再帰構造は上みたいに再帰するのがいっこみたいなやつじゃなくて、2つ以上に分かれて再帰するみたいなのもあるよ。たとえば フィボナッチ数を求めるやつ。呼びだしのスタックを見るとこれは木構造になるね！
(define (fib n)
(cond
((= n 0)(0))
((= n 1)(1))
(else (+ (fib (- n 1)) (fib (- n 2))))))
ただこの書き方は直感的だけど、ひどく効率が悪いね。空間的には再帰の深さ分だけしか資源食わないけど、木のノードの部分全部計算するからね！アホやね！じゃあ再帰の形じゃなくて反復の形で書いてみよう！
(define (fib n)
(define (fib-itr a b count)
(if (= count 0)
b
(fib-itr (+ a b) a (- count 1))))
これでnが増えても計算量はリニアにしか増えなくなったね！でもコードは直感的じゃなくなったね！そんな感じで、再帰の形にするとコードが直感的に書けて書きやすいし読みやすいけど、反復の形にするのはちょっと大変だね！一長一短とはこのことだ！
上に見たみたいに、同じものを求めようとしても、やり方次第で計算量とか空間効率ってのはだいぶ変わってくるんだね！こういう違いを見積もるための、「増加の程度」って考え方があるよ！ n を問題の大きさ(sortならばsortされる要素の数、素数かどうかを判断だったらその数の大きさなど)とするとき、その問題を解くために必要な計算資源を R(n) として、 k1 * f(n) < R(n) < k2 * f(n) （ただしk1,k2はnと独立の正の定数）となるようなfがあるとき、R(n)の計算量の増加の程度は Θ(f(n)) であると言うよ。なんだそれ！よくわかんない！
まあ要するにこれって n が増えたときに、どんな形で計算量が増えて行くかってことを言っているんだね。
例を見ようね。
線形再帰な形の階乗計算だと、計算の量は n が増えれば リニアに n だけ増えて行くし、覚えておかないといけない情報も リニアに n だけ増えて行くね。だからこれは計算量、空間ともにΘ(n)なプロセスになるよ。一方で、線形反復な形だと計算量は リニアに n だけ増えて行くけど、覚えておかないといけない情報は増えないからΘ(1)だね。すごい！効率いいね！
こういうの、リニアに増えて行くΘ(n)、増えないΘ(1)以外にも、例えば指数関数的に増えて行くやつとか対数的に増えて行く(大きくなってもあまり増えない)やつとかあるよ、例を見ようね。
bのn乗を計算する手続きを考えようね。
(define (expt b n)
(if (= n 0)
1
(* b (expt b (- n 1)))))
これは b ^ n == n * (b ^ (n -1)) という定義をそのまま書きくだした直感的なやつだね、線形再帰のパターンだ。さっき見たようにnが増えれば計算量は Θ(n)、空間もΘ(n)で増えて行くね
(define (expt b n)
(define (expt-itr current counter)
(if (= 0 counter)
current
(expt-itr (* b current) (- counter 1))))
(expt-itr 1 n))
今度は線形反復のパターンだね。計算量はΘ(n)、空間はΘ(1)で増えて行くよ。
じゃあここで、b ^ 8 を ( b ( b ( b ( b ( b ( b ( b ( b ) ) ) ) ) ) ) ) って考えるんじゃなくて、((b b) (b b)) ((b b) (b b)) って考えてみよう。半分ずつに分けて行く感じだね！
(define (expt b n)
(define (even? n) (= (remainder n 2) 0))
(cond
((= 0 n) 1)
((even? n) (square (expt b (/ n 2))))
(else (* b (expt b (- n 1)))))
これだと、nが2倍になっても計算量は1回しか増えないよね。つまりΘ(log n)の増加量(低は2)になってるよ！すごいね！効率いいね！
増加の程度を見る例が書いてあるだけだから割愛！
これも増加の程度を見る例が書いてあるだけだから割愛！
フェルマーの小定理っていうの使ってある数が素数かどうかをチェックしてみよう。
n を素数、a を正の整数(ただし a < n)とすると、(a ^ n) % n == a % n である
ってやつだね！ちなみに、以下のこともしられてるよ！
nが素数じゃない場合、ほとんどの場合は (a ^ n) % n != a % n である
これ、なにを意味するかっていうと、任意の n と a を与えたときに (a ^ n) % n != a % n だったら、それは ** 確実に ** 素数ではないし、そうではなかったら ** ほとんどのばあい ** 素数だってことだね！
さっき見たようにべき乗の計算は Θ(log n) で実装できるから、手続きは Θ(log n) で書けるね。
で、これを利用すればΘ(log n)で、「まあたまに間違うけどほぼ間違えない素数チェック」な手続きが書けるよ。こういうのは確率的アルゴリズムって呼ばれてて、いろんな研究とか応用がなされているんだ。すごいね！おもしろいね！
さて、今までは手続きの組み合わせを抽象化する話を見てきたんだけど、このパラメータに手続きをわたしたり、あるいは結果として手続きを返す手続きを作ったりすることができるんだ。で、こういうのを高階手続きと呼ぶよ。言葉だけで言われてもわけわかんないね、例を見ようね！
たとえばこういう三つの手続きがあったとするよ。
; aからbまでを足し合わせる
(define (sum-integers a b)
(if (> a b)
0
(+ a (sum-integers (+ a 1) b))))
; aからbまでの整数の三乗の和を計算する
(define (sum-cubes a b)
(if (> a b)
0
(+ (cube a) (sum-cubes (+ a 1) b))))
; (1 / (1 * 3)) + (1 / (5 * 7)) + (1 / (9 * 11)) … を計算する
(define (pi-sum a b)
(if (> a b)
0
(+ (/ 1 (* a (+ a 2))) (pi-sum (a * 4) b))))
;ちょっと複雑なので書き直す
(define (helper a)
(/ 1 (* a (+ a 2))))
(define (pi-sum a b)
(if (> a b)
0
(+ (hepler a) (pi-sum (a + 4) b))))
これらには共通のパターンがあるね。
(define (なんちゃら a b)
(if (> a b)
0
(+ (aになんかする手続き) (再帰する (次のaを求める手続き) b))
これつまり、aになんかする手続き とか 次のaを求める手続きってのを外から与えてあげられるようにすれば、これらの三つはより抽象化できるってことだよね。
; termがaになんかするための手続き,nextが次のaを求めるための手続き
(define (sum term a next b)
(if (> a b)
0
(+ (term a) (sum term (next a) next b))))
termとnextに渡す手続きを作ればいろいろできるね。
(define (id n) n)
(define (cube n) (* n n n))
(define (inc n) (+ n 1))
(define (double n) (* n 2))
(sum id 1 inc 10) ; 1から10まで足す手続き
(sum cube 1 double 10) ; (1 ^ 3) + (2 ^ 3) + (4 ^ 3) + (8 ^ 3) を計算
sumを使ってあたらしい手続きを定義することだって可能だよ。
(define (sum-cubes a b)
(define (inc n) (+ n 1))
(define (cube n) (* n n n))
(sum cube a inc b))
便利だ！
さっきわざわざ cube とか inc とかを define したけど、べつにこれ引数に渡したいだけだし、他で使う予定ないから、名前ある必要ないよね。そういうときはlambdaっての使うといいよ。
(lambda (引数) (内容))
これで（引数）を取る (内容) な手続きを作成することができるよ。これを使えばさっきのsum-cubesは
(define (sum-cubes a b)
(sum (lambda (n) (* n n n))
a
(lambda (n) (+ n 1))
b))
みたいに書けるよ。JavaScriptで言うところの匿名関数だね！lambdaを使うと手続きの定義を別の書き方ですることもできるよ。
(define double (lambda (n) (* n 2)))
lambda で作った手続きに double という名前をつけてるね。
function double(n) {return n * 2}
var double = function(n){return n * 2};
みたいなもんだね。
こういうこともできるよ。
((lambda (a b c) (+ a b c)) 1 2 3) ; => 6
JSの即時関数みたいなもんだね。
(function(a, b, c){return a + b + c;})(1, 2, 3)
lambdaを使うとうれしいことのもうひとつに、変数のスコープをちっちゃくできるっていうこともあるよ。lambdaの引数はlambdaの中の環境に束縛されているから、lambdaの外には出て行かないってことだね。
;a = (1 + xy)
;b = (1 - y)
;f(x,y) = (a ^ 2 * x) + (b * x) + (a * b)
(define (f x y)
((lambda (a b)
(+ (* a a x)
(* b x)
(* a b)))
(+ 1 (* x y))
(- 1 y)))
JSで書くとこうだね
function f(x, y) {
(function(a, b){
return (a * a * x) + (b * x) + (a * b)
})((1 + (x * y)), (1 - y));
}
このイディオム、JSでグローバルオブジェクトを抽象化して捕まえるのに使われてるよね
(function(global){
//global は 環境によってwindowだったりglobalだったりする
})(this)
で、これだとちょっと読みにくいから、let っていう syntax sugar が用意されてるよ！
(let ((var (exp))
(var (exp))
(var (exp)))
(body))
と書くと、
((lambda (var var var)(body))
(exp) (exp) (exp))
と同じ意味になるよ。どの var にどの exp が束縛されてるか読みやすくていいね！
上のやつを使った例がふたつ出てるだけだから割愛！
今までは引数として lambda で作った手続きを渡せるし、 lambda で作った手続きに define で名前をつけられるよ！って話したけど、それ以外にも、lambda で作った手続きを値として返すことだってできるよ！
(define (average-dump f)
(lambda (x) (average x (f x))))
(define average-of-x-and-cube
(average-dump (lambda (x) (* x x x))))
(average-of-x-and-cude 5)
;
; (average 5 ((lambda (x) (* x x x)) 5)))
; (average 5 125)
; 65
これは、fを渡すと、 f(x)と xの平均を求める手続きを返すっていう手続きだね！JSで書くとこう
function average-dump(f){
return function(x){
return (x + f(x)) / 2;
};
}
JSって読みやすいね！
いろんな例が書いてあるけどただの例なので割愛！
度の過ぎた抽象化はよくないけど、「抽象化できる」、「それを理解してる」ってのは、すごく大切なことだよ！高階手続きがあると、それがないのに比べるとずっと抽象度を高くできるね！
- 変数として名前がつけられる
- 手続きに引数として渡せる
- 手続きの結果として返せる
- データ構造に組み込める
ような要素を一般に「第一級」って言うんだけど、Lispにおいて手続きってのはこれまで見たように第一級なんだ！めっちょ便利だね！！
- 括弧がうざい
- 例題に数学を使う意味がわからない。抽象化できてうれしいね！って話を抽象的な題材でやるのアホだと思う
- 手続きがデータと同じく第一級オブジェクトであることで、難しいけどパワフルな抽象化ができるって例たくさんあって「まあ、強力ね！」って思った。が、まあこれはるっびーーーなひととか Perl なひととか JS なひとにとっては身近なことっぽい感じする。 sub{} 最高ッ！