sicp-3-3-4-a-simulator-for-digital-circuits

#lang racket
(require racket/mpair)

;;;;;;;;;;
;; 3.28 ;;
;;;;;;;;;;

(define (or-gate a1 a2 output)
  (define (or-action-procedure)
    (define 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)

;;;;;;;;;;
;; 3.29 ;;
;;;;;;;;;;

;; Defining an or-gate this way, the or-gate-delay would equal one and-gate-delay
;; plus two inverter-delay's because the first two inverters can run
;; simultaneously, but then the other gates must run in sequence.

(define (alternate-or-gate a1 a2 output)
  (define b1 (make-wire))
  (define b2 (make-wire))
  (define c (make-wire))
  (inverter a1 b1)
  (inverter a2 b2)
  (and-gate b1 b2 c)
  (inverter c output)
  'ok)

;;;;;;;;;;
;; 3.30 ;;
;;;;;;;;;;

(define (half-adder a b s c)
  (define d (make-wire))
  (define e (make-wire))
  (or-gate a b d)
  (and-gate a b c)
  (inverter c e)
  (and-gate d e s)
  'ok)

(define (full-adder a b c-in sum c-out)
  (define s (make-wire))
  (define c1 (make-wire))
  (define c2 (make-wire))
  (half-adder b c-in s c1)
  (half-adder a s sum c2)
  (or-gate c2 c2 c-out)
  'ok)

(define (ripple-carry-adder as bs ss c)
  ; The book goes from index n to index 1; we go from n - 1 to 0.
  (unless (= (length as)
             (length bs)
             (length ss))
    (error "Lists must be same length -- RIPPLE-CARRY-ADDER" as bs ss))
  (define zero-wire (make-wire))
  (set-signal! zero-wire 0)
  (define (loop i carry)
    (cond [(< i 0) 'ok]
          [else
            ; use c for the last carry
            (define next-carry (if (zero? i) c (make-wire)))
            (full-adder (list-ref as i)
                        (list-ref bs i)
                        carry
                        (list-ref ss i)
                        next-carry)
            (loop (sub1 i) next-carry)]))
  (loop (sub1 (length as))
        zero-wire))

;; How much is one ripple-carry-delay in terms of inverter-delay, or-gate-delay,
;; and and-gate-delay?

;; Look at the sicp-3-3-4-test-cases file to see these test runs.

;; For the given delay times:

;; inverter-delay = 2
;; and-gate-delay = 3
;; or-gate-delay  = 5

;; we had:

;; 1 half-adder-delay = 8 = 1 and-gate-delay + 1 or-gate-delay

;; Surprisingly, one full-adder-delay was also 8, and the ripple-carry-adder-delay,
;; for n = 3, was 48 = 2 * n * (or-gate-delay + and-gate-delay).

;; I would not have gotten this right just by looking at the formulas.  The
;; function boxes trigger whenever an input wire changes state.  They do not
;; necessarily run in sequence.  For me that makes it hard to see.

;; Also I think the answer depends on the exact delay times for the primitive
;; gates.  If one primitive gate were a bottleneck, that would change the function
;; box delay times in terms of the primitive gate delay times.  For example, if
;; the inverter delay were huge compared to the others, the half-adder-delay would
;; be one and-gate-delay plus one inverter-delay, instead of one and-gate-delay
;; plus one or-gate-delay.

;;;;;;;;;;
;; 3.31 ;;
;;;;;;;;;;

;; Here is some half-adder test code:

;; TRY A HALF-ADDER

(displayln 'HALF-ADDER)
(define in5 (make-wire))
(set-signal! in5 1)
(define in6 (make-wire))
(define sum (make-wire))
(define carry (make-wire))
(displayln 'BEFORE)
(probe 'in5 in5)
(probe 'in6 in6)
(probe 'sum sum)
(probe 'carry carry)
(displayln 'DURING)
(half-adder in5 in6 sum carry)
(propagate)
(displayln 'AFTER)
(probe 'in5 in5)
(probe 'in6 in6)
(probe 'sum sum)
(probe 'carry carry)
(printf "~n")

;; When you run this "with proc", you get:

;; HALF-ADDER
;; 'done
;; BEFORE
;; in5 0  New-value = 1
;; in6 0  New-value = 0
;; sum 0  New-value = 0
;; carry 0  New-value = 0
;; DURING
;; 'ok
;; sum 8  New-value = 1
;; 'done
;; AFTER
;; in5 8  New-value = 1
;; in6 8  New-value = 0
;; sum 8  New-value = 1
;; carry 8  New-value = 0

;; When you run this "without proc", you get:

;; HALF-ADDER
;; 'done
;; BEFORE
;; DURING
;; 'ok
;; 'done
;; AFTER

;; So even though running add-action! without proc will add the proc to the wire's
;; action-procedures list, it is not getting put on the agenda.  So when we later
;; call propagate, nothing happens.  This is because after-delay is the function
;; that adds actions to the agenda, and after-delay is not called until we run the
;; proc.

;; For example, if you look at inverter, the proc that gets added to the
;; action-procedures list for the input wire is invert-input.  But invert-input
;; calls after-delay, and after-delay calls add-to-agenda!.  So you have to call
;; the proc to put it on the agenda.

;;;;;;;;;;
;; 3.32 ;;
;;;;;;;;;;

;; Even though all the actions in a given segment occur at the same time, their
;; order still matters, some come before others.  If the segment used a LIFO
;; container like a stack, then the actions would be performed in the wrong order.
;; We need a FIFO container like a queue to preserve the correct ordering.

;; To get LIFO behavior, I used the deque construction from 3.3.2.  Then you just
;; had to change insert-queue! to front-insert-deque! etc.  This was easier than
;; trying to rewrite the book program to use a list.

;; I couldn't get the exact book example to work.  But I did get this example:

;; TRY AN AND-GATE
(define in1 (make-wire))
(set-signal! in1 1)
(define in2 (make-wire))
(set-signal! in2 0)
(define out (make-wire))
(and-gate in1 in2 out)
(set-signal! in2 1)
(probe 'in1 in1)
(probe 'in2 in2)
(probe 'out out)
(propagate)

;; Here we have two wires, in1 = 1 and in2 = 0, then we apply an and, then we
;; change the 0 to a 1, and then we propagate.  So the out wire should be 1, which
;; it is with the FIFO queue:

;; 'done
;; 'done
;; 'ok
;; 'done
;; in1 0  New-value = 1
;; in2 0  New-value = 1
;; out 0  New-value = 0
;; out 3  New-value = 1
;; 'done

;; However, with the LIFO deque, out first becomes 1 at time 3 but then reverts to
;; 0 as the original set-signal! of in2 to 0 is hit coming out of the segment:

;; 'done
;; 'done
;; 'ok
;; 'done
;; in1 0  New-value = 1
;; in2 0  New-value = 1
;; out 0  New-value = 0
;; out 3  New-value = 1
;; out 3  New-value = 0
;; 'done

;; So the book is right.  Order within segments matters.  We need a FIFO
;; container.