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 EmptyFrameStack(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 stack_save(self, n, data): 105 106 "Save to location 'n' on the value stack the given 'data'." 107 108 self.value_stack.append(data) 109 110 def stack_load(self, n): 111 112 "Load a value from the value stack at location 'n'." 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 EmptyFrameStack 153 154 def run(self): 155 156 "Execute code in the memory, starting from the current PC address." 157 158 try: 159 while 1: 160 self.execute() 161 except EmptyPCStack: 162 pass 163 164 def execute(self): 165 166 "Execute code in the memory at the current PC address." 167 168 instruction = self.load(self.pc).__class__.__name__ 169 if self.debug: 170 print "%8d %s" % (self.pc, instruction) 171 method = getattr(self, instruction, None) 172 if method is None: 173 raise IllegalInstruction, (self.pc, instruction) 174 else: 175 method() 176 177 def jump(self, addr, next): 178 179 """ 180 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 181 identifies a library function then invoke the library function and set 182 PC to 'next' afterwards; otherwise, set PC to 'addr'. 183 """ 184 185 if isinstance(addr, str): 186 getattr(self, addr)() 187 self.pc = next 188 else: 189 self.push_pc(self.pc + 2) 190 self.pc = addr 191 192 # Instructions. 193 194 def LoadConst(self): 195 196 """ 197 LoadConst addr 198 Load the reference to memory: get the address addr, push the value onto 199 the stack as a value without context. 200 201 This is useful for loading constants. 202 NOTE: This assumes that constants are encoded with context. 203 """ 204 205 op = self.load(self.pc) 206 addr = op.get_operand() 207 value = (addr, None) 208 for result in op.results: 209 self.stack_save(result.level, value) 210 self.pc += 1 211 212 def LoadName(self): 213 214 """ 215 LoadName #n 216 Load from position n in frame: get position n from the current stack 217 frame, push the retrieved value onto the stack. 218 """ 219 220 n = self.load(self.pc).get_operand() 221 frame = self.frame_stack[self.frame_sp] 222 self.push(self.value_stack[frame + n]) 223 self.pc += 1 224 225 def StoreName(self): 226 227 """ 228 StoreName #n 229 Save to position n in frame: pull a value from the stack and set it as 230 position n in the current stack frame. 231 """ 232 233 n = self.load(self.pc).get_operand() 234 frame = self.frame_stack[self.frame_sp] 235 self.value_stack[frame + n] = self.pull() 236 self.pc += 1 237 238 LoadTemp = LoadName 239 StoreTemp = StoreName 240 241 def LoadAttr(self): 242 243 """ 244 LoadAttr #n 245 Load from position n in reference: get the contents of position n in the 246 memory referenced by the value on the top of the stack, replacing the 247 value on the top of the stack with the retrieved value. 248 """ 249 250 n = self.load(self.pc).get_operand() 251 context, ref = self.pull() 252 value = self.load(ref + n) 253 self.push(value) 254 self.pc += 1 255 256 def StoreAttr(self): 257 258 """ 259 StoreAttr #n 260 Save to position n in reference: pull a value from the stack and save it 261 to position n in the memory referenced by the next value on the stack, 262 also removing the next value on the stack. 263 """ 264 265 n = self.load(self.pc).get_operand() 266 value = self.pull() 267 context, ref = self.pull() 268 self.save(ref + n, value) 269 self.pc += 1 270 271 def LoadAttrIndex(self): pass 272 273 def StoreAttrIndex(self): pass 274 275 def LoadAddress(self): 276 277 """ 278 LoadAddress addr 279 Load from addr: get the contents of the location in memory referenced by 280 addr, adding the retrieved value to the top of the stack. 281 """ 282 283 addr = self.load(self.pc).get_operand() 284 value = self.load(addr) 285 self.push(value) 286 self.pc += 1 287 288 def StoreAddress(self): 289 290 """ 291 StoreAddress addr 292 Save to addr: pull a value from the stack and save it to the location in 293 memory referenced by addr, also removing the value on the top of the 294 stack. 295 """ 296 297 addr = self.load(self.pc).get_operand() 298 value = self.pull() 299 self.save(addr, value) 300 self.pc += 1 301 302 def MakeFrame(self): 303 n = self.load(self.pc).get_operand() 304 top = len(self.value_stack) 305 self.add_frame(top) 306 while n > 0: 307 self.push(None) 308 n -= 1 309 self.pc += 1 310 311 def DropFrame(self): 312 result = self.pull() 313 frame = self.pull_frame() 314 self.value_stack = self.value_stack[:frame] # reset stack before call 315 self.push(result) 316 self.pc += 1 317 318 def LoadCallable(self): pass 319 320 def LoadContext(self): 321 322 """ 323 LoadContext 324 Load context from top of stack: get the context from the value on the 325 top of the stack, pushing it onto the stack. 326 """ 327 328 attr = self.value_stack[-1] 329 self.push((attr[1], None)) 330 self.pc += 1 331 332 def CheckFrame(self): pass 333 334 def CheckSelf(self): pass 335 336 def CheckContext(self): 337 338 """ 339 CheckContext 340 Check the context: check the context on the top of the stack 341 """ 342 343 attr = self.value_stack[-1] 344 # NOTE: To be written. 345 self.pc += 1 346 347 def JumpWithFrame(self): 348 attr = self.pull() 349 self.frame_sp += 1 # adopt the added frame 350 target_location = attr[0] 351 target = self.load(target_location) 352 self.jump(target.code_location, self.pc + 1) # return to the instruction after this one 353 354 def Return(self): 355 356 """ 357 Return 358 Return to the address of the caller: pull a value from the PC stack and 359 set it in the PC. 360 """ 361 362 self.pc = self.pull_pc() 363 364 def LoadResult(self): pass 365 366 def Jump(self): pass 367 368 def JumpIfTrue(self): 369 370 """ 371 JumpIfTrue addr 372 Jump to address addr if true: pull a value from the stack and if it 373 represents a true value, jump to address addr. 374 """ 375 376 addr = self.load(self.pc).get_operand() 377 value = self.pull() 378 if value: 379 self.pc = addr 380 else: 381 self.pc += 1 382 383 def JumpIfFalse(self): 384 385 """ 386 JumpIfFalse addr 387 Jump to address addr if false: pull a value from the stack and if it 388 represents a false value, jump to address addr. 389 """ 390 391 addr = self.load(self.pc).get_operand() 392 value = self.pull() 393 if not value: 394 self.pc = addr 395 else: 396 self.pc += 1 397 398 def StoreFrame(self): 399 400 """ 401 StoreFrame #n 402 Move the value from the top of the stack to the argument in position n: 403 pull a value from the stack and store it in the argument frame at the 404 given position. 405 """ 406 407 pos = self.load(self.pc).get_operand() 408 value = self.pull() 409 frame = self.frame_stack[-1] # different from the current frame after MakeFrame 410 self.value_stack[frame + pos] = value 411 self.pc += 1 412 413 # Library functions. 414 415 def rsvp___printnl(self): 416 print self.load(self.value_stack[-1]) 417 418 def rsvp___print(self): 419 print self.load(self.value_stack[-1]), 420 421 def int_____gt__(self): 422 self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1])) 423 424 def int_____sub__(self): 425 result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1]) 426 addr = self.new(1) 427 self.push(addr) 428 self.save(addr, result) 429 430 def int_____mul__(self): 431 result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1]) 432 addr = self.new(1) 433 self.push(addr) 434 self.save(addr, result) 435 436 # vim: tabstop=4 expandtab shiftwidth=4