Automatic Machines

Read time: 55 minutes (13842 words)

If you step back and review what we have accomplished so far, you might get concerned that building the entire machine, which will certainly take more than two components and a single wire to complete, is going to get tedious pretty fast.

That is very true!

Scripting the Machine

We can solve this problem if we turn the machine building process, currently contained in our build_circuit method in the Machine class, into something driven by a data file.

Here is what I have in mind:

machine.hdl
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
PARTS
    c1 : Component;
    c2 : Component
END

CONNECTIONS
    c1.out -> c2.in
END


That hdl extension stands for hardware description language.

Hardware Description Languages

In the “old days”, systems designers connected physical components together with physical wires, powered everything up and probed the system with oscilloscopes to see what was happening. This was a very difficult process, and consumed many man-hours of effort.

In a drive to streamline the process, designers came up with the idea of developing specialized languages that would let them do the same thing, only now using software simulation techniques to test their system. Later, they enhanced this idea to add the ability to actually manufacture a physical system from what is now a formal text file that specifies the system to build.

Wow! Computer design has now become a software process.

We do not have time to explore this idea fully. Doing so would force us to learn yet another language, and there are several really nice ones around. Instead, we will dedicate a short lecture to showing you how to process that simple file above, and add a way to custom craft our machine from a simple text file specification.

Little Languages

The technique we will use is commonly referred to as processing “little languages”. This term popped up when developers found it handy to create a specialized language for some part of their application, and then use common compiling techniques to process their new languages. This processing might be done before the application is compiled, meaning the “little languages” were used to generate application code that would end up being compiled. Or, the “little languages” could be run at run time, allowing real-time changes to how the program runs.

We will use that later approach. Our simulator will start up, read the machine specification from a text file, assemble the parts needed to create that machine, then run the resulting system. This sounds pretty cool!

Compiling 101

We need a brief introduction into how a compiler works to understand the code we will use for this trick.

Lexing

Basically, any program file is just a long stream of characters in one text file stored somewhere on the system. The first thing we need to do is open up that file and break that stream of characters into chunks that are more meaningful. Every language has rules for forming these chunks. There are reserved words, punctuation marks, and user defined names, for example, that have to be identified. Essentially we break the character stream into a stream of identifiable chinks we call tokens.

The process we use to identify these chunks is called lexical Analysis.

You can envision this process as one where we identify the words and punctuation marks in an English language document.

Parsing

Once we can deliver a stream of tokens, we examine the sequence of tokens to see if they follow defined rules for a specific series of tokens. This is called parsing, and the rules we follow are those defined for a specific language. In our English example, we are trying to identify sentences, only as programmers, we usually call these statements. The rules say what token are required, and in what order they should appear.

We call this pass syntax analysis.

Semantic Analysis

In a real compiler, a complex data structure, called a parse tree would be generated during parsing. The last pass uses that parse tree to generate code for the target machine. That involves setting up patterns of machine instructions what cause each sentence to operate inside of the machine the way the programmer expects. The final product of this phase is something that could end up running on a real machine.

Since we are assigning meaning to each language construct, we call this semantic analysys.

Our Compiler

In our simple language, we will not translate anything into instructions for a physical machine. Instead, we will figure out that parts are needed, and how to connect them. The example definition above should build exactly the same machine as we have set up in previous examples, only now, we can modify the file and build a different machine!

Cool!

Scene: Coffee shop

Ada: Hey Alan, how did oyu learn about compilers, and how they work?

Alan: A famous book by Niklaus Wirth, who invented the Pascal Compiler, laid out the entire process, code and all, on one short chapter. The book was called “Algorithms + Data Structures = Programs” [Wir76]. I still have a copy of that somewhere!

Nick: Pascal was pretty popular back in the 1980s, I heard.

Alan: It was taught in many schools, but C and C++ kind of killed it off.

Ada: Wirth was pretty well respected back then. He invented several languages.

Alan: Yep, but in the end C++ won out.

In fact, folks still recreate the simple compiler described by Wirth in beginning compiler classes. Check out PL0 on Google, of GitHub to see examples.

Since our language is so simple, we do not need a complex system to process it. In fact, we will not include error checking in the code presented. It could, and should, be included if we were to make a more serious version of this. For now, we just want to get out machine constructed.

Lexical Analysis

Fortunately, C++ will help out here. We can use the standard “>>” operator to read “strings” from the input file. That operator will load one space separated chunk of text into a variable we call token. All we need to do to check out tokens is make sure we see the reserved words at the right time, and load our system definitions in a simple loop.

Parsing

The language is just two parts for now. One part, starting with a reserved word: COMPONENTS, is just a list of component names, one name per line. We need to create a new component for each name we see and record that name using the constructor. The initial value for all components is zero for now.

