JavaScriptでSICPを勉強する その4
「JavaScriptでSICPを勉強する その4」です。
2.1.3 データとは何か (p.51)
schemeではcar, cdr, consという3つの演算子が非常に重要な役割を果たしています。consを使って2つのオブジェクトを糊づけでき、そのオブジェクトはcar, cdrを使って取り出すことができます。schemeでのcar, cdr, consの実装を見てみましょう。
(define (cons x y) (lambda (m) (m x y))) (define (car z) (z (lambda (p q) p))) (define (cdr z) (z (lambda (p q) q)))
どうやらconsは関数を返す関数で、car, cdrで関数適用で値を取り出しているようです。JavaScriptでも実装しましょう。
function cons(x, y) { return function (m) { return m(x, y); } } function car(z) { return z( function(p, q){return p;} ); } function cdr(z) { return z( function(p, q){return q;} ); }
JavaScriptでもちゃんと動いているか確認してみます。
var x = cons(1, cons(2, 3)); // => function (m) { return m(x, y);} car(x); // => 1 cdr(x); // => function (m) { return m(x, y);} car(cdr(x)); // => 2
ちゃんと動いているように見えます。SchemeだけでなくJavaScriptでcar, cdr, consを実装することで少しは理解が深まったかもしれません。
2.2.1 並びの表現 (p.55)
car, cdr consができたので次はデータの並びlistを表現してみましょう。schemeでのlistは次のようになっています。
(list <a_1> <a_2> ... <a_n>) ;は (cons <a_1> (cons <a_2> (cons ... (cons <a_n> nil))) ;と等価です
どうやらlistはconsが入れ子になっているだけのようです。JavaSciptで配列を受け取りそれをconsを入れ子にして返す関数listとlistを配列に戻す関数toArrayをつくってみます。
function list(a, k){ if( k === undefined ) k = a.length; if( k == 0 ) return null; return cons(a[k], list(a, k-1)); } function toArray(a, res){ if( res === undefined ) res = []; if( typeof(a) == "function" ) res.push( car(a) ); if( cdr(a) == null ) return res; else return toArray(cdr(a), res); }
再帰で実現できました。listでは最初の関数呼び出しのときに配列の長さをkに代入し再帰呼び出しをする度にkの値がひとつずつ小さくなっていきます。schemeではリストの末尾にnilという値で終わりを表していますが、JavaScriptではnullで終わりを表すことにしましょう。
リスト演算 (p.57)
JavaSciriptでschemeと同じ表現でlistが実現できたので次はリストに対する演算を実装してみましょう。まずはlistの長さを返すlengthを実装します。
scheme
(define (length items) (if (null? items) 0 (+ 1 (length (cdr items)))))
function length(items) { if( null == items ) return 0; else return 1 + length(cdr(items)); } var x = list([1, 2, 3, 4]); var y = list([]); // 空のリスト length(x); // => 4 length(y); // => 0
次はリストを連結するappendを実装してみましょう。
scheme
(define (append list1 list2) (if (null? list1) list2 (cons (car list1) (append (cdr list1) list2))))
function append(list1, list2) { if( null == list1 ) return list2; else return cons(car(list1), append(cdr(list1), list2)); } var x = list([1, 2, 3, 4]); var y = list([5, [6, 7]]); var z = append(x, y); // => 4 toArray(z); // => [1, 2, 3, 4, 5, [6, 7]]
car, cdr, consはデータを表現するのに非常に強力であることがわかりました。次回はリストの写像のおはなしで「JavaScriptでSICPを勉強する その5」です。
JavaScriptでSICPを勉強する その3
「JavaScriptでSICPを勉強する その3」です。
1.3 高階手続きによる抽象 (p.31)
例えば
という計算がしたいときは関数を引数に取る関数sigmaを定義するとよいでしょう。
scheme
(define (sigma a b f) (if (> a b) 0 (sigma (f a) b sigma))) (define (f x) (* x x)) (define (g x) (* 2 x)) (sigma 1 3 f) ; => 14 (1 + 4 + 9) (sigma 1 3 g) ; => 12 (2 + 4 + 6)
function sigma(a, b, f) { if (a > b) return 0; else return sigma(a+1, b, f); } function f(x) { return x * x; } function g(x) { return 2 * x; } sigma(1, 3, f); // => 14 (1 + 4 + 9) sigma(1, 3, g); // => 12 (2 + 4 + 6)
このように関数を引数に取る関数のことを高階関数(higher-order function)といいます。高階関数は数学の世界では汎関数と呼ばれているようです。
1.3.2 lambdaを使う手続きの構築 (p.34)
schemeではlambdaは次のような書式で書きます。
(lambda (<引数の並び>) (<関数本体>))
これに対応するJavaScriptのコードは以下のようになります。
function (<引数の並び>) {<関数本体>}
lambdaを使って試しに数値を4増やして返す関数plus4というのを作ってみましょう。
(define plus4 (lambda (x) (+ x 4)))
var plus4 = function (x) {return x + 4;};
局所変数を創りだすletの使い方 (p.35)
また局所変数を使いたいときに便利なletというものがあります。書式は次のようになっています。
(let ((<変数名> <束縛する値>) (<変数名> <束縛する値>) ... (<変数名> <束縛する値>)) <本体>
束縛する変数は複数書くことができます。ちなみにletは次のシンタックスシュガー(構文糖)にすぎません。
((lambda (<変数1>...<変数n>) <本体>) <束縛する値1> ... <束縛する値n>)
例えば2点間の距離を返す関数をつくり、その中でletを使ってみましょう。
(define (dist x1 y1 x2 y2) (let ((x (- x1 x2)) (y (- y1 y2))) (sqrt (+ (* x x) (* y y))))) (dist 0 0 1 1) ; => 1.4142135623730951
今回は高階手続きによる抽象をやりました。次回はcar, cdr, consやlistのおなはしで「JavaScriptでSICPを勉強する その4」です。
JavaScriptでSICPを勉強する その2
「JavaScriptでSICPを勉強する その2」です。
1.2 手続きとその生成するプロセス (p.17)
階乗を計算する関数factorialについて考えてみましょう。
scheme
(define (factorial n) (if (= n 1) 1 (* n (factorial (- n 1)))))
function factorial(n) { if (n == 1) return 1; else return n * factorial(n); }
再帰で階乗を計算していますが、5!を計算するプロセスは以下のようになります。(演算子の順序は前置記法でなく見やすくしています)
(factorial 5) => 5 * (factorial 4) => 5 * 4 * (factorial 3) => 5 * 4 * 3 * (factorial 2) => 5 * 4 * 3 * 2 * (factorial 1) => 5 * 4 * 3 * 2 * 1 => 5 * 4 * 3 * 2 => 5 * 4 * 6 => 5 * 24 => 120
再帰呼び出しの途中では一時的に値をスタックに保持する必要があり、メモリを無駄に消費します。これを末尾再帰に書き換えてみましょう。
scheme
(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)))
function factorial(n) { return fact_iter(1, 1, n); } function fact_iter(product, counter, max_count) { if(counter > max_count) return product; else return fact_iter(counter * product, counter + 1, max_count); }
末尾再帰に書き換えた結果、5!を計算するプロセスは以下のようになりました。見ての通り再帰の途中でproductに計算途中の値が入っています。
(factorial 5) => (fact-iter 1 1 5) => (fact-iter 1 2 5) => (fact-iter 2 3 5) => (fact-iter 6 4 5) => (fact-iter 24 5 5) => (fact-iter 120 6 5)
次はフィボナッチ数を計算してみましょう。フィボナッチ数についての説明はWikipedia:フィボナッチ数にも書いてあります。最初は単純な再帰で書いてみます。
scheme
(define (fib n) (cond ((= n 0) 0) ((= n 1) 1) (else (+ (fib (- n 1)) (fib (- n 2))))))
function fib (n) { if (n == 0) return 0; else if(n == 1) return 1; else return fib(n-1) + fib(n-2); }
このような再帰で書くと計算にとても時間がかかってしまいます。例えばfib(5)を計算するときのプロセスは以下のようになります。(多少評価される順序が違うかも)
(fib 5) => ((fib 4) + (fib 3)) => (((fib 3) + (fib 2)) + ((fib 2) + (fib 1))) => ((((fib 2) + (fib 1)) + ((fib 1) + (fib 0))) + (((fib 1) + (fib 0)) + 1)) ...
同じ計算を何度もしていて非常に効率の悪い計算をしています。これを末尾再帰に書き換えてみましょう。
scheme
(define (fib n) (fib-iter 1 0 n)) (define (fib-iter a b count) (if (= count 0) b (fib-iter (+ a b) a (- count 1))))
function fib(n) { return fib_iter(1, 0, n); } function fib_iter(a, b, count) { if (count == 0) return b; else return fib_iter(a + b, a, count - 1); }
末尾再帰に書き換えた結果、(fib 5)の計算プロセスは以下のようになります。
(fib 5) => (fib-iter 1 0 5) => (fib-iter 1 1 4) => (fib-iter 2 1 3) => (fib-iter 3 2 2) => (fib-iter 5 3 1) => (fib-iter 8 5 0) => 5
再帰呼び出しするときに計算途中の値を引数としているようです。無駄な計算がなくなって効率が良くなりました。
最後にべき乗の計算をする関数を書いてみましょう。
scheme
(define (expt b n) (if (= n 0) 1 (* b (expt b (- n 1))))
function expt(b, n) { if(n == 0) return 1; else return b * expt(b, n-1); }
これも末尾再帰に書き換えてみましょう。
scheme
(define (expt b n) (expt-iter b n 1)) (define (expt-iter b counter product) (if (= counter 0) product (expt-iter b (- counter 1) (* b product))))
function expt(b, n) { return expt_iter(b, n, 1); } function expt_iter(b, counter, product) { if (counter == 0) return product; else return expt_iter(b, counter - 1, b * product); }
単純な再帰の方が簡潔に書ける場合が多いですが、一般的には末尾再帰の方が処理が早いです。いくつかの例を見てなんとなく末尾再帰が理解できた気がします。次回は高階手続きによる抽象のおはなしで「JavaScriptでSICPを勉強する その3」です。
JavaScriptでSICPを勉強する その1
「JavaScriptでSICPを勉強する その1」です。「Schemeのコードを読んでも理解できないならJavaScriptで書いたら理解できるかも！」と思い記事を書きました。schemeとJavaScriptのコードを見比べて理解を深めていきます。主に自分の理解を深めるために記事を書いているので説明が本に書いてある場合は適当に省きます。
1.1 プログラムの要素 (p.2)
schemeでの変数や関数の定義は次のようにします。
; 変数定義 (define pi 3.14159) ; 関数定義 (xの二乗を返す関数) (define (square x) (* x x))
JavaScriptでは変数や関数の定義は次のようになるでしょう。
// 変数定義 var pi = 3.14159; // 関数定義 (xの二乗を返す関数) function square(x) { return x * x; };
schemeでは演算子が前置記法になっていてC言語, C++, Java, JavaScriptなどとは見た目が全然違うものに見えるかもしれませんが、順序が違うだけで本質的には変わらない部分が多いことを理解しましょう。
1.1.6 条件式と述語 (p.9)
次にschemeでの条件分岐とJavaScriptでの条件分岐を比べてみます。
scheme
; 一般形 (if <条件式> <trueのとき評価される式> <falseのとき評価される式>) ; 例 (絶対値を返す関数) (define (abs x) (if (< x 0) (- x) x))
// 一般形 if (<条件式>) <trueのとき評価される式>; else <falseのとき評価される式>; // 例 (絶対値を返す関数) function abs (x) { if (x < 0) return -x; else return x; }
1.1.7 例：Newton法による平方根 (p.12)
schemeとJavaScriptでNewton法による平方根を求める処理を書いてみましょう。Newton法の説明は省きますが、Wikipedia:ニュートン法にも書いてあります。
; 関数sqrt-iterは推測値guessが目的値に充分近くなるまで計算を繰り返す (define (sqrt-iter guess x) (if (good-enough? guess x) guess (sqrt-iter (improve guess x) x))) ; 関数improveは推測値guessをより良い値に改善して返す (define (improve guess x) (average guess (/ x guess))) ; 関数averageは平均を返す (define (average x y) (/ (+ x y) 2)) ; 関数good-enough?は推測値guessが十分よい値になっているかどうかを返す(今回は差が0.001より小さいかどうか) (define (good-enough? guess x) (< (abs (- (square guess) x)) 0.001)) ; 関数sqrtは平方根を返す (define (sqrt x) (sqrt-iter 1.0 x)) (sqrt 9) ; => 3.00009155413138
// 関数sqrt-iterは推測値guessが目的値に充分近くなるまで計算を繰り返す function sqrt_iter(guess, x) { if (good_enough(guess, x)) return guess; else return sqrt_iter(improve(guess, x), x); } // 関数improveは推測値guessをより良い値に改善して返す function improve(guess, x) { return average(guess, x / guess); } // 関数averageは平均を返す function average(x, y) { return (x + y) / 2; } // 関数good-enoughは推測値guessが十分よい値になっているかどうかを返す(今回は差が0.001より小さいかどうか) function good_enough(guess, x) { return (abs(square(guess) - x) < 0.001); } // 関数sqrtは平方根を返す function sqrt(x) { return sqrt_iter(1.0, x); } sqrt(9); // => 3.00009155413138
なんとなくschemeではわからなかったコードでもJavaScriptだと少しは理解できたのではないでしょうか。
次回は再帰のおはなしです。「JavaScriptでSICPを勉強する その2」
JavaScriptでSICPを勉強する！
SICP(計算機プログラムの構造と解釈)という有名な本を読んでいて、私にはどうしてもschemeのコードが理解しづらかったのでJavaScriptに書き換えたら少しは理解しやすくなるのではないかと思いこの記事を書きました。
Advent Calendar Advent Calendar 10日目
この記事は Advent Calendar Advent Calendar 10日目の記事です。前の人は @daimatz さん でした。
今日は あまり知られていないけど役に立つJavascript tips Advent Calendar 2012 を紹介します。
私は個人的にJavaScriptが好きでしばしばJavaScriptのコードを書きます。JavaScriptには
- 関数をオブジェクトとして扱える
- canvasを用いてグラフィカルなものもつくることができる
- HTMLと組み合わせてインタフェースを用意するのが楽
- 最近はnode.jsを用いてサーバサイドプログラミングも可能
など興味深い特徴がたくさんあります。
しかし、JavaScriptは「型が貧弱」「処理系によって動作が大きく異なることがある」「デバッグがしづらく開発効率が悪い」など欠点も多くあります。
このアドベントカレンダーではundefined判定やデバッグテクについて書かれた記事があるのでこれらを見ることで快適なJavaScriptライフを送ることができるようになるかもしれません。
Let's JavaScript programming!
