The last two days I’ve helped Walid with one of his projects. He argues that staged interpreters, i.e. interpreters in which some of the work is done before runtime, drastically outperform simple interpreters, and has strong evidence for this claim. However, some people have been saying that the advantages of staging disappear when the interpreter is optimized using a JIT compiler. Walid asked me to help him show that his claims are true by writing an interpreter in Java and timing programs interpreted by it and programs that correspond to the staged versions.
While this is conceivably possible that JIT compilers make staging unnecessary, anyone who has written an interpreter with today’s compilers knows that the optimizations a JIT compiler can make are on a far lower level of reasoning. Up until about eight years ago, when I was still involved in game development, I wrote assembly code by hand and often won against the compiler; nowadays, I don’t bother with assembly. On the small scale, at the assembly language level, compilers typically outperform anything I could write by hand. But compilers still cannot prevent me from computing something in a profoundly stupid way; it’ll just be a slick, optimized profoundly stupid way. Compilers have not made optimization by humans obsolete, they have only raised the level at which humans need to think.
The program wasn’t hard to write; it was probably easier than the interpreters written in COMP 311. Since we wanted the Java interpreter to correspond as closely as possible to an OCaml interpreter that Walid had already used for timing, some structures were a little bit peculiar.
The resulting program also feels like a weird blend of object-oriented, functional, and procedural programming, but I was gunning for similarity and simplicity. For example, everything is contained in one big file, with nested classes of course. Many helper functions are static, but since I don’t think I’ll extend and override them, making them dynamic and having to use an instance seemed unnecessary. Finally, I used arrays; I initially wrote a version with a functional first-rest-style list and a visitor pattern, which allowed me to imitate the OCaml match more closely, but I decided creating the lists was too verbose and could actually be seen as “non-traditional Java style” and used to dismiss the timings.
Right now, I believe the interpreter is very close to standard Java usage, and even though I didn’t profile or try to optimize it, I don’t think there is a lot of bloat. The only thing that may be non-standard is the environment: I build a chain of function objects using anonymous inner classes that check for the variable name and return a value if it matches or recur if it doesn’t. Traditional Java programmers would probably have used a java.util.Stack.
Anyway, I need to get back to thinking about schedule generation and to making corrections to my thesis. I just noticed that many of my references (apparently all journal articles) are missing the title of the article; they only have the title of the journal. I guess I’m doing something wrong with bibtex.
