SICP 3.3.5 Solutions

January 31, 2020 15:39

Ex. 3.33

To determine the average of two values, we add them together and divide by two (since there are two values we are averaging). So one side of the formula is the sum of the two values a and b, which is also equal to the average multiplied by two. We can use an adder block to produce the sum. Then we use a multiplier, with a constant of 2, to constrain the average and/or the sum of the two values. Visually, it looks like this:

We just need to wire up those component blocks and create the two internal connectors for the averager to be complete. There is one minor wrinkle that can arise, depending on the Scheme implementation. In some cases the average will be a rational value, even if the two values being averaged are integers. If we want to have consistent output (say as a decimal value), then the constant should be set as a decimal (i.e. 2.0) instead of a simple integer. My included tests do not check for the particular format, although they do verify that the output is approximately equal to a given decimal value (which should work regardless of the number’s format).

Ex. 3.34

The problem with this approach is that the system can only calculate a value when there is a single connection left ‘free’, i.e. unconstrained. If two of the inputs are from the same connector, then the internal multiplier can only compute a value when its multiplicands are set (technically it has the special case of forcing the product when one input is 0, but that makes no difference here). When just the product is set, the other side of the squarer will not have a value. In effect, this squarer only works in the ‘forward’ direction, calculating squares, and cannot calculate square roots.

Of note is that the squarer tests themselves cannot (or at least should not) detect the root cause of the problem, since testing should only be done using the external squarer connections. With the averager, we could make explicit tests that check to ensure no single connector sets the others. But since the squarer has only two connections, we can’t check any of the internal connections. Of course proper tests do reveal the circumstances in which the squarer fails, so we have a better understanding of the problem if we are making our tests comprehensive.

Ex. 3.35

The first alternative presented with the ‘primitive’ squarer is when b (the square) has a non-negative value. In this case, we will set a. We have to use the square root function in Scheme (sqrt) to do this. The second alternative starts with us knowing that b has no value. We first have to check if a has a value; if it does, then we set b to be the square (using multiplication or any similar function). When it does not, then neither a nor b is set, and we have nothing to process.

The remainder of the squarer primitive is functionally identical to the adder and multiplier, and only needs to be modified to use the squarer’s particular connections.

Ex. 3.36

Here is the environment diagram in full, just as the procedure for-each-except is starting to execute (in environment E4):

The first two statements create the connectors a and b. Each connector is a procedure ‘object’ that retains its own environment (E1 for a, and the not-shown E2 for b). There are additional internal procedures related to the connectors, but I’m only showing the most relevant one (set-my-value). The next statement is the call to set-value!, which is a function defined in the global environment. That will go through a series of additional procedure calls, which we’ll trace to find where the call to for-each-except happens.

The call to set-value! gets executed in E3, with the arguments as indicated. Within set-value!, the dispatch procedure of the connector is executed with the argument 'set-value!, and what is returned is the particular procedure for set-my-value defined in E1. That procedure is then executed with the arguments of 10 and 'user; this occurs in E11. It is in this procedure that we finally encounter the line we are searching for, the call to for-each-except.

In environment E11, the value of setter is 'user, the value of inform-about-value is the global procedure of that name (shown in the upper right), and the value of constraints is from frame E1, and it turns out to be just an empty list. Since forget-each-except is itself a procedure defined in the global environment, the procedure will be evaluated in a new frame, the environment is E4.

This demonstrates how relatively complex the environment situation can get, even with just a few apparently simple statements. Realistically, these statements are merely concise, not ‘simple’, as the call to make-connector sets up several procedures in a new environment, and anything that then makes use of the system (as the call to set-value! does) will then initiate more procedure calls and possibly the extension of that environment.

Ex. 3.37

There is very little difference between the implementations of each one of these expression-oriented versions of the constraint blocks. The c+ adder provides the template: create a connector, wire up an internal block with that connector on the desired result, and then return the connector. We can use the constraints system and correctly mapped inputs to use an adder to create a subtraction, and a multiplier to create a division result, in much the same way that the averager was built.

We find that since the tests for the temperature converter only made use of the external connection, and verified those values, that we do not need to change them at all, even though the internals of the converter block are entirely different.

Solutions 3.1.3.