やろーじだい

ブログです

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

Aizu SICP 第12回

 やりました。範囲は P99 練習問題 2.6 ~ P101 練習問題 2.10 です。ここから読書会参加者で scheme のテストを利用するようにしました。(gauche 利用者は gauche.test を、 racket 利用者は rackunit を利用しています。) 今後は利用したテストケース (ただし gauche の方だけ) も記述しておきます。

練習問題 2.6

 しっかりチャーチ数について調べていないが、 id 関数に対して何回関数 f を適用するかによって数字というものを表現しているようだ。zero というものは f を受けとるが適用せずに捨てていることに注意したい。

(define zero
  (lambda (f) (lambda (x) x)))

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

(add-1 zero)
;; ↓
(add-1 (lambda (f) (lambda (x) x)))
;; ↓
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
                             ---------------------------
                                  ;; ここが n
;; ↓
(lambda (f) (lambda (x) (f (((lambda (f) (lambda (x) x)) f) x))))
                            -------------------------------
                            ;; f を適用するが f は使われずに内側の (lambda (x) x) だけが残る
;; ↓
(lambda (f) (lambda (x) (f ((lambda (x) x) x))))
                           ------------------
                           ;; (lambda (x) x) に x を渡すと x になる
;; ↓
(lambda (f) (lambda (x) (f x)))
;; これが one

(define one
  (lambda (f) (lambda (x) (f x))))

;; 同様に one に add-1 を適用すれば two ができる
(define two
  (lambda (f) (lambda (x) (f (f x)))))

これはつまり、ある x に対して Haskellsucc 関数のようなものを適用することで次のものにするということを表現していると考えられるので、f として (+1) を、x として 0 を渡せば整数に変換できる。

 ちなみに hoogle:succ にあるように succHaskellEnum 型が持つ method の一つで、『後継 (successor)』を意味する関数になる。(数字だけではなく、順序が定義されていれば渡された値の次の値を返す)

 Scheme では (+1) として inc を定義する。

(define (inc x)
  (+ 1 x))

よって以下のように、zerotwo、またはそれらに add-1 したものに inc0 を渡すことによって整数に変換できる。

((zero inc) 0)
;=> 0
((two inc) 0)
;=> 2
(((add-1 (add-1 two)) inc) 0)
;=> 4

 また、例えば zero として #\afnext-char という手続きを定義して渡せば文字にも変換できる。

(define (next-char x)
  (integer->char (+ 1 (char->integer x))))

