brhfl.com

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.

I have a lot to think about re: instruction set. Ultimately, I want to prioritize low instructions so that programs with small word sizes can still do something. Basic implementation says that LSB dictates stack entry vs. instruction — 1 is for entry, 0 is for instruction. The stack is initialized at 0. If no instruction is given, instruction 0 will run. This means that wo0, with a word size of 0 (and thus no possible program words) is still a valid program — it executes instruction 0 with a 0 on the stack. Some golf languages have implicit output as a default. I’m not sure how I feel about that, particularly given the way my stack operates. So, for my initial instruction set, instruction 0 should output something, otherwise a 0 bit program does nothing user-facing (which essentially means it does nothing). As of right now, instruction 0 prints the stack. So a null program will simply print a 0.

Instruction 1 is our next most precious. Originally I thought I might need to waste it on a NOP. Consider that if one is using ASCII as input, and therefore full bytes, odd-numbered word sizes may leave a two-bit instruction as the last word encountered. A NOP seemed crucial until I realized, one could just stick something on the stack instead, and it would be NOP-equivalent as far as a user is concerned.

Addition was my second thought. Getting some math in early seems like a good idea. But here’s the thing — without anything else to do in the 2-bit realm, you’re just using addition to increment the stack and then output it. It becomes immediately obvious that bumping up the initial word size is a better way to start working with numbers. 11 11 10 00 is a full byte to output 2; 101 000 is only six bits. Addition is important, and probably a wo3 instruction, but it’s not wo2 material.

So here’s where I lose all my nerd cred. I propose that instruction 1 be GOTO. Here’s the thing — at the low end of the instruction set, we need to be very low-level, very primitive. Many low instructions will likely be made redundant by high instructions, and the variable word size demands this. Putting the red-headed stepchild of the looping world out there early gives us: several unique programs in the wo0-wo2 space, and a path for Turing-completeness early on. A higher instruction will let us rewrite instruction points (essentially allowing function definitions).

Instructions 2 and 3 are a Big Deal, and those will come another day. Let’s see what we can do so far. Ultimately a user would convert their binary to ASCII or ASCII+32 or just make a legit binary; for the purposes of readability, these examples will be in binary format separated by word size.

wo0
    0

wo1 '1 1 1 0'
    0    #push three implied zeroes
    0
    0
    0    #stack starts w/ a zero

wo2 '00 10'
    0   #print the contents of the stack
    0   #(remember, that's an initial zero)
    0   #also, goto eats a stack level, but wo stacks don't shrink
    0
    0 … #goto 0

wo2 '11 00 01 10'
    1   #we put a one on the stack this time
    0   #but there's also still a zero there
    1
    0
    1 … #goto 0

…we can’t do much yet, but it’s not half bad for under a byte. I have two instructions to fill for wo3. I hope wo4 can be Turing-complete. From there, it’s all luxury.

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

  1. wo, short for word, short for word size. Invoked like wo4 for a 4-bit initial word size language. I could go with ws, but then it wouldn’t evoke that dope Mya track from the early aughts. ↩︎