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