トラックバックが使えないじゃないの・・・

bloggerって、トラックバック使えないのね・・・

というわけで、はてなにお引越し。

ここです。

oicawaでアカウントとろうとしたら、既にいるって。
これ、ひょっとしたらむか～しはてなブックマーク使おうとして過去の俺が取ったやつかもしれんのだが、
パスワードが思い出せないので、
当時のアカウント取得時にはてなから送信されてきたメールは・・・と思ったら、
確か当時のメインで使ってたメールがyahooで、
ソフトバンクがyahooじゃぱん買収してから、
「日本人を逆差別するような企業のサービスなんか使うかボケ」と思って、
やっとの思いで手に入れたGoogleに全てのサービスをお引越ししたので、
パスワードとかさっぱり思い出せん。

諦めて新しいアカウント作った。

「awacio」

－

SchemeShellが普及すればよかったのに。

Windowsのバッチ処理のfor文なるものを初めて見て思ったこと。

こいつはファイルの操作が簡単にできるという意味で、UNIXにけるシェルスクリプトに相当する位置づけだと思う。
（機能的には全く追随できてないと思うけど）

どちらもファイル操作を簡単に済ますための概念があるように見え、
forで取得したモノを取り出すためにはforの構文で何ができるかを知る必要がある。
ま、これは別にbatでもshellscriptでも、他の言語でも多分そうだ。

だけど、Lisp系なら取り出したものは全てS式だ。
Gaucheならリストの中身はインタラクティブに見ることができるから、
ちょっと試してデータ構造を確認することもできる。
あとは「いつものように」carやcdr使って処理できる。

（って、ここまで書いてて、batでも同じようにDOSコマンドでやりゃできんじゃね？と思ったが、
　多分「表示用のフォーマットで出力される」から、for文で取り出した「データ構造」はわからんな。）

で、何が言いたいかというと、基本データ型が、あらゆるデータ構造を表現する万能なデータ型だったら、その問題領域合わせてその言語を適用できるから、楽だろうになぁと思ったということ。

リストなら、ファイルシステムで現在主流のツリー構造を表現するのに何の苦もないし、
それを統括的に処理するcarやcdrを知ってればとりあえず何でもできるわけで。

ま、でもそれ（carとかcdrとかでいちいち記述する手間）が面倒になるから、
WindowsのバッチやUNIXのシェルスクリプトの存在意義があるのか。
（但し、Windowsのバッチ処理＜＜＜＜越えられない壁＜＜＜＜シェルスクリプト）
あと、Lisp/Schemeのカッコだらけのコード。
初見での精神的敷居の高さはどうしても否定できないわなぁ。俺自身そうだったし。

それにしても、MonaOSのひげぽんさんがシェルをSchemeにしたのはこういうことも考えてなのかなぁと思った。
ご本人にお聞きしてみたいなぁ。

－

SICP 練習問題 1.21 （最少序数を求める）

ただ実行するだけ。


【問題】
smallest-divisor 手続きを使い、次の数の最少序数を見つけよ：
199, 1999, 19999


【解答】
まずは、セクションで定義してた関数群を再掲。これを踏まえて。

;最少の序数を求める
(define (smallest-divisor n)
  (find-divisor n 2))

;除数を求める処理
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n)
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

;除数かどうかの判別処理
(define (divides? a b)
  (= (remainder b a) 0))

で、実行すると、

gosh> (smallest-divisor 199)
199
gosh> (smallest-divisor 1999)
1999
gosh> (smallest-divisor 19999)
7
gosh> 

こんな感じ。なので、答えは、


199 の最少除数は 199
1999 の最少除数は 1999
19999 の最少除数は 7


となります。


－

SICP § 1.2.6 素数性のテスト（その２）

あんまり数学にかかずらわって本来の目的が遂行されないのもアレなので、
例のmodulo演算の展開は「そういうもの」として進むことにしました。

つーわけでコレです。

