Interfrac
Interfrac is a declarative esolang. It was discovered by User:Orby in 1994.
Introduction
In 1994, at the tender age of ten, I made a startling discovery about fractions. They tried to correct me, but I knew in my heart I had discovered something huge. It is a fact that many school children realize. The authorities have been repressing this knowledge for generations. Interfrac is the guiding beacon that will liberate us all. Interfrac is the first programming language that treats fractions how we all know they ought to be treated:
(a / b) + (c / d) = (a + c) / (b + d)
They told you it was wrong, but I am here to share the truth. An Interfrac program is a list of fractions. If those fractions can be added correctly to (n / n) where n is any integer, then the integer n is accepted by the program. Repetitions are allowed.
Edit: There is a proof that the formula is invalid.
Examples
An example of an Interfrac program is
-10/20, 10/-5
Notice that -10/20 + 10/-5 + 10/-5 = (-10 + 10 + 10)/(20 + -5 + -5) = 10/10. Therefore, the input 10 is accepted by the program. In fact, all positive multiples of 10 are accepted by the program. Another example:
-2/5, 1/-7, 1/-3, 1/-2
Notice that -2/5 + -2/5 + 1/-7 = (-2 + -2 + 1)/(5 + 5 + -7) = -3/3 does not mean -3 is accepted. However, -2/5 + 1/-3 + 1/-2 = (-2 + 1 + 1)/(5 + -3 + -2) = 0/0 means 0 is accepted. Another way of saying this is to say that this program halts on empty input.
Implementation
Here's an implementation of the logic behind Interfrac, written in Brachylog version 2. (However, because Brachylog isn't very good at parsing, it takes the program using a different syntax, [[_10,20],[10,_5]].) The program is given as a command-line argument, the input on standard input. (You can also use I as the input, and then the interpreter will print some number that would be accepted.)
~{~h=∋ᵐ\+ᵐ=h}
Computational class
Interfrac is NP-complete:
- Interfrac is capable of solving the wikipedia:subset sum problem, and thus is at least NP-complete;
- The fate of Interfrac programs can be predicted via wikipedia:integer linear programming, and thus Interfrac is at most NP-complete.