The list of components ends when we see the END token. Following that, we see a list of CONNETIONS. Here, we do not name the wires we will create. W identify the input and output components, and use that information to make the required connection. Again, this section ends with an END token.

I said it was a simple language.

If you look at the code, we are allowed to have repeated sections defining components and connections. The only restriction is that we cannot make a connection unless the components on both sides of he wire already exist.

In this system, we collect all components and all wires in an array of objects. We fix the size of that array at compile time, something we should avoid doing in real life. You never know how many the user might require, so a better design would figure that out and allocate memory for the needed array at runtime We will see an example of that as we set up a memory component later.

Before we can add this feature to our simulator, we need to get rid of those statically defined components. We will do that in our next step:

Step06: Adding Control Logic

At this point in our development, we see that the main function is building the system we are simulating, then making it run. It would be much better to move that logic out of main, which really ought to be more focused on the user of this code. Since we still need a place to set up our system, let’s introduce a new class, this one called Machine.

To see this new idea, here is the modified main.cpp file

main.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include "Machine.h"

Machine m;

int main( int argc, char *argv[] ) {
    std::cout << "cycsi v(0.6.0)" << std::endl;
    std::cout << "running ..." << std::endl;

    // construct the machine
    m.build();

    // make data move
    m.run();

    std::cout << "done!" << std::endl;
}

This is much cleaner. All of the setup logic is now gone from main. All main needs to do is create a Machine object, initialize that object (by building the system), and then direct that object to run!

Of course, we need to look at the new Machine class definition:

Machine.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#pragma once
#include "Component.h"
#include "Wire.h"

class Machine {
    public:
        Machine( void );
        void build( void );
        void run( void );
        friend class wire;
    private:
        // parts needed
        Component *c1;
        Component *c2;
        Wire *c1_c2;
};

There is something new in here. Instead of creating our component and wire objects statically, by simply declaring them in the code, I am building everything dynamically, at run time. We store the address of these new objects in a pointer variable. That change means I no longer can call methods using a simple dot notation. Instead, we need to use the -> notation, which simply means “follow this pointer to an object, and call a method you find there”.

Here is the implementation of the Machine class:

Machine.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#include "Machine.h"
#include "Component.h"
#include "Wire.h"

Machine::Machine( void ) {
}

void Machine::build( void ) {
    c1 = new Component("C1",5);
    c2 = new Component("C2", 0);
    c1_c2 = new Wire();
    c1_c2->attach_in(c1);
    c1_c2->attach_out(c2);
}

void Machine::run( void ) {
    c1_c2->tick();
}

Make sure you understand this new notation!

The new way of creating our components and wires means we need to alter the other files slightly:

Component.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
#pragma once
#include <string>
#include "Wire.h"

class Component {
    public:
        Component(std::string n, int val);
        friend class Wire;
    private:
        std::string name;
        int data;

        std::string get_name();
        int read(int val);
        int write( void );
};


Component.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include "Component.h"

Component::Component( std::string n, int val ) {
    data = val;
    name = n;
}

int Component::write( void ) {
    return data;
}

int Component::read( int val ) {
    return data = val;
}

std::string Component::get_name( void ) {
    return name;
}
Wire.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma once
#include <string>

class Component;

class Wire {
    public:
        Wire();
        void attach_in(Component *c_in);
        void attach_out(Component *c_out);
        void tick( void );
    private:
        int data;
        Component *in;
        Component *out;
        std::string source, dest;
        void read(void);
        void write( void );
};


Wire.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <string>
#include "Wire.h"
#include "Component.h"

// constructor
Wire::Wire( void ) {
    data = -1;
    in = NULL;
    out = NULL;
}

// Accessor
void Wire::read(void) {
    // fetch wire value from input side
    data = in->write();
    source = in->get_name();
}

void Wire::write( void ) {
    // deliver wire value to output side
    dest = out->get_name();
    out->write();
    std::cout << source << "-(" << 
        data << ")->" << dest << std::endl;
}

void Wire::attach_in(Component *c_in) {
    in = c_in;
}

void Wire::attach_out(Component *c_out) {
    out = c_out;
}

void Wire::tick( void ) {
    read();
    write();
}

Obviously, we need to test this version:

