計算プロセス(計算過程)の種類に再帰的プロセスと反復的プロセスがあります。

他の多くの言語では反復的プロセスは繰り返し構文で書くのが当たり前ですが、 Schemeではどちらも「再帰的手続き」で書く事ができます。

	再帰的プロセス	反復的プロセス
他言語	再帰的手続き(または繰り返し構文に書き直す)	繰り返し構文
Scheme	再帰的手続き	再帰的手続き

Schemeプログラマにとって再帰は最も自然な考え方です。ところがこれは他の言語のプログラマにとっては非常識に見えるようです。他の言語のプログラマの文章を引用してみましょう。

結論として、階乗の計算には、再帰を使う必要は全然ないということである。 まあ、再帰を使っても計算できないことはない。そういう程度のことを、再帰の見本みたいに紹介する本とかがあるが、あれは完全に狂った世界である。

藤原博文「Cパズルプログラミング 再帰編」 http://karetta.jp/book-node/cpuzzle-recursion/001636

また、こんなことを主張する他の言語のプログラマもいます。

本質的に再帰的なものは再帰で、本質的に反復的なものはループ(繰り返し)で書くべき

これに対してSchemeプログラマはこんなことを思っています。

そんなの(再帰的プロセスでも反復的プロセスでも)どっちも「再帰的手続き」で書けるじゃん。何を騒いでるの?

Schemeの言語仕様を知ったとき、他の言語のプログラマはこう思うことでしょう。

繰り返し構文はdoしかないの? それで使い物になるの?

心配には及びません。Schemeプログラマはdoなんか使わないからです ^{使いもしないdoがなぜSchemeの言語仕様にあるの? と疑問に思うかも知れません。無駄を徹底的に排除することがSchemeの言語仕様の理想ですが、こうした“盲腸”とでも呼ぶべき無駄も残っていたようです。}。 繰り返しを書こうとしてdoの構文を覚えるのは無駄な努力です。心配せずに再帰を書きましょう。

(実はSchemeではdoも再帰的手続きとして書かれています。doを使っていても、知らず知らずのうちに再帰を使っていることになります)

再帰的プロセスと反復的プロセス

計算プロセス(計算過程)の種類に再帰的プロセスと反復的プロセスがあることを冒頭に述べました。

なぜ他の多くの言語では反復的プロセスを繰り返し構文で書くのが当たり前なのでしょうか? それどころか、実装上の制限から再帰的プロセスを反復的プロセスに書き直してループで書くことすらあります。

Schemeではどちらも「再帰的手続き」で書く事ができます。

再帰的手続きとは何でしょうか?

• 再帰的手続きとは自分自身を手続き適用する手続きである

他の手続きを適用する代わりに自分自身を適用しているだけであり、ごく普通の手続きに過ぎません。

他の多くの言語で反復的プロセスをループ(繰り返し)構文で書かざるを得ないのは、末尾再帰を最適化していないからです。末尾再帰の最適化については本節の後半で説明します。

再帰的プロセスの例

「Cパズルプログラミング再帰編」の例にあった階乗計算を数式で表現するなら、

と書けます。階乗計算を再帰的プロセスとして計算してみましょう。

一つ前まで出来ていることにする

ここで一つ前まで出来ていることにするという法則を導入します。 すると階乗計算の数式は次の式に変形できます。

結論としては、階乗計算とはn-1の階乗にnを掛けたものです。

「計算機プログラムの構造と解釈第二版」ではこの性質を利用して、階乗を計算するfactrial手続きを次の通りに書いています。

 (define (factorial n)
   (if (= n 1)
       1
       (* n (factorial (- n 1)))))

factorial手続きはその最後に自分自身を適用しています。factorial手続きは「再帰的手続き」です。

置き換えモデルで計算を確かめる

factorial手続きがどうやって階乗を計算するかは置き換えモデルで確かめることができます。

 (factorial 4)
 ↓
 (* 4 (factorial 3))
 ↓
 (* 4 (* 3 (factorial 2)))
 ↓
 (* 4 (* 3 (* 2 (factorial 1))))
 ↓
 (* 4 (* 3 (* 2 1)))

「一つ前の階乗計算」に順次置き換えていくことで4の階乗が計算できます。

これまで見たとおり、再帰的プロセスの例は対象となる問題の構造がすでに再帰的であった(「一つ前まで出来ている」ことにできる)と言えます。再帰的プロセスは素直に再帰的手続きとして書くことができます。

反復のための特別の構文を導入しなければならない欠点はSchemeにはない

他の言語では反復プロセスを表現するには特別の構文を必要としますが、Schemeにはこの欠点はありません。反復プロセスも再帰的プロセスもどちらも手続き呼び出しで表現できます。

---

by えんどうやすゆき | Permalink | Comments(2) | Trackbacks(0) 

反復的プロセスの例

