Live Rewriting Under Concatenative Programming

Introduction

This system brings together two uncommon programming paradigms at once in a live environment where program structure, visualisation, and editing align in interesting ways. It combines concatenative, rewriting, and live programming in an interactive programming environment, using each of them to compensate for weaknesses of the other, while exposing the system state for inspection and for modification through both direct manipulation and evaluation of ad hoc code.

Concatenative or compositional programming languages (typically) use stacks to store data^, with arguments and return values passed implicitly, and can offer attractive ergonomics for some applications. Each function consumes some arguments from the stack, performs its operation, and leaves its results on the stack, so a pipeline of composed functions is very straightforward, and any subsequence of terms can be trivially factored out into its own named function without any impact on behaviour (that is, a sequence can be removed into the body of a new function and replaced with the name of that function), a structure encouraged by the paradigm^. However, they are also sometimes called "write-only languages" because programs can fall into convoluted stack-juggling, where the values in the stack need complex reordering to align them correctly for the functions that will be applied to them, sometimes interwoven with program logic. Well-known concatenative languages include Forth, Joy, and Factor (Pestov et al. 2010). One concatenative language of note for this work is Mirth, which allows the use of arbitrarily many named stacks.

Rewriting programming languages operate by the repeated application of rewrite rules over some defined field of data (commonly an ordered sequence of values or a multiset). Each rule describes a pattern that can exist in that data, and then a replacement for the elements matched by the pattern. Many formal models operate like this, but are not typically regarded as programming languages in themselves, while many logic programming languages could also be analysed in this way, but explicit rewriting programming languages are relatively rare. One rewriting language of particular note for this work is Nova, which applies rewriting rules across multiple named stacks.

An interesting property of any rewriting system from a live programming perspective is that execution is discrete and memoryless: every rewrite depends only on the data currently present, so that data can be displayed or edited in between any two rule applications. This system takes advantage of synergy between some of the key traits of both paradigms:

• the "factoring" encouraged by concatenative programmers is in effect a rewriting operation, and that operation in reverse can drive the execution of the concatenative code;
• what would be many steps of stack juggling is trivially expressed as a single rewrite rule;
• sequential chained operations are tricky as rewrite rules but the norm for concatenative functions.

The rest of this essay presents a live multi-stack concatenative programming system operating over a rewriting substrate, and argues for the value of such a hybrid. In this system, 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.

The next section will briefly introduce this hybrid language design, while the following looks at the live programming environment around it, and at how the system interacts with the outside world. Section 4 addresses limitations of this approach or its implementation, and endeavours to separate which are inherent and which accidents of the current implementation. Section 5 discusses inspirations and related work, before Section 6 contemplates potential extensions.

Language Design

This programming language is simultaneously concatenative and rewriting, and any program can move freely between the two even within the same function. It is a stack-based language with multiple user-defined stacks, created implicitly if they are referenced within the program code, and two distinguished "execution" and "data" stacks. The data stack is the conventional concatenative stack, used for implicit arguments and return values. The execution stack is where the concatenative-rewriting combination comes into play and where the system becomes very interesting as a live environment: it contains all the code pending execution. When a function is called, its body is pushed onto the top of the execution stack in its place, and each step of evaluation pops one value from the top of that stack^. Functions can be overloaded for different parameter types, and specify which types of value, or literal value, are found at prefixes of any specified stack (or implicitly, the data stack).

For example, suppose we have a function inc defined that will add one to its argument. It can be declared to need a number argument from the data stack, with a body of 1 add. Consider an initial stack layout like the following:

Here, the leftmost term is at the top of the stack. The execution stack contains two atoms (indivisible opaque symbols), inc and print. The data stack contains a number value 1 and a string value "hello". With the inc function defined, the next execution step will be to note that inc is at the top of the execution stack and a number is at the top of the data stack, and to replace inc with its body: pop it off the execution stack, and in its place push on add and 1, so that the stacks now look like this:

