Quirksand

SICP

SICP 3.3.3 Exercises

August 11, 2019 10:54

This section presents us with another system of moderate complexity, 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. 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 simulation makes it fairly useful for testing. However, we don’t just want to use the probes as defined in the text; they simply report on their value. We can do better and define our own automated test action, which can actually check that a wire has the value we wnat 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. The tests don’t handle everything, as they 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.

We also find that in the more complex components there may be a lot of signals we need to test. Those are generally of a form where we want 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. Note that to ease the readability of the inputs and outputs for the ripple adder, I reverse them when feeding them to the system; this is because the description and the diagram in the text suggests that the inputs in a list are given with the LSB first, instead of MSB first which is how binary numbers are usually written.

If you aren’t terribly sure of what the MSB and LSB even are, Most/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 least the Boolean logic which they rely on. The original students of the course this book was written for might well have had more familiarity with the topic. It might not be the same for you. Although digital computers are built from gates like these, it’s not critical to understand logic gates to be good at programming them, although knowing Boolean logic is something that will indeed help.

To aid in this matter, I’ve added my own logical procedures (e.g. logical-and) for use in the gates. I would recommend finding a primer on Boolean logic if it’s unfamiliar to you. The key concept to understand 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 necessary. In the truth table, list all possible input combinations, and then compute the outputs for each set of inputs one at a time. 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

The inputs here are A and B (so 4 possible combinations), and the outputs are S and C. 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 just two inputs,so you only need to refer to the input for the gate and the rules for its output at any one time. You also only need to cover all inputs; for any n inputs there will be 2^n^ entries in the table, no matter the outputs. That does mean sometimes not all output states are ‘reachable’ (e.g. in the half-adder, S and C can never both be 1 as long as the inputs are properly set to 1 or 0).

Variations in time will complicate the way the results are produced, which is the point of creating a simulator, but for these circuits the truth table will always eventually indicate the correct state of the circuit, once its 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 them as binary numbers. 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 number. Binary values are also commonly referred to as ‘bits’, especially when they are part of a representation of other information.

The full adder demonstrates how binary signals are used to represent numbers. Below is the truth table of the full adder, with the outputs interpreted as a binary number. 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. 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 also 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 then be chained to produce a multi-digit adder. This allows us to work with binary numbers of any needed size. I also want to note that, in reference to the exercise, the figure in the text is somewhat misleading. In particular, the signal labeled just C is a carry input. This is not the argument C required in the procedure. The problem description describes C as being generated by the circuit; it is what I’d call the ‘carry out’ from the adder. The signal on the diagram that corresponds to this is actually Cn, the output of the last adder in the chain.

Exercises 3.3.4.