Scheme:lambdaだけで再帰

Scheme:lambdaだけで再帰

質問

Scheme:初心者の質問箱に出た質問:

例えば 1から n までの自然数の和(wa)から n を引いた数を返す関数(wa-n)を考えます。 まず1から n までの自然数の和は

(define (wa n)
  (if (>= 0 n)
      0
      (+ n (wa (- n 1)))))

なので wa-n は

(define (wa-n n)
  (if (>= 0 n)
      0
      (- (wa n) n)))

で、4 を渡すと (4+3+2+1)-4=6 が返ってきます。(そんなんwaに(n-1)を渡したら返ってくる数と同じじゃん、というのはとりあえず) これをラムダを使って一つの関数にしようとすると

(define (wa-n2)
  (if (>= 0 n)
      0
      (- 
       (lambda (i)
         (if (>= 0 i)
             0
             (+ i (.....(- n 1)))));※
         n)
       n)))

というようになると思いますが、※の行の (.....) が思い付きません。この様な場合、局所関数を定義するか、letrec を使うしか(或いは名前付きletとかdoを使うとか)方法は無いのでしょうか? ラムダの中だけで再帰は不可能なのでしょうか?

実用上は、letrecなどを使うのが適切ですが、lambdaだけで再帰を書くことが可能か不可能かという話をするなら、可能です。

最初のアイディア

問題の核心は、waの定義をwa自身を参照せずに書きたい、 つまり以下の定義で【※】の部分をwa無しで何とか表せないか、ということです。

