Hatena::Groupsicp

SICP読書記

2009-12-14

SICP 3.5 ストリームのところをgaucheでやるときの置き換え

 SICP 3.5 ストリームのところをgaucheでやるときの置き換え - SICP読書記 を含むブックマーク はてなブックマーク -  SICP 3.5 ストリームのところをgaucheでやるときの置き換え - SICP読書記

  • cons-stream -> stream-cons
  • the-empty-stream -> stream-null
  • stream-enumerate-intervalは以下でok
(define (stream-enumerate-interval start end)
  (stream-iota (- end start) start))

など。以下参考に。http://practical-scheme.net/gauche/man/gauche-refj_170.html#SEC479

(追記)SICPを解くに当たっては、以下のstream.scmを使うべき。でも、直感的にはgaucheの実装が気持ちが良い。

http://d.hatena.ne.jp/rucifer_hacker/20090127/1233037207

いずれにしてもここではstreamを理解しさえすればいいので、こまけえことは気にするな!の方向で。

問題 3.50

問題 3.50 - SICP読書記 を含むブックマーク はてなブックマーク - 問題 3.50 - SICP読書記

(use util.stream)

(define (display-stream stream)
  (if (stream-null? stream)      (undefined)      (begin         (display (stream-car stream))        (display "\n")
        (display-stream (stream-cdr stream)))))


(define (stream-map proc . argstreams)
  (if (stream-null? (car argstreams))
          stream-null
          (stream-cons
                (apply proc (map stream-car argstreams))
                (apply stream-map
                           (cons proc (map stream-cdr argstreams))))))

(display-stream
 (stream-map + 
        (stream 1 2 3)
        (stream 40 50 60)
        (stream 700 800 900)))

問題 3.51

問題 3.51 - SICP読書記 を含むブックマーク はてなブックマーク - 問題 3.51 - SICP読書記

(use util.stream)

(define (stream-enumerate-interval start end)
  (stream-iota (- end start) start))

(define (display-line str)
  (begin
    (display str)
    (display "\n")))

(define x (stream-map display-line (stream-enumerate-interval 0 10)))

(define main
  (begin
    (display "(stream-ref x 5)")
    (stream-ref x 5)
    (display "(stream-ref x 7)")
    (stream-ref x 7)))

> gosh p192-3.51.scm

(stream-ref x 5)0

1

2

3

4

5

(stream-ref x 7)6

7

あれ?

1回目のstream-refで5番目までのリストが消費されて、2回目でその次の7番目までが消費されるから

こんな感じになると想像してた

0

1

2

3

4

5

6

7

8

9

10

(ストリーム使い切った)



stream.scm

 stream.scm - SICP読書記 を含むブックマーク はてなブックマーク -  stream.scm - SICP読書記

なんだかgaucheのstreamの実装がSICPの期待と違うっぽい。

以下のstream.scmを使ってやってみたら結果が違った

http://d.hatena.ne.jp/rucifer_hacker/20090127/1233037207

問題3.51

> gosh p192-3.51.scm

0(stream-ref x 5)

1

2

3

4

5(stream-ref x 7)

6

7

問題3.52

(load "./stream.scm")

(define sum 0)
(define (accum x)
  (set! sum (+ x sum))
  sum)

(define seq (stream-map accum (stream-enumerate-interval 1 20)))

(define y (stream-filter even? seq))

(define z (stream-filter (lambda (x) (= (remainder x 5) 0))
  seq))

(display-line "stream-ref y 7")
(stream-ref y 7)

(display-line "display-stream z")
(display-stream z)

これで実行

> gosh p192-3.52.scm

stream-ref y 7

display-stream z

10

15

45

55

105

120

190

210

sumの合計がどこでどうなるって言うのが一つ。

想像するに、(stream-ref y 7)では8回seqが評価されるから、1+2+...+8で40。

displayを入れて実験

> gosh p192-3.52.scm

stream-ref y 7

sum=136

display-stream z

10

15

45

55

105

120

190

210

....。あ、そうか。8つめの偶数が出てくるまで評価されるんだ。

7つめの偶数は2,4,6,8,10,12,14,16で16。1~16の合計は136。

TrishaTrisha2011/04/10 18:192YOG4g Great thinking! That really breaks the mold!

idmooddwagbidmooddwagb2011/04/12 04:42kPLDem <a href="http://jnxznjbewwui.com/">jnxznjbewwui</a>

