本文

ペインタと変換の組合せ

ペインタの演算 : 引数のフレームから作られたフレームに関して、元のペインタを発動する新しいペインタを作り出す

ペインタが抽象化されているおかげで、要素ペインタに対してフレームを与えるだけで処理をおこなうことができる。

問題解答

問2.50

(define (flip-horiz painter)
	(transform-painter painter
                     (make-vect 1.0 0.0)
                     (make-vect 0.0 0.0)
                     (make-vect 1.0 1.0)))

(define (rot180 painter)
  (transform-painter painter
                     (make-vect 1.0 1.0)
                     (make-vect 0.0 1.0)
                     (make-vect 1.0 0.0)))

(define (rot270 painter)
  (transform-painter painter
                     (make-vect  0.0 1.0)
                     (make-vect  0.0 0.0)
                     (make-vect  1.0 1.0)))

問2.51

(define (below painter1 painter2)
  (let ((split-point (make-vect 0.0 0.5)))
    (let ((paint-bottom
           (transform-painter painter1
                              (make-vect 0.0 0.0)
                              (make-vect 1.0 0.0)
                              split-point))
          (paint-top
           (transform-painter painter2
                              split-point
                              (make-vect 1.0 0.5)
                              (make-vect 0.0 1.0))))

      (lambda (frame)
        (paint-bottom frame)
        (paint-top frame)))))

(define (below painter1 painter2)
  (rot90 (beside (rot270 painter1) (rot270 painter2))))

問題解答

問2.46

(define (make-vect x y)
  (cons x y))

(define (xcor-vect v)
  (car v))

(define (ycor-vect v)
  (cdr v))

(define (add-vect v1 v2)
  (make-vect
   (+ (xcor-vect v1) (xcor-vect v2))
   (+ (ycor-vect v1) (ycor-vect v2))))

(define (sub-vect v1 v2)
  (make-vect
   (- (xcor-vect v1) (xcor-vect v2))
   (- (ycor-vect v1) (ycor-vect v2))))

(define (scale-vect v s)
  (make-vect
   (* s (xcor-vect v))
   (* s (ycor-vect v))))

(define v1 (make-vect 1 2))
(define v2 (make-vect 2 1))

(xcor-vect v1)
(ycor-vect v1)

(add-vect v1 v2)
(sub-vect v1 v2)
(scale-vect v1 5)

問2.47
方法1

(define (make-frame origin edge1 edge2)
  (list origin edge1 edge2))

(define (frame-origin frame)
  (list-ref frame 0))

(define (frame-edge1 frame)
  (list-ref frame 1))

(define (frame-edge2 frame)
  (list-ref frame 2))

方法2

(define (make-frame origin edge1 edge2)
  (cons origin (cons edge1 edge2)))

(define (frame-origin frame)
  (car frame))

(define (frame-edge1 frame)
  (cadr frame))

(define (frame-edge2 frame)
  (cddr frame))

本文

ペインタ
フレームに合うように画像を描画する手続き

問題解答

問2.48

(define (make-segment v1 v2)
  (cons v1 v2))

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

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

問2.49
a.

(define (outline-painter)
  (segments->painter
   (list (make-segment (make-vect 0 0) (make-vect 1 0))
         (make-segment (make-vect 1 0) (make-vect 1 1))
         (make-segment (make-vect 1 1) (make-vect 0 1))
         (make-segment (make-vect 0 1) (make-vect 0 0)))))

以下、やることは同じなので略。

昨日ガッツリと取り組んだおかげで何とかペースが戻ってきた気がします。引き続きボチボチいきます。

本文

2.2.4 例:図形言語
図形の処理に対して閉包性を持たせる。

問題解答

問2.44

(define (up-split painter n)
  (if (= n 0)
      painter
      (let ((smaller (up-split painter (-n 1))))
        (below painter (beside smaller smaller)))))

本文

高階演算

