This program translates Minsky register machine programs to Rui programs.

mrm_rui.c

/*	mrm_rui.c -- translate Minsky register machine to Rui
	Daniel Cristofani
	6/2020	*/

/*	This program translates register machine programs, as described in Marvin
	Minsky's 1967 book _Computation: Finite and Infinite Machines_, into Rui
	programs as described at https://esolangs.org/wiki/Rui, thus proving Rui
	to be Turing-complete.

	Minsky's book gives several varieties of register machine. This program
	accepts the versions from section 11.1, and provides these five commands:

	2*       zero register 2 (for instance)
	2'       increment register 2
	2-5      if register 2 nonzero, decrement it; else jump to 5th instruction
	H        halt
	g5       jump unconditionally to instruction 5

	A final halt instruction will be added at the end of the program if not
	provided explicitly. Whitespace is ignored, at least between instructions.

	Registers are identified by a natural number; these identifiers need not
	be consecutive, but each must (as an arbitary restriction) be less than
	the program's length in bytes. Values will be read into each at program
	start, and output at program end, in ascending order.

	This program reads a register machine program from a file specified as a
	command-line argument, and outputs its Rui translation to standard output.

	Code should mostly be fairly self-explanatory, but I should perhaps note:
	this program keeps "lists" of three things: source instructions, registers
	that are used, and instruction positions that are targets of at least one
	conditional jump (as each of these needs its own line of Rui code for an
	auxiliary thread to run). The crossreference_arrays function generates
	"packed" versions of the register and target arrays, and links entries in
	the packed and unpacked versions of each to each other. Confusingly, I've
	marked these "o" and "c" as a shorthand for "ordinal" and "cardinal".

	This version of the program comments the Rui program to make it easier to
	see which parts of the source code the Rui code corresponds to.	*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/stat.h>

struct inst{
	char code;
	int reg;
	int target;
};

FILE *prog;
struct stat info;
char *source;
int charct;
int *rc, *ro, rmax, rct; // registers
int *tc, *to, tmax, tct; // targets
struct inst *i; int ict;
int x, y;

int crossreference_arrays(int *c, int *o, int max){
	int x, y;
	for(x=0,y=0;x<=max;x++){
		if (c[x]){
			c[x]=y;
			o[y++]=x;
		}
	}
	return y;
}

int main(int argc, char **argv){
	if (!(prog=fopen(argv[1], "r"))){
		fprintf(stderr, "can't open the file \"%s\".\n", argv[1]);
		exit(1);
	}
	stat(argv[1], &info);
	rc=calloc(info.st_size, sizeof (int));
	tc=calloc(info.st_size/3+2, sizeof (int));
	source = calloc(info.st_size+1, 1);
	i = calloc(info.st_size+1, sizeof (struct inst));
	if (fread(source, 1, info.st_size, prog)!=info.st_size)
		fprintf(stderr, "problem reading %s.\n",argv[1]), exit(1);
	while(y<info.st_size){
		switch(source[y]){
			case '0': case '1': case '2': case '3': case '4':
			case '5': case '6': case '7': case '8': case '9':
				sscanf(source+y, "%d%n",(&(i[ict].reg)), &charct);
				y += charct;
				if (!rc[i[ict].reg]){
					rc[i[ict].reg]=1;
					rct++;
				}
				if (i[ict].reg>rmax) rmax=i[ict].reg;
				while (source[y]==' '||source[y]=='\t') y++;
				switch(source[y]){
					case '\'':
						i[ict++].code='\''; y++; break;
					case '*':
						i[ict++].code='*'; y++; break;
					case '-':
						i[ict].code='-';
						y++;
						while (source[y]==' '||source[y]=='\t') y++;
						sscanf(source+y, "%d%n",(&(i[ict].target)), &charct);
						y+=charct;
						if(!tc[i[ict].target]){
							tc[i[ict].target]=1;
							tct++;
						}
						if (i[ict].target>tmax) tmax=i[ict].target;
						ict++;
						break;
					default:
						fprintf(stderr, "Unexpected character %c at byte %d.\n",
							source[y],y); exit(1);
						break;
				}
				break;
			case 'H':
				i[ict++].code='H'; y++; break;
			case 'g':
				i[ict].code='g';
				y++;
				sscanf(source+y, "%d%n",(&(i[ict++].target)), &charct);
				y += charct;
				break;
			case ' ': case '\n': case '\t': case '\r':
				y++; break;
			default:
				fprintf(stderr, "Unexpected character %c at byte %d.\n",
					source[y],y); exit(1);
				break;
		}
	}
	if(i[ict-1].code != 'H') i[ict++].code='H';
	ro=calloc(rct, sizeof (int));
	to=calloc(tct, sizeof (int));
	crossreference_arrays(rc, ro, rmax);
	crossreference_arrays(tc, to, tmax);
	for(x=0;x<rct;x++) printf("r*%d",tct+ict+x+2);
	printf("=1 #read initial values\n");
	for(y=0;y<ict;y++){
		switch(i[y].code){
			case '\'':
				printf("+%d%s #%d: %d\'\n",rc[i[y].reg]+tct+ict+2,
					strchr("g\'",i[y+1].code)?"":".", y+1,i[y].reg);
				break;
			case '*':
				printf("-%d #%d: %d*\n",rc[i[y].reg]+tct+ict+2, y+1, i[y].reg);
				break;
			case '-':
				printf("-%d+%d...*%d-1 #%d: %d-%d\n", rc[i[y].reg]+tct+ict+2,
					tc[i[y].target]+ict+2, rc[i[y].reg]+tct+ict+2,
					y+1, i[y].reg, i[y].target);
				break;
			case 'H':
				for(x=0;x<rct;x++) printf("-%dw",tct+ict+x+2);
				printf("! #%d: H (output registers and halt)\n", y+1);
				break;
			case 'g':
				printf(":%d #%d: g%d\n",i[y].target+1, y+1, i[y].target);
				break;
		}
	}
	for(y=0;y<tct;y++)
		printf("-0=1~.:%d #jump to instruction %d\n", to[y]+1, to[y]);
	for(y=0;y<rct;y++)
		printf("=%d:%d #register %d\n", tct+ict+y+2, tct+ict+y+2, ro[y]);
	exit(0);
}