1 #!/usr/bin/env python 2 3 """ 4 A really simple virtual processor employing a simple set of instructions which 5 ignore low-level operations and merely concentrate on variable access, structure 6 access, structure allocation and function invocations. 7 8 Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk> 9 10 This program is free software; you can redistribute it and/or modify it under 11 the terms of the GNU General Public License as published by the Free Software 12 Foundation; either version 3 of the License, or (at your option) any later 13 version. 14 15 This program is distributed in the hope that it will be useful, but WITHOUT 16 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS 17 FOR A PARTICULAR PURPOSE. See the GNU General Public License for more 18 details. 19 20 You should have received a copy of the GNU General Public License along with 21 this program. If not, see <http://www.gnu.org/licenses/>. 22 23 -------- 24 25 The execution model of the virtual processor involves the following things: 26 27 * Memory 28 * PC (program counter) stack 29 * Value stack 30 * Frame stack (containing pointers to the value stack) 31 * Current frame and arguments pointers 32 33 The memory contains constants, global variable references and program code. 34 35 The PC stack contains the return address associated with each function 36 invocation. 37 38 The value stack contains references to objects that are being manipulated, along 39 with pointers to previous stack frames. 40 41 The frame stack tracks the position of stack frames within the value stack. 42 """ 43 44 class IllegalInstruction(Exception): 45 pass 46 47 class IllegalAddress(Exception): 48 pass 49 50 class EmptyPCStack(Exception): 51 pass 52 53 class EmptyMetadataStack(Exception): 54 pass 55 56 class RSVPMachine: 57 58 "A really simple virtual processor." 59 60 def __init__(self, memory, pc=None, debug=0): 61 62 """ 63 Initialise the processor with a 'memory' (a list of values containing 64 instructions and data) and the optional program counter 'pc'. 65 """ 66 67 self.memory = memory 68 self.pc = pc or 0 69 self.debug = debug 70 self.pc_stack = [] 71 self.value_stack = [] 72 self.frame_stack = [] 73 self.frame_sp = 0 74 75 def load(self, address): 76 77 "Return the value at the given 'address'." 78 79 try: 80 return self.memory[address] 81 except IndexError: 82 raise IllegalAddress, address 83 84 def save(self, address, value): 85 86 "Save to the given 'address' the specified 'value'." 87 88 try: 89 self.memory[address] = value 90 except IndexError: 91 raise IllegalAddress, address 92 93 def new(self, size): 94 95 """ 96 Allocate space of the given 'size', returning the address of the space. 97 """ 98 99 addr = len(self.memory) 100 for i in range(0, size): 101 self.memory.append(None) 102 return addr 103 104 def push(self, data): 105 106 "Push 'data' onto the value stack." 107 108 self.value_stack.append(data) 109 110 def pull(self): 111 112 "Pull a value from the value stack and return it." 113 114 return self.value_stack.pop() 115 116 def push_pc(self, data): 117 118 "Push 'data' onto the PC stack." 119 120 self.pc_stack.append(data) 121 122 def pull_pc(self): 123 124 "Pull a value from the PC stack and return it." 125 126 try: 127 return self.pc_stack.pop() 128 except IndexError: 129 raise EmptyPCStack 130 131 def add_frame(self, data): 132 133 "Add 'data' to the frame stack without updating the stack pointer." 134 135 self.frame_stack.append(data) 136 137 def push_frame(self, data): 138 139 "Push 'data' onto the frame stack." 140 141 self.frame_stack.append(data) 142 self.frame_sp += 1 143 144 def pull_frame(self): 145 146 "Pull a value from the frame stack and return it." 147 148 try: 149 self.frame_sp -= 1 150 return self.frame_stack.pop() 151 except IndexError: 152 raise EmptyMetadataStack 153 154 def execute(self): 155 156 "Execute code in the memory, starting from the current PC address." 157 158 try: 159 while 1: 160 instruction = self.load(self.pc) 161 if self.debug: 162 print "%8d %s" % (self.pc, instruction) 163 method = getattr(self, instruction, None) 164 if method is None: 165 raise IllegalInstruction, self.pc 166 else: 167 method() 168 except EmptyPCStack: 169 pass 170 171 def jump(self, addr, next): 172 173 """ 174 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 175 identifies a library function then invoke the library function and set 176 PC to 'next' afterwards; otherwise, set PC to 'addr'. 177 """ 178 179 if isinstance(addr, str): 180 getattr(self, addr)() 181 self.pc = next 182 else: 183 self.push_pc(self.pc + 2) 184 self.pc = addr 185 186 # Instructions. 187 188 def MakeFrame(self): 189 top = len(self.value_stack) 190 self.add_frame(top) 191 self.pc += 1 192 193 def DropFrame(self): 194 result = self.pull() 195 frame = self.pull_frame() 196 self.value_stack = self.value_stack[:frame] # reset stack before call 197 self.push(result) 198 self.pc += 1 199 200 def JumpWithFrame(self): 201 addr = self.load(self.pc + 1) 202 self.frame_sp += 1 # adopt the added frame 203 self.jump(addr, self.pc + 2) 204 205 def LoadName(self): 206 207 """ 208 LoadName #n 209 Load from position n in frame: get position n from the current stack 210 frame, push the retrieved value onto the stack. 211 """ 212 213 n = self.load(self.pc + 1) 214 frame = self.frame_stack[self.frame_sp] 215 self.push(self.value_stack[frame + n]) 216 self.pc += 2 217 218 def StoreName(self): 219 220 """ 221 StoreName #n 222 Save to position n in frame: pull a value from the stack and set it as 223 position n in the current stack frame. 224 """ 225 226 n = self.load(self.pc + 1) 227 frame = self.frame_stack[self.frame_sp] 228 self.value_stack[frame + n] = self.pull() 229 self.pc += 2 230 231 def LoadConst(self): 232 233 """ 234 LoadConst addr 235 Load the reference to memory: get the address addr, push the value onto 236 the stack. 237 238 This is useful for loading constants. 239 """ 240 241 addr = self.load(self.pc + 1) 242 self.push(addr) 243 self.pc += 2 244 245 def LoadAttr(self): 246 247 """ 248 LoadAttr #n 249 Load from position n in reference: get the contents of position n in the 250 memory referenced by the value on the top of the stack, replacing the 251 value on the top of the stack with the retrieved value. 252 """ 253 254 n = self.load(self.pc + 1) 255 ref = self.pull() 256 self.push(self.load(ref + n)) 257 self.pc += 2 258 259 def StoreAttr(self): 260 261 """ 262 StoreAttr #n 263 Save to position n in reference: pull a value from the stack and save it 264 to position n in the memory referenced by the next value on the stack, 265 also removing the next value on the stack. 266 """ 267 268 n = self.load(self.pc + 1) 269 value = self.pull() 270 self.save(self.pull() + n, value) 271 self.pc += 2 272 273 def Return(self): 274 275 """ 276 Return 277 Return to the address of the caller: pull a value from the PC stack and 278 set it in the PC. 279 """ 280 281 self.pc = self.pull_pc() 282 283 def JumpIfTrue(self): 284 285 """ 286 JumpIfTrue addr 287 Jump to address addr if true: pull a value from the stack and if it 288 represents a true value, jump to address addr. 289 """ 290 291 addr = self.load(self.pc + 1) 292 value = self.pull() 293 if value: 294 self.pc = addr 295 else: 296 self.pc += 2 297 298 def JumpIfFalse(self): 299 300 """ 301 JumpIfFalse addr 302 Jump to address addr if false: pull a value from the stack and if it 303 represents a false value, jump to address addr. 304 """ 305 306 addr = self.load(self.pc + 1) 307 value = self.pull() 308 if not value: 309 self.pc = addr 310 else: 311 self.pc += 2 312 313 def StoreFrame(self): 314 315 """ 316 StoreFrame #n 317 Move the value from the top of the stack to the argument in position n: 318 pull a value from the stack and store it in the argument frame at the 319 given position. 320 """ 321 322 pos = self.load(self.pc + 1) 323 value = self.pull() 324 frame = self.frame_stack[-1] # different from the current frame after MakeFrame 325 self.value_stack[frame + pos] = value 326 self.pc += 2 327 328 # Library functions. 329 330 def rsvp___printnl(self): 331 print self.load(self.value_stack[-1]) 332 333 def rsvp___print(self): 334 print self.load(self.value_stack[-1]), 335 336 def int_____gt__(self): 337 self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1])) 338 339 def int_____sub__(self): 340 result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1]) 341 addr = self.new(1) 342 self.push(addr) 343 self.save(addr, result) 344 345 def int_____mul__(self): 346 result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1]) 347 addr = self.new(1) 348 self.push(addr) 349 self.save(addr, result) 350 351 # vim: tabstop=4 expandtab shiftwidth=4