Multistack Concatenative Programming Languages

# Multistack Concatenative Programming Languages Source: [https://www.sheeeeeeeep.art/multistack-catlangs.html](https://www.sheeeeeeeep.art/multistack-catlangs.html) > *jotted out, 2026\-08\-07* [Concatenative programming languages](https://www.sheeeeeeeep.art/concatenative-programming.html)\(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 == f1 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](https://www.kevinalbrecht.com/code/joy-mirror/j01tut.html)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"](https://concatenative.org/wiki/view/Concatenative%20language/Name%20code%20not%20values)\. [Juxta](https://www.sheeeeeeeep.art/juxta-the-combinator-cat.html)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](https://rosettacode.org/wiki/Two_sum)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](https://www.sheeeeeeeep.art/lang-things-current-object.html)can enable an escape hatch without compromsing concatenation\. Some examples of this are[Factor's namespace stack](https://docs.factorcode.org/content/article-namespaces.html)and[PostScript's dictionary stack](https://fifth-postulate.nl/postscript-whisperer/guide/tool/dictionary.html#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](https://stk.junglecoder.com/)and[Kit](https://kit.quiltro.org/)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](https://webring.catlang.social/)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](https://github.com/factor/factor/issues/118)\. 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](https://www.dawn-lang.org/)was an early attempt at formalizing multistack catlangs\. - [Mirth](https://git.sr.ht/~typeswitch/mirth)is a strongly typed catlang with multistacks \(called stack labels\) and linear resource types\. It compiles to C\. - [Nova](https://nova-lang.net/)a multistack programming language oriented around multiple named stacks and string rewriting\. - [StackTalk](https://stk.junglecoder.com/)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](https://github.com/yumaikas/onion)\. - [Kit](https://kit.quiltro.org/)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](https://codeberg.org/CapitalEx/Endless)and[Joyful](https://codeberg.org/CapitalEx/joyful), but they are mostly proof of concepts\.*