But Is It Art?
But Is It Art? is an esoteric programming language created by User:ais523 in 2017, as a constraint-solving tarpit.
Syntax
But Is It Art? uses a typical source code design for 2-dimensional languages; each character of input other than newlines is placed in sequence onto a 2-dimensional canvas, with each character typically being placed to the right of the previous character, or at the start of the next line down after a newline is read. The "space" character (32 if the program is encoded in ASCII) is treated as nonexistent after this step, and only serves to adjust the location of the rest of the source code on the canvas.
After this, the source code is split into orthogonally connected regions, each of which is called a tile. For example, there are three tiles in the following program (each of which happens to consist entirely of a single character, but replacing any of the non-space non-newline characters with other non-space non-newline characters would lead to the same division into tiles):
A BBBB A B B AA CC A CC
The actual position of the tiles on the canvas is irrelevant (although their orientation is relevant), so the above program is equivalent to this one:
CC A CC A BBBB AA B B A
I/O encoding
For most characters that appear inside a tile, their actual identity is irrelevant; almost all non-space non-newline characters are interchangeable. However, if a letter appears on a tile, that's a request to do I/O. I/O is done a nybble at a time, with the more significant nybble first. There are, of course, 16 possible nybbles; when doing input, these are encoded as a for 0, b for 1, c for 2, and so on, up to p for 15; and when doing output the same encoding is used but in capital letters (so A is 0, B is 1, and P is 15).
Semantics
A given But Is It Art? program, with given user input, is successful if and only if the following condition is true:
It is possible to dissect some (non-degenerate, i.e. at least 1 character long in each dimension) rectangle of non-space characters into tiles, such that each tile appears in the program in the same orientation, and the sequence of lowercase letters in the rectangle (when read in normal English reading order, top-to-bottom and left-to-right) is the encoding of the entire contents of standard input. This rectangle is called a witness rectangle for the program and input.
Note that it's possible to use a tile more than once, or less than once, when forming the witness rectangle.
If the program is successful for the given input (i.e. at least one witness rectangle exists), an implementation must produce the output encoded by the sequence of capital letters that appears on some witness rectangle (again in normal English reading order), and then exit, indicating that no error occurred. This means that programs can be nondeterministic, in the sense that more than one output is reasonable for a given program. In the case when more than one witness rectangle exists, implementations are not required to select any particular witness rectangle; both consistently selecting the same rectangle each time the program is run, and picking a random rectangle each time the program is run, are reasonable behaviours.
If the program is not successful for the given input, then an implementation has two options:
- If it can prove that the program is not successful, it should exit with an error message, indicating the existence of an error.
- If it cannot prove that the program is not successful, it enters an infinite loop.
It's mostly up to the implementation how much effort it puts into proving that no witness rectangle exists; one implementation could enter an infinite loop on a program/input combination, while another implementation could exit with an error on the same program and input. However, an implementation must at least be able to definitively determine whether a witness rectangle exists in cases where every tile in the program contains a lowercase letter (because such problems can be solved simply via brute force). However, an implementation must always eventually terminate if a witness rectangle does exist.
Example
The following program is successful if and only if the input is empty:
### + = # ++ ==
because it can construct the following witness rectangle for the empty input:
###= #+== +++= ++==
but the fact that it contains no lowercase letters means that any input other than the null string can't possibly match the input sequence.
The following program is conjectured to accept exactly the strings of As (as nybbles: eb) whose length is a composite number:
2eb2 eb3 eb eb 222 333 555 777 2 3 5
The following is an example witness rectangle accepting the string AAAAAAAAA of length 3 × 3 = 9.
2eb2eb3eb 222333555 2eb3eb5eb 555555555 5eb5eb5eb 777777777
Computational class
Numerous Turing complete languages have a fairly direct translation into But Is It Art?, such as Thue (although you typically have to change the halting behaviour by adding an explicit halt state to the language you're compiling from, doing so rarely affects the computational class); But Is It Art? is thus also Turing complete. (Most of the constructions work via choosing the tiles in such a way that the witness rectangle forms a complete history of the execution of the program being compiled.)
External resources
- Implementation at https://github.com/qpliu/esolang/blob/master/random/art.hs