Go implementation started!

I started working the on Go implementation this week.

So far it's going very well. Go is a terrific language that is very well designed. It has all the robustness of a typed and compiled language, and also a lot of the stuff I like about Perl (closures, lists, a GC, ...)

I'm about half done, I currently coding up the instructions.

When I'm done, I'm hoping I can run the CPU in a Cloud Function and invoke it remotely, sending instructions over the Internet and getting the result back!

About performance

As I move forward into a higher-level language implementation, 2 things immediately become evident:

1. My Perl implementation of the CPU is atrociously slow...
2. You really can't do much with 256 bytes of RAM...

So I decided to leave Perl aside for the time being and attempt an implementation of the Scott CPU in Go. So far the performance aspects look positive. On my laptop:

• 10M function calls in Perl: 900ms
• 10M function calls in Go: 15ms  

Moving to Go should definitely help with performance, and I also have made another decision: the Go implementation will have an architecture with a configurable number of bits.  All the different parts (Byte, Enabler, Register, Bus, ...) will be able to support a global configuration of 8 bits of more. 

Ideally, I will be able to select the number of bits that will give me enough RAM for what I want to do, along with am acceptable performance. 

I don't plan to increase the instruction set of the computer to more than 8 bits, but all the transport and part will be adapted to allow the use of more RAM.

Time to write some programs!

With the CPU implementation completed, it's now time to write some programs. For starters we will take a simple program:

r = 20 + 22
print r

Using the Scott CPU and the differents levels of languages I've implemented, we can achieve this in several ways:

Level 1: Machine Code

So the low-level machine instructions to do this operation are as such:

00100000
00010100
00100001
00010110
10000001
00100000
00000001
01111100
01111001
01100001

When fed into the Scott CPU, these instructions will add 20 and 22, select the I/O device 1, which is the equivalent of a teletype, and send the resulting value, 42, to it. The "teletype" will then print the character equivalent to ASCII(42), which is "*".

Coding in machine language is tedious, but since the instruction set can be implemented as a little assembly language, we'll use that instead.

Level 2: Assembly

The "language" described in the book is as such:

ADD   RA, RB
SHR   RA, RB
SHL   RA, RB
NOT   RA, RB
AND   RA, RB
OR    RA, AB
XOR   RA, RB
CMP   RA, RB
LD    RA, RB
ST    RA, RB
DATA  RB, data
JMPR  RB
JMP   addr
JCAEZ addr
CLF
IN    data, RB
IN    addr, RB
OUT   data, RB
OUT   addr, RB

To facilitate coding with it, and to avoid writing a parser, I implemented a small DSL directly in Perl. So the sample program above can now be written like this:

DATA R0, 20 ;
DATA R1, 22 ;
ADD  R0, R1 ;
REM "Activate the TTY device" ;
DATA R0, DEVICES::TTY() ;
OUTA R0 ;
OUTD R1 ;
GOTO "stop" ;
LABEL "stop" ;
HALT ; 

My instruction set is the same as in the book, but I added few things in the assembly language:

• A HALT instruction, that stop the machine, or else it just keeps incrementing the IAR forever and running whatever is in RAM. I did this by using a sub-case of the CLF instruction, 01100001, which is detected by the computer and stops it.
• A LABEL instruction, which identifies a specific instruction
• A GOTO instruction, which allows one to jump to a named location (a LABEL) instead of having to calculate manually where that place is

That's better, but we can go a step further and implement a high level language.

Level 3: High-Level Language

Writing assembly is a lot better than writing machine code, but it's still pretty tedious. The next step is to write in a high-level language.

My high-level language, also implemented as a DSL in Perl, has the following features so far:

• Variables. You can create variables, assign values to them and copy values between them. In the high-level language you can no longer access the registers, you use variables. Variables live in RAM. In order to coexist with the actual program instructions that are also in RAM, variables are allocated starting from the end of RAM going backwards. If ever the instructions meet the variables, you have run out of RAM and an error is thrown.
• The PRINT($var) function, which prints (the character corresponding to the ASCII code of) the  value of the variable.

With these simple features, the small program from before now becomes:

