Over the past week, I've been working on a project that works as an interpreter of sorts for bytecodes in a custom language that would run in a "live" environment. It works, in a sense (I don't have a compiler or anything for it yet, just bytecodes for now and a file format, sorry! They are explained in the serializeObjects() function and the Interpreter.interpretOne() function), but I wanted somebody to review my code before it became too complex, that way I can prune out bad coding practices and see how I could optimize my code further. Here's my code:
To try to describe my code, the Object and Pointer classes descend from the QSILObject class (used for type checking), and are the "objects" used in the language (which is entirely object-oriented). They contain a list called directMemory that stores values such as instance variables, or in the case of methods, which are also objects, literals for a method. They also have a dictionary api, for use by the program to store certain kinds of values, such as the object's class.
The file format is a bit harder to explain:
The file starts with a header ("QSIL") and a version number (1)
Then, objects are stored, beginning with the byte \x00 and a 42-bit integer that stores the object's unique id, and ending with byte \x01.
Within the objects, key/value pairs are stored with an initial byte of \x02 and \x03, respectively. If there is no byte indicating that an object is a key or a value, then the object will be added to the
directMemorylist.32-bit integers are stored in a big-endian format, and are indicated by an initial byte of \x04
Doubles are also stored in a big-endian format, and are indicated by an initial byte of \x05
A "Pointer" to an object is stored beginning with byte \x06, a 42-bit integer with the object that is being pointed to's id, and another byte with the value of \x06
A string is stored beginning with byte \x07, and continues reading until the byte \x07 is encountered again. values can be escaped with byte \x08
The bytecodes are as follows:
\x00 - Push the receiver onto the stack
\x01 arg - Push an instance variable onto the stack by index
\x02 arg - Push an argument onto the stack by index
\x03 arg - Push an temporary variable onto the stack by index
\x04 arg - Push an literal value onto the stack by index
\x05 - Send a message to an object
\x06 - Return the previous stack value to the method that send this message
\x07 arg - Jump to the given pc
\x08 arg - Jump to the given pc if the previous stack value is true
\x09 arg - Jump to the given pc if the previous stack value is false
\x0a arg - Pop the last stack value into the given instance variable by index
\x0b arg - Pop the last stack value into the given temporary variable by index
\x0c - pop the last stack value
\x0d arg - Prints the value of the stack by index. Used for testing
\x10 arg - Performs a primitive. Information on this is located in the
Interpreter.doPrimitivemethod
# Quick Self-Interpreting Language (QSIL) import time import threading import struct from io import BytesIO class QSILObject: """ The superclass for QSIL objects. Used for type checking """ class Pointer(QSILObject, object): """ A pointer of sorts to an Object. This has a .yourself property that returns the object it refers to """ def __init__(self, anId): self.id = anId def __repr__(self): return "Pointer({})".format(self.id) @property def yourself(self): return allobjects[self.id] def appendToSet(self, aCollection): aCollection.add(self) def __hash__(self): return id(self) class Object(QSILObject, dict): """ An object exists in memory. It can either be used internally, such as a stack "frame", or exist as a live object in QSIL """ def __init__(self, *args, **kwargs): super(Object, self).__init__(*args, **kwargs) self.id = 0 self.directMemory = [] def __hash__(self): return id(self) def setId(self, anId): self.id = anId def setMem(self, aList): self.directMemory = aList def __repr__(self): initialValue = 'Object({})'.format(super(Object, self).__repr__()) if self.id != 0: initialValue += '.setId({})'.format(self.id) if self.directMemory: initialValue += '.setMem({})'.format(self.directMemory.__repr__()) return initialValue @property def yourself(self): return self def appendToSet(self, aCollection): aCollection.add(self) for key, value in self.items(): if isinstance(value, QSILObject): value.appendToSet(aCollection) for value in self.directMemory: if isinstance(value, QSILObject): value.appendToSet(aCollection) def read(bytesToRead): """ Read all the objects from the given bytes() object """ def peek(length=1): pos = byteStream.tell() ret = byteStream.read(length) byteStream.seek(pos) return ret byteStream = BytesIO(bytesToRead) assert byteStream.read(4) == b'QSIL', "Unknown file format" assert int(byteStream.read(1)) <= 1, "VM too old" def readSomething(): toRead = int(byteStream.read(1)[0]) if toRead == 0x00: return readObject() elif toRead == 0x02: return readAssociation() # elif toRead == 0x03 # Reserved for value in association elif toRead == 0x04: return readInt() elif toRead == 0x05: return readFloat() elif toRead == 0x06: return readPointer() elif toRead == 0x07: return readString() raise ValueError("Unknown type:", toRead) def readFloat(): return struct.unpack('>d', byteStream.read(8))[0] def readInt(): return struct.unpack('>i', byteStream.read(4))[0] def readPointer(): anId = byteStream.read(6) assert byteStream.read(1)[0] == 0x06 return Pointer(anId) def readAssociation(): """Read an association. Used internally""" key = readSomething() assert byteStream.read(1)[0] == 0x03 value = readSomething() return (key, value) def readString(): theCode = b'' while byteStream.tell() < len(byteStream.getvalue()): # Until we reach an "END STRING" marker, keep reading nextChar = byteStream.read(1) if nextChar[0] == 0x07: break elif nextChar[0] == 0x08: nextChar = byteStream.read(1) theCode += nextChar return theCode def readObject(): """Read an object""" currentObj = Object() objId = byteStream.read(6) currentObj.setId(objId) allobjects[objId] = currentObj toRead = None while (byteStream.tell() < len(byteStream.getvalue())): toRead = peek()[0] if toRead == 0x02: # Special handling for associations byteStream.read(1) assoc = readAssociation() currentObj[assoc[0]] = assoc[1] elif toRead == 0x01: break else: toAdd = readSomething() currentObj.directMemory.append(toAdd) byteStream.read(1) # Pop end of object descriptor return currentObj def readObjectNoId(): """Read an object""" currentObj = Object() toRead = None while (byteStream.tell() < len(byteStream.getvalue())): toRead = peek()[0] if toRead == 0x02: # Special handling for associations byteStream.read(1) assoc = readAssociation() currentObj[assoc[0]] = assoc[1] elif toRead == 0x01: break else: toAdd = readSomething() currentObj.directMemory.append(toAdd) byteStream.read(1) # Pop end of object descriptor return currentObj def readStack(): newContext = Object() if byteStream.read(2) == b'ST': # Read a new context. Otherwise, return a blank one newContext['pc'] = readInt() newContext['method'] = readPointer() newContext['receiver'] = readPointer() assert byteStream.read(1)[0] == 0x00 newContext['args'] = readObjectNoId() assert byteStream.read(1)[0] == 0x00 newContext['tempvars'] = readObjectNoId() assert byteStream.read(1)[0] == 0x00 newContext['stack'] = readObjectNoId() newContext['homeContext'] = readStack() # Nested contexts... return newContext while byteStream.tell() < len(byteStream.getvalue()) and peek()[0] == 0x00: byteStream.read(1) readObject() assert byteStream.read(3) == b'\xab\xcd\xef', "No entry context" interp.setContext(readStack()) def rehashObjects(): """Create a new unique id for every object. Make sure to update all pointers to each object.""" global allobjects minId = newId = 0 # Id to start with hashMap = {} newAllObjects = {} uniqueobjects = set() def store_48bitInt(intToStore): """Return the bytes for storage of a 48-bit integer""" if intToStore < -140737488355328 or intToStore >= 140737488355328: raise ValueError("Outside 48-bit integer range") if intToStore < 0: finalInt = 281474976710656 + intToStore else: finalInt = intToStore def digitAt(theInt, toFind): if toFind > 6: return 0 if theInt < 0: return (0 - theInt >> ((toFind - 1) * 8)) & 0xFF return theInt >> ((toFind - 1) * 8) & 0xFF return bytes([digitAt(intToStore, x) for x in range(6, 0, -1)]) for oldid, theObject in allobjects.items(): theObject.appendToSet(uniqueobjects) for theObject in uniqueobjects: if sum(c << (i * 8) for i, c in enumerate(theObject.id[::-1])) < minId: continue # Do not change the ID for this object if theObject.id in hashMap: theObject.id = hashMap[theObject.id] else: hashMap[theObject.id] = store_48bitInt(newId) theObject.id = store_48bitInt(newId) newId += 1 if isinstance(theObject, Object): newAllObjects[theObject.id] = theObject uniqueobjects = set() interp.saveToContext() thisContext = interp.activeContext while 'pc' in thisContext: thisContext.appendToSet(uniqueobjects) for anObject in thisContext.directMemory: if isinstance(anObject, QSILObject): anObject.appendToSet(uniqueobjects) thisContext = thisContext['homeContext'] uniqueobjects = [x for x in uniqueobjects if not isinstance(x.id, int)] for theObject in uniqueobjects: if sum(c << (i * 8) for i, c in enumerate(theObject.id[::-1])) < minId: continue # Do not change the ID for this object theObject.id = hashMap[theObject.id] interp.readFromContext() allobjects = newAllObjects class Interpreter(object): """ The interpreter interprets the bytecodes that QSIL runs on. """ def __init__(self): self.pc = 0 self._method = None self._receiver = None self.activeContext = None self.args = [] self.tempvars = [] self._stack = [] def setContext(self, aContextObject): self.activeContext = aContextObject self.readFromContext() def popContext(self): """ Return to the previous context. Make sure to set all the state variables """ oldContext = self.activeContext self.activeContext = oldContext['homeContext'] self.setContext(self.activeContext) def pushContext(self, aContextObject): """ Push a new context object. Make sure that that context's parent is set to the current context and store all state variables """ oldContext = self.activeContext aContextObject['homeContext'] = oldContext self.saveToContext() self.setContext(aContextObject) def saveToContext(self): # Save all the state variables to the context. # Method and receiver don't change in context self.activeContext['pc'] = self.pc self.activeContext['args'] = self.args self.activeContext['tempvars'] = self.tempvars self.activeContext['stack'] = self._stack self.activeContext['method'] = self._method self.activeContext['receiver'] = self._receiver def readFromContext(self): self.pc = self.activeContext['pc'] self.args = self.activeContext['args'] self.tempvars = self.activeContext['tempvars'] self._stack = self.activeContext['stack'] self._receiver = self.activeContext['receiver'] self._method = self.activeContext['method'] @property def method(self): return self._method.yourself @property def receiver(self): return self._receiver.yourself @property def stack(self): return self._stack.yourself.directMemory def doPrimitive(self, primByte): r""" Perform a single primitive. # \x00 - integer add # \x01 - integer subtract # \x02 - integer multiply # \x03 - integer division # \x04 - integer comparison # \x05 - integer bitshift left # \x06 - integer bitshift right """ if primByte == 0x00: # Primitive integer add arg2 = self.stack.pop() arg1 = self.stack.pop() self.stack.append(arg1 + arg2) elif primbyte == 0x01: # Primitive integer subtract arg2 = self.stack.pop() arg1 = self.stack.pop() self.stack.append(arg1 - arg2) elif primbyte == 0x02: # Primitive integer multiply arg2 = self.stack.pop() arg1 = self.stack.pop() self.stack.append(arg1 * arg2) elif primbyte == 0x03: # Primitive integer division arg2 = self.stack.pop() arg1 = self.stack.pop() self.stack.append(arg1 / arg2) elif primbyte == 0x04: # Primitive integer comparison arg2 = self.stack.pop() arg1 = self.stack.pop() if arg1 < arg2: self.stack.append(-1) elif arg1 == arg2: self.stack.append(0) else: self.stack.append(1) elif primbyte == 0x05: # Bitshift left arg2 = self.stack.pop() arg1 = self.stack.pop() self.stack.append(arg1 << arg2) elif primbyte == 0x06: # Bitshift right arg2 = self.stack.pop() arg1 = self.stack.pop() self.stack.append(arg1 >> arg2) def interpretOne(self): r""" Interpret a single bytecode. # QSIL Bytecode Manual # \x0_ - Stack Access # \x00 - pushRcvr # \x01 [0] - pushInst: [0] # \x02 [0] - pushArg: [0] # \x03 [0] - pushTemp: [0] # \x04 [0] - pushLiteral: [0] # \x05 - send # \x06 - returnTop # \x07 [0] - jump: [0] # \x08 [0] - jumpIfTrue: [0] # \x09 [0] - jumpIfFalse: [0] # \x0a [0] - popIntoInst: [0] # \x0b [0] - popIntoTemp: [0] # \x0c - pop # \x0d [0] - debugStack: [0] # \x1_ - Primitive Access # \x10 [0] - doPrim: [0] """ nextByte = self.method.directMemory[0][self.pc] if nextByte >= 0x00 and nextByte < 0x10: # Stack Access if nextByte == 0x00: # pushRcvr self.stack.append(Pointer(self.receiver.id)) elif nextByte == 0x01: # pushInst: [0] self.pc += 1 argN = self.method.directMemory[0][self.pc] self.stack.append(self.receiver.directMemory[argN]) elif nextByte == 0x02: # pushArg: self.pc += 1 argN = self.method.directMemory[0][self.pc] self.stack.append(self.args.directMemory[argN]) elif nextByte == 0x03: # pushTemp: self.pc += 1 argN = self.method.directMemory[0][self.pc] self.stack.append(self.tempvars.directMemory[argN]) elif nextByte == 0x04: # pushLiteral: self.pc += 1 argN = self.method.directMemory[0][self.pc] self.stack.append(self.method.directMemory[argN + 1]) elif nextByte == 0x05: # send messageName = self.stack.pop() receiver = self.stack.pop() message = receiver.yourself[b'methods'].yourself[messageName] newContext = Object() newContext['pc'] = 0 newContext['method'] = Pointer(message.id) newContext['receiver'] = Pointer(receiver.id) newContext['args'] = Object() newContext['tempvars'] = Object() newContext['stack'] = Object() for arg in range(len(messageName.split(b':')) - 1): newContext['args'].directMemory.append(self.stack.pop()) newContext['args'].directMemory.reverse() self.pushContext(newContext) return elif nextByte == 0x06: # returnTop returnValue = self.stack.pop() self.popContext() self.stack.append(returnValue) elif nextByte == 0x07: # jump: self.pc += 1 argN = self.method.directMemory[0][self.pc] self.pc = argN - 1 # Minus one because we increment after this elif nextByte == 0x08: # jumpIfTrue: self.pc += 1 toCheck = self.stack.pop() argN = self.method.directMemory[0][self.pc] if toCheck: self.pc = argN - 1 elif nextByte == 0x09: # jumpIfFalse: self.pc += 1 toCheck = self.stack.pop() argN = self.method.directMemory[0][self.pc] if not toCheck: self.pc = argN - 1 elif nextByte == 0x0a: # popIntoInst: toPush = self.stack.pop() self.pc += 1 argN = self.method.directMemory[0][self.pc] self.receiver.directMemory[argN] = toPush elif nextByte == 0x0b: # popIntoTemp: toPush = self.stack.pop() self.pc += 1 argN = self.method.directMemory[0][self.pc] self.tempvars[argN] = toPush elif nextByte == 0x0c: # pop self.stack.pop() elif nextByte == 0x0d: # debugStack: self.pc += 1 argN = self.method.directMemory[0][self.pc] print(self.stack[argN]) elif nextByte >= 0x10 and nextByte < 0x20: # Primitive Access if nextByte == 0x10: # doPrim: self.pc += 1 nextByte = self.method.directMemory[0][self.pc] self.doPrimitive(nextByte) else: raise ValueError("Unknown bytecode: %s", nextByte) self.pc += 1 def serializeObjects(): r""" Serialize all the objects and return a bytes() object that can be used to load an exact copy of the current environment # File format: # \x00 - start object (id is next 6 chars) # \x01 - end object # \x02 - start/end object key # \x03 - start/end object value # \x04 - start int (32 bit) # \x05 - start float (actually a double) # \x06 - start/end pointer # \x07 - start/end string # (\x08) - escape next character """ aStream = BytesIO() def writeSomething(anObject, printId=True): if isinstance(anObject, Pointer): aStream.write(b'\x06') aStream.write(anObject.id) aStream.write(b'\x06') elif isinstance(anObject, Object): aStream.write(b'\x00') if printId: aStream.write(anObject.id) for key, value in anObject.items(): aStream.write(b'\x02') # Begin key writeSomething(key, printId) aStream.write(b'\x03') # Begin value writeSomething(value, printId) for aMemoryObject in anObject.directMemory: writeSomething(aMemoryObject, printId) aStream.write(b'\x01') elif isinstance(anObject, int): aStream.write(b'\x04') aStream.write(struct.pack('>i', anObject)) elif isinstance(anObject, float): aStream.write(b'\x05') aStream.write(struct.pack('>d', anObject)) elif isinstance(anObject, (str, bytes)): aStream.write(b'\x07') toWrite = b'' for char in anObject: if char == 0x07: toWrite += bytes([0x08]) toWrite += bytes([char]) aStream.write(toWrite) aStream.write(b'\x07') aStream.write(b'QSIL1') for anId, anObject in allobjects.items(): writeSomething(anObject) aStream.write(b'\xab\xcd\xef') def writeContext(anObject): if 'pc' in anObject: aStream.write(b'ST') # Context bytes aStream.write(struct.pack('>i', anObject['pc'])) # Encode pc aStream.write(anObject['method'].id) aStream.write(b'\x06') # End pointer aStream.write(anObject['receiver'].id) aStream.write(b'\x06') # End pointer writeSomething(anObject['args'], False) writeSomething(anObject['tempvars'], False) writeSomething(anObject['stack'], False) writeContext(anObject['homeContext'].yourself) else: # Write a blank object aStream.write(b'\x00') interp.saveToContext() # Force a write of interpreter state variables writeContext(interp.activeContext.yourself) return aStream.getvalue() allobjects = {} interp = Interpreter() starterBytes = (b'QSIL1' # File header b'\x00' # Start object 1 b'\x00\x00\x00\x00\x00\x00' # Object id (42-bit zero) b'\x07' # Begin string (bytecodes) b'\x00' # Push rcvr b'\x04\x01' # Push lit 1 b'\x05' # Send b'\x0d\x00' # Debug stack 0 b'\x0c' # Pop b'\x08\x07\x00' # Jump to pc 0 b'\x07' # End string (bytecodes) b'\x06' # Pointer to message receiver b'\x00\x00\x00\x00\x00\x01' # ID of receiver (lit 0) b'\x06' # End pointer to message receiver b'\x07' # Begin string b'doTestTwo' # Message to send (lit 1) b'\x07' # End string b'\x01' # End object 1 b'\x00' # Start object 2 b'\x00\x00\x00\x00\x00\x09' # Object id (42-bit nine) b'\x07' # Begin string (bytecodes) b'\x04\x00' # Push lit 0 b'\x01\x00' # Push inst var 0 b'\x10\x00' # Primitive: 0x00 (Int. Addition) b'\x0a\x00' # Pop to instance var 0 b'\x01\x00' # Push inst var 0 b'\x06' # Return b'\x07' # End string (bytecodes) b'\x04' # Begin literal 0 (int) b'\x00\x00\x00\x01' # Number (1) b'\x01' # End object 2 b'\x00' # Start object 2 (receiver for test code) b'\x00\x00\x00\x00\x00\x01' # Object id (42-bit one) b'\x02' # Start key b'\x07' # Begin string b'superclass' b'\x07' # End string b'\x03' # Begin value b'\x06' # Begin pointer to class (OBJECT, with no superclass) b'\x00\x00\x00\x00\x00\x01' b'\x06' # End pointer b'\x02' # Start key b'\x07' # Begin string b'className' b'\x07' # End string b'\x03' # Begin value b'\x07' # Begin string (This is the OBJECT class) b'object' b'\x07' # End pointer b'\x02' # Start key b'\x07' # Begin string b'methods' b'\x07' # End string b'\x03' # Begin value b'\x06' # Begin pointer b'\x00\x00\x00\x00\x00\x02' b'\x06' # End pointer # Instance variable 0 b'\x04' # Begin int b'\x00\x00\x00\x00' # Number (0) b'\x01' # End object 2 (receiver for test code) b'\x00' # Begin object (array of methods with pointers) b'\x00\x00\x00\x00\x00\x02' # Object id (42-bit two) b'\x02' # Start key b'\x07' # Begin string b'doTest' b'\x07' # End key b'\x03' # Begin value b'\x06' # Begin pointer to method b'\x00\x00\x00\x00\x00\x00' b'\x06' # End pointer to method b'\x02' # Start key b'\x07' # Begin string b'doTestTwo' b'\x07' # End key b'\x03' # Begin value b'\x06' # Begin pointer to method b'\x00\x00\x00\x00\x00\x09' b'\x06' # End pointer to method b'\x01' # End object (array of methods with pointers) b'\xab\xcd\xef' # Separator for live memory b'ST' # Context bytes. Means that there is a context to read b'\x00\x00\x00\x00' # pc b'\x00\x00\x00\x00\x00\x00' # ID of method b'\x06' # End pointer to method b'\x00\x00\x00\x00\x00\x01' # ID of receiver b'\x06' # End pointer to receiver b'\x00' # Begin args object b'\x01' # End args object b'\x00' # Begins tempVars object b'\x01' # End tempVars object b'\x00' # Begin stack object b'\x01' # End stack object b'\x00' # Begin final context (blank, no context byte) ) if __name__ == '__main__': try: with open('test.image', 'rb') as b: x = b.read() starterBytes = x read(starterBytes) # Some test code rehashObjects() while True: # This seems redundant, and useless, because this is just # running a function normally, but this is important because # it prevents Control+C from pausing in the middle of an # operation, which helps to prevent corrupted contexts on a # save. When a primitive is added for saving, then this # can be removed. target = threading.Thread(target=interp.interpretOne) target.start() target.join() finally: with open('test.image', 'wb') as b: # This will exist until a primitive is added for saving b.write(serializeObjects()) 
