6.2.1 Implementing logic

To implement logic using a machine, we need physical ways of representing the two possible values. We use a full bottle of wine to represent true and an empty bottle of wine to represent false. If the value of an input is true, we pour a bottle of wine in the input nozzle; for false inputs we do nothing. Similarly, electronic computers typically use presence of voltage to represent true, and absence of voltage to represent false.

And. A logical and function takes two inputs and produces one output. The output is true if both of the inputs are true; otherwise the output is false. We define a logical-and procedure using an if expression:1

(define (logical-and a b) (if a b false))

To design a mechanical implementation of the logical and function, we want a simpler definition that does not involve implementing something as complex as an if expression.

A different way to define a function is by using a table to show the corresponding output value for each possible pair of input values. This approach is limited to functions with a small number of possible inputs; we could not define addition on integers this way, since there are infinitely many possible different numbers that could be used as inputs. For functions in Boolean logic, there are only two possible values for each input (true and false) so it is feasible to list the outputs for all possible inputs.

We call a table defining a Boolean function a truth table. If there is one input, the table needs two entries, showing the output value for each possible input. When there are two inputs, the table needs four entries, showing the output value for all possible combinations of the input values. The truth table for the logical and function is:

A B (and A B)
false false false
true false false
false true false
true true true

We design a machine that implements the function described by the truth table: if both inputs are true (represented by full bottles of wine in our machine), the output should be true; if either input is false, the output should be false (an empty bottle). One way to do this is shown in Figure 6.1. Both inputs pour into a basin. The output nozzle is placed at a height corresponding to one bottle of wine in the collection basin, so the output bottle will fill (representing true), only if both inputs are true.

Figure 6.1: Computing and with wine.

The design in Figure 6.1 would probably not work very well in practice. Some of the wine is likely to spill, so even when both inputs are true the output might not be a full bottle of wine. What should a $\frac{3}{4}$ full bottle of wine represent? What about a bottle that is half full?

The solution is the digital abstraction. Although there are many different quantities of wine that could be in a bottle, regardless of the actual quantity the value is interpreted as only one of two possible values: true or false. If the bottle has more than a given threshold, say half full, it represents true; otherwise, it represents false. This means an infinitely large set of possible values are abstracted as meaning true, so it doesn’t matter which of the values above half full it is.

The digital abstraction provides a transition between the continuous world of physical things and the logical world of discrete values. It is much easier to design computing systems around discrete values than around continuous values; by mapping a range of possible continuous values to just two discrete values, we give up a lot of information but gain in simplicity and reliability. Nearly all computing machines today operate on discrete values using the digital abstraction.

Or. The logical or function takes two inputs, and outputs true if any of the inputs are true:2

A B (or A B)
false false false
true false true
false true true
true true true

Try to invent your own design for a machine that computes the or function before looking at one solution in Figure 6.2.1.

Implementing not. The output of the not function is the opposite of the value of its input:

A (not A)
false true
true false

It is not possible to produce a logical not without some other source of wine; it needs to create wine (to represent true) when there is none input (representing false). To implement the not function, we need the notion of a source current and a clock. The source current injects a bottle of wine on each clock tick. The clock ticks periodically, on each operation. The inputs need to be set up before the clock tick. When the clock ticks, a bottle of wine is sent through the source current, and the output is produced. Figure 6.2 shows one way to implement the not function.

Figure 6.2: Computing logical or and not with wine

(a) Computing not with wine.

(a) The or machine is similar to the and machine in design, except we move the output nozzle to the bottom of the basin, so if either input is true, the output is true; when both inputs are true, some wine is spilled but the logical result is still true.

(b) Computing or with wine.

(b) The not machine uses a clock. Before the clock tick, the input is set. If the input is true, the float is lifted, blocking the source opening; if the input i false, the float rests on the bottom of the basin. When the clock ticks, the source wine is injected. If the float is up (because of the true input), the opening is blocked, and the output is empty (false). If the float is down (because of the false input), the opening is open, the source wine will pour across the float, filling the output (representing true). (This design assumes wine coming from the source does not leak under the float, which might be hard to build in a real system.)

  1. Scheme provides a special form and that performs the same function as the logical and function. It is a special form, though, since the second input expression is not evaluated unless the first input expression evaluates to true

  2. Scheme provides a special form or that implements the logical or function, similarly to the and special form. If the first input evaluates to true, the second input is not evaluated and the value of the or expression is true