arXiv:1709.05703v1 [] 17 Sep 2017

AI Programmer: Autonomously Creating
Software Programs Using Genetic Algorithms
Kory Becker

Justin Gottschlich

kbecker@primaryobjects.com
Bloomberg LP

justin.gottschlich@intel.com
Intel Labs

Abstract

and, of course, a plethora of tools aimed at assisting programmers in nearly every way [12, 13, 28].
Yet, simultaneous advances in hardware innovation have
occurred with similar frequency, such as increasingly performant general purpose multi-core CPUs with advanced
hardware extensions [22, 41], low power system-on-chip
(SoC) edge compute devices [17], high-performance pluggable coprocessors with near supercomputing performance
of yesteryear [14], wide data-parallel graphics processing
units (GPUs) [26], and application specific integrated circuits (ASICs) for deep neural networks and computer vision [4, 37], to name a few.
While such hardware advances continue to broaden and
deepen the space of what is computationally tractable, they
have the fracturing side-effect of complicating and exacerbating the tension between the ease of developing software and the ability for humans to write maximally efficient
code. In this paper we explore an alternative approach to traditional human-driven software development; one that autonomously creates software programs using genetic algorithms (GAs) requiring only minimal human guidance.

In this paper, we present the first-of-its-kind machine learning (ML) system, called AI Programmer, that can automatically generate full software programs requiring only minimal human guidance. At its core, AI Programmer uses genetic algorithms (GA) coupled with a tightly constrained
programming language that minimizes the overhead of its
ML search space. Part of AI Programmer’s novelty stems
from (i) its unique system design, including an embedded,
hand-crafted interpreter for efficiency and security and (ii)
its augmentation of GAs to include instruction-gene randomization bindings and programming language-specific
genome construction and elimination techniques. We provide a detailed examination of AI Programmer’s system
design, several examples detailing how the system works,
and experimental data demonstrating its software generation
capabilities and performance using only mainstream CPUs.
Keywords Genetic algorithm, program synthesis, genetic
programming, evolutionary computation, artificial intelligence, machine learning, programming languages, code generation and optimization

1.

Introduction

1.1

Since the invention of the computer, having the ability to correctly and efficiently develop software programs has been
a principle challenge [6]. To help address this, countless
breakthroughs have been made in the field of software development. Some of these include safety and flexibility advances in static, dynamic, and gradual type systems [5, 34];
simplification, safety, and robustness advances using automatic memory management and garbage collection systems [7, 15]; generality and specificity progress in both
general-purpose and domain specific languages [33, 38];

The Evolution of Programming Languages

Over the last several decades, programming languages (PLs)
have followed a steady path of providing higher-level programming abstractions, aimed at reducing the challenge of
human-driven software development [2]. To this end, PLs, in
general, have proliferated toward a design goal of simplifying human use. Although this trend is natural in an era where
humans perform the majority of software development, as
we will show, it is suboptimal in an environment where programming is performed predominantly by machines.
The ability for computers to automatically create their
own software programs has been a long-standing goal of artificial intelligence [31]. By largely removing humans from
the time-intensive and error-prone process of software development and replacing them with artificial intelligence, computer software has the potential to be generated in a more
streamlined, correct, and optimized fashion [8, 20].
This paper makes the following technical contributions:

[Copyright notice will appear here once ’preprint’ option is removed.]

1

2017/9/19

1. We present AI Programmer the first-of-its-kind software
generation framework, which constructs programs using genetic algorithms with novel enhancements coupled
with a minimalistic programming language.

lated according to how well the program can solve a given
task. This is performed with a sufficiently large population
size. Those that have the best fitness are mated together to
produce offspring.
Each generation of programs receive extra diversity
from evolutionary techniques including roulette selection,
crossover, and mutation [24]. The process is repeated at
each epoch with each child generation hopefully producing more favorable results than its parents’ generation until
a target solution is found. Through this process, applying
GAs to computer programming automation enacts a survival
of the fittest model for computer program generation [23]. A
deeper examination of these GA principles are provided in
Section 3.

2. We present several critical observations, including an embedded interpreter and simulator solution, for security
and optimization of ML-generated software.
3. We provide empirical results demonstrating the efficacy
and efficiency of AI Programmer across several of its
fully generated software programs on commodity hardware.

2.

Background

In this section we provide a brief synopsis of the challenges
in using traditional programming languages for machinebased program generation. We also provide a brief introduction into genetic algorithms, the ML technique used by AI
Programmer.
2.1

3.

In this section we provide a high-level overview of the AI
Programmer software architecture. The AI Programmer’s
system design is shown in Figure 1.

Programming Language Density

3.1

Most of today’s programming languages were designed for
human use [32]. We refer to such languages as humanintended PLs (HIPLs). Although HIPLs are useful when humans perform the majority of programming and debugging,
their design is usually counter to what is needed and appropriate for ML-based PLs (MLPLs).
HIPLs often introduce unnecessary complexity and overhead for ML program generators due, in part, to the large
number of language identifiers they include. The greater the
number of legal language identifiers, the greater the ML
computational search space. Moreover, type systems compound the challenge of creating legal programs because variable type bindings are intentionally restrictive to protect
against human error, yet provide limited value for ML program generators [30]. For these reasons, we chose to couple AI Programmer with a non-traditional programming language that is both constrained (i.e., using only eight identifiers) and typeless. We discuss this in more detail in Section 3.
Some instructions within any PL may be potentially
harmful and, if used conjunction with an ML-based program
generator, may cause irreversible damage. AI Programmer
has specific measures in place to prevent the occurrence of
such events. We discuss them in more detail in Section 3.4.
2.2

The Design of AI Programmer

