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