Scheme - 質問システムの実装(データベースの保守)

計算機プログラムの構造と解釈
Gerald Jay Sussman, Julie Sussman
Harold Abelson (原著) 和田 英一 (翻訳)

開発環境

• OS X Mavericks - Apple(OS)
• Emacs (CUI)、BBEdit - Bare Bones Software, Inc. (GUI) (Text Editor)
• Scheme (プログラミング言語)
• MIT/GNU Scheme (処理系)

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の4(超言語的抽象)、4.4(論理型プログラミング)、4.4.4(質問システムの実装)、4.4.4.1(駆動ループと具体化)、4.4.4.2(評価器)、単純質問、合成質問、フィルタ、4.4.4.3(パターンマッチにより表明を見つける)、ドット末尾を持つパターン、4.4.4.4(規則とユニフィケーション)、4.4.4.5(データベースの保守)、問題 4.70を解いてみる。

その他参考書籍

• Instructor's Manual to Accompany Structure & Interpretation of Computer Programs

問題 4.70

手続きadd-assertion!とadd-rule!のlet束縛の目的は、問題のようにletにより束縛しないと、cons-streamの第2引数の式の評価はdelayにより遅延されることになるので、THE-ASSERTIONSやTHE-RULESへ意図と違う値が代入されてしまうから。(具体的には無限ループに陥る。)

単純な例で手動で確認。

;; stream、aの定義
(define a (1 2 3 4 5 …))

;; let束縛有りの場合

(let ((old-a (1 2 3 4 5)))
  (set! a (cons-stream 0 old-a)))

;; この時点でold-aは(1 2 3 4 5)

;; aの先頭の値を取り出す。
(stream-ref a 0)

0
;; aの先頭の次の値を取り出す
(stream-ref a 1)

1

;; let束縛が無しの場合
(set! a (cons-stream 0 a))

;; aの先頭の値を取り出す
(stream-ref a 0)

0
;; aの先頭の次の値を取り出す(ここで違いが出現)
(stream-ref a 1)
;; ここで(cons-streamの第2引数のaが評価されて、そのaの先頭の値は0。よって
0

;; なので、let束縛が無いと、永遠に0が取り出されることになる。(無限ストリームになる。)

実際に簡単な例での違いを確認。

コード(BBEdit)

sample.scm

(define ones (cons-stream 1 ones))

(define a (cons-stream 1 (add-streams ones a)))

(define b (cons-stream 1 (add-streams ones b)))

;; ストリームの先頭に0を追加
;; let束縛有りの場合
(let ((old-a a))
  (set! a (cons-stream 0 old-a)))

;; let束縛無しの場合
(set! b (cons-stream 0 b))

入出力結果(Terminal, REPL(Read, Eval, Print, Loop))

$ scheme
MIT/GNU Scheme running under MacOSX
Type `^C' (control-C) followed by `H' to obtain information about interrupts.

Copyright (C) 2011 Massachusetts Institute of Technology
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Image saved on Saturday October 26, 2013 at 11:02:50 PM
  Release 9.1.1 || Microcode 15.3 || Runtime 15.7 || SF 4.41 || LIAR/C 4.118
  Edwin 3.116

1 ]=> (load "./sample.scm")

;Loading "./sample.scm"... done
;Value 2: (1 . #[promise 3])

1 ]=> (stream-ref a 0)

;Value: 0

1 ]=> (stream-ref a 1)

;Value: 1

1 ]=> (stream-ref b 0)

;Value: 0

1 ]=> (stream-ref b 1)

;Value: 0

1 ]=> ^D
End of input stream reached.
Moriturus te saluto.
$