Unix history and the `dc` calculator
howdytx.technology
howdytx.technology
The author is correct on the parsing of "normal" vs. Reverse Polish notation. My `bc`, with normal expressions, needs 1555 LoC for parsing. My `dc` needs just 298.
I have a couple posts ([1], [2]) about `dc` tricks and code on my blog.
And yes, I have an HP 48G [3]. :)
[1]: https://gavinhoward.com/2019/12/bc/dc-tips-and-tricks/
[2]: https://gavinhoward.com/2021/04/a-dc-script-for-easter/
[3]: https://gavinhoward.com/uploads/easter-dc-script/hp-48g.jpg
[1]: https://gavinhoward.com/2023/02/my-code-conquered-another-os...
The really nice thing about stack based calculators that keeps me coming back to mine is that I can get all the numbers I'm working with down in one shot and then figure out which computations I'm applying in which order as a second step.
Until I tried RPN I never noticed how much mental bandwidth I was using shuffling numbers around in my head so I could input them into my calculator in the right order. With my stack calculator I just get all the numbers down and then swap and roll as needed to get the computation right. The number of times I've had to redo a computation because I started out wrong has been reduced to effectively zero, because I'm able to fully engage my math brain instead of juggling numbers at the same time.
do you have a screencast of your calculator's user interface? it sounds interesting!
Short tap on the stack swaps the top two stack items, long press rolls the top three. If I were doing it again I'd have long press roll the entire stack (top becomes bottom, the rest move up)—since it's all visible and I'm not programming it this would actually be more useful.
[0] On my phone at the time I wrote it this box had room for three numbers before scrolling. Now it has 12...
i feel like on a multitouch screen we ought to be able to tap on numbers to roll them to the top of the stack
Oh, yeah, what I'm calling Roll is actually Rot in Forth.
you called two different things 'roll'; one of them is indeed rot in forth but the other is depth 1- roll
E.g. dc -e '_640320[0ksslk3^16lkd12+sk-lmlhd1+sh3^/smlxljsxll545140134+dsllmlxlnk/ls+dls!=P]sP3^sj7sn[6sk1ddshsxsm13591409dsllPx10005v426880*ls/K3-k1/pcln14+snlMx]dsMx'
dc -e '_640320[0ksslk3^16lkd12+sk*-lm*lhd1+sh3^/smlxlj*sxll545140134+dsllm*lxlnk/ls+dls!=P]sP3^sj7sn[6sk1ddshsxsm13591409dsllPx10005v426880*ls/K3-k1/pcln14+snlMx]dsMx'
nix run nixpkgs#busybox -- dc -e '_640320[0ksslk3^16lkd12+sk*-lm*lhd1+sh3^/smlxlj*sxll545140134+dsllm*lxlnk/ls+dls!=P]sP3^sj7sn[6sk1ddshsxsm13591409dsllPx10005v426880*ls/K3-k1/pcln14+snlMx]dsMx' $ nix-locate -r 'bin/dc$' | grep -o '^\w.*\.out' | xargs basename -s .out
plan9port
gavin-bc
busybox
bc
_9base
make sure to check out the pregenerated databases, they're very convenient
I don’t understand why that has to be a macro. It asks for user input, so “because it has to be fast” can’t be the answer, can it?
I also don’t think it avoids some allocations. It’s creating two String’s, one for the call to read_line, and one to convert its trimmed result back to a String, is it?
What do I overlook?
After this post I've looked a man and well, it's a bit limited, googled a bit I've seen it's powerful, with macros, registers, usable for interactive scripts etc, I think it's a remarkable piece of software from another era, not because of RPN witch is very valid today, but because it was designed to run on limited resources to a point of being long to learn, a thing that might be useful today for quickness, but I fail to se a case for dc, and in general is not needed.
A good example of old glories, nice for inspiring some modern design which tend to be crapplily complex on average... We can do much with very little, if we find clever ways to do so.
I'm pretty sure the version with v6 Unix was written in PDP-11 assembler. It's possible it was translated from a version written in B? It wasn't THAT simple, since it had to implement arbitrary precision arithmetic. I have a vague memory of it using a "buddy system" storage allocator, a scheme also described in Knuth volume 1. Maybe the code is still around somewhere.
https://minnie.tuhs.org/cgi-bin/utree.pl?file=V6/usr/source/...
Reverse Polish notation, or RPN, removes the need for operator precedence.
... with postfix operators, the only data structure you need is a stack.
Prefix is perfectly fine for entering formulas into code. In dc or any other scratchpad, I find postfix much, much more convenient.
In a language where all functions had a fixed number of operands, prefix notation (or function invocation in general) could be used without any parentheses.
Parentheses are also required for postfix notation when functions with variable number of operands are accepted (e.g. the sum of an arbitrary number of operands).
We wouldn't want the data notation to have an implicit shape which depends on the programming language semantics of the symbols which appear in it, like their arity.
A LISP program is not (arbitrary) data, i.e. it does not contain arbitrary lists. Giving data, i.e. an arbitrary list to any LISP interpreter or compiler will just result in an error message and a translation failure.
A LISP program contains only invocations of functions or macros (besides special forms) and each invocation has an associated list of arguments. While the classic LISP convention is to write the function/macro name after the opening parenthesis, this notation is equivalent with writing first the name of the function/macro followed by a list of arguments enclosed in parentheses.
Conceptually, data in LISP, which consists of lists of values, should have used a different kind of brackets for delimiting a list.
Because of the limitations of the character sets available in old computers, the round parentheses have a dual role in LISP, as delimiters for lists that are data and as delimiters for the lists of arguments used by function/macro invocations. The two roles are differentiated by the use of the QUOTE special form, which is just a workaround for not using two different kinds of brackets, which would more clearly differentiate LISP data and LISP code.
If all the LISP functions or macros had a fixed number of arguments, then the LISP code, i.e. the invocations of functions or macros, could have been written without parentheses. In that case, the LISP data, i.e. lists, could have been delimited by round parentheses without using the QUOTE special form, which would not have been necessary.
append[listvar;(PARIS BERLIN NEWYORK TOKYO)]
The append call then looked like this:
(APPEND LISTVAR (QUOTE (PARIS BERLIN NEWYORK TOKYO)))
[eq[car[l];0] → cons[(ZERO);cdr[l]]; T → x]
(COND ((EQ (CAR L)) (CONS (QUOTE (ZERO)) (CDR L)))
(T X))
> Because of the limitations of the character sets available in old computers, the round parentheses have a dual role in LISP, as delimiters for lists that are data and as delimiters for the lists of arguments used by function/macro invocations.
No, the syntax above wasn't actually implemented at first. The M-Expression/S-Expression combination was hand translated into S-Expressions, since the Interpreter and Compiler took lists as input.
The reason why the syntax is like this is not a lack of characters or so. The reason is because the language early on worked on code as list data and not on code as text. The input and output was then of list data. The famous "Read Eval Print Loop" reads data, evaluates it and prints the result in data format.
It was thought that a later version of LISP had the M-Expression/S-expression syntax as surface syntax. But that did not get any traction, because the S-expressions would be visible in the programming tools anyway: debugger, code inspector, code stepper. Thus it was more convenient to stay in the s-expression syntax, than to convert S-Expressions both from and into M-Expressions/S-Expressions.
For example a stepper for LISP code might look like this. :s is the single step command:
CL-USER 8 > (step (plus (minus 10 20) (plus 20 30)))
(PLUS (MINUS 10 20) (PLUS 20 30)) -> :s
(MINUS 10 20) -> :s
10 -> :S
10
20 -> :S
20
(- A B) -> :s
A -> :S
10
B -> :s
20
-10
-10
(PLUS 20 30) ->
If we wanted M-Expressions, then the things would needed to be converted everywhere/everytime, which is much less elegant than leaving everything in one notation.
LISP 2 was an effort to modernize LISP and to switch to a different syntax.
How John McCarthy and his coworkers explained LISP between 1958 and 1960 does not necessarily match what LISP really is.
What you say about the history of LISP is correct, but it is not relevant for your thesis, that LISP required parentheses because supposedly LISP code is data.
As you say, LISP is a list processing language. Its main data structure is the list. A list may have a variable number of elements, therefore its notation requires parentheses for enclosing the elements of the list.
On the other hand, a LISP program is data neither more nor less than a BASIC program is data or a C program is data.
After parsing, a LISP program may be stored in lists, but this is an implementation detail that does not matter for the definition of the language. If desired, any program written in any programming language can be stored in lists, after parsing.
An arbitrary list is not a valid LISP expression, i.e. valid LISP code, even if it is valid LISP data. Moreover, LISP code cannot be provided as an operand to a LISP function that processes lists. Only LISP data can be provided as an operand. LISP data includes quoted LISP code.
Quoted LISP code is LISP data and it is of course stored as a list, but unquoted LISP code, i.e. real LISP code, is not normally stored as a list, except in the simplest and least efficient LISP interpreters, which do not have any practical importance.
So LISP code is not LISP data and LISP data is not LISP code. They have different syntax and interchanging LISP code and LISP data in a LISP program will normally cause a syntax error, exactly like interchanging the content of a string constant with a statement (i.e. writing it without quotation marks) will cause a syntax error in most programming languages.
In any programming language you can have a string constant that stores some program sentences or expressions, which is data that can be parsed as code at run time. The only special feature of LISP is that its syntax is very simple and regular, so parsing and processing at run time is trivial.
As I have said, LISP data requires parentheses, but LISP code is not LISP data and it does not require parentheses for being data. It requires parentheses only because most standard functions and special forms may have a variable number of operands. One could make a LISP dialect where all functions with a variable number of operands, like ADD, would be restricted to a fixed number of operands and where the same restriction would be applied to the special forms, e.g. only IF would be used instead of COND, while AND and OR would have two operands. In such a LISP dialect there would be no need for parentheses in LISP code, but the LISP data, i.e. the lists would continue to need parentheses (but QUOTE would no longer be needed to differentiate lists from function/macro invocations).
well, that's obviously wrong. There are so many examples where LISP code is LISP data. It's also just one example, a code for a theorem prover can also be LISP data. The whole idea of LISP is to be able to write interpreters, code transformations, rule engines, compilers as LISP applications which process code in the form of lists.
The idea of being a LIST PROCESSOR is not an implementation detail, it is the core essence of LISP.
In Common Lisp terms, an arbitrary list is a valid expression, but not necessarily a valid form. A form is an expression that occurs in a context where it is presented for evaluation.
It can directly contain arbitary lists or other objects as quoted literals.
It can use macros to create arbitrary syntax, which is then used.
(In mainstream dialects, macros cannot turn an arbitrary list into a form; it has to start with a symbol, after which it can be anything.)
when you have said
* + 3 4 - 5
6
by contrast, in
3 4 + 5 6 - *
i just wrote a command-line postfix calculator in c on my cellphone touchscreen in 20 minutes. it's 31 lines of code. i think that to do that so simply with prefix you have to do it right to left, effectively making it postfix
With prefix, you have to memorize also the yet not executed operations and for each operation you need to memorize how many operands have already been provided for it, in order to execute the operation as soon as its last operand has been provided.
So for a compiled language it does not matter much whether an expression is written with prefix notation or with postfix notation, but for an interpreted language the latter is more efficient.
Prefix notation in its simplest form is essentially the same thing but backwards, and you would only get intermediate results if you start writing from the innermost expression, which is complicated by the fact that that expression doesn't appear in the order you normally type.
From there I may shift to a handy emacs scratch buffer.
After that it moves to firing up Slime into CL. The * * and ** variables (which in CL equate to the 3 most recent evaluation results) is actually quite handy. Plus I just have the Slime history and all that.
None of those are RPN, but at this level I tend to not enter long equations anyway, and I have to do just as much precedence parsing cognitively converting algebraic to RPN or prefix anyway.
cool article
Bc is actually a preprocessor for dc(1), which it invokes
automatically, unless the -c (compile only) option is pre-
sent. In this case the dc input is sent to the standard
output instead.I still have my HP48SX RPN calculator too!
What are the chances all four of us would find the same thread? It’s so fast, so reliable, so omnipresent. Between that and being able to turn multiplication into addition by working in powers of two, I get answers while my colleagues are still waiting for excel to start.
Glad you like it!
(and it sure beats a magnetised needle and a steady hand)
I also use `dc`, together with `grpe` and `gits tatus`.