Circlefuck

From Esolang
Jump to: navigation, search

Circlefuck is a self-modifying derivative of brainfuck, designed in 2012 by User:Koen. It has two particularities: it operates on a finite (and cyclic) tape, and the code is included in the tape. It is an example of a von Neumann architecture.

A program in circlefuck is a non-empty sequence of characters; initially the tape's length is equal to the program's length, and every cell, which is bounded to one byte, contains one char from the program. There are two pointers, refered to as the data pointer and the instruction pointer. Initially both pointers points to the 'first' cell, the cell that contains the first char from the program.

Execution consists in the loop:

  • execute the char under the instruction pointer as an instruction
  • move the instruction pointer to the next cell

Since the tape is circular, that loop is possibly infinite, thus the need for a "halt" instruction.

Instructions

Symbol Instruction
>
Move the data pointer to the next cell
<
Move the data pointer to the previous cell
+
Increment the cell under the data pointer (wrapping)
-
Decrement the cell under the data pointer (wrapping)
.
Output the ascii char signified by the cell under the data pointer
,
Take one byte from input and store it in the cell under the data pointer, or no-op on end of file
[
If the cell under the data pointer is 0, set the instruction pointer to the cell containing the matching ]
]
If the cell under the data pointer is nonzero, set the instruction pointer to the cell containing the matching [
@
Halt execution
#
Move the instruction pointer to the next cell, so that the next instruction will be skipped
{
Insert a new cell, initially containing 0, between the cell under the data pointer and the previous cell, and move the data pointer to that new cell
}
Delete the cell under the data pointer and move any pointer that was pointing to that cell to the next cell
any other char
No-op

Note that if the instruction pointer encounters a [ with no matching ] while the cell under the data pointer is 0, or if it encounters a ] with no matching [ while the cell under the data pointer is nonzero, execution is immediately suspended and the program is considered to never halt.

Escape sequences

Because the initial state of the tape corresponds to the program as it is written, there is a need to represent non-printable bytes in the program. Note that all references to 0 in the instruction descriptions above refer to the numeric value 0, and not to the character '0'. Any escape sequence will be converted into the appropriate byte before execution begins - an escape sequence counts as one character only for the purpose of determining the program's (and thus the tape's) length. Escape sequences begin with the character \; if the program contains an occurrence of that character outside of a correct escape sequence, a syntax error should occur. This, and the empty program, are the only possible syntax errors - all strings of characters are valid circlefuck programs.

Sequence Remarks
\NNN NNN is a three-digit decimal number between 000 and 255 (digits 0-9)
\oNNN NNN is a three-digit octal number between 000 and 377 (digits 0-7)
\xNN NN is a two-digit hexadecimal number between 00 and FF (digits 0-9A-Fa-f)
\N N is a one-digit hexadecimal number between 0 and F (digits 0-9A-F only)
\\ Backslash: equivalent to \092
\space Space: equivalent to \032
\n Linefeed: equivalent to \A
\r Carriage return: equivalent to \D
\t Horizontal tabulation: equivalent to \9
\b Backspace: equivalent to \8

In particular, \n, \A, \010, \o012 and \x0A are equivalent.

Any printable character that is not part of an escape sequence is equivalent to \NNN, where NNN is its ascii value. In circlefuck, "printable" characters correspond to the ascii values in the range 33-126. Non-printable characters outside of escape sequences are ignored, but whitespace (newlines, spaces and horizontal tabs) are not allowed inside escape sequences (except for \space), and act as separators: for instance \000 is the byte 0, but \0 00 is the byte 0 followed by twice the char '0'.

Example programs

Due to the lack of an interpreter, the following programs have not been tested yet and might not be free of bugs.

Hello, World!

Because the symbol , is also an instruction, the following program outputs "Hello World!" followed by a newline, but without the comma:

Hello\ World!\n\0[.>]@

All problems are resolved by placing the data area to the left, so that the instruction pointer never hovers over it:

<[.<]@\0\n!dlroW\ ,olleH

Another solution is to use self-modifying code to transform a harmless * into a , after the instruction pointer has safely passed through it:

Hello*\ World!\n\0>>>>>++<<<<<[.>]@

Quine

Because code and data are merged, writing a quine is very easy. However, in order to keep both pedantry and simplicity, no escape sequence must be used, so the value 0 cannot be in the initial tape. The following program uses '!' as a marker of the end of the program, hence the sequences of 33 - or + (because '!' is \033).

ThisIsAQuine---------------------------------[+++++++++++++++++++++++++++++++++.>---------------------------------]+++++++++++++++++++++++++++++++++.@!

A much shorter version uses the instruction { to insert a new cell containing the value 0.

{>[.>]@

Cat program

{,[.[-],]@

Narcissist

This program will terminate if its input is equal to its source code, or enter an infinite loop if the input is different. Note that it could be easily modified to output '1' or '0' instead of terminating or not terminating, for instance by replacing the two occurrences of [] with a code that outputs '0' and the @ by a code that outputs '1'. Remark: in order for this program to be considered a Narcissist, the sequence \0 at the end of the program must be considered equivalent to end of file at the end of input. This is not a pedantic narcissist, as some might consider that \0 is merely a backslash followed by a 0.

[{,>[-<->]<[]}>]{-,+[]}@\0

Input / output

Circlefuck-i

Circlefuck merges code and data; however, it still relies on data from outside of the initial tape, because of the , input instruction. It is possible to go one step further and merge input with the initial tape. That variation shall be referred to as circlefuck-i. It includes a third pointer called the input pointer, and recognizes one more special character, !. When executed as an instruction it is a no-op (just like any non-special character), but:

  • if there is no ! in the program, the input pointer initially points to the same cell as the other two pointers
  • if there is at least one ! in the program, the input pointer initially points to the cell just after the first !

Note that the initial value of the input pointer depends solely one the initial tape, not on the program as it is written - so \033, \o041 and \x21 are equivalent to !, and if there is only one ! and it is the last character of the program, then the input pointer points to the 'first' cell, the same cell as the other two pointers.

Symbol Instruction
> < + - . [ ] @ # { }
Identical to circlefuck
,
If the cell under the input pointer does not contain the value 255, then overwrite the cell under the data pointer with a copy of the cell under the input pointer, and move the input pointer to the next cell
any other char
No-op

Obviously, circlefuck-i does not allow for interactive I/O. It is suggested, though, that implementations supporting circlefuck-i redirect standard input to extra cells, with the input pointer initially on the first of those cells.

Circlefuck-o

It is possible to go yet one step further by merging output with the final tape: that variant is called circlefuck-o. There is a fourth pointer, the output pointer, initially set to the 'first' cell. The output of a circlefuck-o program is the content of the tape at the end of execution, with the cell under the output pointer as the first cell - if the program doesn't halt, there is no output.

Symbol Instruction
> < + - , [ ] @ # { }
Identical to circlefuck
.
Overwrite the cell under the output pointer with a copy of the cell under the data pointer
:
Move the output pointer to the next cell
;
Move the output pointer to the previous cell
any other char
No-op

The variant circlefuck-io combines the additions of both circlefuck-i and circlefuck-o.

Example program: quine

Writing a quine is even more easy in circlefuck-o, though it is to be noted that if the program doesn't contain a @ (or creates a @ through self-modification) there will be no output.

ThisIs@Quine

Computational class

No proof has been provided yet, but it is suspected that circlefuck is Turing-complete. It is essentially a superset of brainfuck: the only difference is the finite tape, but the { instruction should be enough to fix it.

See also