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 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226
//! # 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. //! //! ## 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: //! //! ``` //! 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. //! //! ``` //! 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: //! //! ``` //! 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("push", vec![3 as Operand]); //! builder.push("push", vec![4 as Operand]); //! builder.push("add", 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. //! //! ``` //! 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("push", vec![3 as Operand]); //! builder.push("push", vec![4 as Operand]); //! builder.push("add", 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. extern crate rmp; mod builder; mod instruction; mod write_once_table; mod write_many_table; mod table; mod frame; mod stack; mod machine; mod instruction_table; mod code; mod to_byte_code; mod from_byte_code; pub use builder::Builder; pub use instruction::{Instruction, InstructionFn}; pub use write_once_table::WriteOnceTable; pub use write_many_table::WriteManyTable; pub use table::Table; pub use frame::Frame; pub use stack::Stack; pub use machine::Machine; pub use instruction_table::InstructionTable; pub use code::Code; pub use to_byte_code::ToByteCode; pub use from_byte_code::FromByteCode; #[cfg(test)] mod acceptance;