# Introduction

## State, evolving the state

After Round 3: Combinational logic we now have a fair bit of insight into
combinational logic and what it can do. Yet, combinational logic
appears fairly restrictive. We can design our circuits to be
*configurable*, but this appears to be nowhere near the
level of versatility that one would expect from a *programmable*
computer. Something must be missing from the big picture.

Say, think about a simple pocket calculator (or the calculator app in your handheld device). Suppose you have a list of 100 numbers whose sum you need to compute. Using the calculator, you can add up the numbers by keying them into the calculator, one number at a time. The machine maintains the sum and evolves it as you key in the numbers.

What we appear to be missing is the ability to maintain
a *state*, and the ability to *evolve* that state.

Let us consider another, even more elementary example.

Let us think about a (binary) *counter* device that adds one to
a count every time you push a button:

Circuit-wise we of course know how to design an incrementer circuit in combinational logic (recall Round 3: Combinational logic), so it would appear like we should be in good shape to arrive at a counter device. So how do we do it?

## Feedback

If you think about it a little, to turn an incrementer into
a counter it suffices to *feed the output back to the input*.
That is, whenever the button is pushed, we set the values of the
input elements to equal the the values of the outputs.
The gates of the circuit will then stabilize to reflect the new values
of the inputs, and we get new values of the outputs. Until we press
the button again, and feedback occurs again, and so forth.
*The same combinational logic is used over and over again to evolve the state*.

This is the gist of *sequential logic*. We take a combinational
circuit and feed the values of some of its output gates back to
some of its input elements, whenever the *clock signal* triggers
the feedback.

Let us review this idea with a little more detail before turning to Scala programming again. Here is a more detailed view to a counter circuit with feedbacks from the outputs of the incrementer to the inputs:

Let us now think how this circuit operates *over time*.

In the context of sequential logic, time is measured in **clocks**.
That is, the time \(t=0,1,2,\ldots\) is equal to how many times the
clock signal has triggered since system start. At start, \(t=0\).

Here is an illustration how the circuit operates over time:

Observe that sequential logic is very simple indeed (compared with all the trouble we had to go to learn combinational logic!):

*When the clock triggers, the specified feedbacks happen*.

Nothing more, nothing less.

Now let us turn to Scala programming to start witnessing the power of sequential logic.

## Upgrade from `tinylog`

to `minilog`

Recall the `tinylog`

package from Round 3: Combinational logic?

A wonderful feature of encapsulation is that client code remains essentially oblivious to changes-in-implementation, assuming the interfaces to that implementation (that is, the classes and their methods visible to clients) remain mostly unchanged.

Our intent in this round is to witness such a change in implementation.
Namely, we will upgrade package `tinylog`

from Round 3: Combinational logic
to package `minilog`

in Round 4: Sequential logic, state and feedback.
This is to (a) get a more efficient circuit simulation,
and (b) extend the package with a feedback mechanism to enable us to build
sequential logic.

From a pedagogical perspective it is of course also important to show
that such changes in the underlying implementation are possible, and enabled
by careful design of the original interfaces. A further pedagogical motivation
is that we get to introduce the principle of *designing with patterns* by
reviewing the designs of both `tinylog`

and `minilog`

.

Before we proceed with the details of the upgrade to `minilog`

, however,
let us *play* with sequential logic.

## Our first design with sequential logic – the counter

Ambitious goals again have humble beginnings. Let us implement the counter circuit.

We start by recalling from Round 3: Combinational logic how to build an incrementer, in combinational logic.

```
import minilog.* // Note: in this round we use the package minilog
// instead of tinylog.
// Here is a builder for an incrementer
def buildHalfAdder(ai: Gate, c: Gate) = (ai && c, (!ai && c)||(ai && !c))
def buildIncrementer(aa: Bus) =
var c = aa.host.True // initial carry is true
val r = new Array[Gate](aa.length)
for i <- 0 until aa.length do
val (c_out,s) = buildHalfAdder(aa(i), c)
r(i) = s
c = c_out
end for
new Bus(r.toSeq)
end buildIncrementer
```

Now we are ready to implement the counter circuit.

```
val n = 4
val c = new Circuit() // a host object for our gates (new in minilog)
val ins = c.inputs(n) // have the host create a new bus of n input elements
val outs = buildIncrementer(ins) // build an incrementer
ins.buildFeedback(outs) // feed the outputs back to the inputs (new in minilog)
```

Observe the feedback statement `ins.buildFeedback(outs)`

.
This statement simply indicates that each input element in the bus `ins`

is to receive its value from the corresponding output in the bus `outs`

when the feedback (clock) is triggered.

Recall the `Toggler`

tool in `tinylog`

?
The `Toggler`

tool has been upgraded in `minilog`

into a tool
called `Trigger`

, which we will put to use right now:

```
val t = new Trigger(c) // trigger requires a host object
t.watch("ins", ins.reverse) // we can watch gates or buses in the host object
t.watch("outs", outs.reverse) // ... reversion shows least significant bit on the right
t.go() // opens up the graphical interface
```

Observe the central new feature of `Trigger`

, namely the
*trigger button* that triggers the clock (and feedback):

Now give a few clicks to the button, and watch the binary counter run!

## Our second design – the accumulator-adder

Let us now return to the example of taking the sum of a list of integers. Say, suppose we want to evaluate (in binary) the sum of

`00001011`

,`00101010`

,`00010101`

, and`01010111`

.

How would we design a machine to help us with this task?

We know how to build an adder circuit, so building sequential logic that accumulates a sum should be within the scope of our tools. Say, we feed the output of the adder back to its first input bus. This enables us to accumulate a sum, one summand at a time, by keying each summand in via the second input bus, and triggering the clock (feedback) to accumulate the sum.

