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 The execution model involves the following things: 9 10 * Memory 11 * PC (program counter) stack 12 * Value stack 13 * Current frame pointer 14 15 The memory contains constants, global variable references and program code. 16 17 The PC stack contains the return address associated with each function 18 invocation. 19 20 The value stack contains references to objects that are being manipulated, along 21 with pointers to previous stack frames. 22 23 The current frame pointer indicates the position of the current stack frame 24 within the value stack. 25 26 The PC and value stacks have their own pointers which remember the top of the 27 stack: this is, in fact, the next position to be used by the stack when pushing 28 a value onto it. 29 """ 30 31 class IllegalInstruction(Exception): 32 pass 33 34 class IllegalAddress(Exception): 35 pass 36 37 class EmptyPCStack(Exception): 38 pass 39 40 class RSVPMachine: 41 42 "A really simple virtual processor." 43 44 def __init__(self, memory, pc=None, debug=0): 45 46 """ 47 Initialise the processor with a 'memory' (a list of values containing 48 instructions and data) and the optional program counter 'pc'. 49 """ 50 51 self.memory = memory 52 self.pc = pc or 0 53 self.debug = debug 54 self.pc_stack = [] 55 self.value_stack = [] 56 self.current_frame = 0 57 58 def load(self, address): 59 60 "Return the value at the given 'address'." 61 62 try: 63 return self.memory[address] 64 except IndexError: 65 raise IllegalAddress, address 66 67 def save(self, address, value): 68 69 "Save to the given 'address' the specified 'value'." 70 71 try: 72 self.memory[address] = value 73 except IndexError: 74 raise IllegalAddress, address 75 76 def new(self, size): 77 78 """ 79 Allocate space of the given 'size', returning the address of the space. 80 """ 81 82 addr = len(self.memory) 83 for i in range(0, size): 84 self.memory.append(None) 85 return addr 86 87 def push(self, data): 88 89 "Push 'data' onto the value stack." 90 91 self.value_stack.append(data) 92 93 def pull(self): 94 95 "Pull a value from the value stack and return it." 96 97 return self.value_stack.pop() 98 99 def push_pc(self, data): 100 101 "Push 'data' onto the PC stack." 102 103 self.pc_stack.append(data) 104 105 def pull_pc(self): 106 107 "Pull a value from the PC stack and return it." 108 109 try: 110 return self.pc_stack.pop() 111 except IndexError: 112 raise EmptyPCStack 113 114 def execute(self): 115 116 "Execute code in the memory, starting from the current PC address." 117 118 try: 119 while 1: 120 instruction = self.load(self.pc) 121 if self.debug: 122 print "%8d %s" % (self.pc, instruction) 123 method = getattr(self, instruction, None) 124 if method is None: 125 raise IllegalInstruction, self.pc 126 else: 127 method() 128 except EmptyPCStack: 129 pass 130 131 def jump(self, addr, next): 132 133 """ 134 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 135 identifies a library function then invoke the library function and set 136 PC to 'next' afterwards; otherwise, set PC to 'addr'. 137 """ 138 139 if isinstance(addr, str): 140 getattr(self, addr)() 141 self.PSF() 142 self.pc = next 143 else: 144 self.push_pc(self.pc + 2) 145 self.pc = addr 146 147 # Instructions. 148 149 def SCF(self): 150 151 """ 152 SCF 153 Save current stack frame: record the current stack frame pointer on the 154 value stack. 155 """ 156 157 self.push(self.current_frame) 158 self.pc += 1 159 160 def NSF(self): 161 162 """ 163 NSF #n 164 Next stack frame of size n: set the current stack frame pointer to the 165 current top of stack value minus n+1 positions, where n positions are 166 used for parameter values and 1 position is used for the previous stack 167 frame pointer value. 168 """ 169 170 top = len(self.value_stack) 171 n = self.load(self.pc + 1) 172 self.current_frame = top - (n+1) 173 self.pc += 2 174 175 def PSF(self): 176 177 """ 178 PSF 179 Previous stack frame: restore the previous stack frame by reading the 180 stored stack frame pointer, setting the current stack frame pointer to 181 that value, and by setting the top of stack to the previous stack frame 182 pointer. In order to propagate return values, the top of the stack from 183 before this instruction is restored afterwards. 184 """ 185 186 result = self.pull() 187 top = self.current_frame 188 self.current_frame = self.value_stack[top] 189 self.value_stack = self.value_stack[:top] 190 self.push(result) 191 self.pc += 1 192 193 def ESF(self): 194 195 """ 196 ESF #m 197 Extend stack frame by n values: allocate n positions on the stack, 198 typically so that local variables can be stored. 199 """ 200 201 n = self.load(self.pc + 1) 202 for i in range(0, n): 203 self.value_stack.append(None) 204 self.pc += 2 205 206 def LPF(self): 207 208 """ 209 LPF #n 210 Load from position n in frame: get position n from the current stack 211 frame, push the retrieved value onto the stack. 212 """ 213 214 n = self.load(self.pc + 1) 215 self.push(self.value_stack[self.current_frame + n]) 216 self.pc += 2 217 218 def SPF(self): 219 220 """ 221 SPF #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 self.value_stack[self.current_frame + n] = self.pull() 228 self.pc += 2 229 230 def LRM(self): 231 232 """ 233 LRM #addr 234 Load the reference to memory: get the address addr, push the value onto 235 the stack. 236 237 This is useful for loading constants. 238 """ 239 240 addr = self.load(self.pc + 1) 241 self.push(addr) 242 self.pc += 2 243 244 def LAM(self): 245 246 """ 247 LAM addr 248 Load from address addr in memory: get the contents of address addr from 249 memory, push the retrieved value onto the stack. 250 251 This is useful for loading globals. 252 """ 253 254 addr = self.load(self.pc + 1) 255 self.push(self.load(addr)) 256 self.pc += 2 257 258 def SAM(self): 259 260 """ 261 SAM addr 262 Save to address addr in memory: pull a value from the stack and save it 263 to address addr in memory. 264 265 This is useful for saving globals. 266 """ 267 268 addr = self.load(self.pc + 1) 269 self.save(addr, self.pull()) 270 self.pc += 2 271 272 def LPR(self): 273 274 """ 275 LPR #n 276 Load from position n in reference: get the contents of position n in the 277 memory referenced by the value on the top of the stack, replacing the 278 value on the top of the stack with the retrieved value. 279 """ 280 281 n = self.load(self.pc + 1) 282 ref = self.pull() 283 self.push(self.load(ref + n)) 284 self.pc += 2 285 286 def SPR(self): 287 288 """ 289 SPR #n 290 Save to position n in reference: pull a value from the stack and save it 291 to position n in the memory referenced by the next value on the stack, 292 also removing the next value on the stack. 293 """ 294 295 n = self.load(self.pc + 1) 296 value = self.pull() 297 self.save(self.pull() + n, value) 298 self.pc += 2 299 300 def JAS(self): 301 302 """ 303 JAS addr 304 Jump to address addr to invoke a subroutine: store the location of the 305 next instruction on the PC stack, set the address addr in the PC. 306 """ 307 308 addr = self.load(self.pc + 1) 309 self.jump(addr, self.pc + 2) 310 311 def RAC(self): 312 313 """ 314 RAC 315 Return to the address of the caller: pull a value from the PC stack and 316 set it in the PC. 317 """ 318 319 self.pc = self.pull_pc() 320 321 def JAT(self): 322 323 """ 324 JAT addr 325 Jump to address addr if true: pull a value from the stack and if it 326 represents a true value, jump to address addr. 327 """ 328 329 addr = self.load(self.pc + 1) 330 value = self.pull() 331 if value: 332 self.pc = addr 333 else: 334 self.pc += 2 335 336 def JAF(self): 337 338 """ 339 JAF addr 340 Jump to address addr if false: pull a value from the stack and if it 341 represents a false value, jump to address addr. 342 """ 343 344 addr = self.load(self.pc + 1) 345 value = self.pull() 346 if not value: 347 self.pc = addr 348 else: 349 self.pc += 2 350 351 # Library functions. 352 353 def rsvp___printnl(self): 354 print self.load(self.value_stack[-1]) 355 356 def rsvp___print(self): 357 print self.load(self.value_stack[-1]), 358 359 def int_____gt__(self): 360 self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1])) 361 362 def int_____sub__(self): 363 result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1]) 364 addr = self.new(1) 365 self.push(addr) 366 self.save(addr, result) 367 368 def int_____mul__(self): 369 result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1]) 370 addr = self.new(1) 371 self.push(addr) 372 self.save(addr, result) 373 374 class RSVPAssembler: 375 376 "An assembler for RSVP code." 377 378 def __init__(self, debug=0): 379 380 "Initialise the assembler." 381 382 self.memory = [] 383 self.label_users = {} 384 self.labels = {} 385 self.debug = debug 386 387 def add(self, value, data=None): 388 389 "Add the given 'value' and optional 'data' to the program." 390 391 if self.debug: 392 if data is None: 393 print value 394 else: 395 print value, data 396 397 self.memory.append(value) 398 if data is not None: 399 if isinstance(data, str) and data.startswith("$"): 400 label_user = len(self.memory) 401 402 # Where a label exists, write an absolute address. 403 404 if self.labels.has_key(data): 405 self.memory.append(self.labels[data]) 406 407 # Otherwise, add a placeholder value. 408 409 else: 410 self.memory.append(None) 411 412 # Add the label "user" for relocation purposes. 413 414 if not self.label_users.has_key(data): 415 self.label_users[data] = [] 416 self.label_users[data].append(label_user) 417 418 else: 419 self.memory.append(data) 420 421 def add_many(self, *instructions): 422 for instruction in instructions: 423 self.add(*instruction) 424 425 def label(self, name, value=None): 426 427 """ 428 Define the label with the given 'name'. If the optional 'value' is 429 specified, associate the label with 'value'; otherwise, associate it 430 with the next position in the program. 431 """ 432 433 if self.debug: 434 if value is None: 435 print name 436 else: 437 print name, "at", value 438 439 if value is None: 440 value = len(self.memory) 441 442 self.labels[name] = value 443 for user in self.label_users.get(name, []): 444 self.memory[user] = value 445 446 def add_labels(self, labels, label_users, offset): 447 448 """ 449 Add the given 'labels' and 'label_users' to the program, with the 450 label definitions and users adjusted by the given 'offset'. 451 """ 452 453 for name, users in label_users.items(): 454 if not self.label_users.has_key(name): 455 self.label_users[name] = [] 456 for user in users: 457 self.label_users[name].append(user + offset) 458 459 for name, value in labels.items(): 460 self.label(name, value + offset) 461 462 def merge(self, assembler): 463 464 "Merge the memory and labels of the given 'assembler' with this one." 465 466 label_base = len(self.memory) 467 self.memory += assembler.memory 468 self.add_labels(assembler.labels, assembler.label_users, label_base) 469 470 def dump(memory): 471 for i in range(0, len(memory)): 472 print "%8d %s" % (i, memory[i]) 473 474 def get_image(*assemblers): 475 merged_assembler = RSVPAssembler() 476 for assembler in assemblers: 477 merged_assembler.merge(assembler) 478 return merged_assembler.memory 479 480 def test_fact(n, debug=0): 481 482 """ 483 Assemble the classic factorial function: 484 def fact(n): 485 if n > 1: 486 return n * fact(n - 1) 487 else: 488 return 1 489 """ 490 491 i_fact = 13 492 i_else = 47 493 i_n = 51 494 i_1 = 52 495 memory = ["SCF", "SCF", "LRM", i_n, "NSF", 1, "JAS", i_fact, "NSF", 1, "JAS", "rsvp___print", "RAC"] 496 memory += ["SCF", "LPF", 1, "LRM", i_1, "NSF", 2, "JAS", "int_____gt__", "JAF", i_else] 497 memory += ["SCF", "LPF", 1, 498 "SCF", 499 "SCF", "LPF", 1, "LRM", i_1, "NSF", 2, "JAS", "int_____sub__", 500 "NSF", 1, "JAS", i_fact, 501 "NSF", 2, "JAS", "int_____mul__", 502 "PSF", "RAC"] 503 memory += ["LRM", i_1, "PSF", "RAC"] 504 memory += [n, 1] 505 506 dump(memory) 507 508 proc = RSVPMachine(memory, debug=debug) 509 proc.execute() 510 511 def test_fact2(n, debug=0): 512 main_assembler = RSVPAssembler() 513 main_assembler.add_many( 514 ("SCF",), ("SCF",), ("LRM", "$n"), ("NSF", 1), ("JAS", "$fact"), ("NSF", 1), ("JAS", "rsvp___print"), ("RAC",) 515 ) 516 517 fact_assembler = RSVPAssembler() 518 fact_assembler.label("$fact") 519 fact_assembler.add_many( 520 ("SCF",), ("LPF", 1), ("LRM", "$1"), ("NSF", 2), ("JAS", "int_____gt__"), ("JAF", "$else"), 521 ("SCF",), ("LPF", 1), 522 ("SCF",), 523 ("SCF",), ("LPF", 1), ("LRM", "$1"), ("NSF", 2), ("JAS", "int_____sub__"), 524 ("NSF", 1), ("JAS", "$fact"), 525 ("NSF", 2), ("JAS", "int_____mul__"), 526 ("PSF",), ("RAC",) 527 ) 528 fact_assembler.label("$else") 529 fact_assembler.add_many( 530 ("LRM", "$1"), ("PSF",), ("RAC",) 531 ) 532 fact_assembler.label("$n") 533 fact_assembler.add(n) 534 fact_assembler.label("$1") 535 fact_assembler.add(1) 536 537 memory = get_image(main_assembler, fact_assembler) 538 539 dump(memory) 540 541 proc = RSVPMachine(memory, debug=debug) 542 proc.execute() 543 544 def test_empty(debug=0): 545 546 "Test an empty memory." 547 548 try: 549 proc = RSVPMachine([], debug=debug) 550 proc.execute() 551 except IllegalAddress, exc: 552 return exc.args[0] == 0 553 554 if __name__ == "__main__": 555 print test_empty() 556 test_fact(3) 557 test_fact2(3) 558 559 # vim: tabstop=4 expandtab shiftwidth=4