やろーじだい

ブログです

Aizu SICP 第 16 ~ 19 回

10/6 に第 16 回、 10/18 に第 17 回、 11/17 に第 18 回、 12/6 に第 19 回を行った。各回が短かめだったのと、18 日は過去の問題に関して改めて議論して終わった (この分は 15 回の記事に書いた) ので、新しくやった分は少なかったこともありまとめました。

P 121 2.2.3 標準インターフェイスとしての列 ~ P123 列の演算 終わりまでと、その後の 練習問題 2.33 ~ 2.39 までです。

2.2.3 標準インターフェイスとしての列

 ここでは主に、プログラムを列に対する演算の連鎖として表現することによる利点が述べられている。列に対する処理の連鎖というのは関数型プログラミングをするにあたっての基本となる操作であると思うので、この辺りを読み、実際のプログラミングを通して確認しながら他のプログラミング手法と比較して実際のところどうなのかを考えたい。

 プログラミングをしているとまず最初にオブジェクト指向的な書き方が頭に浮かび、それを関数型的に書き直すということがよくある。これは単にこれまでのプログラミングの習慣によって起こることなのか、それとも実はオブジェクト指向的な書き方の方が人間の脳に優しいということが (もしかしたら) あるのかもしれない、など考えている。この辺りは今後考えていくとして、ここではまず関数型プログラミングの手法の利点についてしっかりと理解しておきたい。

 ひとまず言えることは、関数型プログラミングをサポートしているとしている言語では、それを援助する様々な汎用的で高速化されている関数や機能 (例えば遅延評価など) が提供されているので、そういったものを使えるように言語にあったプログラミングするべきだろう。

信号の流れという構造が⼿続きの中で明確に⾒て取れるようにプログラムを構成できれば、結果となるコードの概念的な明確さを⾼めることができるでしょう。

(Page 123).

列の演算

プログラムを列の演算として表すことの利点は、モジュール化された形でのプログラムの設計がやりやすくなるということにあります。モジュール化とは、⽐較的独⽴した部品を組み⽴ててプログラムを構築する設計のことです。標準コンポーネントのライブラリとともに、コンポーネントを柔軟に接続できる標準インターフェイスを提供することで、モジュール化された設計を促すことができます。モジュールによる設計は、⼯学の設計において複雑性をコントロールする強⼒な戦略です。例えば、実際の信号処理の応⽤では、標準化されたフィルタや変換器から要素を選び、それを直列につなぐことによってシステムを構築するということを、設計者は⽇常的に⾏っています。同じように、列の演算は⾃由に組み合わせられる標準的なプログラムの要素のライブラリを提供します。

(Page 126).

練習問題 2.33

 これ以降の問題では accumulate が右結合であることに注意する。右結合であるというのは、例えば (accumulate + 0 '(1 2 3)) というのは (+ 1 (+ 2 (+ 3 0))) というように展開さることを意味する。また初期値は列の一番右端に配置される。中置記法の場合 1 + 2 + 3 + 41 + (2 + (3 + 4)) となることを指して右結合と呼ぶが、これと同じことを意味する。

 以下では Gauche で使われている名前であるため関数名に my- を付けた。

(define (my-map p sequence)
  (accumulate (lambda (x y) (cons (p x) y)) nil sequence))

(test-section "ex 2.33")
(test* "my-map1" '(2 4 6) (my-map (^[x] (* x 2)) '(1 2 3)))
(test* "my-map1" '(1 1 1) (my-map (^[x] 1) '(3 9 28)))

(define (my-append seq1 seq2)
  (accumulate cons seq2 seq1))

(test* "my-append1" '(1 2 3 4 5 6) (my-append '(1 2 3) '(4 5 6)))
(test* "my-append2" '(1 2 3) (my-append nil '(1 2 3)))
(test* "my-append3" '(1 2 3) (my-append '(1 2 3) nil))

(define (my-length sequence)
  (accumulate (^[x y] (+ 1 y)) 0 sequence))

