SNUSP
SNUSP (SNUSP's Not Unix, but a Structured Path) is a language with a two-dimensional code space, inspired by PATH. SNUSP is more orthogonal, specifies semantics more concretely, and optionally allows more advanced features.
There are three levels to the language: Core SNUSP is essentially Brainfuck with a two-dimensional control flow, Modular SNUSP adds procedures and a call-stack, and Bloated SNUSP adds concurrency, two-dimensional data space, and nondeterminism.
History
SNUSP was invented around September 2003 by Daniel Brockman, shortly after the release of PATH the previous month. A working draft of a language specification was published, but the final specification (version 1.0) has not been written.
Core SNUSP
As noted, Core SNUSP is a two-dimensional Brainfuck with a more flexible way of expressing loops and conditionals. The commands are
< LEFT Move the memory pointer to the left
> RIGHT Move the memory pointer to the right
+ INCR Increment current memory cell
- DECR Decrement current memory cell
, READ Read a byte into current memory cell
. WRITE Write a byte from current memory cell
\ LURD If going
left, go up
up, go left
right, go down
down, go right
/ RULD If going
right, go up
up, go right
left, go down
down, go left
! SKIP Move the instruction pointer forward one step
? SKIPZ If the current memory cell is zero, do a SKIP
The first six commands are equivalent to those in Brainfuck. The last four combine to replace [ and ] for looping and conditional branching.
A dollar sign ($), if present, indicates the initial position of the instruction pointer. If none is present, the instruction pointer starts at the first character in the top left. Either way, the initial direction is right. Unlike Befunge, the code space is not toroidal; the program halts if the instruction pointer runs off the edge of the code space.
Modular SNUSP
Modular SNUSP adds a call-stack and the commands
@ ENTER Push the current direction and IP location on the call-stack # LEAVE Pop direction and IP location off call-stack and advance IP one step
If the call-stack is empty when a LEAVE (#) instruction is encountered, the program (or current thread, in Bloated SNUSP) ends.
This example from the SNUSP spec shows how to use the call-stack to define an ECHO subroutine and call it twice:
/==!/======ECHO==,==.==#
| |
$==>==@/==@/==<==#
Bloated SNUSP
Bloated SNUSP makes the data space two-dimensional and adds the commands
: UP Move the memory pointer up ; DOWN Move the memory pointer down & SPLIT Create a new thread % RAND Set the value of the current cell to a random number
SPLIT and RAND demand further explanation. SPLIT moves the instruction pointer of the old thread one step forward, so it is possible to distinguish the old thread from the new. RAND chooses a value between zero and the current value of the cell, inclusive.
All threads share the same code space and data space, but each thread has its own instruction pointer, direction, call-stack, and memory pointer. The call stack for the new thread is created empty, while the instruction pointer, direction, and memory pointer are copied from the parent thread.
The following example uses two threads to print ! until a key is pressed:
/==.==<==\
| |
/+++++++++++==&\==>===?!/==<<==#
\+++++++++++\ |
$==>==+++++++++++/ \==>==,==#
Thread Execution
At start, one thread is created with its current direction being right and its instruction pointer at the starting indicator. If the source file contains a $ character, the first $ character found is the starting indicator; otherwise the starting indicator is the first character in the file.
Execution is carried out in ticks; each thread gets one turn per tick. The threads are run in an arbitrary order. A turn involves two steps:
- The instruction at the instruction pointer is carried out.
- The instruction pointer moves in its current direction, unless doing so would move it outside of code space, in which case the thread is stopped.
When all threads have stopped, the process is terminated. Its exit code is the value of the current memory cell of whichever thread was last to take a turn.
NOOP instruction
Any character not attached to a command carries out the NOOP instruction, which does nothing. Two characters typically used for this are = and |, to indicate the flow of execution proceeding horizontally or vertically, respectively.
Examples
Constants
There are several techniques to compactly define small constants and incrementers. The example used here is +48 (commonly used to convert numbers to ASCII digits).
1=++++++++++++++++++++++++++++++++++++++++++++++++#
2=!#++++++++++++++++++++++++=!\\
\/
/\/\/\
3===++++++\
/++++++/
\++++++\
/++++++/
\/\/\/#
#/\/\
4===!\++++\
/++++/
/=\++++\
\!\/\/\/
5===!#++\
/+\
/=\ /+++\
\!\++++++/
\++/
\/
6=@@@+@+++++#
The last mechanism using the call stack is interesting. It is similar to a base-phi number system. It was an interesting exercise to create a program to search for the most efficient space-vs-overhead representation for particular constants. The JavaScript interpreter below now includes a tool to search for this type of constant.
Multiplication
read two characters ,>,==\ * /=================== ATOI ----------\
convert to integers /=/@</@=/ * // /===== ITOA ++++++++++\ /----------/
multiply @ \=!\=========/ // /++++++++++/ \----------\
convert back !/@!\============/ \++++++++++\ /----------/
and print the result \/ \.# * /++++++++++/ \--------#
/====================/ * \++++++++#
|
| /-<+>\ #/?=<<<<\!>>>>\ />>+<+<-\
| #\?===/! BMOV1 =====\ \->>>>+/ // /======== BSPL2 !\======?/#
| /->+<\ /===|=========== FMOV4 =/ // /<<+>+>-\
| #\?===/! FMOV1 =|===|==============\ /====/ /====== FSPL2 !\======?/#
| /==|===|==============|==|=======/
| * * *|* | * | * * * * * * *|* | * * * /+<-\
| * />@/<@/>>@/>>===\ /====>>\@<\@<\ * /==== ADD2 !\>=?/<#
\===== MUL2 =?/>@\==<#<<<==\ \!\<<<<@\>>>>-?/\ * // /-\
* \\ \/@========|======</ * // /== ZERO !\?/#
* * * \\* * * * | * * * * | * * * * *// //
\\ | \==========/ //
\======!\=======================/
Ethiopian Multiplication and number printing
/==!/==atoi==@@@-@-----#
| | /-\ /recurse\ #/?\ zero
$>,@/>,@/?\<=zero=!\?/<=print==!\@\>?!\@/<@\.!\-/
< @ # | \=/ \=itoa=@@@+@+++++#
/==\ \===?!/===-?\>>+# halve ! /+ !/+ !/+ !/+ \ mod10
# ! @ | #>>\?-<+>/ /<+> -\!?-\!?-\!?-\!?-\!
/-<+>\ > ? />+<<++>-\ \?!\-?!\-?!\-?!\-?!\-?/\ div10
?down? | \-<<<!\=======?/\ add & # +/! +/! +/! +/! +/
\>+<-/ | \=<<<!/====?\=\ | double
! # | \<++>-/ | |
\=======\!@>============/!/
Division
Input: cell -1 = numerator, cell 0 = divisor
Output: cell -1 = n DIV d, cell 0 = n MOD d
/-\
$?\<!\?/#!===+<<<\ /-\
\<==@\>@\>>!/?!/=<?\>!\?/<<#
| | #\->->+</
\=!\=?!/->>+<<?\#
#\?<<+>>-/
Multi-digit Print
/recurse\ #/?\ zero
print=!\@\>?!\@/<@\.!\-/
| \=/ \=itoa=@@@+@+++++#
! /+ !/+ !/+ !/+ \ mod10
/<+> -\!?-\!?-\!?-\!?-\!
\?!\-?!\-?!\-?!\-?!\-?/\ div10
# +/! +/! +/! +/! +/
Cat
This program will print out the entire memory. (Without EOF-detection)
/!$\ \>./
With EOF-detection (Assuming EOF = -1):
/$+?\# \>.-/
Square
Implementing the recursive definition: n^2 = (n-1)^2 + 2n + 1
# / ++<+<\ #<\ $?!/>>+<<-?\>!/>-?/<<+>?!/>+<\ \ up2 / \ \?- /
Square root
/>!/?\>=!/?\>!/=======?\<<<#
| \-/<-=\-/ \>>>+<<<-/
sqrt=>+<=!/?!/->-?\+>?/\
\\!=<<+>/<<+>/
\<\ //
\+\ //
\+ /
\/
Ackermann function
/==!/==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) ? ? | | |
\>>+<<-/!==========/ | |
# # | |
| |
#/?========\!==/ \==!/=======?\#
\->>+>+<<</ \>>>+<<<-/
This shows an interesting property of the language: routines can be written to run bidirectionally. The loop labelled (a>0) moves a value two cells left when run clockwise and moves a value two cells right when run counter-clockwise.
One could also perform tail recursion elimination by replacing "@/#" with "/".
Collatz sequence
/@+@@@+++# 27
| halve odd /===count<<\ /recurse\ #/?\ zero
$>@/===!/===-?\==>?!/-<+++\ \!/=!\@\>?!\@/<@\.!\-/
/+<-\!>\?-<+>/++++<\?>+++/*6+4 | | \=/ \=itoa=@@@+@+++++#
\=>?/<=!=\ | | ! /+ !/+ !/+ !/+ \ mod10
|//!==/========\ | /<+> -\!?-\!?-\!?-\!?-\!
/=>?\<=/\<+>!\->+>+<<?/>>=print@/\ln \?!\-?!\-?!\-?!\-?!\-?/\ div10
\+<-/!< ----------.++++++++++/ # +/! +/! +/! +/! +/
Hello world
/@@@@++++# #+++@@\ #-----@@@\n $@\H.@/e.+++++++l.l.+++o.>>++++.< .<@/w.@\o.+++r.++@\l.@\d.>+.@/.# \@@@@=>++++>+++++<<@+++++# #---@@/!=========/!==/
Binary coded variant
H e l l o , w o r l d ! $@\@\@\@\@\@\@\@\@\@\@\@\@\# | | | | | | | | | | | | | |!|!|!|!|!|!|!|!|!|!|!|!|@@@+@-@@@+++# 128 @ @ @ @ @ | | @ @ @ @ @ | \!\!\!\!\!|!|!\!\!\!\!\!|-@@+@@@@+++# 64 | @ @ @ @ @ @ @ @ @ @ @ @ |!\!\!\!\!\!\!\!\!\!\!\!\@@@-@++++# 32 | | | | | | | @ | @ | | | |!|!|!|!|!|!|!\!|!\!|!|!|+@+@++++# 16 @ | @ @ @ @ | | @ | @ | | \!|!\!\!\!\!|!|!\!|!\!|!|@@+++# 8 | @ @ @ @ @ | @ @ | @ @ | |!\!\!\!\!\!|!\!\!|!\!\!|++++# 4 | | | | @ | | @ @ @ | | | |!|!|!|!\!|!|!\!\!\!|!|!|++# 2 | @ | | @ | | @ @ | | | @ |!\!|!|!\!|!|!\!\!|!|!|!\+# 1 | | | | | | | | | | | | | \!\!\!\!\!\!\!\!\!\!\!\!\.># print and move
See also
- PATH, SNUSP's predecessor.
- LNUSP, another PATH-inspired language.
- Extensions to SNUSP, extensions to SNUSP.
- Small SNUSP, the prequel.