#! /usr/bin/python3 import dis import operator from opcode import * # ******************************************************** # CS 200 HW #5 DUE Wednesday, 11/8/2023 at 11:59 pm # via gradescope. # ******************************************************** # Name: # Email address: # ******************************************************** # This file may be opened in python 3. # Lines beginning with hashes are comments. # If you are asked to write a procedure, please make sure it has # the specified name, and the specified number and order of arguments. # The names of the formal arguments need not be the same # as in the problem specification. # For each problem, the intended inputs to your procedures # are specified (for example, "positive integers") # and your procedures need not do anything reasonable # for other possible inputs. # You may write auxiliary procedures in addition to # the requested one(s) -- for each of your auxiliary # procedures, please include a comment explaining # what it does, and giving an example or two. # You may also use procedures you have written # elsewhere in this assignment or previous assignments. # They only need to be defined once somewhere within this file. # Reading: # dis module: https://docs.python.org/3.4/library/dis.html # http://aosabook.org/en/500L/a-python-interpreter-written-in-python.html # operator module: https://docs.python.org/3.4/library/operator.html ''' PVM-lite A Python Virtual Machine for a subset of Python. Included in the subset are: - constants - local variables - arithmetic operators - comparison operators - if/then/else - lists, tuples, sets, dictionaries (maps) - slices - unary operators - inplace operators Not included are: - for, while loops - function calls - function arguments - classes - list comprehensions - generators - global variables - lambda expressions ''' # ******************************************************** # ** problem 0 ** (1 easy point) # Replace the number 0 in the definition below to indicate # the number of hours you spent doing this assignment # Decimal numbers (eg, 6.237) are fine. Exclude time # spent reading. def hours(): return 1 # ******************************************************** # ** problem 1 ** (19 points) # The dis module can disassemble a Python function, printing out # the byte codes for the function. For example, given: def s1(): a = 1 return a ''' dis.dis(s1) produces: 91 0 RESUME 0 92 2 LOAD_CONST 1 (1) 4 STORE_FAST 0 (a) 93 6 LOAD_FAST 0 (a) 8 RETURN_VALUE ''' # Write your own version of dis.dis() that produces a dictionary object # containing the following values: # # names: a list of the function's names (the .co_varnames attribute) # consts: a list of the function's constants (the .co_consts attribute) # code: a list of the function's bytecode (the .co_code attribute) # instructions: a list of the sequence of instructions for the function. # # Each instruction list has the following five components # # adjusted line number: index position in the bytecode list # instruction opcode number: opcode from the bytecode list # opname: symbolic name for the opcode # index: if the opcode takes an argument, the numeric index value, else None # argument: if the opcode takes an argument, the value of the argument, else None ''' makeobj(s1) => {'names': ('a',), 'consts': (None, 1), 'code': b'\x97\x00d\x01}\x00|\x00S\x00', 'instructions': [(0, 151, 'RESUME', 0, 0), (2, 100, 'LOAD_CONST', 1, 1), (4, 125, 'STORE_FAST', 0, 'a'), (6, 124, 'LOAD_FAST', 0, 'a'), (8, 83, 'RETURN_VALUE', None, None)]} ''' # Note that makeobj is similar to dis.dis(). You may use dis.dis() # to help test your implementation of makeobj() # # You may also want to use dis.HAVE_ARGUMENT to identify those # opcodes that do and do not take an argument. def makeobj(fun): result = {} names = fun.__code__.co_varnames result['names'] = names consts = fun.__code__.co_consts result['consts'] = consts code = fun.__code__.co_code result['code'] = code codelen = len(code) instructions = [] ## fill in the rest here result['instructions'] = instructions return result # ******************************************************** # ** problem 2 ** (10 points) # We shall now implement an Interpreter class, along the lines # of the reading, which describes a full implementation of the PVM # and has the source code available on github. We encourage you to # avail yourself of that resource. Our implementation is more modest. # Nevertheless, you should try to borrow as much as possible from # "byterun" implementation. Yes, I am telling you to copy / adapt # code from the byterun github file. # We first define a test function that will execute a Python function # using the Interpreter class. def doit(func, debug=True): interpreter = Interpreter(debug) return interpreter.execute(func) # Next we define a bunch of test functions for the Interpreter ## problem 3 - binary arithmetic def s3(): a = 1 return a + 1 def s3a(): a = 1 b = 2 return (a + b) def s3b(): a = 1 b = 2 return (a - b) def s3c(): a = 2 b = 3 return (a ** b) def s3d(): a = 2 b = 3 return (a * b) def s3e(): a = 6 b = 3 return (a / b) def s3f(): a = 7 b = 3 return (a // b) def s3g(): a = 7 b = 3 return (a % b) # returns string append def s3h(): a = "hello" b = " world" return a + b ## problem 4 - comparison operators def s4(): return 1 > 2 def s4a(): return 1 < 2 def s4b(): return 1 <= 2 def s4c(): return 1 == 2 def s4d(): return 1 != 2 def s4e(): return 1 >= 2 ## problem 5 - jump operators def s5(): a = 1 if a > 2: return 1 else: return 2 def s5a(): a = 1 if a == 2: return 1 else: return 2 ## problem 6 - lists, tuples, sets, subscript # returns tuple def s6(): a = 2 b = a << a return b, b % 2 # returns list def s6a(): b = 5 return [b, b % 2] # returns set def s6b(): b = 9 return {b, b % 2} # returns list subscript def s6c(): a = [1,2,3] return a[1] ## problem 7 - slices # returns list slice def s7(): a = [1,2,3,4,5,6] return a[2:-1], a[2:4] # returns string slice def s7a(): a = "hello world" return a[3:-1] # returns dictionary def s7b(): a = 2 b = a ** 2 d = {} d[a] = b return d # dict access def s7c(): x = {} x['a'] = 1 y = x['a'] return y ## problem 8 - unary and inplace operators def s8b(): x = 1 return -x def s8c(): x = -1 return +x def s8d(): x = 1 return not x def s8e(): x = 1 return ~x def s8f(): x = 1 x += 10 return x def s8g(): x = 1 x -= 10 return x def s8h(): x = 1 x *= 10 return x def s8i(): x = 10 x %= 3 return x def s8j(): x = 10 x /= 3 return x def s8k(): x = 32 x <<= 2 return x def s8l(): x = 32 x >>= 2 return x def s8m(): x = 10 x //= 3 return x ## problem 9 - logical binary operators def s9(): a = 2 return a << 3 def s9a(): a = 19 return a >> 3 def s9b(): a = 19 return a & 3 def s9c(): a = 19 return a | 3 def s9d(): a = 19 return a ^ 3 # extra binary operators # binary in def s10(): a = [1,2,3,4,5,6] b = 4 if b in a: return "yes" else: return "no" def s10a(): a = [1,2,3,4,5,6] b = 4 if b not in a: return "yes" else: return "no" # binary is def s10b(): a = [1,2,3,4,5,6] b = 4 if b is a: return "yes" else: return "no" def s10c(): a = [1,2,3,4,5,6] b = 4 if b is not a: return "yes" else: return "no" ## Now we start to define the Interpreter itself. ## The PVM uses a stack to control execution and pass arguments to functions ## and operators. ## The result instance variable will contain the value returned by the function ## The debug flag is used to turn on debugging output. ## The environment instance variable is a dictionary ## containing variable bindings. ## The pc instance variable is the program counter. class Interpreter: def __init__(self, debug = True): self.stack = [] self.result = None self.debug = debug self.environment = {} self.pc = 0 ## The execute method controls the action. ## It first decodes the function using makeobj() which we defined above. ## It sets the program counter (pc) to 0. If the pc becomes ## greater than the number of instructions, the program halts. # ## execute cycles through the instructions, printing them out if debug is True ## Each PVM opcode/opname is defined as a method of the Interpreter class. ## This means that each opname is an attribute of the class and ## can be accessed using getattr(self, instruction). The ## opcode method is called with or without an argument, as appropriate. ## ## When the while() loop finishes, execute returns the result. def execute(self, func): codedict = makeobj(func) self.instructions = codedict["instructions"] self.pc = 0 while (self.pc < len(self.instructions)): each_step = self.instructions[self.pc] ## if debug, print out symbol for comparison operator if self.debug: suffix = '' if each_step[2] == 'COMPARE_OP': suffix = self.COMPARE_OPERATORS_SYMBOLS[each_step[3]] if each_step[2] == 'BINARY_OP': suffix = self.BINARY_OPERATORS_SYMBOLS[each_step[3]] print (each_step, suffix) self.pc += 1 lineno, inst, instruction, index, argument = each_step bytecode_method = getattr(self, instruction) if argument is None: bytecode_method() else: bytecode_method(argument) return self.result ## Note that execute calls makeobj() defined above. ## If your makeobj function is not working correctly, you can still ## debug your execute function by importing the bytecode version of ## makeobj from hw5a.pyc: # ## from hw5a import makeobj # ## We define a few stack operations that are used in implementing ## the opcode methods def top(self): return self.stack[-1] def pop(self): return self.stack.pop() def push(self, *vals): self.stack.extend(vals) def popn(self, n): """Pop a number of values from the value stack. A list of `n` values is returned, the deepest value first. """ if n: ret = self.stack[-n:] self.stack[-n:] = [] return ret else: return [] ## We first implement the opcodes need to execute function s1() ## Write the following methods. ## This is a noop. You do not need to write more code. def RESUME(self,name): pass def STORE_FAST(self, name): val = self.stack.pop() self.environment[name] = val def LOAD_FAST(self, name): pass def LOAD_CONST(self, number): pass ## set result from stack ## set pc to be out of range and thereby halt. def RETURN_VALUE(self): pass # ******************************************************** # ** problem 3 ** (10 points) # Define the following set of binary operators needed to # execute the s3 set of functions. ## binary operators ## ----------------------------------- BINARY_OPERATORS_SYMBOLS = [ '+', '&', '//', '<<' , '@' , '*', '%' , '|' , '**' , '>>' , '-', '/', '^' , '+=' , '&=' , '//=', '<<=', '@=' , '*=' , '%=' , '|=', '**=', '>>=', '-', '/=', '^='] BINARY_OPERATORS = [ operator.add, # 0 + operator.and_, # 1 & operator.floordiv, # 2 // operator.lshift, # 3 << operator.matmul, # 4 @ operator.mul, # 5 * operator.mod, # 6 % operator.or_, # 7 | operator.pow, # 8 ** operator.rshift, # 9 >> operator.sub, # 10 - operator.truediv, # 11 / operator.xor, # 12 ^ operator.iadd, # 13 += operator.iand, # 14 &= operator.ifloordiv, # 15 //= operator.ilshift, # 16 <<= operator.imatmul, # 17 @= operator.imul, # 18 *= operator.imod, # 19 %= operator.ior, # 20 |= operator.ipow, # 21 **= operator.irshift, # 22 >>= operator.isub, # 23 -= operator.itruediv, # 24 /= operator.ixor # 25 ^= ] def BINARY_OP(self, opnum): pass # ******************************************************** # ** problem 4 ** (10 points) # Define the set of comparison operators needed to # execute the s4 set of functions. ## comparison operators ## ----------------------------------- COMPARE_OPERATORS_SYMBOLS = [ '<', '<=', '==', '!=', '>', '>=', 'in', 'not in', 'is', 'is not', 'sublclass'] COMPARE_OPERATORS = [ operator.lt, operator.le, operator.eq, operator.ne, operator.gt, operator.ge, lambda x, y: x in y, lambda x, y: x not in y, lambda x, y: x is y, lambda x, y: x is not y, lambda x, y: issubclass(x, Exception) and issubclass(x, y), ] def COMPARE_OP(self, opnum): pass # ******************************************************** # ** problem 5 ** (10 points) # Define the set of jump operators needed to # execute the s5 set of functions. Some are given. ## jumps ## ----------------------------------- ## This method is called by the other jump methods. ## It causes the given address to be the next ## instruction to execute def jump(self, address): pass def JUMP_FORWARD(self, jump): self.jump(jump) def JUMP_ABSOLUTE(self, jump): self.jump(jump) def JUMP_IF_TRUE(self, jump): pass def JUMP_IF_FALSE(self, jump): pass def POP_JUMP_IF_FALSE(self, jump): pass def POP_JUMP_FORWARD_IF_FALSE(self, jump): pass def JUMP_IF_TRUE_OR_POP(self, jump): pass def JUMP_IF_FALSE_OR_POP(self, jump): pass # ******************************************************** # ** problem 6 ** (10 points) # Define the set of operators needed to build and index # lists, tuples, and sets, and execute the s6 set of functions. def BUILD_TUPLE(self, count): pass def BUILD_LIST(self, count): pass def BUILD_SET(self, count): pass def BINARY_SUBSCR(self): pass ### new bytecode in 3.9 ## Fixed by Ayelet Kalfus, 11/10/21 def LIST_EXTEND(self,count): elts = ((self.popn(2))) self.push(list(elts[count])) def bad_LIST_EXTEND(self,count): elts = self.popn(2) self.push(elts[count]) # ******************************************************** # ** problem 7 ** (10 points) # Define the set of operators needed to implement the slice function # and define the set of operators needed to implement dictionaries # and execute the s7 set of functions. def BUILD_SLICE(self, count): pass def BUILD_MAP(self, size): pass def STORE_MAP(self): pass def STORE_SUBSCR(self): pass ### new bytecode in 3.9 ### see above def xxxLIST_EXTEND(self,count): elts = self.popn(2) self.push(elts[count]) # ******************************************************** # ** problem 8 ** (10 points) # Define the set of operators to implement unary and inplace functions # and execute the s8 set of functions. def UNARY_POSITIVE(self): pass def UNARY_NEGATIVE(self): pass def UNARY_NOT(self): pass def UNARY_INVERT(self): pass ## inplace functions defined above in BINARY_OP # ******************************************************** # ** problem 9 ** (10 points) # Define the set of operators needed to implement the logical binary # operators and execute the s9 set of functions. ## binary operators defined above in BINARY_OP ## ----------------------------------- # ******************************************************** # ** problem 10 ** ?? ### new bytecode in 3.9 def CONTAINS_OP(self,flag): if flag: self.COMPARE_OP(7) else: self.COMPARE_OP(6) ### new bytecode in 3.9 def IS_OP(self,flag): if flag: self.COMPARE_OP(9) else: self.COMPARE_OP(8) # ******************************************************** # ******************************************************** ### test function from google python course ### ======================================= # Provided simple test() function used in main() to print # what each function returns vs. what it's supposed to return. def test(expected, got): if (hasattr(expected, '__call__')): OK = expected(got) else: OK = (got == expected) if OK: prefix = ' OK ' else: prefix = ' X ' print ('%s got: %s expected: %s' % (prefix, repr(got), repr(expected))) # Provided main() calls the above functions with interesting inputs, # using test() to check if each result is correct or not. def main(): print ('hours') print('# is it greater than 0?') test(lambda x: x > 0, hours()) print ('makeobj') test(makeobj(s1),{'names': ('a',), 'consts': (None, 1), 'code': b'\x97\x00d\x01}\x00|\x00S\x00', 'instructions': [(0, 151, 'RESUME', 0, 0), (2, 100, 'LOAD_CONST', 1, 1), (4, 125, 'STORE_FAST', 0, 'a'), (6, 124, 'LOAD_FAST', 0, 'a'), (8, 83, 'RETURN_VALUE', None, None)]} ) print ('s1 - load and store') test(s1(), doit(s1, False)) print ('s3 - binary arithmetic') test(s3(), doit(s3, False)) test(s3a(), doit(s3a, False)) test(s3b(), doit(s3b, False)) test(s3c(), doit(s3c, False)) test(s3d(), doit(s3d, False)) test(s3e(), doit(s3e, False)) test(s3f(), doit(s3f, False)) test(s3g(), doit(s3g, False)) test(s3h(), doit(s3h, False)) print ('s4 - comparison operators') test(s4(), doit(s4, False)) test(s4a(), doit(s4a, False)) test(s4b(), doit(s4b, False)) test(s4c(), doit(s4c, False)) test(s4d(), doit(s4d, False)) test(s4e(), doit(s4e, False)) print ('s5 - jump operators') test(s5(), doit(s5, False)) print ('s6 - lists, tuple, sets, subscript') test(s6(), doit(s6, False)) test(s6a(), doit(s6a, False)) test(s6b(), doit(s6b, False)) test(s6c(), doit(s6c, False)) print ('s7 - slices and dictionaries') test(s7(), doit(s7, False)) test(s7a(), doit(s7a, False)) test(s7b(), doit(s7b, False)) test(s7c(), doit(s7c, False)) print ('s8 - unary and inplace operators') test(s8b(), doit(s8b, False)) test(s8c(), doit(s8c, False)) test(s8d(), doit(s8d, False)) test(s8e(), doit(s8e, False)) test(s8f(), doit(s8f, False)) test(s8g(), doit(s8g, False)) test(s8h(), doit(s8h, False)) test(s8i(), doit(s8i, False)) test(s8j(), doit(s8j, False)) test(s8k(), doit(s8k, False)) test(s8l(), doit(s8l, False)) test(s8m(), doit(s8m, False)) print ('s9 - logical operators') test(s9(), doit(s9, False)) test(s9a(), doit(s9a, False)) test(s9b(), doit(s9b, False)) test(s9c(), doit(s9c, False)) test(s9d(), doit(s9d, False)) print ('s10 - extra binary operators') test(s10(), doit(s10, False)) test(s10a(), doit(s10a, False)) test(s10b(), doit(s10b, False)) test(s10c(), doit(s10c, False)) if __name__ == '__main__': main()