# stack-vm
This crate implements a generic stack machine for which you provide the
operands and the instructions and this crate provides the rest of the
infrastructure required to run it.
It also provides a simple instruction builder which you can use to generate
your program.
Stack machines are computers which use an operand stack to perform the
evaluation of postfix expressions. Every computer architecture has it's
own instruction set which is the basic set of operations that the computer
can perform.
Instructions usually describe basic arithmetic operations, I/O, jumps, etc.
## License
This crate is licensed under the terms of the MIT license. See the `LICENSE` file for details.
## Computer Architecture
The architecture of a computer system is how the various logic components
are connected together in order to execute the instructions and produce
side-effects (useful outcomes).
There are two main ways to organise a computer architecture:
* *Von Neumann* - in which the program data and instructions are stored in the same memory.
* *Harvard* - in which the program data and instructions are stored in separate memory sections.
The bulk of modern processors are Von Neumann type machines.
We can also classify our machines by the way that they store intermediate
values:
* *Accumulator* - the most basic form of processor where only a single register is used to store the results of computation.
* *Stack* - stack machines use an operand stack to push and pop results off the top of.
* *Register* - register machines use a number of named (or numbered) registers to store values or pass arguments.
Most modern processors are register machines, although interestingly both
register and stack machines can be used to emulate their cousin.
## Instruction Sets
The instruction set is the definition of the machine. Without instructions
your machine can't *do* anything. They are the fundamental building blocks
of your computer, so you need to think this through before building it.
This virtual machine uses Rust functions as instructions rather than
transistors and logic gates, but the effect is the same.
In order to generate your instructions you need to create a bunch of Rust
functions which conform to the `stack_vm::InstructionFn` signature.
For example:
```rust
use stack_vm::Machine;
type Operand = i64;
fn push(machine: &mut Machine<Operand>, args: &[usize]) {
let arg = machine.get_data(args[0]).clone();
machine.operand_push(arg);
}
```
Once you have finished defining your instructions you can use them to build
a `stack_vm::InstructionTable`, where every instruction is identified by
it's `op_code`, `name` and `arity`.
* `op_code` a positive integer which uniquely identifies this instruction. This is manually entered rather than auto-generated from insert order so that you can maintain as much compatibility between versions of your VM as possible.
* `name` a string used to identify this instruction; mainly for debugging.
* `arity` the number of arguments your instruction expects *from program data*. This is not the number of operands your function needs off the operand stack. This is used so that you can place constant data into the program at compile time.
```rust
use stack_vm::{Instruction, InstructionTable, Machine};
type Operand = i64;
fn push(machine: &mut Machine<Operand>, args: &[usize]) {
let arg = machine.get_data(args[0]).clone();
machine.operand_push(arg);
}
fn add(machine: &mut Machine<Operand>, _args: &[usize]) {
let rhs = machine.operand_pop().clone();
let lhs = machine.operand_pop().clone();
machine.operand_push(lhs + rhs);
}
let mut instruction_table = InstructionTable::new();
instruction_table.insert(Instruction::new(0, "push", 1, push));
instruction_table.insert(Instruction::new(1, "add", 0, add));
```
## Code generation
One your instruction set is defined then you can use the
`stack_vm::Builder` object to build a representation that the VM can
execute.
For example, to push two integers on the stack and add them:
```rust
use stack_vm::{Instruction, InstructionTable, Machine, Builder};
type Operand = i64;
fn push(machine: &mut Machine<Operand>, args: &[usize]) {
let arg = machine.get_data(args[0]).clone();
machine.operand_push(arg);
}
fn add(machine: &mut Machine<Operand>, _args: &[usize]) {
let rhs = machine.operand_pop().clone();
let lhs = machine.operand_pop().clone();
machine.operand_push(lhs + rhs);
}
let mut instruction_table = InstructionTable::new();
instruction_table.insert(Instruction::new(0, "push", 1, push));
instruction_table.insert(Instruction::new(1, "add", 0, add));
let mut builder: Builder<Operand> = Builder::new(&instruction_table);
builder.push(0, vec![3 as Operand]);
builder.push(0, vec![4 as Operand]);
builder.push(1, vec![]);
```
This will result in the following code:
```text
@0 = 3
@1 = 4
.main:
push @0
push @1
add
```
## Running your program
Once you have the instructions and code generated then you can put them
together with the `stack_vm::Machine` to execute it.
```rust
use stack_vm::{Instruction, InstructionTable, Machine, Builder, WriteManyTable};
type Operand = i64;
fn push(machine: &mut Machine<Operand>, args: &[usize]) {
let arg = machine.get_data(args[0]).clone();
machine.operand_push(arg);
}
fn add(machine: &mut Machine<Operand>, _args: &[usize]) {
let rhs = machine.operand_pop().clone();
let lhs = machine.operand_pop().clone();
machine.operand_push(lhs + rhs);
}
let mut instruction_table = InstructionTable::new();
instruction_table.insert(Instruction::new(0, "push", 1, push));
instruction_table.insert(Instruction::new(1, "add", 0, add));
let mut builder: Builder<Operand> = Builder::new(&instruction_table);
builder.push(0, vec![3 as Operand]);
builder.push(0, vec![4 as Operand]);
builder.push(1, vec![]);
let constants: WriteManyTable<Operand> = WriteManyTable::new();
let machine = Machine::from_builder(builder, &constants);
let mut machine = Machine::run(machine);
assert_eq!(machine.operand_pop(), 7);
```
## Calling functions:
Functions are executed by having the machine jump to another label within
the code and continue executing from there.
Every time the machine jumps it creates a new call frame, which allows it
to store and retrieve local variables without clobbering their parent
call context. It also contains the return address, meaning that when you
ask the machine to return it will know which address in the code to go back
to after removing the frame.
You can find an example of function calling in this package's acceptance
tests.