原始帰納関数〜3つの関数と1つの手続きから広がる世界

計算論計算可能性とラムダ計算 (コンピュータサイエンス大学講座) をSchemeで - [・ _ゝ・]日記を書くはやみずさん

原始帰納関数って？

原始帰納関数とは、3つの基本関数

零関数 $zero() = 0$
サクセッサー関数 $succ(x)=x+1$
射影関数 $p_i^n(x_1,x_2,\cdots,x_n) = x_i$

と、関数合成および原始帰納法により構成される関数のこと。

(define (zero) 0)
(define (succ x) (+ x 1))
(define (p n i)
  (lambda xs
    (ref xs (- i 1))))

射影関数 $p_i^n$ は (p n i) によって得られる。nは飾りです。

関数合成

関数 $h, g_1, g_2, \cdots , g_m$ が原始帰納関数であるとき、次のように定義される関数 $f$ もまた原始帰納関数。
$f(x_1, x_2, \cdots , x_n) = h(g_1(x_1, x_2, \cdots , x_n), g_2(x_1, x_2, \cdots , x_n), \cdots , g_m(x_1, x_2, \cdots , x_n) )$

をSchemeで

(define (combine-functions f . gs)
  (lambda xs
    (apply f
	   (map (lambda (g) (apply g xs)) gs))))

(define (c/f f . gs)
  (apply combine-functions f gs))

原始帰納法

関数 $g,h$ が原始帰納関数であるとき、次のように定義される関数 $f$ もまた原始帰納関数である。

$f(0,x_1,x_2, \cdots , x_n) = g(x_1,x_2, \dots , x_n)$
$f(y+1,x_1,x_2,\cdots ,x_n) = h(y, f(y,x_1, x_2, \cdots , x_n), x_1, x_2, \cdots , x_n)$

をSchemeで

(define (primitive-recursion g h)
  (letrec 
      ((f (lambda (y . xs)
	    (cond
	     ((= y 0) (apply g xs))
	     (else
	      (apply h (- y 1) 
		     (apply f (- y 1) xs)
		     xs))))))
    f))

(define (p/r g h)
  (primitive-recursion g h))

色々な関数

さて、原始帰納関数の登場人物が全て出揃ったところで、実際にどんな関数がつくれるのかをみてみよう。ちなみに、lambdaを直接使ったら、その時点で原始帰納関数である保証がなくなるの。つまり、

zero
p
succ
c/f
p/r

のみを使って関数を構成していかなければいけない。簡単のために、これら5つの手続きを"原始関数構成子"と呼ぶことがあるかもしれない。

プレデセッサー関数(あるいは前者関数)

$pred(0) = 0, pred(x+1) = x$

をSchemeで

(define pred
  (p/r zero (p 2 1)))

気をつけたいのは、

(define (pred x)
  ((p/r zero (p 2 1)) x))

などとしないこと。生lambda(とかlambdaを使う方法と等価な構文糖衣)は絶対禁止。手続き(関数)を生成するには、原始帰納法か関数合成しか使えないのだ！

加法関数

$add(0,x) = x = p_1^1(x)$
$add(y+1,x) = succ(add(y,x)) = succ(p_2^3(y, add(y,x), x))$

をSchemeで

(define add
  (p/r (p 1 1)
       (c/f succ (p 3 2))))

減法関数

$sub(0,x) = 0$
$sub(y+1,x) = pred(sub(y,x))$

をSchemeで

(define sub
  (c/f
   (p/r (p 1 1)
	(c/f pred (p 3 2)))
   (p 2 2)
   (p 2 1)))

addとの対象性から

(define sub
  (p/r (p 1 1)
       (c/f pred (p 3 2))))

じゃないかと思った人は鋭い。しかし、このようにsubを定義すると sub(x, y) = y - x となってしまう。これは、Schemeの書きやすさのために、教科書とパラメタの順番を入れ替えたためにそうなっている。sub(x,y) = x - y となっているほうが自然だと(はやみずは)感じるため、射影関数と関数合成を使ってパラメタの順番を入れ替えた。

和(シグマ記号)

シグマ記号は、ちょっと扱いが特殊なので原始関数構成子のみを使ったコードを生成するようなマクロを書く。一旦マクロを使うとあとから泥沼にはまる気がするが、、、

(define-macro Sigma
  (lambda (f y . xs)
    (let ((len (+ 2 (length xs))))
      `((p/r (c/f zero)
	     (c/f add
		  (p ,|len| 2)
		  (c/f ,|f|
		       (p ,|len| 1)
		       ,@(map (lambda (x) `(p ,|len| ,|x|))
			      (enum 3 len 1)))))
	,|y| ,@xs))))

(define (enum from to step)
  (let loop((ret '()) (i from))
    (cond ((> i to) (reverse ret))
	  (else
	   (loop (cons i ret) (+ step i))))))

(Sigma f y x1 x2 ...)は [tex:\sum_{z

gosh> (%macroexpand (Sigma (p 1 1) 100))
((p/r (c/f zero) (c/f add (p 2 2) (c/f (p 1 1) (p 2 1)))) 100)
gosh> (Sigma succ 100)
5050

長くなってきたので、続きは回を改めて書く（かも