SNUSP

From Esolang
Jump to navigation Jump to search

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:

  1. The instruction at the instruction pointer is carried out.
  2. 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

External resources