Zack’s Programmable Calculator (zpcalc)

All of the code can be found here

I’ve used a few calculators during my time as a student, from TI-Nspires to PCalc for IOS to Python’s REPL. I figured it was high time I made my own. But of course, I wanted to create something more useful than a simple four-function. Well, I got a little carried away, and now it’s basically an entire programming language…

Reverse Polish Notation (aka Postfix)

We need to start somewhere, so let’s start with notation. Most of the calculators you’ve used are probably infix. Infix expressions look like 2 + 4 - notice that the + is located in between its two arguments. The order of operations is used to determine how expressions like 2 + 3 * 4 are interpreted, with parentheses used to specify alternative orders of evaluation, like in (2 + 3) * 4. In more complicated calculators, you’ll also be able to used more advanced functionalities with the standard function(arguments...) syntax. For example, the TI-84 Plus CE lets you calculate a normal cumulative probability distribution with normalcdf(lower, upper, mean, stdev).

I would argue that this is quite a bit of syntax, and it can be annoying to type out or alter operations. For example, say we have sqrt(a_long_expression_here). Let’s say you realized that you wrote the expression incorrectly - you actually need to calculate a_long_expression raised to the power of 1/e. You would have to hold down the left arrow until you reached the sqrt, delete it, then move all the way to the right and enter ^(1/e).

This, to me, is an inconsistency in the syntax. Even though the sqrt is executed last, it is located at the beginning of the expression. Meanwhile, the power operation (^) is also carried out last, but it is located at the back of the expression. I would argue that it would make more sense to stick with a single ordering for all functions (mathematical or not): either function first and arguments second (like in Lisp), or arguments first and function last (postfix).

Not only does this simplify the syntax, it also removes any ambiguity. For example, 2 + 3 * 4 could be interpreted two ways: as either (2 + 3) * 4 or 2 + (3 * 4) (which is why the order of operations was invented). If we instead use postfix, we would have either 2 3 + 4 * or 2 3 4 * + (note that + and * only operate on the two most recent values entered). There is no mistaking the order in which we evaluate the expression - we either add 2 before the multiplication or afterwards. The only trade-off is that postfix is slightly harder to read and that we can’t exactly use standard mathematical notation. But if we are simply calculating values, I don’t think this is much of an issue.

The Stack

Another advantage of postfix is that it allows us to enter expressions incrementally. Every time we type in a number, it is pushed onto a stack. When you type in a function name such as + or *, the calculator will pop off the top two values of the stack, calculate a result, then push that onto the stack. This lets us “store” values on the stack as long as we need. For example, if we need to calculate an expression like long_expression_1 + (1 / long_expression_2), we can calculate long_expression_1, leave it on the stack, calculate long_expression_2, invert it using the 1/x button (or 1 swap /), then add the two expressions together using +. This (in my opinion) shows the main advantage of RPN calculators: the ability to break down complex expressions into smaller, easier parts to calculate. On an infix calculator, you would probably still conduct this breakdown, but you would be forced to use ANS or variables (or scrolling up repeatedly) in order to use previous results in new expressions.

Now, if you take the concept of an RPN calculator and generalize it to an entire programming language, you basically get Forth. With Forth, all of your variables are located on a stack, and you execute functions postfix. You can then take a sequence of operations and define it as a new function, so there is a method of abstraction. Some implementations of Forth even have objects and advanced data structures. For my calculator, however, I tried to keep things simple (for the time being).

ZPCalc

I decided to use Common Lisp to implement this calculator (you can find some reasons why I like Common Lisp here). Some advantages of this are: I can piggyback off Common Lisp’s numeric types (integer, rational, float, complex) and extensive set of mathematical functions. In addition, it’s extremely easy to get user input and convert it into a lisp type with (read). The symbol datatype in Lisp is really great for prototyping and I wish it were in more languages - there’s no need to define enums or classes just to be able to distinguish two things.

Fun fact: a Lisp Read-Eval-Print Loop (REPL) can literally be implemented as (loop (print (eval (read)))). Now you know where the name comes from.

Design Choices

Internally, the stack is simply a list. I decided against using the built-in functions #'push and #'pop since I didn’t want to manage a lot of mutable state. After some experimentation, I went with the State Monad as the core unit of “stateless” computation. For more details on why I chose this approach, see this blog post.

Now, all I had to do was define some primitive stack actions. Defining push! and pop! were easy enough to do in the language of the State monad, and pretty much everything else could be built on top of these operations. The do! macro helped to write code like (defun apply-binary! (op) (do! (a <- pop!) (b <- pop!) (push! (funcall op b a)))). Now, I could easily use Common Lisp’s built-in functions as part of my own calculator. The majority of the calculator’s built-in operations use #'apply-binary!.

I knew early on that I wanted the calculator to support boolean operations. However, I wasn’t sure if I wanted to use Common Lisp’s boolean types (t and nil), symbols (like :True and :False), or numbers (1 and 0). I ended up defining 0 to be false and everything else (but preferably 1) to be “truthy”.

