Chaingate
Chaingate is a family of esoteric programming languages created by User:ais523 in 2017. The main inspirations were Incident and Malbolge, although the language is somewhat more elegant than either. The language also fits into ZISC form; however, its single command is based on primitives that exist in many high-level languages but not typical assembly languages, so although it admits short implementations, it does not make for as small an executable as most ZISCs do. :≠ is also relevant as an influence; programming in :≠ and in Chaingate is fairly similar, because both languages have reversible data storage and a method of defining functions that can be turned on and off, but not recursed into.
A specific Chaingate language has a name of the form Chaingate-f, where f is a function whose domain and codomain are equal (let's call this set A); each possible f leads to a different member of the Chaingate family. ("Function" here means a mathematical function, i.e. that deterministically maps each possible input to a specific output, in finite time. This language specification assumes that elements of A can easily be compared for equality; in some cases, the choice of a particularly weird A may make the language uncomputable, which is an interesting subject but one that isn't discussed in detail here.)
Syntax
A Chaingate program is a list of elements of A. This list is treated as a circular list, i.e. moving right from the last element moves back to the first element. The programs act as both instructions and data (the language is self-modifying). The program starts executing at the first instruction; implementations of Chaingate languages can either implement an instruction pointer that points to the currently executing program, or else rotate the entire program to always keep the currently executing instruction at the start (the two points of view are equivalent).
Semantics
When an instruction a executes, the following happen, in order:
- The instruction a is mutated to f(a), i.e. each instruction is modified when run (according to f, which serves a similar purpose to Malbolge's "encryption function"). Unlike Malbolge, the mutation is done before running the command rather than afterwards (which is mostly equivalent, but avoids the weird behaviour in which jumps can end up encrypting the instruction before the jump target).
- If exactly one command other than the newly-mutated instruction has the same value as that instruction now has, the instruction pointer will be moved to point at that command (i.e. each command is a jump instruction which jumps to "the other copy" of itself, or does nothing if "the other copy" is not uniquely defined). Alternatively, the program can be rotated to move that command onto the instruction pointer; it comes to the same thing.
- Finally, the instruction pointer moves to the right (so it's pointing at the command after the command that just executed, or after the jump target if there was a jump). That will be the next command to execute.
Execution continues until memory enters exactly the same state twice (i.e. all instructions have mutated themselves back to the values they had at some point in the past, and the instruction pointer is pointing to the same instruction it was at that time), at which point the program halts (because it's obviously in a tight infinite loop). With some programs, this situation might never occur, in which case the program just keeps executing forever.
Free Chaingate
One interesting special case of Chaingate is Free Chaingate; in this language, A is the set of pairs 〈m, n〉 where n is a positive integer or infinity and m is a rational number from 0 inclusive to n exclusive, and f maps 〈m, n〉 to 〈(m+1 mod n), n〉. This makes it trivial to find arbitrarily many cycles of any given length (including infinitely long cycles), and thus provides all the tools needed to write a Chaingate program; in particular, if any Chaingate language with computable f and computable equality on A is Turing-complete, then Free Chaingate is (the ability to make finitely many irreversible changes that some fs have doesn't change the computational class of the language because you could just start executing after those have happened, and thus the lack of such changes in Free Chaingate doesn't matter).
Free Chaingate does have the fairly frustrating property that its reversibility makes it impossible to enter a tight infinite loop unless you're already in one, and thus any program that halts provably halts. As such, it makes sense to add an extra pair to A (such as 〈1,1〉) simply to make halting possible (because it will become 〈0,1〉 after evaluating f once and then stay there, thus providing one reversibility break that can be used to enter a detectable infinite loop and causing the program to halt). This variant of the language is known as Freer Chaingate.
Computational class
ais523 believes that Free Chaingate (and Freer Chaingate) are Turing-complete, but has not yet managed to formally prove this.
One interesting point of note is that Free Chaingate can fairly trivially implement The Amnesiac From Minsk level 4 (whose computational class is unknown); implement a counter as the difference between the m values of two instructions 〈m, ∞〉 – as TAFMl4 ensures that the counter values never go negative, the instructions will always have values in the same relative order, and thus running a specific instruction will increment one counter and decrement another, as required. If the counter is decremented to 0 – i.e. an instruction changes value to equal that of another instruction – control flow will move to just after the decremented counter, otherwise it'll be just after the incremented counter, which is exactly how TAFMl4 defines which trigger to run. A trigger can then be implemented as an instruction whose n part is 1, serving as a goto from just after a counter to just before a counter; usefully, TAFMl4 requires that each counter is the destination of at most one (in fact, exactly one) trigger, so the gotos are stable and always pass execution from one to the other. (Note that even if TAFMl4 turns out to be Turing-incomplete, Free Chaingate might nonetheless be Turing-complete via some other mechanism.)
Implementation
This Perl module, which must be named Chaingate.pm, implements both Chaingate (in general) and Free and Freer Chaingate in particular:
package Chaingate;
require Exporter;
our @ISA = qw(Exporter);
our @EXPORT_OK = qw/chaingate chaingate_free_f/;
=head2 $Debug
Set C<$Chaingate::Debug> to a truthy value in order to get debug output to
stdout (specifically, the state of the program every step).
=cut
our $Debug = 0;
=head2 chaingate
Implements Chaingate with a given function and program. The function is the
first argument; all other arguments specify the program.
This implementation assumes that program elements can be compared via C<eq>, and
that their stringifications will not contain the value of C<$;>. This will often
be the case, but you should probably avoid references in the program (unless
they have an overloaded stringifier), as you probably meant to compare the
I<contents> of the references, rather than the I<values> like this function
does.
=cut
sub chaingate {
my $function = shift;
my @program = @_;
my $ip = 0;
my %seen = ();
local $" = $;;
while (!exists $seen{"$ip @program"}) {
if ($Debug) {
print+($_ == $ip ? "[".$program[$_]."] " : $program[$_]." ")
for 0..$#program;
print "\n";
}
$seen{"$ip @program"} = undef;
$program[$ip] = $function->($program[$ip]);
my @ips = grep {$program[$_] eq $program[$ip]} 0..$#program;
if (2 == scalar @ips) {
$ip = $ips[$ips[0] == $ip ? 1 : 0];
}
$ip++;
$ip %= scalar @program;
}
}
=head2 chaingate_free_f
An implementation of the I<f> from Free Chaingate. (As such, calling
C<chaingate> with C<\&chaingate_free_f> as its first argument produces a Free
Chaingate interpreter.) Can also be used for Freer Chaingate.
The argument format is C<"m/n">, i.e. arguments are strings with I<m> and I<n>
separated by a slash.
=cut
sub chaingate_free_f {
$_[0] =~ m=/=p or die "No / in Free Chaingate element '$_[0]'";
(${^PREMATCH} + 1 >= ${^POSTMATCH}) ?
(((${^PREMATCH} + 1) - ${^POSTMATCH}) . "/" . ${^POSTMATCH}) :
((${^PREMATCH} + 1) . "/" . ${^POSTMATCH});
}
1;