Scheme - 回線の表現、次第書き(シミュレーションの例)

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

開発環境

• OS X Lion - Apple(OS)
• Emacs、BBEdit - Bare Bones Software, Inc. (Text Editor)
• プログラミング言語: MIT/GNU Scheme

計算機プログラムの構造と解釈(Gerald Jay Sussman(原著)、Julie Sussman(原著)、Harold Abelson(原著)、和田 英一(翻訳)、ピアソンエデュケーション、原書: Structure and Interpretation of Computer Programs (MIT Electrical Engineering and Computer Science)(SICP))の3(標準部品化力, オブジェクトおよび状態)、3.3(可変データでのモデル化)、3.3.4(電子回路のシミュレータ)、回線の表現、次第書き、シミュレーションの例の問題 3.31を解いてみる。

その他参考書籍

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

問題3.31

新しいアクション手続きが回線に追加されると、この手続きを直ちに走らせるように規定するという初期化が必要な理由は、初期化がないと、次第書きに追加されないから。

各回線塔の定義。

コード(BBEdit)

sample.scm

(define (or-gate a1 a2 output)
  (define (or-action-procedure)
    (let ((new-value
           (logical-or (get-signal a1) (get-signal a2))))
      (after-delay or-gate-delay
                   (lambda ()
                     (set-signal! output new-value)))))
  (add-action! a1 or-action-procedure)
  (add-action! a2 or-action-procedure)
  'ok)
(define input-1 (make-wire))
;; signal-value 0 action-procedures '()
(define input-2 (make-wire))
;; signal-value 0 action-procedures '()
(define sum (make-wire))
;; signal-value 0 action-procedures '()
(define carry (make-wire))
;; signal-value 0 action-procedures '()

初期化無し、新しい手続きをリストに追加すると同時に一回走らせない場合。

(probe 'sum sum)
;; 回線 sum
;; signal-value 0
;; action-procedures (list (lambda () (newline)…))

(probe 'carry carry)
;; 回線 carry
;; signal-value 0
;; action-procedures (list (lambda () (newline)…))

(half-adder input-1 input-2 sum carry)
;; 回線 d
;; signal-value 0
;; action-procedures '()
;; 回線 e
;; signal-value 0
;; action-procedures '()
(or-gate input-1 input-2 d)
(add-action! input-1 or-action-procedure)
;; 回線 input-1
;; signal-value 0
;; action-procedures (list or-action-procedure)
(add-action! input-2 or-action-procedure)
;; 回線 input-2
;; signal-value 0
;; action-procedures (list or-action-procedure)
(and-gate input-1 input-2 carry)
(add-action! input-1 and-action-procedure)
;; 回線 input-1
;; signal-value 0
;; action-procedures (list and-action-procedure
;;                         or-action-procedure)
(add-action! input-2 add-action-procedure)
;; 回線 input-2
;; signal-value 0
;; action-procedures (list and-action-procedure
;;                         or-action-procedure)
(inverter carry e)
(add-action! carry invert-input)
;; 回線 carry
;; signal-value 0
;; action-procedures (list invert-input
;;                         (lambda () (new-line)…))
(and-gate d e sum)
(add-action d and-action-procedure)
;; 回線 d
;; signal-value 0
;; action-procedures (list and-action-procedure)
(add-action e and-action-procedure)
;; 回線 e
;; action-procedures (list and-action-procedure)
ok

(set-signal! input-1 1)
(set! signal-value 1)
;; 回線 input-1
;; signal-value 1
;; action-procedures (list and-action-procedure
;;                         or-action-procedure)
(call-each action-procedures)
(and-action-procedure)
;; new-value 0
(after-delay 3
             (lambda () (set-signal! carry 1)))
(add-to-agenda! (+ 3 (current-time the-agenda))
                (lambda () (set-signal! carry 1))
                the-agenda)
(or-action-procedure)
(after-delay 5
             (lambda () (set-signal! carry 1)))
(add-to-agenda! (+ 5 (current-time the-agenda))
                (lambda () (set-signal carry 1))
                the-agenda)
done

(propagate)
(set-signal! carry 1)
(set! signal-value 1)
;; 回線 cary
;; signal-value 1
;; action-procedures (list invert-input
;;                         (lambda () (new-line)…))
(call-each action-procedures)
(invert-input)
;; new-value 1
(after-delay inverter-delay
             (lambda ()
               (set-signal! e 1)))
(add-to-agenda! (+ 2 (current-time the-agenda))
                (lambda () set-signal! e 1)
                the-agenda)
(call-each (lambda () (newline)…))
carry 10 New-value = 1

とりあえず出来たけど、トレースが途中からごちゃごちゃしてよく分からなくなってきたので、じっくり確認しながらトレースしなおしてみるかも。