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

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:

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:

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:

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:

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!");
        }
    }

}

Last updated