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.

SICP

SICP 3.2.4 Exercises

November 19, 2017 11:16

Section 3.2 ends with just a single exercise. It’s another one that relies on working by hand and thinking through the environment structure. There are no files to test, but there will be a bunch of diagrams to look at.

SICP

SICP 3.2.3 Solutions

November 5, 2017 11:23

Exercise 3.10.

In order to assign a value to W1, a call to make-withdraw is made. This creates a new frame for that call. The let statement then creates a lambda and calls it, which means another environment is created within the one used for the call to make-withdraw. This image depicts what’s going on:

Once W1 is defined, the environment diagram will look like this:

When W1 is next called with the argument 50, an execution frame is created within the environment that W1 refers to for procedure execution (E11). Let’s call this the ‘reference environment’, to make it easier to describe. This results in the following situation on the second call:

The call results in a change to the value of balance in the reference environment of W1. After the call, the picture looks like this:

For the next step a new withdraw procedure is created, and a completely separate environment chain is created. It is similar to the first but with distinct variables. Note that the code for the procedure body is shared (this represents the actual storage in memory of the code). Any calls using W2 will be executed in its reference environment E21, and only affect the variables there.

When we compare this to the text’s version of make-withdraw, we see that the alternate version involves the creation of an additional environment. In both versions, a new frame is created when make-withdraw is called. In the second, however, the let statement causes the creation of another frame, since it executes a lambda within the environment that make-withdraw uses for evaluation. The lambda that is returned and assigned to the account is created within that second environment (E11 or E21 above). Although it never again makes use of the first frame (in which initial-value is defined), that frame still remains in the chain that is the environment.

Both procedures thus work identically, as they only modify the balance value in the course of their operation. All the let statement did was rename initial-value to balance. The procedures do not rely on anything further back in the chain of frames.

To prove that the two procedures actually do produce identical output, we can run them both through the interpreter. This is the only thing that is checked in the solutions file.

Solutions 3.2.3

SICP

SICP 3.2.3 Exercises

October 28, 2017 11:05

Much like 3.2.2, this is another section with a single exercise involving environment diagrams. There will be a solution file with included code, merely to demonstrate the equivalence of the procedures. There isn’t much to say in advance of the exercises, so I’ll go over in more detail how I’ve drawn my environment diagrams. Here’s an example from the previous section, and I have a few more sample ones below.

The diagrams consist of frames, environment pointers, procedure objects, and my own evaluation boxes. Frames are boxes tinted blue, and contain a list of name-value pairs, i.e. ‘bindings’. The environment pointers may be attached to arrows, but are most often just labeled next to a frame with no arrow. The global environment’s frame is drawn using a larger box (as done in the text), and a lighter tint to show that it’s slightly special as the ‘base’ environment. The evaluation boxes indicate what is being evaluated when the diagram is depicting a point in time.

Initially the difference between environments and frames in the diagrams wasn’t entirely clear to me. The distinction is that a frame is a single box that contains variable bindings. The environment is the sequence of frames that can be followed back via pointers, which are represented by arrows. The names of the pointers are also synonymous with the ‘environment’. For example, when referring to Figure 3.1, the text says “environment D” to mean the environment that D points to. I don’t normally use labels on the arrows, or the initial arrow; the label to the left of a frame marks the start of an environment. Frames typically do not need to be named; in most cases, the number or name of the environment that begins at that frame can be used. For instance, in the diagram below, ‘Frame 21’ would refer to the box marked by E21. The environment E21 would be the sequence Frame 21 → Frame 2 → Global Frame.

Example of environments

For environment naming, the convention I typically follow is that the environment is assigned a number to distinguish it from others with the same parent, and a new digit is appended for each frame in the chain. This means that it’s usually possible to determine the ‘depth’ of an environment and also know its enclosing/parent environment just from the name. Environment ‘E213’ would be the third one created in the first environment of the second environment of the global environment. This doesn’t cover all cases, but the actual names of the environments are not themselves all that important; I just wanted something that could be mostly consistent and easy to come up with.

As I mentioned in the previous section, I also show what is in the process of being evaluated. The current code under evaluation is included in a yellow box next to the frame for it. Usually only one line of code will be written there, to indicate the line that is being evaluated. The name of the procedure (or a description, for lambdas) will be included as a label above the code box. There are many times when a procedure is in the middle of execution, but has called another procedure. In those cases, the code in the box will be slightly grayed out to show that it is not the ‘active’ frame. For a procedure that has completed evaluation, the yellow box will be smaller, and instead of code, the returned value will be shown inside it. The label on top will also use ‘<-’ to show that it is returning from the procedure.