;ある数のべき乗を法とする剰余を求める関数
(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

;おまけ
;実行するときに定義されていないと動かないので一応。
(define (square x)
  (* x x))

で、次に

;Fermatテスト関数
(define (fermat-test n)
  (define (try-it a)
    (= (expmod a n n) a))
  (try-it (+ 1 (random-integer (- n 1)))))

更に、

;Fermatテスト関数を指定回数実行する関数
(define (fast-prime? n times)
  (cond ((= times 0) #t)
        ((fermat-test n) (fast-prime? n (- times 1)))
        (else #f)))

実行結果はコレ。

gosh> (map (lambda (x) (cons x (fast-prime? x 10))) (iota 100 2))
((2 . #t) (3 . #t) (4 . #f) (5 . #t) (6 . #t) (7 . #t) (8 . #f) (9 . #f) (10 . #f)
(11 . #t) (12 . #f) (13 . #t) (14 . #f) (15 . #f) (16 . #f) (17 . #t) (18 . #f) (19 . #t) (20 . #f) 
(21 . #f) (22 . #f) (23 . #t) (24 . #f) (25 . #f) (26 . #f) (27 . #f) (28 . #f) (29 . #t) (30 . #f) 
(31 . #t) (32 . #f) (33 . #f) (34 . #f) (35 . #f) (36 . #f) (37 . #t) (38 . #f) (39 . #f) (40 . #f) 
(41 . #t) (42 . #f) (43 . #t) (44 . #f) (45 . #f) (46 . #f) (47 . #t) (48 . #f) (49 . #f) (50 . #f) 
(51 . #f) (52 . #f) (53 . #t) (54 . #f) (55 . #f) (56 . #f) (57 . #f) (58 . #f) (59 . #t) (60 . #f) 
(61 . #t) (62 . #f) (63 . #f) (64 . #f) (65 . #f) (66 . #f) (67 . #t) (68 . #f) (69 . #f) (70 . #f) 
(71 . #t) (72 . #f) (73 . #t) (74 . #f) (75 . #f) (76 . #f) (77 . #f) (78 . #f) (79 . #t) (80 . #f) 
(81 . #f) (82 . #f) (83 . #t) (84 . #f) (85 . #f) (86 . #f) (87 . #f) (88 . #f) (89 . #t) (90 . #f) 
(91 . #f) (92 . #f) (93 . #f) (94 . #f) (95 . #f) (96 . #f) (97 . #t) (98 . #f) (99 . #f) (100 . #f) (101 . #t))
gosh> 

・・・消化不良ですよ。


－

SICP § 1.2.6 素数性のテスト

いや～、わからねぇwww
まだこのセクション理解しきれてないので、以下、途中経過だけ書いておきます。



■除数の探索

覚えていますか素因数分解。「素数^n」の表記を使って自然数を分解していくアレです。
割ることができる素数が見つからない場合、その数は素数って言えるとか言えないとか。（どっちだよ。）

さて、この素因数分解してるときどうやって「これ以上割りきれる数はない」と判断していたか覚えてます？

例えば 131 という数字。

　
 2・・・ 2 × 65 +  1　ダメ。
 3・・・ 3 × 43 +  2　ダメ。
 5・・・ 5 × 26 +  1　ダメ。
 7・・・ 7 × 18 +  5　ダメ。
11・・・11 × 11 + 10　ダメ。
13・・・13 × 10 +  1　ダメ。

13でそれ以上計算するのやめますよね。
なんでここでやめることができるかというと、これ以上大きな値で探査しても、そのペアになる値はそれまで探査してきた小さい値、2 ～ 11 の範囲の数の再評価になってしまい、意味がないから。

だから、探査する値の２乗が、素数かどうか調べている数よりも大きくなった時点で打ちきることができるわけです。

11^2 = 121 < 131
13^2 = 169 > 131

それを踏まえて、この条件を終了条件とすると、素数を求める処理は次のように記述できます。

;呼び出すだけ
(define (smallest-divisor n)
  (find-divisor n 2))

;除数を求める処理
(define (find-divisor n test-divisor)
  (cond ((> (square test-divisor) n) n) ;これが上の終了条件。
        ((divides? test-divisor n) test-divisor)
        (else (find-divisor n (+ test-divisor 1)))))

;除数かどうかの判別処理
(define (divides? a b)
  (= (remainder b a) 0))

;素数かどうか判別する処理
(define (prime? n)
  (= n (smallest-divisor n)))

これはものすご～く素直な素数チェックのロジックなので得に問題なく理解できました。



■Fermatテスト

このセクション、読んだだけではさっぱり理解できないので、写経しながら自分の理解度を記述しながら進めてみます。

『Fermatの小定理』
n を素数、a を n より小さい任意の正の整数とすると、a の n 乗は n を法として a と合同である。

いや～、読むだけだとさっぱりわからん。一つ一つ順番に見ていきます。
まず登場人物の関係を表してみます。
実際の定理の文言を整理すると、こんな感じ？

n: 素数
a: a < n な自然数
a^n ≡ a (※nを法とする）

で、「法」ってなによ？という部分が、その次のカッコ内の記述にある感じ？

（二つの数は、両者を n で割った時、同じ剰余を持てば、n を法として合同という。
　数 a を n で割った剰余を、「n を法とした a の剰余」あるいは単に、
　「n を法とした a」（a modulo n)と言う。）

この部分はFermatの小定理とは無関係で、あくまで「○○を法とした△△」という表現についての説明だと思います。
だから、文中で出てくる n は、「Fermatの小定理の n」とは全然無関係な数だと考えるべきでしょう。
「○○を法とした△△」という表現を自分の脳内で道具として利用できるようにするには、この表現を見たときにすぐにイメージができるようにしておく必要があります。
なので、実はこの部分を理解するのが最優先事項だと思います。俺的には。
というわけで噛み砕いてみますね。

二つの数をそれぞれ a, b、この２つの数を割る値を n、それぞれの剰余を m_a, m_b、そして、（＋とか－とか×とか÷と同じように）剰余を求める数学的演算子として、modulo とすれば、次の関係式が成り立ちます。

a modulo n = m_a
b modulo n = m_b

で、もし、

m_a = m_b

ならば、

a と b は、n を法として合同

と表現すると。ようするに、

「a modulo n = b modulo n」ならば、「a と b は n を法として合同」と言える。

ということですね。 ここまで来るともう一つの重要な表現である、『数 a を n で割った剰余を、「n を法とした a」』 っていうのは、もはやなんてことなくて、単にその数の剰余を求めてますよ、ということになりますね。
今後、「n を法とした a」という文言を発見したら、脳内で「a modulo n の結果のこと」に即変換してやればいいわけです。
その上で、改めてFermatの小定理をもう一度みてみます。

n: 素数
a: a < n な自然数
a^n ≡ a (※nを法とする）

１行目、２行目はまぁいいとして、３行目！ これは次のように書き換えられますね。

n: 素数
a: a < n な自然数
a^n modulo n = a modulo n

やっと理解できた。。では続きを写経。
あ、その前に、「俺が」混乱しないように今やろうとしていることを整理しておきます。
今議論している内容は、

～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～
「Fermatの小定理を証明すること」ではなく、
「Fermatの小定理を利用して素数を求めるにはどうするか」
～～～～～～～～～～～～～～～～～～～～～～～～～～～～～～

です。あぶねー。勘違いして時間を無駄にするところだったぜ。。

n が素数でない時、一般に a < n なる殆どの数について上の関係は成り立たない。
このことから次の素数性テストのアルゴリズムができる。

与えられた数 n に対し、 a < n なるランダムな数の n を法とした a^n の剰余を計算する。
結果が a でなければ、n は確実に素数ではない。
結果が a ならば、n が素数である確率は高い。
別の数 a をランダムにとり、同じようにテストする。
また等式が成り立つなら、n が素数であることに更に確信が持てる。
更にいろいろな a の値で確かめることで結果の確信度が増す。

このアルゴリズムはFermatテストとして知られている。

ここで話題にしてるのは、Fermatの小定理を使った、「Fermatテスト」なるものについて。 「法」の概念がわかりゃ、上の分かりにくい文章もすっきり整理できるっしょ。

主役： n
脇役： a (< n)
脚本： a^n modulo n
結末： m (= a^n modulo n)
       ① m ≠ a　→ n は素数ではない。
       ② m ＝ a　→ n は「素数である確率が高い」。
          この場合、ランダムに a を選んで同じ評価を繰り替えしていけば、
　　　　　より素数である確率が高くなる。

ここまでくれば、次のschemeの実装も理解できるかも？

Fermatテストを実装するには、ある数のべき乗の別の数を法とした剰余を計算する手続きがいる。

(define (expmod base exp m)
  (cond ((= exp 0) 1)
        ((even? exp)
         (remainder (square (expmod base (/ exp 2) m))
                    m))
        (else
         (remainder (* base (expmod base (- exp 1) m))
                    m))))

「ある数のべき乗の別の数を法とした剰余を計算する手続き」という表現に、文字変数も一緒に記述して欲しいなぁ。。
この定義式のアルゴリズムが理解できないが、定義式中の登場人物、base, exp, m の役割を推測してみると、こんな感じでしょうか。

base ： ある数（べき乗される数）？
exp  ： べき乗（する数）？
m    ： 別の数？

さて、この定義式のアルゴリズムについてですが・・・悲しくなる程理解できません。。
普通に考えたら再帰して「べき乗演算」を実施してからその結果に対して剰余算するのが素直なやり方だと思うんですが、この定義式は、自身を呼び出して、remainderまで含めて再帰している。。

・・・根本的に何かを見落としていそうだなぁ。 ちょっと数式で考えて行ってみましょう。

　
  base^exp modulo m
= (base * base * ... * base) modulo m  (※ (base * base * ... * base)は exp 回繰り返し）

modulo演算は四則演算と同じような位置づけだが、各種演算子に対してどういう法則（分配法則とか結合法則とか）が成り立つかどうかがミソっぽいですね。
ようするに、

= base * ((base * base * ... * base) modulo m)      (※ (base * base * ... * base)は exp-1 回繰り返し)
= base * base * ((base * base * ... * base) modulo m)  (※ (base * base * ... * base)は exp-2 回繰り返し)
　　・
　　・
　　・
= base * base * ... (base modulo m)              (※ base * base * ... は exp-1 回繰り返し)

のように変換ができると何となく再帰で処理できそうな・・・っていやいやいや、これは違うなwww
答えの数字がどんどんデカくなってっちゃうもの。

仕方ない、自分の脳みそで予想できないなら、定義式のアルゴリズムから何をしているかを解析してみましょう。
元の定義式の逐次平方を削除して簡略化して、正規順序評価してみます。
簡略化するとこんな感じ。

(define (expmod base exp m)
  (if (= exp 0)
      1
      (remainder (* base (expmod base (- exp 1) m))
                 m)))

で、例としてこんなパラメータでやってみます。

base = 7
exp  = 5
m    = 3

if構文は逐次評価してやると、こんなツリー構造になる。

(remainder
 (* 7 
    (remainder
     (* 7 
        (remainder
         (* 7 
            (remainder
             (* 7
                (remainder
                 (* 7 
                    1)
                 3))
             3))
         3))
     3))
 3)

こいつを数式にするとこんな風に記述できます。

((7 * ((7 * ((7 * ((7 * ((* 7 1) modulo 3)) modulo 3)) modulo 3)) modulo 3)) modulo 3)

え！？modulo演算てこんな風に展開されるの？？マジで？

シラネーヨw

ギブギブ！！これはもうそういうモンだと解釈して話を進めようw

と思ってたらこんなんありました。

冪剰余（Wikipedia）

この中の「途中で剰余を取る」って項目。
これ、証明できるんだろうなぁ。どうしようか。。


－

SICP 練習問題 1.20 （最大公約数算出で使用されているremainderの正規評価順序と作用評価順序について）

【問題】
手続きが生成するプロセスはもちろん解釈系が使う規則に依存する。
例えば、上で述べた反復的 gcd 手続きを考え、1.1.5節で論じた正規順序評価を使って解釈したとする。（if の正規順序評価規則は問題1.5に書いてある。）
（正規順序の）置き換え法を使い、(gcd 206 40) の評価で生成されるプロセスを図示し、実際に実行されるremainder演算を指示せよ。

(gcd 206 40) の正規順序評価で、remainder演算は実際に何回実行されるか。作用的順序ではどうか。


【解答】

問題が一体何をおっしゃってるのかさっぱりわかりません。。

で、とりあえず1.1.5節をもう一度読み直してみたら少し理解できた。
ここ、多分華麗にスルーしたところですよ。（Schemeやらせろーっ！って思ってすっ飛ばしたところ。）

問題文中にでてくる、正規順序評価とか作用的順序(評価）というのは、

○正規順序評価
　　　基本的演算子だけを持つ式が出てくるまでパラメタへの被演算子の式の置き換えを繰り返し、
　　　基本的演算子が出現してから初めて評価を行う方式。

○作用的順序評価
　　　引数を評価してから作用させる方式。

ということらしい。ここらへん、多分SICPの後半で効いてきそうな気がするぜ。

もっとイメージしやすいお話が、ここで行われている。。
http://www.bookshelf.jp/2ch/tech/1002584344.html#725

すげーなぁ2ch。集合知だよねぇ。

ここ読んでて、以前俺様言語インタプリタを実装してた頃の事を思い出した。
「普通、関数に渡す引数って、その関数の中に入る前に評価するよね～」と、
まったく疑問にも思わず実装したことを思い出したぜ。
これが作用的順序評価に相当し、評価する前に関数に渡してしまうのが正規順序評価なわけだ。
正規順序評価なんて、どーやって実装すんだよ脳みそ溶けちまうわ。

んでは早速この問題を解いてみよう。


まずは正規順序評価から。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))


(gcd 206 40)
(gcd 40 (remainder ...

まて、remainderって基本演算子？てか、基本演算子の定義って何よ？
まぁいいや。remainderは基本演算子じゃないと考えてみるか。

(if (= 40 0)
    206
    (if (= (remainder 206 40) 0)
        40
        (if (= (remainder 40 (remainder 206 40)) 0)
            (remainder 206 40)
            (if (= (remainder (remainder 206 40) 
                              (remainder 40 (remainder 206 40))) 0)
                (remainder 40 (remainder 206 40))
                (gcd (remainder (remainder 206 40) 
                                (remainder 40 (remainder 206 40)))
                     (remainder (remainder 40 (remainder 206 40)) 
                                (remainder (remainder 206 40)
                                           (remainder 40 (remainder 206 40)))))
                (if (= (remainder (remainder 40 (remainder 206 40)) 
                                  (remainder (remainder 206 40)
                                             (remainder 40 (remainder 206 40)))) 0)
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40)))
                    (gcd (remainder (remainder 40 (remainder 206 40)) 
                                    (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40))))
                         (remainder (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40)))
                                    (remainder (remainder 40 (remainder 206 40)) 
                                               (remainder (remainder 206 40)
                                                          (remainder 40
                                                                     (remainder 206 40)))))))))))

最後の if で、条件式が #t になる。とりあえず動くかどうかやってみる。

gosh> (if (= 40 0)
    206
    (if (= (remainder 206 40) 0)
        40
        (if (= (remainder 40 (remainder 206 40)) 0)
            (remainder 206 40)
            (if (= (remainder (remainder 206 40) 
                              (remainder 40 (remainder 206 40))) 0)
                (remainder 40 (remainder 206 40))
                (gcd (remainder (remainder 206 40) 
                                (remainder 40 (remainder 206 40)))
                     (remainder (remainder 40 (remainder 206 40)) 
                                (remainder (remainder 206 40)
                                           (remainder 40 (remainder 206 40)))))
                (if (= (remainder (remainder 40 (remainder 206 40)) 
                                  (remainder (remainder 206 40)
                                             (remainder 40 (remainder 206 40)))) 0)
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40)))
                    (gcd (remainder (remainder 40 (remainder 206 40)) 
                                    (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40))))
                         (remainder (remainder (remainder 206 40)
                                               (remainder 40 (remainder 206 40)))
                                    (remainder (remainder 40 (remainder 206 40)) 
                                               (remainder (remainder 206 40)
                                                          (remainder 40
                                                                     (remainder 206 40)))))))))))
*** ERROR: Compile Error: syntax-error: malformed if: (if (= (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) 0) (remainder 40 (remainder 206 40)) (gcd (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))) (if (= (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) 0) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (gcd (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40)))) (remainder (remainder (remainder 206 40) (remainder 40 (remainder 206 40))) (remainder (remainder 40 (remainder 206 40)) (remainder (remainder 206 40) (remainder 40 (remainder 206 40))))))))
"(stdin)":65:(if (= 40 0) 206 (if (= (remainder 2 ...

Stack Trace:
_______________________________________
gosh> 

うげ。あ、ちょっとまてよ？ifは構文オブジェクトだからなんか特殊な評価をするんだっけ？
問題文にifに関する記述があるんじゃん。

（if の正規順序評価規則は問題1.5に書いてある。）

問題 1.5・・・既に通って来た道なのに。。とりあえず引用してみる。



特殊形式ifの評価規則は、解釈系が正規順序と作用的順序のどちらを使うかに無関係に同じとする。
述語式を最初に評価し、その結果が帰結式と代替式のいずれを評価するかを決める。


おおっと。つまりifが出てきた時点で評価が一発走るわけですね？
（この解釈であってんのか？）

つまり・・・


■１回目

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

は、述語式(= 40 0)が #f になるので、次に評価するのは代替式の

(gcd 40 (remainder 206 40))

■２回目
１回目の引数を評価せずにそのまま使用すると、

(if (= (remainder 206 40) 0)
    40
    (gcd (remainder 206 40) (remainder 40 (remainder 206 40))))

１回目と同じく述語式を評価するとまだ #f 。


■３回目
繰り返して、

(if (= (remainder 40 (remainder 206 40)) 0)
    (remainder 206 40)
    (gcd (remainder 40 (remainder 206 40))
         (remainder (remainder 206 40) 
                    (remainder 40 (remainder 206 40)))))

述語式を評価するとまだ #f 。


■４回目
繰り返して、

(if (= (remainder (remainder 206 40) 
                  (remainder 40 (remainder 206 40))) 0)
    (remainder 40 (remainder 206 40))
    (gcd (remainder (remainder 206 40) 
                    (remainder 40 (remainder 206 40)))
         (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40))))))

述語式を評価するとまだ #f 。

■５回目
繰り返して、

(if (= (remainder (remainder 40 (remainder 206 40)) 
                  (remainder (remainder 206 40) 
                             (remainder 40 (remainder 206 40)))) 0)
    ; 帰結式（ここから）
    (remainder (remainder 206 40) 
               (remainder 40 (remainder 206 40)))
    ; （ここまで）
    (gcd (remainder (remainder 40 (remainder 206 40)) 
                    (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40))))
         (remainder (remainder (remainder 206 40) 
                               (remainder 40 (remainder 206 40))) 
                    (remainder (remainder 40 (remainder 206 40)) 
                               (remainder (remainder 206 40) 
                                          (remainder 40 (remainder 206 40)))))))

述語式を評価するとやっと #t 。
ここに至るまでに、remainder演算子はif（条件式）で次のように呼ばれている。

１回目：０回
２回目：１回
３回目：２回
４回目：４回
５回目：７回

なので、if中では合計14回。


んで、全て置き換え完了後は、帰結式側が評価されるので、合計４回。


疲れた。。






さて次。作用的評価順序だ。

これは簡単だろう。

(gcd 206 40)


(if (= b 0)
    a
    (gcd b (remainder a b)))

■１回目

(if (= 40 0)
    206
    (gcd 40 (remainder 206 40)))

条件式が#fなので、代替式が評価される。
作用的評価順序の場合は演算子より先に被演算子が評価されるので、
このタイミングでremainderが評価され、

(gcd 40 6)

となる。

■２回目

(if (= 6 0)
    40
    (gcd 6 (remainder 40 6)))

条件式が#fなので、代替式が評価される。
１回目と同じくこのタイミングでremainderが評価され、

(gcd 6 4)

■３回目

(if (= 4 0)
    6
    (gcd 4 (remainder 6 4)))

条件式が#fなので、代替式が評価される。
２回目と同じくこのタイミングでremainderが評価され、

(gcd 4 2)

■４回目

(if (= 2 0)
    4
    (gcd 2 (remainder 4 2)))

条件式が#fなので、代替式が評価される。
３回目と同じくこのタイミングでremainderが評価され、

(gcd 2 0)

■５回目

(if (= 0 0)
    2
    (gcd 0 (remainder 2 0)))

条件式が#tなので、帰結式が評価される。
故に答えは 2 。



１～４回目まで、一回ずつremainderが評価されているので
合計４回呼ばれたことになる。



これであってんのかなぁ。。。


－

SICP § 1.2.5 最大公約数 （Euclidのアルゴリズム）

Euclidのアルゴリズム

最大公約数について。

２つの整数 a, b の最大公約数を求める場合、普通は両方の数を素因数分解して、
共通因子を取り出して乗算するけど、もっと効率のいい、すげーアルゴリズムがあるみたい。

このアルゴリズムは、

「a を b で割った剰余を r とすると、
　a と b の公約数は b と r の公約数とまったく同じである」

という考え方に基づいているとのこと。


どういう事かというと、最大公約数を求める関数を GCD とすると、

GCD(a, b) = GCD(b, r)

具体的には、

GCD(206, 40) = GCD(40, 6)   ・・・ 6 = 206 % 40
             = GCD(6, 4)
             = GCD(4, 2)
             = GCD(2, 0)
             = 2

で、204 と 40 の最大公約数は 2 になるそうだ。
お～って思ったんだけど、
な～んかどっかで聞いたような話なんだが、どこで聞いたか思い出せない。。

Schemeで実装するとこんな感じ。
remainder関数は２つの引数の剰余を求める関数です。

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))

