Stack Cats
Stack Cats (abbreviated as SKS) is a stackbased, reversible programming language developed by user:Martin Ender and user:Sp3000. It was originally conceived of for a languagedesign challenge on Code Golf Stack Exchange, but later designed and developed independently of that.
Contents
Basics
Every program in Stack Cats is written on a single line, where each character is a command. Being a reversible programming language means that for every command there is a way to undo it. The language is designed such that any snippet of commands can be undone by mirroring it. This means that the string of commands is reversed and all characters that come in symmetric pairs are swapped (()
, {}
, []
, <>
, \/
). For instance, the snippet >[[(!)/
undoes the snippet \(!)]]<
. Therefore, Stack Cats programs are made up exclusively of characters which are either selfsymmetric (in most fonts) like _!:I
or which come in pairs, i.e. (){}[]<>\/
. Note that from a theoretical standpoint, selfsymmetric characters compute involutions, while symmetric pairs compute bijections (and their inverses).
Syntax
There are only two syntactic rules for Stack Cats:
 Every valid program must have mirror symmetry. That is, if the entire program is mirrored (see above), it must remain unchanged. This has a few implications. a) Every Stack Cats program computes an involution on the global memory state (since every program is its own inverse). b) Every evenlength program computes the identity (i.e. a cat program) provided that it terminates, since the second half undoes the first. c) Every nontrivial program has odd length. If we call the command in the centre of the program
A
, then every such program has the structurepAq
, wherep
is an arbitrary program andq
computes its inverse. Note thatA
needs to be one of the selfsymmetric characters, so it is itself an involution. Hence, programming in Stack Cats is about finding a functionp
which transforms a very simple involutionA
into the desired program.  Parentheses,
()
, and braces,{}
, need to be balanced correctly, as they form loops. They can be nested arbitrarily but not interleaved like({)}
. ([]
and<>
can appear individually and don't need be matched.)
Memory model
Stack Cats operates on an infinite tape of stacks. The tape has a tape head which can be moved and points at the "current" stack. Commands tend to operate locally on or near the tape head. The stacks store arbitraryprecision (signed) integers and contain an implicit, infinite amount of zeros at the bottom. Initially, all stacks but the one where the tape head starts are empty (apart from those zeros).
I/O
To ensure full reversibility, Stack Cats has no I/O commands, as these sideeffects cannot be reversed cleanly. Instead, when the program starts, all input (which has to be finite) is read from the standard input stream. A 1
is pushed on the initial stack, and then all the bytes from the input are pushed, with the first input byte on top and the last input byte at the bottom (just above the 1
).
At the end of the program (provided it terminates), the contents of the current stack (pointed at by the tape head) are taken modulo 256 and printed as bytes to the standard output stream. Again, the value on top is used for the first byte and the value at the bottom is used for the last byte. If the value at the very bottom is 1
, it is ignored.
Execution Options
Every specificationcompliant interpreter should provide the following options for executing Stack Cats programs:
 For input, read decimal signed integers instead of bytes. If this option is used, the input is scanned for numbers matching the regular expression
[+]?[09]+
and push those instead of byte values. (Still with a1
at the bottom.)  For output, print decimal signed integers instead of bytes. Every integer is followed by a single linefeed (0x0A). (Still, an optional
1
at the bottom is ignored.)  Implicitly mirror the source code. Since the second half of every valid Stack Cats program is redundant, there should be an option to omit everything after the centre character. With this option, for example the source code
:>[(!)
would represent the full Stack Cats program:>[(!)(!)]<:
. Note that the final character isn't mirrored, because that would result in a trivial evenlength program.
Commands
In the following section, "the stack" refers to the stack currently pointed at by the tape head, and "the top" refers to the top value on that stack.
Control Flow
Remember that ()
and {}
always have to be balanced correctly.

(
: If the top is zero or negative, jump past the matching)
. 
)
: If the top is zero or negative, jump back past the matching(
. 
{
: Remembers the top. 
}
: If the top differs from the value remembered at the matching{
, jump back past the matching{
(without remembering a new value).
In summary, ()
is a loop which is entered and left only when the top is positive, whereas {}
is a loop which always iterates at least once and stops when the value from the beginning is seen again at the end of an iteration.
Arithmetic


: Negate the top (i.e. multiply by1
). 
!
: Take the bitwise NOT of the top (this is equivalent to incrementing and negating). 
*
: Toggle the leastsignificant bit of the top. In other words, computex XOR 1
. 
_
: Popa
, popb
, pushb
, pushb  a
. 
^
: Popa
, popb
, pushb
, pushb XOR a
.
Stack manipulation

:
: Swap the top two elements of the stack. 
+
: Swap the top and third elements of the stack. 
=
: Swap the top elements of the two adjacent stacks. 

: Reverse all values on the stack down to (and excluding) the first zero from the top. 
T
: If the top is nonzero, reverse the entire stack (down to and including the bottommost nonzero value).
Movement and tape manipulation

<
: Move the tape head left one stack. 
>
: Move the tape head right one stack. 
[
: Move the tape head left one stack, taking the top with it. 
]
: Move the tape head right one stack, taking the top with it. 
I
: If the top is negative, do[
, if it is positive, do]
, if it is zero, do nothing. 
/
: Swap the current stack with the stack to the left, and move the tape head left. 
\
: Swap the current stack with the stack to the right, and move the tape head right. 
X
: Swap the stacks left and right of the current stack.
Computational Class
Stack Cats is Turingcomplete. To show this, we first show that it's Turingcomplete without the requirement for global symmetry. Lifting this requirement, we can translate Brainfuck to Stack Cats as follows. Of course, Brainfuck's I/O commands cannot be translated due to the restricted I/O model of Stack Cats. Instead we assume that the input to the Brainfuck program is already on the tape, and its output remains on the tape afterwards. The Brainfuck tape is represented by the top of every other stack in Stack Cats. The six remaining Brainfuck commands can then be translated as follows:
BF Stack Cats + !  ! > >> < << [ :{]([>*)([>*)<:]<(>*<)(>*<)>(*< ] >*)<:]<}
Note that this implements a somewhat nonstandard Brainfuck variant with arbitraryprecision integers instead of wrapping 8bit cells.
Furthermore, given an arbitrary piece of Stack Cats code abc
that doesn't modify the cell where it starts and returns to that cell at the end, we can construct a program running only this code as follows:
<*(abc)*(cba)*>
External Resources
 GitHub repository including language spec, reference implementation in Ruby and example programs.
 Esoteric IDE which contains an implementation in C# by user:Timwi including a stepthrough debugger.