Presented at the 12th Workshop on Live Programming (LIVE 2026). https://doi.org/10.5281/zenodo.24409800
Concatenative programming languages offer attractive ergonomics for some applications, but are also sometimes called "write-only languages" because programs can fall into convoluted stack-juggling that is difficult to follow. Rewriting systems also offer some very straightforward expressions of some classes of problem, but face complex workarounds in others. Many of these strengths and limitations are complementary: advanced multi-step stack-juggling is complex and hard to follow as concatenative functions, but would be trivially expressed as rewrites over the stack, while rewriting systems often make negation and ordinal comparisons complicated.
Here we present a multi-stack concatenative programming system operating over a rewriting substrate: functions can be defined in conventional concatenative style, or as rewriting operations, or even combinations of both, and all application proceeds by rewriting the remaining program and state. In doing so, new possibilities for run-time intervention are exposed: the program can be paused and both state and pending code can be edited, including the equivalent of the call stack, but yet more dynamic options are also available, including evaluating other programs ad hoc *within* the main program's state. We also identify bindings between program-level stacks and external resources that can allow bidirectional direct manipulation of visible state.
https://michael.homer.nz/notes/live-rewriting-concatenativeThe combination of three less-common approaches to programming — concatenative, rewriting, and live — creates a very interesting interactive environment where there is a clear story for how manipulations are meaningful, and the strengths of each paradigm are complementary. Both concatenative and rewriting languages are uncommon on their own and still more uncommon in live environments, but the prototype here suggests it is worth pursuing these kinds of integration.
This system is influenced by both concatenative and rewriting prior work. On the concatenative side, a particular influence is Mirth, a typed multi-stack concatenative language with conventional textual syntax. Mirth highlights the value of ad-hoc stacks to cleaner concatenative programs, allowing new stacks to be invented by the programmer as needed for application-specific purposes, which is borrowed here. In other respects, Mirth is a conventional textual concatenative language with static typing, effects, and more advanced language features, without any specific live display of state.
Other influences on the concatenative side are R3, a Forth derivative that influenced the design of conditionals, and colorForth. colorForth's (Moore 2009) "magenta variables", which persist run-time changes to their values in the source code, influenced the "static box" functionality of this system. Neither of these provides visual representation of the stack at run time. Another concatenative-visual system that does have run-time display of state is the "In-Line Compositional Visual Programming" system (Homer, PX 2024) which foregoes stacks entirely in favour of an unusual inlining of data within code, but does permit multiple of these code-data "tracks" to be created and shown.
On the rewriting side, the nearest influence is the Nova rewriting language and system presented at LIVE 2025 (Gardner, LIVE 2025). Nova is a fully rewriting-based system with multiple stacks as the rewrite terms: the program execution is by applying rewrite rules that examine prefixes of those stacks and push new items onto them. This is a "pure" rewriting model, unlike the hybrid one of our system. Nova's stacks are always of tuples of atoms, which could be analogous to a stack of unnested quotes in our system, and Nova rewriting rules could be transposed into the system in this way. In the other direction, while Nova does not have a concatenative (or other) language embedded within, it would be possible to simulate one: rewrite rules that match the top 1-tuple of the "execution" stack and whatever prefixes of the other stacks could give the same stack effects as applying those functions, up to primitive operations. However, conditionals, quoting, and some other elements would not translate straightforwardly. Nova's approach to binding access to external resources to special stacks (such as for drawing and input) is directly analogue to the approach used here, although the direct "painter's algorithm" use of a stack for drawing is novel.
The live editing in this system has parallels elswhere, but seems to be novel as a whole. Visual systems for concatenative programming are very rare to begin with, and those we are aware of do not focus on the "mid-execution" direct manipulation that is present in this system. Live rewriting systems are more common. An interesting one is Tote (Hundred Rabbits, 2025): a grid in which sprites can be placed, and rewriting rules that apply transformations to the multiset of sprites on-screen, with the ability to trigger particular or general rewrites through direct-manipulation interactions (clicks, drops, or steps). Our system does not have any way to interactively trigger anything but the unique next execution-stack function, although it does allow the user to create a new item ad hoc and place it into that next-up position. Interactively triggering either or both of concatenative and rewriting rules "at" a position in the displayed data would be an interesting extension to our system, but is not currently present.
Further afield, a number of interactive debuggers for traditional languages do display and sometimes allow editing of stack variables of a paused program. However, analogous to editing the execution stack in our system would be adding or removing stack frames and return pointers, which is not possible in virtually all such debuggers.
The visual display of stack values becomes unwieldy for large stacks. There are two significant places where this comes up: the first is complex recursion, because the "expansion"-based evaluation of user-defined functions results in the entire function body being pushed onto the execution stack at every layer. While in the tail-recursive case this is free, in any other a lengthy chain of trailing operations will accumulate, which is both hard to navigate and a performance problem for the current rendering system. The second common place is in drawing code: a naive painting or image-rendering program might create many small shapes each covering only a few pixels of display. The current implementation backs the "paint" stack directly with an SVG image, so this results in an image with very many children, as well as the many `[circle x y r color]` blocks displayed in the paint stack that obstruct the system performance.
Some elements of this seem to be inherent to the design and the approach being taken: deep body recursion will inevitably result in lengthy execution stacks of queued operations. In most programming systems, recursion may result in stack frame allocation, but those are not generally displayed eagerly nor exactly proportional in size to the body of the function. There are obvious workarounds to some of the problems (e.g. the current system inhibits step animation when any stack has more than 100 items), but the navigability and comprehensibility issues remain.
While the combination of concatenative and rewriting models compensates for some of the drawbacks of each, and the live environment attacks a few more, these are still uncommon and unconventional programming paradigms for a reason. Being able to sidestep some common obstacles (such as replacing complex stack juggling with a single rewrite rule) should be genuinely beneficial, but still involves dealing with two inherently tricky methodologies at once instead of one, or zero.
At one point in development static typechecking was a goal, but the combination of the two paradigms makes this much harder than otherwise. Neither paradigm is particularly straightforward to begin with: statically-typed concatenative languages are rare and practical typed rewriting systems more so. Neither is impossible and mechanical or formal systems in those veins (not intended for manual editing, such as Java bytecode) do exist, but the techniques that help in one paradigm fall over when faced with interference from the other. Resolving this has been left for future work for now.