ストリーム

メモ

SICP勉強会の準備。
スライドを作るまえに、いったんまとめるのが好きなので。

下書き。あとでコードを載せる。

オブジェクト

かなり強引にまとめる。

  • システムを小さい部品(module)で構築したい
    • 各部品は時間とともに変化する状態をもつ
  • 部品をオブジェクトとしてモデル化する
    • 状態は状態変数で表される
    • 実世界の時間経過と計算機内の時間経過は同一視される
(define (make-withdraw blance)
  (lambda(amount)
    (set! blance (- blance amount))
    blance))

(define W2 (make-withdraw 10))
(define W2 (make-withdraw 10))
(W1 1) ; -> 9
(W1 1) ; -> 8
(W1 1) ; -> 7

(W2 3) ; -> 7
  • defineは関数を定義する(ウソだけどね)
  • set!は変数を第2引数の結果に変更する

環境とは(3.2)

lambdaについて少々。ここはカットするかもね。

束縛(binding)
変数名と値の対応
フレーム(frame)
束縛の表。同じ変数名は、高々ひとつの束縛を持つ。各フレームは、ほかのフレームへのポインタを持つ
環境(environment)
フレームの(単方向)リスト
  • 変数の探しかた
  • 評価の規則。変数適用の方法
    • 組合せを各要素を評価する->演算子を適用する
    • lambdaはあたらしいフレームを作る
  • 普通の関数を例として
  • 銀行を例として

オブジェクトの問題点

さらっとね。

いくつか例を示すかもしれない。

ストリーム

ストリームの概要説明。

  • 数学では、x(t)は時間に応じて変化する値を表わす。関数自体は変化しないのに。
  • さらにtを離散時間とすると、この関数を並び(シーケンス)としてモデル化できる
    • 並びは、無限かもしれない
  • この並びをストリームとして表現する
    • ストリームは遅延評価付きリスト

遅延リスト

遅延リストとはなんぞや、の説明。いったんストリームはおいておく。

  • リストだと非常に効率の悪い計算がある
    • しかし反復よりかは、分かりやすい
    • これが遅延リストだと効率がよくなる
  • いくつかの基本的な関数の定義
    • cons-stream,stream-car,stream-cdrを使う
    • consとcar、cdrと代らないよね
  • 遅延ストリームはdelayとforceを使う
    • 特殊形式
(define (stream-ref s n)
  (if (= n 0) 
      (stream-car s)
      (stream-ref (stream-cdr s) (- n 1))))

(define (stream-map proc s)
  (if (stream-null? s)
      the-empty-stream
      (cons-stream (proc (stream-car s))
		   (stream-map proc (stream-cdr s)))))

(define (stream-for-each proc s)
  (if (stream-null? s)
      'done
      (begin (proc (stream-car s))
	     (stream-for-each proc (stream-cdr s)))))

(define (display-stream s)
  (stream-for-each display-line s))

(define (display-line x)
  (display x)
  (newline))

(define (take-stream n s)
  (if (= n 0)
      the-empty-stream
      (cons-stream (stream-car s)
		   (take (- n 1) (stream-cdr s)))))
効率がいい理由
  • 見た目は、ほとんど同じ
  • 関数を展開していくと、無駄な処理が行なわれないことを示す
(stream-car
 (stream-cdr
  (stream-filter filter?
		 (stream-enumerate-interval 10000 1000000))))

(define (stream-enumarate-interval low high)
  (if (> low high)
      the-empty-stream
      (cons-stream low
		   (stream-enumarate-interval (+ low 1) high))))
  • ifとbeginの解説
(define (stream-filter pred s)
  (cond ((stream-null? s) the-empty-stream)
	((pred (stream-car s)) 
	 (cons-stream (stream-car s)
		      (stream-filter pred (stream-cdr s))))
	(else (stream-filter pred (stream-cdr s)))))
  • condの解説
delayとforceの実装

むむ、もしかしたらこの節はカットするかもしれない。