Sequential logic in Scala (*)
Designing with patterns (*)
The principle of designing with patterns amounts to being able
to identify common patterns in existing designs, and
to use the patterns in your own new designs.
The more experienced a programmer you are, the more patterns you know and can use to structure your own programs. It is a good idea to start practicing your pattern-spotting skills as soon as possible, and our intent is to help you in this quest by highlighting in our narrative the patterns that we use in our designs.
Spotting common patterns in package tinylog (*)
Our intent in this section is to upgrade package tinylog to a more
efficient design that also simulates sequential logic. In upgrading the design,
we will review the patterns that we use to build the new design. Towards this end,
it is convenient to start by recalling package tinylog and reviewing its design
from the perspective of patterns.
Recall that the basic gate classes in tinylog are as follows:
// tinylog -- a tiny Scala package for building combinational logic
package tinylog
abstract class Gate()
{
def value: Boolean // implemented by the extending classes
def unary_!: Gate = new NotGate(this)
def &&(that: Gate): Gate = new AndGate(this, that)
def ||(that: Gate): Gate = new OrGate(this, that)
}
object Gate {
val False: Gate = new ConstantGate(false)
val True: Gate = new ConstantGate(true)
def input(): Gate = new InputElement()
}
class InputElement() extends Gate()
{
var v = false // default value is false
def set(s: Boolean) { v = s }
def value = v
}
class NotGate(in: Gate) extends Gate()
{
def value = !in.value
}
class OrGate(in1: Gate, in2: Gate) extends Gate()
{
def value = in1.value || in2.value
}
class AndGate(in1: Gate, in2: Gate) extends Gate()
{
def value = in1.value && in2.value
}
class ConstantGate(v: Boolean) extends Gate()
{
def value = v
}
When an experienced programmer looks at this design, the programmer immediately observes a number of general patterns that are used in the design:
Common abstract base class. A common abstract base class (such as class
Gate) is typically used to share common functionality and to define a common abstract interface by which the concrete extending classes (such as classesInputElement,NotGate,AndGate,OrGate, andConstantGate) can be accessed in client code. The extending concrete classes then implement this abstract interface according to their own structure.Companion object. The companion object to a class (such as
object Gate) is a typical place to accommodate static methods (such as a builder methods for objects in the class, such as methodinput()that builds input gates) and static objects (such as the two constant gatesTrueandFalse).Set and get methods. The class
InputElementimplements a pair of methods (the set method and the get method) that constitute an interface for accessing (setting and getting) its internal state (the value of the gate). In fact, the get method (methodvalue) is a shared interface to all the gate types. The purpose of these methods is to control access to the internal state of a gate, and hide the implementation of the state from client code. (The serendipity of such hiding will become apparent when we upgrade the design in what follows.)Recursion over structure. The interface for obtaining the value of a gate is implemented by recursively computing the values of the gates that supply input to a gate. The base cases of the recursion are the input elements and the constant gates, which always evaluate to their set values. Such recursion over structure is a general pattern that is typical to functional programming – we will study recursion over structure in detail in Module II, for now we are content to just identify the pattern.
Defined operators. In some cases it is useful to write program text in a syntactically more convenient way by using operator expressions rather than a complex sequence of method calls. Arithmetic expressions are perhaps the most natural example of the advantages of an operator syntax that is both easy to read and write, but we already witnessed in Round 3 that defining Boolean operators on gate-objects to enable easy building of circuits is just as natural and convenient.
Builders in an abstract base class. The defined operators in the abstract base class are also builder methods for objects in the extending classes. Such builders are useful in hiding the extending classes from client code and often make the client code more succinct by avoiding cumbersome “
new”-expressions to instantiate new objects.
All right. That was six patterns in one simple design with 45 lines of code.
Why tinylog needs upgrading (*)
While the tinylog design has many good features, it will not be efficient
enough to simulate the propagation of values in the large circuits that we intend
to build.
The main cause for this inefficiency is our choice to use recursion to
compute values of gates (recall Refresher: Objects, references, and recursion recalled),
which in general causes lots of redundant recomputation
of values with larger circuits. (In fact, a circuit with \(2n\) logic gates
can cause tinylog to make at least \(2^n\) gate evaluations.)
Thus, while recursion produces a compact design for simulating combinational
logic, it is lacking in efficiency.
A second reason why tinylog needs upgrading is that we need to
implement the functionality of sequential logic into the simulation.
That is, we must be able to assign a feedback to an input element
from any gate in the circuit, and we must implement the trigger
(“the clock”) for the feedback.
All in all, as a result we will end up rewriting essentially the entire implementation of the circuit simulation. Yet, the interface to client code will not change much, except to accommodate the new functionality of sequential logic.
Let us now proceed to upgrade tinylog, one aspect of the design at
a time. At each upgrade we indicate the pattern that we use in the design.
Building feedback to an input element (*)
Let us start with the easiest aspect of the new design, namely upgrading the design to sequential logic.
Recall that the gist of sequential logic is that we feed (some of) the input
elements with new values when the clock triggers. In terms of Scala, we obtain
these new values for InputElement-objects from Gate-objects that
we have designated as feedback gates when the circuit is built.
Let us insert into class InputElement the functionality to
record a feedback from any designated gate g, which defaults
to the input element itself:
class InputElement() extends Gate()
{
// [...] -- Note: this comment indicates that we have removed code from here
// to focus attention to the design change
var feedback_from: Gate = this // default feedback is from itself
def buildFeedback(g: Gate) { feedback_from = g }
def feedbackValue = feedback_from.value
}
So what pattern is this? You should in fact know this one, based on our
review of tinylog above. The method buildFeedback is a set method
that controls access to the internal state variable feedback_from.
The method feedbackValue is a get method that gets the value
from the gate that supplies feedback.
A similar set method inserted to class Bus enables us to build feedbacks
at bus level, from the gates of one bus to the gates of another bus:
class Bus(gates: Seq[Gate])
extends Seq[Gate]
with SeqLike[Gate,Bus]
{
// [...]
def buildFeedback(that: Bus) = (this zip that).foreach(x => x._1.buildFeedback(x._2))
}
Now we have in place the mechanism to record what gates feed their value back to what input elements when we build a circuit.
Implementing the clock signal functionality (*)
Next we implement the “clock signal” functionality that executes the feedback to the input elements from the assigned gates.
From a design perspective the key issue is how and where we track the input elements that the client code constructs. Indeed, once we can track the input elements, implementing the clock signal takes one method that assigns new values to the input elements. Of course, yet another design issue is where to place the clock method so that the client code may access it.
As with any design issue, there are multiple possiblities to resolve the issue, we simply have to make choices and see where our choices lead us in terms of convenience and efficiency.
To illustrate the possibilities, one way to implement the clock signal is
to use a companion object that contains a collection that keeps track
of all the constructed input elements, and implements a method clock()
that executes the feedback. This companion object could be the companion
object to class Gate. (Recall the “companion object” pattern above.)
Another possibility is to use a host object pattern. This pattern
registers all objects of interest (in our case, each InputElement)
with a host object as the objects are created. This registering
takes place automatically and is hidden from client code, but the host
object itself is typically visible to client code. In particular, the
host object typically has methods that enable manipulation of all the
hosted objects in client code (in our case, the method clock()).
Furthermore, the host object typically also acts as a factory that
the client code may request to manufacture the hosted objects.
The host object pattern itself may be implemented either with a static
object (which we could perhaps call Circuit), or with a class,
to enable instantiation of multiple host objects in client code.
Let us choose the latter approach and see where this leads us.
The hosting mechanism can be implemented by introducing a new class as follows:
import collection.immutable.Queue
class Circuit() {
// [...]
// A hosting mechanism for input elements
var ins = Queue[InputElement]() // all constructed inputs register themselves here ...
def registerInput(g: InputElement) { ins = ins :+ g } // ... using this method
// [...]
}
We also want Circuit-objects be able to manufacture input elements
(that register with their manufacturer):
class Circuit() {
// [...]
// Factory methods for input elements
def input() = new InputElement(this) // manufactures one input
def inputs(n: Int) = new Bus((1 to n).map(x => input())) // manufactures a bus of n inputs
// [...]
}
Now a circuit knows its inputs, assuming the inputs register with their host.
We thus need an upgrade to the design of class InputElement so that
every input element indeed registers with its host:
class InputElement(host: Circuit) extends Gate(host)
{
host.registerInput(this) // register the new input
// [...]
}
Observe how the constructor now requires the host circuit as parameter,
which we also forward to the constructor of class Gate (to enable further
registration, to be discussed in the next section). Inside the constructor,
the newly created input element registers itself with the host. Thus,
all inputs register with a host.
Now that all inputs register with their host, we can implement the “clock signal” for the inputs hosted by a circuit:
class Circuit {
// [...]
def clock() {
(inputs zip inputs.map(_.feedbackValue)).foreach({ case (w,v) => w.set(v) })
}
}
Let us review what the code above does. First, for each input element,
we read the value of the assigned feedback gate for that element
by inputs.map(_.feedbackValue). This produces a sequence of Boolean
values. This sequence is then zip-ped with the input elements
to produce a sequence of tuples (w,v) consisting of an input element
w and a Boolean value v. Finally, we process each tuple
(w,v) so that the value v is set to the input element w.
Remark. Let us step back for a moment and reflect what we just did.
We wanted to extend the design with “clock signal” functionality, and
in the process of making this extension we ended up introducing a host
object (class of host objects) into the design. The host object was
used to track the input elements constructed in client code, and
to accommodate the method clock().
Registering all gates with a host (*)
Now that we have introduced the host object to our design, it in fact makes sense to register not only the input elements, but all gates with the host object. In other words, every gate created in client code will be registered with a unique host object. This enables us to speed up the simulation (as we will soon see) and enables us to detect bad client code that attempts to mix gates with different hosts.
Let us insert a new hosting mechanism in the host object:
class Circuit() {
// [...]
// A hosting mechanism for all gates
var gates = Queue[Gate]() // all constructed gates register themselves here ...
def registerGate(g: InputElement) { gates = gates :+ g } // ... using this method
// [...]
}
Next we must reflect where to place the registration code in the gate classes. Since all constructed gates must be registered, it makes sense that registration happens in the constructor of the abstract base class:
abstract class Gate(val host: Circuit)
{
host.registerGate(this) // register the new gate
// [...]
}
In fact, it makes sense to introduce in the base class an extra constructor that accepts as parameters a list of input gates, and registers the current gate with the same host as these input gates have:
abstract class Gate(val host: Circuit)
{
// [...]
def this(inputs: Gate*) { // a convenience constructor
this(inputs.head.host)
// invoke the main constructor -- gate has the same host as the first input
require(inputs.tail.forall(_.host == inputs.head.host))
// fail unless all inputs have the same host
}
// [...]
}
Indeed, the constructors of the extending classes can now invoke the introduced convenience constructor to register with the same host as their inputs:
class NotGate(in: Gate) extends Gate(in)
{
// [...]
}
class OrGate(in1: Gate, in2: Gate) extends Gate(in1, in2)
{
// [...]
}
class AndGate(in1: Gate, in2: Gate) extends Gate(in1, in2)
{
// [...]
}
// [...]
Observe that we can view what we just did as yet another pattern. We used a convenience constructor in an abstract base class to simplify the implementation of gate registration in extending classes. Every gate created in client code will now automatically and transparently register with a host object.
Speeding up the simulation (*)
Let us now focus speeding up the simulation. Recall that our interface allows essentially three types of actions in client code:
build new gates
set values of input elements
get values of gates
Each gate now has a host object, so we can use the host object to track client actions.
To avoid redundant recursive calls when computing gate values
(recall that this was the reason why tinylog was not efficient enough
for our purposes!) we will use memoization to remember the value of a
gate object once we have computed it. In other words, we will not use
recursion to compute the value of a gate unless it is absolutely necessary
(because of client action) to recompute the value.
Recalling the possible client actions, we must be wary of clients setting values to the input elements, because these will force us to recompute memorized values to reflect the new input. We will implement this so that as soon as the value of one input changes (or when new gates are built), all previously memorized values for the logic gates become invalid (or dirty) and must be updated (or cleaned) when (and no sooner than) client code forces us to work. In effect, we are procrastinating (or being lazy) with the cleanup until we are forced to work. Procrastination is useful because a client may change several inputs in succession before requesting values of gates, so it would be redundant work to update the values after each update to an input.
Let us first implement the dirty/clean pattern. Perhaps the most convenient place to track the dirty status is within the host object:
class Circuit() {
// [...]
var dirty = false // must recompute the memorized values (if any)?
// [...]
def registerGate(g: Gate) {
// [...]
dirty = true // set dirty whenever a new gate is registered
}
// [...]
}
An input element will signal that the memorized values are dirty whenever its value is set:
class InputElement(host: Circuit) extends Gate(host)
{
// [...]
var v = false // default value is false
override def set(s: Boolean) {
v = s // whenever an input is set ...
host.dirty = true // ... flag the host dirty
}
// [...]
}
The design now catches all actions from client code that invalidate memorized values. Next we implement memorization. Here we have chosen a simple implementation that evaluates and memorizes the values of all gates in one pass, after which the values are immediately available until the circuit becomes dirty again. This mechanism is implemented in the abstract base class for gates and in the host object:
abstract class Gate(val host: Circuit)
{
// [...]
var memo = false // memorize my value in this var
def value = {
if(host.dirty) {
host.clean() // recompute all memos if dirty
}
memo // my memorized value is up to date, so return it
}
def eval: Boolean // implemented in extending classes
def clean() { memo = eval } // update memo, invoked by host
// [...]
}
class Circuit() {
// [...]
def clean() {
dirty = false // clear dirty before eval, otherwise infinite loop
gates.foreach(_.clean()) // update and memorize values at gates
}
// [...]
}
What remains are the new implementations of the extending classes.
These require us to implement only the method eval that takes care
of the gate-specific evaluation:
class InputElement(host: Circuit) extends Gate(host)
{
// [...]
def eval = v // return the set value
}
class NotGate(in: Gate) extends Gate(in)
{
def eval = !in.value
}
class OrGate(in1: Gate, in2: Gate) extends Gate(in1, in2)
{
def eval = in1.value || in2.value
}
class AndGate(in1: Gate, in2: Gate) extends Gate(in1, in2)
{
def eval = in1.value && in2.value
}
// [...]
Observe that the gate-specific evaluation functions invoke the
value-method of the input(s) to a gate (if any).
Because we evaluate the gates in the (queue) order they were
registered with the host object, each input to a gate already has its
value memorized when its value-method is invoked, and
hence the method immediately returns the memorized value.
In this way each gate is evaluated at most once after any changes
to the circuit or its input elements.
The art of designing with patterns (*)
We have now reviewed essentially the complete design and implementation
of package minilog, and we hope that the narrative recorded above
reflects the internal dialogue of an experienced programmer when thinking
about the “patterns” in a design.
Reviewing what we have done, perhaps what should be apparent at this point
is that the implementation of package minilog uses rather different
techniques compared with package tinylog, but
the external interface to client code is essentially the same and just as simple as with
tinylog– the main change in the interface is that we have the new functionality that implements sequential logic,the design is now efficient enough to run a complete (16-bit) processor simulation at several thousand simulated clock ticks per second on a basic laptop computer (as we will witness in Round 5),
the internal implementation relies on a few fairly simple patterns, whose careful combination yields the desired functionality.
What should also be apparent that “patterns”, as we have quickly reviewed them here, are more of an art rather than a systematic engineering principle. Sometimes a pattern is useful, sometimes it is not. Yet it is perhaps safe to say that every experienced programmer does at least some conscious pattern matching against prior experience when building up a new design. The study of code written by people with more experience is a great way to pick up useful patterns and new ways of getting things done. And of course, software design patterns have been documented in their own right, and browsing through such documented patterns may be a fruitful exercise when seeking inspiration for a new design.