The Interpreter, Chapter 1
This is the story of one man, on a quest to write an interpreter. This is a man who did not have the stomach to read The Dragon Book at more than twenty pages per week, but didn’t want to wait until he finished that epic tome. No, this man was far too eager.
This man knew little of interpreters or compilers. He knew that he used them often, but didn’t have a clue as to their inner workings. Armed only with his wits and his trusty K&R, he ventured alone into Compilerland.
Our man, whose name we shall say was Jackson, knew exactly where he wanted to begin. He started by constructing a program capable of performing numerical calculations. But he did not want these numbers to be limited by memory registers. For the first week, he tried building a system capable of performing arbitrary-precision arithmetic using those primitive devices that you know as arrays. Jackson was writing this program in C, so he struggled with the limited scope of his arrays. Soon he overcame this struggle, but to his dismay, his arbitrary-precision arithmetic system was far too slow. It was time to call for backup.
Jackson turned to GMP, the world’s greatest bignum library. With this new ally at his side, he was able to push on into Compilerland.
During the second week, he began constructing the platform for the objects in his interpreter. He was able to simulate dynamic typing by using some structs, unions, and a lot of functions. Before long, Jackson’s program could hold both integers and floats, perform various operations on them, and convert between them.
During the third week, Jackson began externalizing his functions. This was his most difficult step yet. Having functions is one thing. But being able to read in a file and determine which functions you’re supposed to call is an entirely different matter.
Soon, though, our hero triumphed. All the bugs were worked out. He could type in arithmetic, like “3 + 5”, or even more advanced functions, like “10 choose 2” or “4000 factorial”, and it would all evaluate properly — to 8, 45, and a number that I do not have room for here. Perhaps the most significant, he had implemented parentheses by recursively defining them. “(3 + 5) * 2” would become “8 * 2”, which would in turn return 16. It was beautiful.
Our hero’s exciting adventures will continue next week, when he implements strings and arrays!