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