brhfl.com

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.

Part of my exercise today made use of calculating modulo. It briefly occurred to me that this could be one of my remaining three wo5 instructions1, but I also wondered how much space one would waste simply implementing it themself in a wo5 program. The answer: 9 bytes. Well, 70 bits, but I guess I have to round up. Instead of implementing modulo, I’m considering a FLOOR instruction. For this demonstration, I’m going to largely comment the state of the stack, with the top to the right. I’m going to use decimal numbers and named instructions. Given that…

10        #Put a number on the stack
4         #And another (these don't count toward the byte count)
1
YANKPST   #PST: 10, 10, 4, 10
1
YANKPST   #PST: 10, 10, 10, 4, 10, 4
DIVIDE    #PST: 10, 10, 10, 10, 4, 2.5
FLOOR     #PST: 10, 10, 10, 10, 4, 2
1         
1
YANKPST   #PST: 10, 10, 10, 10, 10, 4, 1, 2
DIVIDE    #PST: 10, 10, 10, 10, 10, 10, 4, .5
DIVIDE    #PST: 10, 10, 10, 10, 10, 10, 10, 8
-1
DIVIDE    #PST: 10, 10, 10, 10, 10, 10, 10, -8
ADD       #PST: 10, 10, 10, 10, 10, 10, 10, 2

…14 commands at 5 bits each: 70 bits total2. It shows the unwieldiness of using such limited instructions, but at the same time demonstrates that many such instructions still only take 8 bytes. There may be situations where, despite one complex need, a smaller overall word size still leads to shorter code.

This code also goes a ways to demonstrate how our stack can get away from us. Ideally one would either ignore or manage this, but I may be biting off more than I can chew here. I don’t necessarily know that it’ll have the same benefit that the bottom (T) of a 4-level RPN stack has. It may also be worth entertaining a differentiation between popped values and parameters, with, for instance, YANKPST shrinking the stack where the index was taken from (the old top, essentially).

Current Instruction Set:

0, 0, PRNTPST
Print the contents of the primary stack (PST)
1, 1, GOTO
Pop top of stack, go to corresponding word
MNum: Go to word indicated by storage register R2 (more on this later)
Nonexistent word exits
2, 10, ADD
Pop two values off of the stack, push their sum
3, 11, SKIPZERO
Pop one value off of the stack, if == 0, skip all words through next instruction
4, 100, REGISTER
Pop two values off of the stack, set register indexed by first to value of second
MNum: Push value of register indexed by first
5, 101, DOUBLE
Pop two values off of the stack, push value created by treating the popped values as a double number
6, 110, CLEARPST
Empty PST, pushing the top of stack as its only value
7, 111, YANKPST
Pop a value off of the stack, push the value of the stack entry indexed by the popped value
MNum: Could potentially cause a DROP
Negative values indexed from bottom of stack
8, 1000, PICKPST
Pop 1 value off of PST, pop the value off of PST with the index of the first value popped
Negative numbers index from bottom
9, 1001, PICK$ST
Pop 1 value off of PST, pop the value off of $ST with the index of the value popped from PST
MNum: Fold entire SST into string on PST
Negative numbers index from bottom
10, 1010, PUT$ST
Pop one value off of PST, push onto $ST
If value is a string, unfold entire string onto $ST
11, 1011, CLEAR$ST
Clear $ST entirely ($ST, unlike PST, can be empty)
12, 1100, FLOOR
Pop one value from PST, push floor of value
13, 1101, DIVIDE
Pop two values from PST, push (fractional) quotient

  1. Alternatively (and I actually think I’m leaning this way), a register could be used to flag whether DIVIDE returns a fractional quotient or an integer quotient and remainder. ↩︎
  2. Without the initial stack entries: 00011 01110 00011 01110 11010 11000 00011 00011 01110 11010 11010 10011 11010 00100. Padding the final byte with zeroes, we get 1B 86 ED 60 63 76 B5 3D 10. In the Jelly code page, our code is ñ⁶ḣ`cvỌ=Ñ. ↩︎