Programming Language Selection and Challenges

We chose a typeless programming language that contains
only eight instructions to drive AI Programmer’s software
generation [25]. We briefly discuss the advantages of this
approach and the modifications to the language that were
required to integrate it into a GA solution.
Table 1. AI Programmer Instruction Set and Gene Map
Instr

Gene Range

Operation

>
<
+
.
,
[
]

(0, 0.125]
(0.125, 0.25]
(0.25, 0.375]
(0.375, 0.5]
(0.5, 0.625]
(0.625, 0.75]
(0.75, 0.875]
(0.875, 1.0]

Increment the pointer
Decrement the pointer
Increment the byte at the pointer
Decrement the byte at the pointer
Output the byte at the pointer
Input a byte and store it at the ptr
Jump to matching ] if current 0
Jump back to matching [ unless 0

Turing Completeness. AI Programmer’s programming
language, listed in Table 1, is Turing complete. A Turing
complete programming language is theoretically capable of
completing any (single taped Turing machine) programming
task given an unlimited amount of time and memory [40].
In essence, a programming language with this characteristic
is capable of implementations of a vast number of programming problems. Likewise, programs generated with AI Programmer, are theoretically capable of expressing all tasks
that one might want to accomplished with computers.

Programming with Genetic Algorithms

A genetic algorithm (GA) is a type of artificial intelligence, modeled after biological evolution, that begins with
no knowledge of the subject, aside from an encoding of
genes that represent a set of instructions or actions [9]. In
the concept of GA-driven computer programming, a series
of programming instructions are selected at random to serve
as an initial chain of DNA. The complete genome is executed as a program, with the resulting fitness score calcu-

GA Engine and Uniform Gene Distributions. AI Programmer’s genetic algorithm engine represents each generated program’s instructions as an array of floating point
values, which, when considered as a unit, is its genome.
Each individual location within a given genome is called a
2

2017/9/19

Figure 1. The AI Programmer Software Architecture.
+-+-+>-<[++++>+++++<+<>++]>[-[---.--[[-.++++
[+++..].]]]]

gene. Each gene within a program’s genome corresponds to
a single instruction from Table 1.
AI Programmer binds a gene value range to each of its instructions across a continuous uniform distribution (or rectangular distribution) [3] (see Table 1), where each instruction’s gene range is equal in size to each of the others. This
was done so each instruction would have an equally random probability of being chosen at any location in a gene
sequence when randomization was needed. 1

Figure 2. A generated program that outputs “hello”.
space needs to be constrained. As AI Programmer is intended for general purpose developers, limiting the programming instruction set to eight instructions enables the engine
to execute in reasonable times on commodity hardware (see
Section 5).

Simplified Instruction Set. Each of AI Programmer’s instructions manipulate a memory “tape” of byte values, ranging from 0-255. The language works by applying increment
and decrement operations to the current memory cell, while
shifting the memory cell up and down the tape, as instructed
by the program. The values at the current memory pointer
can be input from the user or output to the terminal. Primitive looping instructions also exist (e.g., ‘[’ and ‘]’), offering
a complete instruction set for creating software. An example
program is shown in Figure 2.
The simplified instruction set reduces the search space
in which a target program code can be found. As computational devices improve in speed, larger problem spaces can
be searched. However, on less powerful devices, the search

3.2

Genomes and Generations

To generate a software program using genetic algorithms,
one must first create a genome. A genome is a set of genes
that are grouped together as a single unit. For AI Programmer, the genome is encoded as an array of floating point values, with fixed value ranges per unique instruction ranging
between 0 and 1, as shown in the Gene Range column of
Table 1.
Once a genome is created, it is converted to a corresponding program, executed, and the resulting program is assigned
a fitness score based on the program’s output. The closer a
generated program comes to solving the provided task, the
greater its fitness score and, the more likely it is to continue to the next evolutionary generation. At each generation
epoch, AI Programmer utilizes roulette selection, along with

1 We

did not examine the impact of weighted ranges for different programs,
but note that it may be of interest as future work.

3

2017/9/19

crossover and mutation, to create child programs that contain
slight random perturbations, and potentially better, genomes
than their parents for solving the target task.

diately removed from the pool of genomes. However, programs that succeed are carried forward to produce child programs.3

Constructing a Genome Figure 3 demonstrates an example of constructing a genome from an array of floating point
values. Each value range maps to a specific instruction in
the programming language. Initially, these values are random (see the Random Gene Sequencer in Figure 1), resulting in generated programs that either won’t function properly, throw errors, or simply fail 2 . However, one or two are
bound to run and execute, at a minimum, some number of
valid instructions. The more successful a program is at executing, the more likely it is to continue on and produce offspring with code that achieves more successful results.

Figure 5. Programs are weighted by fitness, with the most
successful used for child program generation.
3.3

The Fitness Test

To use GAs, a fitness test is needed to determine how well a
generated solution performs. In the context of AI Programmer, this can involve scoring the byte-level output of the
generated program, inspecting the generated program’s internal state, or even analysis of intermediate state changes
of the program throughout its execution. The score of the
fitness test is calculated by analyzing these characteristics,
and many others, and then comparing them against a userdefined target.
This concept is similar to test-driven development. When
all unit tests pass, a program may be considered to be functionally correct. Likewise, a fitness test for a GA can be considered as a set of unit tests. In the case of AI Programmer, a
fitness test typically contains a suite of tests for varying scenarios, which guide the genome selection, preserving only
programs that evaluate well on the test suite. Further details
about the construction of AI Programmer fitness tests are described in Section 4.

Figure 3. Decoding a genome as a program.
Crossover and Mutation To create offspring, a parent
genome contributes part of its genes to the child, a process
called crossover, as shown in Figure 4. In addition to inheriting programming instructions from its parent, each child
can also experience mutation, which is the process of adding
controlled, but random perturbation, to specific genes. This
results in modified behavior of the value of a particular gene,
resulting in a change to the resulting programming instruction, and thus, the overall program.

3.4

AI Programmer’s Sandboxed Interpreter

Once a program has been generated, it must be executed so
it can be evaluated against human created fitness tests. However, the execution of ML generated programs may include
potential security risks as well as performance degradations.
Because of this and the need for complex fitness tests (Section 3.3), we developed our own interpreter. This interpreter
is sandboxed within the AI Programmer system to provide
a secure, efficient, and GA-appropriate execution environment. We explain the challenges and benefits of this system
in the following subsections.

Figure 4. An example of crossover and mutation. The child
genome inherits the first 5 instructions from its parent. One
instruction is mutated.
Crossover copies forward potentially beneficial parts of
the parent, while mutation offers differing behaviors of instruction combinations, which may or may not, end up making the child programs more successful.

3.4.1

Execution of Generated Programs in a
Controlled Environment

As generated programs are executed to evaluate their fitness,
the results can often be undesirable and potentially dangerous. Consider a program generated with I/O instructions, allowing for the modification of files on disk. A generated program could potentially overwrite critical system files, ren-

Survival of the Fittest Executable programs are ranked according to how well they have performed. As shown in Figure 5, a particular program that has failed is often imme2 Most

initial programs in the gene pool fail immediately upon being executed. Others may result in endless loops. It is due to these reasons that
exception handling and maximum iteration limits are imposed on the interpreter.

3 In

Figure 5, the bottom program is a valid running program that takes one
byte for input, increments it, and then displays it twice as output.

4

2017/9/19

4.

dering the entire machine inoperable. Likewise, a program
generated with instructions to support networking could inadvertently flood a computer network (e.g., denial of service attack [42]) or replicate itself across machines (e.g.,
worm [1]).
Normally, these types of behaviors are malicious, yet ML
software generators happen upon these situations in an attempt to satisfy fitness goals. By executing programs within
our own secure interpreter, which includes instruction-level
protection checks, AI Programmer can provide the additional security measures that are needed to prevent ML generated software from causing harmful behaviors. Non-ML
generating interpreters and compilers do not generally include these types of checks because management of such
issues are not usually within scope for HIPLs [39].
3.4.2

AI Programmer consists of a modular framework, designed
in C# .NET. It includes an engine for running genetic algorithms, an encoder and decoder for genomes, a sandboxed
interpreter for simulated program execution, and a compiler
to transform code into binary executables. While the initial
design of AI Programmer uses C#, it is important to note that
the principles employed by it are not bound to C#.
AI Programmer’s software framework for fitness test construction is extensible and was developed so users can devise a myriad of customized fitness suites, which eventually
guide the system’s GA generation and evolution of software
programs.
Specifying Requirements of a Program To generate a program, AI Programmer must be provided with the requirements for the desired input and output of the target program.
For example, if a program should prompt a user for a numerical input and then subsequently output a line of text,
this must be specified in the form of training data to AI Programmer. The following subsections detail the step-by-step
process of how a program is specified and generated with AI
Programmer.

Termination of Infinite Loops

Automatically generated software has the potential to create
infinite loops. This can occur from unsatisfied loop termination constraints or unexpected looping instructions. In our
experiments, this type of behavior often arises in early program generations due to the GA maximizing the goal fitness
score at the cost of program execution time. As a result, unterminated programs have the potential to halt the generation
process, resulting in a failure of further program evaluations.
In an attempt to mitigate this, one can add fitness constraints to prefer programs with fewer instruction counts
over larger ones. However, the generation of infinite loops,
especially in early generations of programs, remains a possibility. AI Programmer’s interpreter includes a customizable
maximum instruction count per execution. Programs that exceed the instruction count are terminated. A fitness penalty
can then be applied, reducing the likelihood of future generations of programs carrying forward the infinite loop constructs. With this addition, AI Programmer is guaranteed to
terminate all infinite loops.
3.4.3

Using AI Programmer

Creating Your First Program To begin, a user creates a
C# class within the AI Programmer project, inheriting from
the FitnessBase base class. This class includes all the necessary requirements for specifying a solution to be built by
AI Programmer, including fitness scoring functionality, program termination rules, and program generation capabilities.
Specifying a Target Fitness Score Next, the user indicates
a target fitness score which is specified in the constructor
of the class as shown in Figure 6. The score is typically
based upon characteristics of the desired program. For example, if the target program is intended to output a string,
such as “Hello World”, the fitness score might be the number of characters in the string (i.e., 11). However, since AI
Programmer generates programming code at the byte level,
the fitness score should account for incremental differences
in output characters. In this case, one should multiply each
target character in the output by 256, resulting in 2816 (e.g.,
11 * 256) and use that as the resulting target fitness score.

Simulation of Complex Instructions

Optimizing program execution is a principle concern for
ML program generators. This is because such systems may
generate and execute dozens to millions of programs before
one with a high enough fitness score is found. While simple
operations, such as add, load, store, jmp, may take a
single clock cycle to complete, more complex operations
can require many. Examples include disk I/O, networking,
and peripheral device access. These types of operations can
significantly increase program execution time, as they often
rely on accessing services or devices with increased latency.
AI Programmer can simulate the execution of these complex instructions. In doing so, the GA-based programs it generates can execute more efficiently, while still retaining the
ability to check the program’s fitness goals. Moreover, such
simulation protects the devices themselves from overuse by
the plethora of programs that may attempt to access them
during exploratory evolution of GA program generation.

public StringFitness(GA ga, int maxIterCount)
: base(ga, maxIterCount)
{
_targetStr = "Hello World";
_targetFit = _targetStr.Length * 256;
}

Figure 6. Example target fitness score for “Hello World.”
AI Programmer is designed to continue execution, generating incrementally better programs that satisfy the fitness
conditions, until the current fitness score reaches its target.
5

2017/9/19

Specifying Fitness Conditions Next, the user must specify the rules that are used to score each of the generated
programs (i.e., the fitness test). At each generation epoch,
AI Programmer will favor programs that have fitness scores
that are closer to the target fitness score. Therefore, careful crafting of the fitness conditions are required so fitness
scores accurately represent the desired goal of the program.
In the “Hello World” example, the user must specify that
the output of the program should match the target string. To
achieve this, one can add to the fitness score according to
how close each character in the generated output string is to
the target string. In particular, the fitness test can simply loop
over the characters in the string ”Hello World”, and compare
each one against the characters produced in the output of
the generated program, adding or subtracting accordingly,
as shown in Figure 7.

program, rather than the generation of a program that only
solves the exact training examples provided.
int val;
if (Int32.TryParse(_console.ToString(), out val)) {
Fit += 256 - Math.Abs(val -(input1 + input2));
}

Figure 8. Calculating the fitness of adding two numbers.
Programmatic Sequences of Action Because different
programs require different sequences of actions (e.g., requesting input, outputting a result, etc.), AI Programmer
provides users with a mechanism to specify the necessary
programmatic sequence of actions within the fitness method.
Programmatic sequences can be provided in the form of a
simple state machine within the fitness check method. When
the generated program executes a command to request input
from the user, a bonus score can be applied to the fitness if
it is executed at the correct time in the sequence of actions.
Likewise, when data is output, one can add or subtract from
the fitness score according to the time the action is executed.
It is important for users to account for programmatic sequence bonuses when they are generating the initial target
fitness. Doing so will ensure the generated solution will satisfy all required constraints, including sequences of events,
before returning a viable solution program.

for (int i = 0; i < _targetStr.Length; i++)
if (_console.Length > i)
Fit += 256-Math.Abs(_console[i]-_targetStr[i]);

Figure 7. Adding and subtracting the fitness score based
upon program output.
After assigning a fitness score to each generated program within the current pool, a check is made to determine
whether the target fitness score has been achieved by any of
the generated programs. If so, AI Programmer halts and returns the solution program. Otherwise, it continues with the
next generation of programs.

5.

Results

Using AI Programmer, we were able to generate numerous
complete software programs. A complete listing of these
programs, their associated program generation time, and the
total number of evolutionary generations used to build them
are shown in Table 2. It is important to note that the number of evolutionary generations is not equivalent to the total
computational time to generate a program. This is due, in
large part, to varying genome size and fitness function computation, which is unique to each program.
Even though genetic algorithms are embarrassingly parallel and AI Programmer utilizes task-level parallelism for
each generation’s genome construction and fitness test evaluation, we limited our experimental study to commodity hardware only. All experiments were run on an Intel Quad-Core
i7 CPU, 2.7GHz, containing 16GB ram with an x64-based
processor utilizing up to 4-threads for the parallelism described above. We constrained our experiments in this manner to demonstrate the efficacy of AI Programmer for realworld autonomous software development.
For the remainder of this section, we highlight the details
of some of the programs listed in Table 2 and discuss novel
aspects that emerged when generating them.

Specifying Conditions for Variable Output Previously, we
presented an example on how to train AI Programmer to find
an exact string. However, for more complex scenarios, such
as variable outputs or calculated values, a series of training
examples may be required. In such scenarios, training data
can be created to serve as an initial set of examples to base
the fitness score upon. Thereafter, AI Programmer can be
guided with an evolutionary goal to generalize from the
training data and provide correct results for new data.
As an example of variable output, consider the generation
of a program to output the summation of two numbers. The
target fitness score for this program would be the desired
output, which, in this case, would be one byte, multiplied by
the range of potential values (256). To construct the target
fitness score, we can simply multiply the target fitness for a
single result by the number of training examples. Therefore,
in this case, the target fitness is trainingCount * 256.
After specifying the target fitness score, we can implement the actual fitness check for adding two numbers by
looping over each training set combination (consisting of
two numbers), inputting those values to our program, and
checking the output for the correct sum. An example of this
is shown in Figure 8. By providing varying training input
values we can help foster the generalization of the solution

5.1

Greetings

“Hello World” is usually one of the first programs human
programmers create when they begin learning programming.
6

2017/9/19

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

Table 2. AI Programmer Results
Name

Duration (s)

Generations

hi
Hi!
hello
hello world
reddit
Keep Calm Keep Coding
I love all humans
hello {user}
Addition
Subtraction
Multiply x2
Multiply x3
XOR
Fibonacci
If/then conditionals
cats are evil
Bottles of Beer on the Wall
Reverse string
CSV parse
Extract in quotes
Extract in quotes 2
Trim left of quote
XML to JSON
Warning countdown

52
7,644
1,713
7,702
1,362
944
36,000
1,793
2,698
4,305
6,353
5,165
2,095
21,862
8,313
10,209
2,957
49
173
6,478
9,996
9,030
6,866
48

5,700
1,219,400
252,000
580,900
195,000
21,400
6,057,200
42,800
92,400
177,900
242,000
87,200
146,400
151,900
46,200
814,400
61,400
2,600
9,000
212,100
188,400
341,700
820,900
900

Figure 10. Generated program: “hello world”
mans,” which was successfully generated after 6,057,200
generations. It consists of the code shown in Figure 11. The
fitness method for this example includes a check on the output string length to ensure an exact matching output, without
extraneous text.
To ensure an exact output string, the fitness score includes
not just a check on the output characters, but also a check
on the length of the string. In this case, the target fitness
included an additional 10 points, of which a percentage of
this amount is added to the resulting fitness, depending on
how close the length of the output string matches the length
of the target. This forces the generation of a program that
outputs the exact target string, without extraneous output
instructions, as the generation process will not halt until the
target fitness is reached, of which, 10 points comprise having
the correct output length.
+[>+<+++]+>------------.+<+++++++++++++++++++
++++++++++++.>+++++++++++++++++++++++++++++++
+++.+++.+++++++.-----------------.--<.>--.+++
++++++++..---<.>-.+++++++++++++.--------.-----------.+++++++++++++.+++++.

Figure 11. Generated program: “I love all humans”

As such, we found it fitting to guide AI Programmer to learn
some basic greetings for its early programs. Rather than
starting with “Hello World”, we first had AI Programmer
create a more simplistic program that simply output “hi.” It
was successfully after 5,700 generations and the generated
code is shown in Figure 9.

// Assigning the target fitness.
_targetFitness = _targetString.Length * 256;
_targetFitness += 10;
...

+[+++++-+>++>++-++++++<<]>++.[+.]-.,-#>>]<]
// Calculating the fitness length bonus.
Fitness += 10 * ((_targetString.Length Math.Abs(_console.Length _targetString.Length)) /
_targetString.Length);

Figure 9. Generated program: “hi”
The generated program fulfilled its requirement to output
the target text, but interestingly included subsequent random
characters, which contained parsing errors, including nonmatching brackets. However, AI Programmer’s interpreter
computes results until the program fails. In this manner, the
syntax error (which is later on in the code, after a solution
is reached) does not negatively impact its fitness score, and
thus offers a working solution. In fact, the generated code
can be executed in almost any third-party interpreter as a
valid working program (provided, warnings are ignored).
Next, we guided AI Programmer to generate the famous
“hello world” output which was successfully constructed
after 580,900 generations and consists of the code shown in
Figure 10.

Figure 12. A percentage of 10 points is added to the fitness,
according to how exact the length of the output is to the
target.
5.2

Input-Output Computations

We next guided AI Programmer to generate programs that
perform computations based on user input. In such programs, the user provides some input and the computer program then generates the appropriate output.
Reversing a String AI Programmer was able to generate
the program to reverse any string after only 2,600 generations. The generated code is shown in Figure 13.

“I love all humans” As a humorous aside, we asked AI
Programmer to create the program to output “I love all hu7

2017/9/19

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

branching, successful program generation required more advanced techniques within the fitness function.
In particular, a check was needed to examine the interpreter’s memory register (i.e., current data pointer via shift
operations), where the distinct number of memory registers
being used by the program was counted, providing a bonus
to fitness to favor more memory register usage over less.
This aided in inspiring diversity amongst child programs.
Additionally, the instruction pointer used for each print command was recorded and weighed against the fitness score. A
penalty was applied for reuse of the same print command.
This helped to foster diversity and achieve a successful ifthen result.

Figure 13. Generated program for reversing a string.
When executed, the program prompts the user for input. The
user then types one character at a time until a value of “0” is
entered. A novelty of this program is that it is required to take
variable size input first before performing the majority of
its program logic. However, the program’s internal memory
state must manage the variable input, as the program must
read all input first to locate the final character entered, which
is the first character in the reversed string. The genetic algorithm was able to produce this logic automatically, based
upon the fitness method.

6.

Addition and Subtraction AI Programmer was able to
generate programs for addition after 92,400 generations
(Figure 14) and subtraction after 177,900 generations (Figure 15).

We noticed that the program generation time increased significantly as the length of the target output increased. Furthermore, the need to extend AI Programmer beyond the basic instruction set was deemed a necessity if we were to have
it produce programs with more interesting features, such as
file I/O and networking capabilities.
As such, we extended AI Programmer to use an extended
programming instruction set, which reduced code generation time and improved code compression due to an increased range of instruction specificity (i.e., fewer instructions to achieve the same result). However, a disadvantage
of utilizing the extended instruction set is that the generated
programs would be difficult to test in standard interpreters.
As the extended instruction set for AI Programmer deviated
from the traditional programming language, standard interpreters would no longer be able to run the produced code. In
our case, AI Programmer’s internally developed interpreter
was modified to support the extended instruction set, so this
was not a practical obstacle.

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

Figure 14. Generated program for performing addition.
,-->,-[-<->]<+.

Figure 15. Generated program for performing subtraction.
If-Then Conditionals with User Input Generating programs involving more complex programming logic, such as
the ability to perform if-then decisions and actions, requires
a more advanced type of fitness function. However, as described in Section 3.4, AI Programmer’s embedded interpreter provides significantly more access to program state
than just its output, which is essential for generating a large
variety of more complex programs.
For example, AI Programmer was able to produce a program which prompts the user for input (e.g., 1, 2 or 3) and
outputs text based on which value was entered, similar to selecting an option from a menu. By entering the value “1”,
the program would output “hi”. Entering “2”, resulted in the
program output of “z”. Entering “3”, resulted in the output
“bye”. The program was generated in 446,200 generations.
The produced code was notably larger than previously
generated programs, containing 650 instructions (although
not all instructions are needed). The larger code was required, as the conditional branches are contained within individual blocks of the code.
5.3

Optimizing Program Generation

6.1

Extended Instruction Set

Several extensions of the programming language used by AI
Programmer exist, which are suitable to decrease program
generation time. Specifically, the speed-enhancing extension
set, Extended Type III [10], offers several programming instructions that aid generation. These instructions include the
ability to immediately set the value of a particular cell to
a multiple of 16, also called “fast cell initializers”. This aids
in allowing a generated program to quickly reach displayable
ASCII range characters for output, thus, decreasing the number of individual increment programming instructions that
would normally be required.
In addition to key instructions taken from Extended Type
III, we added several new instructions to support calling
functions from within a program, allowing for increasingly
complex programs to be generated.

Complexity in Fitness Functions

As the complexity of the target program grows, so too does
the fitness function. After all, the fitness function needs to
guide the engine in determining how well a particular child
program matches the targeted solution. For conditionals and

Fibonacci Sequence With these extensions in place, AI
Programmer was able to generate a program to output the
8

2017/9/19

,>,$[!>--$<<a>>]4]+,,-[-<+>]<+.$@

