[・ _ゝ・]日記を書くはやみずさん

■[Scheme][計算論] 計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座) をSchemeで

計算論 計算可能性とラムダ計算 (コンピュータサイエンス大学講座)を遅々としたペースで読み進めていて、これSchemeでやったらどうなるんだろうね、と思って始める。このエントリをインデックスにしていくよ。

1. 原始帰納関数〜3つの関数と1つの手続きから広がる世界 - [・ _ゝ・]日記を書くはやみずさん
2. 計算論をすこしずつ読んでるよ - [・ _ゝ・]日記を書くはやみずさん ※ non-Scheme

Permalink | コメント(0) | トラックバック(0) | 15:03

■[Scheme][計算論] 原始帰納関数〜3つの関数と1つの手続きから広がる世界

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

原始帰納関数って？

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

• 零関数
• サクセッサー関数
• 射影関数

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

をSchemeで

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

射影関数は (p n i) によって得られる。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))

原始帰納法

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

• 
• 

を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つの手続きを"原始関数構成子"と呼ぶことがあるかもしれない。

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

をSchemeで

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

気をつけたいのは、

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

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

加法関数

• 
• 

をSchemeで

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

減法関数

• 
• 

を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 ...)は に対応する。

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

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

Permalink | コメント(2) | トラックバック(0) | 15:03