Scheme入門 第９章 for文は要らない！？

x! = x(x-1)! （ x > 0 のとき）
   = 1       （ x = 0 のとき）

はい、これは何でしょう。そう。階乗と呼ばれるものです。わかりやすく言いますと、5! = 5×4×3×2×1 = 120 で、10! = 10×9×8×7×6×5×4×3×2×1 = 3628800 です。なに？ わからない？ えーと、要するに、

10! = 10×9!
9! = 9×8!
8! = 8×7!
7! = 7×6!
6! = 6×5!
5! = 5×4!
4! = 4×3!
3! = 3×2!
2! = 2×1!
1! = 1×0!
0! = 1

というわけで、これを展開すると 10! = 10×9×8×7×6×5×4×3×2×1 になるわけです。よくわかったところで、この関数を Scheme で書いてみましょう。・・・書けました？いや、読んでるだけじゃなくて、試しに実際に自分で書いてみて下さいな。階乗の関数。ほら、早く。関数名は factorial（階乗という意味）でどうぞ。

・・・書けました？ 次のようになります。やや長いので複数行に分けました。

(define (factorial x)
  (if (zero? x)
    1
    (* x (factorial (- x 1)))))

(display (factorial 10))

3628800 が出ましたか？これはひとつの例で、他にも書きようがあるでしょうけれど(※1)、とにかく 10 を与えて 3628800 が出ればたぶん正しいでしょう。この関数 factorial は、その中で factorial を使ってますよね？定義の中で自分自身を使う。こういうのを再帰と言います。

えーと。よくわからない方、います？ここで理解してください。でないと苦しみます(※2)。なぜかというと、他の言語では、何か繰り返し処理をさせるときは、for文とかwhile文とか、繰り返し文を使うのが普通でしょうけれど、Scheme では、繰り返し処理はすべからく再帰で書くのが普通なのです。なぜ繰り返し文を使わず再帰で書くのかというと、それで必要十分だからです。

例えば "Hello!" を１０回表示するプログラムは、次のように書きます。

(define (hello n)
  (display "Hello!")
  (newline)
  (if (> n 1) (hello (- n 1))))

(hello 10)

再帰を入れる位置や条件を変えれば、好きなように繰り返しを構成することが出来ます。for も while も do も break も continue も redo も要りません。シンプルでいいでしょう？

次の例はリストの要素を順番に表示します。

(define (displist x)
  (if (pair? x)
    (begin
      (display (car x))
      (newline)
      (displist (cdr x)))))

(displist '(1 5 10 20 30))

実行結果はこんな感じ。

1
5
10
20
30

大丈夫ですか？大丈夫ですね？ダメっぽかったら少し戻ってください。DrScheme のデバッガを使って、動きをトレースしてみるのも良い考え。

DrSchemeでは、DrScheme上部の[Debug]ボタンを押すことによってデバッガモードに入る。 デバッガは名前の通りプログラム中のミス(バグ)を見つけるモード。プログラムを組んで上手く動かなかったら、このデバッグモードを使うと良い。 デバッガモードに入ったら、[Step]ボタンで、作ったプログラムの一式一式を順に動作させて行ってその値が考えてたモノと一致してるかどうか調べる事が出来る。なお、DrSchemeのステップモードでは、プログラムの中の評価中の式は矢印で示され、その評価結果はDrScheme上部に表示される。

リストの各要素を１ずつ足す例も挙げときますので、じっくりどうぞ。

(define (listinc x)
  (if (null? x)
    '()
    (cons (+ 1 (car x)) (listinc (cdr x)))))

(display (listinc '(1 5 10)))

第９章・完

第１０章へ

---

※1:実際、Schemeプログラマはこの程度の繰り返し計算では第１２章で扱われている名前付きlet構文で書く場合が多い。何故なら、この章で扱われている再帰は説明モデルとしては良いが、実際はメモリ効率があんまり良くないからだ。
なお、関数factorialを名前付きlet構文で記述すれば次のようになるだろう。





(define (factorial x)
  (let loop ((n x) (result 1))
    (if (zero? n)
        result
        (loop (- n 1) (* n result)))))





名前付きlet構文の使い方は第１２章を参照の事。
また、この章に挙げられている関数を例として、自分で名前付きlet構文で書き直してみるのは、Schemeの良い練習となるだろう。

※2:亀田の考えから言うと「全く苦しみません」。ここで再帰を理解する事に苦しむのは、むしろ「他のプログラミング言語経験者だけ」だと思われる。
実は、「全くプログラミングをやった事が無い」人間にとっては、再帰の方が「繰り返し計算を実現するには一番自然な方法」なのである。なんせ、繰り返しを実現する為には同じ関数を2度、3度と呼び出せば良い、と言う構造は直球勝負で明解だからだ。あまりにも当たり前過ぎて、むしろ「プログラミングの素人が考え付きそうな方法論」である。
実際、プログラム初心者がメジャーな言語(例えばBASIC等)でまず一番最初に躓くハードルはこのテの「繰り返し計算」である。ここで初心者は不自然な、例えば「For文」等を一生懸命ガリガリ書いて、「その思考様式に慣れよう」とする。そして、人間不思議なモノで、その「不自然な考え方」に慣れてしまうと、「普通の考え方」が出来なくなってしまうのだ。
For文等の「繰り返し制御構造」は元々、あくまで「コンピュータのハードウェア上の制約」から出てきた構文であって、「考え方」自体は本質的に人間のモノではなく「機械寄りである」と言う事を忘れてはならない。
Scheme等の関数型言語はむしろ「より人間の普通の考え方」に近い形式で設計されているのだが、「普通のプログラミング言語慣れ」した人間にとっては「難しく見えてしまう」のは皮肉と言える。
亀田が全くのプログラミング初心者に「BASIC言語を勉強する」よりSchemeを薦めるのはこう言う理由である。要するに、「より自然な形で考えられてそのまま記述出来る」からだ。おそらく、大学ではじめてプログラミングを学ぶ学生対象にSchemeを使わせてたと言うMIT(マサチューセッツ工科大学)も同じように考えていたのだろう。
特に、数学を勉強する為「だけ」のプログラミング言語として考えた場合、ハードウェアの能力やメモリ制限がキツかった昔ならいざ知らず、現代で「余計なハードウェア寄りの考え方」を強制するプログラミング言語の採用、なんてのは百害あって一利無し、である。
大昔はSchemeは大型コンピュータじゃないと動かなかったしパソコン上での使用はスペック的に難があったので「BASICしか選択肢が無かった」のだが、現代はハードウェアの能力が格段に向上したので、時代錯誤はいい加減止めた方がいい時期ではある。

DrScheme

1. DrScheme での Language Pack の選択


2. Scheme の単純な式「(+ 3 2)」,　「(- 10 4)」


3. Scheme の単純な式（括弧の入れ子）


4. Scheme の単純な式 (DrScheme の定義ウインドウ)


5. 関数 area-of-disk の定義と，関数適用


6. 関数 area-of-disk，変数 PI の定義と，関数適用(1)


7. 関数 area-of-disk，変数 PI の定義と，関数適用(2)