λ

Chapter 2 Building Abstractions with Data

2.1 Introduction to Data Abstraction

2.1.1 Example: Arithmetic Operations for Rational Numbers

データを抽象化させるとかそんな感じ．例では，二つの整数 n, d の対（pairs）をデータ（structure）として扱い，constructor として make-rat を，selector として numer, denom を定義している．

2.1.2 Abstraction Barriers

abstraction barriers は抽象化の度合い（レベル）のようなもの．
Q. 何故，データを抽象化させるんですか？
A. This simple idea has many advantages. One advantage is that it makes programs much easier to maintain and to modify.

2.1.3 What Is Meant by Data?

うーん，message passing の重要性がまだよく掴めていない．

Exercise 2.6.

Church numerals．これは，ラムダ計算のなかで扱われる項目．wikipedia の当該項目を読んでみても案の定さっぱりなので，ヒントを参考にやってみる．
(Hint: Use substitution to evaluate (add-1 zero)).
以下，ラムダ計算の気分を味わうために，lambda をλと表記することにします．

(define zero (λ (f) (λ (x) x)))

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

(add-1 zero)
;; add-1 を展開する．
-> ((λ (n) (λ (f) (λ (x) (f ((n f) x))))) zero)
;; zero を展開する．
-> ((λ (n) (λ (f) (λ (x) (f ((n f) x))))) (λ (f) (λ (x) x)))
;; 展開された add-1 が評価され，引数 n として，展開された zero を受け取る．
-> (λ (f) (λ (x) (f (((λ (f) (λ (x) x)) f) x))))
;; 受け取った部分（引数 n だった部分）は f を引数とする関数として評価され，
-> (λ (f) (λ (x) (f ((λ (x) x) x))))
;; 更に，((λ (x) x) x) が再帰的に評価され，
-> (λ (f) (λ (x) (f x)))
;; これ以上評価される部分はないので，このラムダ式が返り値となる．
(λ (f) (λ (x) (f x)))

よって，two も同様に考え，

(define one (λ (f) (λ (x) (f x))))     ; ∵ one = (add-1 zero)
(define two (λ (f) (λ (x) (f (f x))))) ; ∵ two = (add-1 one)

となる．以上のことから Church numerals（C:n）は帰納的に次のように表される．

C:0 = (λ (f) (λ (x) x))
C:1 = (λ (f) (λ (x) (f x)))
C:2 = (λ (f) (λ (x) (f (f x))))
...
C:n = (λ (f) (λ (x) (f ... (f x)...))) ; x に対して再帰的に n 回 f を適用

また，(add-1 zero) の評価過程や C:n の一般形から，C:n に関する次のような性質が考察でき，

((λ (n) (λ (f) (λ (x) ((n f) x)))) C:n)
= (λ (f) (λ (x) (f ... (f x)...)))    ; x に対して再帰的に n 回 f を適用

そのことから，

C:m+n = (λ (f) (λ (x) (f ... (f x)...))) ; x に対して再帰的に m + n 回 f を適用
= (λ (f) (λ (x) (f ... ((n f) x)...))) ; ((n f) x) に対して再帰的に m 回 f を適用
= (λ (f) (λ (x) ((m f) ((n f) x))))

となる．従って，

(define (+ m n)
  (λ (f) (λ (x) ((m f) ((n f) x)))))

何故か数学っぽくなる．数学嫌いなのに＞＜

hoge

勉強の仕方とか，ブログへの載せ方がまだ定まらないなあ．chapter 1 は丸々載せちゃってるし．gist とか tumblr あたりに exercise の部分だけちまちま貼りつけていく方がいいんだろうか．

まあ，取り敢えずは，気が向いたときにこのブログに上げることにしよう．

hogehoge

と，ぐだぐだ書いていたら，github に exercise 毎に .scm に小分けにして上げている人を発見してみたり．