Multistack Concatenative Programming Languages

jotted out, 2026-08-07

Concatenative programming languages (catlangs for short) are a style of programming centered around point-free composition of programs. The motto of this style of programming is "juxtaposition is composition". The simpliest implementation of a catlang revolves around a data stack for holding terms and a implicit call stack holding execution tokens.

f g == f₁ f2 f3 f4 ... g1 g2 g3 g4 ...

The principle that a purely concatenative language follows. The composition of f and g is the same as the concatenation of their components. This principle means code can be cleanly factor out from expressions and lifted to their own definitions.

Catlangs additionally come equiped with the ability to "quote" chunks of code. Quotations represent a list of terms that can be manipulated as data and possibly executed as code. This enables catlangs to represent high-order programs. Joy established the common convention of using [ ] to represent quotations.

[ dup * swap dup * + square-root ]

A quotation, that when executed, computes the mangatude of two numbers on the stack.

The full range of ergonomics around these languages has been left mostly unexplored. A common struggle with catlangs can be managing their data stack. Algorithms with poorly structured dataflow can quickly create messy code that is "write only". Some catlangs provide an auxiliary stack for temporarily dipping under values. However, there can still be a desire to "name values" instead of "naming code".

Juxta, an orange tabby with floating square brackets around its head, glares at the viewer. His tail flicks from side to side as he flings a coffee mug off the table. — Juxta trying to convince you to factor your code and streamline your data flow.

A common way to easy the pressure of managing the data stack is to add lexical variables. However, these provide only short term benefits to catlangs. Lexical scopes do not compose via concatenation, but nesting. Logic with lexical variables cannot be decomposed without first extracting the lexical variables, or propgating them down the data stack manually. This often leads to a catlang which feels like "C but awkward and backwards". Worse yet, lexical variables encourage long, unfactor blocks of code, a style of programming which catlangs can punish swiftly.

:: two-sum ( seq target -- index-pair )
    0 seq length 1 - :> ( x! y! ) [
        x y [ seq nth ] bi@ + :> sum {
            { [ sum target = x y = or ] [ f ] }
            { [ sum target > ] [ y 1 - y! t ] }
            [ x 1 + x! t ]
        } cond
    ] loop
    x y = { } { x y } ? ;

An implementation of the two-sum problem from Rosetta code. Operations such as x 1 + x! t, y 1 - y! t, and sum target = x y = or cannot be extracted to their own definitions without modifying the call site. The variables x and y are trapped to the lexical scope of two-sum.

However, non-lexical bindings can enable an escape hatch without compromsing concatenation. Some examples of this are Factor's namespace stack and PostScript's dictionary stack. Feature such as these enable dynamically shifting the current context values and words are accessed in. Scopes can be pushed and popped as needed allowing named values to propgate across function boundaries.

A current design being explore for high-level catlangs is providing a system of multiple named stacks that propgate alongside the data stack. These stacks can be summoned as needed. Then, value can be pushed, peeked, and popped from them.

>x -- push to x from data stack
x> -- pop from x to data stack
@x -- peek value at top of x, same as x> dup >x
=x -- replace value at top of x, same as x> drop >x

An example of a possible notation for operating with named stacks.

Since they are stacks, they can be used to model nested scopes. A value could be pushed to the stack, the popped from it once the scope is over.

1 >x
    ( a scoep where x is 1 )
    2 >x
        ( a new scope where x is 2 )
    x> drop
    ( x is back to being 1 )
x> drop

A series of scopes with `x` bound to some value

Mirth, additionally, adds a convenience operation around named stacks to emulate lexical binding.

def foo {
    10 \x
    # x will be automatically unbound
    # once `foo` terminates
}

An example of a temporary binding in Mirth. def foo { \x ... } is the same as def foo { >x ... x> drop }

With stack effect checking, type-checking, and other forms of static analysis, invarients about a word's behavior can be strictly enforced. This can help prevent values from leaking, prevent the accidental destruction of values, or limit which bindings are current visible to a word. Additionally, with such information, the overhead of these named stacks can be elimited. For Example, Mirth can erase its stacks internally, replacing them with local variables in its C codegen.

Additionally, named stacks can allow a catlang to remove the need for constructing closure objects. A anonymous function being executed can instead access the current environment. Object-oriented catlangs such as StackTalk and Kit explore applying named stacks to objects. Objects in both languages are collections of named stacks that can be used as the current scope of word and value look up.

The full extent of named stacks are still being explored.

A general observation that I and others in the catweb have made is that catlangs generally benefit from stacks that do one-and-only-one thing. For example, Factor provides a retain stack for offloading values during operations such as dip. This frees the call stack from the responsibility of holding data, allowing for it to be specailzed into handling only return addresses. This is unlike forth where its return stack also doubles as a temporary stash.

However, Factor overloads the retain stack to be used for lexical bindings. This results in an edge case where fried quotations and lexical bindings cannot be used in tandum. Both require accessing and manipulating the retain stack, thus a point exist where they interfer with each other destructively. A possible fix for this is a dedicated lexical variable stack.

Projects That Have or Are Exploring Multistack Catlangs

Some notable projects exploring this idea and where it can push high-level catlangs. This list is loosely in order of apperance anor implementation.

Dawn was an early attempt at formalizing multistack catlangs.
Mirth is a strongly typed catlang with multistacks (called stack labels) and linear resource types. It compiles to C.
Nova a multistack programming language oriented around multiple named stacks and string rewriting.
StackTalk is a prototype-based object oriented language where objects themselves are multistack entities. It features a subject stack to enable dynamically changing scopes. The subject stack was also present in prior work by Yumakias such as Onion.
Kit is a prototype-based object oriented catlang centered around cloning objects and message passing. It featuring a focus stack in which bindings are search.

I have some toy projects such as Endless and Joyful, but they are mostly proof of concepts.