{"id":805,"date":"2009-09-10T12:41:21","date_gmt":"2009-09-10T12:41:21","guid":{"rendered":"http:\/\/scientopia.org\/blogs\/goodmath\/2009\/09\/10\/two-dimensional-pathological-beauty-snusp\/"},"modified":"2009-09-10T12:41:21","modified_gmt":"2009-09-10T12:41:21","slug":"two-dimensional-pathological-beauty-snusp","status":"publish","type":"post","link":"http:\/\/www.goodmath.org\/blog\/2009\/09\/10\/two-dimensional-pathological-beauty-snusp\/","title":{"rendered":"Two Dimensional Pathological Beauty: SNUSP"},"content":{"rendered":"

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.<\/em><\/p>\n

Todays programming language insanity is a real delight – it’s one
\nof my all-time favorites. It’s a language
\ncalled SNUSP. You can find the language specification here<\/a>,
\na compiler<\/a>, and
\nan interpreter embedded
\nin a web page<\/a>. It’s sort of like a cross between Befunge<\/a>
\nand Brainfuck<\/a>,
\nexcept that it also allows subroutines. (And in a variant, threads<\/em>!) The
\nreal beauty of SNUSP is its beauty: that is, programs in SNUSP are actually
\nreally quite pretty, and watching them run can be positively entrancing.<\/p>\n

<\/p>\n

SNUSP keeps its data on a tape, like Brainfuck. The basic instructions are
\nvery Brainfuck like:<\/p>\n

\n
<<\/code><\/dt>\n
move the data tape pointer one cell to the left.<\/dd>\n
><\/code><\/dt>\n
move the data tape pointer one cell to the right.<\/dd>\n
+<\/code><\/dt>\n
add one to the value in the current data tape cell.<\/dd>\n
-<\/code><\/dt>\n
subtract one from the value of the current data tape cell.<\/dd>\n
,<\/code><\/dt>\n
read a byte from stdin to the current tape cell.<\/dd>\n
.<\/code><\/dt>\n
write a byte from the current tape cell to stdout.<\/dd>\n<\/dl>\n

As I said, very Brainfuck-like when it comes to handling data. The interesting
\npart is next, when we get to its idea of two-dimensional control flow.
\nThere aren’t many instructions here – but they end up providing something that I find
\nmuch more fascinating that Befunge.<\/p>\n

\n
\/<\/code><\/dt>\n
bounce the current control flow direction as if the “\/” were a mirror: if
\nthe program is flowing up, switch to right; if it’s flowing down, switch to
\nleft; if it’s flowing left, switch to down; and if its flowing right, switch
\nto up.<\/dd>\n
<\/code><\/dt>\n
bounce the other way; also just like a mirror.<\/dd>\n
=<\/code><\/dt>\n
noop for drawing a path flowing left\/right.<\/dd>\n
|<\/code><\/dt>\n
noop for drawing a path flowing up\/down.<\/dd>\n<\/dl>\n

Those control flow operators are pretty much trivial. Conditionals are,
\nobviously, written using a “?” test followed by a mirror. Loops are,
\nliterally, loops. The no-ops allow you to actually draw paths, which makes
\nSNUSP programs look<\/em> really cool, but so far, it’s not particularly
\nfunctionally different from Befunge with a Brainfuck tape. What makes SNUSP
\nboth brilliant and twisted is the last two instructions, which provide
\nsubroutines. In addition to the playfield and the data tape, SNUSP also
\nhas a call stack. Each entry on the call stack consists of a pair of
\n(location,direction). The two subroutine instructions are:<\/p>\n

\n
@<\/code><\/dt>\n
push the current program location and the current direction onto the stack.<\/dd>\n
#<\/code><\/dt>\n
means pop the top of the stack, set the location
\nand direction, and *skip* one cell. If there is nothing on the stack, then
\nexit (end program).<\/dd>\n<\/dl>\n

The final thing you need to know to read a SNUSP program
\nis that program execution starts out wherever there is a “$”, with the PC
\nmoving to the right.<\/p>\n

For our first example, here’s a program that reads a number and then
\nprints it out twice:<\/p>\n

\n\/==!\/===.===#\n|   |\n$====,===@\/==@\/====#\n<\/pre>\n
 So, it starts at the “$” flowing right. Then gets to the “,”, and reads a
\nvalue into the current tape cell. It hits the first “@”, records the location
\nand direction on the stack. Then it hits the “\/” mirror, and goes up until it
\nhits the “\/” mirror, and turns right. It gets to the “!” and skips over the
\n“\/” mirror, then the “.” prints, and the “#” pops the stack. So it returns to
\nthe first “@”, skips over the “\/” mirror, and gets to the second “@”, which
\npushes the stack, etc.\n<\/p>\n
 Here’s a simple subroutine for adding 48 to a cell:<\/p>\n
\n=++++++++++++++++++++++++++++++++++++++++++++++++#\n<\/pre>\n
Or a slight variant:<\/p>\n
\n\/=+++++++++++++++++++++++++\n| #+++++++++++++++++++++++\/\n|\n$\n<\/pre>\n
Or (copying from the language manual), how about this one? This one starts
\nto give you an idea of what I like about this bugger; the programs can be
\nreally beautiful; writing a program in SNUSP can be as much art as it is programming.\n<\/p>\n
\n#\/\/\n$===!++++\n\/++++\/\n\/=++++\n!\/\/\/\n<\/pre>\n
One last +48 subroutine, <\/p>\n
\n123 4\n\/=@@@+@+++++#\n|\n$\n<\/pre>\n
 This last one is very clever, so I’ll walk through it. The “1234” on the top
\nare comments; any character that isn’t an instruction is ignored. They’re
\nthere to label things for me to explain.<\/p>\n
    \n
  1.  The program goes to @1.<\/li>\n
  2.  At @1, itt pushes the loc\/dir on the stack.<\/li>\n
  3.  Then it gets to @2, and pushes again. (So now the stack is “@1right,@2right”). <\/li>\n
  4.  Then it gets to @3, and pushes again, and the stack is “@1right,@2right,@3right”.<\/li>\n
  5.  Then add one to the cell, and push again (stack=@1right,@2right,@3right,@4right”).<\/li>\n
  6.  Then 5 “+”s, so add 5 to the cell; with the earlier “+”, we’ve now added 6 to the cell.<\/li>\n
  7.  Then we hit “#”, so pop, return to @4, and skip forward one cell. So 4 “+”s
    \nget executed, and we’ve now added 10 to the tape cell.<\/p>\n
  8.  Then we pop again (so the stack is “@1right,@2right”), return to @3,
    \nand skip one instruction. That puts us back at @4, so we push (stack=@1right,@2right,@4right).<\/li>\n
  9.  Now there are the five “+”s (so we’ve added +15), and then another pop,
    \nwhich brings us back to @4.<\/li>\n
  10.  We skip a cell, since we just popped back; so now we execute 4 “+”s (+19), and
    \npop again. (stack=@1right), and we’re at @2.<\/li>\n
  11.  As usual, we skip one instruction since we just popped – so we
    \njump over @3. Then we add one (+20), and repeat what happened before when
    \nwe first got to “@4”, adding another 9 (+29). <\/li>\n
  12.  Pop again (so stack is empty), skip one instruction, so we’re at @3.
    \nSkip, push, repeat from @4 (+38). <\/li>\n
  13.  Pop back to @2, skip @3, add one (+39), push @4, repeat the same thing from @4
    \nagain (+48).<\/li>\n<\/ol>\n
     Here’s a real beauty: Multiplication, with documentation. If you look at
    \nit carefully, it’s actually reasonably clear how it works! Given this
    \ninstruction set, that’s truly<\/em> an amazing feat.\n<\/p>\n
    \nread two characters    ,>,==  *    \/=================== ATOI   ----------\nconvert to integers \/=\/@<\/@=\/  *   \/\/ \/===== ITOA  ++++++++++ \/----------\/\nmultiply @ =!=========\/ \/\/           \/++++++++++\/ ----------\nconvert back !\/@!============\/            ++++++++++ \/----------\/\nand print the result \/  .#    *                  \/++++++++++\/ --------#\n\/====================\/          *                  ++++++++#\n|\n|    \/-<+>                    #\/?=<<<<!>>>>                   \/>>+<+<-\n|   #?===\/! BMOV1 =====       ->>>>+\/    \/\/  \/======== BSPL2 !======?\/#\n|    \/->+<         \/===|=========== FMOV4 =\/  \/\/                \/<<+>+>-\n|   #?===\/! FMOV1 =|===|==============  \/====\/  \/====== FSPL2 !======?\/#\n|                \/==|===|==============|==|=======\/\n|           * * *|* | * | * * * * * * *|* | * * *                \/+<-\n|           * \/>@\/<@\/>>@\/>>=== \/====>>@<@<  *   \/==== ADD2  !>=?\/<#\n===== MUL2 =?\/>@==<#<<<==  !<<<<@>>>>-?\/ *  \/\/            \/-\n*    \\        \/@========|======<\/ * \/\/  \/== ZERO  !?\/#\n* * * \\* * * * | * * * * | * * * * *\/\/  \/\/\n\\       |         ==========\/  \/\/\n======!=======================\/\n<\/pre>\n
     Want to see more true brilliance? How about integer square root? Written
    \nto look almost like the square root radical?<\/p>\n
    \n\/>!\/?>=!\/?>!\/=======?<<<#\n|  -\/<-=-\/  >>>+<<<-\/\nsqrt=>+<=!\/?!\/->-?+>?\/\n\\!=<<+>\/<<+>\/\n===<++\/\n<\/pre>\n
     One last example: one of the most pathological functions ever, Ackermann’s
    \nfunction. This was designed by a mathematician trying to prove that there were
    \nprograms that didn’t require the full power of a turing machine, but that were
    \nmore complicated than primitive recursive functions. The definition of the
    \nfunction is:<\/p>\n
    A(x,y) = <\/p>\n
      \n
    •  y + 1 if x = 0<\/li>\n
    •  A(x-1,1) if x > 0 and y = 0<\/li>\n
    •  A(x-1,A(x,y-1)) if x > 0 and y > 0<\/li>\n<\/ul>\n
       The value of Ackerman’s function grows like nothing else. A(4, 2) is about
      \n2×1019728<\/sup>.And it’s done by adding ones that many times. <\/p>\n
       Here’s Ackerman’s in SNUSP:<\/p>\n
      \n\/==!\/==atoi=@@@-@-----#\n|   |\n|   |       \/=========!==!====   ** recursion **\n$,@\/>,@\/==ack=!?<+#    |   |     |   A(0,j) -> j+1\nj   i           <?+>-@\/#  |     |   A(i,0) -> A(i-1,1)\n@>@->@\/@<-@\/#  A(i,j) -> A(i-1,A(i,j-1))\n#      #  |  |     |\n\/-<<+>>!=\/  =====|==@>>>@<<#\n(a > 0)   ?      ?           |   |    |\n>>+<<-\/!==========\/   |    |\n#      #               |    |\n|    |\n#\/?========!==\/    ==!\/=======?#\n->>+>+<<<\/            >>>+<<<-\/\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
      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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2}},"categories":[92],"tags":[],"class_list":["post-805","post","type-post","status-publish","format-standard","hentry","category-pathological-programming"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p4lzZS-cZ","jetpack_sharing_enabled":true,"jetpack_likes_enabled":true,"_links":{"self":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/805","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/comments?post=805"}],"version-history":[{"count":0,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/posts\/805\/revisions"}],"wp:attachment":[{"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/media?parent=805"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/categories?post=805"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.goodmath.org\/blog\/wp-json\/wp\/v2\/tags?post=805"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}