Here is another example to clarify what happens with procedure calls. In this one, function fun2 has finished and is returning a value. The other function, fun1 is still in progress as it is awaiting the result of fun2. The definitions for the two procedures are not shown.

SICP

SICP 3.2.2 Solutions

October 22, 2017 11:23

In the following diagrams, the procedure objects are only shown one time, and then omitted in later diagrams. They are still there, it’s just not really necessary to show them each time, as that part of the diagram does not change. In our model, a procedure (the two-circle symbol with pointers to the parameter list and body, and its enclosing environment) is stored in memory somewhere. When the procedure is evaluated, that is done according to the bindings, but the stored procedure is not affected. Exactly what ‘evaluation’ is will be a major part of the next chapter; for now, we can consider that the evaluator just reads the procedure body and figures out which expression to evaluate next. In most cases I’ve added a box to my diagrams to show which line of the procedure is in the process of being evaluated.

Exercise 3.9.

Let’s go over the recursive version first. In the global environment, we have the single procedure factorial defined. We make a call to it with (factorial 6) and a new evaluation frame is created:

Factorial 6

In the course of evaluating (factorial 6), another call to factorial is made. Since factorial is defined in the global environment, the evaluation frame for any call to it is created there as well. This will proceed for each successive call to factorial, all the way to (factorial 1) at the end:

Maximum depth of factorial

Each procedure is still awaiting the value returned by the procedure calls after it. Once they return, they will finish computing the value and then return. The environment for that call can then be removed, and this will happen in the reverse order in which the environments were created.

For the iterative version, two procedures are defined in the global environment. Otherwise, the model looks initally quite similar to the recursive version, with only the code being evaluated that is different:

The first procedure calls a second one with different parameters. That means the next frame to be created will be for evaluating fact-iter with the product, counter, and max-count set to their starting values. Each call to fact-iter after that will result in a new call to fact-iter with different arguments, until it is called with counter higher than max-count (the greyed-out environments will be explained shortly):

All calls for factorial

The repeated calls once again produce new frames in the global environment. That means seven more frames are created. Why seven instead of six, as with the recursive version? That happens because of a slight difference in the way the two versions terminate. The recursive procedure counts down to 1, and then terminates at that point. The iterative version counts up, and does not terminate until the counter is past the maximum. It requires an extra call and thus one more evaluation frame. In total, eight frames are created for the iterative version.

However, as alluded to in the text’s footnote for this exercise, this model doesn’t quite tell the whole story. It turns out that it’s not really necessary for all the environments to be preserved in the iterative version. Each of these calls (save the last one) will do nothing but call a procedure and return the value of that call. Nothing in that environment will be needed again. When that is the case, it’s possible to allow that environment to disappear. Scheme actually requires this behavior It’s for this reason that I’ve grayed out all the frames — it’s not necessary for them to remain, and in fact, the interpreter will remove them. The recursive version cannot do this, since it must multiply the result by one of its own environment variables befoe returning.

Under this model, we see that the recursive version grows in space and then shrinks again. The iterative version takes up slightly more space initially, and has more calls (even with the difference in termination conditions), but it never actually requires more than one evaluation frame at a time. This mirrors the substitution model somewhat, which was shown in Figures 1.3 and 1.4 in the text.

There is no ‘solutions’ file for this section, since the procedures are explained in Section 1.2.1 in the text.

SICP

SICP 3.2 Exercises

October 15, 2017 11:25

The exercises in Section 3.2 (and some in Section 3.3) do not involve, or at least do not require, any code that needs to be verified by testing. The procedures are largely meant to be computed manually. Therefore there aren’t going to be any ‘exercise’ files for them. I will create solution files in order to demonstrate the code, but most of the actual answers are in understanding the environment model diagrams, or in working out by hand what the result is. Running it through the interpreter is as often as not just a means of finding the solution. The solutions will include my own diagrams in order to explain what happens at each step as well.

SICP

SICP 3.1.3 Solutions

August 6, 2017 11:01

Exercise 3.7.

This one doesn’t require modifying the account creation that already exists; what we’ll do instead is delegate any actions to the original account. Since that account is already considered to exist when we create a joint one, there is no need to do anything in make-joint other than to check the password and pass on the command to the original account if the password is correct. The joint account needs to work in the same way as the original, which means that make-joint must return a procedure. In this case, the ‘dispatch’ of that procedure only does one thing – check the joint accountholder’s password. If it matches, it makes a call to the original account using the original password.

