Automatic Machines

Read time: 39 minutes (9899 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 what 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 our 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 our 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 Component class 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, the names we have been using can be derived from the names of the attached components on each end.

Since the token we are processing identifies the component by name, we look up that name to get the component address, 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 repeat sections defining components and connections. The only restriction is that we cannot make a connection unless the components on both sides of the wire already exist.

In this new 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.

Here is the new step we need to make these changes:

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

Machine.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
attiny85sim (v0.8.0) 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.