putational complexity of generated programs. This approach
been found useful in other areas of genetic programming, including the simulation of artificial life, as described in Ling’s
work [21]. In a simulation library based on genetic algorithms and biological hierarchy, the system, called Ragaraja,
uses biological concepts to form an esoteric programming
language, consisting of a set of 3-character instructions. In
this manner, the system is able to simplify the genetic algorithm generation and mutation process by limiting the number of possible instruction combinations. Although applied
in a completely different domain, the affects of this approach
are similar to AI Programmer, specifically for optimizing the
generation time and limiting the complexity of generated solutions to a constrained set of instructions.

Figure 16. Generated program to output the Fibonacci sequence from two starting input values.
Fibonacci sequence up to 233 4 , which was was generated in
approximately six hours. The program prompts the user for
input of the two starting values in the sequence. It then outputs the next digits in the Fibonacci sequence. The generated
code for this, using the extended instruction set, is shown in
Figure 16.
Advancing Complexity The ability of the GA to generate a
program for solving the Fibonacci sequence was a profound
advancement. The solution program contains several distinct
programming tasks, including prompting the user for input
of two numbers at the beginning of execution, calculating
the addition of values, determining the correct mathematical
sequence, outputting the result, and looping to repeat the
process for each value in the sequence.
This combination of tasks, spreading across a range of
programming abilities, might typically be given to human
programmers in order to evaluate their programming proficiency. The capability of the GA to automatically generate
this type of program demonstrates the potential for future
expansion of the system.

