Bubble sort in dc

dc offers essentially nothing in the way of stack manipulation. Part of the power behind a lot of RPN/RPL HP calculators was that if you were being tidy with your stack, you rarely had to use registers. This is not the case with dc. Of course there’s also nothing resembling array sorting in dc, and I was curious how difficult it would be to implement a basic bubble sort.

As mentioned, we can’t directly manipulate stack elements (beyond swapping the two topmost values), but we can directly address elements of an array. This means that our bubble sort needs to dump the contents of the stack into an array, and potentially dump this array back onto the stack at the end (depending on what we need the sort for).

zsa0si[li:sli1+dsila>A]dsAx

This takes care of putting everything on the stack into array s. It does this by storing the number of items on the stack into register a (which we will need later – dc does not have a means of counting the number of items in an array). We start counter i at zero, and just go one at a time putting the top-of-stack into array s at index i until i is equal to a.

[1si0sclSxlc1=M]sM

The bubble sort itself requires three macros. This first one, M is our main macro, which we will ultimately begin executing to start the sort process. It sets a counter, i to one and a check register, c, to zero. Then it runs our next macro, S, which does one pass through the array. If S has changed anything by running macro R, the check register c will no longer be zeroed out, so we test for this and restart M until no changes have been made.

[lidd1-;sr;s<R1+dsila>S]sS

As mentioned, macro S does one pass of the array s. We fetch our counter, i, duplicate it twice, and decrement the top copy by one. While we work on our array, we’re always looking at i and i-1 essentially, which just makes the comparison a bit tidier at the end vs. i+1 and i. We load the values with these indices from s, compare them, and if they aren’t in order, we run macro R. We still have a copy of i on the stack at this point, so we increment it, duplicate it, store it, and compare with a to see if we’ve hit the end of the array.

[1scddd;sr1-;sli:sr1-:s]sR

Macro R does one instance of reversal. First it puts a one in the check register, c, so that M knows changes have been made to the array. At this point there is still a copy of i on the stack, which we duplicate three times. We load the i-indexed value from s, swap with a lower copy of i which we decrement by one before loading this i-1-indexed value from s. We load i again, and store the old i-1 value (our previous top-of-stack) at this index. This leaves our old i value atop the stack, with i one spot below it. We swap them, subtract one from i, and store the old i value at this new i-1 index in array s.

And that’s actually it. If we populate the stack and run our initial array-populating code before executing lMx, we’ll end up with our values sorted in array s. From here, we can [li1-d;srdsi0<U]dsUx to dump the array onto the stack such that top-of-stack is low, or 0si[lid;sr1+dsila>V]dsVx to dump the array onto the stack such that top-of-stack is high. If, say, we only need min (0;s) or max (la1-;s), these are simple tasks.

Additionally, if we wanted to get the median of these values, we can exploit the fact that dc just uses the floor of a non-whole index into an array. This allows us to avoid an evenness test by always taking ‘two’ values from the middle of the array and calculating their mean. If a is odd, then half of a will end in .5. Conversely, if a is even, half of a will end with no remainder. So we can subtract half of a by .5 to get the lower bound, and then subtract half of a by half of a mod one (either .5 or 0) and average the values at the resulting two indices: la2/d1~-;sr.5-;s+2/p.


Nth-order Fibonacci sequence in dc

After working on the nearest Fibonacci number problem in dc, I got to thinking about how one might implement other generalized Fibonacci sequences in the language. Nth-order sequences seemed like a fun little challenge, and since I was simply doing it for my own pleasure I went ahead and gave it prompts and user input:

% dc -e '[_nacci? ]n?1-sg[terms? ]n?2-snlgsi[0lid1-si1<Z]dsZx1[dls+ssli:flid1+silg>G]sG[li;flid1-si0<R]sRlgsz[0si0sslGxlgsilRxlslzd1+szln>M]dsMxf'
_nacci? 4
terms? 20
20569
10671
5536
2872
1490
773
401
208
108
56
29
15
8
4
2
1
1
0
0
0

…gives us the first 20 terms of the tetranacci sequence. This interested me because unlike a simple Fibonacci iteration that can be handled on the stack with only rudimentary stack manipulation (dsf+lfr), higher order ‘naccis need summation of more terms. For a defined number, I could simply use registers, but dc does support arrays, so setting the order at runtime is plausible. There’s a bit going on here, so I’m going to start by rattling off all of the registers I use:

g:
The order (so, a g-nacci sequence)
n:
Number of terms to run through
s:
Sum
i:
General counter
f:
Array used to temporarily hold the last sequence as it’s being summed
G:
Generalized Fibonacci generating macro
R:
Macro to retrieve previous sequence from f
Z:
Zero-seed macro
z:
Counter for iterations (compares to n)
M:
Main macro

