Two Dimensional Pathological Beauty: SNUSP

Sep 10 2009 Published by under pathological programming

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
and Brainfuck,
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
to up.
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.

  1. The program goes to @1.
  2. At @1, itt pushes the loc/dir on the stack.
  3. Then it gets to @2, and pushes again. (So now the stack is "@1right,@2right").
  4. Then it gets to @3, and pushes again, and the stack is "@1right,@2right,@3right".
  5. Then add one to the cell, and push again (stack=@1right,@2right,@3right,@4right").
  6. Then 5 "+"s, so add 5 to the cell; with the earlier "+", we've now added 6 to the cell.
  7. 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.

  8. 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).
  9. Now there are the five "+"s (so we've added +15), and then another pop,
    which brings us back to @4.
  10. 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.
  11. 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).
  12. Pop again (so stack is empty), skip one instruction, so we're at @3.
    Skip, push, repeat from @4 (+38).
  13. Pop back to @2, skip @3, add one (+39), push @4, repeat the same thing from @4
    again (+48).

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
function is:

A(x,y) =

  • 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)   ?      ?           |   |    |
>>+<<-/!==========/   |    |
#      #               |    |
|    |
#/?========!==/    ==!/=======?#
->>+>+<<</            >>>+<<<-/

5 responses so far

Leave a Reply