9
$\begingroup$

I have made some queue-based esolangs in my time, but I have yet to see a "serious" queue-based programming language in the vein of Forth, Postscript, or Factor for stack-based languages.

Why are there so few queue-based languages? What issues are there when using a queue versus a stack?

$\endgroup$
1
  • $\begingroup$ In Erlang, each process has a message queue. In a way, one might say it's a queue-based language (but unlike the way Forth is stack-based). $\endgroup$ Jul 8, 2023 at 7:19

3 Answers 3

10
$\begingroup$

Programming languages are designed to allow programmers to describe solutions to problems, and although there are many different approaches to problem-solving (yielding many different programming paradigms), all of them involve some kind of composition of solutions to subproblems in order to solve larger problems. That is, a problem is solved by the programmer decomposing it into simpler problems, implementing solutions to the simpler problems, and then composing those solutions together.

The decomposition into subproblems happens in the programmer's brain, or on paper or a whiteboard; but the implementation and composition has to be expressible in the programming language. So at runtime, the program needs to do something like this:

  • Compute the solution to subproblem 1,
  • Compute the solution to subproblem 2,
  • Compute the solution to subproblem n,
  • Combine the already-computed solutions to subproblems 1 through n.

Note that the data used in the last step is the results of the most-recently computed previous steps. These subproblem results must be stored somewhere when they are computed, and then retrieved in order to compose the subproblem results into the result for the larger problem. So the data structure they're stored in must allow efficient retrieval of the most-recently inserted data, i.e. it must be last-in, first out ─ a stack.

This is so fundamental to implementing programming languages that it's not just a feature in "stack-based languages" ─ almost all imperative and functional languages use a call stack, for the same reason as discussed above.


All of this said, it would be very possible to design a language around a queue instead of a stack ─ just because the programmer expresses solutions to larger problems as compositions of solutions to smaller problems, doesn't mean that they have to be computed in that order. It's just that the language implementation needs to do a lot more work to figure out what order to do the computations in, so that their results are available at the right time in the program's execution.

If you're interested in this topic, functional reactive programming (FRP) is worth looking into. In the FRP paradigm, programs represent flows of data and events, so that the results of subproblems are computed and then flow into other computations which combine those results to solve other problems. The ordering of subprograms must be computed in advance by the interpreter or compiler, e.g. by computing the depth of each subprogram in the call graph.

Then at runtime, this ordering is used in a priority queue to ensure that each subprogram which needs to be computed, is evaluated before any other subprograms which depend on it. The results of the earlier subprograms are stored in objects which represent them, and later subprograms can retrieve those results via references to those objects instead of via a call stack.

It seems unlikely that a useful FRP language could avoid a call-stack entirely, but the priority queue is fundamental to the execution model; it would not be unreasonable to call these "priority-queue-based languages".

$\endgroup$
6
$\begingroup$

Once, while trying to make a visual editor for a stack-based language, I accidentally made a queue-based language. I think it illustrates where the difficulties with a queue model are, while also showing where it is actually possible.

What I was building was a system that laid the program out in 2D, with functions (grey) spread below their arguments and above their outputs (white): 2D grid of alternating function (grey) and value (white) rows, with multiple cells in each row. Some functions, like swap, are spread below two cells above and two below, while less is spread below two numbers and above one boolean.

You can take any typical concatenative stack-based program and lay it out this way. I was making an editor, so I also allowed selecting adjacent values (dragging across) and adding a new function below using those arguments. It turned out that that allowed creating programs like the above, which doesn't have an equivalent stack-based version: less is using values that are never at the top of the stack together.


Nonetheless, there is a clear meaning — and it turns out that this is actually a queue-based system: functions are evaluated left-to-right, top-to-bottom, cycling the full queue in each row. This works. People are able to use it, and they don't really notice the queue, focusing on just the correspondence between functions, but this correspondence is hard to work out otherwise.

Those empty cells each side of swap? Those are actually the identity function, just sending a value back to the end of the queue, and it's necessary to do that in order to line things up and to let values with different numbers of computation steps be used as part of the same function call. These are extra bits of program that don't contribute any substance, but are just required to make things work, and figuring out where they need to be unassisted is very challenging as well as taking up program space. For larger programs, a lot of the body ends up taken up by these noops. You could imagine this program instead written out linearly as:

123 "hello" 456 "world" id swap id less id id pick

This version is equivalent, but almost incomprehensible, particularly if you don't know how "wide" the queue is currently. With tooling, we're able to see that and implicitly deal with the bookkeeping, and that makes it workable, at the cost of needing to use this sort of tooling. These sorts of environments are generally slower to use than a text editor — imagine how many drags and clicks were involved in making that versus typing — and without something really providing information about what you can do figuring that out requires simulating the entire program mentally, not just the most recent steps you're actually relying on.

One reason there aren't many of these is that using them effectively requires using additional tooling of the sort that people mostly don't like. It doesn't need to be a visual environment, but something is going to need to show you where you are at any given point.


On the other hand, this actually executes quite well. Once transformed into this model there is a clear evaluation strategy. I used detached queues for executing user functions, though they can be inlined with the right cycling — but again, that's a tool intervention, and not something the programmer can easily write themselves. It's potentially suitable as a compilation target, and you can imagine machines or tasks where that's a good model (perhaps enabling parallelism, etc), but it's nigh-on unmaintainable for a human being, who most programming languages are made for.

For that matter, even ordinary maintaining of the program is difficult: a change that adds an extra output somewhere in the middle of the program requires that you update every single queue cycle (row) afterwards until you get back in alignment, inserting an id or something else in the right place, scattered through the program. That's somewhat workable in this sort of 2D model where you can see it, but virtually impossible to do reliably as a programmer in a linear stream of function calls.

$\endgroup$
1
  • $\begingroup$ This is also equivalent to using the queue as a secondary stack. A typical higher-order version would be 1 "a" 2 "b" [ swap [ less ] dip ] dip pick. Its first-order equivalent is 1 "a" 2 "b" >r swap >r less r> r> pick, where >r is “retain” and r> is “restore”. The trick here is that both can be implemented in terms of queue rotation, if you know the queue size. It corresponds to a row-major/breadth-first traversal of the 2D grid representation, wrapping based on the maximum parallelism; a traversal in column/depth order would wrap based on the critical path length instead. $\endgroup$
    – Jon Purdy
    May 29, 2023 at 0:14
5
$\begingroup$

In programing you typically want to apply some series of operations to the same data. In a stack based language you can easily apply multiple operations to to a base value by just adding the operations one at a time after another. You can easily define custom functions that perform multiple operations on a value and it will input and output in a stack-compatible way by default.

In a queue based language things are very different. If you want to apply multiple operations to a value you need to wait for it to reach the end of the queue again before being able to apply a second operation. This leads to messy confusing code, as any operation needs to be interleaved with what needs to be done with many other values before it gets it's "turn" again.

Re-using code becomes very difficult as well, since you can't really make a "function" if part of it needs to run at some later time.

Not all data needs to be accessed the same amount of times. In a queue based language you need to at least acknowledge each bit of data to push it back to the end if you need to perform any kind of computation on it. This means that you will need a lot of generic "skip" instructions just to get past any bits of the queue you don't need yet. In a stack based language this data could just live at the bottom of the stack till it's needed.

Overall the limitations on queue based programing conflict with how a program typically is structured unlike a stack based language that matches it.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .