Beautiful Insanity: Pathological Programming in SNUSP

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][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:
1. “” move the data tape pointer one cell to the right.
3. “+” add one to the value in the current data tape cell.
4. “-” subtract one from the value of the current data tape cell.
5. “,” read a byte from stdin to the current tape cell.
6. “.” write a byte from the current tape cell to stdout.
7. “!” skip the next instruction.
8. “?” skip the next instruction if the current tape cell contains zero.
Then there’s the two-dimensional control flow. There aren’t many instructions here.
1. “/” 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.
2. “” bounce the other way; also just like a mirror.
3. “=” noop for drawing a path flowing left/right.
4. “|” noop for drawing a path flowing up/down.
So far, we’ve pretty much got a straightforward mix between Brainfuck and Befunge. Here’s where it becomes particularly twisted. It also has two more
instructions for handling subroutines. There’s a call stack which records pairs of location and direction, and the two instructions work with that:
1. “@” means push the current program location and the current direction onto the stack.
2. “#” 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).
Finally, the program execution starts out wherever there is a “$”, moving to the right.
So, for 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 just *look* cool. 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. It pushes the loc/dir on the stack. Then it gets to @2, pushed again. (So now the stack is “@1right,@2right”). Then @3, push (stack=”@1right,@2right,@3right”). Then add one to the cell. Push again (stack=@1right,@2right,@3right,@4right”). Then 5 “+”s, so add 5 to the cell. So we’ve added 6. Then we hit “#”, so pop, return to @4, skip one cell. So 4+s get executed. So we’ve added 10. Then pop again (so stack is “@1right,@2right”), return to @3, skip one instruction. So we’re back to @4; push (stack=@1right,@2right,@4right). Add five (we’re up to “+15”), and pop the stack, which brings us back to @4 again, and skip one cell, so now add another 4 (+19). Pop (stack=@1right), and we’re at @2. Skip one instruction, so we jump over @3. Then 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 / .# * /++++++++++/ ——–#
/====================/ * ++++++++#
|
| /- #/?=<<<>>> />>+<+>>>+/ // /======== BSPL2 !======?/#
| /->+< /===|=========== FMOV4 =/ // /<+>-
| #?===/! FMOV1 =|===|============== /====/ /====== FSPL2 !======?/#
| /==|===|==============|==|=======/
| * * *|* | * | * * * * * * *|* | * * * /+@/>@/>>=== /====>>@<@=?/@==<#<<<== !<<<>>>-?/ * // /-
* \ /@========|======!/?>=!/?>!/=======?<<<#
| -/>>+<<+-?+>?/
\!=</</
=== 0 and y = 0
or 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.
Here’s Ackerman’s in SNUSP:
/==!/==atoi=@@@-@—–#
| |
| | /=========!==!==== ** recursion **
$,@/>,@/==ack=!? j+1
j i -@/# | | A(i,0) -> A(i-1,1)
@>@->@/@ A(i-1,A(i,j-1))
# # | | |
/-<>!=/ =====|==@>>>@< 0) ? ? | | |
>>+<>+>+<<>>+<<<-/
[snuspspec]: http://www.deepwood.net/~drlion/snusp/snusp-1.0-spec-wd1.pdf
[snuspcomp]: http://www.baumanfamily.com/john/esoteric.html
[snupsinterp]: http://www.quirkster.com/snusp/snusp-js.html
[brainfuck]: http://scienceblogs.com/goodmath/2006/07/gmbm_friday_pathological_progr.php
[befunge]: http://scienceblogs.com/goodmath/2006/07/friday_pathological_programmin.php