(((add-1 two) next-char) #\a)
;=> #\d

 次に加算手続き (plusとする) だが、考え方としては、まず最終的には inc0 を受けとれるような形である必要があるので以下のような形になる (... は未定義な場所とする)。

(define (plus a b)
  (lambda (f) (lambda (x) ...)))

次に、ab に入ってくるのは上で定義した onetwo であるので、例えば (plus one two) と呼ばれた場合の結果を考えると以下のようになる。

(lambda (f) (lambda (x) (f (f (f x)))))

これを踏まえると x に対して onetwo によって plus が受けとる f を適用すれば良いことがわかったので、結果は以下のようになる。

(define (plus a b)
  (lambda (f) (lambda (x) ((a f) ((b f) x)))))
;; Test
(test-section "practice 2.6")

(test "zero" 0
      (^[] ((zero inc) 0)))

(test "one" 1
      (^[] ((one inc) 0)))

(test "two" 2
      (^[] ((two inc) 0)))

(test "add-1" 3
      (^[] (((add-1 (add-1 one)) inc) 0)))

(test "plus" 3
      (^[] (((plus two one) inc) 0)))

(test "plus" 5
      (^[] (((plus two three) inc) 0)))

(test "character-church" #\d
      (^[] (((add-1 two) next-char) #\a)))

2.1.4 発展問題: 区間演算

二つ区間の割り算は、⼀つ⽬に⼆つ⽬の逆数をかけることにします。区間の逆数の下限と上限は、上限の逆数と下限の逆数という順番になることに気をつけてください。

(Page 100).

これに関しては、以下の練習問題 2.7 で気にしなくて良いようにした。

練習問題 2.7

 区間のオブジェクトは端点を二つ持ち、upper-bound (lower-bound) によって大きい方 (小さい方) を返すようにした。

(define (upper-bound interval)
  (max (car interval) (cdr interval)))

(define (lower-bound interval)
  (min (car interval) (cdr interval)))

計算量的な問題で以下のように make-intervalcar 部を小さい方、cdr 部を大きい方とするべきだろうと思う。と言うのも upper-boundlower-boundmul-interval などで同じオブジェクトに対して複数回呼ばれるため無駄な計算が増えてしまう。

(define (make-interval a b)
 (if (< a b)
     (cons a b)
     (cons b a)))
(test-section "practice 2.7")

(test "upper-bound" 3
      (^[] (upper-bound (make-interval 3 0))))

(test "lower-bound" 0
      (^[] (lower-bound (make-interval 3 0))))

練習問題 2.8

 差の場合は、引かれる方の最大値から引く方の最小値が、新しい区間の最大に、引かれる方の最小値から引く方の最大値が新しい区間の最小値になる。よって定義は以下のようになる。

(define (sub-interval x y)
  (make-interval (- (upper-bound x) (lower-bound y))
                 (- (lower-bound x) (upper-bound y))))
(test-section "practice 2.8")

(test "sub-interval"
      (cons 8 -2)
      (^[] (sub-interval (make-interval 10 3)
                         (make-interval 5 2))))

(test "sub-interval"
      '(100 . 0)
      (^[] (sub-interval (make-interval 100 25)
                         (make-interval 25 0))))

練習問題 2.9

区間の幅 (width) は、上限と下限の差の半分である。 幅は、区間によって規定される数値の不確かさの程度である。

(Page 101).

幅という単語からは上限と下限の差であることはイメージできるが、半分ということなので精度に近いものだろうということで理解した。

 まず具体例から考えてみる。以下では width という幅を求める関数には区間が渡され、区間[2,5] のように表現することにする。

// 加算
width([2, 5]) = 3.0/2 = 1.5
width([3, 8]) = 5.0/2 = 2.5
width([2, 5]) + width([3, 8]) = 1.5 + 2.5 = 4.0

add-interval([2,5], [3,8]) = [5, 13]
width([5, 13]) = 8.0/2 = 4.0

//減算
width([3, 8]) = 5.0/2 = 2.5
width([2, 5]) = 3.0/2 = 1.5
width([3, 8]) + width([2, 5]) = 2.5 + 1.5 = 4.0

sub-interval([3,8], [2,5]) = [-2, 6]
width([-2, 6]) = 8.0/2 = 4.0

よって、加算と減算に関しては width の結果の関数として表現可能できそうである。関数であるので width の結果の演算になっていれば良く、。これを示すと。

// 加算
// a < b, c < d とする
width([a, b]) = (b-a)/2 = t
width([c, d]) = (d-c)/2 = s
width([a+c, b+d]) = {b+d-(a+c)}/2 = {(b-a)/2} + {(d-c)/2} = t + s

// 減算
// 同じく a < b, c < d とする
width([a, b]) = (b-a)/2 = t
width([c, d]) =  (d-c)/2 = s
width([a-d, b-c]) = {b-c-(a-d)}/2 = {(b-a)/2} + {(d-c)/2} = t + s

よって関数となることを示せた。

 次に積算と除算については具体例で考えてみる。

//積算1
width([3,8]) = (8-3)/2 = 2.5 = t1
width([2,5]) = (5-2)/2 = 1.5 = s1
// それぞれの要素間の積は 3*2 = 6, 3*5 = 15, 8\*2 = 16, 8\*5 = 40 であるので
width([6,40]) = (40-6)/2 = 17 

//積算2
width([4,10]) = (10-4)/2 = 3.0 = t2
width([0,5]) = (5-0)/2 = 2.5 = s2
// それぞれの要素間の積は 0, 20, 0, 50 となるので
width([0,50]) = (50-0)/0 = 25

// 以上の二つを同じ関数では表現できないので、関数化不可能である。除算も同様だと思う。

練習問題 2.10

 ゼロを跨ぐ区間で除算を行うと問題となる理由は y=1/x のグラフを見てみるとわかりやすい (グラフ:wolframalpha)。

 0 での除算は未定義である上、 0 付近での除算が大きい数字になるにも関わらず、現在の div-interval では区間の両端でのみ考えているため誤った結果を返してしまう。

(define (div-interval x y)
  (mul-interval
   x
   (make-interval (/ 1.0 (upper-bound y))
                   (/ 1.0 (lower-bound y)))))

gosh> (div-interval (make-interval 10 20) (make-interval 5 -5))
(-4.0 . 4.0)

分母となる区間の両端の積の符号が負である場合はエラーを返すようにする。

(define (div-interval x y)
  (mul-interval
   x
   (if (>= (* (upper-bound y) (lower-bound y)) 0)
       (make-interval (/ 1.0 (upper-bound y))
                      (/ 1.0 (lower-bound y)))
       (error "ゼロを跨ぐ区間です"))))

gosh> (div-interval (make-interval 10 20) (make-interval 5 -5))
*** ERROR: ゼロを跨ぐ区間です

Aizu SICP 第10,11回

 一回一回の読書会が短めだったため二つ分です。

 第 10 回から 2 章に入りました。2 章は P231 までと長めですがここも面白そうな話題が多いです。

 P84 2 章 データを用いた抽象化の構築 ~ P 99 練習問題 2.6 までやりました。

読書会について

 読書会にあたって slack の Thread を利用しているのだが、コードなどを共有しようとするとかなり場所を取る上、コードのハイライトなどができない (そういう意図で使うことを想定していないと思うので当たり前なのだが) ため、コードの共有には Gist などを利用するべきだろうかと考え中。

2 データを用いた抽象化の構築

 ここからは焦点が手続きからデータに移って行く。

なぜプログラミング言語に複合データが必要なのでしょうか。その理由は、複合手続きが必要である理由と同じです。プログラムを設計する概念レベルを引き上げ、設計のモジュール性を高め、言語の表現力を強くしたいからです。 手続きを定義できることによって基本演算よりも高い概念レベルで手続きを扱 えるようになるように、複合データオブジェクトを構築できることによって、言語の基本データオブジェクトよりも高い概念レベルでデータを扱えるようになります。

(Page 85).

今更だが、この本では、抽象性が高いものが扱えるほど良いプログラミング言語であるという前提がある。少しそれについて考えてみると、ここでも言っている通り、それによって単純に言語の表現力が強くなるという点では良いのだが、抽象性が上がることによって発生する弊害というものありはする。

 例えば単純な例として、抽象度が高い言語を使っていると言語の裏でどのようなことが行われているのかというのが見えにくくなることがある。ただ、自分としても基本的には抽象度は高い方が良いだろうということには賛成である。というのも抽象度が高い言語というのは抽象度をあえて低くした状態で書ける。つまり大は小を兼るということであり、まずはとりあえず抽象度が低い状態で書いていき、抽象度を上げた方が良いと思ったタイミングで抽象度を上げることができる。最初から抽象度が高い状態でプログラミングをすることは (特に、書きながら考えているような時などのプログラムの仕様が明確でない場合) 難しい上に無駄になって辛いことが多い。

 したがって両方を兼るという意味で、プログラミング言語は抽象度が高い (表現力が強い) 方が良いと言って良さそうだと思った。


プログラムの中のデータオブジェクトをどうやって表すかを扱う部分と、データオブジェクトをどうやって使う かを扱う部分とを分離するという汎用的なテクニックは、データ抽象化 (data abstraction) と呼ばれる強力な設計手法です。

(Page 85~86).

 抽象化という単語についてだが、データをどのように表現するかとそれをどう使うかを分離すること、ここを指してデータ抽象化と呼ぶらしい。そう言われると、手続きの抽象化というのも、それがどう実装されているかとそれをどう使うかを分離することを指していることがわかった (しかし P88 の 2.1 ですぐにこれについて言及されているが、そこでも「手続き抽象化」というような単語は表れない。そもそもそれこそが手続きであるとも言えるかもしれない)。また、

ここでは、データ抽象化によって、プログラムの部品間に適切な抽象化の壁 (abstraction barrier) を建てられるようになるというこ とを見ていきます。

(Page 87).

この抽象化の壁というのも、データ抽象化が指す境界線を指しているように考えられる。


具体的には、データ主導プログラミング (data-directed programming) というテクニックを導入します。これは、それぞれのデータ表現を独立して設計し、それらを加法的 (additively) に (つまり、修正なしに) 組み合わせられるようにするものです。

(Page 88).

 最初は総称関数をイメージしたが多分それだろう。2 章の後半で表れるようだ。


2.1 データ抽象化入門

 データ抽象化についてもう少し詳しく書かれている。

2.1.1 例: 有理数の数値演算

まずは、分子と分母から有理数を構築する方法はすでに持っていると仮定しましょう。

(Page 89).

さらっと書かれていたが、これができるかどうかが抽象化が上手く働いているかの基準になりそうだ。まだ実装が無い状態でも、それがどのように実装されているかという詳細を気にする必要はないという抽象化の特性により、そもそもそれが存在していなくとも、それを使う手続きの実装時に (実際には動かないという以外の) 不都合は生じない。そしてこれを指して

ここでは、プログラムを合成していくうえでの強力な戦略である希望的思考 (wishful thinking) を使っています。有理数をどうやって表現するのか、numer, denom, make-rat という手続きをどう実装するのか、まだ何も言っていません。 それでも、もしこれらの手続きを持っていたとすると、足し算、引き算、かけ 算、割り算、等価性のテストは、次のような関係を使って実行できます。

(Page 89).

というように希望的思考 (wishful thinking) と呼ぶようだ。

練習問題 2.1

(define (make-rat n d)
  (let* ([abs-n (abs n)]
         [abs-d (abs d)]
         [g (gcd abs-n abs-d)]
         [sign (if (> (* n d) 0) 1 -1)])
    (cons (* sign (/ abs-n g)) (/ abs-d g))))

if は式なので (Lisp では基本的に全てが式であるので) どこでも使える。


 読書会の疑問に condif の使い分けについて疑問があがった。基本的に三分岐以上の場合は cond を、二分岐の場合は if、一分岐 (真また偽の時だけある処理をすること) の場合は whenunless を用いる。

2.1.2 抽象化の壁

一般的に、データ抽象化の底にある考え方は、それぞれのデータオブ ジェクトの型に対して、それさえあればその型に対するどんな演算も行えるような基本演算セットを特定し、その後はデータを操作するのにそれらの演算し か使わないようにするというものです。

(Page 93).

上の単純な例を引き続き使って、有理数パッケージを設計するにあたって、gcd を実行するタイミングを構築時にするか選択時にするかを最初の段階で決められないとします。この場合、データ抽象化という方法を使うことによって、その決定を後回しにしつつ、システムのほかの部分の開発を進めるということができるようになります。

(Page 95).

ここでも基本的に抽象化は良いものとして言われているが、問題が起こることを予期して抽象化を行うことのコストと、その問題が実際に起こることによるコストを考えると、どちらを取ればよいのかというのは本当に難しいように思う。

 例えば、この後の cons の実装例のように、有理数のデータを lambda を使うことになるかもしれない、ということを想定して、現在のペアで実装されている有理数へのアクセッサーとして carcdr の別名としてのアクセッサーを用意することは、明かに過剰な心配に思える。なので単に carcdr をそのままアクセッサーとして使っても良いのではないかとも考えられるだろうと思ってしまう。しかし、それとは逆に単に別名を与えるだけで抽象化の壁を構築できるならばしておくべきではないかとも考えられるというのもある。

 このようなバランスを考慮することは現在あたっている問題によって変わり、経験や勘が占める部分が大きいように思え、とても難しいところだなあと思った。

練習問題 2.2

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

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

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

(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 (midpoint access-f point1 point2)
  (/ (+ (access-f point1) (access-f point2)) 2))

(define (midpoint-segment seg)
  (let* ([start-point (start-segment seg)]
         [end-point   (end-segment seg)]
         [mid-x (midpoint point-x start-point end-point)]
         [mid-y (midpoint point-y start-point end-point)])
    (make-point mid-x mid-y)))

練習問題 2.3

矩形を表すために二点によって長方形が構成されているとした。

(define (make-rec point-a point-b)
  (cons point-a point-b))

(define (start-point rect)
  (car rect))

(define (end-point rect)
  (cdr rect))

(define (points-diff x-or-y p1 p2)
  (abs (- (x-or-y p1) (x-or-y p2))))

(define (periphery rect)
  (let ([sp (start-point rect)]
        [ep (end-point   rect)])
    (* 2 (+ (points-diff point-x sp ep) (points-diff point-y sp ep)))))

(define (area rect)
  (let ([sp (start-point rect)]
        [ep (end-point   rect)])
    (* (points-diff point-x sp ep) (points-diff point-y sp ep))))

2.1.3 データとは何か

一般的に、データというものは、何らかのセレクタとコンストラクタの集合に加え、それらが有効な表現となるために満たさなければならないと規定された条件によって定義されるものと考えることができます。5

(Page 96).

 つまりデータというのはこれさえ満たせればなんでも良いということになる。条件によって定義されるものとのことだが、この定義というものは基本的にセレクタとコンストラクタの定義に対する条件であるように思える。そうであるならばデータというのは条件付き手続きの集合というように見ていいのだろうか。

5 意外なことに、この考え方は厳密に定式化することが非常に難しいものです。

(Page 96).

面白そうな話題であるので今度ちゃんと調べてみたい。


(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 (cons- x y)
  (lambda (m)
    (cond ((= m 0) x)
          ((= m 1) y)
          (else (error "Argument not 0 or 1: CONS" m)))))

これは、今の段階ではただの面白い考え方のように思えるかもしれませんが、手続きによるデータの表現というものは、私たちのプログラミングのレパートリーの中で中心的な役割を果たしています。このプログラミングスタイルはよくメッセージパッシング (message passing) と呼ばれ、第 3 章でモデル化とシミュレーションの問題を扱う際には、これを基本的な道具として使うことになります。

(Page 98).

 自信が無いのだが (cons 3 2) という手続きによって作られる以下のようなデータがあるとき、

(lambda (m)
  (cond ((= m 0) 3)
        ((= m 1) 2)
        (else (error "Argument not 0 or 1: CONS" m))))

これに対してメッセージ 0 を送ると 3 が返り、メッセージ 1 を送ると 2 が返ってくる。これを指してメッセージパッシングと呼べると考えていいのだろうか。

追記:

(define (cons- x y)
  (lambda (m)
    (cond ((equal? m :car) x)
          ((equal? m :cdr) y)
          (else (error "Argument not 0 or 1: CONS" m)))))

gosh> ((cons- 3 4) :car)
3
gosh> ((cons- 3 4) :cdr)
4

こうすると Smalltalk っぽくなってよりメッセージパッシング感が出た。


練習問題 2.4

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

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

展開してみる。

(car- (cons- 2 3))
;;
(car- (lambda (m) (m x y)))
;;
((lambda (m) (m x y)) (lambda (p q) p))
;;
((lambda (p q) p) x y)
;;
x

正しく x が取り出せる。cdr については car と同じようにすればよい。

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

練習問題 2.5

(define (cons- x y)
  (* (expt 2 x) (expt 3 y)))

(define (car-cdr pair base)
  (let loop [(pair pair) (count 0)]
    (if (= (modulo pair base) 0)
        (loop (/ pair base) (+ count 1))
        count)))

(define (car- pair)
  (car-cdr pair 2))

(define (cdr- pair)
  (car-cdr pair 3))

car-cdr では名前付き let と呼ばれるものを利用している。

練習問題 2.6

頭がごちゃごちゃになっていたので宿題

継続を用いた割り込み処理の実装 (のための継続の学習)

やりたいこと

 sleep などで入力した値だけ処理を停止させておきながら、キーボードが入力された時にそれを見て、それによって停止を中断したりするような割り込みのような処理をしたい。継続使えそうじゃないかと思ったので gauche で実装を試みた。

読む人の時間を奪わないためにまず結論

 最終的に、継続を使う以前に、sleep している処理と並列してキーボード入力を監視、ある入力を受け取ったら sleep から抜けるという方法はわからなかったが、I/O (今回はキーボード入力) に対してタイムアウトを実装すれば間接的に n 秒 sleep しつつ、入力を待つということが実装できることに気付いた。その点でググったら都合良く gauche を使って実装している例があったので解決した。長時間かかる処理にタイムアウトをつける

 継続についての理解が進んだので良かった。最終的に、最初に引数 n を渡して継続を利用した関数を作りそれを呼び出す度に毎回 1 秒スリープして n 回呼び出したら以降は sleep しないような関数、というものを作成したところで解決策がみつかったので終了した。

 以下は継続を勉強した時のメモになる。

継続

 以前から継続という概念については読んだりしていたが、実際に使用して何かをしたこともなく理解しているのかわからないのでまず継続について学びなおした。

まず適当に検索して見つけたページを読んだ。 なんでも継続

処理をひとつづきのパイプのようなものだと考えて、 どこでも良いがどこかをすぱっと切ってみる。その切り口の下側が上側の継続である(図3)。

概念の説明としてはここが一番しっくりきた。

 [末尾再帰と継続]で使われている木の葉の数を数えるプログラムを見てみる。

(define (leaf-count/cps tree cont)
  (if (pair? tree)
      (leaf-count/cps (car tree)
        (lambda (n)
          (leaf-count/cps (cdr tree)
            (lambda (m) (cont (+ n m))))))
      (cont 1)))

(define tree '((a . b) (c . d) . e))

gosh> (leaf-count/cps tree values)
5

(values は多値を返すための関数)

上のプログラムがパッと見難しいので順を追って評価した。lambda 式内で入れ子に表れる nm については区別のために便宜上 - を付与した。

(leaf-count/cps '((a . b) (c . d) . e) values)

;; ↓

(let ((tree '((a . b) (c . d) . e))
      (cont values))
  (leaf-count/cps (car tree)
                  (lambda (n)
                    (leaf-count/cps (cdr tree)
                                    (lambda (m)
                                      (cont (+ n m)))))))

;; ↓

(leaf-count/cps '(a . b)
                (lambda (n)
                  (leaf-count/cps '((c . d) . e)
                                  (lambda (m)
                                    (values (+ n m))))))

;; ↓

(let ((tree '(a . b))
      (cont (lambda (n)
              (leaf-count/cps '((c . d) . e)
                              (lambda (m)
                                (values (+ n m)))))))
  (leaf-count/cps (car tree)
                  (lambda (n-)
                    (leaf-count/cps (cdr tree)
                                    (lambda (m-)
                                      (cont (+ n- m-)))))))

;; ↓

(leaf-count/cps 'a
                (lambda (n-)
                  (leaf-count/cps 'b
                                  (lambda (m-)
                                    ((lambda (n)
                                       (leaf-count/cps '((c . d) . e)
                                                       (lambda (m)
                                                         (values (+ n m)))))
                                     (+ n- m-))))))

;; ↓

((lambda (n-)
   (leaf-count/cps 'b
                   (lambda (m-)
                     ((lambda (n)
                        (leaf-count/cps '((c . d) . e)
                                        (lambda (m)
                                          (values (+ n m)))))
                      (+ n- m-)))))
 1)

;; ↓

(leaf-count/cps 'b
                (lambda (m-)
                  ((lambda (n)
                     (leaf-count/cps '((c . d) . e)
                                     (lambda (m)
                                       (values (+ n m)))))
                   (+ 1 m-))))

;; ↓

((lambda (m-)
   ((lambda (n)
      (leaf-count/cps '((c . d) . e)
                      (lambda (m)
                        (values (+ n m)))))
    (+ 1 m-)))
 1)

;; ↓

((lambda (n)
   (leaf-count/cps '((c . d) . e)
                   (lambda (m)
                     (values (+ n m)))))
 (+ 1 1))

;; ↓

((lambda (n)
   (leaf-count/cps '((c . d) . e)
                   (lambda (m)
                     (values (+ n m)))))
 2)

;; ↓

(leaf-count/cps '((c . d) . e)
                (lambda (m)
                  (values (+ 2 m))))

というように評価されていく。このように見ていくと、cont にうまいこと以降に行われるべき処理が入っており、関数の呼び出し元に戻ることなく処理が最後まで行われることが伺える。

呼び出し側は、leaf-countの戻り値を受け取って処理を続けるかわりに、 leaf-countを呼び出す時点の継続を関数の形にしてcontとして渡すのだ。

というのはこれを言っているのがわかった。

継続渡し形式では、関数からのreturnという概念が無くなる。呼び出し元が指定した継続contを結果の値を引数として呼び出すことが、returnと等価になるわけだ。

これも上の評価で実際にそうなっているのがよくわかった。


 次に実際に Scheme 上で継続を使って実装する方法を探して、[お手元マルチスレッド]という項で継続を用いたマルチスレッド(もどき)を実装しているのでこれを読んでみた。使いたい人のための継続入門

Schemeにはcall/ccという呪文があって、 大域脱出だの例外機構だのマルチスレッドさえ実装できる。 しかし、call/ccは決して怪しい動作をするものなんかじゃなく、 ある意味、とても普通の関数である。 このことを理解してもらうために、call/ccなどと省略せずに、 call-with-current-continuationという正式名称に注目してみよう。

(fact/cps 10 (lambda (a) (* 2 a)))

fact/cps は上は[なんでも継続]であった reaf-count/cps と同じようなものなので、 (fact 10) を計算のあとの継続として (lambda (a) (* 2 a)) があるものだということになる。これを call/cc を使って書くと以下のようになる。

( 2 (call/cc (lambda (cont) (cont (fact 10)))))
contには(lambda (a) (
2 a))が渡ってくると考えられそうだ。 fooの素に相当する現在の継続の素を改めて書く必要はない。

ただし以下の話が続く。

;; call/ccの継続渡し形式への書き換えを試みてみる
((lambda (cont) (cont (fact 10)))
(lambda (a) ( 2 a)))
しかし、よくよく考えると、(
2 …)式の続きの計算はどうなるんだろう?
厳密に考えると、read-eval-print-loopがあるはずで、 次のread-eval-printが延々待ってるハズである。 これは以降の説明でも重要な点で、無視できないので仕方がない。 PRINT-AND-NEXT-REPLというものを便宜的に持ち込もう。 というわけで、次のようにするとしよう。
;; call/ccの継続渡し形式への書き換えを試みてみる(PRINT-AND-NEXT-REPL導入版)
( 2 ((lambda (cont) (cont (fact 10)))
(lambda (a) (PRINT-AND-NEXT-REPL (
2 a)))))

call/cc式の外側にある2倍を行う処理もそのまま残留している。 もし、
;; 継続渡し形式への変換と混同しちゃった版
((lambda (cont) (cont (fact 10)))
(lambda (a) (PRINT-AND-NEXT-REPL (* 2 a))))
という風な継続渡し形式への変換を予想された方は注意。 call/ccは継続渡し形式に変換する関数ではなく、 あくまで、call/cc式自身の継続(自分の値を待っている計算)を自動的に作り、 それをcall/ccの引数であるprocedureに渡して、 そのprocedureをcallするという関数だ。

見事に勘違いしていた。call/cc は外側の継続を持っているが、call/cc 継続自体の存在が call/cc の外側から無くなるわけではない。


保存した継続kは今までの説明のまま機械的に変換すると、 (lambda (a) (PRINT-AND-NEXT-REPL (+ x a z)))になるはずだが、 これは正確ではなかったということだ。
;; 実は不正確だった継続
(lambda (a) (PRINT-AND-NEXT-REPL (+ x a z)))
正しくは、(今のGaucheでは)継続kは (lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))だったのだ。 なぜなら、第二引数であるcall/cc式を評価する前に 第一引数であるxは評価されて1を得ていたからだ。

;; より正確な継続
(lambda (a) (PRINT-AND-NEXT-REPL (+ 1 a z)))
つまり、Gaucheでは左から順に引数を評価するために、

;; 引数の評価順とcall/ccの位置
;; (1) xが評価される
;; (2) call/cc式が評価される
;; (3) zが評価される
;; (4) +が3つの値に適用される

(+ x call/cc式 z)
この式の第二引数のcall/cc式を評価する前に、 すでにxの値が環境から取り出されて1になっており、 call/cc式の継続(続きの計算)には 「環境からxの値を取り出す」という計算は含まれてないのだ。

逆に言えば評価すらも継続の処理一部として考えられるということになる。


もっと細かいことを言えば、 (lambda (a) (PRINT-AND-NEXT-REPL (# 1 a z)))であり、 もし、継続を保存後に(set! + *)とか(set! + max)などとしても、 やはり加算を行なうのである。

Common Lisp ではリストの先頭は関数とみなしてまず引数を評価していたような気がするので確かめたところやはりそうだった。

CL-USER> (undef-func (print 3))

; in: UNDEF-FUNC (PRINT 3)
;     (UNDEF-FUNC (PRINT 3))
;
; caught STYLE-WARNING:
;   undefined function: UNDEF-FUNC
;
; compilation unit finished
;   Undefined function:
;     UNDEF-FUNC
;   caught 1 STYLE-WARNING condition

3 ; Evaluation aborted on #<UNDEFINED-FUNCTION UNDEF-FUNC {1003B1DCB3}>.
CL-USER>

コンパイル時の warning が出ているが、実行時には 3 と表示された後にエラーが出ている。つまり関数の評価の前に引数から評価されている。しかし以下のような話が続いた。

実は今のGaucheでは (lambda (a) (PRINT-AND-NEXT-REPL ((identity +) 1 a x)))なので 破壊後の+の値である#が計算されて(# 1 2 10)から10が返る。 最初の(identity +)が引数の評価より後なのだ。 実は+などの様な組込み関数を使わずにユーザ定義関数を使う場合にも最後に評価される。 というか、むしろ逆で組込み関数の場合に最適化のために 引数が評価されるより前に#に評価済みになっているのだ。

一応試してみる。

(define adding
  (lambda a
    (apply + a)))

gosh> (define k #f)
k
gosh> (define x 1)
x
gosh> (adding x (call/cc (lambda (cont) (set! k cont) 2)) x)
4
gosh> (set! x 10)
10
gosh> (k 2)
13
gosh> (set! adding max)
#<subr (max arg0 :rest args)>
gosh> (k 2)
10

確かに継続 k の実行時に addingmax として振る舞っている。 Common Lisp ではどうなってるのか (組み込み関数とユーザー定義関数を区別しているのか) を調べる手段がわからなかった。


 本題のお手元マルチスレッド (お手軽マルチスレッド?) の部分と部分継続の項の前例をやっていて継続についてある程度理解が進んだ気がした。次に 「sleep 中にキーボード入力で任意のタイミングで sleep を解除する」というものを実装しようとした。

 考えた方法は、継続を利用して呼び出す度に 1 秒 sleep する関数を実装し、それを呼ぶ度にキーボード入力を見る処理を挟むというもの。とりあえず sleep の部分を実装した。

(define cont-sleep #f) ; 継続保存用

(define (sleep/cps n)
  (let ([n-rest n])
    (call/cc (^[cc] (set! cont-sleep cc)))
    (if (not (= n-rest 0))
        (begin
          (sys-sleep 1)
          (set! n-rest (- n-rest 1))
          #t)
        #f)))

gosh> (sleep/cps 3)
#t
gosh> (cont-sleep)
#t
gosh> (cont-sleep)
#t
gosh> (cont-sleep)
#f

期待通りの動作をした。しかし、この間にキーボード入力を見に行くということをするとしても、このキー入力自体にタイムアウトなどがなければ、正しい時間スリープすることができないことに気がついた。ここで read に対してタイムアウトが実装できれば良いということに気付いたので検索したところみつかった。

 長時間かかる処理にタイムアウトをつける。詳細についてこのページで解説されているが、この関数では、継続を脱出のために利用している。

おわり

(16. 継続)http://www.shido.info/lisp/scheme_cc.htmlleaf-generator が全く理解できていない。