$ make
make[2]: Nothing to be done for `all'.

And run it:

$ make run
./cosc2325
cycsi v(0.6.0)
running ...
C1-(5)->C2
done!

Note

You should commit this version of the code now. Tag it as version v.0.6.0

Step07: Introducing Wires

It is time to set up the class that will model connections between our components. The Wire class will have no real purpose other than to facilitate the movement of data from register to register in our simulator. Wires, in general, have only one input source at a time. They may be read by many components. In real circuits, there is a limit on the number of components you can attach to a wire, but we will ignore that limitation.

For now, we will focus on a single input and a single output for the wire objects.

Wire Class

Wire objects will hold pointer variables to the input and output components. We will provide methods to make these connections, each providing the address of the associated component as a parameter.

We will let the wire objects respond to the clock ticks as well, which is not something normally done in simulators.

I am setting things up this way so we can watch our data moving over the wires from place to place. We will build two kinds of output displays, a simple console log of the actions taken, and a graphical system we can use to visualize what is going on, using a display similar to those found on oscilloscopes. The basic idea is simple:

  • The clock will “tick” and all components will perform actions as required.
  • The clock will tock” and all wires will transfer data from input registers to the output registers. We will add output to this action for our display.

Here is our new Wire class specification:

Wire.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma once
#include <string>

class Component;

class Wire {
    public:
        Wire();
        void attach_in(Component *c_in);
        void attach_out(Component *c_out);
        void tick( void );
    private:
        int data;
        Component *in;
        Component *out;
        std::string source, dest;
        void read(void);
        void write( void );
};


Notice that we provide attributes that will store the names of the attached components. This data will be used for our display.

And the required implementation:

Wire.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <iostream>
#include <string>
#include "Wire.h"
#include "Component.h"

// constructor
Wire::Wire( void ) {
    data = -1;
    in = NULL;
    out = NULL;
}

// Accessor
void Wire::read(void) {
    // fetch wire value from input side
    data = in->write();
    source = in->get_name();
}

void Wire::write( void ) {
    // deliver wire value to output side
    dest = out->get_name();
    out->write();
    std::cout << source << "-(" << 
        data << ")->" << dest << std::endl;
}

void Wire::attach_in(Component *c_in) {
    in = c_in;
}

void Wire::attach_out(Component *c_out) {
    out = c_out;
}

void Wire::tick( void ) {
    read();
    write();
}

The read and write methods now include code that will complete a single line of output. The display is intended to look like Register Transfer Language notation, augmented witht he actual data value (as an unsigned number) being moved.

In this simulation, we are only moving simple integer numbers over our “wires”.

Component Class

There are no changes in the ``Component `` class.

Machine Class

The machine class has one new function. It will start the log output. For this example, we only display console messages. The run method has the needed code.

The class specification file is unchanged

The implementation adds output in the run method. This code starts a line of output by displaying a clock “tick” number. The run method is not set up to run for several cycles. Since our simulator is not doing any real work for now, the output will be a set of repeated lines.

Machine.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include "Machine.h"
#include "Component.h"
#include "Wire.h"

Machine::Machine( void ) {
}

void Machine::build( void ) {
    c1 = new Component("C1",5);
    c2 = new Component("C2", 0);
    c1_c2 = new Wire();
    c1_c2->attach_in(c1);
    c1_c2->attach_out(c2);
}

void Machine::run( void ) {
    int max_ticks = 10;
    for( int time = 0; time < max_ticks; time++ ) {
        std::cout << "t" << time << ": ";
        c1_c2->tick();
    }
}

Main Function

The main function remains unchanged, except for the version number:

main.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
#include <iostream>
#include "Machine.h"

Machine m;

int main( int argc, char *argv[] ) {
    std::cout << "cycsi v(0.7.0)" << std::endl;
    std::cout << "running ..." << std::endl;

    // build the machine
    m.build();

    // make the data move
    m.run();

    std::cout << "done!" << std::endl;
}

Let’s check out this version:

$ make
make[2]: Nothing to be done for `all'.

And run it:

$ make run
./cosc2325
cycsi v(0.7.0)
running ...
t0: C1-(5)->C2
t1: C1-(5)->C2
t2: C1-(5)->C2
t3: C1-(5)->C2
t4: C1-(5)->C2
t5: C1-(5)->C2
t6: C1-(5)->C2
t7: C1-(5)->C2
t8: C1-(5)->C2
t9: C1-(5)->C2
done!

Note

You should commit this version of the code now. Tag it as version v.0.7.0

Step08: We Need More Parts

Obviously, we cannot get very far if we only have two components and a single wire. We need to generalize this code so we cna construct more complex systems. The change is fairly simple, we will create n array of components and another array of wires.

The Machine class is where these changes need to occur:

Component.h
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
#pragma once
#include "Component.h"
#include "Wire.h"

class Machine {
    public:
        Machine( void );
        void build( void );
        void run( void );
        friend class wire;
    private:
        std::string machine_def;
        // parts needed
        Component *parts[10];
        Wire *wires[10];
        int part_count;
        int wire_count;

        Component *find_part( std::string name );
};

We have added attributes to track the number of components and wires allocated in our system.

There is a new method here as well. We will need a way to locate a component by name, so we we provide a simple search method that can do that job.