7.

7.2

AI Programmer has similarities to a program synthesis technique called sketching in that each approach attempts to automatically generate software by using some human guidance. However, the similarities between the two approaches
ends there. On one hand, sketching is a program synthesis
technique where a programmer provides only a minimalistic
outline of an implementation and the compiler generates the
remaining code [35, 36]. On the other hand, AI Programmerrequires no partial implementation, but instead requires human developers to design fitness tests which guide the evolutionary algorithm for the entire program construction.
Another slightly related work is verified lifting [16]. Verified lifting aims to lift algorithms written in one language
and place a formally verified equivalent in another language.
The benefits of verified lifting are highly practical, especially
when considering the need for such systems as real software
systems often migrate from one programming language to
another. However, verified lifting and AI Programmer are
only loosely similar in that both systems perform automatic
code generation, but do not possess any other similarities in
their approaches.

Related Work

Genetic programming has previously been applied in some
restricted cases. A key limitation in their broader application has been in the computational density of the search
space involved in program generation, which exponentially
increases as programs grow in complexity [18]. AI Programmer provides to novel mitigation of this inefficiency by using
a minimalistic programming language, exploiting the natural parallelism of GAs, simulating complex instructions, and
embedding an optimized interpreter for fast execution and
fast-failure of defunct programs.
7.1