(define wa
  (lambda (n)
    (if (>= 0 n)
      0
      (+ n (【※】 (- n 1)))))

とりあえず、【※】の部分がどうなるかわからないので、これを引数で与えてみます。

(lambda (f)
  (lambda (n)
    (if (>= 0 n)
      0
      (+ n (f (- n 1))))))

この関数は関数を返す関数です。引数にwaが渡されれば:

((lambda (f)
   (lambda (n)
     (if (>= 0 n)
       0
       (+ n (f (- n 1))))))
  wa)

返される関数はこうなります:

(lambda (n)
  (if (>= 0 n)
    0
    (+ n (wa (- n 1)))))

これは元々欲しかったwaの定義ですね。つまり上の(lambda (f) ...)は、 waを作る関数なので、make-waと呼ぶことにします。

(define make-wa
  (lambda (f)
    (lambda (n)
      (if (>= 0 n)
        0
        (+ n (f (- n 1)))))))

make-waはwaを渡せばwaを作ってくれるので、 waの定義はこう書けるはず…

;; 動かない
(define wa
  (make-wa wa))

と言いたいところですが、このままではまだ動きません。(make-wa wa)を評価するにはまず waの値が求まらないとならないのに、waの値は(make-wa wa)が戻ってこないとわからない。 鶏と卵の問題になってしまいます。

合わせ鏡

ここで一工夫します。今仮に、ある関数Xがあって、XにX自身を適用するとwaが返ってくる、 そんなXを作れるでしょうか。

(X X) => wa

もう一度waの定義を見直してみます。そして、waを再帰的に呼び出しているところを、 (X X)に置き換えてみましょう。

(define wa
  (lambda (n)
    (if (>= 0 n)
      0
      (+ n ((X X) (- n 1))))))

Xが何だかはまだわからないけれど、上でwaからmake-waを作ったのと同じように、 「Xを引数に受け取ってwaを返す」関数make-wa2を書くことができます。

(define make-wa2
  (lambda (X)
    (lambda (n)
      (if (>= 0 n)
        0
        (+ n ((X X) (- n 1)))))))

つまり、

(make-wa2 X) => wa

ということです。ところで、もともとXというのは次の性質を持っていました。

(X X) => wa

ということは、make-wa2もXが満たすべき性質を満たしていることになります。 つまり

(make-wa2 make-wa2) => wa

になります。

狐につままれたような気になるかもしれませんが、 次のコード片を実行して、waが確かに動作することを確認してみましょう。

(define make-wa2
  (lambda (X)
    (lambda (n)
      (if (>= 0 n)
        0
        (+ n ((X X) (- n 1)))))))

(define wa (make-wa2 make-wa2))

make-wa2の定義からはwaもmake-wa2も参照されていないので、make-wa2自体を 定義のlambda式に置き換えることも可能です。そうやって置き換えると、 waを次のとおり定義できます (これも実行して確かめられます):

(define wa
  ((lambda (X)
     (lambda (n)
       (if (>= 0 n)
         0
         (+ n ((X X) (- n 1))))))
   (lambda (X)
     (lambda (n)
       (if (>= 0 n)
         0
         (+ n ((X X) (- n 1))))))))

これで、「名前を再帰的に参照することなく、再帰関数を定義する」という目的が達成されました。

この不思議な定義は、こんなふうに考えることもできます。 (make-wa wa) ≡ wa であるということは、 waの箇所を(make-wa wa)で置き換えられるということです。 つまり、wa ≡ (make-wa wa) ≡ (make-wa (make-wa wa)) ≡ (make-wa (make-wa (make-wa wa))) … とどこまでも展開できます。 この「無限の循環」をどうにかして有限の関数で表したいわけです。

合わせ鏡は、自分自身に自分を写すことで、有限の鏡の中に無限に続く鏡像を作り出せます。

(X X) ≡ wa、というのが、合わせ鏡に自分を写しているように思えませんか。

そしてYになる

上の手順はどんな再帰関数にも使えます。つまり、

このパターンを手続きとして抽象化できないでしょうか。つまり、

(define wa
  (lambda (n)
    (if (>= 0 n)
      0
      (+ n (wa (- n 1)))))

のような再帰関数が欲しいとき、waを引数にしたlambda式、いわば「waのタネ」:

;; waのタネ
(lambda (wa)
  (lambda (n)
    (if (>= 0 n)
      0
      (+ n (wa (- n 1))))))

を受け取って、うまい具合に再帰呼び出しをしてくれる関数を返すような関数です。

上記waの部分を(X X)に直接「書き換える」かわりに、 引数waに (lambda (x) ((X X) x)) という関数を渡してやれば、 (wa (- n 1)) の部分が ((lambda (x) ((X X) x)) (- n 1))、すなわち ((X X) (- n 1))になります。

ここでは、まだXが何だかわからないので、Xを引数で受け取るlambdaでくるんでおきます。

(define make-wa3
  (lambda (X)
    ((lambda (wa)                 ; ここがwaのタネ
       (lambda (n)                ;  ↓
         (if (>= 0 n)             ;  ↓
           0                      ;  ↓
          (+ n (wa (- n 1))))))   ;  ↓
     (lambda (x) ((X X) x)))))

(X X) => wa で、 (make-wa3 X) => wa ですから、make-wa3はXとしても使えます。 すなわち

(define wa (make-wa3 make-wa3))

になります。上のmake-wa3とこの定義を実行して確かめてみてください。

上のmake-wa3は「waのタネ」を直接含んでいましたが、それを引数で受けとるようにしてみましょう。

(define make-recursive
  (lambda (f)
    (lambda (X)
      (f (lambda (x) ((X X) x))))))

つまり、make-wa3 ≡ (make-recursive waのタネ) ということです。

wa ≡ (make-wa3 make-wa3) を make-recursiveで書けば

wa ≡ ((make-recursive waのタネ) (make-recursive waのタネ))

になりますが、「waのタネ」がどんな関数でもこれで再帰ができるわけなんで、 次の関数を定義しておけば:

(define make-recursive2
  (lambda (f)
    ((make-recursive f) (make-recursive f))))

wa ≡ (make-recursive2 waのタネ) と書けることになります。これで、当初の目標である 「『waのタネ』から再帰呼び出しをするwaを作り出す」が実現できました。

上のmake-recursive2の定義中のmake-recursiveを元のlambda式に置き換えれば、 次の定義が得られます。

(define make-recursive2
  (lambda (f)
    (((lambda (f)
        (lambda (X)
          (f (lambda (x) ((X X) x)))))
      f)
     ((lambda (f)
        (lambda (X)
          (f (lambda (x) ((X X) x)))))
      f))))

((lambda (f) ほにゃらら) f)の部分は ほにゃらら と同じなので簡略化すると:

(define Y
  (lambda (f)
    ((lambda (X) (f (lambda (x) ((X X) x))))
     (lambda (X) (f (lambda (x) ((X X) x)))))))

この関数Yを使えば、waは「waのタネ」から定義できます。

(define wa
  (Y
    (lambda (wa)                 ; waのタネ
      (lambda (n)                ;  ↓
        (if (>= 0 n)             ;  ↓
          0                      ;  ↓
          (+ n (wa (- n 1))))))));  ↓

この、「再帰関数のタネ」から再帰関数を作り出す関数を、Yコンビネータと呼びます。

最初に書いたように、現実のプログラムを書く場合はdefineもletrecもあるので Yコンビネータをわざわざ使う意味はありません。ただ、lambda抽象(lambda式による関数定義)と 関数適用さえあれば、任意の再帰関数が書けるという事実は、 ラムダ計算がチューリングマシンと同等の力を持つことにつながっています。


Last modified : 2018/05/31 17:19:28 UTC