MSR
MSR or Match Switch Reverse is an esoteric programming language invented by User:GDavid.
The memory of a program is infinite.
Bits in memory are called fields.
Every field can be identified by <number of dimensions> whole numbers.
Programs have the following structure:
number of dimensions number of operations operations... number of set fields set fields... steps to step back or 0 to step forward steps to log after or 0 to disable logging
Operations have the following structure:
number of fields required to be set fields required to be set... number of fields required to be not set fields required to be not set... number of fields to be switched fields to be switched...
The fields specified to be switched in an operation are switched when all requirements are met.
Operations are executed in order.
Forward execution halts when no operation's conditions are met in one cycle.
Reverse execution halts when nothing to reverse or after <steps> cycles.
Example code
One bit increment (if overflow is not set)
1 2 1 i 1 o 2 i o 0 2 i o 1 i x 0 0
More compact
1 2 1 i 1 o 2 i o 0 2 i o 1 i x 0 0
i is address of data bit, o is address of overflow bit, x is 1 i if input is 1, 0 otherwise.
Computational class
Most likely a finite state automata.
But it's possible to write a BF interpreter in it for a finite tape length and a known program and input size.
It's also possible to write a BF interpreter in it for a finite tape length and a known program size that halts when it needs input.
After that, the input fields are set, the wait for input field is unset manually and the program is executed again with that data.
In both cases, the program to interpret is hard-coded in the interpreter.
The result would be most close to a linear bounded automata.
It would be possible to prepare it to handle a max string length long BF program with as long tape as possible, but it would probably be very slow and would be huge.
As real computers have finite memory too, it's possible to do anything using a BF interpreter in MSR that a real computer can do.
Implementations
The original interpreter written in C++
#include <iostream>
#include <vector>
#include <set>
using namespace std;
class op {
public:
op() {}
op(
size_t conditions,
vector<vector<long long> > condition,
size_t aconditions,
vector<vector<long long> > acondition,
size_t switches,
vector<vector<long long> > toswitch
) : conditions(conditions), condition(condition), aconditions(aconditions), acondition(acondition), switches(switches), toswitch(toswitch) {}
bool trycond(const set<vector<long long> >& world) {
for (size_t c = 0; c < conditions; c++) {
if (!world.count(condition[c])) {
return false;
}
}
for (size_t c = 0; c < aconditions; c++) {
if (world.count(condition[c])) {
return false;
}
}
return true;
}
void doswitch(set<vector<long long> >& world) {
for (size_t s = 0; s < switches; s++) {
set<vector<long long> >::iterator found = world.find(toswitch[s]);
if (found != world.end()) {
world.erase(found);
} else {
world.insert(toswitch[s]);
}
}
}
private:
size_t conditions;
vector<vector<long long> > condition;
size_t aconditions;
vector<vector<long long> > acondition;
size_t switches;
vector<vector<long long> > toswitch;
};
int main()
{
size_t dimensions;
cin >> dimensions;
size_t operations;
cin >> operations;
vector<op> operation;
operation.resize(operations);
vector<long long> v;
v.resize(dimensions);
for (size_t o = 0; o < operations; o++) {
size_t conditions;
cin >> conditions;
vector<vector<long long> > condition;
condition.resize(conditions, v);
for (size_t c = 0; c < conditions; c++) {
for (size_t d = 0; d < dimensions; d++) {
cin >> condition[c][d];
}
}
size_t aconditions;
cin >> aconditions;
vector<vector<long long> > acondition;
acondition.resize(aconditions, v);
for (size_t ac = 0; ac < aconditions; ac++) {
for (size_t d = 0; d < dimensions; d++) {
cin >> acondition[ac][d];
}
}
size_t switches;
cin >> switches;
vector<vector<long long> > toswitch;
toswitch.resize(switches, v);
for (size_t s = 0; s < switches; s++) {
for (size_t d = 0; d < dimensions; d++) {
cin >> toswitch[s][d];
}
}
operation[o] = op(conditions, condition, aconditions, acondition, switches, toswitch);
}
set<vector<long long>> world;
size_t set;
cin >> set;
for (size_t s = 0; s < set; s++) {
vector<long long> coord;
coord.resize(dimensions);
for (size_t d = 0; d < dimensions; d++) {
cin >> coord[d];
}
world.insert(coord);
}
unsigned long long steps;
cin >> steps;
unsigned long long log;
cin >> log;
if (steps == 0) {
bool changed = true;
while (changed) {
changed = false;
for (size_t o = 0; o < operations; o++) {
if (operation[o].trycond(world)) {
changed = true;
operation[o].doswitch(world);
}
}
if (log != 0 && steps % log == 0) {
cout << world.size() << endl;
for (vector<long long> coord : world) {
for (size_t d = 0; d < dimensions; d++) {
if (d != 0) {
cout << " ";
}
cout << coord[d];
}
cout << endl;
}
cout << steps << endl;
cout << endl;
}
steps++;
}
steps--;
cout << world.size() << endl;
for (vector<long long> coord : world) {
for (size_t d = 0; d < dimensions; d++) {
if (d != 0) {
cout << " ";
}
cout << coord[d];
}
cout << endl;
}
cout << steps << endl;
} else {
bool changed = true;
while (steps > 0 && changed) {
changed = false;
for (size_t o = operations - 1; o > 0; o--) {
operation[o].doswitch(world);
if (operation[o].trycond(world)) {
changed = true;
} else {
operation[o].doswitch(world);
}
}
if (log != 0 && steps % log == 0) {
cout << world.size() << endl;
for (vector<long long> coord : world) {
for (size_t d = 0; d < dimensions; d++) {
if (d != 0) {
cout << " ";
}
cout << coord[d];
}
cout << endl;
}
cout << steps << endl;
cout << endl;
}
steps--;
}
cout << world.size() << endl;
for (vector<long long> coord : world) {
for (size_t d = 0; d < dimensions; d++) {
if (d != 0) {
cout << " ";
}
cout << coord[d];
}
cout << endl;
}
}
return 0;
}