Wagon
Wagon is a stack-based language created by Chris Pressey in 2019. It is "purely concatenative" in the sense of Carriage and Equipage (there are no nested blocks) but it is also "second-order concatenative": instead of functions that take states to states, the symbols of a Wagon program represent functions that take functions from states to states, to functions from states to states. Wagon calls these "macros".
Since a Wagon program is a macro, it expects a function and returns a function. But when we run a program, typically we want to give it an initial state, and we expect the result to be a final state. So by convention, to run a Wagon program means to apply the macro that the Wagon program represents to the identity function, and apply the resulting function to the initial program state.
Program states in Wagon are unbounded stacks of unbounded integers.
Primitives
Wagon provides eleven built-in macros which can be composed to form Wagon programs.
| Symbol | Description |
|---|---|
i
|
Takes an operation o and returns an operation which performs o then pushes a 1 onto the stack. |
I
|
Takes an operation o and returns an operation which pushes a 1 onto the stack then performs o. |
s
|
Takes an operation o and returns an operation which performs o then pops a from the stack then pops b from the stack and pushes b - a. |
S
|
Takes an operation o and returns an operation which pops a from the stack then pops b from the stack and pushes b - a then performs o. |
p
|
Takes an operation o and returns an operation which performs o then pops a value from the stack and discards it. |
P
|
Takes an operation o and returns an operation which pops a value from the stack and discards it, then performs o. |
d
|
Takes an operation o and returns an operation which performs o then duplicates the top value on the stack. |
D
|
Takes an operation o and returns an operation which duplicates the top value on the stack then performs o. |
r
|
Takes an operation o and returns an operation which performs o then pops a value n from the stack, then pops n values from the stack and temporarily remember them, then reverses the remainder of the stack, then pushes those n remembered values back onto the stack. n must be zero or one. |
R
|
Takes an operation o and returns an operation which pops a value n from the stack, then pops n values from the stack and temporarily remember them, then reverses the remainder of the stack, then pushes those n remembered values back onto the stack, then performs o. Again, n must be zero or one. |
@
|
Takes an operation o and returns an operation that repeatedly performs o as long as there are elements on the stack and the top element of the stack is non-zero. |
Whitespace is also allowed; it corresponds to the identity macro, i.e. it has no effect on the resulting program.
One result of being able to write only macros, not functions, is that Wagon programs can have nested loops, but only one loop may be nested inside any loop.
Computational class
Despite the restriction to strictly-singly-nested loops, Wagon has been shown to be Turing-complete, since any Tag system can be compiled to a Wagon program (see link below.)