(define -ayalog '())

括弧に魅せられて道を外した名前のないプログラマ

SICPを読む_(13)2章_データによる抽象の構築(p49-59)

Scheme SICP

明日と言って、「明日」書いた覚えがない程度にダメ人間。
さて、今日は暇なのでにゅるっと頑張る。

2.1.2 抽象の壁(p49-50)

抽象の壁、ということでシステムの異なるレベルを隔離するものとして表現されている。
有理数の演算について考えた場合、add-rat,sub-rat,mul-rat,div-rat及びequal-rat?だけを使って、有理数そのものを操作する公共用の手続きとなる。add-ratなどの手続きは構成子と選択子だけを使って実装されている為、更に下のレベルにある対などを意識する必要がない。

  • 単純な考え方には多くの長所がある、ひとつはプログラムの維持、修正が容易であること
    • 有理数の例では既約にまで簡約する問題を、有理数を構成するときではなく、その部分を取り出すときに行うことができるのを示している
    • 有理数の構成子と選択子の内部が変更されても、それを使用している手続きに影響はない

問題2.2(p50)

解いたのはGitHubに上がってます。 SICP/Chapter-2
点の構成子とx座標・y座標それぞれの選択子、それと線分の構成子に、始点・終点の選択子を書いた。
あとはそれをよしなにして上げるだけ。始点のx座標と終点のx座標を足して2で割ってー、みたいな感じで中間点出せたと思ってる。

問題2.3

2.2を使いたくなるだろうって書いてある割に、使ってない気がする。
点の構成子と選択子は使いましたが。そんなに難しくなかった。

2.1.3 データとは何か(p51-)

なんか深いテーマきた。「XXとは何か」ってわくてかする。

  • 「与えられた選択子と構成子で実装されているもの」というのでは不十分
    • 有理数xをnとdから構成したのなら、xからnumerとdenomで取り出して割ったものはnをdで割ったものと同じになる保証がいる
  • データは選択子と構成子と、これらの手続きを有効な表現とするために満たすべき条件とで定義される

なので、次の手続きでcons,car,cdrは実装できる。

(define (cons x y)
  (define (dispatch m)
    (cond ((= m 0) x)
	  ((= m 1) y)
	  (else (error "Argument not 0 or 1 -- CONS" m))))
  dispatch)

(define (car z) (z 0))
(define (cdr z) (z 1))

これで「真の」データ構造を使う実装とは区別できない、っていうのもなかなか凄いなと感じてしまいます。

問題2.4(p52)

ん。これは簡単。証明せよ、って何したらいいんか分からんけど。
元の形はこれで(car (cons x y))がxになることを証明する感じ。

(define (cons x y)
  (lambda (m) (m x y)))
(define (car z)
  (z (lambda (p q) p)))

まず、(cons x y)だけど具体的にxに10、yに20入れたら次のラムダ式になる。(lambda (m) (m 10 20))。
これが(car z)のzになるので、次のようになる。

((lambda (m)
   (m 10 20))
 (lambda (p q) p))

それでこうなる。

((lambda (p q) p)
 10 20)

だから10になるので、xとなりますよっと。
cdrについてはGitHubの方参照。

問題2.5(p52)

これもGitHubでいいかなん。
単純に(cons 3 7)が17496になって、carが3、cdrが7になれば良いです。

問題2.6(p52)

チャーチ数に関してはこの辺で書いたのでいいかな。
答えもGitHubに上がっております。

2.1.4 拡張問題:区間算術演算

このへん懐かしいなーと思いながらもう思い出せないので苦労しました。(抵抗の話)

問題2.7〜2.16(p53-54)

2.9,2.14,2.15,2.16はスキップ。(何言ってるのか分かんない…)
その他は特に難しくないのでGitHub。

2.2 階層データ構造と閉包性

箱とポインタ記法は、結構色んなところで見かけるので、ちょっと今更感。(けど本家本元はSICPなんでしたっけ？)
ということで合成データの閉包性の重要さを勉強するよ。

  • 閉包性
    • consは数値だけでなく、対も組み合わせることができる
    • 演算(cons)を使って組み合わせた結果(対)を同じ演算(cons)で組み合わせられる
      • このとき閉包性を満足する
    • 閉包によって階層的構造をつくることができる

2.2.1 並びの表現

  • 対を使って作ることの出来る有用な構造は並び(データオブジェクトの順序付けられた集り)
  • 入れ子のconsで作られた対の並びをリストという

SICPでは「リスト」と「リスト構造」を使い分けていて、前者はリスト終わりの印(nil)で終端した対の値、後者はリストだけでなく対で作られた任意のデータ構造のことらしい。
で、何故か(?)この辺からnilという言葉が出てくるけど、僕はGaucheで書いてるのでプログラム中のnilは'()に置き換えている。*1
ちなみにnilとか'()については、血で血を洗う争いがあったとかないとか（ない

[追記]
SICPでnilが出てるのはp57に解説あった。。。

対の鎖を愁嘆するのに使うnilの値は要素の1つもない並び、空リストと考えてよい。nilという言葉はラテン語の「何もない」という意味の語nihilの短縮形である。

クォートを説明していないので、空リストを'()と表現していないだけみたい。2.3からはnilではなくて'()と書くよって書いてある。。

リスト演算

「cdrダウン」「consアップ」ってなんか技名みたいでカッコいい。
ということで特に難しいことは何もないのでするするっと。

問題2.17(p58)

(define (last-pair ls)
  (cond ((null? (cdr ls)) ls)
	(else (last-pair (cdr ls)))))
(last-pair '(1 2 3))

にょろっと。

問題2.18(p58)

うっかりnamed-letを使ってしまうのですが、SICP的な書き方で。

(define (reverse ls)
  (define (iter l rl)
    (if (null? l)
	rl
	(iter (cdr l) (cons (car l) rl))))
  (iter ls '()))

問題2.19(p58)

難しくないよね。

(define (first-denomination coin-values)
  (car coin-values))

(define (except-first-denomination coin-values)
  (cdr coin-values))

(define (no-more? coin-values)
  (null? coin-values))

問題2.20(p59)

正直書いてみたけど汚いなーって思った。
最初の1つ目の引数でリストから取得する偶奇性を変えるっていうのがなんともスマートにならない気がして。

(define (same-pariry . args)
  (define (iter ls pred answer)
    (cond ((null? ls) answer)
	  ((pred (car ls))
	   (iter (cdr ls) pred (cons (car ls) answer)))
	  (else
	   (iter (cdr ls) pred answer))))
  (reverse (iter args
		 (if (odd? (car args)) odd? even?)
		 '())))

とりあえず、ここまでー。

*1:Common LispのnilとSchemeの'()は同じではないぽいけど、とりあえずSICPの問題は置き換えで動くのでいいや