Insert, a language for self-modifying code

Insert, a language for self-modifying code

If you ever find yourself with time to kill and crave a fun challenge, you can write a program that prints out its own source code, called a quine. Go on, give it a try, it's good fun!

Once that's done, what's to stop you from modifying the source code instead of printing it verbatim, slowly shifting forms as you iterate on each successive output? Naturally, you'll want to make a game that's played in its own source code (click for an animation):

#include<stdio.h>
#define z else
#define y return
#define x int
#define w if(
#define v putchar(
#define B v 10);
#define A v 92);
/* IOCCC29, w = up, e = down */
x a= 32 ; x b= 6 ; x c= -1 ; x d= 1 ; x e= 5 ; x f= 10 ; x g= 62 ; x h= 5 ;
x i[6]={ 1,3,1,4,1,0} ; char*j[]={ "\
\ #include<stdio.h>'#define$z$else'#define$y$return'#define$x$int'#defin\
e$w$if('#define$v$putchar('#define$B$v$10);'#define$A$v$92);''/*$IOCCC\
29,$w$=$up,$e$=$down$*/''x$a=","32",";x$b=","6",";x$c=","-1",";x$d=","\
1",";x$e=","5",";x$f=","10",";x$g=","62",";x$h=","5",";x$i[6]={1,3,1,4\
,1,0};char*j[]={","","};x$k=0;x$l=1;x$m(){l++;w$l==1)y!v$44);w$l==2)y!\
v$34) ;char$o=j[k][l-3];w!o){l=0;k++;y!v$34);}w$o==34){A$y$v $34);\
}w$o= =92){A$y$A}w$o!=32&&o!=1 0)y!v$o);y$m();}void$n(x$o, x$p){\
aspri ntf(j+o,\"%i\",p);}x$mai n(x$o,char**p){char*q;w$c<2 )a+=c\
;b+=d ;x$r=b+2>f/2&&b<f/2+5;x$s=a+2==g&&b+2>h&&b<h+5;w$c<2){ w$a==\
e+2&& r||s){a-=c;b-=d;c=-c;}w$a<0||a>67){w$a<0){c=2;d=0;}a=3 4;b=6\
;}w$b<0||b>13){b-=d;d=-d;}w$f/2>10)f-=2;w$h>10)h--;w$o>1){w*p[1]==119&\
&h>0)h--;w*p[1]==101&&h<10)h++;}s=f/2-b+1;w$s<0)f++;w$s>0)f--;}z{b++;w\
$d<0)d++;w$b>=13){w$o>1&&*p[1]==119)d=-4;b=13;}w$f/2<15-i[c-2])f+=2;z$\
e--;w$h<15-i[c-1])h++;z$g--;w$e+3<=0){c++;w$c<7){e=g;f=h*2;g=70;h=15-i\
[c-1];}z{e=5;g=62;c=1;d=1;}}w$a+2==e&&r||s){c=2;e=5;f=28;g=62;h=12;}}n\
\(1,a);n(3,b);n(5,c);n(7,d);n(9,e);n(11,f);n(13,g);n(15,h);for(s=0;s<"\
,29",";s++){w$s)v$32);q=j[s];r=1;for(char*t=q;*t;t++)w*t==","36",")v$32);z$w*t==","39",")B$z$w*t!=32&&*t!=10){r=0;v*t);w*t==123||*t==125||*t==59)v$32);}w$r){m();A$B$A$B$for(o=0;o<15;o++){for(x$u=0;u<70;u++)w$k>=","29","||u>=a&&o>=b&&u-a<3&&o-b<2||u>=e&&o>=f/2&&u-e<3&&o-f/2<5||u>=g&&o>=h&&u-g<3&&o-h<5)v$32);z$w$m())u++;w$l)A$B}w$l)A$B$for(;k<"\
,29",";)m();}}B}" } ; x k=0; x l=1; x m(){ l++; w l==1)y!v 44); w l==2)y!v 34);
char o=j[k][l-3]; w!o){ l=0; k++; y!v 34); } w o==34){ A y v 34); } w o==92){ A y A}
w o!=32&&o!=10)y!v o); y m(); } void n(x o,x p){ asprintf(j+o,"%i",p); }
x main(x o,char**p){ char*q; w c<2)a+=c; b+=d; x r=b+2>f/2&&b<f/2+5;
x s=a+2==g&&b+2>h&&b<h+5; w c<2){ w a==e+2&&r||s){ a-=c; b-=d; c=-c; }
w a<0||a>67){ w a<0){ c=2; d=0; } a=34; b=6; } w b<0||b>13){ b-=d; d=-d; }
w f/2>10)f-=2; w h>10)h--; w o>1){ w*p[1]==119&&h>0)h--; w*p[1]==101&&h<10)h++; }
s=f/2-b+1; w s<0)f++; w s>0)f--; } z{ b++; w d<0)d++; w b>=13){ w o>1&&*p[1]==119)d=-4;
b=13; } w f/2<15-i[c-2])f+=2; z e--; w h<15-i[c-1])h++; z g--; w e+3<=0){ c++;
w c<7){ e=g; f=h*2; g=70; h=15-i[c-1]; } z{ e=5; g=62; c=1; d=1; } }
w a+2==e&&r||s){ c=2; e=5; f=28; g=62; h=12; } } n(1,a); n(3,b); n(5,c);
n(7,d); n(9,e); n(11,f); n(13,g); n(15,h); for(s=0; s< 29 ; s++){ w s)v 32);
q=j[s]; r=1; for(char*t=q; *t; t++)w*t== 36 )v 32); z w*t== 39 )B
z w*t!=32&&*t!=10){ r=0; v*t); w*t==123||*t==125||*t==59)v 32); }
w r){ m(); A B A B for(o=0; o<15; o++){ for(x u=0; u<70; u++)w k>= 29
||u>=a&&o>=b&&u-a<3&&o-b<2||u>=e&&o>=f/2&&u-e<3&&o-f/2<5||u>=g&&o>=h&&u-g<3&&o-h<5)v 32);
z w m())u++; w l)A B} w l)A B for(; k< 29 ; )m(); } } B}

