計算機プログラムの構造と解釈 第二版 P52 問題2.6

この問題、異常に手間暇をかける必要がある。
お母さんの愛情料理、もしくはシェフのこだわりカレーのような問題。

まず、必要な解は以下の3つ

• oneの直接定義
• twoの直接定義
• 手続き「+」の定義

oneの直接定義

とにもかくにもまずはoneを求めてみる。
oneを定義するには、

(add-1 zero)
を置き換えを使って表現すればいい。そうすると、

脳内で、僕はこうやった。
zeroって手続きを返す値だから、
かえされた手続きにあえて名前をつけてやるならこんな感じ。

(define (zero-f f)
  (lambda (x) x))

んで、add-1の引数としてこいつを与えると。
(add-1 zero-f)
のは以下のように表現できる。

(add-1 zero-f)の中の表現1

(lambda (f) (lambda (x) (f ((zero-f f) x)))))

そうすると、上の式で
(zero-f f)が実行されているので、
これによって返される手続きに、(脳内で)名前をつけてやると
こんな手続きになる。

(define (zero-ff x) x)

なので以下のように表現ができる。

(add-1 zero-f)の中の表現2

(lambda (f) (lambda (x) (f (zero-ff x))))

またまた、そうすると、上の式で
(zero-ff x)が実行されているから、これって、xに置き換えられるから

(add-1 zero-f)の中の表現3

(lambda (f) (lambda (x) (f x)))

を、できたくさい。
名前をつけてやってできあがり。

(define one (lambda (f) (lambda (x) (f x))))

twoの直接定義

次は、twoでいくtwoも同じ方針で解いていくでやっていく。
だからこんな感じだ、
(add-1 one)
を置き換えを使って表現すればいい。そうすると、

脳内で、僕はこうやった。
oneって手続きを返す値だから、
かえされた手続きにあえて名前をつけてやるならこんな感じ。

(define (one-f f)
  (lambda (x) (f x)))

んで、add-1の引数としてこいつを与えると。
(add-1 zero-f)
のは以下のように表現できる。

(add-1 one-f)の中の表現1

(lambda (f) (lambda (x) (f ((one-f f) x)))))

そうすると、上の式で
(zero-f f)が実行されているので、
これによって返される手続きに、(脳内で)名前をつけてやると
こんな手続きになる。

(define (one-ff x) (f x))

なので以下のように表現ができる。

(add-1 one-f)の中の表現2

(lambda (f) (lambda (x) (f (one-ff x))))

またまた、そうすると、上の式で
(one-ff x)が実行されているから、これって、(f x)

(add-1 one-f)の中の表現3

(lambda (f) (lambda (x) (f (f x))))

お、できたくさい。
名前をつけてやってできあがり。

(define two (lambda (f) (lambda (x) (f (f x)))))

確認のための手続きdisplay-num

こんな狂った表現は何とかした方がいい。

(display zero)

とかやっても、ほとんど意味不明だ

この手続き表現の数値を、普通の数値(0とか、1とかさーそういうの)として表現するための
方法がないと、俺は狂ってしまってにゃんにゃんにゃにゃん。

こんな感じで、数値が表示される手続きを作る。

(display-num n)

zero

(define zero (lambda (f) (lambda (x) x)))

one

(define one (lambda (f) (lambda (x) (f x))))

two

(define two (lambda (f) (lambda (x) (f (f x)))))

lets帰納法！！
上記のzero、one、twoから見ても解るように、多分あれだ、
(define (zero-ff x) x)
だから、数字で表現する場合、最終的に渡すxは0だってことがわかる。
で、

(define (one-ff x) (f x))
だし、
(two-ff x)を考えると

(define two (lambda (f) (lambda (x) (f (f x)))))

