DSM Version 1.0.0
v. 2024-09-05 00:00
Introduction
Version 1 of the deepcode Stack Machine (DSM) specifies the stack machine and a corresponding code generator. There are portions of the specification that may seem incomplete, such as missing provisions for error-handling in the interface to the machine. In cases like this, the implementer is free to extend the specification to accommodate desired changes.
Stack Machine
Interface
API
Programmers interact with the virtual machine through an API that has 4 functions. Here are example signatures of the functions in C. If you implement the machine in an object-oriented language, these can be methods (and the initializer and cleanup functions can be the constructor and destructor).
/**
* @return A new instance of a VM.
*/
struct VM vm_new(void);
/**
* Load a program into a VM.
*
* @param vm The virtual machine to load the program into.
* @param program An array of instructions.
* @param program_length The number of instructions in @c program.
*/
void vm_load_program(struct VM* vm, uint16_t* program, size_t program_length);
/**
* Run a loaded program.
*
* @param vm The VM containing the program to run.
*/
void vm_run(struct VM* vm);
/**
* Access the value at the top of a VM's stack.
*
* @param vm The VM holding the stack to inspect.
* @return The value at the top of @c vm 's stack.
*/
uint16_t vm_top_of_stack(struct VM* vm);
CLI
Programs are runnable through a command-line tool. The tool takes as input a single argument which is a path to a binary file containing instructions for the DSM. The tool then runs the program in the DSM.
Instructions
Instructions are 16 bits wide. The first 2 bits counting from the most significant bit are the instruction type, and the remaining 14 bits are the instruction data. The following instruction types are supported:
| Instruction Type (bits 15, 14) | Description |
|---|---|
0b00 | Store a positive integer. The last 14 bits are the integer. |
0b01 | Store a negative integer. The last 14 bits are the positive integer. (Assume the machine converts the positive integer to a negative integer when storing the value.) |
0b10 | Perform an opcode-based instruction. The last 14 bits hold the opcode. |
0b11 | Unsupported. |
Opcodes for opcode-based instructions are as follows. The opcode value starts from the least significant bit.
| Opcode (bits 13 - 0) | Description |
|---|---|
0x0 | Halt. Stop executing a program. |
0x1 | Add. Pop the top two values off the stack, add them, and push the result onto the stack. |
0x2 | Subtract. Pop the top two values off the stack, subtract the first popped value from the second, and push the result onto the stack. |
0x3 | Multiply. Pop the top two values off the stack, multiply them, and push the result onto the stack. |
0x4 | Integer division. Pop the top two values off the stack, divide the last popped value by the first popped value, and push the result onto the stack. |
Code Generator
Language
The deepcode Stack Machine Language (DSML) consists of only numbers and operators. The grammar is below:
expression: (number | operator)*
number: [0-9]+
operator: ('+' | '-' | '*' | '/')
Programs are expressions written in postfix notation. Whitespace separates numbers and operators and is otherwise ignored. For example, the following are valid programs.
This is an empty program. It simply halts.
0
This program simply pushes 0 onto the stack and then halts.
0 -20 + 5
/
This says to push 0 onto the stack, push -20 onto the stack, and then pop
the top two items off the stack, add them, and push the result. The top of the
stack is now -20. Then, push 5 onto the stack. Next, pop the top two values
off the stack, divide the first popped value into the second, and then push the
result onto the stack. The final state of the stack is -4. The program then
halts.
1 +
This says to push 1 onto the stack and then attempt to pop two values off the
stack to perform addition. However, there are not enough values on the stack, so
the virtual machine behavior is undefined.
Interface
The code generator is a command-line tool. The tool can be named anything. The tool takes a single command-line argument which is a path to a file containing DSML source code. The tool converts the source code to DSM machine code and writes the machine code to a binary file in the current working directory.
Changelog
Changes to this specification that result in version bumps (see the precise version information at the top of the specification) are listed here. There are no such changes at this time.