This section presents us with another system of moderate complexity. It’s one that is difficult to test without having most of the system in place. Luckily for us, we don’t actually have to implement or test the agenda system itself; we’re only creating and working with the components. That said, it’s not that easy to test these components without having the system defined. For this reason, the tests are reserved until later in the file, after the various components have been defined, and after several exercises are completed. It is possible to use the tests without going through the later parts of the chapter, although it may be useful to at least read through the section in order to understand what’s going on (or what to do when something isn’t working as expected).

These tests are slightly different from those in previous sections, in that we’re going to use the system itself to process the tests. If you think about it, this system is designed to handle a sequence of operations in a time-stepped simulation. That the whole process is simulated makes it fairly useful for testing, as we can add in our testing operations without really disturbing the system. However, we don’t just want to use the probes as defined in the text, which simply report the value. We can do better and define our own automated test action, which can actually check that a wire has the value we want and report a pass/fail. This test is defined as follows:

(define (test-signal wire expected-value testing-time . name)
  (define (test-action)
    (let ((actual-value (get-signal wire))
          )
      (if (not (null? name))
          (display (car name))
          (display "test")
          )
      (display ": ")
      (if (= expected-value actual-value)
          (display "passed")
          (begin
            (display "test failed: Expected ")
            (display expected-value)
            (display " but was ")
            (display actual-value)
            )
          )
      (newline)
      )
    )
ㅤ ㅤ
  (add-to-agenda! testing-time
                  test-action
                  the-agenda
                  )
  'test-added
  )

We give the test a wire to check, the value we expect it to have, and the time to perform the test. When the test executes, it will compare the wire’s value with the expected one, and report either success or failure (along with an optional description of the test). This will not affect any other tests and doesn’t interrupt the agenda. About the only thing we need to do is choose some ‘reasonable’ time for when to execute the test action, as it should fire after the signals have had time to propagate.

This form of test doesn’t handle everything the way we might want, however. These won’t work if there’s something that causes an error in the action, since that typically causes the agenda to exit before we can get to the test. Some additional work will be necessary to fix those sorts of bugs.

It’s also true that in the more complex components there may be quite a lot of signals we need to test. The typical scenario is to set a number of inputs, then at a later time, check a set of outputs. In order to process those, I added a more complex ‘test-series’ action block that accomplishes this. This will take a set of input signals, wires, and expected outcomes and run them in order, with a given ‘waiting time’ between them at which to check for a result. The reason this is wrapped up as a series is because these tests actually depend on the order in which they are run. The system being simulated takes a different amount of time to switch from some values to other values. At least one exercise questions what the expected propagation time will be, and the provided test series should be sufficient to give a ‘worst-case’ instance to check against.

Since we need to test those wires directly, it’s important to ensure that the wires used for the test series end up being the same as those in the device being tested. For these devices that take multiple inputs, interpreting them correctly for testing also means making sure that the MSB (or LSB) of our input and output is the same as the MSB and LSB of the input, at least when that matters, as with an adder. That basically means making sure that the lists of input and expected output are in the right order for being processed — in the tests I have them listed MSB first, which means they can be read left-to-right as numbers generally are.

If you aren’t terribly sure of what the MSB and LSB even are Most and Least Significant Bit, that highlights another potential stumbling block in this section: It’s rather difficult to know how to work these exercises unless you have a decent understanding of digital circuits, or at a minimum the Boolean logic that they rely on. The original students this book was written for might well have had more familiarity with the topic, so this example would have been relatable to them. It might not be the same for you. Digital computers may well be built from gates like these, but it’s not necessary to even know that fact to understand how to program them.

To aid in this matter, I’ve included logical procedures (e.g. logical-and) that can be used by the gates. I would still recommend finding a primer on Boolean logic if it’s unfamiliar to you. The key concept to understand with respect to Boolean logic is that everything can only have two values, either a 1 or 0 (also referred to as ‘true’ or ‘false’). That places a hard limit on the possible range that a group of inputs and outputs can have. For this reason, truth tables (which just enumerate all possible values) are often used to explain how the output is generated from the input. There are likely countless sources available that will cover the subject. Two brief ones that I’ve found on the web are this one that discusses logic gates, and this page from Electronics Post which includes a discussion of DeMorgan’s Rules, an invaluable aid in figuring out Exercise 3.29.