Different Approaches in Program Generation

7.3

Genetic Algorithms in Other Domains

Slow Acceptance of Genetic Algorithms

The potential capabilities of automated program generation
using machine learning techniques have been considered for
some time. Yet, these approaches have encountered obstacles inhibiting their practical application. Part of those obstacles were a lack of computational power and data movement throughout. Advances in these fields have had recent
breakthroughs leading to the democratization of machine
learning, especially in the area of deep learning, which requires complex neural networks and a large amount of training data [11].
Still, other challenges remain in automated programming,
as explained by O’Neil et al. [27], which describes the slow
growth of genetic programming, despite the successes that it
has achieved in various real-world domains. To the best of
our knowledge, AI Programmer is the first end-to-end GA

Somewhat related to our work, is the use of program synthesis driven by genetic programming in hardware-based
niche fields. Koza et al. used an automated process for creating analog circuits, involving genetically evolved designs
with evolutionary computation to produce circuit components that typically require human-level intelligence to construct [19]. In addition, they used human constructed fitness
methods to guide their circuit design. Although applied in
different domains, the high-level machine learning approach
of Koza et al.’s system is similar to AI Programmer.
One of the key components of our research is the usage
of a minimalistic programming language to limit the com4 255

is the max value for a byte, with the next Fibonacci sequence value
being 377.

