第9回SICP勉強会

SICP

今日から2章。勉強会中に軽くメモって、終了と同時に投下するというパターン

2.1 データ抽象入門

  • 合成データの要素としてのcons, car, cdr
2.1.1 有理数の算術演算
  • print-ratで#が表示されるのは最後のdisplayの返り値として#が返ってくるから
2.1.2 抽象の壁
  • データ抽象を使う（上の）プログラムを、データ抽象を実装する（下の）プログラムから分けている。
    • 下の階層の実装は知らずに、インターフェースさえわかっていればいい
  • 各レベルの手続きは、抽象の壁を定義し、異なるレベルを接続するインターフェースである。
2.1.3 データとは何か
  • 一般に、データは選択子と構成子と、、これらの手続きを有効な表現とするために満たすべき条件とで定義されると思ってよい。

問題

問題2.1
;; 有理数を既約にまで簡約化する
;; 有理数の足し算
(define (add-rat x y)
  (make-rat (+ (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

;; 有理数の引き算
(define (sub-rat x y)
  (make-rat (- (* (numer x) (denom y))
               (* (numer y) (denom x)))
            (* (denom x) (denom y))))

;; 有理数の掛け算
(define (mul-rat x y)
  (make-rat (* (numer x) (numer y))
            (* (denom x) (denom y))))

;; 有理数の割り算
(define (div-rat x y)
  (make-rat (* (numer x) (denom y))
            (* (denom x) (numer y))))

;; 有理数の等価性テスト
(define (equal-rat? x y)
  (= (* (numer x) (denom y))
     (* (numer y) (denom x))))

;; 有理数の表現
(define (make-rat n d) (cons n d))
(define (numer x) (car x))
(define (denom x) (cdr x))

(define (print-rat x)
  (newline)
  (display (numer x))
  (display "/")
  (display (denom x)))

(define (gcd a b)
  (if (= b 0)
      a
      (gcd b (remainder a b))))


;; 有理数が正なら分子、分母ともに正
;; 有理数が負なら分子だけを負とする
(define (make-rat n d)
  (let ((g (abs (gcd n d))))
     (if (< d 0)
         (cons (/ (- n) g) (/ (- d) g))
         (cons (/ n g) (/ d g)))))

(define (check n d)
  (print-rat (make-rat n d)))

(check 6 9)
;; gosh> 
;; 2/3
(check 6 -9)
;; gosh> 
;; -2/3
(check -6 9)
;; gosh> 
;; -2/3
(check -6 -9)
;; gosh>  ;; 2/3
問題2.2
;; 問題2.2
;; 平面上のの線分を表現する
;; 線分は：始発点と終着点で表現されている

;; 線を表現する
(define (make-segment start-point end-point)
  (cons start-point end-point))

(define (start-segment seg)
  (car seg))

(define (end-segment seg)
  (cdr seg))

;; 点を表現する
(define (make-point x y)
  (cons x y))

(define (x-point point)
  (car point))

(define (y-point point)
  (cdr point))

;; 引数として線分をとり、中間点を返す手続き
(define (midpoint-segment seg)
  (let ((start (start-segment seg))
        (end (end-segment seg)))
    (print-point (make-point (/ (+ (x-point start) (x-point end)) 2.0)
                       (/ (+ (y-point start) (y-point end)) 2.0)))))

(midpoint-segment (make-segment (make-point 1 2)
                                (make-point 3 5)))
;; gosh> 
;; (2.0,3.5)

;; 点を出力する手続き
(define (print-point p)
  (newline)
  (display "(")
  (display (x-point p))
  (display ",")
  (display (y-point p))
  (display ")"))
 (make-segment (make-point 2 5) (make-point 3 10))
問題2.3
;; 問題2.3
; 平面上の長方形の表現を実装する

;; 長方形の表現(左上の点と右下の点)
(define (make-rectangle upper-left-point lower-right-point)
  (cons upper-left-point lower-right-point))

(define (upper-left-point rec)
  (car rec))

(define (lower-right-point rec)
  (cdr rec))

;; 点の表現する
(define (make-point x y)
  (cons x y))

(define (x-point point)
  (car point))

(define (y-point point)
  (cdr point))

(define (calc-width rec)
  (abs (- (x-point (lower-right-point rec))
          (x-point (upper-left-point rec)))))

(define (calc-height rec)
  (abs (- (y-point (upper-left-point rec))
          (y-point (lower-right-point rec)))))

;; 長方形の周囲の長さ
(define (calc-perimeter rec)
  (+ (* 2 (calc-width rec))
     (* 2 (calc-height rec))))

(calc-perimeter (make-rectangle (make-point 5 10) (make-point 10 5)))
;; gosh> 20

;; 長方形の面積
(define (calc-area rec)
  (* (calc-width rec) (calc-height rec)))

(calc-area (make-rectangle (make-point 5 10) (make-point 10 5)))
;; gosh> 25
;; 正しく動いていることが確認できた


;; 長方形の違う表現(高さと幅)
(define (make-rectangle height width)
  (cons height width))

(define (rec-height rec)
  (car rec))

(define (rec-width rec)
  (car rec))

(calc-perimeter (make-rectangle (make-point 5 10) (make-point 10 5)))
;; gosh> 20

(calc-area (make-rectangle (make-point 5 10) (make-point 10 5)))
;; gosh> 25 ;; 異なる長方形の表現でも動いている
問題2.4
;; 問題2.4

(define (cons x y)
  (lambda (m) (m x y)))

(define (car z)
  (z (lambda (p q) p)))

(define (cdr z)
  (z (lambda (p q) q)))

(car (cons 1 2))
;; gosh> 1
(cdr (cons 1 2))
;; gosh> 2

;; (car (cons 1 2))
;; => (car (lambda (m) 1 2))
;; => ((lambda (m) 1 2) (lambda (p q) q))
;; cons手続きで値が２つ渡されており、1つの引数をとるlambdaを返す
;; carおよび、cdr手続きは、引数にとった手続きに対して、
;; ２つの引数のうちに最初(or 後)の引数を返す手続きを渡す
問題2.5
;; 問題2.5

(define (cons a b)
  (* (expt 2 a) (expt 3 b)))

;; carは対で2が割り切れなくなるまで割る回数
(define (car z)
  (define (iter x count)
    (if (> (abs (remainder x 2)) 0)
        count
        (iter (/ x 2) (+ count 1))))
  (iter z 0))

;; cdrは対で割り切れなくなるまで割る回数
(define (cdr z)
  (define (iter x count)
    (if (> (abs (remainder x 3)) 0)
        count
        (iter (/ x 3) (+ count 1))))
  (iter z 0))

;; やってること自体は同じなので更に抽象化できる
(define (pair z n)
  (define (iter x count)
    (if (> (abs (remainder x n)) 0)
        count
        (iter (/ x n) (+ count 1))))
  (iter z 0))

(define (car z)
  (pair z 2))

(define (cdr z)
  (pair z 3))

(cons 6 10)
;; gosh> 3779136
(car (cons 6 10))
;; gosh> 6
(cdr (cons 6 10)) ;; gosh> 10

所感

  • 次回は問題2.6から問題2.9まで