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