QQ: The Queue-Based Programming Language

A puzzle in every program

Published Jan 30, 2021

A few weekends ago, I took part in the first Quirky Languages Done Quick mini-hackathon (QLDQ). I want to share my thoughts about how it went and the design process my team went through. I had fun, and we’ll probably do it again, so let me know if you’d like to join us next time!

If you’d like to see the language before the design process, check out the repo.

How to Hackathon

It started with 5 people and no plan, so we spent a bit getting to know each other and discussing interesting programming language ideas. It’s always fun to chat about weird programming stuff! There were a ton of interesting thoughts (someone should have them all written down somewhere 🤞), and most of them were closer to research than hackathon. From various connections, we all mostly-three-wise knew each other, so we shuf’d our way into two teams.

A hackathon needs a theme, so we picked one idea to serve as a shared prompt. And hackathons must have winners, so we decided to judge “most X” and “least X” for criteria we’d wait to decide until the end.

Taking the event title literally, our prompt was the idea with the best quirk: a queue-based programming language.

How to Language

My team started with a discussion of how we’d interpret the prompt: what did “queue-based” mean to us? Naturally, a queue-based language was proposed in contrast to stack-based languages like Forth. In Forth, operators take their arguments from the top of the stack and push back to the top. To become queue-based, all operators would take their arguments on the front of the queue and push the result to the back.

We were the three-person team, and all three of us have experience in some everything-is-a languages:

  • C: everything is an int
  • Lisp: everything is a list
  • shells: everything is a string

So what about making everything a queue? That sounds a lot like everything-is-a-list, but there’s one very important difference: you can scan a list without changing it, but you can’t scan a queue without consuming the elements in it!

With this slightly more concrete idea of the language, the next step was to see if programs could be written at all. We wrote these tiny programs together to convince ourselves that the basics made sense:

  • Print some text to the screen: String literals are nice, and the interpreter/compiler needs to provide print as a built-in function.
  • Basic math: Numeric literals were already assumed. This proved that binary operators can make sense, and are actually a fun puzzle. I don’t know if this notation has a name, but I’d go with “inverse Polish notation” (because reverse Polish notation is already taken).

To get the syntax down, we each tried to write a program that would reverse a string. This was surprisingly difficult! Even after deciding on the queue-based algorithm together, I couldn’t finish my program in the 30 minutes we gave ourselves. This exercise informed us that language needed some more features:

  • Conditionals
  • User-defined functions
  • Local state

Without those, we found ourselves needing to rotate the queue after nearly every operation, and that was more frustrating than fun. That turned into our major design principle: make the language difficult, not hostile. Think brainfuck, not Malbolge.

I was in charge of the parser (to no one’s surprise) which I implemented using Parsimonious as a parser generator. I like PEG for playing with grammars, especially for small ones like ours. And this was the only Python PEG parser I hadn’t already tried! Parsing is always built on graphs or trees, so my queue-based contribution is the Abstract Syntax Queue (ASQ).

All the other interesting parts made it into the language proper, so check out the example programs.