1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/rsvp.py Mon Aug 06 00:54:45 2007 +0200
1.3 @@ -0,0 +1,559 @@
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 +The execution model involves the following things:
1.12 +
1.13 + * Memory
1.14 + * PC (program counter) stack
1.15 + * Value stack
1.16 + * Current frame pointer
1.17 +
1.18 +The memory contains constants, global variable references and program code.
1.19 +
1.20 +The PC stack contains the return address associated with each function
1.21 +invocation.
1.22 +
1.23 +The value stack contains references to objects that are being manipulated, along
1.24 +with pointers to previous stack frames.
1.25 +
1.26 +The current frame pointer indicates the position of the current stack frame
1.27 +within the value stack.
1.28 +
1.29 +The PC and value stacks have their own pointers which remember the top of the
1.30 +stack: this is, in fact, the next position to be used by the stack when pushing
1.31 +a value onto it.
1.32 +"""
1.33 +
1.34 +class IllegalInstruction(Exception):
1.35 + pass
1.36 +
1.37 +class IllegalAddress(Exception):
1.38 + pass
1.39 +
1.40 +class EmptyPCStack(Exception):
1.41 + pass
1.42 +
1.43 +class RSVPMachine:
1.44 +
1.45 + "A really simple virtual processor."
1.46 +
1.47 + def __init__(self, memory, pc=None, debug=0):
1.48 +
1.49 + """
1.50 + Initialise the processor with a 'memory' (a list of values containing
1.51 + instructions and data) and the optional program counter 'pc'.
1.52 + """
1.53 +
1.54 + self.memory = memory
1.55 + self.pc = pc or 0
1.56 + self.debug = debug
1.57 + self.pc_stack = []
1.58 + self.value_stack = []
1.59 + self.current_frame = 0
1.60 +
1.61 + def load(self, address):
1.62 +
1.63 + "Return the value at the given 'address'."
1.64 +
1.65 + try:
1.66 + return self.memory[address]
1.67 + except IndexError:
1.68 + raise IllegalAddress, address
1.69 +
1.70 + def save(self, address, value):
1.71 +
1.72 + "Save to the given 'address' the specified 'value'."
1.73 +
1.74 + try:
1.75 + self.memory[address] = value
1.76 + except IndexError:
1.77 + raise IllegalAddress, address
1.78 +
1.79 + def new(self, size):
1.80 +
1.81 + """
1.82 + Allocate space of the given 'size', returning the address of the space.
1.83 + """
1.84 +
1.85 + addr = len(self.memory)
1.86 + for i in range(0, size):
1.87 + self.memory.append(None)
1.88 + return addr
1.89 +
1.90 + def push(self, data):
1.91 +
1.92 + "Push 'data' onto the value stack."
1.93 +
1.94 + self.value_stack.append(data)
1.95 +
1.96 + def pull(self):
1.97 +
1.98 + "Pull a value from the value stack and return it."
1.99 +
1.100 + return self.value_stack.pop()
1.101 +
1.102 + def push_pc(self, data):
1.103 +
1.104 + "Push 'data' onto the PC stack."
1.105 +
1.106 + self.pc_stack.append(data)
1.107 +
1.108 + def pull_pc(self):
1.109 +
1.110 + "Pull a value from the PC stack and return it."
1.111 +
1.112 + try:
1.113 + return self.pc_stack.pop()
1.114 + except IndexError:
1.115 + raise EmptyPCStack
1.116 +
1.117 + def execute(self):
1.118 +
1.119 + "Execute code in the memory, starting from the current PC address."
1.120 +
1.121 + try:
1.122 + while 1:
1.123 + instruction = self.load(self.pc)
1.124 + if self.debug:
1.125 + print "%8d %s" % (self.pc, instruction)
1.126 + method = getattr(self, instruction, None)
1.127 + if method is None:
1.128 + raise IllegalInstruction, self.pc
1.129 + else:
1.130 + method()
1.131 + except EmptyPCStack:
1.132 + pass
1.133 +
1.134 + def jump(self, addr, next):
1.135 +
1.136 + """
1.137 + Jump to the subroutine at (or identified by) 'addr'. If 'addr'
1.138 + identifies a library function then invoke the library function and set
1.139 + PC to 'next' afterwards; otherwise, set PC to 'addr'.
1.140 + """
1.141 +
1.142 + if isinstance(addr, str):
1.143 + getattr(self, addr)()
1.144 + self.PSF()
1.145 + self.pc = next
1.146 + else:
1.147 + self.push_pc(self.pc + 2)
1.148 + self.pc = addr
1.149 +
1.150 + # Instructions.
1.151 +
1.152 + def SCF(self):
1.153 +
1.154 + """
1.155 + SCF
1.156 + Save current stack frame: record the current stack frame pointer on the
1.157 + value stack.
1.158 + """
1.159 +
1.160 + self.push(self.current_frame)
1.161 + self.pc += 1
1.162 +
1.163 + def NSF(self):
1.164 +
1.165 + """
1.166 + NSF #n
1.167 + Next stack frame of size n: set the current stack frame pointer to the
1.168 + current top of stack value minus n+1 positions, where n positions are
1.169 + used for parameter values and 1 position is used for the previous stack
1.170 + frame pointer value.
1.171 + """
1.172 +
1.173 + top = len(self.value_stack)
1.174 + n = self.load(self.pc + 1)
1.175 + self.current_frame = top - (n+1)
1.176 + self.pc += 2
1.177 +
1.178 + def PSF(self):
1.179 +
1.180 + """
1.181 + PSF
1.182 + Previous stack frame: restore the previous stack frame by reading the
1.183 + stored stack frame pointer, setting the current stack frame pointer to
1.184 + that value, and by setting the top of stack to the previous stack frame
1.185 + pointer. In order to propagate return values, the top of the stack from
1.186 + before this instruction is restored afterwards.
1.187 + """
1.188 +
1.189 + result = self.pull()
1.190 + top = self.current_frame
1.191 + self.current_frame = self.value_stack[top]
1.192 + self.value_stack = self.value_stack[:top]
1.193 + self.push(result)
1.194 + self.pc += 1
1.195 +
1.196 + def ESF(self):
1.197 +
1.198 + """
1.199 + ESF #m
1.200 + Extend stack frame by n values: allocate n positions on the stack,
1.201 + typically so that local variables can be stored.
1.202 + """
1.203 +
1.204 + n = self.load(self.pc + 1)
1.205 + for i in range(0, n):
1.206 + self.value_stack.append(None)
1.207 + self.pc += 2
1.208 +
1.209 + def LPF(self):
1.210 +
1.211 + """
1.212 + LPF #n
1.213 + Load from position n in frame: get position n from the current stack
1.214 + frame, push the retrieved value onto the stack.
1.215 + """
1.216 +
1.217 + n = self.load(self.pc + 1)
1.218 + self.push(self.value_stack[self.current_frame + n])
1.219 + self.pc += 2
1.220 +
1.221 + def SPF(self):
1.222 +
1.223 + """
1.224 + SPF #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 + self.value_stack[self.current_frame + n] = self.pull()
1.231 + self.pc += 2
1.232 +
1.233 + def LRM(self):
1.234 +
1.235 + """
1.236 + LRM #addr
1.237 + Load the reference to memory: get the address addr, push the value onto
1.238 + the stack.
1.239 +
1.240 + This is useful for loading constants.
1.241 + """
1.242 +
1.243 + addr = self.load(self.pc + 1)
1.244 + self.push(addr)
1.245 + self.pc += 2
1.246 +
1.247 + def LAM(self):
1.248 +
1.249 + """
1.250 + LAM addr
1.251 + Load from address addr in memory: get the contents of address addr from
1.252 + memory, push the retrieved value onto the stack.
1.253 +
1.254 + This is useful for loading globals.
1.255 + """
1.256 +
1.257 + addr = self.load(self.pc + 1)
1.258 + self.push(self.load(addr))
1.259 + self.pc += 2
1.260 +
1.261 + def SAM(self):
1.262 +
1.263 + """
1.264 + SAM addr
1.265 + Save to address addr in memory: pull a value from the stack and save it
1.266 + to address addr in memory.
1.267 +
1.268 + This is useful for saving globals.
1.269 + """
1.270 +
1.271 + addr = self.load(self.pc + 1)
1.272 + self.save(addr, self.pull())
1.273 + self.pc += 2
1.274 +
1.275 + def LPR(self):
1.276 +
1.277 + """
1.278 + LPR #n
1.279 + Load from position n in reference: get the contents of position n in the
1.280 + memory referenced by the value on the top of the stack, replacing the
1.281 + value on the top of the stack with the retrieved value.
1.282 + """
1.283 +
1.284 + n = self.load(self.pc + 1)
1.285 + ref = self.pull()
1.286 + self.push(self.load(ref + n))
1.287 + self.pc += 2
1.288 +
1.289 + def SPR(self):
1.290 +
1.291 + """
1.292 + SPR #n
1.293 + Save to position n in reference: pull a value from the stack and save it
1.294 + to position n in the memory referenced by the next value on the stack,
1.295 + also removing the next value on the stack.
1.296 + """
1.297 +
1.298 + n = self.load(self.pc + 1)
1.299 + value = self.pull()
1.300 + self.save(self.pull() + n, value)
1.301 + self.pc += 2
1.302 +
1.303 + def JAS(self):
1.304 +
1.305 + """
1.306 + JAS addr
1.307 + Jump to address addr to invoke a subroutine: store the location of the
1.308 + next instruction on the PC stack, set the address addr in the PC.
1.309 + """
1.310 +
1.311 + addr = self.load(self.pc + 1)
1.312 + self.jump(addr, self.pc + 2)
1.313 +
1.314 + def RAC(self):
1.315 +
1.316 + """
1.317 + RAC
1.318 + Return to the address of the caller: pull a value from the PC stack and
1.319 + set it in the PC.
1.320 + """
1.321 +
1.322 + self.pc = self.pull_pc()
1.323 +
1.324 + def JAT(self):
1.325 +
1.326 + """
1.327 + JAT addr
1.328 + Jump to address addr if true: pull a value from the stack and if it
1.329 + represents a true value, jump to address addr.
1.330 + """
1.331 +
1.332 + addr = self.load(self.pc + 1)
1.333 + value = self.pull()
1.334 + if value:
1.335 + self.pc = addr
1.336 + else:
1.337 + self.pc += 2
1.338 +
1.339 + def JAF(self):
1.340 +
1.341 + """
1.342 + JAF addr
1.343 + Jump to address addr if false: pull a value from the stack and if it
1.344 + represents a false value, jump to address addr.
1.345 + """
1.346 +
1.347 + addr = self.load(self.pc + 1)
1.348 + value = self.pull()
1.349 + if not value:
1.350 + self.pc = addr
1.351 + else:
1.352 + self.pc += 2
1.353 +
1.354 + # Library functions.
1.355 +
1.356 + def rsvp___printnl(self):
1.357 + print self.load(self.value_stack[-1])
1.358 +
1.359 + def rsvp___print(self):
1.360 + print self.load(self.value_stack[-1]),
1.361 +
1.362 + def int_____gt__(self):
1.363 + self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1]))
1.364 +
1.365 + def int_____sub__(self):
1.366 + result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1])
1.367 + addr = self.new(1)
1.368 + self.push(addr)
1.369 + self.save(addr, result)
1.370 +
1.371 + def int_____mul__(self):
1.372 + result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1])
1.373 + addr = self.new(1)
1.374 + self.push(addr)
1.375 + self.save(addr, result)
1.376 +
1.377 +class RSVPAssembler:
1.378 +
1.379 + "An assembler for RSVP code."
1.380 +
1.381 + def __init__(self, debug=0):
1.382 +
1.383 + "Initialise the assembler."
1.384 +
1.385 + self.memory = []
1.386 + self.label_users = {}
1.387 + self.labels = {}
1.388 + self.debug = debug
1.389 +
1.390 + def add(self, value, data=None):
1.391 +
1.392 + "Add the given 'value' and optional 'data' to the program."
1.393 +
1.394 + if self.debug:
1.395 + if data is None:
1.396 + print value
1.397 + else:
1.398 + print value, data
1.399 +
1.400 + self.memory.append(value)
1.401 + if data is not None:
1.402 + if isinstance(data, str) and data.startswith("$"):
1.403 + label_user = len(self.memory)
1.404 +
1.405 + # Where a label exists, write an absolute address.
1.406 +
1.407 + if self.labels.has_key(data):
1.408 + self.memory.append(self.labels[data])
1.409 +
1.410 + # Otherwise, add a placeholder value.
1.411 +
1.412 + else:
1.413 + self.memory.append(None)
1.414 +
1.415 + # Add the label "user" for relocation purposes.
1.416 +
1.417 + if not self.label_users.has_key(data):
1.418 + self.label_users[data] = []
1.419 + self.label_users[data].append(label_user)
1.420 +
1.421 + else:
1.422 + self.memory.append(data)
1.423 +
1.424 + def add_many(self, *instructions):
1.425 + for instruction in instructions:
1.426 + self.add(*instruction)
1.427 +
1.428 + def label(self, name, value=None):
1.429 +
1.430 + """
1.431 + Define the label with the given 'name'. If the optional 'value' is
1.432 + specified, associate the label with 'value'; otherwise, associate it
1.433 + with the next position in the program.
1.434 + """
1.435 +
1.436 + if self.debug:
1.437 + if value is None:
1.438 + print name
1.439 + else:
1.440 + print name, "at", value
1.441 +
1.442 + if value is None:
1.443 + value = len(self.memory)
1.444 +
1.445 + self.labels[name] = value
1.446 + for user in self.label_users.get(name, []):
1.447 + self.memory[user] = value
1.448 +
1.449 + def add_labels(self, labels, label_users, offset):
1.450 +
1.451 + """
1.452 + Add the given 'labels' and 'label_users' to the program, with the
1.453 + label definitions and users adjusted by the given 'offset'.
1.454 + """
1.455 +
1.456 + for name, users in label_users.items():
1.457 + if not self.label_users.has_key(name):
1.458 + self.label_users[name] = []
1.459 + for user in users:
1.460 + self.label_users[name].append(user + offset)
1.461 +
1.462 + for name, value in labels.items():
1.463 + self.label(name, value + offset)
1.464 +
1.465 + def merge(self, assembler):
1.466 +
1.467 + "Merge the memory and labels of the given 'assembler' with this one."
1.468 +
1.469 + label_base = len(self.memory)
1.470 + self.memory += assembler.memory
1.471 + self.add_labels(assembler.labels, assembler.label_users, label_base)
1.472 +
1.473 +def dump(memory):
1.474 + for i in range(0, len(memory)):
1.475 + print "%8d %s" % (i, memory[i])
1.476 +
1.477 +def get_image(*assemblers):
1.478 + merged_assembler = RSVPAssembler()
1.479 + for assembler in assemblers:
1.480 + merged_assembler.merge(assembler)
1.481 + return merged_assembler.memory
1.482 +
1.483 +def test_fact(n, debug=0):
1.484 +
1.485 + """
1.486 + Assemble the classic factorial function:
1.487 + def fact(n):
1.488 + if n > 1:
1.489 + return n * fact(n - 1)
1.490 + else:
1.491 + return 1
1.492 + """
1.493 +
1.494 + i_fact = 13
1.495 + i_else = 47
1.496 + i_n = 51
1.497 + i_1 = 52
1.498 + memory = ["SCF", "SCF", "LRM", i_n, "NSF", 1, "JAS", i_fact, "NSF", 1, "JAS", "rsvp___print", "RAC"]
1.499 + memory += ["SCF", "LPF", 1, "LRM", i_1, "NSF", 2, "JAS", "int_____gt__", "JAF", i_else]
1.500 + memory += ["SCF", "LPF", 1,
1.501 + "SCF",
1.502 + "SCF", "LPF", 1, "LRM", i_1, "NSF", 2, "JAS", "int_____sub__",
1.503 + "NSF", 1, "JAS", i_fact,
1.504 + "NSF", 2, "JAS", "int_____mul__",
1.505 + "PSF", "RAC"]
1.506 + memory += ["LRM", i_1, "PSF", "RAC"]
1.507 + memory += [n, 1]
1.508 +
1.509 + dump(memory)
1.510 +
1.511 + proc = RSVPMachine(memory, debug=debug)
1.512 + proc.execute()
1.513 +
1.514 +def test_fact2(n, debug=0):
1.515 + main_assembler = RSVPAssembler()
1.516 + main_assembler.add_many(
1.517 + ("SCF",), ("SCF",), ("LRM", "$n"), ("NSF", 1), ("JAS", "$fact"), ("NSF", 1), ("JAS", "rsvp___print"), ("RAC",)
1.518 + )
1.519 +
1.520 + fact_assembler = RSVPAssembler()
1.521 + fact_assembler.label("$fact")
1.522 + fact_assembler.add_many(
1.523 + ("SCF",), ("LPF", 1), ("LRM", "$1"), ("NSF", 2), ("JAS", "int_____gt__"), ("JAF", "$else"),
1.524 + ("SCF",), ("LPF", 1),
1.525 + ("SCF",),
1.526 + ("SCF",), ("LPF", 1), ("LRM", "$1"), ("NSF", 2), ("JAS", "int_____sub__"),
1.527 + ("NSF", 1), ("JAS", "$fact"),
1.528 + ("NSF", 2), ("JAS", "int_____mul__"),
1.529 + ("PSF",), ("RAC",)
1.530 + )
1.531 + fact_assembler.label("$else")
1.532 + fact_assembler.add_many(
1.533 + ("LRM", "$1"), ("PSF",), ("RAC",)
1.534 + )
1.535 + fact_assembler.label("$n")
1.536 + fact_assembler.add(n)
1.537 + fact_assembler.label("$1")
1.538 + fact_assembler.add(1)
1.539 +
1.540 + memory = get_image(main_assembler, fact_assembler)
1.541 +
1.542 + dump(memory)
1.543 +
1.544 + proc = RSVPMachine(memory, debug=debug)
1.545 + proc.execute()
1.546 +
1.547 +def test_empty(debug=0):
1.548 +
1.549 + "Test an empty memory."
1.550 +
1.551 + try:
1.552 + proc = RSVPMachine([], debug=debug)
1.553 + proc.execute()
1.554 + except IllegalAddress, exc:
1.555 + return exc.args[0] == 0
1.556 +
1.557 +if __name__ == "__main__":
1.558 + print test_empty()
1.559 + test_fact(3)
1.560 + test_fact2(3)
1.561 +
1.562 +# vim: tabstop=4 expandtab shiftwidth=4