Here is a builder for an adder (written in functional style):

```
def buildAdder(aa: Bus, bb: Bus) =
new Bus(
((aa zip bb).scanLeft((aa.host.False, aa.host.False))) {
case ((s,c),(a,b)) => (a+b+c,(a && b)||(a && c)||(b && c))
}.drop(1).map(_._1))
end buildAdder
```

So now we are ready to build the accumulator-adder:

```
val n = 8
val c = new Circuit()
val accum_in = c.inputs(n)
val user_in = c.inputs(n)
val accum_out = buildAdder(accum_in, user_in)
accum_in.buildFeedback(accum_out)
```

Let us witness this in `Trigger`

:

```
val t = new Trigger(c)
t.watch("accum_in", accum_in.reverse)
t.watch("user_in", user_in.reverse)
t.watch("accum_out", accum_out.reverse)
t.go()
```

Now, toggle “`user_in`

” to whatever value you want, and trigger feedback
to have it added to the accumulator!

The feedback from `accum_out`

to `accum_in`

now in effect acts
as \(n = 8\) bits of memory, which is used to store and accumulate the sum.

*The accumulator-adder can in fact be viewed as an extremely simple special-purpose processor design.*

The processor has only one *operation* it can perform, namely add the
contents of an 8-bit user input into an 8-bit *register*
(or, the accumulator).

## Our third design – the accumulator-adder-subtracter

Our third design already includes configurable functionality. Namely, the machine can either add or subtract the user input from the accumulator, depending on what the user selects.

Here is a builder for a subtracter:

```
def buildSubtracter(aa: Bus, bb: Bus) =
new Bus(
((aa zip bb).scanLeft((aa.host.False, aa.host.True))) {
case ((s,c),(a,b)) => (!(a+b+c),(a && !b)||(a && c)||(!b && c))
}.drop(1).map(_._1))
end buildSubtracter
```

So now we can build the accumulator-adder-subtracter:

```
val n = 8
val c = new Circuit()
val accum_in = c.inputs(n)
val user_in = c.inputs(n)
val sel = c.input()
val res_add = buildAdder(accum_in, user_in)
val res_sub = buildSubtracter(accum_in, user_in)
val accum_out = (res_add && !sel) | (res_sub && sel)
accum_in.buildFeedback(accum_out)
```

Let us witness this in `Trigger`

:

```
val t = new Trigger(c)
t.watch("accum_in", accum_in.reverse)
t.watch("sel", sel)
t.watch("user_in", user_in.reverse)
t.watch("accum_out", accum_out.reverse)
t.go()
```

After a little bit of play, let us now pause and reflect.
Sequential logic has suddenly made our tools more powerful. We can
now maintain a state inside a circuit, and evolve it according to
combinational logic that can be *configured* (for example, either to add
or to subtract) by toggling input.

## Towards understanding the computer

Let us think about our quest to understand the computer. It appears
we have come a fair way now, but yet the notion of *programmability*
(e.g. a console that executes our commands) appears more powerful
than *configurability*. For example, we can now add integers
by keying them into input elements of sequential logic and then
triggering the clock.

But how do we instruct the machine to, say, take the sum of the first 100 million positive integers and then report back to us? It still appears that we do not have the full picture. Yet we are not far from our goal.

## Building an instructable data path – a roadmap for this round

Our objective in this round is to familiarize ourselves with sequential logic and continue towards our objective of understanding the computer. In fact, during this round we will cover most of the way to a fully functional, programmable processor architecture.

Yet again our strategy is to proceed from the bottom up.
We start by upgrading our circuit-building and -simulation
tools to sequential logic. In the process we will introduce
the principle of *designing with patterns* to structure our
programs in Sequential logic in Scala (*)

Once we have package `minilog`

ready, we have all the tools
required to fully and finally resolve the mystery of the
programmable computer. In essence, *it is all just sequential logic*.

To back this claim, our goal in the next two rounds is
to deploy sequential logic to build the `armlet`

, in many respects
a substantially simplified but yet fully programmable processor
architecture loosely inspired by the ARM architecture.

Note

Most modern mobile devices and embedded systems have long used processors based on the ARM architecture. In fact, it is likely that you currently have an ARM processor running in your pocket or purse.

In recent years even personal computers based on the ARM architecture have become more common. For example, in 2020 Apple introduced products in their Air Pro, and Mini lines built around their M1 system.

Our objective in this round to build the *data path* of the `armlet`

.
That is, the part of the processor that maintains and manipulates
the data in our computations, one step (clock tick) at a time.
The two key components of the data path are the *arithmetic logic unit*
(that implements the arithmetic and logic operations in our computations)
and the *memory interface unit* (that loads and stores words of data
from a *memory unit* outside the processor). The armlet data path

Furthermore, our goal is to be able to *instruct* the data path.
That is, we want our design to be such that we can configure what
the data path does at any given step by means of an *instruction*,
that is, one word of control input to combinational logic. The armlet instruction set

Yet again what is above may sound like a formidable objective, but
in fact we have essentially all the tools ready. The `armlet`

data path is in essence nothing but a somewhat more intricate
accumulator-adder (recall our design above): a combinational logic
circuit with simple feedbacks from selected outputs to inputs.

In the exercises we will practice sequential logic design ranging from simple oscillators to the design of a pipelined multiplier unit.

In the next round, we extend the single-step functionality of the data path with an execution-and-control unit to obtain a fully programmable Von Neumann architecture, which we then proceed to program. Finally, we take a look at Scala itself and the progression from a Scala program to execution on actual physical hardware.