9

2017/9/19

system to demonstrate rapid progress in non-trivial program
generation achieved entirely on commodity hardware.

8.

[3] Uniform distribution. URL https://en.wikipedia.org/
wiki/Uniform_distribution_(continuous).
[4] M. Abadi, P. Barham, J. Chen, Z. Chen, A. Davis, J. Dean,
M. Devin, S. Ghemawat, G. Irving, M. Isard, M. Kudlur,
J. Levenberg, R. Monga, S. Moore, D. G. Murray, B. Steiner,
P. A. Tucker, V. Vasudevan, P. Warden, M. Wicke, Y. Yu,
and X. Zhang. Tensorflow: A system for large-scale machine learning. CoRR, abs/1605.08695, 2016. URL http:
//arxiv.org/abs/1605.08695.

Conclusion and Future Work

Traditional human-based computer programming is approaching a dramatic shift. With increasingly complex software and hardware advances and the growing challenges
integrating the two, the craft of software development will
inevitably surpass the capabilities of humans. As that time
approaches, it will be necessary to have some form of automatic software generation to assist humans in software development beyond what exists today (e.g., compilers, higherlevel programming languages, etc.).
The results presented in this paper, provide early notions
about the power that machine learning techniques, specifically genetic algorithms, may offer a partial solution for
automatic program generation. We showed that fully functional programs can indeed be automatically generated, provided they are supplied with some human guidance in the
way of input parameters and training data. While the initial
set of programs generated by AI Programmer are similar in
complexity to that a novice human programmer, the range of
generated programs need not restricted to traditional means
such as human time or human intellect. Instead, they are simply a function of fitness test complexity and computational
resources.
In addition to correctness, efficient implementation of fitness methods are imperative to the practical application of
AI Programmer. This is because each generated program is
checked against the fitness method every time a new program is evaluated. An important open area of future work is
the deep examination of how to implement fitness methods
as efficiently as possible while still retaining a high degree
of correctness. One possible solution is to build superoptimizers specifically for fitness test optimizations [29].
Another important open area in ML-based program generation is the need for specifically crafted programming languages that have strong alignment with the constraints of
ML computation. The current programming languages we
use today, for humans, are ill-suited for ML-based program
generation. The approach we use for typical program language creation needs to be abandoned and rethought when
considering a future of ML-driven program generation. Only
once this is done, can we begin to envision a new future of
computer software development, driven by artificial intelligence based systems, with human creativity and design guiding the way.