eizyabbreizyabbr2011/04/13 07:056iMrjp , [url=http://wvvbuylirhkh.com/]wvvbuylirhkh[/url], [link=http://aebieveibhev.com/]aebieveibhev[/link], http://mtrjxksgirct.com/

2009-12-13

方針

方針 - SICP読書記 を含むブックマーク はてなブックマーク - 方針 - SICP読書記


SICPの1章は2章の準備であり、2章は3章の準備であり、3章は4章の準備であり、4章前半のメタサーキュラーインタープリタSICPのすべて。4章後半の論理型プログラミングと5章は応用あるいは補足

Twitter / yadokarielectric: SICPの1章は2章の準備であり、2章は3章の準備で ...

これを読んだので、方針をさらに変更。

3.1 代入と局所状態

3.2 評価の環境モデル

3.3 可変データでのモデル化

この辺はもうやっちゃってるところもあるけど、斜めに眺めるだけにする。

3.4 並列性:時が本質的

とりあえずこの項目名の日本語もよく分からないし、こういうのは今すでに分かってないと困る。test-and-setとかそういうのは別にSICPで勉強しなくて良いと判断してスキップ。

3.5 ストリーム

@hayato_1980 SICPでStreamまでいくと同じ感動をお手製で味わえる、という寸法

Twitter / Takayuki Kurosawa: @hayato_1980 SICPでStreamまで ...

Haskell遅延評価を理解したときにひっくり返った感動を再度味わうためにここは読む。

4章は普通に読む。少なくとも4-1~4-3までは。そこから先はそれから考えよう。

2009-11-22

問題3.9

問題3.9 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.9 - SICP読書記

再帰

(define (factorial n)
  (if (= n 1)
      1
      (* n (factorial (- n 1)))))

(factorial 6)

呼び出しのスタックトレースは以下の通り。それぞれの環境に名前をつける。

(factorial 6) [E1]

→(factorial 5) [E2]

→(factorial 4) [E3]

→(factorial 3) [E4]

→(factorial 2) [E5]

→(factorial 1) [E6]

環境の構成としては

大域環境

|

    • E6
    • E5
    • E4
    • E3
    • E2
    • E1

になる。

反復版

(define (factorial n)
  (fact-iter 1 1 n))

(define (fact-iter product count max-count)
  (if (> counter max-count)
      product
      (fact-iter (* counter product)
                 (+ counter 1)
                 max-count)))

(factorial 6)

呼び出しは

(factorial 6) [E1]

→(fact-iter 1 1 6) [E2]

→(fact-iter 1 2 6) [E3]

→(fact-iter 2 3 6) [E4]

→(fact-iter 6 4 6) [E5]

→(fact-iter 24 5 6) [E6]

→(fact-iter 120 6 6) [E7]

→(fact-iter 720 7 6) [E8]

環境の構成は

大域環境

    • E1
    • E2
    • E3
    • E4
    • E5
    • E6
    • E7
    • E8

結局どっちも大域環境下に直接全ての手続きが束縛されているので、環境も大域環境の一段階下にぶらさがる。

問題3.12

問題3.12 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.12 - SICP読書記

(define x (list 'a 'b))

(define y (list 'c 'd))

(define z (append x y))



(cdr x)
;;-> (b)

(define w (append! x y))

(cdr x)
;; -> (b c d)

問題3.13

問題3.13 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.13 - SICP読書記

(18088)> rlwrap gosh

gosh> (define (make-cycle x)

(set-cdr! (last-pair x) x) x)

make-cycle

gosh> (define z (make-cycle (list 'a 'b 'c)))

z

gosh> (last-pair z)

かえってこない〜

cycleを回り続けているはずですね。

append!も、set-car!やset-cdr!も、理解はできるが気持ちが悪い。。。

schemeは以外と普通のプログラミング言語だったと言うことで納得しよう。

問題3.14

問題3.14 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.14 - SICP読書記

(use slib)
(require 'trace)

(define (mystery x)
  (define (loop x y)
	(if (null? x)
		y
		(let ((temp (cdr x)))
		  (set-cdr! x y)
		  (loop temp x))))
  (trace loop)
  (loop x '()))

(define v (list 'a 'b 'c 'd))

(define w (mystery v))

(print w)

(trace loop)を入れてみた。

(mystery v)を評価したときのtraceは以下の通り

CALL loop (a b c d) ()
 CALL loop (b c d) (a)
  CALL loop (c d) (b a)
   CALL loop (d) (c b a)
    CALL loop () (d c b a)
    RETN loop (d c b a)
   RETN loop (d c b a)
  RETN loop (d c b a)
 RETN loop (d c b a)
RETN loop (d c b a)

つまり、最終的にreverseと同じ値を返す。

(set-cdr! x y)ってのは、要するにyの先頭にxをつけちゃってxとするっていう操作。それを末尾再帰でループしているのはreverse以外の何者でもない。

違うのは、最終的にmysteryの引数を壊しちゃうってこと。

最後で(print v)すると

(a)

になっちゃう。

2009-11-21

問題3.1

問題3.1 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.1 - SICP読書記

(define (make-accumulator initial)
  (lambda (next) (begin 
				   (set! initial (+ initial next))
				   initial)))


(define A (make-accumulator 5))

(A 10)
;; -> 15

(A 10)
;; -> 25

へえ。面白い。でも最近haskell触ってて、schemeとの共通点をちょっと見てたのでset!がちょっと違和感がある。

問題3.2

問題3.2 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.2 - SICP読書記


(define (make-monitored func)
  (define count 0)
  (lambda (arg)
	(if (eq? arg 'how-many-calls?)
		count
		(begin
		  (set! count (+ count 1))
		  (func arg)))))


(define s (make-monitored sqrt))

(s 100)
;; -> 10.0

(s 'how-many-calls?)
;; -> 1

クロージャ大好きという人の気持ちが少し分かる。


問題3.3

問題3.3 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.3 - SICP読書記

(define (make-account balance password)
  (define (withdraw amount)
	(if (>= balance amount)
		(begin (set! balance (- balance amount))
			   balance)
		"Insufficient funds"))
  (define (deposit amount)
	(set! balance (+ balance amount))
	balance)
  (define (dispatch input-password m)
	(if (eq? input-password password)
		(cond ((eq? m 'withdraw) withdraw)
			  ((eq? m 'deposit) deposit)
			  (else (error "Unknown request -- MAKE-ACCOUNT"
						   m)))
		(error "Incorrect Password")))
  dispatch)

もうメソッド呼び出しにしか見えない。

フィールドが環境に閉じ込められてるってぐらいで。

問題3.7

問題3.7 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.7 - SICP読書記

(define (make-joint account original-password new-password)
  (lambda (password m)
	(if (eq? password new-password)
		(account original-password m)
		(error "Incorrect joint account password"))))

(define peater-acc (make-account 100 'peater-password))

(define paul-acc 
  (make-joint peater-acc 'peater-password 'paul-password))

((peater-acc 'peater-password 'deposit) 50)
;; -> 150

((paul-acc 'paul-password 'withdraw) 100)
;; -> 50

見事隣の人の口座からカネを引き出すことに成功


問題3.8

問題3.8 - SICP読書記 を含むブックマーク はてなブックマーク - 問題3.8 - SICP読書記

(define f
  (let ((value undefined))
	(lambda (x) (if (eq? value undefined)
					(set! value x)
					value))))

(+ (f 0) (f 1))
;; -> 0 となる
;; つまり、gaucheは左から順に引数を評価している

2009-11-20

問題2.61

問題2.61 - SICP読書記 を含むブックマーク はてなブックマーク - 問題2.61 - SICP読書記

;; 順序づけられていない場合は、element-of-setを使って
;; リストの最後まで探索する必要があるが、
;; 順序づけられている場合は挿入位置が見つかるまで探索すればよい
;; これはsetの要素数がnの場合平均n/2の計算量になる
(define (adjoin-set x set)
  (if (null? set)
	  (list x)
	  (if (< x (car set))
		  (cons x set)
		  (cons (car set) (adjoin-set x (cdr set))))))


(print (adjoin-set 5 '(1 2 4 8 10)))
;; => (1 2 4 5 8 10)

xが入る場所を探して、見つかったら入れる。

問題2.62

 問題2.62 - SICP読書記 を含むブックマーク はてなブックマーク -  問題2.62 - SICP読書記



(define (union-set set1 set2)
	(cond ((null? set1) set2)
		  ((null? set2) set1)
		  (else  (let ((x1 (car set1))
					   (x2 (car set2)))
				   (cond ((eq? x1 x2) 
						  (cons x1 
								(union-set (cdr set1) (cdr set2))))
						 ((< x1 x2)
						  (cons x1 (union-set (cdr set1) set2)))
						 (else 
						  (cons x2 (union-set set1 (cdr set2)))))))))

(print (union-set '(1 3 5 7 9) '(0 1 2 4 7)))
;; ->  (0 1 2 3 4 5 7 9)

要するにマージソートかつuniqueしろと言ってますよね。

2.4 抽象データの多重表現

2.4 抽象データの多重表現 - SICP読書記 を含むブックマーク はてなブックマーク - 2.4 抽象データの多重表現 - SICP読書記

オブジェクト指向的な話をしているよね。

まあ細かく掘る必要ないか、ということでここもスキップ!

2.5 汎用演算のシステム

2.5 汎用演算のシステム - SICP読書記 を含むブックマーク はてなブックマーク - 2.5 汎用演算のシステム - SICP読書記

Numeric型からはじまるいろんな数値型を統一的に扱うようなことを言っているよね。まあここも飛ばすか。