Now to break down what’s going on. [_nacci? ]n?1-sg[terms? ]n?2-sn just prompts the user and inputs g and n. We reduce each of these in the process to appease the loops. After doing this, we need to seed the sequence with g-1 zeroes, and one one. lgsi sets counter i to g, and then the macro Z, does nothing but put a zero on the stack and loop: [0lid1-si1<Z]1. dsZx stores the macro and executes it; then 1 pushes the necessary one onto the stack such that we can begin.

[dls+ss]sS is our macro, S, which is a simple summer for register s. It duplicates the top of stack, recalls s, adds the two together, and then writes that back to s. The stack is returned to its original state.

Our next macro, G, has a bit more going on: [dls+ssli:flid1+silg>G]sG. It starts with a simple summer for register s, dls+ss. This duplicates the stack, recalls s, adds them and then overwrites s with the new sum. The stack returns to its original state. The next thing we need to do is move the top of the stack into our holding array, f. We’ll use our counter i as an index, so we load i and then do the array operation, li:f. Every time we do these two things, our summation (the next number in the sequence) nears its next value, and our stack shrinks. The rest of the macro, lid1+sig>G just handles incrementing i and comparing it to our order, g, determining whether or not to continue the loop.

Macro R, [li;flid1-si0<R]sR repopulates the stack from array f. Before calling R, i is set to g, and we use that as our array index to pull from, thus treating the array as a LIFO2. li;f does this, and then the rest of the macro is (surprise, surprise) counter/loop handling.

Before we run macro M, which is our main macro essentially, we set counter z to our order number g, which accounts for the fact that we already have our first few terms in assorted zeroes and a one. M, [0si0sslGxlgsilRxlslzd1+szln>M]dsMx, starts out by resetting counter i and the sum register s to zero: 0si0ss. lGx runs macro G, lgsi sets counter i to our order g, and then lRx runs macro R. ls puts our sum (the new Fibonacci value) at the top of the stack, and then the rest of the thing is counter/loop handling. dsMx saves the macro as M and also sets it running, while our last command, f prints the entire stack.


Nearest Fibonacci number in dc

I hadn’t really exercised my code golf skills in a while, but saw a fun challenge today that seemed like an easy solve, well-suited for dc. The challenge was, given a positive integer, return the nearest Fibonacci number. The Fibonacci sequence is fun on its own in a stack language; in dc one step can be performed with something like dsf+lfr. Given that the stack is prepared with two integers, this will duplicate the top, store it in an intermediate register f, add the two previous values, push f back onto the stack, and then swap them such that they’re in the correct order. It doesn’t pollute the stack, either, these two values are all that remain.

For this challenge, those two values are all I ever need – my input (which I will refer to as i) is always going to fall between two consecutive numbers in the Fibonacci sequence (or on one of them, in which case I would only need that value to test against). Keeping as much work on the stack as possible is ideal when golfing in dc because the byte cost of working with registers adds up quickly. So my strategy is to seed the Fibonacci generator with two 1s, and run it until the larger of the two Fibonacci numbers is greater than i. One of those two Fibonacci numbers will be the right one, and if i happened to be a Fibonacci number, I’ve just generated an extra one for no reason. I convert both of the Fibonacci numbers to their respective differences from i. Since I know for a fact that the top of the stack is greater than i, and the second value on the stack is either less than or equal to i, I don’t have to worry about dc’s lack of an absolute value mechanism; I simply subtract i from the big one and subtract the small one from i. Since I know which difference is which, I have no need to retain the Fibonacci numbers. I simply compare the differences, and then reconstruct the Fibonacci number by adding or subtracting the difference to i depending on which difference ‘won’. The code:

?si1d[dsf+lfrdli>F]dsFxli-rlir-sd[lild-pq]sDdld<Dli+p

…and the explanation:

?si                  Store user input in register i
1d                   Push 1 to stack, duplicate it to seed Fibonacci sequence
[dsf+lfrdli>F]dsFX   Macro F: Fibonacci generator as described above, with the
                       addition of loading register i and continuing to run F
                       until the top-of-stack Fibonacci number is larger than i
li-                  Turn our high Fibonacci number into its difference
rlir-                Swap the stack, and turn our low Fibonacci number into its
                       difference. The stack stays swapped, but it doesn't 
                       matter
sd                   Store our low Fibonacci difference in register d
[lild-pq]sD          Macro D: reconstruct the low Fibonacci number by 
                       subtracting d (the difference) from i; print the result
                       and quit. Macro is stored for later use.
dld<D                Duplicate the high Fibonacci difference and push the low 
                       Fibonacci difference onto the stack. Compare them and run
                       D if the low difference is less than the high difference
li+p                 Else, add i to the high difference and print the result

