CS 22
Clab 23: Event-driven Simulation
Here is the sicp queue code:
<![CDATA[
(define (front-ptr queue) (car queue))
(define (rear-ptr queue) (cdr queue))
(define (set-front-ptr! queue item) (set-car! queue item))
(define (set-rear-ptr! queue item) (set-cdr! queue item))
(define (empty-queue? queue) (null? (front-ptr queue)))
(define (make-queue) (cons '() '()))
(define (front-queue queue)
(if (empty-queue? queue)
(error "FRONT called with an empty queue" queue)
(car (front-ptr queue))))
(define (insert-queue! queue item)
(let ((new-pair (cons item '())))
(cond ((empty-queue? queue)
(set-front-ptr! queue new-pair)
(set-rear-ptr! queue new-pair)
queue)
(else
(set-cdr! (rear-ptr queue) new-pair)
(set-rear-ptr! queue new-pair)
queue))))
(define (delete-queue! queue)
(cond ((empty-queue? queue)
(error "DELETE! called with an empty queue" queue))
(else
(set-front-ptr! queue (cdr (front-ptr queue)))
queue)))
]]>
We will need this in much of what follows.
We want to throughly understand the simulator for digital circuits
presented on pp. 273-285.
The authors present the material in a top-down manner using
abstraction and appropriate wishful thinking (ie. assume we can work
out the details later). Having gone through that, it is more fun to
implement it in a bottom-up fashion. That way we can test things as
we go along and get those legal CS highs. So, make sure you have all
the queue stuff loaded and lets start on p. 283. The agenda is the
structure that will hold tasks yet to be performed in the simulation.
Selectors and constructors for the agenda are defined on pp. 283-285.
Here it is. Put this in a drscheme window (and file) with the queue stuff
and press execute.
<![CDATA[
;;;Implementing agenda
(define (make-time-segment time queue)
(cons time queue))
(define (segment-time s) (car s))
(define (segment-queue s) (cdr s))
(define (make-agenda) (list 0))
(define (current-time agenda) (car agenda))
(define (set-current-time! agenda time)
(set-car! agenda time))
(define (segments agenda) (cdr agenda))
(define (set-segments! agenda segments)
(set-cdr! agenda segments))
(define (first-segment agenda) (car (segments agenda)))
(define (rest-segments agenda) (cdr (segments agenda)))
(define (empty-agenda? agenda)
(null? (segments agenda)))
(define (add-to-agenda! time action agenda)
(define (belongs-before? segments)
(or (null? segments)
(< time (segment-time (car segments)))))
(define (make-new-time-segment time action)
(let ((q (make-queue)))
(insert-queue! q action)
(make-time-segment time q)))
(define (add-to-segments! segments)
(if (= (segment-time (car segments)) time)
(insert-queue! (segment-queue (car segments))
action)
(let ((rest (cdr segments)))
(if (belongs-before? rest)
(set-cdr!
segments
(cons (make-new-time-segment time action)
(cdr segments)))
(add-to-segments! rest)))))
(let ((segments (segments agenda)))
(if (belongs-before? segments)
(set-segments!
agenda
(cons (make-new-time-segment time action)
segments))
(add-to-segments! segments))))
(define (remove-first-agenda-item! agenda)
(let ((q (segment-queue (first-segment agenda))))
(delete-queue! q)
(if (empty-queue? q)
(set-segments! agenda (rest-segments agenda)))))
(define (first-agenda-item agenda)
(if (empty-agenda? agenda)
(error "Agenda is empty -- FIRST-AGENDA-ITEM")
(let ((first-seg (first-segment agenda)))
(set-current-time! agenda (segment-time first-seg))
(front-queue (segment-queue first-seg)))))
]]>
Once we have the constructors and selectors, we can play with an
agenda. Execute the following. If you don't get what I got, try to
figure out what is wrong and call me over if
you are stuck.
<![CDATA[
> (define triagenda (make-agenda))
> triagenda
(0)
> (add-to-agenda! 1 'fstact triagenda)
> (add-to-agenda! 2 'secact triagenda)
> triagenda
(0 (1 (fstact) fstact) (2 (secact) secact))
> (add-to-agenda! 1 'bsecact triagenda)
((fstact bsecact) bsecact)
> triagenda
(0 (1 (fstact bsecact) bsecact) (2 (secact) secact))
>
]]>
Hmm. This might be interesting. Continue with:
<![CDATA[
> (add-to-agenda! 4 'fst4act triagenda)
> (add-to-agenda! 4 'sec4act triagenda)
((fst4act sec4act) sec4act)
> triagenda
(0 (1 (fstact bsecact) bsecact) (2 (secact) secact) (4 (fst4act sec4act) sec4act))
>
]]>
This is interesting. The simulation time is 0. We have two
things to do at time 1 (fstact and bsecact), one thing to do at
time 2 (secact), and two things to do at time 4 (fst4act and sec4act).
Make sure that you understand how the agenda code is handling these
insertions.
Now do the following:
<![CDATA[
> (current-time triagenda)
0
> (segments triagenda)
((1 (fstact bsecact) bsecact) (2 (secact) secact) (4 (fst4act sec4act) sec4act))
> (first-agenda-item triagenda)
fstact
> triagenda
(1 (1 (fstact bsecact) bsecact) (2 (secact) secact) (4 (fst4act sec4act) sec4act))
> (current-time triagenda)
1
> (add-to-agenda! 1.5 'fst1andhalf triagenda)
> triagenda
(1
(1 (fstact bsecact) bsecact)
(1.5 (fst1andhalf) fst1andhalf)
(2 (secact) secact)
(4 (fst4act sec4act) sec4act))
>
]]>
The selectors, current-time, segments, and first-agenda-item seem
to all work.
Note that first-agenda-item returned the first thing on the agenda
(fstact) without removing it and set the simulated time
to 1 (that of the first agenda item.
Then we added something to the agenda that was put in the proper
place. Make sure you see how the code is achieving these things.
Ask questions if you have them.
Now the agenda is really supposed to have functions in the queues. I
put atoms in just to test it. The propagate function on p. 281 really
'runs' the simulation. It goes through the agenda executing the
functions in the queues. Some of those functions will add other
functions to the agenda. To test propagate on our simple triagenda,
we will define a slightly modified version that will print the atoms
now in the queues instead of excuting the functions that will be
there later. Add the following to your definitions window, execute and
save.
<![CDATA[
(define (displayb x) ;;;writes x followed by a blank. returns " "
(begin (display x)
(display " ")
" "))
;;; test version of propagate from p. 281
(define (propagate)
(if (empty-agenda? the-agenda)
'done
(let ((first-item (first-agenda-item the-agenda)))
(displayb first-item) ;;;remove displayb for regular version
(remove-first-agenda-item! the-agenda)
(propagate))))
;;; To build-up original triagenda after pressing execute
(define triagenda (make-agenda))
(add-to-agenda! 1 'fstact triagenda)
(add-to-agenda! 2 'secact triagenda)
(add-to-agenda! 1 'bsecact triagenda)
(add-to-agenda! 4 'fst4act triagenda)
(add-to-agenda! 4 'sec4act triagenda)
(add-to-agenda! 1.5 'fst1andhalf triagenda)
(define the-agenda triagenda) ;;; because author's propagate
;;; uses global the-agenda
]]>
Then do the following in the interaction window.
<![CDATA[
> the-agenda
(0
(1 (fstact bsecact) bsecact)
(1.5 (fst1andhalf) fst1andhalf)
(2 (secact) secact)
(4 (fst4act sec4act) sec4act))
> (propagate)
fstact bsecact fst1andhalf secact fst4act sec4act
done
> the-agenda
(4)
]]>
propagate went through the-agenda printing the stuff in the queues
in the order of the agenda not the chronological order in which
they were added to the agenda.
The real propagate will execute the functions in the queues. While
doing its work, propagate emptied the-agenda.
It may not look it.
BUT the-agenda IS EFFECTIVELY EMPTY. Also the simulated time is now
4, that of the last agenda item 'executed'.
Now get rid of the triagenda stuff and change the definition of
propagate back to that in the book (by removing the displayb) and
evaluate the definition by pressing the execute button. Now
propagate will go through the-agenda and execute the functions in the
queues.
So, where are we? Well, we have the tools to put functions in an
agenda with a specified time for execution. We also have the ability
to execute all the functions in an agenda. We now need to get some
functions on theagenda.
So check the text's descriptions of the following, put them in
your definitions window, save, and press execute.
<![CDATA[
(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)))))
(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))
(define (after-delay delay action)
(add-to-agenda! (+ delay (current-time the-agenda))
action
the-agenda))
(define (probe name wire)
(add-action! wire
(lambda ()
(newline)
(display name)
(display " ")
(display (current-time the-agenda))
(display " New-value = ")
(display (get-signal wire)))))
]]>
Notice that whenever the signal changes on a wire, all its
action-procedures are executed.
Now we can actually make a wire and see what happens. Try
the following in your interactions window.
<![CDATA[
> (define the-agenda (make-agenda))
> (define teswire (make-wire))
> (probe 'teswire teswire)
teswire 0 New-value = 0
> (set-signal! teswire 1)
teswire 0 New-value = 1
done
>
]]>
Look at the code implementing this and make sure you understand
what is happening. the only reason we are seeing output is that
the probe made outputing one of the action-procedures for teswire.
We can make a wire. Let's make an inverter.
So check the text's descriptions of the following on page 277, put them in
your definitions window, save, and press execute.
<![CDATA[
(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 inverter-delay 2)
(define (logical-not s)
(cond ((= s 0) 1)
((= s 1) 0)
(else (error "Invalid signal" s))))
]]>
Note that inverter defines an internal procedure invert-input. If
executed invert-input will put the lambda() function on the agenda
to be executed at inverter-delay amount of time after the current
simulated time. That lambda() function (when executed) will set
the signal on the output wire.
Now do the following in the interactions window.
<![CDATA[
> (define the-agenda (make-agenda))
> the-agenda
(0)
> (define tesin (make-wire))
> (define tesout (make-wire))
> (get-signal tesin)
0
> (get-signal tesout)
0
> (inverter tesin tesout)
ok
> (get-signal tesin)
0
> (get-signal tesout)
0
> the-agenda
(0 (2 (#<procedure>) #<procedure>))
> (propagate)
done
> (get-signal tesin)
0
> (get-signal tesout)
1
> the-agenda
(2)
]]>
Let's review what we are looking at. We defined the-agenda setting the
simulated time to 0. The wires start with default values of 0.
The call to inverter (through its call to add-action!) put the function call
(set-signal! output new-value) on the agenda to be executed at
time 2 but did not change the signals on tesin or tesout.
propagate runs the simulation which essentially executes (and modifies)
the-agenda. So after the call to propagate, the signal on wire
tesout has been changed to 1 (logical-not of the input 0) and the simulated
time is 2. Now try:
<![CDATA[
> (set-signal! tesin 1)
done
> the-agenda
(2 (4 (#<procedure>) #<procedure>))
> (get-signal tesin)
1
> (get-signal tesout)
1
> (propagate)
done
> the-agenda
(4)
> (get-signal tesin)
1
> (get-signal tesout)
0
]]>
Make sure you understand every output.
Now look at the definition of and-gate on page 277.
<![CDATA[
(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)
]]>
In order to run, it needs a delay time and a function logical-and that
takes two inputs. If both inputs are 1, logical-and should return 1.
If either input is not a 0 or a 1, logical-and should announce an
error. Otherwise, logical-and should return 0. Here is a delay.
<![CDATA[
(define and-gate-delay 3)
]]>
You define and
test a logical-and function, then test the and-gate, just like we
tested the inverter above. Then do ex. 3.28 on page 277. Define and
test your or-gate. If you finish 3.28 and I haven't started talking
yet, do 3.29 on page 278.
<![CDATA[
> (define the-agenda (make-agenda))
> (define ain (make-wire))
> (define bin (make-wire))
> (define cout (make-wire))
> (and-gate ain bin cout)
ok
> (get-signal ain)
0
> (get-signal bin)
0
> (get-signal cout)
0
> the-agenda
(0 (3 (#<procedure> #<procedure>) #<procedure>))
> (set-signal! ain 1)
done
> (set-signal! bin 1)
done
> (propagate)
done
> (get-signal ain)
1
> (get-signal bin)
1
> (get-signal cout)
1
> the-agenda
(3)
]]>
So it looks right for inputs of 0,0 (the default wire values) and
inputs of 1,1. Here is 0,1.
<![CDATA[
> (set-signal! ain 0)
done
> (get-signal ain)
0
> (get-signal bin)
1
> the-agenda
(3 (6 (#<procedure>) #<procedure>))
> (propagate)
done
> (get-signal cout)
0
> the-agenda
(6)
]]>
Looks good, cout got changed to a 0 after the and-gate-delay amount of
time. I'll check 1,0 using probes.
<![CDATA[
> (probe 'ain ain)
ain 6 New-value = 0
> (probe 'bin bin)
bin 6 New-value = 1
> (probe 'cout cout)
cout 6 New-value = 0
> (set-signal! ain 1)
ain 6 New-value = 1
done
> (set-signal! bin 0)
bin 6 New-value = 0
done
> the-agenda
(6 (9 (#<procedure> #<procedure>) #<procedure>))
> (propagate)
cout 9 New-value = 1
cout 9 New-value = 0
done
>
]]>
Looks good the value of cout was temporarily 1 again because I
set ain to 1 before I changed bin to 0.
Ask any questions you may have.
<![CDATA[
]]>
<![CDATA[
]]>
Here is a solution to ex3.10 in pdf format.
I did not expect you to do it in this much detail but thought you
might like to study it.