The Interpreter, Chapter 3
The continuing story of one man’s quest to write an interpreter.
There is one very important thing that every language needs: variables. How was our hero going to implement variables?
Before it could use variables, the interpreter had to be able to handle hash tables. Jackson looked online for a hash table library, and found a pretty good one. Unfortunately, it could only map strings to strings. The interpreter was using a dynamically typed system, and it needed to be able to have anything as a key and anything as a value. Despite having no idea how to worked, Jackson was faced with the task of implementing a hash table. And, lo and behold, after twenty minutes of Wikipedia-reading and three hours of struggling with implementations and bugs, a working hash table was born.
But just how good was this implementation? Jackson ran some benchmarks against the string hash table he had found online — his was a mere tenth as fast. He knew he could do better. So he spent the next three days trying to improve the system. As it turned out, his hash function was far too slow. Converting every value to a string and then using a hash function on a string was taking a long time. So he wrote a hash function that could handle different data types. There were more collisions (that is, two different values hashing to the same number), but it was worth it to make the hash function three times faster. At that point, Jackson accepted that it was simply impossible to make a hash table for any value as fast as a hash table for only strings; the program was fast enough.
Next, it was time to implement variables. The interpreter contained a hash table with variable names pointing to actual values. In fact, variables proved surprisingly easy to implement. It only took a couple of hours before they had full functionality.
The program had progressed surprisingly far, but many basic functions — exponentiation and logarithms, among others — still did not work. Floating-point numbers in GMP were insufficient. A supplementary library, MPFR, was added to provide additional support. It had the power to do exponents and logarithms for not just positive integers but for decimals and negative numbers as well. The initial stages were complete.