my $a = VAR(20) ;
my $b = VAR(22) ;
my $c = PLUS($a, $b) ;
PRINT($c) ;

Now it's getting interesting, but there are more features to come... 

Ta Daa!

After a couple of evenings of heavy coding, I have completed implementing the bulk of the Scott CPU!

All the instructions are implemented, except for the IO instruction. I have automated tests for all of them, and so far everything seems to hold up pretty well:

My goal is to now code the peripheral support for the keyboard, display and boot phase. Then I'll be good to write some actual programs!

Next will be to write a simple assembler, and probably a DSL in Perl to make it easier to use the computer. 

Around Instructions...

After a (another) Clock and Stepper overhaul, I finally think I've got the implementation down pat. I have over 550 unit tests for the clock and stepper alone, so I think I've got everything covered.

Over the course of the weekend, I worked on 3 things:

• The concept of Breadboard
• Getting the framework ready for processing instructions
• Getting the framework ready for implementing instructions

Breadboard

With all these components imlpemented, I needed a way to instantiate them all and have them readily available for interconnecting them. 

I'm not a electronics buff, but I found out that a device used to connect components together to create a circuit is called a breadboard. I created a Breadboard object in my project that comes pre-loaded with all the parts that make up the bulk of the computer:

• System Bus and all registers (seen so far)
• ALU and RAM
• All necessarry wires to connect everything together properly

Instruction Processing

Instruction Processing basically involves creating the circuit for steps 1 through 3, which involves loading the current instruction (refered to by IAR) from RAM to IR and incrementing IAR. Here we add to the Breadboard:

• IAR and IR
• Circuitry decribed on page 110 of the book

Instruction Implementation

Instruction Implementation means setting up all the necessary scaffolding that will enable creating circuits for specific instructions. That includes:

• RegA and RegB enable and set circuitry
• The "All Enables" and "All Sets" sides of the Control Unit
• The circuits to set and enable R0 through R3 (page 117)
• The Instruction Decoder circuit from page 122

Introducing "Elastic OR"

This setup is difficult to build in steps because all the OR gates for the Enable and Set sides of the Control Unit will have a certain number of wires connected to them, but we have not build those circuits yet...

In a real life situation, you would probably just leave those pind unconnected and they would send 0 to the gate. But in my case, the gates must have wires connected everywhere when they are created.

To accomodate for that, I have come up with something I called an "Elastic OR". An "Elastic OR" is really just a 6-pin OR that come pre-configured as such:

It basically has all "off" wires already attached, so by default it returns 0. When you attach something to an input, it effectively replaces the pre-attached wire with the new one, so the circuit now effectively returns the value of that one new wire. As you keep adding wires, the "Elastic OR" adapts to always return the correct value according to the number of connections.

This construct allows me to setup those OR gates in advance and have them working, even though not all the connections are in place yet.

With all this in place, we are ready to start wiring specific instructions!

Step by step...

With the Clock working, I started working the Stepper. Through this I realized that the Stepper is a tricky beast. Maybe not when it is physically constructed, but in my virtual implementation it required special attention.

The issues boils down to something I call "signal delivery order". When the power changes on a wire, it trickles down the circuit, propagating it's effect down the path. The way this works in my implementation goes something like this:

So the signal is delivered to each component in a specific order, namely the order in which they were connected to the wire.

In the Stepper, there are a bunch of Memory circuits, and 2 wires that toggle the 's' inputs for them. In my signal-delivering algorithm, sometimes a signal gets delivered to the 'i' input before the one destined to the 's' input, and that causes the wrong value to output by 'o'.

In most cases the delivery order doesn't seem to be important, but in the Stepper it turns out it really is. I had to work around this by cheating a bit and forcing these specific signals to be delivered first.

In the end I have a functional Stepper, which can be hooked to a Clock. I also created a Harness, which is like a minimalist motherboard that has all the components of the computer, except for the Instruction circuits, which are not yet implemented. Here is an example of how it is used, using the "Something Useful Revisited" example from the book, pages 103-106:

This will output the (admittedly not so exciting) output:

I also contacted John Clark Scott, the author of "But How Do It Know?" with some questions about the CPU desigg. He was very gracious and answered my questions promptly. Thanks John!