これまで例にあげた階乗計算は反復的プロセスに書き直すことができます。他の言語では反復的プロセスをループ(繰り返し)で書きますが、Schemeでは反復的プロセスも再帰的手続き、つまり自分自身を適用する手続きとして書くことができます。

階乗計算は以下の計算に分解することができます。

1. nを1づつ減少させていく
2. 今までの積を保存しておく

1づつ減少させる引数nと、今までの積を保存しておく引数ansを引数にとる補助的な手続きfact-iterを書くことで上記の計算が実現できます。

  (define (fact n)
    (define (fact-iter n ans)  
      (if (zero? n)
        ans
        (fact-iter (- n 1) (* n ans)))) ; 最後に自分自身を呼び出している
    (fact-iter n 1))

fact-iterは最後に自分自身を呼び出しています。つまりfact-iterは再帰的手続きです。

たとえば(fact 5)を計算すると、

  (fact 5)
  ((fact-iter 5 1))
  (((fact-iter 4 5)))
  ((((fact-iter 3 20))))
  (((((fact-iter 2 60)))))
  ((((((fact-iter 1 120))))))
  (((((((fact-iter 0 120)))))))
  ((((((120))))))
  (((((120)))))
  ((((120))))
  (((120)))
  ((120))
  (120)
  120

となります。途中の積を保存しておくansという引数を与えたことで、最後に自分自身(fact-iter)を呼び出した後は値を返すだけになっています。fact-iterから返ってきた値は順に呼出元のところへ返っていき、一番最初に呼び出したところまで値が返されていきます。この間では値に変化はありません。下のように一気に最初の呼出元に値を返したいものです。

  (fact 5)
  ((fact-iter 5 1))
  (((fact-iter 4 5)))
  ((((fact-iter 3 20))))
  (((((fact-iter 2 60)))))
  ((((((fact-iter 1 120))))))
  (((((((fact-iter 0 120)))))))
  120

また、残り仕事を取っておくためのスペースも無駄です。下のように無駄なスペースのないプロセスになって欲しいところです。

  (fact 5)
  (fact-iter 5 1)
  (fact-iter 4 5)
  (fact-iter 3 20)
  (fact-iter 2 60)
  (fact-iter 1 120)
  (fact-iter 0 120)
  120

実はSchemeでは上記の最適化を行うことが必須になっています。これを末尾再帰の最適化と呼んでいます。

以下の2つの条件を満たすときを末尾呼び出しと呼びます。

• ある関数が別の関数を呼び出している
• 別の関数の戻り値がそのままその関数の戻り値になる

末尾呼び出しで自分自身を呼び出しているときを末尾再帰と言います。fact-iterは自分自身を呼び出し、かつその再帰呼び出しの戻り値がそのまま戻り値になっています。したがってfact-iterは末尾再帰手続きです。

この末尾再帰の最適化という機能があるとfactの呼出しのプロセスは以下のようになります。

  (fact 5)
  (fact-iter 5 1)
  (fact-iter 4 5)
  (fact-iter 3 20)
  (fact-iter 2 60)
  (fact-iter 1 120)
  (fact-iter 0 120)
  120

fact-iterの呼出しが終わった後は答えの値が直接呼出元にまで返ってきています。

Scheme処理系では末尾再帰が必ず最適化されるので、反復的プロセスも再帰的手続きとして書くことができます。これがSchemeプログラマがdoを使わない理由、つまりSchemeでは繰り返し構文が必要でない理由です。

---

by えんどうやすゆき | Permalink | Comments(0) | Trackbacks(0) 

再帰的データ構造としてのconsセル

「すべてリストである」で見たように、consセルは再帰的なデータ構造になっています。carとcdrを再帰的に適用することでどんな構造のconsセルでも処理することができます。

 (define (odd-sigma ls)
   (cond ((not (pair? ls))                    ;; リストが空か?
           0)                                 ;; 0を返す
         ((odd? (car ls))                     ;; 先頭要素が奇数か?
           (+ (car ls) (odd-sigma (cdr ls)))) ;; 先頭要素と残りの奇数要素の総和
         (else                                ;; 先頭要素が偶数
           (odd-sigma (cdr ls)))))            ;; 残りの奇数要素の総和

リスト要素が奇数のものだけの総和を計算するodd-sigma手続きは、carとcdrを再帰的に適用することで上記のように書けました。ただしodd-sigmaはちょっと不恰好です。もっとエレガントに書けないでしょうか?

Gaucheで外部ライブラリを使う

Gaucheにはモジュールと呼ばれる外部ライブラリを利用する機能があります。

 (use モジュール名)

use式を書くことでモジュールを利用することができます。Gaucheでは数多くのモジュールが提供されています。ここではリスト処理に便利なsrfi-1モジュールを使うことにします。

 gosh> (use srfi-1)

これでsrfi-1モジュールが使用できるようになりました。

再帰が見えなくなる