ほほう。


－

SICP 練習問題 1.19 （逐次平方変換を利用したFibonacci数を求める末尾再帰処理）

これ結構楽しかった。


【問題】
Fibonacci数を対数的ステップ数で計算するうまいアルゴリズムがある。
1.2.2節の fib-iter プロセスで使った状態変数 a, b の変換、

a ← a + b
b ← a

に注意しよう。この変換を T と呼ぶ。
1 と 0 から始め、T を繰り返して n 回作用させると、Fib(n+1) と Fib(n) の対ができる。
言い換えればFibonacci数は、対 (1, 0) に T^n、つまり変換 T の n 乗を作用させると得られる。
さて、T_pq は対 (a, b) を、

a ← bq + aq + ap
b ← bp + aq

にしたがって変換するものとし、T を変換族 T_pq の p=0, q=1 の特例としよう。

変換 T_pq を2回使うとその効果は同じ形式の変換 T_p'q' を1回使ったのと同じになることを示し、
p', q' を、p, q を使って表せ。
これで変換を二乗する方法が得られ、fast-exptのように逐次平方を使い、T^n を計算することができる。
これらをすべてまとめ、対数的ステップ数の以下の手続きを完成せよ。

(define (fib n)
  (fib-iter 1 0 0 1 n))

(define (fib_iter a b p q count)
  (cond ((= count 0) b)
        ((even? count)
         (fib_iter a
                   b
                     ;p'を計算
                     ;q'を計算
                   (/ count 2)))
        (else
         (fib_iter (+ (* b q) (* a q) (* a p))
                   (+ (* q a) (* p b))
                   p
                   q
                   (- count 1)))))

【解答】

問題文には求める計算式のほぼ全容が記載されており、p' と q' の穴埋め問題になっていた。
が、もったいないのでその部分は見ずに、関数を生成するところまで含めて全部自前で解いてみた。
なので、以下の解答の記述は一部問題文の関数と表記が異なる箇所があるがご了承を。

今回の柱は、

１．(T_pq)^2 と T_p'q' の変換結果から、p', q' を求める。
２．逐次平方による末尾再帰のFibonacci数を算出する関数を求める。

の二本立て。



■(T_pq)^2 と T_p'q' の変換結果から、p', q' を求める。

（１）まずは「(T_pq)^2」から。

T_pq を１回作用させたものを a' b'とすると、問題文の変換式より次のようになる。

a' = bq + aq + ap
b' = bp + aq

次に、a', b' にもう１回 T_pq を作用させたものを a'' b'' とすると、

a'' = b'q + a'q + a'p
b'' = b'p + a'q

と表記できる。
これらから a'', b'', a 及び b の関係を求めると、次のようになる。

a'' = b'q        + a'q             + a'p
    = (bp + aq)q + (bq + aq + ap)q + (bq + aq + ap)p

