Metaprogramming with AI

Greg Surma

Jun 4, 2019·5 min read

In today’s article, we are going to learn how to write programs that write programs. The notion of programs that can generate other programs is called metaprogramming and by the end of this article, you will be able to create your own code-generating system.

Take a look at the following example of a self-generated program that prints ‘HI’ to the console.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+.

Brainf*ck

If you are confused by the above code, don’t worry - you are not alone. It’s written in an esoteric, though Turing complete programming language called Brainf*ck which is notorious for i’s unreadability. However, while being extra hard to understand for humans, it’s very simple to understand for computers.

It has only 8 instructions

“>” Increment the pointer.
“<” Decrement the pointer.
“+” Increment the byte at the pointer.
“-” Decrement the byte at the pointer.
“.” Output the byte at the pointer.
“[“ Jump forward past the matching ] if the byte at the pointer is zero.
“]”] Jump backward to the matching [ unless the byte at the pointer is zero.
“,” Input a byte and store it in the byte at the pointer.

so it’s relatively easy to write an interpreter for it. If you are curious, take a look at the Python interpreter I wrote for this project.

But why do we need this weird language in the first place?

Let’s define our project’s problem first.

We are striving to generate a program that does something simple, like for example printing some text on a screen.

Okay, but what is a ‘program’?

Without going too much into the technical details, we can define a program as a collection of instructions that are being executed by a computer.

With that being said, our goal is to find this specific collection of instructions that after being executed by a computer, will output a specific text on a screen.

We just defined our problem as a search one and if you read my previous articles that dealt with it like for example

or

you already know that in order to find a correct solution to the search problem in a reasonable amount of time, we should strive to limit the search space.

Brainf*ck with it’s only 8 possible instructions seems like a perfect fit for this task!

Take a look at the following example

[->+]+.-><>+

This is a syntactically correct Brain*ck program but unfortunately for us, it does nothing. Our goal would be to find a collection of instructions that actually prints a specific text on a screen.

How are going to find such a solution?

Genetic Evolution (GE)

In order to find a desired combination of instructions, we are going to use an evolutionary algorithm. If you are not familiar with Genetic Algorithms, I recommend you to check my previous articles on this topic like

or

GE Metaprogramming

Finally, with a well-designed problem and an idea of how to solve it, let’s implement it!

I recommend you to open the Meta Intelligence project that you can find on GitHub and follow along.

Our goal is to generate a Brainf*ck program that outputs a given target string. Example usage for a target string of ‘HI’:

python3 genetic_evolution_meta_programmer.py ‘HI’

1. We are going to start with a population of random chromosomes where every chromosome will be a brainfuck program represented as a string of random instructions. Example chromosome: [->+]+.-><>+. Keep in mind that the vast majority of randomly generated programs will be syntactically incorrect so we need to validate them with the interpreter before adding to the population.
2. Then we are going to proceed to the selection phase where we are going to pick top-performing programs. Programs are evaluated with a fitness function that calculates a score for every character with the following function: fitness_score += ASCII_CHARS_COUNT-abs(input_score-target_score)which is basically calculating the distance from the given character to the desired one on the ASCII table. The closer we are to the target character. The bigger the score, the closer we are to our target with ASCII_CHARS_COUNT as a max per character. Maximum fitness score per chromosome is calculated as len(self.target)*ASCII_CHARS_COUNT.
3. Next, we are going to pair chromosomes with roulette selection and perform a crossover.
4. Finally, we are going to perform mutation. Some programs after mutation are invalid so we are going to replace them with the random valid ones to keep the population constant in size.
5. We are going to repeat steps 2–4 until we find the target string.

You can check the full code here.

Results

With the following hyperparameters:

POPULATION = 100
MUTATION_RATE = 0.115
MAX_MUTATION_ATTEMPTS = 500
SELECTION_RATE = 0.9
PROGRAM_LENGTH_LOWER_BOUND = 10
PROGRAM_LENGTH_UPPER_BOUND = 100

I was able to achieve the following results:

FOUND SOLUTION: +++++++++++++++++++++++++++++++++. for: '!' in: 5 minutes

FOUND SOLUTION: ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++.+. for: ‘HI’ in: 27 minutes

FOUND SOLUTION: +++++-+++[>+++++++<-]>-+.+.+. for: ‘123’ in: 20 minutes

What’s Next?

In the Meta Intelligence project we’ve showed that Genetic Evolution can be used for a very simple code generation. I encourage you to play with the hyperparameters and GE settings to achieve even better results!

While GE approach appeared to be successful, we don’t have to stop there. In Part 2 of this project, we are going to use Reinforcement Learning methods to find out if we can improve our metaprogramming system, stay tuned!

Don’t forget to check the project’s GitHub page.

Questions? Comments? Feel free to leave your feedback in the comments section or contact me directly at https://gsurma.github.io.

And don’t forget to 👏 if you enjoyed this article 🙂.