odd-sigma手続きをエレガントに書き直すために、srfi-1モジュールに含まれるfilter手続きを導入してみましょう。

 (filter 判定式 リスト)

filter手続きは、リスト中の要素を判定式で判定し、真の要素だけのリストを返します。

奇数の要素だけのリストを得るには、

 gosh> (filter odd? (list 0 1 2 3 4 5))
 (1 3 5)

odd?手続きで奇数かどうか判定させれば良いのです。

filterを使ってodd-sigmaを書き直してみましょう。

 gosh> (define (odd-sigma ls)
         (apply + (filter odd? ls)))
 odd-sigma
 
 gosh> (odd-sigma (list 0 1 2 3 4 5))
 9

+手続きがリストに対してそのまま適用できないことに注意してください。

 gosh> (+ (list 1 3 5))
 *** ERROR: number required, but got (1 3 5)
 Stack Trace:
 _______________________________________

+手続きをリストに適用するにはapplyを使います。

 gosh> (apply + (list 1 3 5))
 9

filterを導入することで、odd-sigma手続きは一見再帰を使っていないかのように見えるようになりました。では本当に再帰が使われていないのでしょうか?

「計算機プログラムの構造と解釈第二版」ではfilter手続きは次の通りに書かれています。

 (define (filter predicate sequence)
   (cond ((null? sequence) nil)
         ((predicate (car sequence))
          (cons (car sequence)
                (filter predicate (cdr sequence))))
         (else (filter predicate (cdr sequence)))))

filter手続きはリストに対してcar、cdrを再帰的に適用し、自分自身を呼び出している再帰的手続きです。

filter手続きを導入したことで、実際には再帰を使っているにもかかわらず、まるで再帰していないかのように書くことができました。

上記のfilter手続きが、再帰を素直に使ったodd-sigma手続きに似ていることに気づいたかも知れません。

 (define (odd-sigma ls)
   (cond ((not (pair? ls))                    ;; リストが空か?
           0)                                 ;; 0を返す
         ((odd? (car ls))                     ;; 先頭要素が奇数か?
           (+ (car ls) (odd-sigma (cdr ls)))) ;; 先頭要素と残りの奇数要素の総和
         (else                                ;; 先頭要素が偶数
           (odd-sigma (cdr ls)))))            ;; 残りの奇数要素の総和

filter手続きはodd-sigma手続きのうち、任意の判定式を与えて要素を取り出す部分を一般化したものとも考えられます。

現実的なプログラミングでは再帰を明示的に書くことはむしろ稀です。filter手続きを始めとする高階手続きを使うことで、あたかも再帰を使っていないかのように書くのが普通です。

高階手続きとは手続きを引数にとる手続きのことです。filterと並んで多く使われる高階手続きとしてmap、foldがあげられます。

---

by えんどうやすゆき | Permalink | Comments(2) | Trackbacks(0) 

繰り返しとしてのリスト

「すべてリストである」でリストがconsセルであるということを説明しました。

 (list 0 1 2 3 4)

は、

 (cons 0 (cons 1 (cons 2 (cons 3 (cons 4 ())))))

でした。ここで上の式のconsを、+に変えたらどうなるでしょうか?

 (+ 0 (+ 1 (+ 2 (+ 3 (+ 4 0)))))

consを+に変えることで、(list 0 1 2 3 4)を使って0から4までの数の和を表現することができます。

もう一つ例をあげます。階乗計算の例をもう一度見てみましょう。

階乗計算をエレガントに書き直すために、srfi-1モジュールに含まれるiota手続きを導入してみます。

 gosh> (use srfi-1)

これでsrfi-1モジュールが使えるようになりました。

 gosh> (iota 5)
 (0 1 2 3 4)

iota手続きは0から(n - 1)までの数字のリストを生成します。(iota 5)は(list 0 1 2 3 4)を生成します。

また、iota手続きの2番目の引数として、開始の数を与えることもできます。

 gosh> (iota 5 1) ;; 1から5まで
 (1 2 3 4 5)

iota手続きを使って階乗計算を書いてみましょう。

 gosh> (define (factorial n)
         (apply * (iota n 1)))
 factorial

(iota n 1)で1からnまでのリストを生成します。applyはリスト(list 1 2 3 4 5)に*手続きを適用します。

 gosh> (factorial 5)
 120

*手続きは複数の引数をとり、その引数すべてを乗算します。

+手続きのときと同様に、*手続きがリストに対してそのまま適用できないことに注意してください。

 gosh> (* (iota 5 1))
 *** ERROR: number required, but got (1 2 3 4 5)
 Stack Trace:

*手続きをリストに適用したいときapplyを使います。

 gosh> (apply * (iota 5 1))
 120

最初に再帰的プロセスや反復的プロセスの例を見てきましたが、リストを使って繰り返しを表現することもできるのです。

---

by えんどうやすゆき | Permalink | Comments(0) | Trackbacks(0)