If you are stuck trying to figure out exactly what something does (or what it’s supposed to do), try building a truth table using all available wires/signals. Follow them through without worrying about the ‘time delay’ initially. That can be calculated later, if it is necessary. As an example, here’s the truth table for the half-adder.

A B S C 
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 1

This is constructed by cycling the inputs through all possible combinations (for n inputs, there will be 2ⁿ entries), and calculating the outputs for the combination one at a time. Here, the inputs A and B go through all possible values they could have, and the outputs S and C are computed for each row.

If you’re having trouble seeing how the inputs here produce the outputs, try adding the ‘internal’ signals D and E to the table; each of those is dependent on how the gates process the other signals, and since these are all two-input gates, you only need to refer to two gates (or inputs) at any one time. It is also only necessary in a truth table to enumerate the possible set of inputs, since those are the only values that can be controlled. Sometimes in a more complex arrangement there can be a sequence of outputs that is essentially ‘unreachable’ (e.g. in the half-adder, S and C can never both end on 1 as long as the inputs are properly set to 1 or 0). Variations in time delays may indeed complicate the actual results at particular times, which is part of the point of creating a simulator. However, for these circuits the truth table will always be eventually correct, once the overall delay time has passed.

The other piece of the puzzle would be in understanding how these Boolean-valued signals are used to create more complex mathematical systems. Even though every individual digital signal can only be 1 or 0, we can interpret a collection of signals in such a way that it means something more than just true or false (or 0/1). In particular for these addition examples, we will treat a set of values as a binary number. Each digit of a binary number can only be a 0 or 1, but if we put those digits in some order, then they represent larger numbers. It’s just like the decimal system — we only ever write the digits 0 to 9, but putting them in a certain order lets us create any possible whole number. Binary digits are also commonly referred to as ‘bits’, especially when they are part of a representation of other information.

The full adder gives a good demonstration of interpreting signals this way. Below is the truth table of the full adder. It shows the outputs interpreted as a binary number, the decimal equivalent of that number, and an arithmetic expression using the input values. In this reading, the actual ‘sum’ is made up of two digits (Cout and SUM). As with digital numbers, binary values are written left to right, so Cout appears on the left. This is where the idea of bit significance comes in; the ‘most signficant’ bit is the one that represents the largest value; the ‘least significant’ is the bit that represents the smallest value. Since Cout means a value of 2, it would be the MSB here. We can also see that the carry input (Cin) is working as just another single-bit digit that’s being added to A and B.

A B Cin Cout|SUM Decimal  Equivalent expression
0 0  0    00        0       0 + 0 + 0 = 0
0 1  0    01        1       0 + 1 + 0 = 1
1 0  0    01        1       1 + 0 + 0 = 1
1 1  0    10        2       1 + 1 + 0 = 2
0 0  1    01        1       0 + 0 + 1 = 1
0 1  1    10        2       0 + 1 + 1 = 1
1 0  1    10        2       1 + 0 + 1 = 2
1 1  1    11        3       1 + 1 + 1 = 3

The diagram in the text for Exercise 3.30 (Figure 3.27) shows how full adders can be chained to produce a multi-digit adder. This allows us to work with binary numbers of any needed size. I do want to note that this exercise uses a naming convention where the higher subscript represents smaller bit values. That means A1, B1, and S1 represent the MSB, and An, Bn, etc. are the least significant bits. This makes it easier to discuss and deal with devices of arbitrary bit-length, since bit 1 is always the MSB. It is not really the most common convention, since most interfaces have standardized on how many bits wide they are, and the highest named bit is usually the MSB (not to mention that numbering from 0 is also fairly typical as well). The important thing is simply to ensure that your device interprets them in the expected order, since otherwise the tests will indicate errors.

This set of exercises relies on the queue definitions from the text. These are included in the library file ‘queuedef’, and they should be simple enough to not be dependent on which Scheme interpreter you are using.

Queue definitions

Exercises 3.3.4.