[5] L. Cardelli and P. Wegner. On understanding types, data
abstraction, and polymorphism. ACM Comput. Surv., 17(4):
471–523, Dec. 1985. ISSN 0360-0300. URL http://doi.
acm.org/10.1145/6041.6042.
[6] T. H. Cormen, C. Stein, R. L. Rivest, and C. E. Leiserson.
Introduction to Algorithms. McGraw-Hill Higher Education,
2nd edition, 2001. ISBN 0070131511.
[7] E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and
E. F. M. Steffens. On-the-fly garbage collection: An exercise
in cooperation. Commun. ACM, 21(11):966–975, Nov. 1978.
ISSN 0001-0782. URL http://doi.acm.org/10.1145/
359642.359655.
[8] E. D. Dolan and J. J. Moré. Benchmarking optimization software with performance profiles. Mathematical programming,
91(2):201–213, 2002.
[9] P. Domingos. The Master Algorithm: How the Quest for the
Ultimate Learning Machine Will Remake Our World. 2015.
[10] Esolangs.org. Extended type iii. URL https://goo.gl/
9bS2gF.
[11] I. Goodfellow, Y. Bengio, and A. Courville. Deep Learning.
MIT Press, 2016. URL http://www.deeplearningbook.
org. Book in preparation for MIT Press.
[12] J. E. Gottschlich, M. P. Herlihy, G. A. Pokam, and J. G.
Siek. Visualizing transactional memory. In Proceedings of
the 21st International Conference on Parallel Architectures
and Compilation Techniques, PACT ’12, pages 159–170, New
York, NY, USA, 2012. ACM. ISBN 978-1-4503-1182-3. URL
http://doi.acm.org/10.1145/2370816.2370842.
[13] S. L. Graham, P. B. Kessler, and M. K. Mckusick. Gprof: A
call graph execution profiler. SIGPLAN Not., 17(6):120–126,
June 1982. ISSN 0362-1340. URL http://doi.acm.org/
10.1145/872726.806987.
[14] J. Jeffers and J. Reinders. Intel Xeon Phi Coprocessor High
Performance Programming. Morgan Kaufmann Publishers
Inc., San Francisco, CA, USA, 1st edition, 2013. ISBN
9780124104143, 9780124104945.
[15] R. Jones and R. Lins. Garbage Collection: Algorithms for
Automatic Dynamic Memory Management. John Wiley &
Sons, Inc., New York, NY, USA, 1996. ISBN 0-471-94148-4.
[16] S. Kamil, A. Cheung, S. Itzhaky, and A. Solar-Lezama. Verified lifting of stencil computations. In Proceedings of the
37th ACM SIGPLAN Conference on Programming Language
Design and Implementation, PLDI ’16, pages 711–726, New
York, NY, USA, 2016. ACM. ISBN 978-1-4503-4261-2. doi:
10.1145/2908080.2908117. URL http://doi.acm.org/
10.1145/2908080.2908117.

References
[1] Computer worm.
URL https://en.wikipedia.org/
wiki/Computer_worm.
[2] The 2017 top programming languages.
URL
https://spectrum.ieee.org/computing/software/
the-2017-top-programming-languages.

10

2017/9/19

ISBN 1-55860-442-1.

[17] M. Keating, D. Flynn, R. Aitken, A. Gibbons, and K. Shi. Low
Power Methodology Manual: For System-on-Chip Design.
Springer Publishing Company, Incorporated, 2007. ISBN
0387718184, 9780387718187.

[33] M. L. Scott. Programming Language Pragmatics, Third Edition. Morgan Kaufmann Publishers Inc., San Francisco, CA,
USA, 3rd edition, 2009. ISBN 0123745144, 9780123745149.

[18] J. R. Koza. Human-competitive results produced by genetic
programming. Genetic Programming and Evolvable Machines, 11(3-4):251–284, 2010.

[34] J. G. Siek and W. Taha. Gradual typing for functional languages. In IN SCHEME AND FUNCTIONAL PROGRAMMING WORKSHOP, pages 81–92, 2006.