There is one point of contention however. That concerns the response to invalid passwords. If make-account has a separate password-checking procedure from make-joint, then we potentially have two separate places where the checking code exist. Future changes, such as adding the ‘call-the-cops’ alarm for example, would require changes in both procedures. Doing the same thing in two places isn’t generally a good practice, especially when from an external point of view the entity (the ‘account’, whether joint or single) is expected to be the same. The users (‘bank customers’ in this case) should be able to interact with the joint account exactly as if it were a regular account. That goes even for improper interactions too; perhaps especially so.

There are several approaches to this problem. It might be feasible to delegate password responses to the original account, by delivering either a valid or invalid original password depending on whether the joint accountholder’s password is valid. We could also modify make-account to incorporate joint accounts as a special case, but there are many situations in which the original code can’t be easily modified. A robust way to deal with this is to have a separate password-checking processor. That way, both original accounts and joint accounts would always be working with the same system. Of course, that would require at least some changes to make-account, although to a lesser extent than adding in joint accounts as a special case would require.

Exercise 3.8.

If we’re considering that the addition will yield different results depending on the evaluation order of its arguments, then we have to think about what it means when we change the evaluation order. If we’re going ‘left-to-right’, that means the arguments are evaluated in sequence, with the leftmost argument is evaluated first, then the next one, and so on. If it’s ‘right-to-left’, then the rightmost argument is evaluated first, in reverse fashion from the other order. Which means what we really want is for the procedure f to give different results depending on what arguments it has been called with in the past.

In order for the results of a procedure to always be different depending on when it is called, we need some sort of stored state. (Randomness would give different resuls, but none that we could rely on). Our function f will be designed similarly to those in previous exercises, where a let variable is preserved locally in a lambda expression that is the required procedure.

Some open questions with the exercise are whether the procedure f only needs to exhibit this behavior one time, or if it can change when it’s repeated. We also don’t know if it can accept other input values besides 0 or 1. It’s definitely much easier to design one that can give the answer without any of those conditions; I originally had a solution that only fulfills the requirements of the text, but then came up with one that’s more versatile.

The first solution I have (a ‘filtering buffer’) will work only with the expressions as given in the text, and can hanle repeated calls as long as certain conditions are met. In that version the saved state is just a toggle that switches back and forth. It is thus only valid as long as the calls to f come in pairs, and the input should be limited to the values 0 and 1.

My second approach does not have limitations on its input, and works whatever the previous calls to f were. It saves two variables; one is the last input received, and another which keeps track of the last returned value. Here’s the procedure:

(define f
  (let ((returned 0)
        (last 0)
        )
        (lambda(x)
          (set! returned (+ (- returned) last))
          (set! last x)
          returned
          )
    )
  )

This function returns a value that is the negation of the most recently returned value, added to the most recent input. Suppose we call it with some value x as the input. It will save x as the last value and return some value, which we’ll call a. We can’t know what a is, since it depends on past calls. On the next call, it will return -a + x since x is currently stored as the last value. Therefore if we sum the results of two consecutive calls, we get aa + x, which is simply x. This procedure works in such a way that summing the result of any two sequential calls yields whatever the input to the first call was. In this exercise, that means our sum will come out to whatever argument is evaluated first, whether it be from the left or from the right.

Solutions 3.1.3.

SICP

SICP 3.1.3 Exercises

July 16, 2017 11:05

There are only two exercises here. The first one is an addition to code from previous exercises (Section 3.1.1 specifically). If you have not completed all the exercises for that part, you’ll need to do so, or download the solution file. The tests also rely on check-eqv? defined as it was in that file, so make sure it exists either in the old file or that you put it the new one. It’s a good idea to keep the old file as-is, with all its tests, so that if it somehow gets altered, it’ll be easier to determine where the error lies.

The second exercise initially seems difficult to test, since it asks for a function that changes its result depending on which order the arguments are evaluated in. In order to test it based on what we know how to do, there are two possible approaches. We’ll learn other ways to change evaluation order later The first is just to change the expression itself, so that (+ (f 0) (f 1)) is compared with (+ (f 1) (f 0)). It turns out that the Scheme language does not actually specify a particular order of argument evaluation. That means that while solutions to this exercise will show a difference, there’s no way to know which one is actually ‘right-to-left’ or ‘left-to-right’. The second approach is to use nested let statements. Each let works to evaluate an ‘argument’ as a variable for the let, and by changing the order of nesting, the order of evaluation is changed. This will give us a guaranteed order, since we are evaluating the arguments prior to the addition statement. By capturing the result of these let expressions, we can determine if the results are as expected.

Additionally, there’s an ‘optional’ part of the testing for the second exercise. The problem statement doesn’t clarify if the function only needs to work once, or work at any point in time. Adding more conditions makes the exercise considerably more difficult to solve, so it’s fine to ignore them, as they may not be an intended part of the exercise and thus don’t really need to be tested.

Exercises 3.1.3.