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 1 and execute itself, effectively producing an infinite series of 1s 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.
==See also==
* Equipage
==External resources==
* 
Category:Languages
Category:Stack-based
Category:Unknown computational class
Category:Implemented
Category:No IO
Category:2012