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

More like this

Todays programming language insanity is a real winner. It's a language called SNUSP. You can find the language specification [here][snuspspec], a [compiler][snuspcomp], and [an interpreter embedded in a web page][snuspinterp]. It's sort of like a cross between [Befunge][befunge] and [Brainfuck][…
I'm sure that in the friday pathological programming languages, I have a fondness for languages that make your code beautiful: languages like [SNUSP][snusp], [Befunge][befunge], [Piet][piet], and such. Those languages all you two-dimensional layouts for their programs. [snusp]: http://scienceblogs…
Todays programming pathology is programs as art. Start with a really simple stack based language, add in a crazy way of encoding instructions using color, and you end up with a masterpiece of beautiful insanity. It's not too exciting from a purely computational point of view, but the programs are…
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…

This reminds me a lot of a Brainfuck/Befunge hybrid that I came up with a few years ago (as any hybrid of the two likely would). Mine didn't have subroutines, though, but featured self-modification as a guiding philosophy. My name links to the program, a simple interpreter and a pair of sample programs.

So ! means "skip next instruction"?

By John Fouhy (not verified) on 10 Sep 2009 #permalink

Some rightmost portion of the multiplication program appears to be cut off?

By Carl Meyer (not verified) on 02 Oct 2009 #permalink

@4:
Seems you can see it if you "zoom out" the text (on firefox its ctl-mouse wheel down).