wo: 9-byte modulo

While working on a code golf challenge in dc today, my mind turned to if and how I could solve the same challenge with the current instruction set of wo. We left off in the middle of wo5, with six slots to go and the promise of division. Internally, I was filling a couple of slots with additional stack manipulation instructions, with three slots still open. The goal isn’t necessarily to be able to do everything (or, perhaps, much of anything) efficiently at this point, but to leave that bit-shaving option on the table, letting the programmer do the most with the least. Since there’s no fractional input, division was a no-brainer: now you can enter fractions, you can waste a little time making a reciprocal for multiplication, and you can (of course) divide.


wo: Registers

Thoughts on wo have slowed down slightly, largely because I think I’ve gotten a lot of easy answers out of the way. I haven’t yet addressed – no. 4, REGISTER. Delegating as much responsibility to internal registers as possible, and allowing a wo programmer to modify these registers is paramount to opening up the extent of what can be done inside of a limited instruction set. As few system registers as possible will be reset at every turn – this is likely necessary for something like ‘stack depth,’ as it is a valuable value for a user to be able to fetch, but for a user to change it would be both unpredictable and of limited value.


wo: Stacks

At some point the question of stacks in wo needs to come up. How many, how do they work, how do we manipulate them. As mentioned in the first post in the matter, I’ve been operating under the premise of a stack that does not shrink (unless cleared). It takes the theoretically-infinite stack of RPL, and combines it with the repeating bottom of RPN. Thus (pseudocode, obvs):

> 1 2 PRINT_STACK
1
2

> 3 PRINT_STACK
1
2
3

> DROP PRINT_STACK
1
1
2

wo: Implementing the interpreter

I’ve been thinking a lot about instructions for wo, how to eke the most out of low-byte-count programs. And, while I haven’t touched on it here yet (soon!), I’ve been thinking a lot about what system registers could prove useful as well. But a big part of me wonders how I’ll implement the thing, if I ever do. That so many esoteric/golfing languages are just layers on top of another scripting language makes me a bit grumpy, and that isn’t a path I’d like to take with wo. My plan would be to write the reference interpreter in go, but I wouldn’t discount ANSI C either. That decision is trivial, though.


wo: A truth machine in wo3

In wo3, we get two extra instructions for a total of four. OISCs can be Turing complete, so four instructions should be enough to give us some brunt. At this point, some amount of math is probably a good idea. Instruction three, then, is ADD, which does what you think it does. Since we’re capable of entering negatives, we can pretty much get to any number we want at this point, albeit terribly inefficiently.

Branching would be very convenient at this point as well, so a simple SKIPZERO instruction gets the no. 4 position; it pops a value from the stack and if that value is zero, it skips until past the next instruction. All odd (input) words are skipped until an even (instruction) word is encountered, at which point that is skipped and the next word is interpreted. Skip if zero is a standard simple conditional branch, but I’ll likely change this to skip if (skip register), so a user can theoretically set the branch condition via a register (with a command certain to be available in wo4).


wo: Numbers

A draft of this post began:

A few thoughts on numbers in wo. Numbered input is pushed to the stack via LSB==1. LSB==0 signifies an instruction, so in either case, effective word size is 1 bit less than total word size. The stack itself won’t care what sort of numbers it’s holding, input is the tricky part. wo3 would allow you to enter the integers 0-3, or 2-1 depending on unsigned vs. signed input. wo4 0-7 or 4-3. These aren’t big numbers to work with, so getting instructions in early to allow for more complicated input would be welcome. The easiest solution here is simply getting the WORDSIZE instruction out of the way as early as possible, ideally in two bits. With signed input, this would only get a user up to a 4-bit word size with 6 bits of input. Unsigned, a user could get up to 6-bit word size in the same 6-bit input, which raises the question of whether allowing a single word input of 1 is more important than more immediate access to slightly higher integers. Signed input would reduce the need for a sign-changing instruction at the low end of the set, and there are little hacks that could be put in place – for example, if 1s’ complement was used instead of 2s’, 0 could act as a stand-in for the next highest byte size or the like. Thus 6 bits of input could immediately kick word size up to a full byte.

As outlined in this post killing off WORDSIZE, I have changed my thoughts on that matter. I do think input will (by default) be 1s’ complement, with 0 receiving special treatment, what I am internally referring to as the Magic Number or MNum. MNum would allow some instructions to serve multiple purposes, which could theoretically put us on the path to larger integers at lower word sizes. Additionally, MNum can act as a stand-in for a predetermined value for other instructions, again opening up some integer growth options.


wo: Word size

