Good Math, Bad Math

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 left.
2. ">” 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 /=/@ multiply @ \=!\=========/ // /++++++++++/ \----------\
convert back !/@!\============/ \++++++++++\ /----------/
and print the result \/ \.# * /++++++++++/ \--------#
/====================/ * \++++++++#
|
| /-<+>\ #/?=<<<<\!>>>>\ />>+<+<-\
| #\?===/! BMOV1 =====\ \->>>>+/ // /======== BSPL2 !\======?/#
| /->+<\ /===|=========== FMOV4 =/ // /<<+>+>-\
| #\?===/! FMOV1 =|===|==============\ /====/ /====== FSPL2 !\======?/#
| /==|===|==============|==|=======/
| * * *|* | * | * * * * * * *|* | * * * /+<-\
| * />@/<@/>>@/>>===\ /====>>\@<\@<\ * /==== ADD2 !\>=?/<#
\===== MUL2 =?/>@\==<#<<<==\ \!\<<<<@\>>>>-?/\ * // /-\
* \\ \/@========|====== * * * \\* * * * | * * * * | * * * * *// //
\\ | \==========/ //
\======!\=======================/

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
or A(x-1,1) if x > 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=!\?\<+# | | | 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) ? ? | | |
\>>+<<-/!==========/ | |
# # | |
| |
#/?========\!==/ \==!/=======?\#
\->>+>+<<>>+<<<-/

[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

Comments

  1. #1 MattF
    August 18, 2006

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

  2. #2 MiguelB
    August 18, 2006

    Amazing language.

    The documented multiplication and square root programs seem to be missing the $ ? Where do they start?

  3. #3 Thomas Winwood
    August 18, 2006

    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. :)

  4. #4 Mark C. Chu-Carroll
    August 18, 2006

    MiguelB:

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

  5. #5 Mark C. Chu-Carroll
    August 18, 2006

    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.

  6. #6 Joe Shelby
    August 18, 2006

    like sick languages? give Shakespeare a try ;-)

    (no, i haven’t bothered to learn it myself…)

  7. #7 Ken Hirsch
    August 18, 2006

    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.

  8. #8 Daniel Martin
    August 18, 2006

    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)

  9. #9 Tomosaur
    August 22, 2006

    This is an amazing language, I’m having great fun with it :D

  10. #10 John Bauman
    September 11, 2006

    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).

  11. #11 Jonathan Vos Post
    October 3, 2006

    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

    =======

  12. #12 Robbert
    December 2, 2006

    This post makes me think of the Ook! programming language. :)

  13. #13 Ian
    December 2, 2006

    MattF – the busy beaver function isn’t computable, though.

  14. #14 Teltariat
    December 5, 2006

    I think my nose is bleeding.

  15. #15 Mark Hudson
    March 26, 2007

    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.

  16. #16 Ian Osgood
    March 6, 2008

    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

  17. #17 BR
    January 25, 2010

    On your example:

              /==!/===.===#
              |   |
    $====,===@/==@/====#

    There are a few unnecessary characters.

              /==!/===.===#
              |   |
    $====,===@/===/

    This works just fine. As does the simple:

    ,..
  18. #18 BR
    January 25, 2010

    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!

The site is currently under maintenance and will be back shortly. New comments have been disabled during this time, please check back soon.