UNIX History & the `dc` Calculator

When you need to do a bit of math, like most people, you probably reach for your phone's built-in calculator. If you're on a computer, you might bust open the Windows calculator, or any of the Linux equivalents. Perhaps, if you're in a terminal, you do something like:

$ python
Python 3.12.4 (main, Jun  7 2024, 06:33:07) [GCC 14.1.1 20240522] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> 39480 * 4
157920
>>>

You may even know that there's a dedicated UNIX utility, bc, which can do the exact same thing, and can run interactively, or with piped input, or a script. But have you ever tried dc? Maybe your fingers slipped one day, and you accidentally typed dc instead of cd, as I did. In that case, like me, you were presented with a simple blank line—not a prompt, not a copyright message, but just a blank line.

If you had that experience, you may have typed man dc out of curiosity (tldrdc if you were in a hurry). In that case, you'd see this:

dc(1)                                                                 
General Commands Manual                                                     
            dc(1)

NAME
       dc - an arbitrary precision calculator

SYNOPSIS
       dc [-V] [--version] [-h] [--help]
          [-e scriptexpression] [--expression=scriptexpression]
          [-f scriptfile] [--file=scriptfile]
          [file ...]

DESCRIPTION
       dc is a reverse-polish desk calculator which supports unlimited
precision arithmetic.  It also allows you to define and call macros.  
Normally dc reads from the  standard  input;  if any command arguments are 
given to it, they are filenames, and dc reads and executes the contents of 
the files before reading from standard input.  All normal output is to 
standard output; all error output is to standard error.

       A reverse-polish calculator stores numbers on a stack.  Entering a 
number pushes it on the stack.  Arithmetic operations pop arguments  off  
the  stack  and push the results.

       To enter a number in dc, type the digits (using upper case letters A 
through F as "digits" when working with input bases greater than ten), with 
an optional  decimal  point.  Exponential notation is not supported.  To 
enter a negative number, begin the number with ‘‘_''.  ‘‘-'' cannot be used 
for this, as it is a binary operator for subtraction instead.  To enter two 
numbers in succession, separate them with spaces or newlines.  These have 
no meaning as commands.

Well, that seems redundant. Just how many calculators does one need? My dear reader, the correct answer is "all of them." But what makes this calculator special, and what is all that about "reverse-polish calculators" and "stacks?"

To answer that, we need to examine the usual way of writing math. For example, when you want to operate on a couple of numbers, you typically write the operator between them, like this: \(1 + 2 = 3\). But there are other ways. There's function notation, which might look like \(\mathrm{add}(1, 2) = 3\). You could even have a lambda calculus notation, e.g. \(\mathrm{add}\,m\,n = \lambda s.\,\lambda z.\,m\,s\,(n\,s\,z)\) where \(1 + 2 = 3\) would be written \(5 = \mathrm{add}\,2\,3 = \lambda s.\, \lambda z.\,2\,s\,(3\,s\,z)\).

You could also have prefix, or Polish notation, where addition is written \(+\,3\,4\). This is really recognizable to lisp users. Reverse Polish notation, or postfix notation, is the opposite. It has operators following operands, like so: \(3\,4\,+\). You may wonder why on earth anyone would write math that way, but there is a good technical reason. Reverse Polish notation, or RPN, removes the need for operator precedence.

If you write a naïve program reading symbols and doing operations for infix notation, you'll quickly wind up tripping over expressions like \(3 + 4 \times 9 + 2\). The correct answer is \(41\). A simple interpreter would evaluate from left to right, and wind up with 63. To correctly apply the order of operations with infix notation, you would need to include either a parser that builds and evaluates an expression tree, or parentheses to specify the order. In contrast, the RPN equivalent of \(4\,9\,\times\,2\,3\,+\,+\) is easy to parse. Here's why.

Parsers aren't hard to implement for simple infix notation, but right-associative operators like exponentiation can be more difficult. In any case, a parse tree needs to be built somehow, and the tree needs to be simplified from its leaves downwards to its root. But with postfix operators, the only data structure you need is a stack.

The process is simple. Push numbers onto the stack. When you encounter a binary operator, pop two and operate, else, pop one. Push the result back onto the stack. At the end, the answer will be the only number left.

The History

This is a very simple algorithm, and it needs only very simple tools. Perhaps this is why dc, the UNIX RPN calculator, was the first utility ported to UNIX, way back in the PDP-11 days. It even predates the C programming language; originally it was implemented in B. This program is ancient in computing terms—right up there with dinosaurs, magnetic tape, and punch cards. Wikipedia calls it the "oldest surviving UNIX program."

RPN isn't unique to dc. The first recognizable electronic (or electromechanical) computer, Konrad Zuse's Z3, used RPN as its input scheme in 1941. Since that time, all manner of calculators and computers, desktop, handheld, or otherwise, have used RPN as the input scheme because it is efficient and unambiguous. Hewlett-Packard's calculators notably used RPN for every field, from accounting to engineering. You may know the venerable HP-15C, which offered everything from matrix operations to numerical integration, all with RPN on 1980s hardware.

Ah, simplicity...

Now

Just for fun, yesterday afternoon I implemented a little dc-like calculator in Rust. It doesn't have registers or support for macros yet, but it does implement addition/subtraction, multiplication/division, exponentiation, and square and cube roots. The arbitrary precision is supplied by the bigdecimal crate. I thought about using Malachite, but neither it nor num support taking roots. They want their operations to remain closed on the ring ℚ, and roots are a great way to get irrational numbers!

You can find the source code here. Just clone the repo and do:

cargo run

to start the program. Then, type in your RPN expressions. You can print the entire stack with "p," clear it with "c," print the top item with "t," and take square and cube roots with "v" and "b," respectively.

I'm especially proud of my little prompt macro, which is the first Rust macro I've written. I never understood why something like this wasn't included in the standard library, but here you go, for what it's worth:

/// A simple macro to grab input from the user.
#[macro_export]
macro_rules! prompt {
    ($prompt:expr) => {{
        print!("{}", $prompt);
        use std::io::Write;
        std::io::stdout()
            .flush()
            .expect("Writing to stdout failed!");
        let mut input = String::new();
        match std::io::stdin().read_line(&mut input) {
            Ok(0) => std::process::exit(0), // Handle EOF
            _ => {}
        };
        input.trim().to_string()
    }};
}

You use it like this, which I think is pretty handy.

let input = prompt!("Enter a number> ");

Thanks for reading! I'd appreciate your comments. Please, connect with me on LinkedIn, or email me at ethan.barry@howdytx.technology.