1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rsvp.py Mon Apr 21 00:13:09 2008 +0200
1.3 @@ -0,0 +1,351 @@
1.4 +#!/usr/bin/env python
1.5 +
1.6 +"""
1.7 +A really simple virtual processor employing a simple set of instructions which
1.8 +ignore low-level operations and merely concentrate on variable access, structure
1.9 +access, structure allocation and function invocations.
1.10 +
1.11 +Copyright (C) 2007, 2008 Paul Boddie <paul@boddie.org.uk>
1.12 +
1.13 +This program is free software; you can redistribute it and/or modify it under
1.14 +the terms of the GNU General Public License as published by the Free Software
1.15 +Foundation; either version 3 of the License, or (at your option) any later
1.16 +version.
1.17 +
1.18 +This program is distributed in the hope that it will be useful, but WITHOUT
1.19 +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
1.20 +FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
1.21 +details.
1.22 +
1.23 +You should have received a copy of the GNU General Public License along with
1.24 +this program. If not, see <http://www.gnu.org/licenses/>.
1.25 +
1.26 +--------
1.27 +
1.28 +The execution model of the virtual processor involves the following things:
1.29 +
1.30 + * Memory
1.31 + * PC (program counter) stack
1.32 + * Value stack
1.33 + * Frame stack (containing pointers to the value stack)
1.34 + * Current frame and arguments pointers
1.35 +
1.36 +The memory contains constants, global variable references and program code.
1.37 +
1.38 +The PC stack contains the return address associated with each function
1.39 +invocation.
1.40 +
1.41 +The value stack contains references to objects that are being manipulated, along
1.42 +with pointers to previous stack frames.
1.43 +
1.44 +The frame stack tracks the position of stack frames within the value stack.
1.45 +"""
1.46 +
1.47 +class IllegalInstruction(Exception):
1.48 + pass
1.49 +
1.50 +class IllegalAddress(Exception):
1.51 + pass
1.52 +
1.53 +class EmptyPCStack(Exception):
1.54 + pass
1.55 +
1.56 +class EmptyMetadataStack(Exception):
1.57 + pass
1.58 +
1.59 +class RSVPMachine:
1.60 +
1.61 + "A really simple virtual processor."
1.62 +
1.63 + def __init__(self, memory, pc=None, debug=0):
1.64 +
1.65 + """
1.66 + Initialise the processor with a 'memory' (a list of values containing
1.67 + instructions and data) and the optional program counter 'pc'.
1.68 + """
1.69 +
1.70 + self.memory = memory
1.71 + self.pc = pc or 0
1.72 + self.debug = debug
1.73 + self.pc_stack = []
1.74 + self.value_stack = []
1.75 + self.frame_stack = []
1.76 + self.frame_sp = 0
1.77 +
1.78 + def load(self, address):
1.79 +
1.80 + "Return the value at the given 'address'."
1.81 +
1.82 + try:
1.83 + return self.memory[address]
1.84 + except IndexError:
1.85 + raise IllegalAddress, address
1.86 +
1.87 + def save(self, address, value):
1.88 +
1.89 + "Save to the given 'address' the specified 'value'."
1.90 +
1.91 + try:
1.92 + self.memory[address] = value
1.93 + except IndexError:
1.94 + raise IllegalAddress, address
1.95 +
1.96 + def new(self, size):
1.97 +
1.98 + """
1.99 + Allocate space of the given 'size', returning the address of the space.
1.100 + """
1.101 +
1.102 + addr = len(self.memory)
1.103 + for i in range(0, size):
1.104 + self.memory.append(None)
1.105 + return addr
1.106 +
1.107 + def push(self, data):
1.108 +
1.109 + "Push 'data' onto the value stack."
1.110 +
1.111 + self.value_stack.append(data)
1.112 +
1.113 + def pull(self):
1.114 +
1.115 + "Pull a value from the value stack and return it."
1.116 +
1.117 + return self.value_stack.pop()
1.118 +
1.119 + def push_pc(self, data):
1.120 +
1.121 + "Push 'data' onto the PC stack."
1.122 +
1.123 + self.pc_stack.append(data)
1.124 +
1.125 + def pull_pc(self):
1.126 +
1.127 + "Pull a value from the PC stack and return it."
1.128 +
1.129 + try:
1.130 + return self.pc_stack.pop()
1.131 + except IndexError:
1.132 + raise EmptyPCStack
1.133 +
1.134 + def add_frame(self, data):
1.135 +
1.136 + "Add 'data' to the frame stack without updating the stack pointer."
1.137 +
1.138 + self.frame_stack.append(data)
1.139 +
1.140 + def push_frame(self, data):
1.141 +
1.142 + "Push 'data' onto the frame stack."
1.143 +
1.144 + self.frame_stack.append(data)
1.145 + self.frame_sp += 1
1.146 +
1.147 + def pull_frame(self):
1.148 +
1.149 + "Pull a value from the frame stack and return it."
1.150 +
1.151 + try:
1.152 + self.frame_sp -= 1
1.153 + return self.frame_stack.pop()
1.154 + except IndexError:
1.155 + raise EmptyMetadataStack
1.156 +
1.157 + def execute(self):
1.158 +
1.159 + "Execute code in the memory, starting from the current PC address."
1.160 +
1.161 + try:
1.162 + while 1:
1.163 + instruction = self.load(self.pc)
1.164 + if self.debug:
1.165 + print "%8d %s" % (self.pc, instruction)
1.166 + method = getattr(self, instruction, None)
1.167 + if method is None:
1.168 + raise IllegalInstruction, self.pc
1.169 + else:
1.170 + method()
1.171 + except EmptyPCStack:
1.172 + pass
1.173 +
1.174 + def jump(self, addr, next):
1.175 +
1.176 + """
1.177 + Jump to the subroutine at (or identified by) 'addr'. If 'addr'
1.178 + identifies a library function then invoke the library function and set
1.179 + PC to 'next' afterwards; otherwise, set PC to 'addr'.
1.180 + """
1.181 +
1.182 + if isinstance(addr, str):
1.183 + getattr(self, addr)()
1.184 + self.pc = next
1.185 + else:
1.186 + self.push_pc(self.pc + 2)
1.187 + self.pc = addr
1.188 +
1.189 + # Instructions.
1.190 +
1.191 + def MakeFrame(self):
1.192 + top = len(self.value_stack)
1.193 + self.add_frame(top)
1.194 + self.pc += 1
1.195 +
1.196 + def DropFrame(self):
1.197 + result = self.pull()
1.198 + frame = self.pull_frame()
1.199 + self.value_stack = self.value_stack[:frame] # reset stack before call
1.200 + self.push(result)
1.201 + self.pc += 1
1.202 +
1.203 + def JumpWithFrame(self):
1.204 + addr = self.load(self.pc + 1)
1.205 + self.frame_sp += 1 # adopt the added frame
1.206 + self.jump(addr, self.pc + 2)
1.207 +
1.208 + def LoadName(self):
1.209 +
1.210 + """
1.211 + LoadName #n
1.212 + Load from position n in frame: get position n from the current stack
1.213 + frame, push the retrieved value onto the stack.
1.214 + """
1.215 +
1.216 + n = self.load(self.pc + 1)
1.217 + frame = self.frame_stack[self.frame_sp]
1.218 + self.push(self.value_stack[frame + n])
1.219 + self.pc += 2
1.220 +
1.221 + def StoreName(self):
1.222 +
1.223 + """
1.224 + StoreName #n
1.225 + Save to position n in frame: pull a value from the stack and set it as
1.226 + position n in the current stack frame.
1.227 + """
1.228 +
1.229 + n = self.load(self.pc + 1)
1.230 + frame = self.frame_stack[self.frame_sp]
1.231 + self.value_stack[frame + n] = self.pull()
1.232 + self.pc += 2
1.233 +
1.234 + def LoadConst(self):
1.235 +
1.236 + """
1.237 + LoadConst addr
1.238 + Load the reference to memory: get the address addr, push the value onto
1.239 + the stack.
1.240 +
1.241 + This is useful for loading constants.
1.242 + """
1.243 +
1.244 + addr = self.load(self.pc + 1)
1.245 + self.push(addr)
1.246 + self.pc += 2
1.247 +
1.248 + def LoadAttr(self):
1.249 +
1.250 + """
1.251 + LoadAttr #n
1.252 + Load from position n in reference: get the contents of position n in the
1.253 + memory referenced by the value on the top of the stack, replacing the
1.254 + value on the top of the stack with the retrieved value.
1.255 + """
1.256 +
1.257 + n = self.load(self.pc + 1)
1.258 + ref = self.pull()
1.259 + self.push(self.load(ref + n))
1.260 + self.pc += 2
1.261 +
1.262 + def StoreAttr(self):
1.263 +
1.264 + """
1.265 + StoreAttr #n
1.266 + Save to position n in reference: pull a value from the stack and save it
1.267 + to position n in the memory referenced by the next value on the stack,
1.268 + also removing the next value on the stack.
1.269 + """
1.270 +
1.271 + n = self.load(self.pc + 1)
1.272 + value = self.pull()
1.273 + self.save(self.pull() + n, value)
1.274 + self.pc += 2
1.275 +
1.276 + def Return(self):
1.277 +
1.278 + """
1.279 + Return
1.280 + Return to the address of the caller: pull a value from the PC stack and
1.281 + set it in the PC.
1.282 + """
1.283 +
1.284 + self.pc = self.pull_pc()
1.285 +
1.286 + def JumpIfTrue(self):
1.287 +
1.288 + """
1.289 + JumpIfTrue addr
1.290 + Jump to address addr if true: pull a value from the stack and if it
1.291 + represents a true value, jump to address addr.
1.292 + """
1.293 +
1.294 + addr = self.load(self.pc + 1)
1.295 + value = self.pull()
1.296 + if value:
1.297 + self.pc = addr
1.298 + else:
1.299 + self.pc += 2
1.300 +
1.301 + def JumpIfFalse(self):
1.302 +
1.303 + """
1.304 + JumpIfFalse addr
1.305 + Jump to address addr if false: pull a value from the stack and if it
1.306 + represents a false value, jump to address addr.
1.307 + """
1.308 +
1.309 + addr = self.load(self.pc + 1)
1.310 + value = self.pull()
1.311 + if not value:
1.312 + self.pc = addr
1.313 + else:
1.314 + self.pc += 2
1.315 +
1.316 + def StoreFrame(self):
1.317 +
1.318 + """
1.319 + StoreFrame #n
1.320 + Move the value from the top of the stack to the argument in position n:
1.321 + pull a value from the stack and store it in the argument frame at the
1.322 + given position.
1.323 + """
1.324 +
1.325 + pos = self.load(self.pc + 1)
1.326 + value = self.pull()
1.327 + frame = self.frame_stack[-1] # different from the current frame after MakeFrame
1.328 + self.value_stack[frame + pos] = value
1.329 + self.pc += 2
1.330 +
1.331 + # Library functions.
1.332 +
1.333 + def rsvp___printnl(self):
1.334 + print self.load(self.value_stack[-1])
1.335 +
1.336 + def rsvp___print(self):
1.337 + print self.load(self.value_stack[-1]),
1.338 +
1.339 + def int_____gt__(self):
1.340 + self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1]))
1.341 +
1.342 + def int_____sub__(self):
1.343 + result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1])
1.344 + addr = self.new(1)
1.345 + self.push(addr)
1.346 + self.save(addr, result)
1.347 +
1.348 + def int_____mul__(self):
1.349 + result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1])
1.350 + addr = self.new(1)
1.351 + self.push(addr)
1.352 + self.save(addr, result)
1.353 +
1.354 +# vim: tabstop=4 expandtab shiftwidth=4