Each step performs one operation from the execution stack, with whatever effects that step has.

The execution stack holds all of the pending code terms: atoms for function names, literal values to be pushed to the data stack when reached, or quoted sequences of terms [a 2 "C"] What is interesting about this approach is that what is essentially a standard concatenative semantics is obtained by what looks like a rewriting rule: we match the pattern

• Top of execution stack is inc
• Top of data stack is a number

and rewrite them to

• Top of execution stack is number 1
• Second of execution stack is atom add
• Top of data stack is the same number as before

In fact, we are in a rewriting system, and concatenative functions do create rewriting rules behind the scenes; we can also create our own rewriting rules that match and rewrite any prefixes of the stacks. The system has one constraint: every rewrite rule must match on an element of the execution stack.

This allows the concatenative- and rewriting-style code to interact and even be interchangeable: even a single function can be given multiple definitions, overloaded on argument types, and some of those can be defined as imperative functions and others as rewrites. When faced with a task more easily suited to one or other paradigm the programmer can switch between them trivially and compatibly, so can perform stack reordering as a rewrite leading directly into concatenative functions consuming the new arguments, for example. Below, the same simple task as in the rewriting program above is executed using conventional concatenative stack-juggling operations, which already at this scale show the increased complexity.

For ease of writing, a pattern term can be preceded by an ampersand & to include it implicitly on the right-hand side of a rule, retaining it intact for subsequent steps.

Available Terms

Items on normal stacks and in function or rewrite bodies and signatures can be one of seven types:

• atom, an opaque label. Used for function names and explicit labels.
• number, a floating-point value
• string, text, written in double quotes
• binding, a placeholder value that can be matched and unified, written $name
• stack reference, either asserting (in a signature) or pushing (in a body) a value at the top of a given stack, written stackname:valueterm. In a signature, an atom as value is used as a type label (number, atom, etc). When the stack name is omitted it is implicitly the data stack.
• quote, a sequence of terms, written in square brackets [a 1 "C" ...]. A quote at the top of the execution stack has its body spliced into the stack in its place, and a signature/pattern can match specific contents of a quote. When a quote appears within a stack reference on the execution stack, a placeholder _ can appear to splice items from the data stack into place at that position when it is evaluated.
• box, a boxed variable which can be dereferenced or updated, written in braces {5}. When a box is cloned, it continues to refer to the same variable, so updates in one place are visible in any others as well.

More or more complex types^ would likely be useful in future, but this minimal set has been enough for experimentation so far. A common pattern has been to use quotes containing specific atoms and literal values to build compound values: [circle 75 100 50 blue] is used to represent a circle centered at (75, 100) with radius 50 in one of the drawing systems described later, for example.

A function signature or rewrite pattern can match on these compound values: [circle $x $y $radius $c] will match the above value, and will make available the four bindings $x, $y, $radius, and $c to be used in the replacement text. These bindings will be replaced by the captured values when substituted in, or when they appear multiple times in the pattern every instance must bind an identical value.

Live Programming Environment

What the rewriting backend gives us is that all state can be made fully manifest: the full contents of the stacks, including the execution stack, will be displayed at all times while the program is running. Each stack is displayed horizontally, with the leftmost item the "top" of the stack. When each rule or function is applied, the effects of that application are animated: values move smoothly between stacks, fade off to the side if consumed, or slide in if they are new. In this way it is illustrated very clearly exactly where each item came from and what the current state of the program is.

There is one further aspect gained from the underlying rewriting, common to all rewriting models: the "in between" times after one rule has been applied, before applying the next, are ideal intervention points. This system allows the program to be paused, resumed, single-stepped, or run slowly or quickly (without animations).

During a pause between steps the user can directly manipulate the stack contents (again including the execution stack) by dragging items between stacks or positions in a stack, by creating new terms on the "Scratch" stack to be moved elsewhere, or by removing terms entirely. They can modify any term in-place by clicking and typing a new value within it.

Because of the memoryless nature of the model, the next execution step will pick up as though this new state was what was always there.

