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.
- 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
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) ? ? | | | \>>+<<-/!==========/ | | # # | | | | #/?========\!==/ \==!/=======?\# \->>+>+<<</ \>>>+<<<-/
- Log in to post comments
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"?
Yes. You can find a more complete language description here:
http://esoteric.voxelperfect.net/wiki/SNUSP
Some rightmost portion of the multiplication program appears to be cut off?
@4:
Seems you can see it if you "zoom out" the text (on firefox its ctl-mouse wheel down).