Do you think Computer Science equals building websites and mobile apps?
Are you feeling that you are doing repetitive and not so intelligent work?
Are you feeling a bit sick about reading manuals and copy-pasting code and keep poking around until it works all day long?
Do you want to understand the soul of Computer Science?
If yes, read SICP!!!
In part 3 we can finally start talking about the digital circuits.
The wire is an object. It has two states:
signal-value represents the current signal on the wire (0 or 1), initialized to 0.
action-proceduresis a collection of procedures to be run when signal changes on the wire.
The constructor of wire is implemented using the *message-passing*style. If you don’t know what is message-passing, take a look at my previous post.
(define (make-wire) (let ((signal-value 0) (action-procedures '())) (define (set-my-signal! new-value) (if (not (= signal-value new-value)) (begin (set! signal-value new-value) (call-each action-procedures)) 'done)) (define (accept-action-procedure! proc) (set! action-procedures (cons proc action-procedures)) (proc)) (define (dispatch m) (cond ((eq? m 'get-signal) signal-value) ((eq? m 'set-signal!) set-my-signal!) ((eq? m 'add-action!) accept-action-procedure!) (else (error "Unknown operation: WIRE" m)))) dispatch)) (define (call-each procedures) (if (null? procedures) 'done (begin ((car procedures)) (call-each (cdr procedures)))))
With the constructor at hand, we can now define the following operations on wires.
(define (get-signal wire) (wire 'get-signal)) (define (set-signal! wire new-value) ((wire 'set-signal!) new-value)) (define (add-action! wire action-procedure) ((wire 'add-action!) action-procedure))
You can see that these procedures are more of a syntatic sugar. I think they are very self explanatory and need no more words.
Let’s make gates out of wires.
inverter consisted of two wires,
The functionality is to invert signal. But it happens after a delay.
(define (inverter input output) (define (invert-input) (let ((new-value (logical-not (get-signal input)))) (after-delay inverter-delay (lambda () (set-signal! output new-value))))) (add-action! input invert-input) 'ok) (define (logical-not s) (cond ((= s 0) 1) ((= s 1) 0) (else (error "Invalid signal" s)))) ;; Adds to the global the-agenda an action with a delay (define (after-delay delay action) (add-to-agenda! (+ delay (current-time the-agenda)) action the-agenda)) (define inverter-delay 2)
The AND gate is similar.
(define (and-gate a1 a2 output) (define (and-action-procedure) (let ((new-value (logical-and (get-signal a1) (get-signal a2)))) (after-delay and-gate-delay (lambda () (set-signal! output new-value))))) (add-action! a1 and-action-procedure) (add-action! a2 and-action-procedure) 'ok) (define (logical-and a b) (if (and (= a 1) (= b 1)) 1 0)) (define and-gate-delay 3)
Try to implement the OR gate by yourself.
(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 (logical-or a b) (if (and (= a 0) (= b 0)) 0 1)) (define or-gate-delay 5)
OK, we have implemented everything now. Let’s try to make a real circuit!
Make a simple circuit
Let’s make a circuit as in the following picture:
First let’s make a global agenda called
(define the-agenda (make-agenda))
Now let’s make the wires and connect them:
; make wires (define a1 (make-wire)) (define a2 (make-wire)) (define a3 (make-wire)) (define output (make-wire)) ;connect the circuit (and-gate a1 a2 a3) (inverter a3 output)
Let’s pause now, and take a look at
the-agenda, what do you think it looks like now? Empty, right? Wrong!
the-agenda ;(0 (2 (#[compound-procedure 14]) #[compound-procedure 14]) (3 (#[compound-procedure 15] #[compound-procedure 16]) #[compound-procedure 16]))
It may be a bit hard to make sense of it, but it means:
The current simulation time is 0.
There are 1 procedure scheduled to run at time 2(#[compound-procedure 14]), and 2 procedures schedulted to run at time 3(#[compound-procedure 15] and #[compound-procedure 16]).
You may wonder, well, we just simply connected the wires and haven’t done anything yet, why there are procedures already scheduled to run in the agenda?
The key is the
accept-action-procedure! inside the
(define (accept-action-procedure! proc) (set! action-procedures (cons proc action-procedures)) (proc))
Notice that it execute the new
proc right after it put it in the
In order to understand why it does it, let’s compare what we get if it does not do it.
Let’s run everything again with the
Then if we check
the-agenda again, it shows:
Which one do you think is correct?
Let’s judge using common sense.
One thing to note is that all wires have signal 0 by default. Imagine in real life you assembled a circuit just like this, what will happen right after everything is connected?
a2 both are 0 now, that means
and-gate-delay time later,
a3 will become 0. Notice also that
a3 is already 0 now, that means
inverter-delay time later, output will be 1.
Now you should see that even without changing any signal in the circuit, after construction, the circuit will start running automatically, because all the wires have initial signal 0.
OK, now we set the
a1’s signal to 1 and call
(set-signal! a1 1) (propagate) the-agenda ; (3)
Next we set the
a2 also to 1 and
(set-signal! a2 1) (propagate) the-agenda ; (8)
Try to go through what really happened and see if you really understand what is going on.