Metacompilation

post by Donald Hobson (donald-hobson) · 2025-02-24T22:58:00.085Z · LW · GW · 0 comments

Contents

  The baisc idea
  Self reference and infinite regress
  Defining our programming language.
  Metacompiling our toy language
  Proof theory notes
  What's the point
None
No comments

A post that is going to be part of my sequence on rethinking programming languages.

The baisc idea

A compiler is a piece of machine code $C$, that takes as input a text string describing a program $p$ and returns the compiled machine code $C\left(p\right)$

Let $Opt$ be a function that takes in a machine code program and returns another potentially faster or smaller program. 

A metacompliler has the formula $C\left(p\right)=Opt("C(p).run()")$

To understand how this works, first let's look at a less self referential case. Let $C_r$ be a regular compiler. $C_1\left(p\right)=Opt("C_r(p).run()")$  

$p$ is just a string. Maybe it's "print(1+2)"

$"C_r\left(p\right).run\left(\right)"$ is a machine code program. This program, if run, would first compile $p$ into machine code, and then would run that machine code. Therefore it is a machine code program that does the same thing as $p$. It has a fairly significant size for even a small program, as it contains a complete copy of the compiler. 

What does $Opt("C_r(p).run()")$ do? It optimizes that machine code. The first thing it can do is cut out big chunks of the compiler. At least in simple cases. If the code is running arbitrary eval statements, all the compiler might be needed. In the case of this simple program, the parts of the compiler that handle floats, loops etc are just not used. If the optimizer is good, it could simplify the code all the way down to $"\left[MACHINECODEOUTPUT3\right]"$. Some programming languages (see zig) already run code at compile time. The difference between compile and run time is just in what variables you currently know the value of, and the relative cost of compute.

For code with a finite runtime that just runs by itself, not interacting with the outside world, it can all, in principle be simplified down to a single print statement. In practice computer programs interact with the "outside world" in all sorts of ways. In some contexts, writes to disk or sending data to a GPU might be considered interactions with an external world. But for simplicity, assume the only form of interaction is input() and print()

Self reference and infinite regress

So that's what a metacompiler does. But does it actually do anything. The most naive metacompiler implimentation has  $Opt\left(x\right)=x$.  When we call $C\left(p\right)$ we get the program$"C\left(p\right).run\left(\right)"$. And when we proceed to run that program, that program first calls $C\left(p\right)$ to generate the machine code $"C\left(p\right).run\left(\right)"$ and then runs that machine code. This leads to an infinite regress. We haven't actually used $p$ anywhere. What we essentially have is just.

def get_pi():
	return get_pi()

A program that is clearly an infinite loop, with no actual relation to pi.

So we need the optimization step of the metacompiler to be doing something non-trivial to make the code halt in a finite time at all. 

Defining our programming language.

Lets define a small toy programming language, so we can talk about how to compile it.

We will give our programming language one data type, arbitrary size integers. 

We will allow definitions, inputs, calculations and loops.

a=1
b=input()
a=3
c=a+b
d=b-c
a=c*d
while_nonzero(d){
 d=d-a
 b=b*d
}
print(b)

This example program shows all the features of this programming language. It is rather minimal. 

Metacompiling our toy language

The only free parameter in the metacompiler (as above) is in the choice of $Opt$

For clarity, machine code instructions will look the same as programming language instructions, except the machine code will be in BOLD

The program consists of a number of definitions,  (of the format [name]=[number], looking like $\text{a=1}$ ) followed by the first non-definition statement. If the same name is used multiple times, only the last definition is needed. Ie the code $\text{a=1;b=2;a=3}$ can be optimized to $\text{b=2;a=3}$

Suppose the optimizer takes in $"C\left(p\right).run\left(\right)"$ code where the first non-definition in $p$ happens to be a calculation. For example. $"C{(}^{\prime }\text{a=1;b=2;k=a+b;}..stuff.{.}^{\prime }).run()"$ this can get optimized into $"C{(}^{\prime }\text{a=1;b=2;k=3;}..stuff.{.}^{\prime }).run()"$

