A First Look at Computers

Examining an Elementary Computer

Before we examine the EVM, we will look at a very simple computer to get an understanding of the process a computer undergoes when running. By understanding the logistics of an elementary computer, we will have the foundation necessary to understand more sophisticated computers.

The Cuzco Model

The Cuzco Model is a basic computer that I have created for the purposes of this section; this computer is capable of performing basic arithmetic operations.

To get started, we will first discuss the architecture of the Cuzco Model - i.e. the components that the Cuzco Model is comprised of:

• Instructions: an ordered list of operations that the computer will perform. This list is 0-indexed.

• Program Counter (PC): keeps track of the current instruction to execute

• Stack: data structure that is updated via operations

Now that we have discussed the architecture of the Cuzco Model, we will examine the stack - although simple, the stack allows us for the Cuzco Model to be memoryful. Otherwise, we can perform an infinite number of operations and our computer would still remain in the same "state". Like all stacks, the stack that the Cuzco Model utilizes operates on a last-in, first-out principle. However, this stack grows up, not down.

Next, we discuss the operations that the Cuzco Model is capable of; listed below are a

Operation	Operation Code (OpCode)	Description
Push v	0x00 v	Pushes v to the top of the stack
Addition	0x01	Pops the top two elements from the stack, computes their sum, and pushes the result to the stack
Subtraction	0x02	Pops the top two elements from the stack, computes their difference, and pushes the result to the stack
Logical And	0x03	Pops the topmost element from the stack, computes the logical and operation of the value, and pushes the result to the stack
Bitwise And	0x04	Pops the topmost elements from the stack, computes the bitwise and operation of the value, and pushes the result to the stack
Stop	0x05	Stops execution of the program

Finally, listed below are the invariants that the Cuzco model abides by:

• All values on the stack are 8-bit signed integers.

  • Furthermore, there is no protection against integer overflow

• The stack has a maximum depth of 4 values

Now that we have the specification of the Cuzco Model outlined, let's examine a couple of examples that show the power of the Cuzco Model!

Example One: Adding Two Values

We begin by adding two numbers; although this may seem like an easy task at first, there are multiple steps involved for the Cuzco Model to execute this.

Assume that we want to compute the sum of 1 + 2. The first step in this is to get the values 1 and 2 onto the computer itself. To do this, we can use the Push operation; listed below are the two Push operations that we need to input 1 and 2 into the Cuzco Model:

0x00 0x01 (Push 2)
0x00 0x02 (Push 1)

Now that we have the two values 1 and 2 pushed onto the stack, we want to compute their sum. To do this, we can use the addition operation. Our updated list of instructions is as follows:

0x00 0x1 (Push 2)
0x00 0x2 (Push 1)
0x01 (Addition)

Finally, to signal to the computer that we are finished executing, we include the Stop operation at the end of our instructions. Therefore, our final set of instructions is as follows:

0x00 0x1 (Push 2)
0x00 0x2 (Push 1)
0x01 (Addition)
0x05 (Stop)

We now run the Cuzco Model on the set of instructions provided above. Below is a table which shows the state of the computer at each step of execution:

PC	Instruction	Stack	Description
0x0	0x00 0x1	1 |	We are pushing 1 onto the stack
0x1	0x00 0x2	2 | 1 |	We are pushing two onto the stack
0x2	0x01	3 |	We are computing the sum of 1 and 2
0x3	0x05	3 |	We are terminating the program

Example Two: Multiple Arithmetic Operations

In this next example, we will introduce the subtraction operation. Here, we will compute (1 + 2) - 5, which should yield us the value -2. Rather than having to rewrite our original list of instructions, we just need to add the following two operations:

• We need to push 5 onto the stack before we push 1 and 2

• After computing the sum of 1 and 2, we need to compute the difference of the result and 5

Therefore, our updated set of instructions is as follows:

0x00 0x5 (Push 5)
0x00 0x1 (Push 2)
0x00 0x2 (Push 1)
0x01 (Addition)
0x02 (Subtraction)
0x05 (Stop)

Running the Cuzco Model on the new set of instructions, our state table is as follows:

