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 execute(self): 155 156 "Execute code in the memory, starting from the current PC address." 157 158 try: 159 while 1: 160 instruction = self.load(self.pc) 161 if self.debug: 162 print "%8d %s" % (self.pc, instruction) 163 method = getattr(self, instruction, None) 164 if method is None: 165 raise IllegalInstruction, self.pc 166 else: 167 method() 168 except EmptyPCStack: 169 pass 170 171 def jump(self, addr, next): 172 173 """ 174 Jump to the subroutine at (or identified by) 'addr'. If 'addr' 175 identifies a library function then invoke the library function and set 176 PC to 'next' afterwards; otherwise, set PC to 'addr'. 177 """ 178 179 if isinstance(addr, str): 180 getattr(self, addr)() 181 self.pc = next 182 else: 183 self.push_pc(self.pc + 2) 184 self.pc = addr 185 186 # Instructions. 187 188 def MakeFrame(self): 189 top = len(self.value_stack) 190 self.add_frame(top) 191 self.pc += 1 192 193 def DropFrame(self): 194 result = self.pull() 195 frame = self.pull_frame() 196 self.value_stack = self.value_stack[:frame] # reset stack before call 197 self.push(result) 198 self.pc += 1 199 200 def JumpWithFrame(self): 201 addr = self.load(self.pc + 1) 202 self.frame_sp += 1 # adopt the added frame 203 self.jump(addr, self.pc + 2) 204 205 def LoadName(self): 206 207 """ 208 LoadName #n 209 Load from position n in frame: get position n from the current stack 210 frame, push the retrieved value onto the stack. 211 """ 212 213 n = self.load(self.pc + 1) 214 frame = self.frame_stack[self.frame_sp] 215 self.push(self.value_stack[frame + n]) 216 self.pc += 2 217 218 def StoreName(self): 219 220 """ 221 StoreName #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 frame = self.frame_stack[self.frame_sp] 228 self.value_stack[frame + n] = self.pull() 229 self.pc += 2 230 231 LoadTemp = LoadName 232 StoreTemp = StoreName 233 234 def LoadConst(self): 235 236 """ 237 LoadConst addr 238 Load the reference to memory: get the address addr, push the value onto 239 the stack. 240 241 This is useful for loading constants. 242 """ 243 244 addr = self.load(self.pc + 1) 245 self.push(addr) 246 self.pc += 2 247 248 def LoadAttr(self): 249 250 """ 251 LoadAttr #n 252 Load from position n in reference: get the contents of position n in the 253 memory referenced by the value on the top of the stack, replacing the 254 value on the top of the stack with the retrieved value. 255 """ 256 257 n = self.load(self.pc + 1) 258 ref = self.pull() 259 self.push(self.load(ref + n)) 260 self.pc += 2 261 262 def StoreAttr(self): 263 264 """ 265 StoreAttr #n 266 Save to position n in reference: pull a value from the stack and save it 267 to position n in the memory referenced by the next value on the stack, 268 also removing the next value on the stack. 269 """ 270 271 n = self.load(self.pc + 1) 272 value = self.pull() 273 self.save(self.pull() + n, value) 274 self.pc += 2 275 276 def LoadAddress(self): 277 278 """ 279 LoadAddress addr, #n 280 Load from position n in reference at addr: get the contents of position 281 n in the memory referenced by addr, adding the retrieved value to the 282 top of the stack. 283 """ 284 285 red = self.load(self.pc + 1) 286 n = self.load(self.pc + 2) 287 self.push(self.load(ref + n)) 288 self.pc += 3 289 290 def StoreAddress(self): 291 292 """ 293 StoreAddress addr, #n 294 Save to position n in reference at addr: pull a value from the stack and 295 save it to position n in the memory referenced by addr, also removing 296 the value on the top of the stack. 297 """ 298 299 ref = self.load(self.pc + 1) 300 n = self.load(self.pc + 2) 301 value = self.pull() 302 self.save(ref + n, value) 303 self.pc += 3 304 305 def Return(self): 306 307 """ 308 Return 309 Return to the address of the caller: pull a value from the PC stack and 310 set it in the PC. 311 """ 312 313 self.pc = self.pull_pc() 314 315 def JumpIfTrue(self): 316 317 """ 318 JumpIfTrue addr 319 Jump to address addr if true: pull a value from the stack and if it 320 represents a true value, jump to address addr. 321 """ 322 323 addr = self.load(self.pc + 1) 324 value = self.pull() 325 if value: 326 self.pc = addr 327 else: 328 self.pc += 2 329 330 def JumpIfFalse(self): 331 332 """ 333 JumpIfFalse addr 334 Jump to address addr if false: pull a value from the stack and if it 335 represents a false value, jump to address addr. 336 """ 337 338 addr = self.load(self.pc + 1) 339 value = self.pull() 340 if not value: 341 self.pc = addr 342 else: 343 self.pc += 2 344 345 def StoreFrame(self): 346 347 """ 348 StoreFrame #n 349 Move the value from the top of the stack to the argument in position n: 350 pull a value from the stack and store it in the argument frame at the 351 given position. 352 """ 353 354 pos = self.load(self.pc + 1) 355 value = self.pull() 356 frame = self.frame_stack[-1] # different from the current frame after MakeFrame 357 self.value_stack[frame + pos] = value 358 self.pc += 2 359 360 # Library functions. 361 362 def rsvp___printnl(self): 363 print self.load(self.value_stack[-1]) 364 365 def rsvp___print(self): 366 print self.load(self.value_stack[-1]), 367 368 def int_____gt__(self): 369 self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1])) 370 371 def int_____sub__(self): 372 result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1]) 373 addr = self.new(1) 374 self.push(addr) 375 self.save(addr, result) 376 377 def int_____mul__(self): 378 result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1]) 379 addr = self.new(1) 380 self.push(addr) 381 self.save(addr, result) 382 383 # vim: tabstop=4 expandtab shiftwidth=4