Now suppose the first non-definition in $p$ is an $\text{input()}$.  For example. $"C{(}^{\prime }\text{a=1;b=input();}..stuff.{.}^{\prime }).run()"$ This can be converted into. 

$"\text{b=input();}C{(}^{\prime }\text{a=1;b=\%s;}..stuff.{.}^{\prime }\text{.string\_format(b)}).run()"$

The way to think about this is that, if $C$ were a normal compiler, the $Opt$ function would convert a machine code program containing $C$ into another machine code program that still contains $C$ but that makes $C$ do slightly less work. 

The rest is much the same. 

$"C{(}^{\prime }\text{a=1;print(a);}..stuff.{.}^{\prime }).run()"$ turns into $"\text{print(1);}C{(}^{\prime }\text{a=1;}..stuff.{.}^{\prime }).run()"$

And $"C{(}^{\prime }\text{a=1;while\_nonzero(a){}..stuff..\text{}}..morestuff.{.}^{\prime }).run()"$ turns into 

$"C{(}^{\prime }\text{a=1;}..stuff..\text{while\_nonzero(a){}..stuff..\text{}}..morestuff.{.}^{\prime }).run()"$ while the similar $"C{(}^{\prime }\text{a=0;while\_nonzero(a){}..stuff..\text{}}..morestuff.{.}^{\prime }).run()"$ can simplify down to $"C{(}^{\prime }\text{a=0;}..morestuff.{.}^{\prime }).run()"$

This gives a functioning toy example of a metacompiler. The above simplification rules are used in the definition of $Opt$, which is in turn used in the definition of $C$. 

This produces code that, while excessively self referential, runs and produces output in a finite time, at least assuming the output of a regular compiler would run in finite time on the program.  

Note that $Opt$ only does 1 simplification step, and is only run once at compile time. 

Proof theory notes

Suppose we insisted that, before $Opt$ is allowed to simplify a piece of machine code, it must first prove that it's simplification won't change the result. This can be proved, by lob's theorem. However it isn't sufficient to make the metacompiler actually valid. Lob's theorem just says that ZFC approves of infinite buck passing. At some point we need to actually understand our programming language. 

If however we make $Opt$ prove that $X$ is equivalent to $"C_r\left(p\right).run\left(\right)"$ before $Opt("C(p).run()")$ is allowed to output $X$. Then that is sufficient. Your directly proving that your meta-compiler is doing the same thing as a regular compiler, which gives you a ground truth about the meaning of the programming language.

What's the point

While the example meta-compiler given above isn't particularly fast, the toy example shows that metacompilers can exist. And the space of meta-compilers seems like it should contain all sorts of interesting optimizations. 

For example. I was doing some programming involving numerically integrating systems of Stochastic Differential Equations (SDE's). Basically, I choose various settings and then run a tight loop involving those settings. And ideally I would like the speed of special purpose compiled code within the tight loop, without having the overhead of a full compilation from source every time I change a setting. 

So, what I would ideally want is a program that contains precompiled snippets of code. Once the particular values of the settings are known, a highly optimized machine code program could be put together by little more than pasting together the relevant blocks of machine code to make a complete machine code program. 

And I'm wanting a way to make the programming language do this, or other clever things like this, automagically. 

Another clever thing. Suppose your program contains $\text{eval}$ of arbitrary user generated strings. But you know this is only a small fraction of runtime. And the user isn't allowed to use various language features. You might want to make a cut down minified version of the full language compiler, something with the unused features cut out, and some of the optimization tricks removed. 

The hope is to totally blur the line between compile time and runtime, with code that can rewrite itself on the fly in all sorts of clever and highly performant ways. 

0 comments

Comments sorted by top scores.