[19] J. R. Koza, F. H. Bennett, D. Andre, M. A. Keane, and F. Dunlap. Automated synthesis of analog electrical circuits by
means of genetic programming. IEEE Transactions on evolutionary computation, 1(2):109–128, 1997.

[35] A. Solar-Lezama, R. Rabbah, R. Bodı́k, and K. Ebcioğlu. Programming by sketching for bit-streaming programs. SIGPLAN Not., 40(6):281–294, June 2005. ISSN 0362-1340. doi:
10.1145/1064978.1065045. URL http://doi.acm.org/
10.1145/1064978.1065045.

[20] L. Lamport. Proving the correctness of multiprocess programs. IEEE transactions on software engineering, (2):125–
143, 1977.

[36] A. Solar-Lezama, L. Tancau, R. Bodik, S. Seshia, and
V. Saraswat. Combinatorial sketching for finite programs.
SIGOPS Oper. Syst. Rev., 40(5):404–415, Oct. 2006. ISSN
0163-5980. doi: 10.1145/1168917.1168907. URL http:
//doi.acm.org/10.1145/1168917.1168907.

[21] M. H. Ling. An artificial life simulation library based on
genetic algorithm, 3-character genetic code and biological
hierarchy. The Python Papers, 7:5, 2012.

[37] G. P. Stein, G. Hayun, E. Rushinek, and A. Shashua. A
computer vision system on a chip: a case study from the
automotive domain. 2012 IEEE Computer Society Conference
on Computer Vision and Pattern Recognition Workshops, 00:
130, 2005. ISSN 1063-6919.

[22] F. McKeen, I. Alexandrovich, I. Anati, D. Caspi, S. Johnson,
R. Leslie-Hurd, and C. Rozas. Intel&reg; software guard extensions (intel&reg; sgx) support for dynamic memory management inside an enclave. In Proceedings of the Hardware
and Architectural Support for Security and Privacy 2016,
HASP 2016, pages 10:1–10:9, New York, NY, USA, 2016.
ACM. ISBN 978-1-4503-4769-3. URL http://doi.acm.
org/10.1145/2948618.2954331.

[38] A. K. Sujeeth, K. J. Brown, H. Lee, T. Rompf, H. Chafi,
M. Odersky, and K. Olukotun. Delite: A compiler architecture for performance-oriented embedded domain-specific languages. ACM Trans. Embed. Comput. Syst., 13(4s):134:1–
134:25, Apr. 2014. ISSN 1539-9087. URL http://doi.
acm.org/10.1145/2584665.

[23] Z. Michalewicz. Genetic Algorithms Plus Data Structures
Equals Evolution Programs. Springer-Verlag New York, Inc.,
Secaucus, NJ, USA, 2nd edition, 1994. ISBN 0387580905.

[39] L. Torczon and K. Cooper. Engineering A Compiler. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 2nd
edition, 2011. ISBN 012088478X.

[24] M. Mitchell. An Introduction to Genetic Algorithms. MIT
Press, Cambridge, MA, USA, 1998. ISBN 0262631857.
[25] U. Müller. Esoteric programming. URL https://goo.gl/
GnzaQe.

[40] A. Turing. Turing completeness. URL https://en.
wikipedia.org/wiki/Turing_completeness.

[26] H. Nguyen. Gpu Gems 3. Addison-Wesley Professional, first
edition, 2007. ISBN 9780321545428.

[41] R. M. Yoo, C. J. Hughes, K. Lai, and R. Rajwar. Performance
evaluation of intel&reg; transactional synchronization extensions for high-performance computing. In Proceedings of the
International Conference on High Performance Computing,
Networking, Storage and Analysis, SC ’13, pages 19:1–19:11,
New York, NY, USA, 2013. ACM. ISBN 978-1-4503-2378-9.
URL http://doi.acm.org/10.1145/2503210.2503232.

[27] M. O’Neill, L. Vanneschi, S. Gustafson, and W. Banzhaf.
Open issues in genetic programming. Genetic Programming
and Evolvable Machines, 11(3-4):339–363, 2010.
[28] H. Patil, C. Pereira, M. Stallcup, G. Lueck, and J. Cownie.
Pinplay: A framework for deterministic replay and reproducible analysis of parallel programs. In Proceedings of
the 8th Annual IEEE/ACM International Symposium on Code
Generation and Optimization, CGO ’10, pages 2–11, New
York, NY, USA, 2010. ACM. ISBN 978-1-60558-635-9. URL
http://doi.acm.org/10.1145/1772954.1772958.

[42] S. T. Zargar, J. Joshi, and D. Tipper. A survey of defense
mechanisms against distributed denial of service (ddos) flooding attacks. IEEE Communications Surveys and Tutorials, 15
(4):2046–2069, 2013. URL http://dblp.uni-trier.de/
db/journals/comsur/comsur15.html#ZargarJT13.

[29] P. M. Phothilimthana, A. Thakur, R. Bodik, and D. Dhurjati.
Scaling up superoptimization. SIGPLAN Not., 51(4):297–310,
Mar. 2016. ISSN 0362-1340. doi: 10.1145/2954679.2872387.
URL http://doi.acm.org/10.1145/2954679.2872387.
[30] B. C. Pierce. Types and Programming Languages. The MIT
Press, 1st edition, 2002. ISBN 0262162091, 9780262162098.
[31] S. J. Russell and P. Norvig. Artificial Intelligence: A Modern Approach. Pearson Education, 2 edition, 2003. ISBN
0137903952.
[32] M. L. Scott. Programming Language Pragmatics. Morgan
Kaufmann Publishers Inc., San Francisco, CA, USA, 2000.

11

2017/9/19