0 thoughts on “Beautiful Insanity: Pathological Programming in SNUSP

  1. MattF

    Amazing. Self-diagramming programs. Also– I’m just a born nitpicker– the Busy Beaver function increases faster than the Ackerman function..

    Reply
  2. Thomas Winwood

    Normally novelty programming languages like this one make me panic and want to hide in my bed, but this one, along with Brainfuck and Befunge, look downright fun to program with. I wonder if there’s any documented examples of serious programs written in any of them.
    And you still haven’t covered INTERCAL. 🙂

    Reply
  3. Mark C. Chu-Carroll

    MiguelB:
    Sorry; I forgot to say in the article. If there is no “$”, the program starts at the top-left corner moving right.

    Reply
  4. Mark C. Chu-Carroll

    Thomas:
    That’s exactly the effect that I want. The pathological languages that I like are ones that are twisted, obscure, and insane; but which have something about them that makes them *fun* to program. I look at Thue, or Brainfuck, or SNUSP, and I want to program in them! Even though they’re insane, they have some kind of beauty hiding in them that’s inspiring.

    Reply
  5. Ken Hirsch

    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.
    He wanted to give a function that was computable, but not primitive-recursive. He did this in 1928, but Turing machines didn’t come about until 1936, and similiar concepts (general-recursive, lambda-reducability, etc.) date from 1932-1936.
    So he didn’t try to show that his function was less “powerful” than those things (which hadn’t been invented yet), just that is was computable but not primitive-recursive. I think the term primite-recursive wasn’t invented until 1936.

    Reply
  6. Daniel Martin

    I assume our host is familiar with this resource: esoteric programming languages wiki.
    And I don’t know what to think about Shakespeare. I first thought it was as trivial and basically uninteresting as Chef, but there are bits in there that could be interesting. I like the perverse method of specifying constants, for example.
    I would hope our host will look into OISC, or its relative MISC (I could actually see someone implementing MISC-16 in hardware). OISC is interesting primarily because it was a bit of an academic joke in a few ACM articles way before esoteric programming languages became a thing. (1987, which easily predates Brainfuck)

    Reply
  7. John Bauman

    Yeah, that’s why I created the compiler. The language is nice and simple, but because it’s 2d you can do some really interesting things with it. The compiler’s just so you don’t have to wait an eternity for the program to finish (and because writing it was interesting, of course).

    Reply
  8. Jonathan Vos Post

    Some 2-Dimensional Turing Machines for Number Theory
    I’d like some feedback on a class of sequences I’m
    working on. They are generated by a (virtual)
    2-dimensional Turing machine. Let me start with some
    involving prime factorization. All have, in common, a
    counter starting with 1 (which becomes the n in the
    sequences), and a cursor (read/write head) located in
    an initially blank square lattice, i.e. integer-valued
    Cartesian space.
    (device #1)
    (1) start with cursor at origin, and count = 1.
    (2) write the number where the cursor is.
    (3) Add 1 to the counter.
    (4) Find the prime factorization of the counter.
    (5) If counter is prime, move cursor to first empty
    space to the Right, go to statement (2).
    (6) Else if counter is semiprime, move cursor to first
    empty space to the Left, go to statement (2).
    (7) Else move cursor Up to first empty space, go to
    statement (2).
    Through n = 62 we have the following 2-D array of
    numbers produced:
    __,__,58,57,56,59
    __,__,__,__,55,54
    __,__,__,__,52,53
    __,__,__,__,51,50
    __,__,__,__,__,49,48
    __,__,__,__,46,45,47
    __,__,__,__,__,44
    __,__,__,__,42,43
    __,__,__,40,41
    __,__,__,39,38,36,37
    __,__,__,__,__,35,34,33,32
    __,__,__,__,__,__,__,30,31
    __,__,__,__,__,__,28,29
    __,__,__,__,__,__,27
    __,__,__,__,__,__,26,25,24
    __,__,__,__,__,22,21,20,23
    __,__,__,__,__,__,18,19
    __,__,__,__,__,16,17
    __,__,__,__,__,15,14,12,13
    __,__,__,__,10,09,08,11
    6,4,01,02,03,05,07
    This never moves Down. It is not a random walk, but
    may be measured by means typical of random walk
    theory. One can ask approximately, and
    asymptotically, what is the position of the cursor
    along the x and y axes at time = n. One can flatten
    it to the 1-D sequence of DistanceSquared from origin
    a(n) = 0, 1, 4, 1, 9, 4, 16, 17, 10, 5, 26, 29, …
    One can differentiate to get velocity vector of the
    cursor.
    One can project the shape to the sequence of number of
    values on nth row, starting at row containing origin =
    b(n) = 7, 4, 4, 2, 2, 4, 3, 1, 2, 2, 4, 4, 2, 2, 1, 3,
    2, 2, 2, 2, 4, …
    ———————————-
    (device #2)
    (1) start with cursor at origin, and count = 1.
    (2) write the number where the cursor is.
    (3) Add 1 to the counter.
    (4) Find the prime factorization of the counter.
    (5) If counter is prime, move cursor to first empty
    space to the Right, go to statement (2).
    (6) Else if counter is semiprime, move cursor to first
    empty space to the Left, go to statement (2).
    (7) Else if counter is 3-almost prime, move cursor Up
    to first empty space, go to statement (2).
    (8) Else (counter is k-almost prime for k>3) move
    cursor Down to first empty space, go to statement (2).
    By n = 55 we see:
    __,__,__,__,__,__,30,31
    __,__,__,__,__,28,29
    __,__,__,__,__,27,22,21,20,23
    __,__,__,__,52,26,25,18,19,24,53
    __,__,__,55,51,50,15,14,13,54
    __,__,__,__,__,10,09,08,11
    46,06,04,01,02,03,05,07,45,47
    __,__,__,__,__,__,49,16,17,44,48
    __,__,__,__,42,35,34,33,32,43
    __,__,__,39,38,36,37
    __,__,__,40,41
    __,__,58,57,56,59
    Asymptotically, this moves mostly Down.
    DistanceSqaured(n) =
    0,1,4,1,9,4,16,17,10,5,26,29,40,20,13,10,17,25,34,41,32,29,52
    where 17 is a fixed point.
    This relates to the 2-D flow of control programming
    language SNUSP, for which definition, interpreter,
    compiler exist online.
    I’ll stop email here, before getting to the devices
    based on number of distinct factors, and the class of
    devices that move R,L,U,D depending on value mod 4 of
    sequences from OEIS, of which I first did a rigid
    example, a silly example with length of english name
    of n, and some others.
    This is a way of getting a 2-D graphic from almost any
    OEIS sequence.
    I cannot easily show here some 3-D Turing machines
    I’ve played with.
    My son has some clever questions about the inverse
    problem (inferring th rules from the 2-D sequence),
    and what happens if one can overwrite or erase (which
    lead quickly to noncomputable situations).
    Any comments on this, and its suitability for OEIS,
    and some more citations?
    Best,
    Jonathan Vos Post
    2D Turing machines Inbox
    Dr R.H. Barbour
    to me
    More options Oct 1 (1 day ago)
    Hi Jonathan,
    Interesting study.
    2D Turing machines (2D TMs) have been studied by Chris
    Langton among others as I am sure you know and also
    appear in OEIS under a search for ‘ant’, and ‘cellular
    automata’ but not ‘turmite’ or ‘vant’. There are also
    interesting links to four valued logics…. Belnap’s
    Four and Gray’s Code.
    My current interest is in 2D four colour cellular
    automata in both Moore and von Neumann neighborhoods.
    I am interested in links between the sequences
    generated by 2D TMs and those generated in other
    contexts that ‘match’ 2D TM sequences.
    Best Wishes,
    Bob
    Reply Forward Invite Dr to Gmail
    Jonathan Post to jvospost2, andrewpost, Dr
    More options Oct 1 (23 hours ago)
    Dear Dr. R. H. Barbour,
    I have a sister-in-law in New Zealand, and friends.
    I met Chris Langton at the 2nd Artificial Life
    conference, where I gave a poster session (which
    deserved to be in the Proceedings, I believe) and some
    AL poems.
    Cellular Automata were, of course, co-invented by John
    von Neumann and Stanilsaw Ulam. I was to have
    coauthored with Ulam, based on a Bell Labs
    videoconference we had in the 1970s.
    I am a student of a student of Norbert Weiner, and
    have a cybernetics set of mentors.
    On OEIS, I commented on the “accelerated ant”
    sequence.
    I am 50 pages into writing a paper on four valued
    logics and n-valued logics with “imaginary” Boolean
    values.
    My son presented my paper for me at the poster session
    of this past June’s Wolfram NKS Conference. I knew
    Wolfram when he was a professor of Physics at Caltech,
    and I a Physics major undergraduate.
    My work, and your work, especially in pretty colors
    growing over time, might make a nice collaboration for
    next year’s NKS.
    I just posted 3 more 2D devices on seqfans.
    Please tell me more about you and your research!
    Best,
    Jonathan Vos Post,
    ex-Adjunct Professor of Mathematics, Woodbury
    University, Burbank, California
    ex-Adjunct Professor of Astronomy, Cypress College,
    Cypress, California
    sequences Inbox
    jonathan post
    to me, andrewpost
    More options Oct 1 (1 day ago)
    (device #3)
    (1) start with cursor at origin, and count = 1.
    (2) write the number where the cursor is.
    (3) Add 1 to the counter.
    (4) Find the prime factorization of the counter [what
    matters here is the number of DISTINCT prime factors,
    omega(n)].
    (5) If omega(n) = 1 [counter is prime or a prime
    power], move cursor to first empty space to the Right,
    go to statement (2).
    (6) Else if omega(n) = 2 [counter is product of two
    primes or prime powers], move cursor to first empty
    space to the Left, go to statement (2).
    (7) Else if omega(n) = 3 [counter is of form p^a q^b
    r^c, p, q, r prime], move cursor Up to first empty
    space, go to statement (2).
    (8) Else if omega(n) > 3 move cursor Down to first
    empty space, go to statement (2).
    By n = 50 we see:
    row 1:
    28,_26,_24,_22,_21,_20,_18,_15,_14,_12,_10,_06,_01,_02,_03,_04,_05,_07,_08,_09,_11,_13,_16,_17,_19,_23,_25,_27,_29
    row 2 (above row 1, 40 above 13):
    40,_39,_38,_36,_35,_34,_33,_30,_31,_32,_37,_41
    row 3 (above row 2, 42 above 41):
    50,_48,_46,_45,_44,_42,_43,_47,_49
    ========
    Device #4
    The first of several where we take f(n) mod 4 for
    various f(n). We start with the simplest:
    (1) start with cursor at origin, and count = 1.
    (2) write the number where the cursor is.
    (3) Add 1 to the counter.
    (4) divide counter by 4, consider remainder (n mod
    4).
    (5) if 0 mod 4, move cursor Down to first empty
    space, go to statement (2).
    (6) if 1 mod 4, move cursor Right to first empty
    space, go to statement (2).
    (7) if 2 mod 4, move cursor Left to first empty
    space, go to statement (2).
    (8) if 3 mod 4, move cursor Up to first empty space,
    go to statement (2).
    This is crystalline:
    _______________03
    ____________07_02_01
    _________11_06_04_05
    ______15_10_08_09
    ___19_14_12_13
    23_18_16_17
    the pattern is:
    ____n+3
    n+7_n+2__n_n+1
    n+6_n+4_n+5
    n+8
    so reading from left to right, top to bottom, we have
    this permutation of the natural numbers:
    3, 7, 2, 1, 11, 6, 4, 5, 15, 10, 8, 9, 19, 14, 12, 13,
    23, 18, 16, 17, 27, 22, 20, 21, 31, 26, 24, 25, 35,
    30, …
    ========
    Device #5
    where we take f(n) mod 4 for f(n) = number of letters
    in English name of n.
    A005589
    Number of letters in the English name of n, excluding
    spaces and hyphens.
    (1) start with cursor at origin, and count = 1.
    (2) write the number n = counter where the cursor is.
    (3) Add 1 to the counter.
    (4) Calculate f(n) = number of letters in English
    name of n.
    (5) Find r = f(n) mod 4.
    (6) if r = 0 move cursor Down to first empty space,
    go to statement (2).
    (7) if r = 1, move cursor Right to first empty space,
    go to statement (2).
    (8) if r = 2, move cursor Left to first empty space,
    go to statement (2).
    (9) if r = 3, move cursor Up to first empty space, go
    to statement (2).
    After n = 44, we see:
    ________________________39_38_40
    ___________________________37_41
    ___16_17_______43_35_34_33_36_42_44
    ___15_18____30_29_28_31_32
    ___12_11_10_______27
    25_06_07_08_24_23_26
    20_02_03
    ___01_04
    ______05
    ______13
    ______14
    ========
    Next email, we’ll see
    Device #6, naturally mod 4, which graphs the minimum
    number of nonnegative squares needed to sum to n
    =======

    Reply
  9. TauCeti.NET

    Today’s Links

    Beautiful Insanity: Pathological Programming in SNUSP – Eine Programmiersprache für Leute, die sonst nichts Anderes zu tun haben 😉
    Wozu der canvas-Tag gut ist – Mit netten Beispiel-Applikationen: CanvasPaint , Canvascape , CanvasGraph.js , …

    Reply
  10. Mark Hudson

    Hi,
    Sorry for opening up comments on this post again, but I’ve only recently started working through some of the interesting things in the archive.
    This is one of the more entertaining esoteric languages I’ve come across, so I’m probably going to have a go at writing an interpreter for it. Anyway, a couple of your example programs don’t look as though they will work. (I apologise for not using fixed font in the program quotes, but I wasn’t able to get things aligned with that anyway):
    This one:
    /=+++++++++++++++++++++++++
    | #+++++++++++++++++++++++/
    |
    $
    shouldn’t work because the spec says that one starts at the first $ symbol (if present) with the direction set to “right”. Whereas you want the direction to be “up”. And it also looks like the “=” symbol is misaligned.
    Similarly, with the example:
    123 4
    /=@@@+@+++++#
    |
    $
    you won’t be going “up” at the start.
    Or am I missing something?
    Mark.

    Reply
  11. Ian Osgood

    The link to my JavaScript SNUSP interpreter embedded in a web page was broken in the article. Here it is:
    http://www.quirkster.com/iano/snusp/snusp-js.html
    The page also contains a routine to print a decimal number and an implementation of 99 bottles of beer on the wall.
    This page on Ward’s wiki was where I first heard about Daniel Brockman’s fine language. It is also where many of the programming techniques, like the base-phi constants using @+#, were originally worked out:
    http://c2.com/cgi/wiki?SnuspLanguage

    Reply
  12. BR

    On your example:
    /==!/===.===#
    | |
    $====,===@/==@/====#
    There are a few unnecessary characters.
    /==!/===.===#
    | |
    $====,===@/===/
    This works just fine. As does the simple:
    ,..

    Reply
  13. BR

    Oops, I forgot to mention that the =’s you used to space it out are almost always unnecessary – they’re just to space it out for readability.
    On the whole, though, great article!

    Reply

Leave a Reply