A few things have occurred to me regarding the WORDSIZE instruction in wo. Namely, that changing word size in the middle of a program could be entirely unpredictable – my first thought would be to break every word out into an array before interpreting (aside from the WORDSIZE instruction itself), but that would be impossible – the stack would necessarily have to be computed before WORDSIZE could execute. Even before this, I was wondering if I should really prioritize it so low in the instruction set, or if it just turns into an abuse of a reduced instruction set claim.


wo: Introduction

I’ve been thinking a lot about languages designed for code golf and programming puzzles/challenges. They run no risk of extinction — seems a new utterly inexplicable dialect is always freshly hatching. And here I am, about to fan these flames with my own bonkers idea. I call it wo1. Here’s the thing – there will be several posts in this series, as I figure out how I would ideally like this thing to work. There will be a lot of theoretical code. But it is very possible that I will never actually bother writing a reference implementation for it. I’d like to think that I will, but I’m really not a great programmer and the fun for me is largely in the thought experiment, the puzzle.

There are a few key points that I think will make this language unique. First and foremost, it’s based on binary instructions with variable word sizes. The interpreter should set the initial word size based on invocation: wo4 would start with 4 bit words, wo7 with 7 bit words, etc. Smaller word sizes mean more instructions per byte, but fewer instructions are available (and smaller numbers can be pushed to the stack). It is postfix, stack-based, influenced by RPN, RPL, Forth, and dc. The main stack is initialized at zero, and can never be empty. I am very seriously considering a stack that grows but does not shrink (aside from clears) – drop operations would duplicate the bottom of the stack like RPN. Word size would be resettable via a relatively low (preferably 3-bit) instruction. A separate stack would handle certain scratch activities like string manipulation. Least Significant Bit (LSB) would determine stack input vs. instruction execution. Nearly every instruction would be rewritable (don’t need GOTO? plop something else in there before dropping your word size and taking care of business). That pretty much sums up the core philosophy/principals, the big remaining question is implementation — primarily, instruction set.


Collatz sequences in dc

Inspired by this recent post and code snippet by John Gruber, I decided to have a go at outputting Collatz conjecture sequences in dc. Running

    dc -e '?[r3*1+]so[d2~1=opd1<x]dsxx'

from the command line will take a single value as input, and run the sequence. ? takes input, puts it on the stack. [r3*1+]so is our macro for n3+1, what we do when we encounter an odd value. [d2~1=opd1<x]dsxx is our main macro, as well as our macro for handling even numbers (n/2). First it duplicates the value on the stack (last iteration) and divides by 2 to return the quotient and the remainder. 1=o uses the remainder to test for oddness and run o if true. Here I do something rather lazy for the sake of concise code: that initial duplication was solely for the sake of oddness. o swaps the top of the stack to get that value back, then multiplies by three and adds one, leaving this value on the stack. Evenness will never run this, and since the test for evenness leaves the outcome for evenness on the stack (what luck!), and the initial duplication is below it. Either way, the bottom of the stack is going to fill up with a lot of garbage, which should be inconsequential unless our sequences become absurdly long. At this point, the top of our stack is the result of the current step, so we print it, duplicate it, and run x if it’s greater than 0. Finally, we duplicate our main macro, save it as x, and then execute the copy we left on the stack.


dc as a code golf language

Code golf is a quirky little game – complete the challenge at hand in your preferred programming language in as few bytes as possible. Whole languages exist just for this purpose, with single-character commands and little regard for whitespace. dc always seemed like a plausible language for these exercises, and I recently attempted a few tasks which I would not ordinarily use dc for, notably 99 Bottles of Beer.


dc

This is an old post from an old blog; assets may be missing, links may be broken, and my opinions may differ considerably by this point…

Even though I generally have an HP or two handy, the POSIX command-line RPN calculator, dc, is probably the calculator that I use most often. The manpage is pretty clear on its operation, albeit in a very manpagish way. While the manpage makes for a nice reference, I've not seen a friendly, readable primer available on the program before. This is likely because there aren't really people lining up to use dc, but there are a couple of compelling reasons to get to know it. First, it's a (and in fact, the only calculator, if memory serves) required inclusion in a POSIX-compliant OS. This is important if you're going to be stuck doing calculations on an unknown system. It's also important if you're already comfortable in a postfix environment, as the selection of such calculators can be limiting.


dc Syntax for Vim

This is an old post from an old blog; assets may be missing, links may be broken, and my opinions may differ considerably by this point…

I use dc as my primary calculator for day-to-day needs. I use other calculators as well, but I try to largely stick to dc for two reasons - I was raised on postfix (HP 41CX, to be exact) and I'm pretty much guaranteed to find dc on any *nix machine I happen to come across. Recently, however, I've been expanding my horizons, experimenting with dc as a programming environment, something safe and comfortable to use as a mental exercise. All of that is another post for another day, however - right now I want to discuss writing a dc syntax definition for vim.