""" An interpreter for a strange word-based language: the program is a list of space-separated words. Most words push themselves on a stack; some words have another action. The result is the space-separated words from the stack. Hello World => 'Hello World' 6 7 ADD => '13' 'ADD' is a special word 7 * 5 = 7 5 MUL => '7 * 5 = 35' '*' and '=' are not special words Arithmetic on non-integers gives a 'symbolic' result: X 2 MUL => 'X*2' Input arguments can be passed on the command-line, and used as #1, #2, etc.: #1 1 ADD => one more than the argument on the command-line, or if it was not an integer, concatenates '+1' You can store back into an (existing) argument index with ->#N: #1 5 ADD ->#1 Braces { } delimitate a loop. Don't forget spaces around each one. The '}' pops an integer value off the stack and loops if it is not zero: { #1 #1 1 SUB ->#1 #1 } => when called with 5, gives '5 4 3 2 1' """ from rpython.rlib.jit import hint, promote, dont_look_inside # # See pypy/doc/jit.txt for a higher-level overview of the JIT techniques # detailed in the following comments. # class Box: # Although all words are in theory strings, we use two subclasses # to represent the strings differently from the words known to be integers. # This is an optimization that is essential for the JIT and merely # useful for the basic interpreter. pass class IntBox(Box): def __init__(self, intval): self.intval = intval def as_int(self): return self.intval def as_str(self): return str(self.intval) class StrBox(Box): def __init__(self, strval): self.strval = strval def as_int(self): return myint(self.strval) def as_str(self): return self.strval def func_add_int(ix, iy): return ix + iy def func_sub_int(ix, iy): return ix - iy def func_mul_int(ix, iy): return ix * iy def func_add_str(sx, sy): return sx + '+' + sy def func_sub_str(sx, sy): return sx + '-' + sy def func_mul_str(sx, sy): return sx + '*' + sy def op2(stack, func_int, func_str): # Operate on the top two stack items. The promotion hints force the # class of each arguments (IntBox or StrBox) to turn into a compile-time # constant if they weren't already. The effect we seek is to make the # calls to as_int() direct calls at compile-time, instead of indirect # ones. The JIT compiler cannot look into indirect calls, but it # can analyze and inline the code in directly-called functions. y = stack.pop() promote(y.__class__) x = stack.pop() promote(x.__class__) try: z = IntBox(func_int(x.as_int(), y.as_int())) except ValueError: z = StrBox(func_str(x.as_str(), y.as_str())) stack.append(z) def interpret(bytecode, args): """The interpreter's entry point and portal function. """ # ------------------------------ # First a lot of JIT hints... # # A portal needs a "global merge point" at the beginning, for # technical reasons, if it uses promotion hints: hint(None, global_merge_point=True) # An important hint: 'bytecode' is a list, which is in theory # mutable. Let's tell the JIT compiler that it can assume that the # list is entirely frozen, i.e. immutable and only containing immutable # objects. Otherwise, it cannot do anything - it would have to assume # that the list can unpredictably change at runtime. bytecode = hint(bytecode, deepfreeze=True) # Now some strange code that makes a copy of the 'args' list in # a complicated way... this is a workaround forcing the whole 'args' # list to be virtual. It is a way to tell the JIT compiler that it # doesn't have to worry about the 'args' list being unpredictably # modified. oldargs = args argcount = promote(len(oldargs)) args = [] n = 0 while n < argcount: hint(n, concrete=True) args.append(oldargs[n]) n += 1 # ------------------------------ # the real code starts here loops = [] stack = [] pos = 0 while pos < len(bytecode): # It is a good idea to put another 'global merge point' at the # start of each iteration in the interpreter's main loop. The # JIT compiler keeps a table of all the times it passed through # the global merge point. It allows it to detect when it can # stop compiling and generate a jump back to some machine code # that was already generated earlier. hint(None, global_merge_point=True) opcode = bytecode[pos] hint(opcode, concrete=True) # same as in tiny1.py pos += 1 if opcode == 'ADD': op2(stack, func_add_int, func_add_str) elif opcode == 'SUB': op2(stack, func_sub_int, func_sub_str) elif opcode == 'MUL': op2(stack, func_mul_int, func_mul_str) elif opcode[0] == '#': n = myint(opcode, start=1) stack.append(args[n-1]) elif opcode.startswith('->#'): n = myint(opcode, start=3) if n > len(args): raise IndexError args[n-1] = stack.pop() elif opcode == '{': loops.append(pos) elif opcode == '}': if stack.pop().as_int() == 0: loops.pop() else: pos = loops[-1] # A common problem when interpreting loops or jumps: the 'pos' # above is read out of a list, so the hint-annotator thinks # it must be red (not a compile-time constant). But the # hint(opcode, concrete=True) in the next iteration of the # loop requires all variables the 'opcode' depends on to be # green, including this 'pos'. We promote 'pos' to a green # here, as early as possible. Note that in practice the 'pos' # read out of the 'loops' list will be a compile-time constant # because it was pushed as a compile-time constant by the '{' # case above into 'loops', which is a virtual list, so the promote(pos) else: stack.append(StrBox(opcode)) return stack def repr(stack): # this bit moved out of the portal function because JIT'ing it is not # very useful, and the JIT generator is confused by the 'for' right now... return ' '.join([x.as_str() for x in stack]) # ------------------------------ # Pure workaround code! It will eventually be unnecessary. # For now, myint(s, n) is a JIT-friendly way to spell int(s[n:]). # We don't support negative numbers, though. @dont_look_inside def myint_internal(s, start=0): if start >= len(s): return -1 res = 0 while start < len(s): c = s[start] n = ord(c) - ord('0') if not (0 <= n <= 9): return -1 res = res * 10 + n start += 1 return res def myint(s, start=0): n = myint_internal(s, start) if n < 0: raise ValueError return n # ------------------------------ def test_main(): main = """#1 5 ADD""".split() res = interpret(main, [IntBox(20)]) assert repr(res) == '25' res = interpret(main, [StrBox('foo')]) assert repr(res) == 'foo+5' FACTORIAL = """The factorial of #1 is 1 { #1 MUL #1 1 SUB ->#1 #1 }""".split() def test_factorial(): res = interpret(FACTORIAL, [IntBox(5)]) assert repr(res) == 'The factorial of 5 is 120' FIBONACCI = """Fibonacci numbers: { #1 #2 #1 #2 ADD ->#2 ->#1 #3 1 SUB ->#3 #3 }""".split() def test_fibonacci(): res = interpret(FIBONACCI, [IntBox(1), IntBox(1), IntBox(10)]) assert repr(res) == "Fibonacci numbers: 1 1 2 3 5 8 13 21 34 55"