b'' = b'p        + a'q
    = (bp + aq)p + (bq + aq + ap)q

（２）次に「T_p'q'」を求める。

T_p'q' を１回作用させたものは、a'' b'' になり、かつ T_pq とは同じ変換方式になるので、

a'' = bq' + aq' + ap'
b'' = bp' + aq'

（３）「(T_pq)^2 = T_p'q'」から、a, b それぞれの係数を比較。
（１）、（２）の結果それぞれを、「X・a + Y・b」の形式に変換することにより、
a, b それぞれの係数を比較することで p', q', p, q の関係式が導き出される。

では（１）から。

a'' = b'q        + a'q               + a'p
    = (bp + aq)q + (bq + aq + ap)q   + (bq + aq + ap)p
    = bpq + aq^2 + bq^2 + aq^2 + apq + bpq + apq + ap^2
        ※a, b で項をまとめる。
    = (2q^2 + 2pq + p^2)・a + (2pq + q^2)・b  　　　　　・・・(i)

b'' = b'p        + a'q
    = (bp + aq)p + (bq + aq + ap)q
    = bp^2 + apq + bq^2 + aq^2 + apq
        ※a, b で項をまとめる。
    = (2pq + q^2)・a + (p^2 + q^2)・b　　　　　　　　　　・・・(ii)

次に（２）を変換。

a'' = bq' + aq' + ap'
    = (p' + q')・a + q'・b　　　　　　　　　　　　　　　　・・・(iii)

b'' = bp' + aq'
    = q'・a + p'・b　　　　　　　　　　　　　　　　　　　　・・・(iv)

(i)～(iv)までのそれぞれの係数を比べてみると、つぎのようになる。

p' + q' = 2q^2 + 2pq + p^2   ・・・(i)と(iii)の a の係数の比較
q'      = 2pq + q^2          ・・・(i)と(iii)の b の係数の比較
q'      = 2pq + q^2          ・・・(ii)と(iv)の a の係数の比較
p'      = p^2 + q^2          ・・・(ii)と(iv)の b の係数の比較

関係式が過剰供給気味だが、上記から、次の関係式が得られる。

p' = p^2 + q^2
q' = q^2 + 2pq

これが１本目の柱の答えね。


■逐次平方による末尾再帰のFibonacci数を算出する関数を求める。

さて、再帰処理の登場人物を考えよう。

a : １つ前の項の数値（と同時に解答でもある）
b : ２つ前の項の数値
p : 変換係数その１
q : 変換係数その２
i : あと何回計算するべきか。

こんなもんか？登場人物が出揃ったところで関数のおおまかな全体像を記述してみよう。

(define (Fib_log a b p q i)
  (cond ((= i 0) b)
        ((even? i) ①)
        (else ②)))

こんな感じになる。こいつの導出はもういいよね？メインディッシュは、①と②の導出の仕方だし。
で、その①と②にはそれぞれこんな処理をさせたい。

① : T_p'q'に相当する変換係数 p', q' を求める処理を行ってから、
     同じ a, b でFib_logを呼び出す。
     その際、i を半分にしてしまう。
② : T_pqに相当する変換処理を行ってからFib_logを呼び出す。
     その際、i を 1 減算する。

具体的に実装してみよう。

① = (Fib_log a
              b
              (+ (* p p) (* q q))
              (+ (* q q) (* 2 p q))
              (/ i 2)) 

② = (Fib_log (+ (* b q) (* a q) (* a p))
              (+ (* q a) (* p b))
              p
              q
              (- i 1))

おお！これでいけるっしょ！？
完成形を書いてみるぜ。

(define (Fib_log a b p q i)
  (cond ((= i 0) b)
        ((even? i)
         (Fib_log a
                  b
                  (+ (* p p) (* q q))
                  (+ (* q q) (* 2 p q))
                  (/ i 2)))
        (else
         (Fib_log (+ (* b q) (* a q) (* a p))
                  (+ (* q a) (* p b))
                  p
                  q
                  (- i 1)))))

実行してみる。

gosh> (map (lambda (x) (Fib_log 1 0 0 1 x)) '(0 1 2 3 4 5 6 7 8 9 10))
(0 1 1 2 3 5 8 13 21 34 55)
gosh> 

おお～。今回はかなりすんなりできたなぁ。


－

SICP 練習問題 1.18 （1.17の末尾再帰化・・・）

あ。。


【問題】
問題 1.16, 1.17 の結果を使い、加算、二倍、二分による、対数的ステップ数の、
２つの整数の乗算の反復的プロセスを生成する手続きを工夫せよ。


【解答】
これ、1.17の段階でやっちゃってるので省略します。。

－

SICP 練習問題 1.17 （逐次加算？を用いた乗算）

割とすんなりできたなぁ。


【問題】
本節のべき乗アルゴリズムは乗算の繰り返しによるべき乗の実行に基づいていた。
同様に整数の乗算を加算の繰り返しで実行できる。
次の乗算手続きは expt 手続きに似たものである。
（この言語には加算はあるが乗算はないと仮定する）

(define (* a b)
  (if (= b 0)
      0
      (+ a (* a (- b 1)))))

このアルゴリズムは b に雪景のステップ数をとる。
加算の他に、整数を2倍する double 演算と（偶数の）整数を２で割る halve 演算もあるとしよう。
これらを使い、fast-exptと類似の対数的ステップ数の乗算手続きを設計せよ。



【解答】
本練習問題の前に、参考書に記載されていた expt 手続きを書いておこう。

;;非末尾再帰バージョン
(define (expt b n)
  (if (= n 0)
      1
      (* b (expt b (- n 1)))))

;;末尾再帰バージョン
(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))))

さて、今回は掛け算を逐次平方のようなスタイルで実装するとのこと。
まずは double と halveを定義しよう。

(define (double x)
  (+ x x))

(define (halve x)
  (/ x 2))

これらを使って対数的ステップ数の乗算手続きを求めていく。
具体的に問題を解析してみよう。

a × b = a + a + a + ... + a  (※aをb回加算する）

b が偶数だったら、その後は b/2 回だけ a+a を加算していく処理にすればつじつまがあうよね。
b が奇数だったら、その時は a を加算して、その後は b-1 回だけ a を加算していく処理にすればOK。

で、末尾再帰に必要な、不変数（終了時はそれが解答になり、終了しない時は次の再帰処理での材料になるやつ）をaccm という名前にすると、上記の処理はこんな感じになる。

a    : 今回の加算値
b    : 残りの加算回数
a'   : 次回の加算値
b'   : 次回の加算回数
accm : 累計値

b が偶数の場合
a'   = a + a
b'   = b / 2
accm = accm

b が奇数の場合
a'   = a
b'   = b - 1
accm = accm + a

あとは、終了条件だが、これは b = 0 になった時に、accmを返せばいいだけ。

これそのまま実装していきゃできそうだな。

「*」を再定義するのはイヤなので、multiplyって名前にしてみる。

(define (multiply a b accm)
  (cond ((= b 0) accm)
        ((even? b) (multiply (double a) (halve b) accm))
        (else (multiply a (- b 1) (+ accm a)))))

できた～。


－

SICP 練習問題 1.16 （逐次平方を使った末尾再帰のベキ乗計算）

【問題】
fast-exptのように、逐次平方をを使い、対数的ステップ数の反復的ベキ乗プロセスを生成する手続きを設計せよ。

ヒント：

(b^(n/2))^2 = (b^2)^(n/2)

に注意し、指数nと底bの他にもう一つの状態変数aを用意する。
状態の移り変わりで積ab^nが不変であるように状態遷移を定義する。プロセス開始時にaを1とし、プロセス終了時にaが結果になるようにする。
一般に、状態の移り変わり不変のままの普遍量（invariant quantity）を定義する技法は、反復的アルゴリズムの設計に有用である。



【解答】

いきなり記述されている「fast-expt」について、参考書の方でどう記述されていたかを載せよう。

;squareはなかったけど必要なので定義した。
(define (square x)
  (* x x))


(define (fast-expt b n)
  (cond ((= n 0) 1)
        ((even? n) (square (fast-expt b (/ n 2))))
        (else (* b (fast-expt b (- n 1))))))

これが末尾再帰になってないので末尾再帰にしてね、という問題だと思う。




末尾再帰のコツは、

１．終了時にはそれが答えになり、
２．かつ終了しない場合は再帰処理の材料になる

そういうモノを全て引数で渡していくように考えること。
問題文のヒントにあるとおりに順番に考えていこう。

まず状態変数 a （つまりこれが上の１，２を満たす値になるわけだ）を用意するって話なので、今から定義していく関数のインタフェースはこんな感じになる。

(define (fast-expt2 b n a)
  なんらかの処理)

「何らかの処理」のところは、「ab^n」が不変になるようにするとのことなので、
とりあえずそう書いてみようか。

(define (fast-expt2 b n a)
  (* a (ベキ乗処理 b n)))

こんな感じ。「ベキ乗処理」やるなら再帰なので、ここで自分自身を呼び出す必要があるよね。

(define (fast-expt2 b n a)
  (* a (fast-expt2 b (- n 1) 次のa)))

「次のa」は、bをひとつ掛けた値になる。

(define (fast-expt2 b n a)
  (* a (fast-expt2 b (- n 1) (* a b))))

そうすると、「(* a (fast-expt2 b (- n 1) (* a b)))」の意味がわからんな。
最終的には、終了条件を満たした時に、aを返却すればいいんだから、
「(* a (fast-expt2 ...))」の、「(* a 」の部分は不要だなぁ。

(define (fast-expt2 b n a)
  (fast-expt2 b (- n 1) (* a b)))

お、すっきり。

じゃ、次に、終了条件を考えよう。これがないと終わらねーからな。
n=0の時に終了すればいいんだから、こう書ける。

(define (fast-expt2 b n a)
  (if (= n 0)
      a
      (fast-expt2 b (- n 1) (* a b))))

さて、これだと普通のベキ乗の計算を末尾再帰にしただけだな。
逐次平方を使うんだから、これにその概念を取り入れねば。

とりあえず、同じような形にしてみよう。

今作ったfast-expt2は n の比較を、「= 0 の場合」しか判別してないけど、
逐次平方ならば「偶数かどうか」という判別処理が必要になるから、
ifではなくてcondに変更してみる。

(define (fast-expt2 b n a)
  (cond ((= n 0) a)
        (else (fast-expt2 b (- n 1) (* a b)))))

じゃ、改めまして偶数判別のケースを入れてみる。

(define (fast-expt2 b n a)
  (cond ((= n 0) a)
        ((even? n) ここでうまい処理をする)
        (else (fast-expt2 b (- n 1) (* a b)))))

「ここでうまい処理をする」ってｗ

さて、どーすりゃいいんだろうなぁ。


元の処理は、「(square (fast-expt b (/ n 2)))」


となっているが、これだとfast-exptから戻ってきてから、squareしないとならん。
つまり末尾再帰じゃなくなってしまう。



あ！そうか、渡す b の値を２乗した値に変えちまえばいいんじゃね！！？

(define (fast-expt2 b n a)
  (cond ((= n 0) a)
        ((even? n) (fast-expt2 (* b b) (/ n 2) a))
        (else (fast-expt2 b (- n 1) (* a b)))))

できた～。実行結果もＯＫっぽい。

gosh> (map (lambda (x) (fast-expt2 2 x 1)) (iota 20))
(1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288)

他の人の解答もおんなじ感じだし♪


－

SICP 練習問題 1.15 （sine近似ネタでステップ数とスペース数を求める）

【問題】
（ラジアンで表す）角度の正弦はｘが十分小さい時、

sin(x)≒x

の近似と、正弦の引数の値を小さくする為の三角関係式、

sin(x) = 3 sin(x/3) - 4 sin^3(x/3)

を使って計算できる。
（この問題の為には、角度の大きさが0.1ラジアンより大きくなければ「十分小さい」と考える。）

この方法は次の手続きに採用してある。

(define (cube x)
  (* x x x))

(define (p x)
  (- (* 3 x) (* 4 (cube x))))

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

a) (sine 12.15)の評価で、手続きpは何回作用させられたか。

b) (sine a)の評価で、手続きsineの生成するプロセスが使うスペースとステップ数の増加の程度は
(aの関数として)何か。