Here is the new implementation logic.

Machine.cpp
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
#include <iostream>
#include <fstream>
#include "Machine.h"
#include "Component.h"
#include "Wire.h"

Machine::Machine( void ) {
    machine_def = "machine.hdl";
}

Component *Machine::find_part( std::string name ) {
        for( int i=0; i<part_count; i++ ) {
                    if( parts[i]->get_name() == name ) return parts[i];
                        }
            return NULL;
}

void Machine::build( void ) {
    std::fstream fin;
    std::string token, in_token, out_token;

    fin.open(machine_def);
    if(!fin) {
        std::cout << "no machine def found. Aborting..." << std::endl;
        exit(EXIT_FAILURE);
    }
    while( fin >> token)  {
        // load all component parts
        if( token == "PARTS" ) {
            std::cout << "begin part definitions" << std::endl;
            fin >> token;   // component name
            while( token != "END" ) {
                parts[part_count++] = new Component( token, 0 );
                std::cout << "\t" << token << std::endl;
                fin >> token;   // colon
                fin >> token; // type
                fin >> token; // next symbol
            }
            std::cout << "end part definitions" << std::endl;
        } else if( token == "CONNECTIONS" ) {
            // wire up all connections with wires
            std::cout << "begin connection definitions" << std::endl;
            fin >> token;
            while( token != "END" ) {
                in_token = token.substr(0,token.find("."));
                wires[wire_count] = new Wire();
                std::cout << "\t" << in_token;
                fin >> token;   // "->" symbol
                fin >> token; // type
                out_token = token.substr(0,token.find("."));
                std::cout << "->";
                // create this connection
                std::cout << out_token << std::endl;
                wires[wire_count]->attach_in(find_part( in_token ));
                wires[wire_count]->attach_out(find_part( out_token ));
                wire_count++;
                fin >> token; // next symbol
            }
            std::cout << "end connection definitions" << std::endl;
        } else {
            std::cout <<  "\t" <<
                token <<
                std::endl;
        }
    }
    std::cout << "Machine constructed using:" << std::endl;
    std::cout << "\t" << part_count << " components" << std::endl;
    std::cout << "\t" << wire_count << " wires" << std::endl;
}

void Machine::run( void ) {
    int max_ticks = 10;
    for( int time = 0; time < max_ticks; time++ ) {
        for(int w = 0; w < wire_count; w++ ) {
            std::cout << "t" << time << ": ";
            wires[w]->tick();
        }
    }
}

There is a lot of new code here. Most of the additions are in the build method.

Building the Machine

While we could simply code in the machine we want, that is not very user friendly. It would be better if we provide a way for the user to decide what this machine should look like.

As a start on this idea, I am providing a simple definition file that details the machine we want to build:

machine.hdl
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
PARTS
    c1 : Component;
    c2 : Component
END

CONNECTIONS
    c1.out -> c2.in
END


Note

That hdl extension stands for Hardware Description Language.

It is quite common in the electronics world to set up circuit simulations from a data file that defines all the parts in the circuit and the connections needed to wire everything up. We are borrowing that idea here, and will simply create the same machine we have been using all along in this example development.

In order to process this file, we need to build some code that will read the data file, and figure out what to create.

The file structure is very simple, so we can read it using simple C++ file input stream code.

We collect space separated chunks of input text into a string variable named token. We check that the required markers are found by simple pattern matching the strings we collect from the data file.

If you look closely, you can set up the definition file using multiple “PARTS” and “CONNECTIONS” sections, in any order. (Be kind to the user!) The only restriction is that the parts to be connected to a wire must be defined before the connection is made.

Most of this logic should be pretty easy to follow. We are using standard C++ string methods to break up those “tokens” as needed to figure out how we are to wire things together. The search routine locates a defined component in the array by name, so we can pass the address of the components to the wire connection methods.

The only other change in this version is the version number in main.

Let’s make sure this version builds our machine correctly:

$ make
make[2]: Nothing to be done for `all'.

And run it:

$ make run
./cosc2325 cycsi.hdl
ex1: exchanging data
running ...
begin part definitions
	c1
	c2
end part definitions
begin connection definitions
	c1->c2
end connection definitions
Machine constructed using:
	2 components
	1 wires
t0: c1-(0)->c2
t1: c1-(0)->c2
t2: c1-(0)->c2
t3: c1-(0)->c2
t4: c1-(0)->c2
t5: c1-(0)->c2
t6: c1-(0)->c2
t7: c1-(0)->c2
t8: c1-(0)->c2
t9: c1-(0)->c2
done!

Note

You should commit this version of the code now. Tag it as version v.0.8.0.

This completes Lab4. Make sure everything runs correctly, and that all needed tags are in place. It would be wise to explore your code on GitHub to make sure.