We can push this a little further: rather than only pure direct manipulation, we can allow another program to run within this data, with its own execution and data stacks but otherwise full access to manipulate the system state or perform behaviours. A secondary program can be created on an ad-hoc basis and run against the system state to perform complex changes or simply to obtain its outcomes.

It would be possible to take things further still: interleave the execution of multiple programs in the same space, allowing them to manipulate the shared data (or even each other). The current system has very limited support for such weaving, but this and other possibilities are discussed in the future work section below.

Implementation

A prototype implementation of this approach runs in any modern web browser, with the backing code and interface built with web technologies. A user can enter code as text, single-step or run the program fully, and pause execution, and can edit the stacks by drag-and-drop or by creating new terms in the scratch stack.

Outside Interactions

In order for the program to do anything other than move data around, it is necessary to be able to do something with an effect outside the program. There are two routes available, and used, to do this: most basically, some of the concatenative-style builtin functions are implemented with platform-native code and have side effects, or expose primitive operations not otherwise expressible within the language (like arithmetic). The more interesting route is that one or more of the stacks may be bound to some outside effect: they can either automatically contain values from the outside world (for example, user input events) ready to be popped, or pushes can represent instructions to the outside, or both. We can zoom in on two particular bound stacks to illustrate both sides of that coin.

Painter's Algorithm

The prototype system defines a paint stack where the stack contents and ordering correspond to simple "painter's algorithm" drawing layers. The stack can contain many items like [circle 75 100 50 blue] or [rect 20 60 40 40 red]

Manipulations of the stack directly impact the drawing: swapping the top two elements, for example, will alter which of the two paints over and occludes the other. Removing an item from the stack will erase its contribution to the image. Both programmatic and manual changes to the stack will have an immediate impact.

:paintswap paint:$x paint:$y -> paint:$y paint:$x


paint:[circle 100 100 50 blue] paint:[rect 100 100 100 50 red] paintswap paintswap

In the prototype, this stack is backed directly by an SVG image: the circle and rect above are exactly the SVG element names, and outside changes to the elements in the image will also be reflected in the stack for both the visualisation and any code. This stack is simulated by the runtime system, being used identically to the other stacks by any code in the language, but using distinct backing behind it to allow for special semantics. In other respects, it behaves like any other stack to the code and to the user, permitting the same live interactions as other stacks, including updates that cause live changes to the displayed image.

:move step:1 $x $y paint:[polygon $fill $stroke $a $b $c $d $e $f] -> paint:[polygon $fill $stroke $x $y $c $d $e $f] step:2
:move step:2 $x $y paint:[polygon $fill $stroke $a $b $c $d $e $f] -> paint:[polygon $fill $stroke $a $b $x $y $e $f] step:3
:move step:3 $x $y paint:[polygon $fill $stroke $a $b $c $d $e $f] -> paint:[polygon $fill $stroke $a $b $c $d $x $y] step:1


:dx1  = {-1}


:dy1  = {1}


:dx2  = {1}


:dy2  = {-1}


:dx3  = {-1}


:dy3  = {1}


:dx1b  = {1}


:dy1b  = {-1}


:dx2b  = {-1}


:dy2b  = {1}


:dx3b  = {-1}


:dy3b  = {-1}


:flip :box = unbox -1 mul rebox drop


:advance step:1 paint:[polygon $fill $stroke $x $y $c $d $e $f] = dy1 debox $y add 1 199 outside? [dy1 flip] dx1 debox $x add 1 319 outside? [dx1 flip] move advance
:advance step:2 paint:[polygon $fill $stroke $a $b $x $y $e $f] = dy2 debox $y add 1 199 outside? [dy2 flip] dx2 debox $x add 1 319 outside? [dx2 flip] move advance
:advance step:3 paint:[polygon $fill $stroke $a $b $c $d $x $y] = dy3 debox $y add 1 199 outside? [dy3 flip] dx3 debox $x add 1 319 outside? [dx3 flip] move swap-paint advance2


