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 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 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 Pop(self): 195 self.pull() 196 self.pc += 1 197 198 def MakeFrame(self): 199 top = len(self.value_stack) 200 self.add_frame(top) 201 self.pc += 1 202 203 def ReserveFrame(self): 204 n = self.load(self.pc).get_operand() 205 while n > 0: 206 self.push(None) 207 n -= 1 208 self.pc += 1 209 210 def DropFrame(self): 211 result = self.pull() 212 frame = self.pull_frame() 213 self.value_stack = self.value_stack[:frame] # reset stack before call 214 self.push(result) 215 self.pc += 1 216 217 def JumpWithFrame(self): 218 attr = self.pull() 219 self.frame_sp += 1 # adopt the added frame 220 target_location = attr[0] 221 target = self.load(target_location) 222 self.jump(target.code_location, self.pc + 1) # return to the instruction after this one 223 224 def LoadContext(self): 225 226 """ 227 LoadContext 228 Load context from top of stack: get the context from the value on the 229 top of the stack, pushing it onto the stack. 230 """ 231 232 attr = self.value_stack[-1] 233 self.push((attr[1], None)) 234 self.pc += 1 235 236 def CheckContext(self): 237 238 """ 239 CheckContext 240 Check the context: check the context on the top of the stack 241 """ 242 243 attr = self.value_stack[-1] 244 # NOTE: To be written. 245 self.pc += 1 246 247 def LoadName(self): 248 249 """ 250 LoadName #n 251 Load from position n in frame: get position n from the current stack 252 frame, push the retrieved value onto the stack. 253 """ 254 255 n = self.load(self.pc).get_operand() 256 frame = self.frame_stack[self.frame_sp] 257 self.push(self.value_stack[frame + n]) 258 self.pc += 1 259 260 def StoreName(self): 261 262 """ 263 StoreName #n 264 Save to position n in frame: pull a value from the stack and set it as 265 position n in the current stack frame. 266 """ 267 268 n = self.load(self.pc).get_operand() 269 frame = self.frame_stack[self.frame_sp] 270 self.value_stack[frame + n] = self.pull() 271 self.pc += 1 272 273 LoadTemp = LoadName 274 StoreTemp = StoreName 275 276 def LoadConst(self): 277 278 """ 279 LoadConst addr 280 Load the reference to memory: get the address addr, push the value onto 281 the stack as a value without context. 282 283 This is useful for loading constants. 284 NOTE: This assumes that constants are encoded with context. 285 """ 286 287 addr = self.load(self.pc).get_operand() 288 value = (addr, None) 289 self.push(value) 290 self.pc += 1 291 292 def LoadAttr(self): 293 294 """ 295 LoadAttr #n 296 Load from position n in reference: get the contents of position n in the 297 memory referenced by the value on the top of the stack, replacing the 298 value on the top of the stack with the retrieved value. 299 """ 300 301 n = self.load(self.pc).get_operand() 302 context, ref = self.pull() 303 value = self.load(ref + n) 304 self.push(value) 305 self.pc += 1 306 307 def StoreAttr(self): 308 309 """ 310 StoreAttr #n 311 Save to position n in reference: pull a value from the stack and save it 312 to position n in the memory referenced by the next value on the stack, 313 also removing the next value on the stack. 314 """ 315 316 n = self.load(self.pc).get_operand() 317 value = self.pull() 318 context, ref = self.pull() 319 self.save(ref + n, value) 320 self.pc += 1 321 322 def LoadAddress(self): 323 324 """ 325 LoadAddress addr 326 Load from addr: get the contents of the location in memory referenced by 327 addr, adding the retrieved value to the top of the stack. 328 """ 329 330 addr = self.load(self.pc).get_operand() 331 value = self.load(addr) 332 self.push(value) 333 self.pc += 1 334 335 def StoreAddress(self): 336 337 """ 338 StoreAddress addr 339 Save to addr: pull a value from the stack and save it to the location in 340 memory referenced by addr, also removing the value on the top of the 341 stack. 342 """ 343 344 addr = self.load(self.pc).get_operand() 345 value = self.pull() 346 self.save(addr, value) 347 self.pc += 1 348 349 def Return(self): 350 351 """ 352 Return 353 Return to the address of the caller: pull a value from the PC stack and 354 set it in the PC. 355 """ 356 357 self.pc = self.pull_pc() 358 359 def JumpIfTrue(self): 360 361 """ 362 JumpIfTrue addr 363 Jump to address addr if true: pull a value from the stack and if it 364 represents a true value, jump to address addr. 365 """ 366 367 addr = self.load(self.pc).get_operand() 368 value = self.pull() 369 if value: 370 self.pc = addr 371 else: 372 self.pc += 1 373 374 def JumpIfFalse(self): 375 376 """ 377 JumpIfFalse addr 378 Jump to address addr if false: pull a value from the stack and if it 379 represents a false value, jump to address addr. 380 """ 381 382 addr = self.load(self.pc).get_operand() 383 value = self.pull() 384 if not value: 385 self.pc = addr 386 else: 387 self.pc += 1 388 389 def StoreFrame(self): 390 391 """ 392 StoreFrame #n 393 Move the value from the top of the stack to the argument in position n: 394 pull a value from the stack and store it in the argument frame at the 395 given position. 396 """ 397 398 pos = self.load(self.pc).get_operand() 399 value = self.pull() 400 frame = self.frame_stack[-1] # different from the current frame after MakeFrame 401 self.value_stack[frame + pos] = value 402 self.pc += 1 403 404 # Library functions. 405 406 def rsvp___printnl(self): 407 print self.load(self.value_stack[-1]) 408 409 def rsvp___print(self): 410 print self.load(self.value_stack[-1]), 411 412 def int_____gt__(self): 413 self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1])) 414 415 def int_____sub__(self): 416 result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1]) 417 addr = self.new(1) 418 self.push(addr) 419 self.save(addr, result) 420 421 def int_____mul__(self): 422 result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1]) 423 addr = self.new(1) 424 self.push(addr) 425 self.save(addr, result) 426 427 # vim: tabstop=4 expandtab shiftwidth=4