My Programming Journey Part 2: Calculators led to Parsing led to Programming Languages
Every programmer has a favorite toy problem or smallish program idea that they like to use to try out new tools. For quick testing of GUI tools, mine is a 4-function calculator. This fascination started at an early age, when I was programming QBASIC at the age of 14. I wrote one in 15 lines of code that prompted for the first number, operation and second number. When I moved on to Envelop Basic, I created a GUI calculator with three text boxes, two inputs and one output, with a button for each of the 4 operations.
Then, as my family was traveling from Kansas to Florida in 2011, I was introduced to Petzold’s CODE, and advised that C# would be a good language to pick up for finding jobs. One of my key discoveries working in BASIC during my teenage years was that I had to have a project in mind if I was going to get any programming really done. So I decided that to learn C#, I would build as much of a scientific calculator as I could figure out.
The days I spent pondering this problem were heady and inspirational. My only other general knowledge of the field came from Coders at Work and Head First C#, 2nd Edition. My Googling skills were non-existent. Working on that scientific calculator, I independently discovered how to write integer and decimal (digits and decimal point) parsers, after pondering the problem for a few days. At first, I attempted to convert from math strings into my own assembly-esqe op-code language, but I struggled to handle varying length arguments as I seperated the code from the data into separate arrays.
As I gained comfort with objects and references via my weekly exercises in Head First C#, I also conceived the bare basics of recursive descent parsing and tree-walking evaluation, which allowed me to handle parenthesis, without actually reading a reference on either. At one point, I actually had a calculator that could take strings containing numbers with decimal points, the 4 math operators, and parenthesis, and return a correct result. Then I decided to try and add Square Root.
Now, at the time, my programming research skills were still anemic, and I was still rather ignorant, so rather than using the now-obvious
Math.Sqrt in C#, I began research on how to implement my own. This was about where that project fizzled out, as I ended getting my first software development internship in C# and then had my hands more than full trying to keep up with it. But even though it was never completely finished, it left me with two things: a fascination for parsing, and a attitude of figuring things out, no matter how initially confusing.
Since then, I’ve had multiple attempts at creating my own programming language, usually getting stuck somewhere in the processor of trying to define a grammar and write a parser. Side projects can be like that. Part of the problem is that I didn’t want to write a lisp, but didn’t have the time/concentration between work and school to properly hand-write a recursive descent parser for anything else I was interested in at the time. Looking back, I probably should have embraced ANTLR or bison, but that’s another story for another time.
At one point in 2014 or so, I finally decided that I wanted to just make something Turing Complete, so that I had finally done it. The end result was a line-oriented, half inspired by CIL, and half crazed
VM-esqe interpreted thing that only spoke in a stack of numbers, and a buffer crafted out of a couple late nights with Go on my laptop. A Fibbionaci and looping program later, and I was satisfied to have finally done something that could be considered Turing Complete.
A semester or so later I ended up porting the same language into a Java version. My original plan had been to build my own version of Blockly or Scratch’s UI, and build an AST evaluator below it, but dynamically nesting UI in Swing and JavaFX was something I couldn’t figure out inside that semester. I do believe it is possible, but it is likely far more effort than it’s worth.
Not long after this, I ran across Factor. After fiddling with it for a while, I began to realize that I could probably manage to parse quotations and word definitions, and wrote up a simple as possible proof of concept in Go. I think one late night finished a basic parser and interpreter that was able to handle booleans, numbers, word definitions, and quotations and some basic operations on them. I didn’t have a name for a while, but eventually landed on a pun of the idea of Position Independent Code: Position Independent Source Code, aka PISC.
PISC has served a few purposes for me. Firstly, it served to cross “Implemented reasonably complete programming language” off my bucket list. Secondly, since the basic implementation was completed so quickly, I’ve decided to use it as a means of learning all of the non-parsing things related to building a programming language. So far, that’s been things like building a standard library and writing a syntax highlighter for Sublime Text 3. Going forward, it includes things like figuring out how to best distribute it while using fossil, finding a good niche for PISC. I’ve also had the opportunity to spend some time trying to optimize it, though there is a lot of performance that can still be gained.
One of the surprising things about PISC is how easy it has been to work on. Building the various bits and pieces of it has rarely taken more than 10 hours per bit. Stack based programming languages are often overlooked, backwards flowing nature their because. But because they are so easy to parse, and rather syntactically flexible, they lend themselves to very easy expansion. (And PISC isn’t even properly meta-syntactic yet). The other reason for this is that I’ve gone down the road of creating a dynamically typed programming language with a minimal number of types, and little to no type-level reasoning, at least yet. PISC only has 9 types at the moment: Integers, Doubles, Strings, Vectors, Dictionaries, Symbols, Quotations (which do live on the stack), and Native Go Functions.
PISC will be one of my side projects for some time to come, as there is still a lot to learn and design with it. I think stack based languages might be my new programming toy problem.
Published March 19th