takatoh's blog – Learning programming languages.
WordPress で LaTeX の数式を表示できるようにするプラグインはいくつかあるようだけど、Easy WP LaTeX ってのが簡単そうで評価も高いようだったのでインストールしてみた。
cf. WordPressでTeX数式が使用できるプラグイン「Easy WP LaTeX」 ― レンサバ比較のカルマ
インストールは簡単。
これでOK。
設定は、WordPress のメニュー → 「設定」 → 「Easy WP LaTeX」 で、色と大きさ、記法の設定ができる。
試しに表示してみると、
[math](a+b)^2 = a^2 + b^2 + 2ab[/math]
LaTeX のソースはこれ。
(a+b)^2 = a^2 + b^2 + 2ab
これも東大の Scheme演習のページから。
cf. Scheme演習 第２回
フィボナッチ関数の定義（fib(0)=0、fib(1)=1 …）が載っていて、
この定義をそのまま使って関数 (fib1 n) を作れ。
(define fib1
(lambda (n)
(cond
((= n 0) 0)
((= n 1) 1)
(else (+ (fib1 (- n 1)) (fib1 (- n 2)))))))
gosh> (load "fib1") #t gosh> (fib1 30) 832040 gosh> (fib1 40) 102334155
末尾再帰を使って、n に対して線形の時間で求める関数 (fib2 n) を作れ。その際、ブロック構造を用いて、トップレベルに定義する関数は fib2 のみとせよ。
(define fib2
(lambda (n)
(define fib-iter
(lambda (m a b)
(if (zero? m)
a
(fib-iter (- m 1) b (+ a b)))))
(fib-iter n 0 1)))
gosh> (load "fib2") #t gosh> (fib2 40) 102334155
ふたつのプログラムを同じ引数で実行してみて、時間を比較せよ。さらにその時間の違いの理由について考察せよ。
厳密には時間を計っていないけど、引数が 40 の場合 fib1 は数十秒かかるのに対して、fib2 は一瞬で結果が得られる。理由は簡単、fib1 では再帰のたびに同じ引数に対する計算を何度も行っているのに対して、fib2 では同じ引数に対する計算は1度ですんでいるから。
「Scheme手習い」9章は問答についていくのが大変なので、今日はちょっとそこから離れて関数の練習。
東大のScheme演習のページから。
cf. Scheme演習 第１回
問２
5つの整数を引数として受け取り、そのうち偶数が奇数より多い場合は #t を返し、奇数が偶数より多い場合は #f を返す述語 even>odd? を定義せよ。当然、いろいろな定義の仕方がある。
いろいろな定義の仕方がある、っていうんだから3つくらいは挙げなきゃな。
最初に思いついたのがこれ。
(define even>odd?
(lambda (a b c d e)
(> (length (filter even? (list a b c d e))) 2)))
(print (even>odd? 1 2 3 4 5))
(print (even>odd? 2 -3 4 5 -6))
^o^ > gosh even_gt_odd1.scm #f #t
次にこれ。上のやつの (length (filter even? ...)) の代わりに再帰関数で偶数の数を数えている。
(define even>odd?
(lambda (a b c d e)
(define evens
(lambda (lis)
(cond
((null? lis) 0)
((even? (car lis)) (+ 1 (evens (cdr lis))))
(else (evens (cdr lis))))))
(> (evens (list a b c d e)) 2)))
(print (even>odd? 1 2 3 4 5))
(print (even>odd? 2 -3 4 5 -6))
^o^ > gosh even_gt_odd2.scm #f #t
3つ目、前に作った evens-and-odds を使う。
(define even>odd?
(lambda (a b c d e)
(define evens-and-odds
(lambda (lis co)
(cond
((null? lis) (co '() '()))
((even? (car lis))
(evens-and-odds (cdr lis) (lambda (e o) (co (cons (car lis) e) o))))
(else
(evens-and-odds (cdr lis) (lambda (e o) (co e (cons (car lis) o))))))))
(define friend
(lambda (e o)
(> (length e) (length o))))
(evens-and-odds (list a b c d e) friend)))
(print (even>odd? 1 2 3 4 5))
(print (even>odd? 2 -3 4 5 -6))
^o^ > gosh even_gt_odd3.scm #f #t
今度はアッカーマン関数だ。Wikipedia の解説を読んでもよくわからないんだけど、引数が大きくなると爆発的に計算量が大きくなるらしい。
(use mymodule)
(define A
(lambda (n m)
(cond
((zero? n) (add1 m))
((zero? m) (A (sub1 n) 1))
(else (A (sub1 n) (A n (sub1 m)))))))
(print (A 1 0))
(print (A 1 1))
(print (A 2 2))
^o^ > gosh -I. A.scm 2 3 7
といっても、上の例ではすぐに計算が終わって値が返ってくる。ところが (A 4 3) を計算させてみたところ、一晩かかっても終わらなかった。問答では「現実的な問題として、答は得られないでしょう。」と書いてある。
それでもこれは全関数らしい。
こんな関数 C が出てきた。
(define C
(lambda (n)
(cond
((one? n) 1)
(else
((even? n) (C (o/ n 2)))
(else (C (add1 (o* 3 n))))))))
これはコラッツの問題だ。
問答の答には「0に対しては値を持ちませんが、それ以外の引数に対して全関数であるかどうかは誰も知りません。ありがとう、Lother Collatz（1910～1990）。」と書いてある。もしコラッツの予想が正しければ全関数だということになるけど、まだ証明されていない。Wikipedia によれば、3 × 2 の53乗までは反例がないことが確かめられているとのこと。
今度はわかるぞ。
shuffle は align と似ているけど、7章で出てきた revpair を使う。
(use mymodule)
(define revpair
(lambda (pair)
(build (second pair) (first pair))))
(define shuffle
(lambda (pora)
(cond
((atom? pora) pora)
((a-pair? (first pora)) (shuffle (revpair pora)))
(else (build (first pora) (shuffle (second pora)))))))
(print (shuffle '(a (b c))))
(print (shuffle '(a b)))
^o^ > gosh -I. shuffle.scm (a (b c)) (a b)
うまく動いているようだ。ということは全関数なんだろうか。
ここで、(shuffle '((a b) (c d))) の値を求めてみる。引数の第1要素がペアなので、cond の2番目に当たる。すると (shuffle (revpair '((a b) (c d)))) と再帰してこれは (shuffle '((c d) (a b))) に同じ。さらに進めるとまた cond の2番目にあたり、(shuffle (revpair '((c d) (a b)))) となり、これは (shuffle '((a b) (c d))) と同じになる。つまり、最初と同じになってしまう。
というわけで、shuffle は引数によっては停止しない部分関数ということになる。
うーん、問答についていけなくなった。
順を追っていこう。
まずは関数 shift。これは、ペアのペアを引数にとって、ペアの第1要素の第2要素を、ペアの第2要素に移し変える（ややこしいな）。
(use mymodule)
(define shift
(lambda (pair)
(build (first (first pair)) (build (second (first pair)) (second pair)))))
(print (shift '((a b) c)))
(print (shift '((a b) (c d))))
^o^ > gosh -I. shift.scm (a (b c)) (a (b (c d)))
うん、ここまではOK。
次、align。この関数は、
(use mymodule)
(define shift
(lambda (pair)
(build (first (first pair)) (build (second (first pair)) (second pair)))))
(define align
(lambda (para)
(cond
((atom? para) para)
((a-pair? (first para))
(align (shift para)))
(else
(build (first para) (align (second para)))))))
(print (align 'a))
(print (align '(a (b c d))))
(print (align '((a b) (c d))))
(print (align '((a b c) (d e f))))
^o^ > gosh -I. align.scm a (a (b c)) (a (b (c d))) ((a b c) (d e))
まだ大丈夫、これもわかる。
この align は前回のエントリに出てきた keep-looking と共通するところがあって、それはどちらの関数も引数を変更して再帰するけど、その変更によってゴールに近づいている保証がないことだそう。
ここで問答は aling の cond の2つ目の行に注目する。(arign (shift para)) というふうに再帰しているけど、その引数はもとの引数の一部ではなく、第7の戒律に反しているという。確かに shift はペアの要素を並べ替えるだけなので、一部ではない。言い換えると新たな引数にはもとの引数と同じ数のアトムが含まれている。
(use mymodule)
(define shift
(lambda (pair)
(build (first (first pair)) (build (second (first pair)) (second pair)))))
(define length*
(lambda (para)
(cond
((atom? para) 1)
(else (o+ (length* (first para)) (length* (second para)))))))
(print (length* '((a b) c)))
(print (length* (shift '((a b) c))))
^o^ > gosh -I. length_star.scm 3 3
まあ、確かめるまでもなく同じになる。
さて、わからなくなるのはここからだ。align を再帰する際に、ペアの第1要素はより簡単になっているけど第2要素はより複雑になっているという。確かに shift によってそうなっている。だけど、「引数の長さを決めるのに length* は間違った関数ではないでしょうか。」「もっとよい関数では、第1要素にもっと注意を払わなければいけません。」とはどういうことだろう。「少なくとも２ばいは必要です。」とは？
もっとよい関数として weight* が出てくる。
(use mymodule)
(define shift
(lambda (pair)
(build (first (first pair)) (build (second (first pair)) (second pair)))))
(define weight*
(lambda (pora)
(cond
((atom? pora) 1)
(else (o+ (o* (weight* (first pora)) 2) (weight* (second pora)))))))
(print (weight* '((a b) c)))
(print (weight* (shift '((a b) c))))
^o^ > gosh -I. weight_star.scm 7 5
weight* の動作自体はわかる。第1要素の数に2を書けることによって重み付けをしている。結果、shift するとアトムが第1要素から第2要素に移動する分だけ値が小さくなるわけだ。
で、これがなぜ次の問答につながるのかがわからない。
「align は部分関数ですか。」「いいえ。すべての引数に対して値を持ちます。」
うーん、誰か解説してほしい･･････
今日から9章。
次のような関数 looking が出てきた。
(use mymodule)
(define pick
(lambda (n lat)
(cond
((zero? (sub1 n)) (car lat))
(else (pick (sub1 n) (cdr lat))))))
(define keep-looking
(lambda (a sorn lat)
(cond
((number? sorn) (keep-looking a (pick sorn lat) lat))
(else (eq? sorn a)))))
(define looking
(lambda (a lat)
(keep-looking a (pick 1 lat) lat)))
(print (looking 'caviar '(6 2 4 caviar 5 7 3)))
(print (looking 'caviar '(6 2 grits caviar 5 7 3)))
この関数 looking は次のように動作する。まず、引数 lat の1番目の要素を見て、それが数 n なら今度はn番目の要素を見る。そしてそれが数ならまた同じように繰り返す。最終的に数でないアトムに行き当たったとき、それが引数 a と eq? なら #t、そうでないなら #f を返す。
実行してみよう。
^o^ > gosh -I. looking.scm #t #f
最初の例では、6 → 7 → 3 → 4 → caviar となって無事 caviar が見つかるので #t が返っている。一方、2つ目の例では、6 → 7 → 3 → grits となって caviar が見つからないので #f が返っている。
動作そのもの以外に注目するところがある。今まで出てきた関数はすべて lat の部分に対して再帰してきた。ところが looking は lat そのものに対して再帰している。これを不自然な再帰というらしい。
さて、この looking はどんなときにも答を返すだろうか。上の2つの例ではどちらも答が返っているが、たとえば、(looking 'caviar '(7 1 2 caviar 5 6 3)) がどうやって動くか見てみると、
7 → 3 → 2 → 1 → 7 → 3 → 2 → 1 → 7 → … となって数でないアトムにたどり着かない。言い換えると looking は停止しない。これはプログラムの停止性の問題だ。どうやら9章のテーマはこれらしい。
さて、この looking のような関数を「部分関数」、今まで出てきたような関数を「全関数」というらしい。
次に eternity という関数が出てきた。
(define eternity
(lambda (x)
(eternity x)))
この関数はどんな引数が与えられても停止しない。eternity は最も部分的な関数だと書いてある。
うーん、9章にはいって難しげになってきた。
8章では収集子関数といっていたけど、「継続（continuation）」というほうが一般的みたいだ。この、継続を関数として再帰するスタイルを「継続渡しスタイル（Continuation Passing Style、CPS）と呼ぶみたい。
で、簡単な例で練習。この関数 evens-and-odds は、与えられた数のリストから、偶数だけのリストと奇数だけのリストを作る。最後に friend がリストのペアにして返している。
(define evens-and-odds
(lambda (l co)
(cond
((null? l) (co (quote ()) (quote ())))
((even? (car l)) (evens-and-odds (cdr l)
(lambda (e o) (co (cons (car l) e) o))))
(else (evens-and-odds (cdr l) (lambda (e o) (co e (cons (car l) o))))))))
(define friend
(lambda (x y)
(cons x (cons y (quote ())))))
(print (evens-and-odds '(1 2 3 4 5 6 7 8 9 10) friend))
^o^ > gosh evens-and-odds.scm ((2 4 6 8 10) (1 3 5 7 9))
うん、うまくいった。
関数 evens-only* は入れ子になった数のリストからすべての奇数を削除する。「簡単な練習でしょう」なんて書いてあるので、今度も答を見ないで書いてみる。ちなみに、偶数であることを判定する even? の定義は質問の中で提示されている。
(use mymodule)
(define even?
(lambda (n)
(o= (o* (o/ n 2) 2) n)))
(define evens-only*
(lambda (l)
(cond
((null? l) (quote ()))
((atom? (car l))
(cond
((even? (car l)) (cons (car l) (evens-only* (cdr l))))
(else (evens-only* (cdr l)))))
(else
(cons (evens-only* (car l)) (evens-only* (cdr l)))))))
(print (evens-only* '((9 1 2 8) 3 10 ((9 9) 7 6) 2)))
^o^ > gosh -I. evens-only_star.scm ((2 8) 10 (() 6) 2)
うん、簡単。
こっちが本題。関数 evens-only*&co は、引数から奇数を削除して偶数だけの入れ子のリストを作る一方、同時に引数中の偶数の積と奇数の和を計算する関数。概要が示されているので、それをもとに書いてみよう･･････と思ったけど、最後の else の再帰をどうすればわからなくて、結局答を見て写経した。
(use mymodule)
(define even?
(lambda (n)
(o= (o* (o/ n 2) 2) n)))
(define evens-only*&co
(lambda (l col)
(cond
((null? l) (col (quote ()) 1 0))
((atom? (car l))
(cond
((even? (car l)) (evens-only*&co (cdr l)
(lambda (newl p s) (col (cons (car l) newl) (o* (car l) p) s))))
(else (evens-only*&co (cdr l)
(lambda (newl p s) (col newl p (o+ (car l) s)))))))
(else
(evens-only*&co (car l)
(lambda (al ap as)
(evens-only*&co (cdr l)
(lambda (dl dp ds)
(col (cons al dl) (o* ap dp) (o+ as ds))))))))))
(define the-last-friend
(lambda (newl product sum)
(cons sum (cons product newl))))
(print (evens-only*&co '((9 1 2 8) 3 10 ((9 9) 7 6) 2) the-last-friend))
最後の else の再帰は、まず (car l) について evens-only*&co を再帰してその収集子の中でさらに (cdr l) について再帰している。(car l) についての収集子の引数 al、ap、ps は (car l) のなかの偶数のリスト、偶数の積、奇数の和。それから (cdr l) についての収集子の引数 dl、dp、ds は (cdr l) のなかの偶数のリスト、偶数の積、奇数の和だ。そして最後にリストは cons、積は o*、和は o+ をそれぞれ適用しているわけだ。ああ、なんてややこしいんだ。
実行結果：
^o^ > gosh -I. evens-only_star_and_co.scm (38 1920 (2 8) 10 (() 6) 2)
はあ、なんとかできた。
これで8章も終わり。