# HG changeset patch
# User paulb@localhost.localdomain
# Date 1186354485 -7200
# Node ID feb9c0c7aa199c00668f82cad6440689ddfc9119
# Parent  ec716eb53281859dd4cd182a719fac903aafe3e8
Added tentative code generation support.


diff -r ec716eb53281 -r feb9c0c7aa19 rsvp.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/rsvp.py	Mon Aug 06 00:54:45 2007 +0200
@@ -0,0 +1,559 @@
+#!/usr/bin/env python
+
+"""
+A really simple virtual processor employing a simple set of instructions which
+ignore low-level operations and merely concentrate on variable access, structure
+access, structure allocation and function invocations.
+
+The execution model involves the following things:
+
+  * Memory
+  * PC (program counter) stack
+  * Value stack
+  * Current frame pointer
+
+The memory contains constants, global variable references and program code.
+
+The PC stack contains the return address associated with each function
+invocation.
+
+The value stack contains references to objects that are being manipulated, along
+with pointers to previous stack frames.
+
+The current frame pointer indicates the position of the current stack frame
+within the value stack.
+
+The PC and value stacks have their own pointers which remember the top of the
+stack: this is, in fact, the next position to be used by the stack when pushing
+a value onto it.
+"""
+
+class IllegalInstruction(Exception):
+    pass
+
+class IllegalAddress(Exception):
+    pass
+
+class EmptyPCStack(Exception):
+    pass
+
+class RSVPMachine:
+
+    "A really simple virtual processor."
+
+    def __init__(self, memory, pc=None, debug=0):
+
+        """
+        Initialise the processor with a 'memory' (a list of values containing
+        instructions and data) and the optional program counter 'pc'.
+        """
+
+        self.memory = memory
+        self.pc = pc or 0
+        self.debug = debug
+        self.pc_stack = []
+        self.value_stack = []
+        self.current_frame = 0
+
+    def load(self, address):
+
+        "Return the value at the given 'address'."
+
+        try:
+            return self.memory[address]
+        except IndexError:
+            raise IllegalAddress, address
+
+    def save(self, address, value):
+
+        "Save to the given 'address' the specified 'value'."
+
+        try:
+            self.memory[address] = value
+        except IndexError:
+            raise IllegalAddress, address
+
+    def new(self, size):
+
+        """
+        Allocate space of the given 'size', returning the address of the space.
+        """
+
+        addr = len(self.memory)
+        for i in range(0, size):
+            self.memory.append(None)
+        return addr
+
+    def push(self, data):
+
+        "Push 'data' onto the value stack."
+
+        self.value_stack.append(data)
+
+    def pull(self):
+
+        "Pull a value from the value stack and return it."
+
+        return self.value_stack.pop()
+
+    def push_pc(self, data):
+
+        "Push 'data' onto the PC stack."
+
+        self.pc_stack.append(data)
+
+    def pull_pc(self):
+
+        "Pull a value from the PC stack and return it."
+
+        try:
+            return self.pc_stack.pop()
+        except IndexError:
+            raise EmptyPCStack
+        
+    def execute(self):
+
+        "Execute code in the memory, starting from the current PC address."
+
+        try:
+            while 1:
+                instruction = self.load(self.pc)
+                if self.debug:
+                    print "%8d %s" % (self.pc, instruction)
+                method = getattr(self, instruction, None)
+                if method is None:
+                    raise IllegalInstruction, self.pc
+                else:
+                    method()
+        except EmptyPCStack:
+            pass
+
+    def jump(self, addr, next):
+
+        """
+        Jump to the subroutine at (or identified by) 'addr'. If 'addr'
+        identifies a library function then invoke the library function and set
+        PC to 'next' afterwards; otherwise, set PC to 'addr'.
+        """
+
+        if isinstance(addr, str):
+            getattr(self, addr)()
+            self.PSF()
+            self.pc = next
+        else:
+            self.push_pc(self.pc + 2)
+            self.pc = addr
+
+    # Instructions.
+
+    def SCF(self):
+
+        """
+        SCF
+        Save current stack frame: record the current stack frame pointer on the
+        value stack.
+        """
+
+        self.push(self.current_frame)
+        self.pc += 1
+
+    def NSF(self):
+
+        """
+        NSF #n
+        Next stack frame of size n: set the current stack frame pointer to the
+        current top of stack value minus n+1 positions, where n positions are
+        used for parameter values and 1 position is used for the previous stack
+        frame pointer value.
+        """
+
+        top = len(self.value_stack)
+        n = self.load(self.pc + 1)
+        self.current_frame = top - (n+1)
+        self.pc += 2
+
+    def PSF(self):
+
+        """
+        PSF
+        Previous stack frame: restore the previous stack frame by reading the
+        stored stack frame pointer, setting the current stack frame pointer to
+        that value, and by setting the top of stack to the previous stack frame
+        pointer. In order to propagate return values, the top of the stack from
+        before this instruction is restored afterwards.
+        """
+
+        result = self.pull()
+        top = self.current_frame
+        self.current_frame = self.value_stack[top]
+        self.value_stack = self.value_stack[:top]
+        self.push(result)
+        self.pc += 1
+
+    def ESF(self):
+
+        """
+        ESF #m
+        Extend stack frame by n values: allocate n positions on the stack,
+        typically so that local variables can be stored.
+        """
+
+        n = self.load(self.pc + 1)
+        for i in range(0, n):
+            self.value_stack.append(None)
+        self.pc += 2
+
+    def LPF(self):
+
+        """
+        LPF #n
+        Load from position n in frame: get position n from the current stack
+        frame, push the retrieved value onto the stack.
+        """
+
+        n = self.load(self.pc + 1)
+        self.push(self.value_stack[self.current_frame + n])
+        self.pc += 2
+
+    def SPF(self):
+
+        """
+        SPF #n
+        Save to position n in frame: pull a value from the stack and set it as
+        position n in the current stack frame.
+        """
+
+        n = self.load(self.pc + 1)
+        self.value_stack[self.current_frame + n] = self.pull()
+        self.pc += 2
+
+    def LRM(self):
+
+        """
+        LRM #addr
+        Load the reference to memory: get the address addr, push the value onto
+        the stack.
+
+        This is useful for loading constants.
+        """
+
+        addr = self.load(self.pc + 1)
+        self.push(addr)
+        self.pc += 2
+
+    def LAM(self):
+
+        """
+        LAM addr
+        Load from address addr in memory: get the contents of address addr from
+        memory, push the retrieved value onto the stack.
+
+        This is useful for loading globals.
+        """
+
+        addr = self.load(self.pc + 1)
+        self.push(self.load(addr))
+        self.pc += 2
+
+    def SAM(self):
+
+        """
+        SAM addr
+        Save to address addr in memory: pull a value from the stack and save it
+        to address addr in memory.
+
+        This is useful for saving globals.
+        """
+
+        addr = self.load(self.pc + 1)
+        self.save(addr, self.pull())
+        self.pc += 2
+
+    def LPR(self):
+
+        """
+        LPR #n
+        Load from position n in reference: get the contents of position n in the
+        memory referenced by the value on the top of the stack, replacing the
+        value on the top of the stack with the retrieved value.
+        """
+
+        n = self.load(self.pc + 1)
+        ref = self.pull()
+        self.push(self.load(ref + n))
+        self.pc += 2
+
+    def SPR(self):
+
+        """
+        SPR #n
+        Save to position n in reference: pull a value from the stack and save it
+        to position n in the memory referenced by the next value on the stack,
+        also removing the next value on the stack.
+        """
+
+        n = self.load(self.pc + 1)
+        value = self.pull()
+        self.save(self.pull() + n, value)
+        self.pc += 2
+
+    def JAS(self):
+
+        """
+        JAS addr
+        Jump to address addr to invoke a subroutine: store the location of the
+        next instruction on the PC stack, set the address addr in the PC.
+        """
+
+        addr = self.load(self.pc + 1)
+        self.jump(addr, self.pc + 2)
+
+    def RAC(self):
+
+        """
+        RAC
+        Return to the address of the caller: pull a value from the PC stack and
+        set it in the PC.
+        """
+
+        self.pc = self.pull_pc()
+
+    def JAT(self):
+
+        """
+        JAT addr
+        Jump to address addr if true: pull a value from the stack and if it
+        represents a true value, jump to address addr.
+        """
+
+        addr = self.load(self.pc + 1)
+        value = self.pull()
+        if value:
+            self.pc = addr
+        else:
+            self.pc += 2
+
+    def JAF(self):
+
+        """
+        JAF addr
+        Jump to address addr if false: pull a value from the stack and if it
+        represents a false value, jump to address addr.
+        """
+
+        addr = self.load(self.pc + 1)
+        value = self.pull()
+        if not value:
+            self.pc = addr
+        else:
+            self.pc += 2
+
+    # Library functions.
+
+    def rsvp___printnl(self):
+        print self.load(self.value_stack[-1])
+
+    def rsvp___print(self):
+        print self.load(self.value_stack[-1]),
+
+    def int_____gt__(self):
+        self.push(self.load(self.value_stack[-2]) > self.load(self.value_stack[-1]))
+
+    def int_____sub__(self):
+        result = self.load(self.value_stack[-2]) - self.load(self.value_stack[-1])
+        addr = self.new(1)
+        self.push(addr)
+        self.save(addr, result)
+
+    def int_____mul__(self):
+        result = self.load(self.value_stack[-2]) * self.load(self.value_stack[-1])
+        addr = self.new(1)
+        self.push(addr)
+        self.save(addr, result)
+
+class RSVPAssembler:
+
+    "An assembler for RSVP code."
+
+    def __init__(self, debug=0):
+
+        "Initialise the assembler."
+
+        self.memory = []
+        self.label_users = {}
+        self.labels = {}
+        self.debug = debug
+
+    def add(self, value, data=None):
+
+        "Add the given 'value' and optional 'data' to the program."
+
+        if self.debug:
+            if data is None:
+                print value
+            else:
+                print value, data
+
+        self.memory.append(value)
+        if data is not None:
+            if isinstance(data, str) and data.startswith("$"):
+                label_user = len(self.memory)
+
+                # Where a label exists, write an absolute address.
+
+                if self.labels.has_key(data):
+                    self.memory.append(self.labels[data])
+
+                # Otherwise, add a placeholder value.
+
+                else:
+                    self.memory.append(None)
+
+                # Add the label "user" for relocation purposes.
+
+                if not self.label_users.has_key(data):
+                    self.label_users[data] = []
+                self.label_users[data].append(label_user)
+
+            else:
+                self.memory.append(data)
+
+    def add_many(self, *instructions):
+        for instruction in instructions:
+            self.add(*instruction)
+
+    def label(self, name, value=None):
+
+        """
+        Define the label with the given 'name'. If the optional 'value' is
+        specified, associate the label with 'value'; otherwise, associate it
+        with the next position in the program.
+        """
+
+        if self.debug:
+            if value is None:
+                print name
+            else:
+                print name, "at", value
+
+        if value is None:
+            value = len(self.memory)
+
+        self.labels[name] = value
+        for user in self.label_users.get(name, []):
+            self.memory[user] = value
+
+    def add_labels(self, labels, label_users, offset):
+
+        """
+        Add the given 'labels' and 'label_users' to the program, with the
+        label definitions and users adjusted by the given 'offset'.
+        """
+
+        for name, users in label_users.items():
+            if not self.label_users.has_key(name):
+                self.label_users[name] = []
+            for user in users:
+                self.label_users[name].append(user + offset)
+                
+        for name, value in labels.items():
+            self.label(name, value + offset)
+
+    def merge(self, assembler):
+
+        "Merge the memory and labels of the given 'assembler' with this one."
+
+        label_base = len(self.memory)
+        self.memory += assembler.memory
+        self.add_labels(assembler.labels, assembler.label_users, label_base)
+
+def dump(memory):
+    for i in range(0, len(memory)):
+        print "%8d %s" % (i, memory[i])
+
+def get_image(*assemblers):
+    merged_assembler = RSVPAssembler()
+    for assembler in assemblers:
+        merged_assembler.merge(assembler)
+    return merged_assembler.memory
+
+def test_fact(n, debug=0):
+
+    """
+    Assemble the classic factorial function:
+    def fact(n):
+        if n > 1:
+            return n * fact(n - 1)
+        else:
+            return 1
+    """
+
+    i_fact = 13
+    i_else = 47
+    i_n = 51
+    i_1 = 52
+    memory = ["SCF", "SCF", "LRM", i_n, "NSF", 1, "JAS", i_fact, "NSF", 1, "JAS", "rsvp___print", "RAC"]
+    memory += ["SCF", "LPF", 1, "LRM", i_1, "NSF", 2, "JAS", "int_____gt__", "JAF", i_else]
+    memory += ["SCF", "LPF", 1,
+        "SCF",
+        "SCF", "LPF", 1, "LRM", i_1, "NSF", 2, "JAS", "int_____sub__",
+        "NSF", 1, "JAS", i_fact,
+        "NSF", 2, "JAS", "int_____mul__",
+        "PSF", "RAC"]
+    memory += ["LRM", i_1, "PSF", "RAC"]
+    memory += [n, 1]
+
+    dump(memory)
+
+    proc = RSVPMachine(memory, debug=debug)
+    proc.execute()
+
+def test_fact2(n, debug=0):
+    main_assembler = RSVPAssembler()
+    main_assembler.add_many(
+        ("SCF",), ("SCF",), ("LRM", "$n"), ("NSF", 1), ("JAS", "$fact"), ("NSF", 1), ("JAS", "rsvp___print"), ("RAC",)
+        )
+
+    fact_assembler = RSVPAssembler()
+    fact_assembler.label("$fact")
+    fact_assembler.add_many(
+        ("SCF",), ("LPF", 1), ("LRM", "$1"), ("NSF", 2), ("JAS", "int_____gt__"), ("JAF", "$else"),
+        ("SCF",), ("LPF", 1),
+        ("SCF",),
+        ("SCF",), ("LPF", 1), ("LRM", "$1"), ("NSF", 2), ("JAS", "int_____sub__"),
+        ("NSF", 1), ("JAS", "$fact"),
+        ("NSF", 2), ("JAS", "int_____mul__"),
+        ("PSF",), ("RAC",)
+        )
+    fact_assembler.label("$else")
+    fact_assembler.add_many(
+        ("LRM", "$1"), ("PSF",), ("RAC",)
+        )
+    fact_assembler.label("$n")
+    fact_assembler.add(n)
+    fact_assembler.label("$1")
+    fact_assembler.add(1)
+
+    memory = get_image(main_assembler, fact_assembler)
+
+    dump(memory)
+
+    proc = RSVPMachine(memory, debug=debug)
+    proc.execute()
+
+def test_empty(debug=0):
+
+    "Test an empty memory."
+
+    try:
+        proc = RSVPMachine([], debug=debug)
+        proc.execute()
+    except IllegalAddress, exc:
+        return exc.args[0] == 0
+
+if __name__ == "__main__":
+    print test_empty()
+    test_fact(3)
+    test_fact2(3)
+
+# vim: tabstop=4 expandtab shiftwidth=4
diff -r ec716eb53281 -r feb9c0c7aa19 simplify/generator.py
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/simplify/generator.py	Mon Aug 06 00:54:45 2007 +0200
@@ -0,0 +1,166 @@
+#!/usr/bin/env python
+
+"""
+Generate RSVP code from simplified nodes.
+
+Copyright (C) 2007 Paul Boddie <paul@boddie.org.uk>
+
+This program is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free Software
+Foundation; either version 3 of the License, or (at your option) any later
+version.
+
+This program is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
+details.
+
+You should have received a copy of the GNU General Public License along with
+this program.  If not, see <http://www.gnu.org/licenses/>.
+"""
+
+from simplify.simplified import *
+import rsvp
+
+# Classes.
+
+class Generator(Visitor):
+
+    "An RSVP code generator."
+
+    def __init__(self):
+
+        "Initialise the visitor."
+
+        Visitor.__init__(self)
+        self.assemblers = []
+        self.current_assemblers = []
+
+        # Satisfy visitor issues.
+
+        self.visitor = self
+
+    def get_code(self):
+        return rsvp.get_image(*self.assemblers)
+
+    def assembler(self):
+        return self.current_assemblers[-1]
+
+    def process(self, module):
+
+        """
+        Process the given 'module', creating RSVP assemblers to store code and
+        data.
+        """
+
+        self.module = module
+
+        main = rsvp.RSVPAssembler(1)
+        self.current_assemblers.append(main)
+
+        # Store constants.
+
+        for name, const in module.simplifier.constants.items():
+            main.label("const$%s$%s" % (self.module.name, name))
+            main.add(const.value)
+
+        # Reserve the namespace.
+
+        for name in module.namespace.keys():
+            main.label("global$%s$%s" % (self.module.name, name))
+            main.add(None)
+
+        # Generate subprograms.
+
+        for subprogram in module.simplifier.subprograms:
+            if not subprogram.internal:
+
+                # Generate specific subprograms.
+
+                for specialisation in subprogram.specialisations():
+                    self.process_subprogram(specialisation)
+
+        # Generate the initialisation.
+
+        self.dispatch(module)
+
+        # Remember the assembler used.
+
+        self.current_assemblers.pop()
+        self.assemblers.append(main)
+
+    def default(self, node, *args):
+        if hasattr(node, "code"):
+            self.dispatches(node.code)
+
+    def visitInvoke(self, invoke):
+
+        "Process the given 'invoke' node."
+
+        sub = self.assembler()
+
+        # NOTE: Generate arguments in a way compatible with subprogram
+        # NOTE: consumption as parameters.
+
+        for subprogram in invoke.invocations:
+
+            # NOTE: Generate switch table.
+
+            # Reserve the namespace.
+
+            params = subprogram.paramtypes.keys()
+            nparams = len(params)
+            if not invoke.share_locals:
+                sub.add("NSF", nparams)
+
+            sub.add("JAS", subprogram.full_name())
+
+            if not invoke.share_locals:
+                sub.add("PSF") # previous stack frame
+
+    visitInvokeFunction = visitInvoke
+    visitInvokeRef = visitInvoke
+
+    def visitModule(self, module):
+
+        "Process the given 'module'."
+
+        self.dispatches(module.code)
+
+    def visitSubprogram(self, subprogram):
+
+        "Process the 'subprogram'."
+
+        if subprogram.internal:
+            self.process_subprogram(subprogram)
+
+    def process_subprogram(self, subprogram):
+
+        sub = rsvp.RSVPAssembler(1)
+        self.current_assemblers.append(sub)
+
+        sub.label("sub$%s$%s" % (self.module.name, subprogram.full_name()))
+
+        locals = subprogram.namespace.keys()
+        params = subprogram.paramtypes.keys()
+        nparams = len(params)
+        non_params = len(locals) - nparams
+
+        if non_params > 0:
+            sub.add("ESF", non_params) # extend stack frame for locals
+
+        # Produce the standard end of subprogram return.
+
+        sub.add("RAC") # return
+
+        self.current_assemblers.pop()
+        self.assemblers.append(sub)
+
+# Convenience functions.
+
+def generate(module):
+    generator = Generator()
+    generator.process(module)
+    return generator.get_code()
+
+# vim: tabstop=4 expandtab shiftwidth=4