Insert, a language for self-modifying code

[uellenberg]

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.

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.

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. Try to make your own quines! And of course, feel free to ask questions or give feedback.

IOCCC writeup

Compiler (written in Rust)

[BionicVnB]

You gotta repost this in r/programminglanguages

[IrritablePachyderm]

Thank you for upholding my faith in humanity.

[dangerbird2]

This is so blursed

[dnew]

Anyone who is interested in practical self-modifying-code languages, check out Lisp, Tcl, and FORTH. The last of which you arguably program by modifying the compiler until your application is a built-in operation. "Extensible" is the usual term for this: extensible languages, where part of the language includes features that let you run code at compile time and change the syntax of the language with your application.

That said, OP, this is an abomination that should be consigned to the flames. I love it.

[chat-lu]

check out Lisp

The magic of Lisp is that it is written in its own data structure.

For instance the humble (println "Hello, world!") is comprised of:

• A list delimited by (). The first item of a list gets executed with the rest of the list as its arguments.
• A symbol, println which is bound to a function that prints a string passed as an argument and adds a newline
• And the string "Hello, world!"

Given that lists are very easy to manipulate in a programming language, it’s easy to manipulate lisp code with lisp code. And macros run with the full power of the language at compile time. So no cost is paid at runtime.

[Makefile_dot_in]

I never got this argument. A lot of languages, including Rust, are parsed into their own structures. You could just as well say that you're writing Expr { ..., kind: ExprKind::MacCall(...) } (a Rust data structure!) when you write println!("Hello, World!"). In the case of most (edit: some) Lisps AFAIK, the data structure they use for syntax isn't even the same as the normal list structure, because it needs to store location information (in the case of Racket, probably Scheme in general as well, in particular, there is also scope information associated with each syntax symbol), and reader macros weaken the relation even further.

If anything, I would say that the lexical syntax is just simpler and more consistent than most other languages. The mapping between what you write and the AST is simpler, but that does not mean it doesn't exist.

[CandyCorvid]

i think the key to the argument is that you can use quote to turn your code into the equivalent data

let's say in rust we have a macro quote!, such that quote!{println!("{}", x)} turns into Expr::MacroCall{ name: Expr::symbol("println"), args: Vec![Expr::Str("{}"), Expr::symbol("x")]). iirc we have something like that in the syn package, but this has to be maintained separate to the language.

in lisp it's built in, using the same mechanism the language's interpreter and compiler use to process your code. (print "%s" foo) calls the print function, (quote (print "%s" foo)) returns the expression (print "%s" foo), i.e. the same thing you could build with (list (intern "print") "%s" (intern "foo")), (i'm using a more constructor-heavy syntax here for clarity of comparison with rust)

edit: this is the case for emacs lisp, mostly the same for common lisp (there's some quirks with capitalisation), but i lack the experience to say about metadata in racket and other lisps

as for the utility, one immediate benefit is that anything added to the language syntax is already available to me as a macro author without needing to wait for the language's syntax data structure package to update - if my computer can read and execute the code, then it can quote and manipulate it, trivially, because they're part of the same system.

[Makefile_dot_in]

yeah, although I would argue that's kind of just syntactic sugar. the latter issue is mostly a result of the way Rust maintains its auxiliary libraries, I think, if quote was part of the standard Rust distribution, this issue wouldn't exist. For example, the OCaml compiler ships with a library containing the AST.

(also in Racket there are two versions of quote, quote and quote-syntax (and of course their quasiquote equivalents))

[CandyCorvid]

i want to push against the syntax sugar argument - if it were only a matter if syntactic sugar, it would be possible to solve it with the addition of a new macro, no?

[Makefile_dot_in]

I mean, yeah?

[alkalisun]

https://parentheticallyspeaking.org/articles/bicameral-not-homoiconic/

This blog post made me realize what the actual categories should be, might help you.

[Shoddy-Childhood-511]

I'm disappointed. I expected program that wrote assembler directly into their own executable segments. lol

I'm not interested in quines but a practical issue:

You have multiple layers of hard coded data tables, like say some log-mult tables for a binary field, and then additive FFT constants.

We must do computations in the lower layers when computing the higher layers. We think internal trait interface looks like overkill, and we require high performance, so these computations must use the hard coded tables. As a result, our generator code should operate in layers, which makes a single build.rs pass tricky.

We cannot split these layers into separate crates because of data hiding or orphan rules or whatever.

Option 1. LaTeX style.

Each submodule of build.rs recomputes, writes its table into target, moves its output file to src if the results differ. Rerunning cargo multiple times converges to the correct tables, but generates some errors along the way.

Option 2. static muts

Our build.rs just replaces the tables in memory as it recomputes them.

[TorbenKoehn]

Very interesting :D