Carriage
Carriage is a concatenative programming language designed by Chris Pressey in mid-November 2012. It is the result of trying to devise a "pure" concatenative language, i.e. one where the rule "concatenation = function composition" is taken to be strictly literal and universal (with no exceptions such as allowing nested quoted programs.) It falls short of that goal somewhat, but it has some mildly unusual properties, so it is presented here as an esolang.
Note that this article describes Carriage version 0.1. It will not be version 1.0 until the author assures himself that there are no more instructions that are needed to write simple programs, and no fatal flaws.
State
The state of a Carriage program is a stack of unbounded size. Each element on the stack may be of one of three types:
- an unbounded integer
- a function which takes stacks to stacks
- an instruction symbol
Syntax
Carriage defines nine instruction symbols. Each instruction symbol has an interpretation as a function which takes stacks to stacks.
Any sequence of instructions (including an entire Carriage program) has two interpretations:
- the code interpretation, which is the composition of the functions represented by each of the instruction symbols, in the manner of concatenative languages. For example, if the instruction symbol A has the interpretation f(s), and the instruction symbol B has the interpretation g(s), then the sequence AB has the interpretation g(f(s)). A sequence of length zero is taken to be the identity function.
- the data interpretation, where the sequence of instruction symbols is taken to be a stack of instruction symbols, with the first symbol in the sequence at the bottom of the stack. A sequence of length zero is taken to be an empty stack.
Whitespace has no meaning; the code interpretation of whitespace is the identity function, and the data interpretation does not introduce any instruction symbol onto the stack. However, attempting to take the code interpretation of any other symbol which is not defined by Carriage will cause the program to explode.
Semantics
Evaluation of a Carriage program can be summed up in one sentence: The function which the program represents under the code interpretation is applied to the stack which the program represents under the data interpretation.
The result of executing a Carriage program is always either the stack to which the initial stack was mapped by the function, or an explosion.
The instruction symbols defined by Carriage are listed below. The functions to which they are mapped by the interpretation function are described in operational terms for simplicity of explanation, but they are really functions which take stacks to stacks.
1("one") pushes the integer 1 onto the stack.
~("pick") pops an integer n off the stack, then copies the element which is n (zero-based) positions deep in the stack, and pushes that copy onto the stack. If n is negative or greater than the size of the stack or not an integer, the program explodes. If the element to be copied is an instruction symbol, the program explodes.
\("swap") pops an element a off the stack, then pops an element b off the stack, then pushes a back onto the stack, then pushes b back onto the stack.
$("pop") pops an element off the stack and discards it.
#("size") counts the number of elements into an integer k then pushes k onto the stack.
+("add") pops an integer a off the stack, then pops an integer b off the stack, then pushes the sum (a + b) onto the stack. If either a or b is not an integer, the program explodes.
-("sub") pops an integer a off the stack, then pops an integer b off the stack, then pushes the difference (b - a) onto the stack. If either a or b is not an integer, the program explodes.
@("slice") pops an integer k off the stack, then pops an integer p off the stack. It then copies k instruction symbols from the stack into a sequence, starting at stack position p, zero-based, measured from the bottom of the stack. It then applies the code interpretation to this sequence to obtain a function. It then pushes this function onto the stack. If k or p is not an integer, or k is less than 0, or k is greater than 0 and either p or p+(k-1) refers to some position not inside the stack proper, or k is greater than 0 and any of the elements between p and p+(k-1) inclusive are not instruction symbols, the program explodes.
!("apply") pops a function f off the stack and applies f to the stack to obtain a new stack. If f is not a function the program explodes.
If the stack is empty any time an attempt is made to pop something off of it, the program explodes.
Examples
Basic Stack Manipulation
As a simple example, the Carriage program
111-~+
will be turned into a function which we might spell out in, say, Erlang, as
fun(S) -> add(pick(sub(one(one(one(S))))))
which will be applied to a stack
(fun(S) -> add(pick(sub(one(one(one(S)))))))(["1","1","1","-","~","+"])
which could be stated more succinctly as
add(pick(sub(one(one(one(["1","1","1","-","~","+"]))))))
and whose evaluation could be depicted as
add(pick(sub(one(one(["1","1","1","-","~","+",1]))))) add(pick(sub(one(["1","1","1","-","~","+",1,1])))) add(pick(sub(["1","1","1","-","~","+",1,1,1]))) add(pick(["1","1","1","-","~","+",1,0])) add(["1","1","1","-","~","+",1,1])
finally evaluating to the result stack
["1","1","1","-","~","+",2]
(Note that stacks are being depicted bottom-to-top. I realize that's not how you'd typically implement them as lists in a functional language. Please just ignore that detail.)
Function Creation and Application
The previous example does not really demonstrate the power of the language. For that, we need to show how apply, and more importantly slice, work. Take the program
11+$11+111+@!
The result stack of evaluating this program is
["1","1","+","$","1","1","+","1","1","1","+","@","!",3]
The interpretation of the first four instruction symbols is just the identity function (create 2 then pop it, leaving the stack as it was.)
The next seven instruction symbols leave [2,1,2] on the stack.
The slice instruction then pops k = 2, p = 1, and retrieves a sequence of
2 instruction symbols from the stack starting from position 1 (that is, the element on top of the bottom element of the stack.) We can
see that that sequence is 1+. It then applies the code interpretation
to that sequence to get a function (which pops a value off a stack and
pushes the successor of that value back onto the stack) and it pushes
this function onto the stack, which now looks like this:
[...,"!",2,<fn>]
Finally, the apply instruction pops the function, and applies it to the stack: the 2 is popped, 1 is added to it, and the result, 3, is pushed back on.
Note on "slice"
We note that slice has the practical effect of delimiting some part of the program into a "subroutine" of sorts. However, there are some unusual consequences here.
One is that these "subroutines" may overlap.
Another is that these "subroutines" may be of variable size, as k need not be a constant. This may be used to affect a conditional of sorts. (k is allowed to be zero, in which case the slice is a zero-length sequence whose interpretation is the identity function.)
Another is that, in a terminating and non-exploding program, every "subroutine" must be evaluated at least once -- because the entire program is turned into a single function (which is applied to the initial stack) and this single function contains all of its possible subroutines.
In the above example, we anticipated this, and wrote our "subroutine" so that
the first time it is evaluated, it has no effect. In fact, through
lucky coincidence, if we remove it from the program, the second and
third instruction symbols are still 1 and +, so we didn't need to
go to such lengths. But this is in general not the case.
Note also that the restriction on the pick instruction, that it not be able to pick instruction symbols from the stack, was introduced to prevent construction of new "subroutines" which did not exist in the original program. (Instruction symbols can still be popped and swapped, but these modifications to the "program on the stack" are quite minor.)
Note also that, despite being a concatenative language, and thus supposedly mathematically pleasing, evaluating a "subfunction" with slice and apply has a distinctly machine-language feel to it (similar perhaps to Aubergine and Cfluviurrh), what with the absolute indexes into the stack and all. One small saving grace is that adding whitespace to the program does not change the indexes of the "subroutines".
Infinite Loop
111-@11-~!$11111++++11-~@11-~!
Explanation:
111-@
Push identity function (zero-length slice at position 1) onto the stack.
11-~!
Duplicate object on the stack and apply it. (This is our subfunction.)
$
Remove identity function from the stack.
11111++++11-~@
Push our subfunction (slice at position 5 with length 5) onto the stack.
11-~!
Duplicate object on the stack and apply it. This applies our subfunction, with our subfunction already on the stack; so the subfunction will duplicate it, then apply its copy, ad infinitum. (A cleverer implementation might be able to use this last snippet of code as the subfunction.)
Finish with Empty Stack
Any program which consists entirely of pops evaluates to an empty stack.
$$$ => ["$","$","$"] => ["$","$"] => ["$"] => []
It would, however, be an interesting exercise to write a generic program which always ends with a completely empty stack. (Or show that one cannot be written.)
Sketch of a Truth-machine
Start the program with either 1 to simulate a 1-input or 11- to simulate a 0-input.
Push p, the position of a subfunction to be written, onto the stack.
Use 1~ to pick the input value.
Use 11-~11-~11-~11-~ to have five copies of it on the stack.
Use ++++ to sum those copies. If the input was 0, it will be 0, and if the input was 1, it will be 5.
Use @ to create a function. If the input was 0, this will just be the identity function; if it was 1, it will be our subroutine.
Use ! to apply the function. If it was the identity function, the original 0 will remain on the stack (consider it "outputted".) If it was our subroutine, our subroutine will push a 1 onto the stack and call itself.
We can at this point define our subroutine. It should push p onto the stack, then 5, then do @1\!.
Then we surround our subroutine with instructions so that, if it is evaluated "inline" (after determining the input was 0), it has no effect. Of course, since it unilaterally applies a function that it created itself, this is easier said than done.
And of course, the numbers here don't entirely work out either, because our subroutine is going to be a lot more than 5 symbols long. But in principle, we ought to be able to push suitable p and k onto the stack, while devising ways to push them onto the stack that are smaller than k.
Truth-machine implementation
111-@1\11-~!$$11+1+1+1+\1+1+1+1+1+1+@11-~!$$1-
We start with 0 or 1 on the stack, which will be called the truth argument.
111-@
Create a void (identity) slice.
1\11-~!
Behavior of this piece of code depends on the top of the stack.
- If it is equal to the identity function (as it is the first time it is executed), it will leave
[... <> 1]on the stack. - If it is equal to a slice of itself, it will push
1and execute itself, effectively producing an infinite series of1s on the stack. - If it is equal to a slice of itself without the trailing
!, it will leave[... 1 <1\11-~> <1\11-~>]on the stack.
$$
Clean the stack of the [... <> 1] junk left by the above function.
11+1+1+1+
Push 5 (that is, the starting index of the above function).
\1+1+1+1+1+1+
Swap and add 6 to the truth argument (6 or 7).
@11-~!
Slice, duplicate and apply the slice defined by p = 5 and k = 6 + truth argument.
If k = 6, then the slice lacks the trailing ! defined above.
$$1-
If the code reaches this point, then the above application terminates and as such the truth argument was 0. We then clear the stack of the two slices, then subtract 1 to the 1 pushed during the application and end the code.
Future work
We leave the further problems of showing that a (non-pathological) conditional can be constructed, that a factorial function can be written, and that Carriage is Turing-complete, as exercises for the reader. (The author suspects that some of these are possible, but hasn't had the time to actually sit down and figure them out. It is very likely one or two more instructions will need to be added. It's also possible that there is a fatal flaw in here somewhere!)
Implementations
- Carriage/Carriage.hs, a quick-and-dirty implementation in Haskell.
- Carriage/carriage.ml, an implementation in Ocaml.