(test* "my-length1" 3 (my-length '(1 2 3)))
(test* "my-length2" 0 (my-length nil))
(test* "my-length3" 5 (my-length '(3 6 9 12 15)))

練習問題 2.34

 数式は  {a_{n}x^{n} + a_{n-1}x^{n-1}+ \cdots + a_{1}x + a_{0}} のように  a の添字は  {n} から始まるが、入力は  {0} からなので注意する。

(define (horner-eval x coefficient-sequence)
  (accumulate (lambda (this-coeff higher-terms) (+ this-coeff (* higher-terms x)))
              0
              coefficient-sequence))

練習問題 2.35

 count-leaves を集積として再定義せよという問題だが、map の使い方におうじて解答がいろいろ出た。

;; 私
;; P125 で実装されている enumerate-tree を使った
(define (count-leaves-acc t)
  (accumulate + 0 (map (^[x] 1) (enumerate-tree t))))

(test-section "ex 2.35")

(test* "count-leaves1" 4 (count-leaves-acc (cons (list 1 2) (list 3 4))))
(test* "count-leaves2" 8 (count-leaves-acc (list (cons (list 1 2) (list 3 4))
                                                 (cons (list 1 2) (list 3 4)))))

;; @sux2mfgj
(define (depth l)
 (if (null? l)
  0
  (if (number? l)
    1
    (+ (depth (car l)) (depth (cdr l))))))

(define (count-leaves-acc t)
(accumulate + 0 (map depth t)))

(test* "count-leaves1" 4 (count-leaves-acc (cons (list 1 2) (list 3 4))))
(test* "count-leaves2" 8 (count-leaves-acc (list (cons (list 1 2) (list 3 4))
(test* "count-leaves3" 14 (count-leaves-acc (list (list (list 1 2) (list 1 2) (list 1 2) (list 1 2))
                                                  (list 1 2) (list 1 2) (list 1 2))))

 あとで気が付いたが下の例は depth という関数が既に count-leaves の役割を果たしてしまっていた。

gosh> (test* "count-leaves3" 14 (depth (list (list (list 1 2) (list 1 2) (list 1 2) (list 1 2))
                                             (list 1 2) (list 1 2) (list 1 2))))
test count-leaves3, expects 14 ==> ok
#<undef>

練習問題 2.36

(define (accumulate-n op init seqs)
  (if (null? (car seqs))
      nil
      (cons (accumulate   op init (map car seqs))
            (accumulate-n op init (map cdr seqs)))))

(test* "accumulate-n" '(22 26 30) (accumulate-n + 0 '((1 2 3) (4 5 6) (7 8 9) (10 11 12))))

 各列の先頭を取り出し、それに対して accumulate をしていき結果でリストを構築する。

練習問題 2.37

それぞれ、ひとつ前で定義した手続きを使ってうまく使えるようになっている。

(define (dot-product v w)
  (accumulate + 0 (map * v w)))

(test-section "ex 2.37")

(test* "dot-product" 26 (dot-product '(1 2 3) '(3 4 5)))

(define (matrix-*-vector m v)
  (map (^[mc] (dot-product mc v)) m))

(test* "matrix-*-vector" '(14 32 50) (matrix-*-vector '((1 2 3) (4 5 6) (7 8 9)) '(1 2 3)))

(define (transpose mat)
  (accumulate-n cons nil mat))

(test* "transpose" '((1 4 7) (2 5 8) (3 6 9)) (transpose '((1 2 3) (4 5 6) (7 8 9))))

(define (matrix-*-matrix m n)
  (let ((cols (transpose n)))
    (map (^[mc] (matrix-*-vector cols mc)) m)))

(test* "matrix-*-matrix" '((9 12) (24 33)) (matrix-*-matrix '((1 2) (4 5)) '((1 2) (4 5))))

練習問題 2.38

前述した通り accumulate は右結合であるので fold-right と呼ばれる。 Gauche では fold-leftfold-right という手続きが実装されているので Haskell にならって foldl, foldr とした。

(define (foldl op initial sequence)
  (define (iter result rest)
    (if (null? rest)
        result
        (iter (op result (car rest)) (cdr rest))))
  (iter initial sequence))

(define foldr accumulate)

(test-section "ex 2.37")

(test* "foldr1" 3/2 (foldr / 1 (list 1 2 3)))
(test* "foldl1" 1/6  (foldl / 1 (list 1 2 3)))
;; '(1 (2 (3 nil)))
(test* "foldr2" (list 1 (list 2 (list 3 nil))) (foldr list nil (list 1 2 3)))
;; '(((nil 1) 2) 3)
(test* "foldl2" (list (list (list nil 1) 2) 3) (foldl list nil (list 1 2 3)))

また Gauche では fold という手続きも実装されている。fold-left は左結合かつ初期値と畳み込まれていく値が二項演算の第一項 (左側) だが、fold は第二項 (右側) になる。

gosh> (foldl cons '() '(1 2 3))
(((() . 1) . 2) . 3)
;; (cons (cons (cons '() 1) 2) 3)
gosh> (fold cons '() '(1 2 3))
(3 2 1)
;; (cons 3 (cons 2 (cons 1 '())))
gosh> (fold-right cons '() '(1 2 3))
(1 2 3)
;; (cons 1 (cons 2 (cons 3 '())))

fold-right と fold-left が任意の列に対して同じ値を返すこと を保証するために、op が満たさなければならない性質を答えよ。

(Page 130).

op は交換法則を満す必要がある。

練習問題 2.39

結合法則と初期値の位置を意識すること。

(define (reverse-r sequence)
  (foldr (lambda (x y) (append y (list x))) nil sequence))

(define (reverse-l sequence)
  (foldl (lambda (x y) (cons y x)) nil sequence))

(test-section "ex 2.38")

(test* "reverse-r" '(3 2 1) (reverse-r '(1 2 3)))
(test* "reverse-l" '(3 2 1) (reverse-l '(1 2 3)))

Aizu SICP 第 15 回 part 2

part1 の続きです。

リストに対するマップ

練習問題 2.21

 穴埋め問題。  以前から利用していたため今更だがラムダ式の表記として、 Gauche で用意されている別名である ^ を利用している。参考

(define (square-list1 items)
  (if (null? items)
      nil
      (cons (* (car items) (car items))
            (square-list1 (cdr items)))))

(define (square-list2 items)
  (map (^x (* x x)) items))

(test-section "ex 2.21")

(test* "square-list1.1" (list 1 4 9) (square-list1 '(1 2 3)))
(test* "square-list1.2" (list 1 1 1) (square-list1 '(1 1 1)))

(test* "square-list2.1" (list 1 4 9) (square-list2 '(1 2 3)))
(test* "square-list2.2" (list 1 1 1) (square-list2 '(1 1 1)))

練習問題 2.22

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things)
              (cons (square (car things))
                    answer))))
  (iter items nil))

(square-list '(1 2 3)) というのを展開していく。

(square-list '(1 2 3))
;; ↓
(iter '(1 2 3) nil)
;; ↓
(iter '(2 3) (cons 1 nil))
;; ↓
(iter '(3) (cons 4 (cons 1 nil)))

という形になり、nil に対して iter の第二引数として渡されるリストの先頭を二乗した数を順に nil に追加していくので逆順になってしまう。

(define (square-list items)
  (define (iter things answer)
    (if (null? things)
        answer
        (iter (cdr things) (cons answer (square (car things))))))
  (iter items nil))

修正したものに関しても展開してみる。

(square-list '(1 2 3))
;; ↓
(iter '(1 2 3) nil)
;; ↓
(iter '(2 3) (cons nil 1))

ここで、リストというのは終端が nil であるようなコンスの連なりであるので、(1 2 3) とは (1 . (2 . (3 . nil))) であることに注意する。上の式の (cons nil 1) を評価すると (nil . 1) というものになりリストにならない。

練習問題 2.23

(define (my-for-each proc lis)
  (define (proc-iter l)
    (proc (car l))
    (my-for-each proc (cdr l)))
  (if (not (null? lis))
      (proc-iter lis)))

if は以下のように条件が偽でありながら第3式が無い場合は #<undef> という未定義の値になる。参考 今回はとりあえず #<undef> を返すようにした。

gosh> (if #f 1)
#<undef>
gosh> (my-for-each (^ (x)
                      (newline)
                      (display x))
                   (list 1 2 3))

1
2
3#<undef>

2.2.2 階層構造

例えば、次の式によって構築されるオブジェクト '((1 2) 3 4) は、 (cons (list 1 2) (list 3 4)) 三つの項目を持つリストとして見ることができ、その一つ目の項目はそれ自身 が (1 2) というリストということになります。

(Page 115)

読書会の参加者もそうであったが (cons (list 1 2) (list 3 4)) を評価すると (1 2 3 4) となるのではないかと考えてしまう場合が多いので、勘違いした場合は図 2.5 を見てよくみてみること。((1 2) 3 4)(1 2 3 4) は構造としては全く違ったものになる。

練習問題 2.24

gosh> (list 1 (list 2 (list 3 4)))
(1 (2 (3 4)))

このプログラムは以下のように cons で書き直せる。

(cons 1
      (cons (cons 2
                  (cons (cons 3
                              (cons 4 nil))
                        nil))
            nil))

(test* "" (list 1 (list 2 (list 3 4)))
          (cons 1 (cons (cons 2 (cons (cons 3 (cons 4 nil)) nil)) nil)))

練習問題 2.25

(test-section "ex 2.25")

(test* "" 7 (car (cdaddr '(1 3 (5 7) 9))))
(test* "" 7 (caar '((7))))
(test* "" 7 (cadadr (cadadr (cadadr '(1 (2 (3 (4 (5 (6 7))))))))))

(car (cdr l)) というのは (cadr l) と書ける。Gauche では cxr という形のアクセッサーは最大4回の操作をまとめたものが定義されている。 R7RS cxrアクセサ

練習問題 2.26

(define x (list 1 2 3))
(define y (list 4 5 6))

(test-section "ex 2.26")

(test* "" '(1 2 3 4 5 6) (append x y))
(test* "" '((1 2 3) 4 5 6) (cons x y))
(test* "" '((1 2 3) (4 5 6)) (list x y))

練習問題 2.27

まず my-reverse という名前で通常の reverse を実装した。

(define (my-reverse lis)
  (define (iter lis acm)
    (if (null? lis)
        acm
        (iter (cdr lis) (cons (car lis) acm))))
  (iter lis nil))

それを使って deep-reverse を実装する。

(define (deep-reverse lis)
  (if (not (pair? lis))
      lis
      (map deep-reverse (my-reverse lis))))
(test-section "ex 2.27")

(test* "deep-reverse1" '(1) (deep-reverse '(1)))
(test* "deep-reverse2" '(3 2 1) (deep-reverse '(1 2 3)))
(test* "deep-reverse3" '((4 3) (2 1)) (deep-reverse '((1 2) (3 4))))
(test* "deep-reverse4" '((1 2) ((4 3) (2 1))) (deep-reverse '(((1 2) (3 4)) (2 1))))

(test* "deep-reverse5" '((4 3) (2 1)) (deep-reverse '((1 2) (3 4))))
(test* "deep-reverse6" '((4 (3 2)) 1) (deep-reverse '(1 ((2 3) 4))))

(test* "deep-reverse7" '((2 1)) (deep-reverse '((1 2))))
(test* "deep-reverse8" '((4 3) (2 1)) (deep-reverse '((1 2) (3 4))))

練習問題 2.28

葉を集めるプログラム。

(define (fringe tree)
  (cond ((not (pair? tree))
         tree)
        ((not (pair? (car tree)))
         (cons (car tree) (fringe (cdr tree))))
        (else (append (fringe (car tree)) (fringe (cdr tree))))))

(test-section "ex 2.28")

(test* "fringe1" '(1 2 3 4 5) (fringe '(1 2 (3) 4 5)))
(test* "fringe2" '(1 2 3 4 5) (fringe '((1) (2) (3) (4) (5))))
(test* "fringe3" '(1 2 3 4 5) (fringe '(1 (2 (3) 4) 5)))
(test* "fringe4" '(1 2 3 4 5) (fringe '(1 (2 (3) 4) 5)))

練習問題 2.29

 まずモビールとは何かということで困った問題。二枝モビールの例  上記画像のように、任意の長さの棒と、その両端にはある長さの紐があり、そこには重りかまた別な棒がぶら下がっている。それらがバランスを取りあっているような再帰的構造を持つ飾りのことを指すようだ。

;; 両端に何かがぶら下がっているある棒を表すデータである mobile を定義する関数
(define (make-mobile left right)
  (list left right))

;; mobile の両端にぶら下がっている紐の長さと、そこに付いているデータからなる branch を定義する関数
;; structure には make-mobile で作られたものか、重りを表す数値が入る
(define (make-branch length structure)
  (list length structure))
a
(define (left-branch mobile)
  (car mobile))

(define (right-branch mobile)
  (cadr mobile))

(define (branch-length branch)
  (car branch))

(define (branch-structure branch)
  (cadr branch))

(test-section "ex 2.29")

(test* "left-branch" '(1 2 3) (left-branch (make-mobile '(1 2 3) '(4 5 6))))
(test* "right-branch" '(4 5 6) (right-branch (make-mobile '(1 2 3) '(4 5 6))))

(test* "branch-length" 3 (branch-length (make-branch 3 '(4 5 6))))
(test* "branch-structure" '(4 5 6) (branch-structure (make-branch 3 '(4 5 6))))

(cdr mobile) では余分なリストにくるまれた状態になってしまうのでそこから取り出すために cadr を使っている。

b
(define (total-weight mobile)
  (if (pair? mobile)
      (+ (total-weight (branch-structure (left-branch mobile)))
         (total-weight (branch-structure (right-branch mobile))))
      mobile))

(test* "total-weight" 5
       (total-weight (make-mobile (make-branch 2 2) (make-branch 3 3))))

(test* "total-weight" 7
       (total-weight (make-mobile (make-branch 2 (make-mobile (make-branch 1 2)
                                                              (make-branch 1 2)))
                                  (make-branch 3 3))))

(test* "total-weight"
       15
       (total-weight (make-mobile (make-branch 3
                                               (make-mobile (make-branch 2 5)
                                                            (make-branch 1 5)))
                                  (make-branch 3 5))))
c
;; branch を受けとって紐の長さと総重量の積を取る。
(define (get-torque branch)
  (* (branch-length branch) (total-weight (branch-structure branch))))

(define (balanced? mobile)
  (= (get-torque (left-branch mobile)) (get-torque (right-branch mobile))))

;;   |
;; -----
;; |   |
;; |   |
;; 2   |
;;     3
(test* "get-torque1"
       5
       (get-torque (make-branch 1
                                (make-mobile (make-branch 2 2)
                                             (make-branch 3 3)))))

(test* "balanced?1"
       #f
       (balanced? (make-mobile (make-branch 2 2)
                               (make-branch 3 3))))

(test* "get-torque2"
       14
       (get-torque (make-branch 2
                                (make-mobile
                                 (make-branch 2
                                              (make-mobile
                                               (make-branch 1 2)
                                               (make-branch 1 2)))
                                 (make-branch 3 3)))))

(test* "get-torque3"
       45
       (get-torque (make-branch 3
                                (make-mobile
                                 (make-branch 3
                                              (make-mobile
                                               (make-branch 2 5)
                                               (make-branch 1 5)))
                                 (make-branch 3 5)))))

(test* "balanced?2"
       #t
       (balanced?
        (make-mobile
         (make-branch 3
                      (make-mobile
                       (make-branch 3
                                    (make-mobile
                                     (make-branch 2 5)
                                     (make-branch 1 5)))
                       (make-branch 3 5)))
         (make-mobile 9
                      (make-mobile
                       (make-branch 2 2)
                       (make-branch 3 3))))))

(test* "balanced?3"
       #f
       (balanced?
        (make-mobile
         (make-branch 3
                      (make-mobile
                       (make-branch 3
                                    (make-mobile
                                     (make-branch 2 5)
                                     (make-branch 1 5)))
                       (make-branch 3 5)))
         (make-mobile 4
                      (make-mobile
                       (make-branch 2 2)
                       (make-branch 3 3))))))

(define test-b
  (make-mobile
   (make-branch 3 6)
   (make-branch 2
                (make-mobile
                 (make-branch 1 4)
                 (make-branch 1 5)))))

(test* "check-balanced"
       #t
       (balanced? test-b))

テストに統一性が無いが他の人のものもそのまま掲載した。

d

この変更に対しては right-branchbranch-structure (cadr でアクセスしていた二つ) を以下のように cdr でアクセスするように変更するだけでよい。

(define (make-mobile left right)
  (cons left right))

(define (make-branch length structure)
  (cons length structure))

(define (right-branch mobile)
  (cdr mobile))

(define (branch-structure branch)
  (cdr branch))

(test* "total-weight-d" 5
       (total-weight (make-mobile (make-branch 2 2) (make-branch 3 3))))

(test* "total-weight-d"
       15
       (total-weight (make-mobile (make-branch 3
                                               (make-mobile (make-branch 2 5)
                                                            (make-branch 1 5)))
                                  (make-branch 3 5))))

(test* "get-torque1-d"
       5
       (get-torque (make-branch 1
                                (make-mobile (make-branch 2 2)
                                             (make-branch 3 3)))))
(test* "get-torque2-d"
       14
       (get-torque (make-branch 2
                                (make-mobile
                                 (make-branch 2
                                              (make-mobile
                                               (make-branch 1 2)
                                               (make-branch 1 2)))
                                 (make-branch 3 3)))))

練習問題 2.30

二倍にする関数を square として定義する。

(define (square x)
  (* x x))
;; 高階関数を使わない版
(define (square-tree1 tree)
  (cond ((null? tree) '())
        ((not (pair? tree)) (square tree))
        (else (cons (square-tree1 (car tree)) (square-tree1 (cdr tree))))))

;; 使う版
(define (square-tree2 tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (square-tree2 sub-tree)
             (square sub-tree)))
       tree))

(test-section "ex 2.30")

(test* "square-tree1" '(1 (4 (9 16) 25) (36 49)) (square-tree1 '(1 (2 (3 4) 5) (6 7))))
(test* "square-tree2" '(1 (4 (9 16) 25) (36 49)) (square-tree2 '(1 (2 (3 4) 5) (6 7))))

練習問題 2.31

(define (tree-map proc tree)
  (map (lambda (sub-tree)
         (if (pair? sub-tree)
             (tree-map proc sub-tree)
             (proc sub-tree)))
       tree))

(define (square-tree3 tree)
  (tree-map square tree))

(test-section "ex 2.31")

(test* "square-tree3.a" '(1 (4 (9 16) 25) (36 49)) (square-tree3 '(1 (2 (3 4) 5) (6 7))))
(test* "square-tree3.b" (square-tree1 '(1 (2 (3 4) 5) (6 7))) (square-tree3 '(1 (2 (3 4) 5) (6 7))))

練習問題 2.32

(define (subsets s)
  (if (null? s)
      (list nil)
      (let ((rest (subsets (cdr s))))
        (append rest (map (lambda (e) (cons (car s) e))
                          rest)))))

(test-section "2.32")

(test* "" '(() (3) (2) (2 3) (1) (1 3) (1 2) (1 2 3)) (subsets '(1 2 3)))
(test* "" '(() (2) (1) (1 2)) (subsets '(1 2)))

(subsets '(1 2)) と実行することにする。rest の値を求める為に subsets が繰り返し呼ばれることに注目する。毎回 subsets 引数の s ('(1 2)) が cdr によって小さくなっていくので、一番底の呼び出しである subsets (ここでこの関数を subsets-last と呼ぶ) は '() が渡されることになり、そこでは if の分岐により (list '()) が実行され (()) が返る。この subsets-last の呼び出し元である subtests ではその (())rest に束縛され、そこでは s'(2) が束縛されている。これは (append rest (map (lambda (e) (cons (car s) e)) rest)) によって、(append '(()) '(2)) から (() '(2)) になる。これはまさに '(2) の部分集合である。次にこの subsets を読んでいる subsets がある。これを subsets-top と呼ぶことにする。subsets-top では rest に対して '(() (2)) が束縛され、それに対して subsets-tops ('(1 2)) の先頭である 1 がコンスされ、restappend されることによって (() (2) (1) (1 2)) が作られる。  このようにある集合の全ての部分集合の集合というのは、ある集合の先頭を抜いた集合の全ての部分集合と、それらの部分集合にその先頭を追加したものの集合和という意味になる。(append rest (map (lambda (e) (cons (car s) e)) rest)) というのはまさにそれを表している。

Aizu SICP 第 15 回 part 1

時間が空いてしまいましたが 9/4~6 に合宿として旅館に泊まってやりました。現在は11月下旬で会津は雪が降っており嫌になっています。

 合宿での範囲は P103 2.2 階層データと閉包性 ~ P 121 2.2.3 標準インターフェイスとしての例 前までです。 やった範囲が広く練習問題が多かったため記事が長るのと一気に書くとつらいので分けて書きます。合宿自体については別記事に書きました。

lhcpr.hatenablog.com

2.2 階層データと閉包性

ここからはツリーの操作という Lisp において基本となることをやっていく。この辺りの問題は Lisp の本の入門書などにあるような話題や演習が多い。この本の序盤で少し触れたことも多く出てくるが、時間が空いているので少し細かく見ていきたい。

2.2.1 列の表現

プログラムでは変数 nil という値として表されます。

(Page 106).

Gauche では (Racket では未確認) nil が定義されていないので代わりに '() を使うか、またはファイルの先頭で (define nil '()) と宣言しておくと SICP の本のコードをそのまま利用できるので楽だった。 後々出てくると思うが ' によって任意の S 式をデータとして扱うことができる。 '(+ 1 2) の評価値は (+ 1 2) であり、(+ 1 2) の評価値は 3 であるという違いがある。詳細は後程本の中で出てくると思う。

8 この本では、リスト (list) という言葉はリスト終端マーカーで終わるペアのチェーンという意味で使います。それに対して、リスト構造 (list structure) という用語は、リストに限らず、ペアによって作られた任意のデータ構造を指します。

(Page 106).

つまり、終端が nil ('()) で終わるもののみを指してリストと呼ぶ。このこと (構造) は以降の練習問題などでも重要であるので注意したい。

式 (list 1 2 3 4) と、その式を評価した結果として得られるリスト (1 2 3 4) を混同しないように気をつけてください。式 (1 2 3 4) を評価しようとすると、インタプリタは手続き 1 を引数 2, 3, 4 に適用しようとして、 エラーを起こします。

(Page 107).

Lisp のプログラムにおいて括弧を評価する時は、要素の先頭は関数であることが必須であることに注意すること。

length は、反復スタイルで計算することもできます。

(define (length items) (define (length-iter a count) (if (null? a) count (length-iter (cdr a) (+ 1 count)))) (length-iter items 0))

(Page 109).

反復スタイルというのは、 P33 1.2.1 線形再帰と反復で出てきた反復プロセスを指す。反復プロセスの特徴は遅延演算が無いので、後で実行する処理を保存しておく必要がないため効率が良い (この辺りの用語が不安な人は P33~36 を読みなおしておくと良いかもしれません)。

練習問題 2.17

帰り値は一要素のリストであるので注意する。

(define (last-pair lis)
  (let ([cdr-lis (cdr lis)])
    (if (null? cdr-lis)
        lis
        (last-pair cdr-lis))))

(test-section "last-pair")

(test* "" (list 1) (last-pair (list 1)))
(test* "" (list 3) (last-pair (list 1 2 3)))

練習問題 2.18

(define (my-reverse lis)
  (define (%reverse lis acm)
    (if (null? lis)
        acm
        (%reverse (cdr lis) (cons (car lis) acm))))
  (%reverse lis nil))

(test-section "my-reverse")

(test* "" (list 3 2 1) (my-reverse (list 1 2 3)))
(test* "" (list 1) (my-reverse (list 1)))
(test* "" nil (my-reverse nil))

練習問題 2.19

ここでは一度 1.2.2 節に戻りどういう仕様の問題であったかを確認する必要があった。プログラムは以下のようなものだった。

;; 1.2.2 両替パターンの計算 ( cc を cc-old, first-denomination を first-denomination-old という名前に変更している )
(define (count-change amount)
  (cc-old amount 5))

(define (first-denomination-old kinds-of-coins)
  (cond ((= kinds-of-coins 1) 1)
        ((= kinds-of-coins 2) 5)
        ((= kinds-of-coins 3) 10)
        ((= kinds-of-coins 4) 25)
        ((= kinds-of-coins 5) 50)))

(define (cc-old amount kinds-of-coins)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (= kinds-of-coins 0)) 0)
        (else (+ (cc-old amount (- kinds-of-coins 1))
                 (cc-old (- amount (first-denomination-old kinds-of-coins))
                         kinds-of-coins)))))

(test-section "cc-old")

(test* "" 292 (count-change 100))

このプログラムはお金の値を入れたときに、その値になるようなコインの組み合わせが何種類あるかを表示するものだった。上の test の例では 100 セントの場合のコインの組み合わせの数は 292 種類あるという意味になる。

 練習問題に戻ると以下のように既に変更した後のプログラムが書かれている。

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

問題としては上記のプログラムの中にある未定義の手続きを実装することである。 kinds-of-coins がコインの種類の番号、coin-values がリストであることを考慮して、1.2.2 章のプログラムとの対応を考えていくとわかりやすい。

(= kinds-of-coins 0)                 (no-more? coin-values)
(first-denomination kinds-of-coins)  (first-denomination coin-values)
(- kinds-of-coins 1)                 (except-first-denomination coin-values)

以下は解答。

(define uk-coins (list 100 50 20 10 5 2 1 0.5))

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

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

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

(define (cc amount coin-values)
  (cond ((= amount 0) 1)
        ((or (< amount 0) (no-more? coin-values)) 0)
        (else
         (+ (cc amount (except-first-denomination coin-values))
            (cc (- amount
                   (first-denomination coin-values))
                coin-values)))))

(test-section "cc")

(test* "" 292 (cc 100 us-coins))

リスト coin-values の順序は、cc によって返される解答に影響を与えるだろうか、それとも与えないだろうか。それはどうしてだろうか。

(Page 111).

元は以下のような順番で定義されている。

(define us-coins (list 50 25 10 5 1))

いくつか試してみる。

gosh> (cc 100 us-coins)
292
gosh> (cc 100 (reverse us-coins))
292
gosh> (cc 100 (list 5 10 50 25 1))
292

変わらないようだが、全てにおいて成り立つのかどうかわからないので、単純に全通り試してみる。Gauche のライブラリ util.cominationspermutations という、リストを受けとって全ての順列を返してくれる関数があるのでこれを利用する。

gosh> (use util.combinations)
gosh> (permutations '(1 2 3))
((1 2 3) (1 3 2) (2 1 3) (2 3 1) (3 1 2) (3 2 1))

gosh> (every (^[x] (= x 292)) (map (^[coins] (cc 100 coins)) (permutations us-coins)))
#t

(permutations us-coins) でコインの種類の全ての順列を生成し、(map (^(coins) (cc 100 coins)) ...) で全ての順列に対して cc を適用して、(every (^(x) (= x 292)) ...) で全ての cc の結果が 292 であるかどうかを調べている。その結果が #t であるのでどんな順番であっても cc の返り値に影響は無いということである。

 任意の順番でも問題にならないことは確認できたが、なぜそうなるのについてが気になるところである。  順序に応じてツリーの構造と葉の数が大きく変わることを確認したので、計算量は違っているはず。だが、どのようにして形式的にこれを表現できるのかがわからなかった。インターネットを探してみたが、基本的に何個か展開して結果を見ると同じになります、ぐらいの確認のみで、証明らしいものはみつからなかった。

誰かわかる人がいましたら教えて下さい。

練習問題 2.20

いまいち意図にあった実装なのかわからないが、リストではなく直接任意の値を渡せることの確認であると理解して実装した。 nums に任意の長さのリストが入ることだけ意識すれば良いだけ?

(define (same-parity . nums)
  (define (get-evens l)
    (cond [(null? l)
           nil]
          [(even? (car l))
           (cons (car l) (get-evens (cdr l)))]
          [else
           (get-evens (cdr l))]))
  (define (get-odds l)
    (cond [(null? l)
           nil]
          [(odd? (car l))
           (cons (car l) (get-odds (cdr l)))]
          [else
           (get-odds (cdr l))]))
  (if (even? (car nums))
      (get-evens nums)
      (get-odds nums)))

(test-section "ex 2.20")

(test* "same-parity1" (list 1) (same-parity 1))
(test* "same-parity2" (list 2) (same-parity 2))
(test* "same-parity3" (list 2 4 6) (same-parity 2 3 4 5 6))
(test* "same-parity4" (list 1 3 5) (same-parity 1 2 3 4 5 6))

Aizu SICP 合宿を行った

Aizu SICP 合宿と称して会津芦ノ牧にある丸峰というところに行った。最高だった。

旅館の記録

9/4~6 の 2 泊 3 日で、7月頃に予定を決めていた。ゆったり寛ぎプランとかそんな感じのプランで朝食 (バイキング) 夕食 (コースお膳?) が付いていて一人一泊 8 千円という安さだった。

 場所は会津若松駅から片道30分位の600円ほど。交通費がとても安く済んだのがまず良かった。元々はどこか遠くに行こうという予定だったが交通費がかさんでしまうので近場から選んだ。

 部屋は画像の感じで 4 人で十分に余裕がありお茶や茶菓子などもあった。シャワーもついているので温泉に行く程ではないけどみたいなタイミングで使えて便利だった。

f:id:lhcpr:20170925113240j:plain:w300
f:id:lhcpr:20170925113354j:plain:w300

 朝食はバイキングだった。かなりの種類の料理があり何もかもおいしかった。

 夕食は画像の感じだった (途中で電池が切れたので夕食の一部になってしまった) 。量もかなり多いうえにはちゃめちゃに美味しかった。もしかしてこれ料理は別料金か?込み込みの 8 千円でこんなご飯食べていいのか?と不安になる美味しさだった。お酒だけは別料金だった (金額がかかれたメニューを渡されるのでそれが別料金であることはすぐにわかった) が支払い時に予定通りの金額だったので安心した。

f:id:lhcpr:20170925113405j:plain:w300f:id:lhcpr:20170925113418j:plain:w300f:id:lhcpr:20170925113421j:plain:w300f:id:lhcpr:20170925113424j:plain:w300

 二日目の昼のために近くのラーメン屋に行った程度で基本的に外に出なかったが,外の景色もとても綺麗だった。

f:id:lhcpr:20170925113435j:plain:w300

 コンビニがちょっと遠かったが朝・夕食でお腹一杯食べれるので買い食いなどする必要がなくそこまで問題ではなかった。

勉強会

勉強会は自分としては思っていたよりは集中して進めることができた。横になったりしながらの自由な格好で勉強できたので机に座ってやるよりも楽に取りくめた。勉強内容についてはまた別な記事に書く。

 温泉などに入ることによる疲れなどもあり、二日目はお昼寝を挟んだりしながらやった。2泊3日の合宿で、実際に勉強に使える時間は基本的に初日の夜と二日目で、三日目は朝出る時間にもよるが基本的に不可能なので、全体として勉強に使える時間は短いということがわかった。可能なら 3 泊 4 日とかで次はやりたい。

 一番の問題は wifi が無かったことで、各自テザリングなどを利用していたが通信料を使いまくってしまった。こういった温泉宿に泊まりにくる時はポケット wifi などを準備した方が良いということがわかった。

終わり

かなり良い三日間だった。また開催したい。する。

Aizu SICP 第 13, 14 回

先月末にやりました。練習問題タイムで楽しかった。

練習問題 2.11

区間の両端点の符号をテストすると mul-interval は 9 パターン に場合分けできて、3 回以上のかけ算が必要になるのはその中のひとつだけだよ。”

(Page 101).

参加者により掛ける区間 (区間1) と掛けられる区間 (区間2) の下限と上限が、それぞれ 0 より大きいか小さいかで 9 パターンに分けられることに気付いた。区間1, 区間2, 演算結果の区間をそれぞれ X, Y, Z とし、下限を L, 上限を U で表すと以下のような表で表せる。

0 < X.L < X.U X.L <= 0 <= X.U X.L < X.U < 0
0 < Y.L < Y.U
Y.L <= 0 <= Y.U
Y.L < Y.U < 0

この時のそれぞれの場合の掛け算は、上限と下限について以下の表のように考えることができる。

0 < X.L < X.U X.L <= 0 <= X.U X.L < X.U < 0
0 < Y.L < Y.U Z.L = X.L * Y.L Z.L = X.L * Y.U Z.L = X.L * Y.U
Z.U = X.U * Y.U Z.U = X.U * Y.U Z.U = X.U * Y.L
Y.L <= 0 <= Y.U Z.L = X.U * Y.L Z.L = X.L * Y.U
Z.U = X.U * Y.U Z.U = X.L * Y.L
Y.L < Y.U < 0 Z.L = X.U * Y.L Z.L = X.U * Y.L Z.L = X.U * Y.U
Z.U = X.L * Y.U Z.U = X.L * Y.L Z.U = X.L * Y.L

たとえば両方の区間の下限と上限が全て 0 より大きい場合、結果の区間の下限はそれぞれの区間の下限の乗算の結果になる。結果の区間の上限も同様にそれぞれの区間の上限の乗算の結果になるというのがわかる。負の場合などについても符号に気を付ければ同様に考えることができる。よって表からわかるように3回以上の掛け算が必要となるのは、中央の場合のみである。中央のケースは記号だけではわからないため、以下のような元の mul-interval と同じ計算を行った。

(define (mul-interval x y)
  (let ((p1 (* (lower-bound x) (lower-bound y)))
        (p2 (* (lower-bound x) (upper-bound y)))
        (p3 (* (upper-bound x) (lower-bound y)))
        (p4 (* (upper-bound x) (upper-bound y))))
    (make-interval (min p1 p2 p3 p4)
                   (max p1 p2 p3 p4))))

ただし、xy の下限は負で上限は正であることはわかっているので、下限は正と負の積のどちらかに限られ、上限は符号が一致する積のどちらかに限られる。したがってこの部分の最小限の実装は以下のようになる。

(let ((p1 (* (lower-bound x) (lower-bound y)))
      (p2 (* (lower-bound x) (upper-bound y)))
      (p3 (* (upper-bound x) (lower-bound y)))
      (p4 (* (upper-bound x) (upper-bound y))))
  (make-interval (min p2 p3)
                 (max p1 p4)))

 全体のプログラムについてはとくに綺麗に書く方法を思い付かず、単にそれぞれの区間を場合分けで3種類に分類して場合分けで書いた。

(define (interval-type int)
  (cond [(and (> (lower-bound int) 0) (> (upper-bound int) 0))
         :positive]
        [(and (<= (lower-bound int) 0) (>= (upper-bound int) 0))
         :include-0]
        [(and (< (lower-bound int) 0) (< (upper-bound int) 0))
         :negative]))

(define (new-mul-interval x y)
  (let ([x-type (interval-type x)]
        [y-type (interval-type y)])
    (cond [(equal? x-type :positive)
           (cond [(equal? y-type :positive)
                  (make-interval (* (lower-bound x) (lower-bound y))
                                 (* (upper-bound x) (upper-bound y)))]
                 [(equal? y-type :include-0)
                  (make-interval (* (upper-bound x) (lower-bound y))
                                 (* (upper-bound x) (upper-bound y)))]
                 [(equal? y-type :negative)
                  (make-interval (* (upper-bound x) (lower-bound y))
                                 (* (lower-bound x) (upper-bound y)))])]
          [(equal? x-type :include-0)
           (cond [(equal? y-type :positive)
                  (make-interval (* (lower-bound x) (upper-bound y))
                                 (* (upper-bound x) (upper-bound y)))]
                 [(equal? y-type :include-0)
                  (let ((p1 (* (lower-bound x) (lower-bound y)))
                        (p2 (* (lower-bound x) (upper-bound y)))
                        (p3 (* (upper-bound x) (lower-bound y)))
                        (p4 (* (upper-bound x) (upper-bound y))))
                    (make-interval (min p2 p3)
                                   (max p1 p4)))]
                 [(equal? y-type :negative)
                  (make-interval (* (upper-bound x) (lower-bound y))
                                 (* (lower-bound x) (lower-bound y)))])]
          [(equal? x-type :negative)
           (cond [(equal? y-type :positive)
                  (make-interval (* (lower-bound x) (upper-bound y))
                                 (* (upper-bound x) (lower-bound y)))]
                 [(equal? y-type :include-0)
                  (make-interval (* (lower-bound x) (upper-bound y))
                                 (* (lower-bound x) (lower-bound y)))]
                 [(equal? y-type :negative)
                  (make-interval (* (upper-bound x) (upper-bound y))
                                 (* (lower-bound x) (lower-bound y)))])])))
;; Tests

(test-section "interval-type")

(test* "interval-type1"
       :positive
       (interval-type (make-interval 1 2)))

(test* "interval-type2"
       :include-0
       (interval-type (make-interval -1 1)))

(test* "interval-type3"
       :negative
       (interval-type (make-interval -3 -2)))

(test* "interval-type4"
       :include-0
       (interval-type (make-interval 0 1)))

(test-section "new-mul-interval")
(test-section "x+y+")
(test* "new-mul-interval"
       (mul-interval (make-interval 1 5) (make-interval 1 1))
       (new-mul-interval (make-interval 1 5) (make-interval 1 1)))

(test-section "x+y-")
(test* "new-mul-interval"
       (mul-interval (make-interval 1 5) (make-interval 1 1))
       (new-mul-interval (make-interval 1 5) (make-interval 1 1)))

(test-section "x+y+-")
(test* "new-mul-interval"
       (mul-interval (make-interval 1 5) (make-interval -1 1))
       (new-mul-interval (make-interval 1 5) (make-interval -1 1)))

(test-section "x-y+")
(test* "new-mul-interval"
       (mul-interval (make-interval -5 -1) (make-interval 1 2))
       (new-mul-interval (make-interval -5 -1) (make-interval 1 2)))

(test-section "x-y+-")
(test* "new-mul-interval"
       (mul-interval (make-interval -5 -1) (make-interval -1 2))
       (new-mul-interval (make-interval -5 -1) (make-interval -1 2)))

(test-section "x-y-")
(test* "new-mul-interval"
       (mul-interval (make-interval -5 -1) (make-interval -2 -1))
       (new-mul-interval (make-interval -5 -1) (make-interval -2 -1)))

(test-section "x+-y+")
(test* "new-mul-interval"
       (mul-interval (make-interval -5 5) (make-interval 1 2))
       (new-mul-interval (make-interval -5 5) (make-interval 1 2)))

(test-section "x+-y+-")
(test* "new-mul-interval"
       (mul-interval (make-interval 0 5) (make-interval 0 1))
       (new-mul-interval (make-interval 0 5) (make-interval 0 1)))
(test* "new-mul-interval"
       (mul-interval (make-interval 1 -1) (make-interval 5 -5))
       (new-mul-interval (make-interval 1 -1) (make-interval 5 -5)))

(test-section "x+-y-")
(test* "mul-interval"
       (mul-interval (make-interval -5 5) (make-interval -2 -1))
       (new-mul-interval (make-interval -5 5) (make-interval -2 -1)))

以下ではマクロを使って書いてみたが、単に (positive-interal? interval) などの述語を作ればよいだけだった。interval-type の実装があまり良くなかった。折角なので一応載せておく。

(define-syntax match-interval-type
  (syntax-rules ()
    ((_ target (type1 case1) (type2 case2) (type3 case3))
     (let ([target-type (interval-type target)])
       (cond [(equal? target-type type1)
              case1]
             [(equal? target-type type2)
              case2]
             [(equal? target-type type3)
              case3])))))

(define (new-mul-interval x y)
  (match-interval-type x
    [:positive (match-interval-type y
                 [:positive
                  (make-interval (* (lower-bound x) (lower-bound y))
                                 (* (upper-bound x) (upper-bound y)))]
                 [:include-0
                  (make-interval (* (upper-bound x) (lower-bound y))
                                 (* (upper-bound x) (upper-bound y)))]
                 [:negative
                  (make-interval (* (upper-bound x) (lower-bound y))
                                 (* (lower-bound x) (upper-bound y)))])]
    [:include-0 (match-interval-type y
                  [:positive
                   (make-interval (* (lower-bound x) (upper-bound y))
                                  (* (upper-bound x) (upper-bound y)))]
                  [:include-0
                   (let ((p1 (* (lower-bound x) (lower-bound y)))
                         (p2 (* (lower-bound x) (upper-bound y)))
                         (p3 (* (upper-bound x) (lower-bound y)))
                         (p4 (* (upper-bound x) (upper-bound y))))
                     (make-interval (min p2 p3)
                                    (max p1 p4)))]
                  [:negative
                   (make-interval (* (upper-bound x) (lower-bound y))
                                  (* (lower-bound x) (lower-bound y)))])]
    [:negative (match-interval-type y
                 [:positive
                  (make-interval (* (lower-bound x) (upper-bound y))
                                 (* (upper-bound x) (lower-bound y)))]
                 [:include-0
                  (make-interval (* (lower-bound x) (upper-bound y))
                                 (* (lower-bound x) (lower-bound y)))]
                 [:negative
                  (make-interval (* (upper-bound x) (upper-bound y))
                                 (* (lower-bound x) (lower-bound y)))])]))

本文

(define (width i)
  (/ (- (upper-bound i) (lower-bound i)) 2))

本文の中で定義されている幅 (width) だが、区間の幅というのは直感的には 上限 - 下限 であると思ったのだが (上限 - 下限) / 2 と定義されている。つまり中央値から端点への距離を幅として定義しているので注意したい。

練習問題 2.12

自分は make-interval を使って書いた。しかし、参加者の make-center-width を使ったものの方が綺麗なのでそちらも載せた。

;; make-interval 版
(define (make-center-percent c p)
  (let ([error (/ p 100)])
    (make-interval (- c (* c error)) (+ c (* c error)))))

;; make-center-with 版
(define (make-center-percent c p)
  (make-center-width c (* (* c p) 0.01)))

percent に関しても同様で、自分は何も考えず関数を書いてしまったが、widthcenter を使うべきだった (折角本文で作っているのを無視してしまった)

;; idiot 版
(define (percent i)
  (let* [(c (center i))
         (ub (upper-bound i))]
    (* (- (/ ub c) 1) 100)))

;; genius 版
(define (percent i)
  (* (/ (width i) (center i)) 100))

練習問題 2.13

全ての数値が正であると仮定する。 { \displaystyle R1 }, { \displaystyle R2 }区間を、{ \displaystyle a }, { \displaystyle c } は中央値, { \displaystyle b }, { \displaystyle d } は誤差とする。区間(下限, 上限) と表現する。また、本文中では「パーセント許容誤差」という単語と「許容誤差」という単語が混在しているが、ここでは許容誤差と統一する。

以下証明。

{ \displaystyle R1 }{ \displaystyle a \pm b (0 \leqq b \leqq 1) } であるとすると、

{ R1 = \left[a(1-b),\ a(1+b)\right] }

{ \displaystyle R2 }{ \displaystyle c \pm d (0 \leqq d \leqq 1) } であるとすると、

{ R2 = \left[c(1-d), c(1+d)\right] }

になる。

この時、練習問題 2.11 で定義した mul-interval区間両方が正である場合の計算から、

{ R1 \cdot R2 = \left[ac(1-b)(1-d), ac(1+b)(1+d)\right] }

になる。

ここで

{ ac(1-b)(1-d) = ac(1 - (b+d) + bd)}

であるが、問題文の仮定から許容誤差 { \displaystyle b }, { \displaystyle d } は非常に小さいため { \displaystyle b \cdot d \fallingdotseq 0} と考えられるので、

{ ac(1 - (b+d) + bd) = ac(1 - (b+d))}

となる。

同様に

{ ac(1+b)(1+d) = ac(1 + (b+d))}

従って区間 { \displaystyle R1 }, { \displaystyle R2 } の積は

{ R1 \cdot R2 = \left[ac(1-(b+d)), ac(1+(b+d))\right]}

ここから中央値は

{ \displaystyle \frac{(ac(1-(b+d)) + ac(1+(b+d)))}{2} = \frac{ac(1+1-(b+d)+(b+d))}{2} = ac}

幅は

{ \displaystyle \frac{(ac(1+(b+d)) - ac(1-(b+d)))}{2} = \frac{ac( 1+(b+d) - (1-(b+d)) )}{2} = ac(b+d)}

最後に、許容誤差は 幅 / 中央値 で求められるので

{ \displaystyle \frac{ac(b+d)}{ac} = (b+d)}

よって二つの区間の積の許容誤差は、因数の許容誤差である { \displaystyle b}{ \displaystyle d} を使って { \displaystyle (b+d)} と表現できることがわかった。

証明終わり。

 実際に計算してみると、以下のようにほぼ (b+d) になる。

;; 1.0 を掛けて実数に変換
gosh> (* (percent (mul-interval (make-center-percent 100 0.00001) (make-center-percent 100 0.00001))) 1.0)
2.0000000004074335e-5

練習問題 2.14

まず適当に par1par2 の結果を見てみる。

gosh> (par1 (make-center-percent 5 1) (make-center-percent 10 5))
(3.0241157556270095 . 3.669550173010381)
gosh> (par2 (make-center-percent 5 1) (make-center-percent 10 5))
(3.2543252595155714 . 3.409967845659164)

gosh> (par1 (make-center-percent 10 10) (make-center-percent 20 15))
(4.5 . 9.730769230769232)
gosh> (par2 (make-center-percent 10 10) (make-center-percent 20 15))
(5.884615384615384 . 7.4411764705882355)

このように全く異なる結果になる。

ある区間 A と B を作成し、式 A/A と A/B の計算においてそれらを用いよ。

(Page 100).

ここで特に A/A に注目してみる。

gosh> (let ([A (make-center-percent 10 10)]
            [B (make-center-percent 20 15)])
        (div-interval A A))
(0.8181818181818182 . 1.222222222222222)

このように、予期していた (1 . 1) から大きくズレている。ここでは、このズレは除算による誤差であると考えた。次に問題文の続きを読むと以下のようにある。

幅が中央値の小さなパーセンテージである区間を用いることで多くの実態を掴むことができるだろう。

(Page 100).

そこで実際に試してみる。

gosh> (let ([A (make-center-percent 10 0.01)])
        (div-interval A A))
(0.9998000199980004 . 1.000200020002)

このようにみると誤差が小さくなったように見える。

 しかし以下の第4回の原稿というものを読んでみるとこの考えは間違っていたことがわかった。

応用数理』チュートリアル 「精度保証付き数値計算」

以下代数学における用語について正確で無い可能性があるが、自分なりに説明を試みてみる。

 上記の原稿の 「2.4 区間演算の性質」において、区間演算では加法と乗法に関する逆元が存在しないとなっている。実際計算してみると、[1,2] - [1,2] = [-1,1] であるが、[-1,1] + [1,2] = [0,3] となり元に戻らないため、加法において [-1,1][1,2]単位元ではない。同様に乗算についても [1,2] / [1,2] = [1/2, 2] となり、これもあきらかに乗法における単位元にはならい。そうなると P99 の式は「代数的」には等価であるのだが、区間である { \displaystyle R_1 }{ \displaystyle R_2 } は逆元を持たないので { \displaystyle \frac{R_1}{R_1} = 1 } とはならない。これが原因で par1par2 の答が一致しないと考えられる。  代数学において、任意の { \displaystyle a \in G } に対して { \displaystyle b \cdot a = a \cdot b = e } を満たす { \displaystyle b \in G } が存在することが群の条件のひとつであるが、区間は加算についても乗算についてもこれを持たない。以上のことから、{ \displaystyle \frac{R_1}{R_1}=1 } といった代数的な演算は適用できないと考えられる。つまり、これは区間が (少なくとも今回の区間の定義においては) 代数的操作をするための性質を持たないことによって起こる問題であると考えられる。

練習問題 2.15

彼女は Alyssa のシステムを用いて区間の計算をする式が、もし式が不確かな値を表現する変数がどれも繰り返されない形であれば、より厳しいエラーの限界を算出すると言う。従って彼女は抵抗の並列に対し、par2 の方が par1 より “より良い” プログラムであると述べた。彼女は正しいだろうか? それは何故か?

(Page 100).

文がいまいちピンと来なかったが、参加者が「不確かな値を表現する変数」というのは並列接続の抵抗の式における { \displaystyle R_1 }{ \displaystyle R_2 } だとすれば、最初の式 (par1) の積 { \displaystyle R_1 R_2 } や、それを { \displaystyle R_1 + R_2 } で除算することのように、変数同士の計算を行うことでこの不確かな変数同士の計算によってより大きな不確かさが生じてしまうということを指しているのではと考えた。これと比べて二番目の式 (par2) では 1 という定数と変数の計算が殆どであり、不確かさが生じそうなのは { \displaystyle \frac{1}{R_1} } の結果と { \displaystyle \frac{1}{R_2} } の結果を足すところのみであるので、こちらの方が不確かさ (=誤差?) が小さくて済みそうである。

 したがって Eva は正しいと言えそうだ。

練習問題 2.16

(警告:この問題はと ても難しい)

(Page 100).

とのことであまり深入りはしていないがぱっと思いついたことを書いておく。

 練習問題 2.14 で言ったように、今回の区間は加法と乗法について逆元を持たないため、通常扱っているような数値と同じような式変形はできない。逆を言えば代数的な変換をするためには逆元を持つように区間というものを表現できれば良いということで、区間というものをそのような形で表現する方法を考えれば良いのだろうか。  練習問題 2.14 で挙げた参考文献にはこれに対する手法が書かれているようだ。なんらかの手法で区間というものを別な次元に写像して、そこでの変換を行うというようなアプローチになるのだろうか。すぐには理解できそうになかったので一旦諦めた。掘り下げたくなったら参考文献などに当たってみたい。

青森に行った

日記です。

期間と場所

 8/23 - 8/26 の3泊4日青森に行った。弘前というところに滞在した。

目的

主な目的は 電気関係学会東北支部連合大会 の、 Student Session というものに参加することだった

 Student Session は学生による英語での発表の練習の場として位置付けられており、発表と質疑応答は英語で行われた。 Student Session に提出する論文は 1 ページ論文で提出さえすれば基本的に参加できる。発表は 12 分、質疑応答約 3 分というものなので、国際学会を経験する前に一度公式での英語での発表の雰囲気を経験したいという人に向くかもしれない。毎年行われており、去年は仙台だったため来年は東北の内の他の県になると思う。

観光

あまり写真を取ってなかった。

 一日目は新幹線を含む電車を乗り継いで弘前に向った。アップル製品がなんか一杯あった。

f:id:lhcpr:20170827214506j:plain:w500 f:id:lhcpr:20170827214539j:plain:w500 f:id:lhcpr:20170827214547j:plain:w500

 青森出身の先輩に教えて頂いた、急須で飲めるコーヒーというものを飲みに 成田専蔵珈琲 に行った。おいしかった。

f:id:lhcpr:20170827214601j:plain:w500

 その後はスーパーを除いて各自買い物をしてホテル近くにある居酒屋で初日から飲んだ。そして風邪を引いた。

 二日目は体調がやばいなと思いつつ、ホテルを出るしかなかったので我慢しつつ、午前中は弘前城を見にいった。

f:id:lhcpr:20170827214627j:plain:w500

 その後一度学会会場に行き近くの定食屋でごはんを食べたのだが、体調が悪すぎてしんどかったのでホテルに帰って寝た。

 三日目は発表日だったので、午前中から学会会場に行き、午前は発表の準備をしていた。昼は弘前大学近くのもみじ亭というところでそばを食べた。ちまきもあって美味しかった。

f:id:lhcpr:20170827214657j:plain:w500

 発表はしんどかった。

 最終日は寝坊をしてホテルの朝食を食べ逃した。チェックアウトには間に合った。駅弁食べながら帰った。

 本は8冊も抱えて行った。しかし持っていった内の一つの『老人と海』は読み終えたが,読み始めた『シュレーディンガーの猫を追って』の途中までしか読めなかった。良い筋トレになった。読んだ分はおもしろかった。将来は老人になりたい。

愚痴

※以下、読む人が少し不愉快に感じるであろう内容を含みます。

 23日の夜のホテルで温度調節や入眠に失敗してしまい、体調を崩し風邪をひいてしまった。そのため観光も学会もあまり楽しめなかった。最近遠出する度に体調を崩してしまっているので、家以外に泊まるときも家の時と同じようなリズムを心がけるようにしたい。

 自分も時々してしまうのだが、失敗に対して笑うということをする人が自分の発表会場に複数見られ、自分の発表以前から完全にやる気を失なってしまった。特に座長は後ろの参加者に全く聞こえない声で質問する上に、英語などで学生が詰まると笑うというような人だったため不愉快で仕方がなかった。

 自分の発表するセッションがひどかっただけなのだが (ひとつ前も見ていたがそんな雰囲気はなかった) とても嫌な雰囲気だった。初めて英語で発表するという立場だったら、英語での発表を二度としたくないと思ったかもしれない。

 自分の発表は準備不足でひどかった。体調不良であることは全く関係の無い、ひどい発表だったので、聞いていた人に申し訳なかった。

OSX (10.11.6) で BSSID を指定して接続する

別な帯域だが同じ SSIDwifi が飛んでいるという場面に遭遇し、選択して接続する方法に困ったが解決したのでまとめておく。

まず BSSID を取得する

Linuxiwconfig のようなものは MacOSX では airport が提供されている。場所は以下にあるので Path を通すなりしておく。

/System/Library/PrivateFrameworks/Apple80211.framework/Versions/Current/Resources/airport

airport-bssid を導入する

現在 airport では BSSID を指定することができないので、公開されている airport-bssid というものを利用する。Path の通った場所に実行ファイルをコピーしている。

$ git clone https://github.com/qpSHiNqp/airport-bssid.git
$ cp airport-bssid/Build/airport-bssid /path/to/bin

実行

まず BSSID と channel の情報を取得する。

$ airport scan
...(略)

channel については airportのissue で指定しておくと動いたというケースがあったので、もし動かない場合は対処できるかもしれない。channel が 11 だとすると以下のように指定できる。

$ sudo airport -c11

Ethrenet の port も確認しておく。

$ networksetup -listallhardwareports

Hardware Port: Wi-Fi
Device: en0
...(略)

最後に以下で接続する。

$ airport-bssid EthernetPort BSSID password
...
Associated to network "入力したSSID" (BSSID: 入力した BSSID)

となれば成功しているはず。以下で現在接続している wifi を確認できる。

$ airport -I