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:

1. op<stack or stack>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.
2. stack+op: add the value of the operand to the value
   on the top of the target stack.
3. stack-op: subtract the value of the operand from
   the value on top of the target stack.
4. 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 pseudo-stack. 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
(n-1
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>s-10
s?
(s-22 s?
(s-16
j+0
s+0
j>t
0>u
(t-1 u+s+0 t?)
n+u
10>t
0>u
j+0
(t-1 u+j+0 t?)
0>j?
u>j
0>s?)
)
)
n+0 a<n>b+0
0>u
(a-1 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
a-43 a>z? 0>y (z y? 0>z?) (y? a>t b?) #if a.peek()=='+' t.push(a.pop())
a-44 a>z? 0>y (z y? 0>z?) (y? a>t b?)
a-45 a>z? 0>y (z y? 0>z?) (y? a>t b?)
a-46 a>z? 0>y (z y? 0>z?) (y? a>t b?)
a-60 a>z? 0>y (z y? 0>z?) (y? a>t b?)
a-62 a>z? 0>y (z y? 0>z?) (y? a>t b?)
a-91 a>z? 0>y (z y? 0>z?) (y? a>t b?)
a-93 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
a-33 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
# +
s-43
s>x? 0>y (x y? 0>x?)
(y?
d>z+1
z-256 z? z>q #emulate 8 bit cells
z>d
)
# -
s-45
s>x? 0>y (x y? 0>x?)
(y?
d>z+0
z>q? 0>r (q r? 0>q? z-1)
(r z+255 r?) #emulate 8 bit cells
z>d
)
# ,
s-44
s>x? 0>y (x y? 0>x?)
(y? d>z i>d)
# .
s-46
s>x? 0>y (x y? 0>x?)
(y? d+0 d>p)
# <
s-60
s>x? 0>y (x y? 0>x?)
(y? d<e)
# >
s-62
s>x? 0>y (x y? 0>x?)
(y? d>e)
# [
s-91
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
s-91  s>x? 0>y (x y? 0>x?)  (y? b+1)
s-93  s>x? 0>y (x y? 0>x?)  (y? b-1)
b?
)
n?
)
y?
)
# ]
s-93
s>x? 0>y (x y? 0>x?)
(y
d+0 d>n?
(n
1>b
(b
s<t
s-91  s>x? 0>y (x y? 0>x?)  (y? b-1)
s-93  s>x? 0>y (x y? 0>x?)  (y? b+1)
b?
)
0>n?
)
y?
)
s>t
)
(p>o)