I’m currently away on a family vacation, and as soon as vacation is over, I’m off on a business trip for a week. And along the way, I’ve got some deadlines for my book. So to fill in, I’m recycling some old posts. I decided that it’s been entirely too long since there was any pathological programming ’round these parts, so I’m going to repost some of my favorites.
Todays programming language insanity is a real delight – it’s one
of my all-time favorites. It’s a language
called SNUSP. You can find the language specification here,
a compiler, and
an interpreter embedded
in a web page. It’s sort of like a cross between Befunge
except that it also allows subroutines. (And in a variant, threads!) The
real beauty of SNUSP is its beauty: that is, programs in SNUSP are actually
really quite pretty, and watching them run can be positively entrancing.
SNUSP keeps its data on a tape, like Brainfuck. The basic instructions are
very Brainfuck like:
- move the data tape pointer one cell to the left.
- move the data tape pointer one cell to the right.
- add one to the value in the current data tape cell.
- subtract one from the value of the current data tape cell.
- read a byte from stdin to the current tape cell.
- write a byte from the current tape cell to stdout.
As I said, very Brainfuck-like when it comes to handling data. The interesting
part is next, when we get to its idea of two-dimensional control flow.
There aren’t many instructions here – but they end up providing something that I find
much more fascinating that Befunge.
- bounce the current control flow direction as if the “/” were a mirror: if
the program is flowing up, switch to right; if it’s flowing down, switch to
left; if it’s flowing left, switch to down; and if its flowing right, switch
- bounce the other way; also just like a mirror.
- noop for drawing a path flowing left/right.
- noop for drawing a path flowing up/down.
Those control flow operators are pretty much trivial. Conditionals are,
obviously, written using a “?” test followed by a mirror. Loops are,
literally, loops. The no-ops allow you to actually draw paths, which makes
SNUSP programs look really cool, but so far, it’s not particularly
functionally different from Befunge with a Brainfuck tape. What makes SNUSP
both brilliant and twisted is the last two instructions, which provide
subroutines. In addition to the playfield and the data tape, SNUSP also
has a call stack. Each entry on the call stack consists of a pair of
(location,direction). The two subroutine instructions are:
- push the current program location and the current direction onto the stack.
- means pop the top of the stack, set the location
and direction, and *skip* one cell. If there is nothing on the stack, then
exit (end program).
The final thing you need to know to read a SNUSP program
is that program execution starts out wherever there is a “$”, with the PC
moving to the right.
For our first example, here’s a program that reads a number and then
prints it out twice:
/==!/===.===# | | $====,===@/==@/====#
So, it starts at the “$” flowing right. Then gets to the “,”, and reads a
value into the current tape cell. It hits the first “@”, records the location
and direction on the stack. Then it hits the “/” mirror, and goes up until it
hits the “/” mirror, and turns right. It gets to the “!” and skips over the
“/” mirror, then the “.” prints, and the “#” pops the stack. So it returns to
the first “@”, skips over the “/” mirror, and gets to the second “@”, which
pushes the stack, etc.
Here’s a simple subroutine for adding 48 to a cell:
Or a slight variant:
/=+++++++++++++++++++++++++ | #+++++++++++++++++++++++/ | $
Or (copying from the language manual), how about this one? This one starts
to give you an idea of what I like about this bugger; the programs can be
really beautiful; writing a program in SNUSP can be as much art as it is programming.
#// $===!++++ /++++/ /=++++ !///
One last +48 subroutine,
123 4 /=@@@+@+++++# | $
This last one is very clever, so I’ll walk through it. The “1234” on the top
are comments; any character that isn’t an instruction is ignored. They’re
there to label things for me to explain.
- The program goes to @1.
- At @1, itt pushes the loc/dir on the stack.
- Then it gets to @2, and pushes again. (So now the stack is “@1right,@2right”).
- Then it gets to @3, and pushes again, and the stack is “@1right,@2right,@3right”.
- Then add one to the cell, and push again (stack=@1right,@2right,@3right,@4right”).
- Then 5 “+”s, so add 5 to the cell; with the earlier “+”, we’ve now added 6 to the cell.
- Then we hit “#”, so pop, return to @4, and skip forward one cell. So 4 “+”s
get executed, and we’ve now added 10 to the tape cell.
- Then we pop again (so the stack is “@1right,@2right”), return to @3,
and skip one instruction. That puts us back at @4, so we push (stack=@1right,@2right,@4right).
- Now there are the five “+”s (so we’ve added +15), and then another pop,
which brings us back to @4.
- We skip a cell, since we just popped back; so now we execute 4 “+”s (+19), and
pop again. (stack=@1right), and we’re at @2.
- As usual, we skip one instruction since we just popped – so we
jump over @3. Then we add one (+20), and repeat what happened before when
we first got to “@4”, adding another 9 (+29).
- Pop again (so stack is empty), skip one instruction, so we’re at @3.
Skip, push, repeat from @4 (+38).
- Pop back to @2, skip @3, add one (+39), push @4, repeat the same thing from @4
Here’s a real beauty: Multiplication, with documentation. If you look at
it carefully, it’s actually reasonably clear how it works! Given this
instruction set, that’s truly an amazing feat.
read two characters ,>,== * /=================== ATOI ---------- convert to integers /=/@</@=/ * // /===== ITOA ++++++++++ /----------/ multiply @ =!=========/ // /++++++++++/ ---------- convert back !/@!============/ ++++++++++ /----------/ and print the result / .# * /++++++++++/ --------# /====================/ * ++++++++# | | /-<+> #/?=<<<<!>>>> />>+<+<- | #?===/! BMOV1 ===== ->>>>+/ // /======== BSPL2 !======?/# | /->+< /===|=========== FMOV4 =/ // /<<+>+>- | #?===/! FMOV1 =|===|============== /====/ /====== FSPL2 !======?/# | /==|===|==============|==|=======/ | * * *|* | * | * * * * * * *|* | * * * /+<- | * />@/<@/>>@/>>=== /====>>@<@< * /==== ADD2 !>=?/<# ===== MUL2 =?/>@==<#<<<== !<<<<@>>>>-?/ * // /- * \ /@========|======</ * // /== ZERO !?/# * * * \* * * * | * * * * | * * * * *// // \ | ==========/ // ======!=======================/
Want to see more true brilliance? How about integer square root? Written
to look almost like the square root radical?
/>!/?>=!/?>!/=======?<<<# | -/<-=-/ >>>+<<<-/ sqrt=>+<=!/?!/->-?+>?/ \!=<<+>/<<+>/ ===<++/
One last example: one of the most pathological functions ever, Ackermann’s
function. This was designed by a mathematician trying to prove that there were
programs that didn’t require the full power of a turing machine, but that were
more complicated than primitive recursive functions. The definition of the
- y + 1 if x = 0
- A(x-1,1) if x > 0 and y = 0
- A(x-1,A(x,y-1)) if x > 0 and y > 0
The value of Ackerman’s function grows like nothing else. A(4, 2) is about
2×1019728.And it’s done by adding ones that many times.
Here’s Ackerman’s in SNUSP:
/==!/==atoi=@@@-@-----# | | | | /=========!==!==== ** recursion ** $,@/>,@/==ack=!?<+# | | | A(0,j) -> j+1 j i <?+>-@/# | | A(i,0) -> A(i-1,1) @>@->@/@<-@/# A(i,j) -> A(i-1,A(i,j-1)) # # | | | /-<<+>>!=/ =====|==@>>>@<<# (a > 0) ? ? | | | >>+<<-/!==========/ | | # # | | | | #/?========!==/ ==!/=======?# ->>+>+<<</ >>>+<<<-/