Japanese version

Multiplication is defined as the following.

MULT := λ m n f . m (n f)

Since

2 := λ f x. f (f x)

3 := λ f x. f (f (f x)),

MULT 2 3 := (λ m n f . m (n f)) (λ f x. f (f x)) (λ f x. f (f (f x)))

= (λ n f . (λ f x. f (f x)) (n f)) (λ f x. f (f (f x)))

You can see that (n f) is copied as many as f-s.

= (λ n f . (λ x. (n f) ((n f) x))) (λ f x. f (f (f x)))

(n f) is copied the first argument (=2) times. The second argument (=3)

is replaced with n of (n f).

= (λ f . (λ x. ((λ f x. f (f (f x))) f) (((λ f x. f (f (f x))) f) x)))

= (λ f . (λ x. (λ x. f (f (f x))) (((λ x. f (f (f x)))) x)))

= (λ f . (λ x. f (f (f (((λ x. f (f (f x)))) x) x))))

= (λ f . (λ x. f (f (f (f (f (f x))) x))))

= (λ f . f (f (f (f (f (f x))))))

= 6

There is another multiplication definition.

MULT := λ m n. m (PLUS n) 0

I thought this 0 is just number 0 instead of Church number 0, when I saw

this in Wilipedia. This is not easy for beginners.

MULT 2 3 := (λ m n. m (PLUS n) (λ f x. x)) (λ f x. f (f x)) (λ f x. f (f (f x)))

= (λ n. (λ f x. f (f x)) (PLUS n) (λ f x. x)) (λ f x. f (f (f x)))

You can find the similar pattern as the first definition, (PLUS n) is

copied k-times (k = the first argument number).

= (λ n. (λ x. (PLUS n) ((PLUS n) x)) (λ f x. x)) (λ f x. f (f (f x)))

= (λ n. (PLUS n) ((PLUS n) (λ f x. x))) (λ f x. f (f (f x)))

= (PLUS (λ f x. f (f (f x)))) ((PLUS (λ f x. f (f (f x)))) (λ f x. x))

The underline part, PLUS 3 0 is 3 (= 3 + 0). Therefore,

= (PLUS (λ f x. f (f (f x)))) (λ f x. f (f (f x))).

This is 3 + 3, then,

= 6.

PDP8のプログラム技法

19 hours ago

## No comments:

Post a Comment