フレーム
フレーム座標写像の方法がイマイチ理解できない。フレームを定義するには 3 つのベクトルが必要なのに、frame-coord-map では一つのベクトルしか返さない。これで写像できるのか?

→単位方形内に定義された画像の要素をフレーム内に貼り付けるための処理ということっぽい。たしかに文章でもそう書いている。

一週間間が空いたせいでペースがつかめなくなってしまって SICP に手を伸ばすまでにものすごく時間がかかるようになってしまいました。
ここで辞めてしまうと本当にやらなくなっちゃうのでちょいと踏ん張り所です。一日一問でも進めて徐々にペースを戻さないと。

問題解答

問2.42
とっかかりが掴めない。というか、どういうデータ構造で格納されるのか?が想像つかない。
しかたがないので empty-board をカンニング。

(define empty-board '())

ん?これでいいのか?

クィーンの置く場所を数値として表すらしい。 サンプルだと (3 7 2 8 5 1 4 6) となるということか。
それを踏まえて元のコードをじっと眺める。

。。。だがダメ。ダメ。全く頭が動かない。一週間空くとここまでダメなのか(もともとダメという話は無かったことに)。
仕方ないから全部カンニングしてきちんと把握することにします。

(define (flatmap proc seq)
  (accumulate append '() (map proc seq)))

map で作成したリストを展開する

seq に (1 2) のような値が入力され、各値に proc を施すことで
((1 1) (2 2)) のようなリストのリストになる場合、リストに変換する。

この場合は (1 1 2 2) になる。

(define (adjoin-position new-row k rest-of-queens)
  (cons new-row rest-of-queens))

既存のクィーンの並びに新しいクィーン new-row を加える

(define (accumulate op initial sequence)
  (if (null? sequence)
      initial
      (op (car sequence)
          (accumulate op initial (cdr sequence)))))

初期値を initial として、返り値に対して sequence の各値を op で処理していく。sequence が (1 2 3) だった場合、(op 1 (op 2 (op 3 initial))) という処理になる。

(define (enumerate-interval low high)
  (if (> low high)
      '()
      (cons low (enumerate-interval (+ low 1) high))))

low から high まで値を数え上げ、リストにして返す

(define (filter predicate sequence)
  (cond ((null? sequence) '())
        ((predicate (car sequence))
         (cons (car sequence)
               (filter predicate (cdr sequence))))
        (else (filter predicate (cdr sequence)))))

predicate で評価されて true になるもののリストを返す

(define (safe? k positions)
  (define (safe1 x n)
    (or (= n k)
        (let ((y (list-ref positions n)))
          (and (not (= x y))
               (not (= (- x y) n))
               (not (= (- y x) n))
               (safe1 x (+ n 1))))))

  (safe1 (car positions) 1))

list-ref なる未知の関数が使われている。Gauche のマニュアルを見ると

listのk番目の要素を返します。

ということのようで。これ、もっと早めに教えてよっ!!(涙。
LISP の文法関係は、SICP だけじゃ足りないのか、、、、

ということで、safe1 では一番頭にある値とそれ以降の値を比較して許容できる配置かどうかをチェックしている。

(not (= x y) ; 同じ行にクィーンが配置されていないか
(not (= (- x y) n)) ; 斜め方向にクィーンが配置されていないか
(not (= (- y x) n)) ; 斜め方向にクィーンが配置されていないか
(safe1 x (+ n 1)))))) ; 次のアイテムをチェック

(define empty-board '())

空のリストを作成

ここまで来て本体の確認をします。

(define (queens board-size)
  (define (queen-cols k)
    (if (= k 0)
        (list empty-board)
        (filter
         (lambda (positions) (safe? k positions))
         (flatmap
          (lambda (rest-of-queens)
            (map (lambda (new-row)
                   (adjoin-position 
                    new-row 
                    k
                    rest-of-queens))
                 (enumerate-interval 1 board-size)))
          (queen-cols (- k 1))))))
  (queen-cols board-size))

(enumerate-interval 1 board-size) で 1 から board-size までの値を数え上げ。board-size が 3 なら (1 2 3)。

まず、k=1 の場合を考える。 (queen-cols (-k 1)) は (()) になる。
この値を使用して flatmap 内の動作確認。rest-of-queens は (()) から要素が一つづつ取り出されるので、()。

(map (lambda (new-row)
       (adjoin-position 
        new-row 
        k
        rest-of-queens))
     (enumerate-interval 1 board-size)))

この部分は (1 2 3) のアイテムに対して adjoin-position を適用したリストを返す。
rest-of-queens は () 、new-row は 1,2,3 が繰り返し毎に入るので結果は
((1) (2) (3))。

flatmap の実態は map なので、まずは map で考える。

(map
 (lambda (rest-of-queens)
   (map (lambda (new-row)
          (adjoin-position 
           new-row 
           k
           rest-of-queens))
        (enumerate-interval 1 board-size)))
 (queen-cols (- k 1)))

やっていることは rest-of-queens を取り替えながら map を実行して、その結果をリストにしていることなので (((1) (2) (3)))。
flatmap リストを一つ解除するので ((1) (2) (3))。この、(1),(2),(3) それぞれに対してsafe? で評価して取捨選択するのが filter。結果は ((1) (2) (3))。これが k=1 のときの結果。

k=2 の時は

(flatmap
 (lambda (rest-of-queens)
   (map (lambda (new-row)
          (adjoin-position 
           new-row 
           2
           rest-of-queens))
        (enumerate-interval 1 board-size)))
 '((1) (2) (3))')

という処理になる(k-1 の時の結果をわかりやすいようにシングルクォーテーションで囲っている)。
rest-of-queens の最初の値は (1) なので、map の結果は ((1 1) (2 1) (3 1))。flatmap 内の map まで処理が終ると

(((1 1) (2 1) (3 1))
 ((1 2) (2 2) (3 2))
 ((1 3) (2 3) (3 3)))

になるので、flatmap されて ((1 1) (2 1) (3 1) (1 2) (2 2) (3 2) (1 3) (2 3) (3 3))。
ここから filter されて ((3 1) (1 3)) が残る。以下同様に処理をおこなう。

こんな感じでしょうかね。map がネストすると途端に処理を追いかけられなくなってしまいます。何となく、map の処理が自分の中でキチンとモデル化できていない感じです。

問2.43
外側のループの数が増えるのが原因? flatmap 内で処理がおこなわれる回数は変わらないきがするけれども。。。

→ queens-cols の呼ばれる回数が増えると、その下で再帰される分が増える。

board-size を s とする。
最初の実装だと queens-cols が呼ばれると s 回再帰で呼ばれる。
Louis の実装だと enumerate-interval 毎に s 回呼ばれ、それぞれの中で再帰されていく。
そのため、quessn-cols の呼ばれる回数は

k = s のとき 1
k = s-1 のとき s
k = s-2 のとき s^2
:
:
k = 1 のとき s^(s-1)

これは等比数列なので合計で呼び出される回数は初項 a、公比 r、項数 n で a(r^n-1)/(r-1) から (s^s-1)/(s-1)。

最初のものと比較すると (s^s-1)/(s-1)/s は大体 s^(s-2) 倍処理がおこなわれていることになる。

結局カンニングして何とか流れを追うことができました。でも、自分で一から回答できるかというとできる自信がないですね、、、、
ちょっと気にはなるものの、次に進むことにします。

この一週間は新婚旅行に行っていたので SICP はおやすみ。今日から気合一新再開です。
一週間空いたおかげで細かいところを忘れているのでまずはおさらいから。

…というか、今日はおさらいするだけでおしまい。明日から本気出します(ぁ

問題解答

問2.42
とりあえず本に書いてあるコードは打ち込んだので、あしたから本格的に問題に取り掛かる。