miumixu's tech blog

オンラインSICP読書女子会 #2 (1.1.7~1.1.8)

Thu, 04 Feb 2016 00:00:00 +0900

オンラインSICP読書女子会 #2 (1.1.7~1.1.8)

ということで2回目です。

まずは平方根をニュートン法で求めるという話がありました。

(define (square x) (* x x))

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- (square guess) x)) 0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

練習問題 1.6

これは前回の範囲で答えることができます。

(define (new-if predicate then-clause else-clause)
  (cond (predicate then-clause)
        (else else-clause)))

このような new-if 関数があったとして、次のように sqrt-iter を書いたらどうなるかという話ですね。

(define (sqrt-iter guess x)
  (new-if (good-enough? guess x)
          guess
          (sqrt-iter (improve guess x) x)))

new-if 関数というのは特殊形式ではないため、述語式が評価された後に結果式と代替式の どちらかを評価するわけではありません 。これは何を意味するかというと、次のような簡単な例を考えてみると理解しやすいです。

(new-if #t
        (println "true")
        (println "false"))

この例をREPLで評価してみると次のような出力を得ることができます。

"true"
"false"

これは new-if 関数が if 特殊形式のように 述語式を評価した後に結果式と代替式のどちらかのみを評価する わけではないということを意味しています。

また、 sqrt-iter 関数は再帰関数であるという性質から、平方根を計算しようとした場合に無限ループに陥いることは明白です。

練習問題 1.7

どのような数のときにうまくいかないかという話ですね。

(私はあまりよくわからなかったので後で勉強して補記するかもしれないです)

(define (average x y)
  (/ (+ x y) 2))

(define (improve guess x)
  (average guess (/ x guess)))

(define (good-enough? guess x)
  (< (abs (- guess (improve guess x))) 0.001))

(define (sqrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (sqrt-iter (improve guess x) x)))

(define (sqrt x)
  (sqrt-iter 1.0 x))

練習問題 1.8

少し悩むけど、基本的に答えは書いてあるようなものなので、今迄の平方根を計算するプログラムを修正したら動きます。

具体的には improve 関数に問題に書いてある式に落とし込んで、 good-enough? 関数も微修正します。(何を元にこの問題を解くかで多少変わりますが)

(define (improve guess x)
  (/ (+ (/ x (square guess))
        (* 2 guess))
     3))

(define (good-enough? guess x)
  (< (abs (- guess (improve guess x))) 0.001))

(define (cbrt-iter guess x)
  (if (good-enough? guess x)
      guess
      (cbrt-iter (improve guess x) x)))

(define (cbrt x)
  (cbrt-iter 1.0 x))

結構、チャットでやるとカオス :black_joker: で楽しかったです。という感じで2回目でした :smiley_cat:

オンラインSICP読書女子会 #1 (1.1.1~1.1.6)

Wed, 03 Feb 2016 00:00:00 +0900

オンラインSICP読書女子会 #1 (1.1.1~1.1.6)

オンラインSICP読書女子会 #1

これが開催された後から参加したので、私はこの部分を一緒にやってませんがやってみます。

ちなみに私はGaucheではなくてRacketにしました。Emacsでgeiserを使いたかったので、サポートされているものから選んだらRacketになりました。 (ChickenSchemeを最初に試したんですが、分数型をデフォルトで使えないみたいだったのでRacketに変更しました)

練習問題 1.1

10 ;-> 10
(+ 5 3 4) ;-> 12
(- 9 1) ;-> 8
(/ 6 2) ;-> 3
(+ (* 2 4) (- 4 6)) ;-> 6
(define a 3)
(define b (+ a 1))
(+ a b (* a b)) ;-> 19
(= a b) ;-> #f
(if (and (> b a) (< b (* a b)))
    b
    a) ;-> 4
(cond ((= a 4) 6)
      ((= b 4) (+ 6 7 a))
      (else 25)) ;-> 16
(+ 2 (if (> b a) b a)) ;-> 6
(* (cond ((> a b) a)
         ((< a b) b)
         (else -1))
   (+ a 1)) ;-> 16

練習問題 1.2

(/ (+ 5 4 (- 2 (- 3 (+ 6 (/ 4 5)))))
   (* 3 (- 6 2) (- 2 7))) ;-> -37/150

練習問題 1.3

(define (square x) (* x x))
(define (sum-of-squares x y)
  (+ (square x)
     (square y)))

(define (f a b c)
  (max (sum-of-squares a b)
       (sum-of-squares b c)
       (sum-of-squares c a)))
(f 3 4 5) ;-> 41
(f 4 5 3) ;-> 41
(f 5 3 4) ;-> 41

練習問題 1.4

(define (a-plus-abs-b a b)
  ((if (> b 0) + -) a b))
(a-plus-abs-b 10 -10) ;-> 20
(a-plus-abs-b 10 10) ;-> 20

練習問題 1.5

(define (p) (p))
(define (test x y)
  (if (= x 0) 0 y))
(test 0 (p))

適用順序評価の場合

この場合、以下のような実行結果になることが予想されます。

(test 0 (p))
(test 0 ((p)))
(test 0 (((p))))
(test 0 ((((p)))))
(test 0 (((((p))))))
...

適用順序評価の場合、 test 関数が展開されるよりも先に引数である (p) が評価されるため、無限ループに陥いります。

正規順序評価の場合

(test 0 (p))
(if (= 0 0) 0 (p))
0

正規順序評価の場合は (p) が評価されるよりも前に test 関数が展開されるはずなので、展開形となり if 特殊形式を含んだ式になります。
if 特殊形式の評価規則は適用順序評価、正規順序評価共に同じであると仮定していいので、述語式が評価された後に結果式と代替式の どちらか が評価されます。
述語式を評価した結果として結果式が評価されるため、代替式を評価することなく綺麗に終えることができます。

かな。

新しいブログはじめました

Wed, 03 Feb 2016 00:00:00 +0900

新しいブログはじめました

技術的なこととか勉強したこととか書いていきます :)

(display "Hello, my new blog!")