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)
end Gate

object Gate:
  val False: Gate = new ConstantGate(false)
  val True: Gate  = new ConstantGate(true)
  def input(): Gate = new InputElement()
end Gate

class InputElement() extends Gate():
  var v = false                     // default value is false
  def set(s: Boolean) { v = s }
  def value = v
end InputElement

class NotGate(in: Gate) extends Gate():
  def value = !in.value
end NotGate

class OrGate(in1: Gate, in2: Gate) extends Gate():
  def value = in1.value || in2.value
end OrGate

class AndGate(in1: Gate, in2: Gate) extends Gate():
  def value = in1.value && in2.value
end AndGate

class ConstantGate(v: Boolean) extends Gate():
  def value = v
end ConstantGate

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 classes InputElement, NotGate, AndGate, OrGate, and ConstantGate) 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 method input() that builds input gates) and static objects (such as the two constant gates True and False).

  • Set and get methods. The class InputElement implements 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 (method value) 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: Programming abstractions and analysis, 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: Combinational logic 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 a few 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 buildFeedbackFrom(g: Gate) =
     feedback_from = g
  end buildFeedbackFrom
  def feedbackValue = feedback_from.value
end Gate

So what pattern is this? You should in fact know this one, based on our review of tinylog above. The method buildFeedbackFrom 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 buildFeedbackFrom(that: Bus) = (this zip that).foreach((b1,b2) => b1.buildFeedbackFrom(b2))

end Bus

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
  end registerInput

  // [...]

end Circuit

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

  // [...]

end Circuit

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

  // [...]

end InputElement

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((w,v) => w.set(v))

end Circuit

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
   end registerGate

   // [...]

end Circuit

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

  // [...]
end 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):

  // [...]

  // a convenience constructor
  def this(inputs: Gate*) =
    // invoke the main constructor -- gate has the same host as the first input
    this(inputs.head.host)
    // fail unless all inputs have the same host
    require(inputs.tail.forall(_.host == inputs.head.host))
  end this

  // [...]
end Gate

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):

  // [...]
end NotGate

class OrGate(in1: Gate, in2: Gate) extends Gate(in1, in2):

  // [...]
end OrGate

class AndGate(in1: Gate, in2: Gate) extends Gate(in1, in2):

  // [...]
end AndGate

// [...]

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:

  1. build new gates

  2. set values of input elements

  3. 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
  end registerGate

  // [...]
end Circuit

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
  end set

  // [...]
end InputElement

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 then
      host.clean()       // recompute all memos if dirty
    end if
    memo                 // my memorized value is up to date, so return it
  end value

  def eval: Boolean      // implemented in extending classes
  def clean() =
     memo = eval         // update memo, invoked by host
  end clean

  // [...]
}

class Circuit():
  // [...]

  def clean() =
    dirty = false            // clear dirty before eval, otherwise infinite loop
    gates.foreach(_.clean()) // update and memorize values at gates
  end clean

  // [...]
end Circuit

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
end InputElement

class NotGate(in: Gate) extends Gate(in):
  def eval = !in.value
end NotGate

class OrGate(in1: Gate, in2: Gate) extends Gate(in1, in2):
  def eval = in1.value || in2.value
end OrGate

class AndGate(in1: Gate, in2: Gate) extends Gate(in1, in2):
  def eval = in1.value && in2.value
end AndGate

// [...]

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: A programmable computer),

  • 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.