abstract.py

"""
python3 abstract.py |\
  cat - <(echo "int main() { func(3,4); }") |\
  clang-format - |\
  tee /tmp/foo.c |\
  gcc -O2 -x c -fno-asynchronous-unwind-tables - -o /tmp/foo &&\
    bat --theme=gruvbox-dark /tmp/foo.c &&\
    /tmp/foo
"""

class Op:
    LOAD_CONST = 0
    BINARY_ADD = 1
    RETURN_VALUE = 2
    PRINT_VALUE = 3
    LOAD_ARG = 4


class AbstractVM:
    def run(self, prog):
        i = 0
        while True:
            op, arg = prog[i]
            i += 1
            if op == Op.LOAD_CONST:
                self.push(arg)
            elif op == Op.BINARY_ADD:
                right = self.pop()
                left = self.pop()
                self.push(self.add(left, right))
            elif op == Op.RETURN_VALUE:
                result = self.pop()
                break
            elif op == Op.PRINT_VALUE:
                result = self.top()
                self.print(result)
            elif op == Op.LOAD_ARG:
                value = self.arg(arg)
                self.push(value)
            else:
                raise RuntimeError(f"unknown opcode {op}")
        return self.process(result)


class VM(AbstractVM):
    def __init__(self, args=()):
        self.stack = []
        self.args = args

    def arg(self, idx):
        return self.args[idx]

    def push(self, value):
        self.stack.append(value)

    def top(self):
        return self.stack[-1]

    def pop(self):
        return self.stack.pop()

    def add(self, left, right):
        return left + right

    def print(self, value):
        print(value)

    def process(self, result):
        return result


class Compiler(AbstractVM):
    def __init__(self, args=()):
        self.sym_id = 0
        self.statements = []
        self.env = {}
        self.stack = []
        self.args = args
        self.emit_raw("#include <stdio.h>")
        argdecl = ", ".join(f"int {name}" for name in args)
        self.emit_raw(f"int func({argdecl}) {{")

    def gensym(self):
        name = f"tmp{self.sym_id}"
        self.sym_id += 1
        return name

    def emit_raw(self, code):
        self.statements.append(code)

    def emit(self, code):
        self.emit_raw(code + ";")

    def chase(self, value):
        if isinstance(value, int):
            return value
        if value in self.env:
            value = self.env[value]
        return value

    def push(self, value):
        value = self.chase(value)
        self.stack.append(value)

    def top(self):
        name = self.gensym()
        value = self.chase(self.stack[-1])
        self.env[name] = value
        return name

    def pop(self):
        name = self.gensym()
        value = self.chase(self.stack.pop())
        self.env[name] = value
        return name

    def add(self, left, right):
        left = self.chase(left)
        right = self.chase(right)
        name = self.gensym()
        if isinstance(left, int) and isinstance(right, int):
            result = left + right
            self.env[name] = result
            return name
        self.emit(f"int {name} = {left} + {right}")
        return name

    def arg(self, idx):
        return self.args[idx]

    def print(self, value):
        value = self.chase(value)
        self.emit(f"""printf("%d\\n", {value})""")

    def process(self, result):
        result = self.chase(result)
        self.emit(f"return {result}")
        self.emit_raw("}")
        print("\n".join(self.statements))


# (arg0+arg1) + (1+2) -> (arg0+arg1) + 3
prog = [
    (Op.LOAD_ARG, 0),
    (Op.LOAD_ARG, 1),
    (Op.BINARY_ADD, 0),
    (Op.LOAD_CONST, 1),
    (Op.LOAD_CONST, 2),
    (Op.BINARY_ADD, 0),
    (Op.BINARY_ADD, 0),
    (Op.PRINT_VALUE, 0),
    (Op.RETURN_VALUE, 0),
]

# TODO: Could we easily do the following?
# (arg0+1) + (arg1+2) -> (arg0+arg1) + 3
# prog = [
#     (Op.LOAD_ARG, 0),
#     (Op.LOAD_CONST, 1),
#     (Op.BINARY_ADD, 0),
#     (Op.LOAD_CONST, 2),
#     (Op.LOAD_ARG, 1),
#     (Op.BINARY_ADD, 0),
#     (Op.BINARY_ADD, 0),
#     (Op.PRINT_VALUE, 0),
#     (Op.RETURN_VALUE, 0),
# ]

argnames = ("x", "y")
argvals = (3, 4)
assert len(argnames) == len(argvals)
# VM(args=argvals).run(prog)
Compiler(args=argnames).run(prog)

foo.c

#include <stdio.h>
int func(int x, int y) {
  int tmp2 = x + y;
  int tmp8 = tmp2 + 3;
  printf("%d\n", tmp8);
  return tmp8;
}
int main() { func(3, 4); }