【解答】

a)について。


trace使えば何回呼ばれたかわかるよね。
というわけで準備。

gosh> (use slib)
#
gosh> (require `trace)
#t
gosh> trace
#
gosh> (trace p)
#

んでは実行してみましょう。

gosh> (sine 12.15)
CALL p 0.049999999999999996
RETN p 0.1495
CALL p 0.1495
RETN p 0.4351345505
CALL p 0.4351345505
RETN p 0.9758465331678772
CALL p 0.9758465331678772
RETN p -0.7895631144708228
CALL p -0.7895631144708228
RETN p -0.39980345741334
-0.39980345741334
gosh> 

CALLされた回数だから、答えは５回。ずるいとか言わない。



b)について

これ、例によってまったく分からん。。解答をカンニング！

SICP Reading's Wiki



藤谷さんの回答でちょっと分かったような気がしてきた。
藤谷さん、ありがとうございました！


終了条件に目をつけるのね。

aを3で割る回数がn回になった時に *終了した* と仮定すると、

(define (sine angle)
  (if (not (> (abs angle) 0.1))
      angle
      (p (sine (/ angle 3.0)))))

↓notじゃない表記にすると・・・

(define (sine angle)
  (if (<= (abs angle) 0.1)
      angle
      (p (sine (/ angle 3.0)))))

の定義（特に終了の定義）から、a ≡ angleであるので、

a * (1/3) * (1/3) * (1/3) * ... * (1/3) <= 0.1  ・・・(1)  (※左辺は(1/3)をn回掛けている）

という関係式が成り立つ。 n回の時に初めてこれが成り立つという仮定なので、n-1回の時は勿論↓こうなる。

0.1 < a * (1/3) * (1/3) * (1/3) * ... * (1/3)   ・・・(2)　(※右辺は(1/3)をn-1回掛けている）

なので、(1), (2)から、次の関係式が導かれる。

a/3^n <= 0.1 < a/3^(n-1)

こいつを元に、n =[f(a)] の関係式を導く。 ちなみに、[x]という表記は、「xを超えない最大の整数」という意味を持つ。 nは当然ながら「回数」であるので自然数の範疇であるから、この意味は納得できる。 さて、n=...の形にしたい場合、ベキ乗になっているnを通常の項にしてやらないとならんので、 まずは両辺の対数を取る。しかも3^nの3を消去したいので底は３にする必要がある。

log_3(a/3^n) <= log_3(0.1) < log_3(a/3^(n-1))
log_3(a) - log_3(3^n) <= log_3(0.1) < log_3(a) - log_3(3^(n-1))
log_3(a) - n・log_3(3) <= log_3(0.1) < log_3(a) - (n-1)・log_3(3)
log_3(a) - n <= log_3(0.1) < log_3(a) - n - 1

各数式にnを加算。

log_3(a) <= log_3(0.1) + n < log_3(a) - 1

各数式からに log_3(0.1) を減算。

log_3(a) - log_3(0.1) <= n < log_3(a) - log_3(0.1) - 1

上記の式から、[x]で表記可能にするには、取りうる値の最大の値（式）を採用したいので、右辺を採用して、

n = [log_3(a) - log_3(0.1) - 1]

となる。 Θは、定数項、次元の低い項、定数係数は無視するので、 ステップ数nは、Θ(log_3(a)) となる。 ちょっと分かった！（気がする（かも）） しかしスペースに関しては「これだ！」という計算の方法がわからない。 けど、sine関数は末尾再帰になってなくて、かつ枝分かれするタイプでもないので、 ステップ数に比例して、pの計算の為の領域が増加していくイメージは湧く。 ステップ数と比例関係にあるから、やっぱりスペース数もΘ(log_3(a))でいいんじゃない？ 藤谷さんの解答にもあったけど、このイメージ↓。

(sine 12.15)
(p (sine 4.05))
(p (p (sine 1.35)))
(p (p (p (sine 0.45))))
(p (p (p (p (sine 0.15)))))
(p (p (p (p (p (sine 0.05))))))

－

SICP 練習問題 1.14 （両替の場合計算に関するスペースとステップの問題）

こいつはさっぱりわからん。。
前段の「1.2.3　増加の程度」を読むと、言いたいことはわかるんだが、
じゃあそのΘ(なんちゃら）を求めるには具体的にどうすりゃいいのよ？ってところがわからん。

とりあえず次のようにやってみた。「解答」というレベルではないぞ。。


【問題】
1.2.2節のcount-change手続きが11セントの両替の場合に生成するプロセスを示す木構造を描け。
両替の金額の増加につれ、このプロセスが使うスペースとステップ数の増加の程度は何か。


【なぐりがき解答】
まずはその両替の関数群を記載しよう。

(define (count-change amount)
  (cc amount 5))

(define (cc amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc amount
                     (- kinds-of-coins 1))
                 (cc (- amount
                        (first-denomination kinds-of-coins))
                     kinds-of-coins)))))

(define (first-denomination kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

上記の関数群中、再帰的に呼び出されているのは「cc」なので、トレースしちゃう。

gosh> (count-change 11)
CALL cc 11 5
  CALL cc 11 4
    CALL cc 11 3
      CALL cc 11 2
        CALL cc 11 1
        RETN cc 1
        CALL cc 6 2
        RETN cc 2
      RETN cc 3
      CALL cc 1 3
        CALL cc 1 2
        RETN cc 1
        CALL cc -9 3
        RETN cc 0
      RETN cc 1
    RETN cc 4
    CALL cc -14 4
    RETN cc 0
  RETN cc 4
  CALL cc -39 5
  RETN cc 0
RETN cc 4
4
gosh> 

木構造を描くのはこれでいんじゃね？頭の中で描いたのはまさにこんな感じのモノ。 次の、「両替の金額の増加につれ、このプロセスが使うスペースとステップ数の増加の程度は何か。」 は、ホントに全くどう考えればいいのか不明っす。 とりあえず、0～99まで渡してみた。

gosh> (use srfi-1) ;iotaを使用したいので。
#
gosh> (map count-change (iota 100))
(1 1 1 1 1 2 2 2 2 2 4 4 4 4 4 6 6 6 6 6 9 9 9 9 9 13 13 13 13 13 18 18 18 18 18 24 24 24 24 
24 31 31 31 31 31 39 39 39 39 39 50 50 50 50 50 62 62 62 62 62 77 77 77 77 77 93 93 93 93 93 
112 112 112 112 112 134 134 134 134 134 159 159 159 159 159 187 187 187 187 187 218 218 218 
218 218 252 252 252 252 252)
gosh> 

返却されたリストを５個づつ順番に整理するとこんな感じになった。

1   1   1   1   1
  2   2   2   2   2   
  4   4   4   4   4   
  6   6   6   6   6   
  9   9   9   9   9   
 13  13  13  13  13  
 18  18  18  18  18  
 24  24  24  24  24  
 31  31  31  31  31  
 39  39  39  39  39  
 50  50  50  50  50  
 62  62  62  62  62  
 77  77  77  77  77  
 93  93  93  93  93  
112 112 112 112 112 
134 134 134 134 134 
159 159 159 159 159 
187 187 187 187 187 
218 218 218 218 218 
252 252 252 252 252

でもこれじゃ金額の増加とともに両替の場合の数がどう変化するか、しかわかんねー。
何を元にして考えりゃいいんだろ。。


－

SICP 練習問題 1.13 （Fibonacci数の帰納的証明？）

練習問題 1.13は、普通に数学の問題なんじゃ。。
ちなみに命題の前半は、どう表現すればよいのかさっぱりわかりません！
なので、ヒント以降を証明しよう。


【問題】

φ = (1 + √5)) / 2

として、Fib(n)が (φ^n) / √5) に最も近い整数であることを証明せよ。

ヒント：

ψ = (1 - √5)) / 2

とする。帰納法とFibonacci数の定義(1.2.2節参照）を用い、

Fib(n) = (φ^n - ψ^n) / 5^(1/2)

を証明せよ。


【解答】
φとψの特性として、次が成り立つ。

φ^2 = φ + 1
ψ^2 = ψ + 1

また、初期条件として、n=0、n=1のケースを考える。

Fib(0) = (φ^0 - ψ^0) / √5
       = (0 - 0) / √5
       = 0

Fib(1) = (φ^1 - ψ^1) / √5)
       = (φ - ψ) / √5
       = (((1 + √5) / 2) - ((1 - √5)) / 2) / √5
       = ((1 + √5 - 1 + √5) / 2) / √5
       = (2√5 / 2) / √5
       = √5 / √5
       = 1

さて、n≧2 の場合、次のように表現することが可能。

Fib(n) = (φ^n - ψ^n) / √5
       = (φ^(n-2)・φ^2 - ψ^(n-2)・ψ^2) / √5
       = (φ^(n-2)・(φ + 1) - ψ^(n-2)・(ψ + 1)) / √5
       = (φ^(n-1) + φ^(n-2) - ψ^(n-1) - ψ^(n-2)) / √5
       = (φ^(n-1) - ψ^(n-1)) / √5 + (φ^(n-2) - ψ^(n-2)) / √5
       = Fib(n-1) + Fib(n-2)

よって、「ヒント」の命題は示せた。

あってる？


Q.E.D.

－

SICP 練習問題 1.12 （Pascal三角形）

今度は１日で解けた～。（マイペースマイペース。。）
思ったんだけど、１つの問題につき１エントリの方がいいかもなぁ。
さて、Pascal三角形です。


【問題】
次の数のパターンをPascal三角形と言う。

0:      1
1:     1 1
2:    1 2 1
3:   1 3 3 1
4:  1 4 6 4 1

三角形の返上の数は全て 1、三角形の内部の数はその上の２つの数の和である。
再帰的プロセスの方法でPascal三角形の要素を計算する手続きを書け。



【解答】
リストで考えると楽かもと思い、要素が数のリストを受け取ったら、
それに対して上記の条件（その上の２つの数の和）を満たすリストを生成して返す、
という方針でまずは問題の核を解く。

登場人物は、元になるリスト「src」、計算して生成されるリスト「dst」の２つ。
こいつらを渡してどうするか。

(define (calc src dst)
  (if (null? src) ;;srcがnullならdstを返却。
      dst
      (calc                              ;;そうでなければ、
        (cdr src)                        ;;srcの残りと、
        (cons (+ 更に前の要素 (car src)) ;;「更に前の要素」とsrcの先頭要素の和を
              dst))))                    ;;dstに連結したものを引数としてcalcに渡す。

さて、ここで「更に前の要素」なるものが登場しましたが、これはsrcのcarよりも一つ前に格納されていた数値です。つまり、上記のソースではもはやアクセスできない要素になっています。
従って、引数として渡しちゃいます。

(define (calc v src dst) ;「v」として、srcのcarよりも一つ前の情報を渡しちゃう。
  (if (null? src) ;;srcがnullならdstを返却。
      dst
      (calc
        (car src) ; 今のsrcのcarを次の「v」としてcalcに渡す。
        (cdr src)
        (cons (+ v (car src)) ;「v」とsrcのcarを加算する。
              dst))))

ここで一回実行してみましょう。

gosh> (calc 0 '(1) '())
(1)
gosh> (calc 0 '(1 1) '())
(2 1)
gosh> (calc 0 '(1 2 1) '())
(3 3 1)
gosh> (calc 0 '(1 3 3 1) '())
(4 6 4 1)
gosh> (calc 0 '(1 4 6 4 1) '())
(5 10 10 5 1)
gosh> 

・・・最後に連結されるべき要素が連結されていない？
一つ前のコードを良く見ると、確かに終了判定された際にそのままdstを返してますね。
これじゃあ最後のsrcリストの要素が無視されてしまう。。
なので、終了前に「v」をdstに連結してしまおう。

(define (calc v src dst)
  (if (null? src)
      (cons v dst) ; 終了時に「v」を「dst」に連結してから返却
      (calc
        (car src)
        (cdr src)
        (cons (+ v (car src))
              dst))))

これでどうだ！

gosh> (calc 0 '(1) '())
(1 1)
gosh> (calc 0 '(1 1) '())
(1 2 1)
gosh> (calc 0 '(1 2 1) '())
(1 3 3 1)
gosh> (calc 0 '(1 5 1) '())
(1 6 6 1)
gosh> 

おお～、できた。

さて、今度はこのイテレータを呼び出す関数を考える。
呼び出す側は、何番目の行を表示させるか、を引数として渡してあげたい感じなので、インターフェースとして行番号を渡してみる。

(define (f row)
  どうにかしてcalcを呼び出す)

こんな感じ。とりあえずcalcを呼び出してみる。

(define (f row)
  (calc 0 元ネタのリスト '()))

元ネタのリストは、calcが返却するリストです。こいつは元をたどれば「f」が渡してやるべきリストなので、初期値は「'(1)」になります。なので、letを使って、

(define (f row)
  (let ((src '(1)))
    (calc 0 src '())))

さて、これだと一発呼んで終わっちまうので、calcが返却してくるリストを使って、更にcalcを呼び出す必要があり、それはrowで指定された回数だけ呼び出す必要があるので、名前付きletを使って再帰してみる。

(define (f row)
  (let loop ((src '(1)))
    (loop (calc 0 src '()))))

これだと終了条件がないので、終了条件を考えると、row回やったら終わるので、
letにcount変数を指定してやって、初期値をrow、loop呼び出すたびに１づつ減らしていって0になったら終了する。

(define (f row)
  (let loop ((count row)
      (src '(1)))
    (if (= count 0)
 src
 (loop (- count 1) (calc 0 src '())))))

これでいける？

gosh> (f 0)
(1)
gosh> (f 1)
(1 1)
gosh> (f 2)
(1 2 1)
gosh> (f 3)
(1 3 3 1)
gosh> (f 4)
(1 4 6 4 1)
gosh> (f 5)
(1 5 10 10 5 1)
gosh> (f 6)
(1 6 15 20 15 6 1)
gosh> 

できた。

で、ブログに書いてて気づいたが、俺の解答は再帰的プロセスじゃなくて反復（末尾再帰）か？
てか、そもそもリスト使ったやり方って、問題の意図をくんでいるかどうかかなり怪しい気がしてきた。

他の人の解答を見てみよっと。

－

SICP 練習問題 1.11

べらぼーに時間がかかってしまいましたよ、練習問題の1.11。
でもなんとか自力で解けた（ハズな）ので結構満足。
んでは当時の脳内をトレースして参りましょう。

練習問題 1.11

F(n) = n                          (※ n ＜ 3)
     = F(n-1) + 2F(n-2) + 3F(n-3) (※ 3 ≦ n)

上記の関数を実装する。


【再帰的（非末尾再帰）】
これは特別なひねりなしで実装できた。

(define (f-0 n)
  (if (< n 3)
      n
      (+ (f-0 (- n 1))
         (* 2 (f-0 (- n 2)))
         (* 3 (f-0 (- n 3))))))

【反復的（末尾再帰的）】
さて、末尾再帰ですよ。
重要なのは、自身を再帰呼び出しする箇所を一ヶ所にすることだと思う。
このルールを守ることで、tree構造の計算処理にならなくなるので。

とすると、引数として受け取った数値をそのまま次の計算に使用できるようにする必要がある。 じゃ、どうやるか。
オペレーション F(n-1) と F(n-2) と F(n-3) について、既に計算された結果を、 再帰関数 f-1-iter に渡す、と考える。
この関数の定義だと、次のように解釈することにした。

--------------------
・F(n-1) = n_1 大きい
・F(n-2) = n_2　 ↓↑
・F(n-3) = n_3　小さい
--------------------

そうすると、f-1-iter が受け取る引数を n_1, n_2, n_3 とすれば、計算のエッセンスは次のように記述できる。

(define (f-1-iter n_3 n_2 n_1)
  (f-1-iter n_2                           ;n_2を、次の計算のn_3とみなして渡す。
            n_1                           ;n_1を、次の計算のn_2とみなして渡す。
            (+ n_1 (* 2 n_2) (* 3 n_3)))) ;所定の計算式を実行し、新たな項の値を求めてからn_1とみなして渡す。

さて、問題の根幹は上記でOKだと思うので、次に終了条件を考えよう。
この計算を行う時に、再帰的処理の f-0 と同じように呼び出したいとすると、「何番目？」の情報を引数として渡す感じ。
なので、その定義は次のようになる？

(define (f-1 n)
  (if (< n 3) ;;ここはまぁ普通に問題の条件式を実装する。
      n
      (f-1-iter 0 1 2))) ;で、条件に合致しない場合はf-1-iterを呼び出す感じ。

実際の終了処理は、f-1-iter側で決定するのが自然か？
(あんまり推敲してないから別のやり方があるかもしれないけど。)
「何番目？」の情報で終了チェックをするため、「n」をiterに渡してやる。

(define (f-1 n)
  (if (< n 3)
      n
      (f-1-iter 0 1 2 n)))

受け取る側としては、「n」が3以下になったら処理の終了とし、 その時の n_1 を返却する？

(define (f-1-iter n_3 n_2 n_1 n)
  (if (< n 3)
      n_1
      (f-1-iter n_2
                n_1
                (+ n_1 (* 2 n_2) (* 3 n_3))
                (- n 1))))

一応これで期待通りの動作をしてくれましたけど、もっときれいに記述できそうですよね～。

また加筆修正しま～す。

－

SICP 練習問題 1.6〜1.10

つづいて、さっきまで取り組んでいた練習問題1.6〜1.10の解答を掲載。

;------------------------------
; 1.6
; 特殊形式 if について。（要するに、オペレータではなくて構文だよって言いたいってこと？）
(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

(define (new-sqrt x)
  (let loop ((count 5)
             (src x))
    (new-if (= count 0)
            (exact->inexact src)
            (loop #?=(- count 1) #?=(/ (+ src (/ x src)) 2)))))

;;-> 構文のifならば、第１引数が評価された後に、第２引数、
;;   または第３引数の「どちらか一方が」評価される。
;;   したがって、終了条件が明確になるためちゃんと終了することができる。
;;   翻って、new-ifは単なるオペレータであるため、new-ifで定義している処理を評価する前に、
;;   第１引数から第３引数までが先に評価されてしまう。
;;   つまり、無条件に第３引数の「(loop (- count 1) (/ (+ src (/ x src)) 2))」が評価されてしまい、
;;   無限再帰することになってしまう。
;;   coutはマイナス無限大になっていき、srcは限りなく正しい値に漸近していく感じ？
;;   「#?=」つけてみたら、なんとなくそんな感じにはなってたぞ。


;------------------------------
; 1.7
;;-> すんません、ちょっとすっ飛ばしたい感じなのでそうします。。
;;   （これでもかつては物理専攻でした。。）


;------------------------------
; 1.8
(define (root x proc)
  (let loop ((count 6)
             (src x))
    (if (= count 0)
        (exact->inexact src)
        (loop (- count 1) (proc x src)))))

(define (sqrt x)
  (root x (lambda (x src) (/ (+ src (/ x src)) 2))))

(define (3root x)
  (root x (lambda (x src) (/ (+ (/ x (* src src)) (* 2 src)) 3))))


;;========================================
;;1.9の前に、再帰的 or 反復的 のお勉強を。
;;========================================
; 1.2.1 線形再帰と反復
; n! = n・(n-1)・(n-2)... 3・2・1
(define (factorial1 n)
  (if (= n 1)
      1
      (* n (factorial1 (- n 1)))))

(define (factorial2 n)
  (let loop ((seed n)
             (ans 1))
    (if (= seed 1)
        ans
        (loop (- seed 1) (* ans seed)))))
;; factorial2だとtraceが使えないのでちょこっと変更。
;; ちなみにtraceを利用するには、
;; ------------------------------
;; gosh> (use slib)
;; gosh> (require 'trace)
;; ------------------------------
;; とやって、
;; ------------------------------
;; gosh> (trace factorial1)
;; #
;; ------------------------------
;; とやった上で、関数を評価してやると、こんな風にでる。
;; ------------------------------
;; gosh> (factorial1 5)
;; CALL factorial1 5
;;  CALL factorial1 4
;;   CALL factorial1 3
;;    CALL factorial1 2
;;    RETN factorial1 2
;;   RETN factorial1 6
;;  RETN factorial1 24
;; RETN factorial1 120
;; 120
;; ------------------------------
(define (f-iter seed ans)
  (if (= seed 1)
      ans
      (f-iter (- seed 1) (* ans seed))))

(define (factorial3 n)
  (f-iter n 1))

;; すんごい適当な理解だけど、SICPで言及されてる「反復的」「再帰的」ってのは、
;; ・反復的 → 末尾再帰
;; ・再帰的 → 非末尾再帰
;; って解釈でいいんかな？

;------------------------------
; 1.9
(define (dec x) (- x 1))
(define (inc x) (+ x 1))

(define (plus a b)
  (if (= a 0)
      b
      (inc (plus (dec a) b))))

(define (plus2 a b)
  (if (= a 0)
      b
      (plus2 (dec a) (inc b))))
;;-> plusはincで入れ子になってく。plus2は末尾再帰してると思う。


;------------------------------
; 1.10
(define (A x y)
  (cond ((= y 0) 0)
        ((= x 0) (* 2 y))
        ((= y 1) 2)
        (else (A (- x 1)
                 (A x (- y 1))))))

;;-> (A 1 10) -> 1024
;;-> (A 2 4)  -> 65536
;;-> (A 3 3)  -> 65536

(define (f n) (A 0 n))   ;-> ２n？
(define (g n) (A 1 n))   ;-> ２^n？
(define (h n) (A 2 n))   ;-> すんません、マジわかりません。。
(define (k n) (* 5 n n)) ;-> 5n^2

1.7が面倒くさそうでやめちまったい。後で後悔するかなぁ。。
あと、1.10はマジわかんね。何コレ？
誰か知ってる人教えてください。

俺数学じゃなくてSchemeをやりたいんだけどなぁ〜。

−

SICP 練習問題 1.1〜1.5

昨日夜更かししてやった、練習問題1.1〜1.5を一挙掲載だ。
とにかくアップだ。

;------------------------------
; 1.1
10
;;-> 10

(+ 5 3 4)
;; -> 12

(- 9 1)
;;-> 8

(/ 6 2)
;;-> 8

(+ (* 2 4) (- 4 6)) 
;;-> 6

(define a 3)
;;-> a

(define b (+ a 1))
;;-> b

(+ a b (* a b))
;;-> 19

(= a b)
;;-> #f

(if (and (> b a) (< b (* a b)))
    b
    a)
;;-> 4

(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25))
;;-> 16

(+ 2 (if (> b a) b a))
;;-> 6

(* (cond ((> a b) a)
  ((< a b) b)
  (else -1))
   (+ a 1))
;;-> 16


;------------------------------
; 1.2
; 5 + 4 + (2 - (3 - (6 + 4/5)))
;ーーーーーーーーーーーーーーーーー
;       3(6 - 2)(2 - 7)
(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5) )))) (* 3 (- 6 2) (- 2 7)))


;------------------------------
; 1.3
(define (squre x)
  (* x x))

(define (larger2-squre-sum . values)
  (let ((lis (reverse (sort values))))
    (+ (squre (car lis)) (squre (cadr lis)))))
    

;------------------------------
; 1.4
(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))
;-> if で、手続き「+」または「-」を返却している。


;------------------------------
; 1.5
(define (p)
  (p))

(define (test x y)
  (if (= x 0)
      0
      y))
;-> (test 0 (p))を評価すると、まず第２引数の(p)が評価される。
;   pは内部で再帰的にpを呼び出すが停止条件がないため、処理が戻ってこなくなる。

今んとこ、得に疑問点とか問題点はない。と思う。

−

SCIP購入！

また大分ご無沙汰してしまいました。
だって業務多忙だったのと、体調崩して寝込んでたのとで・・・

ふん、三日坊主と罵るがいいさ。。


さて、寝込んだとは言ってもただただ寝込んでいたわけではありませんよ？
何をしていたかというと、次のようなことを考えてました。

<妄想>
Schemeで自作の宛名作成ツールのリファクタリングをやってはみたけど、
これって所詮自分の脳みそで思いついたことしかできないから「習熟速度」が期待できないなぁ〜。。
今俺がやらにゃならんことは、「ムリヤリにでも思考の枠を広げる」ことだからな〜。。
</妄想>

そう！俺は今ぬるい環境にいてはいけないのです！
オブジェクト指向のパラダイムに頭の先までドップリ漬かっちまったこの脳みそを、
一度ぶっ壊して関数型（なの？）指向に作り替えなきゃならんのです！
今年で３３になるのです！もう悠長なことをしてる時間はないのです！

さて。

Scheme関連でいろんな人のブログを読んでると、
スゴイ人たちは結構な割合でみんなあるモノを読んでいる、
あるいはやっている傾向があるんですね〜。

その名も「計算機プログラムの構造と解釈」！
上述のブログ主さんたちで練習問題をやり遂げた人は、
みんな「やってよかった」という感想を持っているようです。

ちなみにこの本、あの有名なマサチューセッツ工科大学で教材として採用されており、
１年生はこれでScheme（というか計算機の概念？）をみっちり叩き込まれるらしいです。
大分昔の、もう古典と言われるような本なのですが、名著だってことなんでしょうね。

というわけでアマゾンしました。
昨日自宅に届いて俺狂喜乱舞。


地道に練習問題を解いていこうと思います。

ー

mapすごいよ map

あ～、いきなり空けてしまった。。

その上。

Gaucheのスナップショットからのビルドなのですが、
自分、情けないのですがSchemeそのものをまだまだ全然理解できておらず、
まず雑音無しでSchemeの勉強すべきと考えなおしました。
で、Version 0.9 のアーカイブを落としてきて環境を整え直しました。
Schemeの範疇で一通りのことができるようになったら、開発へ貢献しようと思います。
がんばるぞ。


さて、本題。

以前作成した年賀はがき用の宛名印刷プログラムですが、これ最初はRubyで作成していました。
で、ちょうど良い大きさのプログラムなので、これをお勉強の為にGaucheで再実装してみました。

最初にできたプログラムはものすご～く手続きチックなモノだったのですが（今も割とそうだけど）、
それでもありとあらゆるものを再帰で書きまくってると、
かなりの頻度で同じようなイディオムになってくれるので、
再帰に違和感はなくなりました。もうループ別にイラネ。


Gauche作者のShiroさんが、冗談でこんな記事を書かれてらっしゃいますが、
このレベル４の「前半のみ」をクリアした感じです。

が、実はその段階ではレベル３をクリアしてませんでした。
なんと作りたての時は「map」を一切使用してなかったのです。
（map使えば１行、２行で終わるような処理まで再帰で自前実装してた。）
宛名印刷プログラムをschemeで再実装する前に、
一応mapとかfindとかfoldの練習問題は解いていたんですよ？
でも練習問題解くだけじゃダメで、やっぱり実践こなさないとすんなり使えるようにはならんのですねぇ。

リファクタリングをしているうちにmapのことを思い出し、
今度はなんでもmap化してみました。すごいね、map。
再帰を実践していた時よりも、mapを実践した時の方が自分の脳内で何かが変わった気がする。


今までのscheme絡みの感動は、

--------------------------------------------------
・構文のシンプルさによる可能性を知って、
　脳内のプログラミングの世界が一気に広がったこと。
　（その時は具体例は思いつかなかったんだけど、それでもリアルに鳥肌がたった。）

・「手続きを渡す処理」の便利さをmapで実感できたこと。
--------------------------------------------------

の２つ。

さて、次の感動はScheme「プログラマのレベル」によるとどうやら「継続」のようですが、
既に結構いろんな情報をあさりまくってるのにイマイチ理解できない。。

mapの時もそうだったけど、俺はあんまり理解力がないタイプなので、
最初泥臭くコーディングして、それを継続で置き換える、というプロセスを経ないと理解できないかも。。
う～む。

GaucheをSubversionスナップショットからインストールしてみる。

scheme勉強中だが、schemeだけでなくて言語処理系としてのGaucheも勉強させていただこうということで、Subversionのスナップショットからコンパイルしてみることにしました。

http://practical-scheme.net/gauche/download-j.html

に記載されている通り、端末エミュレータに次のコマンドを入力。

svn co https://gauche.svn.sourceforge.net/svnroot/gauche/Gauche/trunk Gauche

しばらくすると生ソースコードがチェックアウトされてきます。
チェックアウト完了後、上述のURLの最後に記載されている通り、
「HACKING」というテキストファイルの内容を確認します。

・・・英語です。

でも最近OSSに関わっていこうと思って、
はりーぽったーの原著とAudioBookで目と耳を鍛えていたので狼狽えません。
まさに漢の中の漢。
（すげーLinuxでも「おとこの」って入れたら変換候補に
　「漢の」が出てくる時代になったんですねぇ・・・）

とりあえず読みます。
自分が使っているプラットフォームはUbuntu9.10なので、
「On Unix Platforms」のとこを見ればOKですね。

autoconf 2.54以上が必要なようなので、とりあえず「sudo apt-get install autoconf」
でパッケージをインストールします。
インストール完了後、「autoconf -h」でヘルプを確認。
バージョンを「autoconf -V」として確認すると、2.64とのこと。OKですね。

次を読むと、どうやらコンパイルに必要なCのソースコードを生成する為に、
Gaucheの最新リリースバージョンがインストールされている必要があるみたいです。
作成者であるShiroさんの記事を憧憬の思いでいろいろ読ませて頂いてますが、
Cのソースコードもschemeで生成するって記事、確かどっかで読んだなぁ。。
しかもCをLispのように記述してしまったとかなんとか。。あれのことかなぁ。
おっと横道にそれてしまった。。

この記述のすぐ後に、「./DIST gen」を実行せよとの記述がある。
このスクリプト（DIST）内でgoshが使われるのかなぁと、
中身を確認するとあるこたあるがそこのロジックは通らなそう。
渡す引数が「gen」のみなので、呼ばれているのは「autoconf」だけっぽい。
autoconfがgoshを必要とするのかなぁ。。
とりあえずこれ以上の調査は保留にしておいてやってみようか。
まずは「sudo apt-get install gauche」で最新のリリースをインストールします。

gaucheのインストール後、「./DIST gen」を実行します。
すると「configure」ファイルが生成されてます。

さて、この後は「Install.in」ファイルの通りに実行すればよいのかな？
（いろいろとコンパイルオプションがあるようなのですが、
とりあえず自分の今の環境では得にこれらを指定する必要はないので。）
というわけで、次の手順を実行。

./configure
make
make test
make install

・・・makeしたらなんかたくさんエラーがでてる。。
スナップショットってビルドも通らないケースがあるもんなのかな？
「make test」も「make install」も当然エラー。。う～む。

明日はソースを見てみて、俺でも理解できそうならデバッグしてみよう。

というわけで勉強結果を公開していきます。

少し前に「cria.log」というブログを1年ほどやってました。
内容は、オリジナルスクリプト言語の処理系を実装していく過程で思ったことや考えたことでした。
着手から１年程経過してそれなりに動くものができてたんですが、途中でschemeに出会って一気に、ほんとにビックリするぐらい一気にcriaに対する情熱が冷めてしまい、schemeの勉強にとりかかっています。（継続するのって本っ当～に難しいですねぇ・・・）

まだまだ手続き型でモノを考えてしまっていますが、なんとか頑張って立派なschemerになりたいと思います！

プログラマ 35歳 定年説 笑い飛ばして 我が道を征く

諸君 私はプログラミングが好きだ
諸君 私はプログラミングが好きだ
諸君 私はプログラミングが大好きだ

Javaが好きだ
Cが好きだ
Schemeが好きだ
リファクタリングが好きだ
デバッグが好きだ
プロトタイピングが好きだ
Emacsが好きだ
GNUが好きだ
オープンソースが好きだ
Linuxが大好きだ

会社で
自宅で
友人宅で
自分の実家で
妻の実家で
駅構内で
新幹線で
旅行先で
徹夜で
夢の中で

この地上(？)で行われるありとあらゆるプログラミング行動が大好きだ


汚いコードをならべたでっちあげのプロトタイプが 期待した結果と共に正常終了するのが好きだ
年末に急いで作った年賀状用の宛名印刷ツールが 住所や氏名を正しい位置に印刷した時など心がおどる


プログラマの操るテキストエディタが スパゲッティ状態のコードをリファクタリングするのが好きだ
悲鳴を上げたくなるような設計のコードをエレガントにモジュール化して
コードサイズが１／３になった時など胸がすくような気持ちだった


自分のブライドが蹂躙されるのが好きだ
考えぬいた設計に対して 自分よりスキルの高い人から
何度も何度もダメ出しを喰らう様など感動すら覚える


静的言語が大好きだったのに オリジナル言語処理系の作成過程で動的言語のすごさを思い知り
静的言語への忠誠心が木端微塵に粉砕された時など絶頂すら覚える


未知の技術や概念に出会い 勉強して自分の血肉にしていくのが好きだ
30歳を過ぎるまでLisp/schemeの価値を理解できなかった様（ザマ）は とてもとても悲しいものだ


意味のない大量の作業に押し潰されて時間を浪費するのはイヤだ
プログラマ35歳定年説を引き合いに出され他人の管理をするために地べたを這いずり回るのは屈辱の極みだ


諸君 私はプログラミングを 生涯プログラミングを望んでいる
諸君 日々の業務に追われているプログラマ諸君
君達は一体何を望んでいる？

更なるデジドカプログラミングを望むか？
情け容赦のない、糞の様なデジドカプログラミングを望むか？
勉強・実践の限りを尽くし、世の中に変革を与える嵐の様なオープンソースプログラミングを望むか？


『オープンソースプログラミング！　オープンソースプログラミング！　オープンソースプログラミング！』


（語呂は悪いが）よろしい ならば勉強と実践だ


我々は渾身の力をこめて今まさにEnterキーに振り降ろさんとする小指だ（弱そうだな）
だがこの暗い闇の底で社会人になって以来堪え続けてきた我々に
ただのプログラミングではもはや足りない！！

大オープンソースプログラミングを！！（いきなりでっかいのは無理ですよ）
一心不乱の大オープンソースプログラミングを！！（だからいきなりでかいのは無理ですってば）

我々はわずかに一個大隊 千人に満たぬプログラマに過ぎない
だが諸君は一騎当千のプログラマだと私は信仰している
ならば我らは諸君と私で総力100万と1人のオープンソースプログラマ集団となる

我々をその他大勢の彼方へと追いやり 眠りこけている連中を叩き起こそう
髪の毛をつかんで引きずり降ろし眼を開けさせ思い出させよう
連中にプログラミングの味を思い出させてやる
連中に我々の打鍵の音を思い出させてやる

天と地のはざまにはデジドカの哲学では思いもよらないコードへの情熱があることを思い出させてやる
オープンソースプログラマのコーディングで世界を変革し尽くしてやる

「ひよっこプログラマより全サラリーマンプログラマへ」
目標　任意のオープンソースプロジェクトへのコントリビュート！！

第二次プログラマ自己研鑚作戦　状況を開始せよ



征くぞ　諸君


－