At least, that's the rabbit hole I fell into while working on my IOCCC entry above, which is a version of pong that outputs a modified copy of its source code to generate the next frame of the game, rendering the current frame inside that same source code. It can be played by continuously compiling and running the output of the previous program, passing args to control your player.

This led me to writing Insert, a programming language to do just that (because, frankly, I'm not sure I have what it takes to write it all by hand). Its purpose is to produce C programs that can modify and output their own code, and which are optimized to be as small as possible (in number of characters). Click here for the original source code used to create the monstrous incantation of C above.

Why bother?

Of course, something like this isn't particularly useful, but that's never been a good reason not to do it! On the contrary, I've found a lot of value in indulging in silly programs like this, and there are so many fascinating things that have to be done to make it all work.

At a high level, you have to finish most of the compilation process to get a nearly complete piece of C code, then inject that code into itself so it can be accessed at runtime. There are a few tricks needed to sidestep some of the chicken-and-egg problems that arise from quines, which makes the whole process very interesting to dive into.

For example, the nearly complete C code might look like:

string thisCode = "INJECT HERE";
int main() { /* ... */ }

Then, after injecting into itself, it looks like:

string thisCode = "string thisCode = \"INJECT HERE\";\nint main() { /* ... */ }";
int main() { /* ... */ }

Of course, if you just print out the value of thisCode, you'll get the nearly complete version of code instead of the actual version that you ran. So, at runtime, INJECT HERE must first be replaced with the value of thisCode, completing the quine.

Brain teasers

There are a bunch of other brain teasers, such as how the program's behavior must depend on what its compiled output looks like. For example, at the program in the top, spaces are replaced by $ to free them up for formatting, but the reason dollar sign in particular is used is just because it doesn't appear in the compiled output.

Instead of somehow modifying the program based on future knowledge, you can very carefully inject some data derived from the nearly complete C code back into it, being mindful of how this affects program behavior (in this case, by injecting it as a character code and not a literal).

Dive deeper

So, if you're curious about self-modifying quines or strange (and exciting!) compiler optimizations, I invite you to read through the writeup and tinker with the language and compiler. I've written about the language features and other design considerations that let the compiler automate a lot of the work to generate these quines, and am more than happy to answer any questions or to go into more detail!

• IOCCC writeup
• Compiler (written in Rust)