PC	Instruction	Stack	Description
0x0	0x00 0x5	5 |	We are pushing 5 onto the stack
0x1	0x00 0x1	1 | 5	We are pushing 1 onto the stack
0x2	0x00 0x2	2 | 1 | 5	We are pushing 2 onto the stack
0x3	0x01	3 | 5	We are computing the sum of 1 and 2
0x4	0x02	-2 |	We are computing the difference of 3 and 5
0x5	0x05	-2 |	We are terminating the program

Example Three: Introducing Logical Operators

In this example, we want to compute the result of 1 && 2 (where && is the logical and operator). Since 1, 2 are nonzero values, this should equal 1. First writing our set of instructions:

0x00 0x1 (Push 1)
0x00 0x2 (Push 2)
0x03 (Logical And)
0x05 (Stop)

Running the Cuzco Model on the set of instructions above:

PC	Instruction	Stack	Description
0x0	0x00 0x1	1 |	We are pushing 1 onto the stack
0x1	0x00 0x2	2 | 1 |	We are pushing 2 onto the stack
0x2	0x03	1 |	We are popping 1 and 2 from the stack, computing the logical and operation, and pushing the result onto the stack
0x3	0x05	1 |	We are terminating the program

Example Four: Introducing Bitwise Operators

In our final example, we will introduce the usage of the bitwise and operator.

For this example, we want to compute 1 & -2 (where & is the bitwise and operator). Before writing the instructions, we want to first understand what the expected result should be. For this, we will need to represent 1 and -2 in binary notation (using two's complement. Therefore, we have:

1 => 00000001
-2 => 11111110

The bitwise and operator, as the name might suggest, applies the and operation on a bit-by-bit basis. Therefore, it is easy to see that 1 & -2 = 0. Now that we know what the expected result should be, we write the instructions our compute will execute:

0x00 0x01 (Push 1)
0x00 0xFE (Push -2)
0x04 (Bitwise And)
0x05 (Stop)

Our state table is as follows:

PC	Instruction	Stack	Description
0x0	0x00 0x1	1 |	We are pushing 1 onto the stack
0x1	0x00 0xFe	-2 | 1 |	We are pushing -2 onto the stack
0x2	0x04	0 |	We are popping 1 and 2 from the stack, computing the bitwise and operation, and pushing the result onto the stack
0x3	0x05	0 |	We are terminating the program

Cuzco Machine, in Solidity!

// SPDX-License-Identifier: MIT
pragma solidity ^0.8.0;

contract CuzcoMachine {

    int8[] stack;

    function execute(bytes calldata insn) public returns (int8) {
        uint counter = 0;
        while (counter < insn.length) {
            if (insn[counter] == 0x0) {
                // We have push operation
                // Extract pushvalue
                int8 pushValue = int8(uint8(insn[counter + 1]));
                pushOntoStack(pushValue);
                counter += 2;
            } else {
                // Not push operation
                if (insn[counter] == hex"01") {
                    // Add
                    add();
                } else if (insn[counter] == hex"02") {
                    // Subtract
                    subtract();
                } else if (insn[counter] == hex"03") {
                    // Logical And
                    logicalAnd();
                } else if (insn[counter] == hex"04") {
                    // Bitwise And
                    bitwiseAnd();
                } else {
                    // Stop
                    break;
                }
                counter += 1;
            }
        }
        return stack[stack.length - 1];
    }

    function popTwo() private returns (int8, int8) {
        // Pop two values off stack
        int8 a = stack[stack.length - 1];
        stack.pop();
        int8 b = stack[stack.length - 1];
        stack.pop();
        return (a, b);
    }

    function add() private {
        (int8 a, int8 b) = popTwo();
        stack.push(a + b);
    }

    function subtract() private {
        (int8 a, int8 b) = popTwo();
        stack.push(a - b);
    }

    function logicalAnd() private {
        (int8 a, int8 b) = popTwo();
        // We need to convert a, b to boolean values
        bool a_bool = a != 0;
        bool b_bool = b != 0;
        bool result = a_bool && b_bool;
        int8 result_int;
        if (result) {
            result_int = 1;
        }

        stack.push(result_int);
    }

    function bitwiseAnd() private {
        (int8 a, int8 b) = popTwo();
        stack.push(a & b);
    }

    function pushOntoStack(int8 val) private {
        stack.push(val);
        if (stack.length > 4) {
            revert("Stack overflow!");
        }
    }

}