:advance2 step:1 paint:[polygon $fill $stroke $x $y $c $d $e $f] = dy1b debox $y add 1 199 outside? [dy1b flip] dx1b debox $x add 1 319 outside? [dx1b flip] move advance2
:advance2 step:2 paint:[polygon $fill $stroke $a $b $x $y $e $f] = dy2b debox $y add 1 199 outside? [dy2b flip] dx2b debox $x add 1 319 outside? [dx2b flip] move advance2
:advance2 step:3 paint:[polygon $fill $stroke $a $b $c $d $x $y] = dy3b debox $y add 1 199 outside? [dy3b flip] dx3b debox $x add 1 319 outside? [dx3b flip] move swap-paint advance


:swap-paint paint:$a paint:$b -> paint:$b paint:$a




step:1 paint:[circle 160 100 10 green] paint:[polygon none blue 75 100 200 180 300 10] paint:[polygon none red 300 150 150 60 90 180] advance

Keyboard Events

The prototype also provides an input stack which automatically receives representations of keys being pressed within the drawing area. For the duration of the "H" key being pressed, for example, a quote [key H] will be in the stack, available to be matched against. When the key is released, this item is removed from the stack automatically. In both cases, the stack change occurs "between" steps, so an inconsistent stack is never visible to code.

When multiple keys are pressed at once, all of them will appear in the input stack. The most recent key will appear at the top, but released keys will be removed from any position.

When a function matches and removes a keypress, the key will automatically be re-added to the stack before the next step is taken (provided it is still depressed). Between the drawing stack and key events it is possible to create a simple game or drawing application relatively easily. The program will be an infinite tail recursion — which is costless in this evaluation model — with multiple overloads of the recursive function. For example, a function can be defined:

:go input:[key W] paint:[circle $x $y $r $c] = $y 5 sub $x recircle go
:go input:[key A] paint:[circle $x $y $r $c] = $y $x 5 sub recircle go
:go input:[key S] paint:[circle $x $y $r $c] = $y 5 add $x recircle go
:go input:[key D] paint:[circle $x $y $r $c] = $y $x 5 add recircle go
:go = 50 wait go

This function will have an overload for each key to be responded to, matched on the input stack. These overloads also match a circle on top of the paint stack, extract the coordinates from inside, and call a function or rewrite rule to push a new circle with slightly different coordinates, in effect moving the shape around in response to input. The first-defined matching overload will be evaluated, putting its body onto the execution stack. All of the overloads end with a call to the same function again, ready for more input.

:recircle $x $y paint:[circle $a $b $c $d] -> paint:[circle $x $y 10 green]


:go input:[key W] paint:[circle $x $y $r $c] = $y 5 sub $x recircle go
:go input:[key A] paint:[circle $x $y $r $c] = $y $x 5 sub recircle go
:go input:[key S] paint:[circle $x $y $r $c] = $y 5 add $x recircle go
:go input:[key D] paint:[circle $x $y $r $c] = $y $x 5 add recircle go
:go = 50 wait go


paint:[circle 160 100 10 green] go

Persistence

A benefit of the approach of this system is that the program can be "frozen" at any time and evaluated more later, giving a simple sort of persistence and enabling some of the live programming discussed above. The inherent discrete state transitions enable this and to some extent blur the line between when the program is running and when it isn't. However, when the program is run from scratch, it always starts from a blank slate and empty stacks. It would be interesting and sometimes useful to have a little more persistence, and to blur the line yet further.

To that end, we make an extension to the boxed variable type described earlier — or make explicit what was latent originally. A box literally written in the source code, {5} It will move to the data stack when it reaches the top of the execution stack, and the inner value can be accessed or updated at that point. It can be duplicated and the duplicates will access the same shared value. This includes the box written in the source code!

