Stack-based languages exposing additional stacks

Question

Stack-based programming languages use a stack for argument and return value passing, and often have a stack for return addresses also. I'm looking for instances of existing stack-based languages that expose further distinct stacks than that.

These additional stacks could have varied purposes, but the key is that program code has some way of manipulating them alongside the main stack or running in context of that stack. For example, this could be a language that provided a separate stack used for iteration data, a parallel stack of metadata about the data stack, or just multiple data stacks with distinct operations on them.

I'm looking for programming languages intended to be written by humans, not compilation targets or notional machines. The language should exist already — I'm not looking for speculation or concepts — and have some level of notability in its own sphere, but it doesn't need to be a published system. I'm looking at the language design level here, not implementation strategies using isolated stacks for function evaluations. Answers should identify applicable languages and how these additional stacks are used in them.

Answer 1

PostScript is a notable example of a stack-based language with several stacks. They are used for different sorts of objects:

• Operand stack — holds general operands and results, including integers, floating-point numbers, symbols, and pointers to compound objects such as strings and arrays.

• Execution stack — holds procedure return addresses.

• Dictionary stack — holds environment mappings, which can be used for top-level procedure definitions, or local variables.

• Graphics stack — allows saving and restoring the graphics state, including the path under construction, the current drawing properties such as width and colour, as well as the current local coordinate system.

I believe this is a typical pattern in stack languages that have more than two stacks.

The stacks may be divided by expected usage patterns, as they are here: certain states will all be saved and restored in a LIFO manner, but independently of one another.

Or, they may be divided by type—for example, a Forth implementation may have separate integer and floating-point stacks. These might be wired to corresponding types of ALUs in hardware, much like how a register architecture such as x86 has designated integer and float/vector registers for different storage classes.

Answer 2

AMPLE, a FORTH-like language, had a number stack and an additional string stack (as well as, presumably, a return stack).

It's a bit obscure, but it certainly qualifies.  AMPLE is an acronym (or at least backronym) for ‘Advanced Music Production Language and Environment’, and was supplied with the Music 500 System, a synthesiser module that connected to the BBC Micro.  Later versions added software modules functioning like a sequencer, mixing desk, &c, along with hardware for MIDI and a physical keyboard — but early versions were controlled entirely via AMPLE.

AMPLE is a stack-based programming language, borrowing heavily from FORTH, but adding some general-purpose programming language features.  (As well as a swathe of keywords for defining waveforms, setting up sound channels, and playing music with them; that included full co-operative multitasking so you can code each track separately.  Lilypond looks vaguely similar to some of the note-related parts.)

In particular, it adds full support for strings, with their own stack separate from the number stack.  So for example the word $CHR pops a number from the top of the number stack, converts it to a character, and pushes the corresponding one-character string onto the string stack; while $PAD pops a value from both stacks, and adds the given number of spaces to the string, pushing the result onto the string stack.

(Generating music doesn't generally need much string processing, but it's handy for displaying text on screen.)

AMPLE was certainly used back in the day; there were several whole ‘albums’ published on floppy disk for it, and I wrote a good many pieces myself.

You can see the full manual here.

Answer 3

FORTH has two stacks -- a data stack and a return (or control) stack. The data stack is used for values, while the return stack is used for return addresses of functions and can also be used for other data. The programmer can manually move values between the two stacks and need only ensure that the value on top of the return stack is the correct return address when a function exits.

The return stack is used explicitly by the compile-words in the language to store information about loops and branches/conditions while compiling code, so its not just (or even primarily) for return addresses.

Answer 4

There are a few esolangs with multiple stacks.

The first one off the top of my head is Stack Cats. Stack Cats is interesting because of the following properties:

• Each program must be its own mirror image.
• Non-symmetrical characters undo their mirror image (e.g. () is a no-op).
• Symmetrical characters are involutions (- for an obvious example).

This makes it impossible to do anything meaningful with a program of even length.

As I understand it, each Stack Cats program has arbitrarily many stacks that you can move between -- and you can even change the order of the stacks.

Perhaps less notably, my esolang Trilangle has one stack per "thread". Any operations that involve modifying the middle of the stack require multithreading and sometimes-painful synchronization, made possible by the guarantee that all threads tick at the same rate. See my implementation of selection sort for an example program that does this.

Answer 5

My stack-based toy language, fffff, does exactly this. User programs can create new stacks at runtime, and (references to) stacks are values which can exist within other stacks (docs link).

A stack can be "descended to", making it the new "current stack", so that other operations will now push and pop from that stack. Likewise, stacks can be "ascended from", restoring the earlier "current stack". Descending and ascending work by pushing and popping stacks to the "metastack", which is a stack of (references to) stacks, the head of which is the "current stack".

The operation [ creates a new stack and descends to it; the operation .[ descends to a stack which already exists (via a reference taken from the top of the current stack). Similarly, ] ascends from the current stack, and ]. ascends while pushing the old current stack's reference to the new current stack.

For example, starting in the global stack, the code [1 2 3]. creates a new stack, descends to it, pushes the constants 1, 2 and 3 to it, then ascends while leaving a reference to the new stack on the global stack. Although it looks syntactically like a list literal, semantically it is more like executing some code in a separate context, and the context is a first-class data structure. If this doesn't make sense, it might help to try entering the commands [, 1, 2, 3, ]. separately on the browser-based REPL, which shows the program state at each step.

A few side-notes:

• Since [ and ] are independent operations, it's not a syntax error for them to be unmatched.
• Unfortunately for fans of crazy meta-programming, the "metastack" itself is not a first-class value, since it does not have the same semantics as other stacks. Particularly, it can only contain stacks, and a runtime error occurs if it would become empty.
• In fffff, scopes are also first-class objects, which can be descended to or ascended from. Currently-active scopes are stored on the "scope stack", which is another special non-first-class stack.