Two Dimensional Pathological Beauty: SNUSP

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
href="http://www.deepwood.net/~drlion/snusp/snusp-1.0-spec-wd1.pdf">here,
a compiler, and
an interpreter embedded
in a web page. It's sort of like a cross between
href="http://scienceblogs.com/goodmath/2009/09/two-dimensional_pathology_befu.php">Befunge
and
href="http://scienceblogs.com/goodmath/2009/09/the_one_the_only_brainfck.php">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×10¹⁹⁷²⁸.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)   ?      ?           |   |    |     
                \>>+<<-/!==========/   |    |
                #      #               |    |
                                       |    |  
                        #/?========\!==/    \==!/=======?\#
                         \->>+>+<<</            \>>>+<<<-/