^!
^! (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)
Clean
This program 'cleans' a ^! source file by removing all comments and non-instruction characters.
,:[
( Prepare main stack with ASCII codes )
want ( 33 36 37 42 43 44 45 46 58 59 60 62 63 64 91 93 94 )
> (-> c aux)
^!!!!:+ 8
:> 8 (-> 8 aux)
:+:+ 32
:> 32 (-> 32 aux)
!:!!! 33 36
:! 33 36 37
:!!!!! 33 36 37 42
:!:!:!:!: 33 36 37 42 43 44 45 46 46
^!!!!:: 33 36 37 42 43 44 45 46 46 4 4 4
++ 33 36 37 42 43 44 45 46 46 12
+ 33 36 37 42 43 44 45 46 58
:!:> 33 36 37 42 43 44 45 46 58 59 (-> 59 aux)
:!:!!:!:! 33 36 37 42 43 44 45 46 58 59 60 62 63 64
<<:> 33 36 37 42 43 44 45 46 58 59 60 62 63 64 (59 32 <-> 32 aux)
+ 33 36 37 42 43 44 45 46 58 59 60 62 63 64 91
:!!:! 33 36 37 42 43 44 45 46 58 59 60 62 63 64 91 93 94
<< (32 8 <- aux)
+:! 40 41
< 40 41 (c <- aux)
( Handle comments )
: 40 41 c c
@- 40 c (c-41)
:[*^^!-^] 40 c 0|(-1)
![ 40 c (1|0 loop?)
(if c == 41 -- right bracket)
<* assume aux has elements
^]
:@- c (c-40)
:[*^^!-^]![
(if c == 40 -- left bracket)
^>
^]
( Handle instructions )
^;[?[*?]^^!-^]![
(if aux empty)
> 33 36 37 42 43 44 45 58 59 60 62 63 64 91 93 94 (-> c aux)
?[
(while main non-empty)
<: (main x c c <- aux)
@- c (c-x)
:[*^^!-^]![
(if c == x)
:.
^]
> (main -> c aux)
?]
< (c <- aux)
*
^]
,:]
^!!!!!:+. final newline
Using itself as its own input:
,:[>^!!!!:+:>:+:+:>!:!!!:!:!!!!!:!:!:!:!:^!!!!::+++:!:>:!:!!:!:!<<:>+:!!:!<<+:!<:@-:[*^^!-^]![<*^]:@-:[*^^!-^]![^>^]^;[?[*?]^^!-^]![>?[<:@-:[*^^!-^]![:.^]>?]<*^],:]^!!!!!:+.
Less than
This program fragment evaluates x < y for x and y on the stack (y on top). The same program can be adapted for x ≥ y by inverting the condition (i.e. change line 1 to ^!> and line 10 to <*^>).
1 ^> initialise result to false (0) and store on aux 2 :[ while (y != 0) 3 %:@% (x y --> x y x) 4 :[* if (x != 0) 5 ^!-% decrement y (main... (y-1) x) 6 ^!-% decrement x (main... (x-1) (y-1)) 7 ^^!- push (-1) to skip else 8 ^] 9 ![ else 10 <!> set conditon to true (incrementing 0 to 1) 11 *^ zero out y (main... x=0 y=0) 12 ^] 13 :] 14 ** drop x and y 15 < load result from aux
Multiply
This program fragment mulitplies the top two stack elements (a and b) by repeated repetition.
1 ^> initialise result to 0 2 :[ for (; b != 0; b--) 3 %: duplicate a 4 <+> add a to result 5 % swap a and b (b on top) 6 ^!-:] decrement b and loop 7 ** drop a and b 8 < get result back from aux
Power
This program fragment raises the element under the top (b) to the power of the top element (n).
1 ^!> initialise accumulator to 1 2 :[ for (; n != 0; n--) 3 %: duplicate b 4 < get accumulator from aux 5 ^>:[%:<+>%^!-:]** left multiply accumulator by b 6 % swap b and n (n on top) 7 ^!-:] decrement n and loop 8 ** drop b and n 9 < get result from aux
Integer division
This program fragment finds the quotient and remainder of the top two stack elements (n and b). It makes use of the greater-than program described above (with the correct alterations), but it is used in minimised form here for brevity. This uses a very simple algorithm with repeated division. When n < b, we have found the remainder. The quotient is simply the number of subtractions needed to reach this condition. Note that division by zero causes an infinite loop.
1 ^> store quotient (initally 0) on aux for later 2 %:@:@% get (n b n b) on stack 3 ^!>:[%:@%:[*^!-%^!-%^^!-^]![<*^>*^^]:]**< (condition n >= b) 4 [ while (n >= b) 5 :>-< decrement n by b 6 <!> increment quotient 7 %:@:@% get (n b n b) again 8 ^!>:[%:@%:[*^!-%^!-%^^!-^]![<*^>*^^]:]**< (conditon n >= b) 9 ] 10 % swap n and b (NOTE: n = r, the remainder.) 11 <% get q back and swap it with r
Get number
This program fragment gets a number from the user and stores it (modulo 256) on the stack.
1 ^> initialise number to zero and store on aux 2 3 ^!!!!:+::+::++:@!!:@ (48 10 10 48) 4 ,%- subtract 48 from input 5 :@ (48 10 (in-48) (in-48) 10) 6 ^>:[%:@%:[*^!-%^!-%^^!-^]![<!>*^^]:]**< (condition (in-48) < 10) 7 [ while ((in-48) < 10) 8 <:+::+:++ mulitply previous digit by 10 9 +> add new digit and store back on aux 10 %:@:@ restore stack to (48 10 10 48) 11 ,%-:@ set up next input 12 ^>:[%:@%:[*^!-%^!-%^^!-^]![<!>*^^]:]**< (condition (in-48) < 10) 13 ] 14 *** drop (48 10 (in-48)) 15 < get number from aux
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.
Certain aspects of brainfuck which are implementation-defined are defined by ^! semantics. Namely, memory cells are 8-bit and wrap on overflow, and EOF returns 0. Also, negative memory cells are not allowed, and trying to access them will result in a stack underflow error. Any brainfuck program adhering to these specifications will produce a valid ^! program under the transpiler.
Although the transpiler is useful for showing Turing-completeness, the output of the transpiler is often unidiomatic for ^!. Since brainfuck does not view its memory in terms of two stacks, certain accommodations have to be made to make the stacks act like brainfuck's memory cell array which would be superfluous in handwritten ^!. Idiomatic ^! embraces the stack semantics of its memory, which can often lead to shorter code than the output of the transpiler. For example, brainfuck has to make heavy use of > and < to move between different cells, whereas ^! can save values by simply burying them on main, and then later uncovering them by either popping the higher elements or by using the % or @ instructions.
The transpiler has been implemented in ^! itself. For best results, the input or output (or both) should be redirected, otherwise the initial ^ is written before any input is taken.
External resources
- Reference implementation on GitHub – written in C.
- Brainfuck to ^! transpiler – written in ^!.