Insane Stacking
Todays pathology is playing with stacks. Lots of lots of stacks. Stacks for data. Stacks for control. Stacks out the wazoo. It’s called Kipple for no particularly good reason that I know of.
Kipple happens to be one of the pathological languages that I highly recommend trying to write some programs in. It’s crazy enough to be a challenge, but there is a basic logic to how you program to it – which makes figuring out how to write programs rewarding rather than just frustrating.
Kipple has only four operators, and one control structure. Everything is really based around the stacks. There are 26 of them, named “a” through “z”, and every
operator needs to specify which of the stacks it’s going to work with:

op<stack
orstack>op
: push a value onto
a stack. The value of the operand “op” is pushed onto the specified stack.
“>” and “<” are equivalent, except that the order of the operand and
stack are switched. An operand can be either an integer, or another stack; if
it’s another stack, it pops the top value from that other stack, and pops it
onto the target stack. 
stack+op
: add the value of the operand to the value
on the top of the target stack. 
stackop
: subtract the value of the operand from
the value on top of the target stack. 
stack?
: if the top of the specified stack is 0, then
empty the stack. Otherwise, do nothing.
To make things confusing, you can chain things together: “a>b<c
” is the same as “a>b
” followed by “b<c
“.
The only control structure is a the loop. A loop is code inside of parens; the first thing in the parens is the name of the stack that controls the loop. The loop will be executed as long as the controlling stack is not empty. Just like with the operators, you can use chaining; if the first thing in the loop is an operator expression, then the first stack named in the operator expression is also the
controlling stack.
So, for example, to copy stack a to stack b, the clear way of doing it is:
“(a a>b)
” (while a is not empty, pop a value from a and push it onto b.) It can be written more concisely as “(a>b)
“.
For doing input and output, the stacks “i” and “o” are special: at the start of the program, any input to the program is put onto the “i” stack; when the program stops, anything on the “o” stack is output as a character.
There are two convenience extensions. One is a pseudostack. Pushing a number onto
the stack “@” pushes the characters needed to print the number onto the “o” stack. So
if the top of stack a was “273”, then “a>@
” would push “2”, “7”, and “3”
onto the “o” stack. The other convenience is string literals: a<"HI"
is
the same as a<77 a<78
.
So, as usual, we start with hello world. It’s remarkably simple in Kipple:
"Hello World!">o
Pretty simple. It doesn’t even look pathological! Let’s try a bit harder…
#Prints "Hello World!" 33>o<100 108>o<114 111>o<87 32>o<111 108>o<108 101>o<72
Now, that’s more like it. Work it out, and you’ll see it’s pushing the characters
of “Hello world!” onto the o stack in the correct order.
Let’s get a bit harder, and look at the fibonacci series.
24>n 0>t 1>a # push fibonacci numbers onto stack t (n1 a+0 t<a>b+a c<b>a<c n? ) # output numbers: (t>@ (@>o) 32>o )
It’s actually amazingly clear. “n” used as a loop counter. Each iteration through the loop, it pushes the last fib number onto the “t” stack; then it does an add and swap, so that “a” and “b” contain the next pair of fibonacci numbers; and then it checks if the loop index is zero – if it is, it empties the stack, ending the loop. Then it outputs the numbers on t, with spaces between them.
Getting slightly trickier, here’s a program that squares a number taken from
the input. The reason for trickiness is that it needs to do multiple nested loops to be able to do the multiplication.
#Reads a number from input, and squares it. #by Jannis Harder 1>j 0>n (i>s10 s? (s22 s? (s16 j+0 s+0 j>t 0>u (t1 u+s+0 t?) n+u 10>t 0>u j+0 (t1 u+j+0 t?) 0>j? u>j 0>s?) ) ) n+0 a<n>b+0 0>u (a1 u+b+0 a?) u>@ 10>o (@>o)
And finally, as usually for pathological languages, the proof that it’s really Turing complete is a Brainfuck interpreter. It’s actually quite a nice piece of code – easier to understand than the squaring program above!
# Brainfuck interpreter. Input is separated from the source with # an ! character. Cell size is 8 bits. # # Brainfuck example: # # >,[>,]<[.<]!Hello. # # This program (the part before the !) will output it's input # (the part after the !) in reverse (i>a) 1>x # Loop that reads the source code into t, ignoring invalid # characters, until an ! is encountered: (x #while(!x.empty()) 0>b a43 a>z? 0>y (z y? 0>z?) (y? a>t b?) #if a.peek()=='+' t.push(a.pop()) a44 a>z? 0>y (z y? 0>z?) (y? a>t b?) a45 a>z? 0>y (z y? 0>z?) (y? a>t b?) a46 a>z? 0>y (z y? 0>z?) (y? a>t b?) a60 a>z? 0>y (z y? 0>z?) (y? a>t b?) a62 a>z? 0>y (z y? 0>z?) (y? a>t b?) a91 a>z? 0>y (z y? 0>z?) (y? a>t b?) a93 a>z? 0>y (z y? 0>z?) (y? a>t b?) (b a>z b?) # discard characters that aren't Brainfuck operators # if current character is ! then stop a33 a>x? x>y? (y a+0 a>x? 0>y? ) #Move the source code to s (t>s) a>z # discard the ! character (a>b) (b>i) # move the input to i (s 0>z? #empty z # + s43 s>x? 0>y (x y? 0>x?) (y? d>z+1 z256 z? z>q #emulate 8 bit cells z>d ) #  s45 s>x? 0>y (x y? 0>x?) (y? d>z+0 z>q? 0>r (q r? 0>q? z1) (r z+255 r?) #emulate 8 bit cells z>d ) # , s44 s>x? 0>y (x y? 0>x?) (y? d>z i>d) # . s46 s>x? 0>y (x y? 0>x?) (y? d+0 d>p) # < s60 s>x? 0>y (x y? 0>x?) (y? d<e) # > s62 s>x? 0>y (x y? 0>x?) (y? d>e) # [ s91 s>x? 0>y (x y? 0>x?) (y d+0 d>m? 0>n (m n? 0>m?) (n 1>b (b s>t s91 s>x? 0>y (x y? 0>x?) (y? b+1) s93 s>x? 0>y (x y? 0>x?) (y? b1) b? ) n? ) y? ) # ] s93 s>x? 0>y (x y? 0>x?) (y d+0 d>n? (n 1>b (b s<t s91 s>x? 0>y (x y? 0>x?) (y? b1) s93 s>x? 0>y (x y? 0>x?) (y? b+1) b? ) 0>n? ) y? ) s>t ) (p>o)
Completely off topic, but nonetheless highly relevant. Mark, I think you deserve some of those:
http://scq.ubc.ca/sciencescouts/
🙂 Cheers!
“Kipple” is the word Philip K. Dick uses in Do Androids Dream of Electric Sheep? for the accumulated dust and refuse which builds everywhere as entropy increases.
Ah, but Wikipedia has some decent guesses.
I also think that your initial description of < and > is reversed – it’s op>stack or stack<op
If I understand the fibonacci code correctly, stack+op has to be doing stack.push(stack.peek() + op). Right?
Mark, do you know Wouter van Oortmerssen and the languages he designed?
See http://strlen.com/ for his homepage. IMO he invented some of the fanciest yet theoreticallyuseful languages I know 😉
‘False’ would be a candidate for your Pathological series.
And thanks for your great work, every single one of your articles is educating and full of information.