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 at the current PC address." 167 168 instruction = self.load(self.pc) 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.load(self.pc + 1) 208 self.frame_sp += 1 # adopt the added frame 209 self.jump(addr, self.pc + 2) 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 + 1) 220 frame = self.frame_stack[self.frame_sp] 221 self.push(self.value_stack[frame + n]) 222 self.pc += 2 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 + 1) 233 frame = self.frame_stack[self.frame_sp] 234 self.value_stack[frame + n] = self.pull() 235 self.pc += 2 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 + 1) 252 self.push(addr) 253 self.pc += 2 254 255 def LoadAttr(self): 256 257 """ 258 LoadAttr #n 259 Load from position n in reference: get the contents of position n in the 260 memory referenced by the value on the top of the stack, replacing the 261 value on the top of the stack with the retrieved value. 262 """ 263 264 n = self.load(self.pc + 1) 265 ref = self.pull() 266 self.push(self.load(ref + n)) 267 self.pc += 2 268 269 def StoreAttr(self): 270 271 """ 272 StoreAttr #n 273 Save to position n in reference: pull a value from the stack and save it 274 to position n in the memory referenced by the next value on the stack, 275 also removing the next value on the stack. 276 """ 277 278 n = self.load(self.pc + 1) 279 value = self.pull() 280 self.save(self.pull() + n, value) 281 self.pc += 2 282 283 def LoadAddress(self): 284 285 """ 286 LoadAddress addr 287 Load from addr: get the contents of the location in memory referenced by 288 addr, adding the retrieved value to the top of the stack. 289 """ 290 291 ref = self.load(self.pc + 1) 292 self.push(self.load(ref)) 293 self.pc += 2 294 295 def StoreAddress(self): 296 297 """ 298 StoreAddress addr 299 Save to addr: pull a value from the stack and save it to the location in 300 memory referenced by addr, also removing the value on the top of the 301 stack. 302 """ 303 304 ref = self.load(self.pc + 1) 305 value = self.pull() 306 self.save(ref, value) 307 self.pc += 2 308 309 def Return(self): 310 311 """ 312 Return 313 Return to the address of the caller: pull a value from the PC stack and 314 set it in the PC. 315 """ 316 317 self.pc = self.pull_pc() 318 319 def JumpIfTrue(self): 320 321 """ 322 JumpIfTrue addr 323 Jump to address addr if true: pull a value from the stack and if it 324 represents a true value, jump to address addr. 325 """ 326 327 addr = self.load(self.pc + 1) 328 value = self.pull() 329 if value: 330 self.pc = addr 331 else: 332 self.pc += 2 333 334 def JumpIfFalse(self): 335 336 """ 337 JumpIfFalse addr 338 Jump to address addr if false: pull a value from the stack and if it 339 represents a false value, jump to address addr. 340 """ 341 342 addr = self.load(self.pc + 1) 343 value = self.pull() 344 if not value: 345 self.pc = addr 346 else: 347 self.pc += 2 348 349 def StoreFrame(self): 350 351 """ 352 StoreFrame #n 353 Move the value from the top of the stack to the argument in position n: 354 pull a value from the stack and store it in the argument frame at the 355 given position. 356 """ 357 358 pos = self.load(self.pc + 1) 359 value = self.pull() 360 frame = self.frame_stack[-1] # different from the current frame after MakeFrame 361 self.value_stack[frame + pos] = value 362 self.pc += 2 363 364 # Library functions. 365 366 def rsvp___printnl(self): 367 print self.load(self.value_stack[-1]) 368 369 def rsvp___print(self): 370 print self.load(self.value_stack[-1]), 371 372 def int_____gt__(self): 373 self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1])) 374 375 def int_____sub__(self): 376 result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1]) 377 addr = self.new(1) 378 self.push(addr) 379 self.save(addr, result) 380 381 def int_____mul__(self): 382 result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1]) 383 addr = self.new(1) 384 self.push(addr) 385 self.save(addr, result) 386 387 # vim: tabstop=4 expandtab shiftwidth=4