^!
^! (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 ^!.