When a box that was written in the source code (as opposed to created at run time with the box function) is updated, the change affects the source code as well, updated in-place. The next time the program is run afresh, the new value will always have been present as far as that execution is concerned. In this way, changes can be accumulated across multiple evaluations of the program, explicitly within the text of the program itself and able to be commented or given a descriptive function name. This could be used, for example, to cache recently-used computations, or to maintain the high score for a simple game.

In this way the boundaries between the static artifact of source code, the frozen run-time state of a paused program, and the actively evaluating code become more indistinct than before. As a live environment, there is an extent to which even when the program is not running there is still live code state to access, and the reverse as well. These static boxes will not be useful all the time and should probably be used with care, but open up some interesting pathways to explore further.

Limitations and Drawbacks

This system presents some interesting takeaways that could be factored into other systems, but has some definite weaknesses as well. This section will discuss a selection of key issues identified, and how they fit into the takeaways from this work.

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.

Inspirations and Related Work

This system is influenced by both concatenative and rewriting prior work, as well as recent advocacy to take esoteric programming languages seriously and explore hybrids of less-common paradigms for potential synergies. 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.

Dawn (Maddox 2022) represents an attempt at formalising the semantics of a multi-stack concatenative language, but ultimately the language faced issues of complex type-checking and legibility. Other multi-stack concatenative languages include StackTalk, an object-oriented system where objects are collections of named stacks, which permits multiple stacks of the same name to exist isolated from one another. This approach might be a constructive extension to the "quotations with fixed atoms" compound-values pattern, but is not part of this system currently.

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. A visualisation framework has been created for the KKJ formal semantics (Steingartner et al. 2026) that gives step-by-step display of the state and transitions of a formal concatenative calculus, although this is primarily an execution trace rather than a dynamic display. Another concatenative-visual system that does have run-time display of state is the In-Line Compositional Visual Programming system (Homer 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 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 this system. Nova's stacks are always of tuples of atoms, which could be analogous to a stack of unnested quotes in this 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 elsewhere, 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 2026) : 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. A wholly graphical rewriting system is Bitpict (Furnas 1991), where graphical rules trigger pixel-level rewrites to effect computation. These rules are two-dimensional, unlike the single-dimensional rules of our system or the cardinality-based Tote model, and conceptually could accommodate live raster editing during evaluation; the kinds of animations created above could arise as direct products of rewrites on the visible image itself.

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 this system would be adding or removing stack frames and return pointers, which is not possible in virtually all such debuggers.

Possible Extensions and Future Work

In the same way that the system allows executing ad-hoc other programs sharing the state stacks, it would be possible to execute multiple programs automatically. These could be interleaved round-robin style, one step apiece at a time. They could also operate preemptively, perhaps taking over briefly in response to an event, which would enable some different styles of programming. The interleaved style could be particularly interesting for programmatic music or visual art.

The language currently supports a minimal range of data types for stack values, with no extensibility other than encoding compound values in quotes. Both additional basic types and more advanced compound types could be useful. Some functions definitions would be cleaner if user-defined disjunctive types were available to match many distinct values at once.

There are a wealth of possible external bindings to stacks that could be implemented. These could range from using the stack merely as an input/output "port" to the kind of direct one-to-one mapping of the painter's algorithm drawing stack. One possibility that has not been explored is binding a stack to another program's stack across a network, which would enable significantly different kinds of program.

Presently, the system operates only over stacks of data, in the common concatenative style. An interesting extension would be to allow some of the stacks to be declared to have alternative semantics, such as queue, set, or multiset. These could also simplify some programs where, for example, preserving the order of events for processing using queue semantics is useful. Very preliminary explorations have shown interesting behaviours, but more work is needed to solidify the required semantics of mixing these models.

For sets and multisets, pattern matching would need to be on any item in the collection, rather than the unique top or front of a stack or queue. Multiset-based rewriting systems do exist, from at least as early as Conway's FRACTRAN (Conway 1987) to the aforementioned Tote. Those systems are built around that conceit, while incorporating them within another might lead to complications, but the unordered semantics are worth exploration.