Interpreters versus Compilers

In the world of programming languages you have languages that are interpreted, and ones that are compiled. A compiled language takes your input source and does the scanning, parsing, and analyzing phases like you've done here. A compiler then "emits" machine code based on this analysis by walking it and writing the bytes that a real computer (or fake one) needs to run the CPU. Some compilers add an additional step of translating the input source code to an "intermediate language" that is generic enough to then compile down to bytes for the machine. Compilers are normally identified because you typically can't just run them, but first you have to run the source through the compiler, then execute the result. C is a classic compiler, and you run a C program like this:

$ cc ex1.c -o ex1
$ ./ex1

The cc command is the "c compiler", and you're saying take the ex1.c file, scan, parse, and analyze it, then output the executable bytes to the ex1 file. Once you do that you then just run it like you would any other program.

An interpreter doesn't produce compiled bytecode that you run, but instead it just runs the result of the analysis directly. It is "interpreting" the input language the same way a bi-lingual person might interpret my English to my friend's Thai. It loads the source file, then scans, parses, and analyzes it just like a compiler does. Then it simply uses the interpreter's own language (in this case, Python) to run it based on the analysis.

If we were to implement a JavaScript interpreter in Python we would be interpreting "JavaScript with Python". JavaScript is my English, and an interpreter is interpreting it into Python (Thai) for me on the fly. If I wanted to interpret 1 + 2 from JavaScript using Python, I might do it like this:

1. Scan 1 + 2 and produce tokens INT(1) PLUS INT(2).
2. Parse that into an expression AddExpr(IntExpr(1), IntExpr(2).
3. Analyze that to convert the text 1 and 2 into actual Python integers.
4. Interpret that with the Python code result = 1 + 2, which I can pass to the rest of the parse tree.

By comparison, a compiler would do everything I did with 1-3, but then at 4 it would write bytecode (machine code) to another file, which I can then run on the CPU.

Python Is Both

Python is a bit more modern and takes advantage of faster computers by almost doing both compilation and interpretation. It will work like an interpreter so you don't have to go through a compilation phase. But, interpreters are notorioiusly slow, so Python has an internal virtual machine of sorts. When you run a script like python ex1.py, Python actually runs it and compiles that to a ex1.cpython-36.pyc file in the __pycache__ directory. That file is bytecode that the python program knows how to load and run, and it works kind of like fake machine code.

Your interpreter will never, and should never, be that fancy. Yours should just scan, parse, analyze, and interpret the Puny Python script.

How to Write an Interpreter

When you write an interpreter you are going to need to work between all three stages to fix things you missed or got wrong. I suggest that you get adding numbers to work first, then work on more complicated expressions until your script runs. I would appraoch it like this:

1. Add your first interpret method to the AddExpr class and have it just print out a message.
2. Get your Interpreter to visit this class reliably, passing in the PunyPyWorld it needs.
3. Once you've got that you can get the AddExpr.interpret to do the job of calculating the addition of its two expressions and returning the result.
4. After that you then have to figure out where the results of this interpret step should go. To keep things simple, let's assume Puny Python is an expression-based language, so everything returns a value. In that case, calls to one interpreter always have a return that parent calls can use.
5. Finally, since Puny Python is expression-based, you can have your Interpreter print out the final result of its interpret call.

If you do that, you'll have the basics of your Interpreter, and you can start to implement all the other interpret methods you need to make this run.

Exercise Challenge

Writing the Interpreter for Puny Python should involve nothing more than writing another visitor pattern that goes through the analyzed parse tree doing what the parse tree says to do. Your only goal is to get this one tiny (puny even) script to run. That seems stupid since this is just three lines of code, but it is three lines that covers a wide range of topics in programming languages: variables, addition, expression, function definitions, and function calls. If you implement if-statements you'd almost have a working programming language.

Your job is to write a PunyPyInterpreter class that takes the PunyPyWorld and the results of running PunyPyAnalyzer to execute the script. You're going to have to implement print as simply something that prints its variables, but the rest of the code should be something you run as you go through each production class.

Study Drills

1. Once you have a PunyPyInterpreter, you should implement if-statements and boolean expressions and then expand your set of language tests to make sure this works. Try to push this little Python interpreter as far as you can go.
2. What would it take to make Puny Python have statements too?

Further Study

You should be able to now study the grammars and specifications for as many languages as you like. Go ahead and find some languages and study them, but do it using the source code to the language. You should also do a more complete study of the IETF ABNF specification at https://tools.ietf.org/html/rfc5234 to prepare you for the next two exercises.