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
Good Math/Bad Math
The beauty of math; the humor of stupidity.
Amazing. Self-diagramming programs. Also– I’m just a born nitpicker– the Busy Beaver function increases faster than the Ackerman function..
Amazing language.
The documented multiplication and square root programs seem to be missing the $ ? Where do they start?
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. 🙂
MiguelB:
Sorry; I forgot to say in the article. If there is no “$”, the program starts at the top-left corner moving right.
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.
like sick languages? give Shakespeare a try 😉
(no, i haven’t bothered to learn it myself…)
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.
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)
This is an amazing language, I’m having great fun with it 😀
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).
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
=======
This post makes me think of the Ook! programming language. 🙂
MattF – the busy beaver function isn’t computable, though.
I think my nose is bleeding.
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 , …
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.
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
On your example:
/==!/===.===#
| |
$====,===@/==@/====#
There are a few unnecessary characters.
/==!/===.===#
| |
$====,===@/===/
This works just fine. As does the simple:
,..
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!