One annoying aspect of the calculator is dealing with the difference between exact values (integer & rational) and inexact numbers (floats). Common Lisp handles all of the conversions and generic math, but I didn’t like all of its behaviors. For example, Common Lisp uses single-precision floats by default instead of double-precision, which is very frustrating (even though it probably doesn’t matter in practice) because I know that I’m missing out on precision. To force Common Lisp to use double-precision floats, I need to make sure all irrational functions receive double-floats as arguments (like (sqrt (coerce 'double-float 2)) instead of (sqrt 2)).

In addition, I want certain functions to be able to preserve exactness. For example, I want 4/9 sqrt to return 2/3 instead of 0.6666666..., and I wanted log 1024 2 to return 10 instead of 10.0. To fix this, I basically checked if both arguments were exact, did the operation with the arguments converted to floats, then checked if the answer was close enough to an integer. If the integer result was valid (which I checked by doing the operation in reverse), then I would return it. Otherwise, I would revert to the floating-point answer. This results in a bit of extra computation, but I think it’s worth it.

When first implementing the calculator, I only supported “symbol functions”, which were symbols that expanded into more symbols. For example, (def inv+ dup inv +) would record inv+ as a new function that would expand into three more instructions: dup, inv, and +. However, more complicated functions would get very annoying. For example, writing a function to calculate the roots of a quadratic given its three coefficients a, b, and c was possible, but it would require a whole lot of stack shuffling.

I figured that I might as well add in a lexical scoping system so that arguments to functions could be given names and referred to more easily. Implementing an environment was easy - an environment can be defined simply as a cons cell containing a hash table and a parent environment. To resolve a variable, you just check if a variable is defined in the current environment’s hash table. If it isn’t, go up to the parent environment and repeat. I provided the :var syntax and (store :var) construct to interact with the environment. Now, I could allow functions to provide argument names. Each time the function is called, it will automatically pop arguments from the stack and store them into the corresponding variables. For example, (def (f x y) :x :y *) would be desugared to (def f (store y) drop (store x) drop :x :y *). In addition, I figured that variables could be useful as calculator registers, so I added a top-level lexical environment and allowed :var and (store :x) to be called outside of function definitions.

Another thing I figured that I should probably support was metaprogramming. Both Forth and Lisp have the concept of a quotation, so I wanted to implement that in my calculator. I made it so that you could push anything onto the stack by quoting it first, and then it could be evaluated by running eval. In fact, the definition of eval in my code was literally just (do! (top <- pop!) (compile-action top env)), where compile-action is the function that is used to convert inputs into an executable stack action. Now, inputs like '(2 *) can be thought of as anonymous functions that can be called using eval. In addition, quoting special constructs like (if) and (while) “just works”, since eval is using the same function (compile-action) that I would use to run those actions anyway.

On the topic of special constructs - implementing while caused me pain. At first, I tried to implement while using only built-in calculator operations. For some reason, I was really dedicated to do looping with recursion. I would generate an anonymous function, add it to the environment, and then have the body of the while loop call itself. This actually ended up working, though it caused a stack overflow on ECL if there was too much looping. The next day, I realized that this was an idiotic implementation and that I just needed to go down one level of abstraction. Instead of trying to shoehorn in while using the calculator-level function calls, I could use a Common Lisp loop inside of a State monad. Now, there are no problems with stack overflow or runtime/space overhead.

I actually added undo and redo very early on. I was inspired by Haskell’s zipper - a way of “navigating” through a data structure in a pure manner. For my calculator, I kept the past and future states of the stack on two Lisp stacks. Whenever I ran undo, the latest state would be popped off the “undo stack”, and the current state would be pushed onto the “redo” stack (and vice versa for redo). If I executed an operation that changed the state of the stack, the current stack state would be pushed onto the undo stack and the redo stack would be cleared. Yes, this meant that redo states could be lost, but I didn’t want to bother implementing a whole undo/redo ring like the one Emacs has. However, the basic undo and redo worked properly, so I was happy.

Later on, I wanted to add some extensibility to the calculator. Originally, all user-defined functions were kept in single namespace. I wanted to allow users to write self-contained “packages”. I implemented an extremely basic namespace mechanism similar to the Common Lisp packaging system. You can enter a namespace with (in-package <namespace>), and all of the functions you define will be stored in that namespace. Then, you can call functions in other namespaces with the dot syntax, like so: other-namespace.function-name. To help users out when it comes to writing libraries, I added (with-package) so that you could execute code in a different package and return to the current one. This way, you could write code in a file, execute it using (load), and still remain in the same package.

After all of this, I figured that ZPCalc was ready to be released. Check it out here! Beware: there’s probably still plenty of bugs. If you have any comments or suggestions, feel free to contact me or open up an issue on Github!