^!

^! (pronounced "caret-bang") is a stack-based esoteric programming language created by User:Ninesquared81.

Language overview

Data is stored on two stacks – the main stack and the auxiliary stack – which are both initially empty. Each ^! instruction manipulates one or both of the stacks, by pushing and popping values. There is only one data type in ^!, unsigned 8-bit integers, which wrap on overflow (i.e. arithmetic is modulo 256). Any source code text that is not part of the language is treated as a comment and ignored. The instructions are:

Instruction	Description
^	Push zero to the main stack
!	Increment the element at the top of the main stack
*	Pop and discard the element at the top of the main stack
:	Duplicate the element at the top of the main stack
,	Read a character from stdin and push it to the main stack
.	Pop the element at the top of the main stack and print it as an ASCII character to stdout
+	Add the top element of the main stack to the next element
-	Subtract the top element of the main stack from the next element
%	Swap the top two elements of the main stack
@	Rotate the top three elements of the main stack like so: ...c b a → ...b a c
>	Move the element at the top of the main stack to the top of the auxiliary stack
<	Move the element at the top of the auxiliary stack to the top of the main stack
?	Push 1 to the main stack if it contains elements, or 0 if it is empty
;	Push 1 to the main stack if the auxiliary stack contains elements, or 0 if it is empty
$	Pop the element at the top of the main stack and exit the program, using the popped value as the exit status
[ … ]	Repeatedly pop the top element of the main stack and execute the enclosed instructions if the popped element is non-zero
( … )	Ignore the text enclosed (nestable)

History

^! started out as a more convenient notation for writing Motorway programs, and as such shares many commands with it, albeit spelt differently. However, as ^! matured, it gained many features of its own, most notably a second stack.

Examples

Hello World

Full version with comments:

(loop to get powers of 2 on aux)
main and aux are both empty

^!!     start with 2
:[      while non zero
    :>      copy to aux
    :+      double (if top was 128, we'd get 256, but because cells are only 8 bits, this wraps around to 0)
:]      end while
<       we immediately bring back 128 and leave it at the bottom of the stack (unused)
 
(print "H")
main is 0 128
aux is  2 4 8 16 32 64

<:      get 64 from aux and duplicate it
<<@     get 32 and 16 and grab the duplicated 64
<::>    grab 8 duplicate it twice then place it back on aux
@+.     grab 64 again then add it to 8 to get 72 which is the ASCII code for 'H'

(print "e")
main is 0 128 64 32 16 8
aux is  2 4 8

%>      put 16 back on aux
%:>     copy 32 back to aux
@:>     copy 64 back to aux
+!!!!   add 64 and 32 to get 96 and increment to get 100
:!.     duplicate increment and print 'e'

(print "llo")
main is 0 128 8 100
aux is  2 4 8 16 32 64

:@+     duplicate 100 then grab 8 and add to 100
:::     duplicate three times (to get 4 copies -- two for now, one to increment, and one for later)
..      print twice ("ll")
!!!     increment three times to get 111 ('o')
:.      duplicate for later then print the result

(print ", W")
main is 0 128 100 108 111
aux is  2 4 8 16 32 64

<<:<<@  get 64 32 16 8 from aux and bring a copy of 32 to the top of main
:@:@+   duplicate 32 and 8 then add them
<:@+    get 4 from aux then add a copy to the 40 previously calculated
.       print 44 (',')
%>%.    put 4 back on aux then print 32 (' ')
+       add 4 and 16
%>      put 32 back on aux
+!!!.   add 20 to 64 then increment three times to print 87 ('W')

(print "orld")
:.      duplicate 111 then print ('o')
!!!.    increment three times then print ('r')
.       print 108 from before ('l')
.       print 100 from before ('d')

(print "!\n")
main is 0 128
aux is  2 8 32

<!.     get 32 from aux then increment and print ('!')
<<+.    get 8 2 from aux then add and print ('\n')

(final stack state)
main is 0 128       doesn't matter that there's data left
aux is empty

A minimised version:

^!!:[:>:+:]<<:<<@<::>@+.%>%:>@:>+!!!!:!.:@+:::..!!!:.<<:<<@:@:@+<:@+.%>%.+%>+!!!.:.!!!...<!.<<+.

Cat

,       get initial input from user
:[      while not EOF
    .       print current character
    ,       get next character
:]      end while
*       discard elements on stack

Truth-machine

(A program which prints '0' once if user inputs a '0', or '1' indefinitely if they input a '1'
(other cases are undefined))

,:              get user input and duplicate it
^!!!!:+:+::++   push 48 ('0') to main
-               (input - 48 (result is 1 or 0))

:[:^!- [^!$]^]  exit on bad input

[               if non zero (i.e. if user input '1')
    :.              print (a copy of) the user's input (i.e. '1')
^!]             continue to loop infinitely by pushing 1 as the condition

.               print the user's input (i.e. '0' -- this is unreachable from the infinite loop)

Computational class

^! is Turing-complete. This is demonstrated by translation from brainfuck.

Brainfuck to ^! transpiler

The following schema may be used to translate any brainfuck program to ^!:

• The main stack shall hold the current cell at its top, and then every cell to the right of the data pointer underneath.
• The auxiliary stack shall hold all the cells to the left of the data pointer.
• The ^! program shall start with an initial ^ instruction.
• Then, every brainfuck instruction shall be translated to an equivalent sequence of ^! instructions, which are tabulated below:

Brainfuck instruction	^! instruction(s)
>	>?^!-[^^]
<	<
+	!
-	^!-
.	:.
,	*,
[	:[
]	:]

Notes on the transpiler

In order to be Turing-complete, the number of memory cells must be unbounded. Rather than pre-allocating an arbitrary amount of memory at the beginning of the program, the main stack is grown ad-hoc. This is what is going on with the > instruction. First, the top element of the main stack is pushed to the auxiliary stack, which corresponds to the > instruction in brainfuck (using the memory model discussed above). Then, if the main stack is empty, an extra, zero-initialized element is pushed to main to be the new current cell. The initial ^ ensures that the main stack starts with one element.

The transpiler has been implemented in ^! itself.

External resources

• Reference implementation on GitHub – written in C.
• Brainfuck to ^! transpiler – written in ^!.