(define (two-f f)
  (lambda (x) (f (f x)))

(define (two-ff x) (f (f x))

ってことなので、

上記の、このfと言う手続きfはたぶん1を足す手続きだ。
だからfこんな感じのてつづきになるであろう。

(define (f x)
  (+ x 1))

あとで、「+」を自分で定義するので、+を置き換えておく

(define add +)

だので、

(define (f x)
  (add x 1))

後でやる置き換えのためにちょこっと考えて

(define f (lambda (x) (add x 1)))

よし、脳内で逆に置換していくのだ。たとえば、(display-num one)をやったとすると
内側はこうしたい。

(display 1)

一回目の置き換え

(display one)

二回め

(display ((one-f f) x))

三回め(前述のようにxは0だから

(display ((one-f f) 0))

四回目(fを置き換える。前述のようにfは(lambda (x) (add x 1)だから)

(display ((one-f (lambda (x) (add x 1)) 0))

五回目one-fって言うのは、結局パラメータのn

(display ((n (lambda (x) (add x 1)) 0))

六回目defineで名前をつけてやりましょう。

(define (display-num n)
  (display ((n (lambda (x) (add x 1)) 0)))

できたよね。こりゃ。

手続き「+」の定義

その前に予測で、threeを作ってみる。
zero

(define zero (lambda (f) (lambda (x) x)))

one

(define one (lambda (f) (lambda (x) (f x))))

two

(define two (lambda (f) (lambda (x) (f (f x)))))

から予測するに

three

(define three (lambda (f) (lambda (x) (f (f (f x))))))

だろう。(fを増やしてみた。)
確認。

実行

(display-num three)

3と表示される。

よしよしよし。

まず、求める手続きはこんな奴

(+ n1 n2)

結果はn1 + n2したやつ。
これを具体的に考えてみると定義はこうなる。

(define (+ two one) three)

上の式、threeを、twoとoneで表現できるように置き換えていく。
一回目、threeを置換えると

(define (+ two one)
  (lambda (f) (lambda (x) (f (f (f x))))))

二回目、(f x)ってのは、前述した(one-ff x)と同じなので、そのように書き換え

(define (+ two one)
  (lambda (f) (lambda (x) (f (f (one-ff x))))))

三回目、(one-ff x)をyとすると、、、

(define (+ two one)
  (lambda (f) (lambda (x) (f (f y)))))

四回目、(f (f x))ってのは、前述の(two-ff x)とおなじなので、
(f (f y))ってのは、(two-ff y)だから、

(define (+ two one)
  (lambda (f) (lambda (x) (two-ff y))))

五回目、前述の(two-f f)の定義から
(two-ff y)は、((two-f f) y)と置き換えられるから、置き換えて

(define (+ two one)
  (lambda (f) (lambda (x) ((two-f f) y))))

六回目、前述のtwoの定義から
(two-f f)は(two f)と置き換えられるから、置き換えて

(define (+ two one)
  (lambda (f) (lambda (x) ((two f) y))))

七回目、yを元に戻す

(define (+ two one)
  (lambda (f) (lambda (x) ((two f) (one-ff x)))))

八回目、、前述の(one-f f)の定義から
(one-ff x)は、((one-f f) x)と置き換えられるから、置き換えて

(define (+ two one)
  (lambda (f) (lambda (x) ((two f) ((one-f f) x)))))

九回目、前述のoneの定義から
(one-f f)は(one f)と置き換えられるから、置き換えて

(define (+ two one)
  (lambda (f) (lambda (x) ((two f) ((one f) x)))))

十回目、ラスト。
twoをn1と、oneをn2と置き換えて

(define (+ n1 n2)
  (lambda (f) (lambda (x) ((n1 f) ((n2 f) x)))))

できた。

以下今回のまとめの実相

#!/usr/local/bin/gosh
;; -*- coding: utf-8 -*-

(define zero (lambda (f) (lambda (x) x)))

(define (add-1 n)
  (lambda (f) (lambda (x) (f ((n f) x)))))


;;oneは(add-1 zero)の結果と考えられるので、
;;作用させた感じで展開してみる。
(define one (lambda (f) (lambda (x) (f x))))

;;twoは(add-1 one)の結果と考えられるので、
;;作用させた感じで展開してみる。
(define two (lambda (f) (lambda (x) (f (f x)))))

;;threeはもはや勘で実装できる。
(define three (lambda (f) (lambda (x) (f (f (f x))))))


;;+を定義するので、先にaddに+を移しておく。
(define add +)

;;出力するための手続き
(define (display-num n)
  (display ((n (lambda (x) (add x 1))) 0)))

(define (+ n1 n2) 
  (lambda (f) (lambda (x) ((n1 f) ((n2 f) x)))))



;; main
(define (main args)
  
  (newline)
  (display "(display zero)とかやっても出力はシャンとしない。")(newline)
  (display "(display zero): ")
  (display zero)(newline)
  (display "(display zero): ")
  (display-num zero)(newline)


  (newline)
  (display "「one」を定義")(newline)
  (display "(display-num one): ")
  (display-num one)(newline)

  (newline)
  (display "「two」を定義")(newline)
  (display "(display-num two): ")
  (display-num two)(newline)

  (newline)
  (display "(display-num (add-1 one)): ")
  (display-num (add-1 one))(newline)
  (display "(display-num three): ")
  (display-num three)(newline)

  (newline)
  (display "加算手続き「+」を定義")(newline)
  (display "(display-num (+ two two)): ")
  (display-num (+ two two))(newline)


  (newline)
0)

実行

(display zero)とかやっても出力はシャンとしない。
(display zero): #<closure zero>
(display zero): #<closure (add-1 add-1)>

自分で作った表示用の手続きにかましてやる
(display-num zero): 0

「one」を定義
(display-num one): 1

「two」を定義
(display-num two): 2

(display-num (add-1 one)): 2
(display-num three): 3

加算手続き「+」を定義
(display-num (+ two two)): 4

できた、、、長すぎるよ。。。。