The next Battleground for AI : Automating Software Development

There are big arguments going around these days about whether Artificial Intelligence (AI) is over-hyped or not. It's time to put AI on trial to prove itself in a domain that is very difficult to solve efficiently, where there is very little theoretical guidance available and where a solution would save the world tons of money immediately. Such a battleground domain is here: automation of software development and automated programming.

As we all know by now, software eats the world.

Every year trillions of $$ are invested and spent on manually producing and maintaining software systems of all sorts and complexities around the globe. If only a small part of these expenses could be cut by automation, it would save us all billions. It's therefore quite surprising, considering the size of the software market globally and the money that could be made and saved by automating programming, that not more efforts are put into automating the various software development stages and maintenance processes.

Put AI to the Test

Automating software development is not only a perfect use-case for AI as it is a very difficult problem to be solved with no efficient conventional or standard methods available. It is a perfect environment for AI to prove itself.

In addition, at the heart of AI lies the problem of making AI systems not only self-learning but also self-optimising. An ideal AI system would not just learn from its interactions with the world it would also improve itself when noticing that some of its features are operating and performing sub-standard or sub-optimal. A perfect AI system would hence constantly monitor its own performance and improve and update its own code whenever needed and appropriate.

It's the main prediction of the Singularity theorists that AI systems at some point will start to improve themselves, self-optimise in iterative steps their own code in an exponentially shortening time frame and eventually leading to super-intelligent systems drastically outperforming humans in all intellectual capabilities.

Whether or not the Singularity will happen any time soon, it's in the key interest of AI researchers and our society as a whole to understand how software can be generated automatically and optimised efficiently - in a controlled manner.

I will describe here just a few promising ways how to approach this problem with AI methods and discuss some of the approaches that are currently used or emerging. Obviously, this is a vast and very complex scientific area so I will concentrate on just a few potential solutions and will not be able to cover the whole space here.

Automating the Software Development Cycle

AI can in principle be used beneficially in all phases and stages of the software development process and lifecycle. Starting with the planning and budgeting stage, to resource allocation, to the requirement specifications, to the design, the core programming and implementation, to integration with existing legacy systems and to testing, documentation, acceptance and finally to the roll-out, maintenance and administration of the software. In larger software projects the core programming part itself is usually only a small fraction of the overall project and mostly not the biggest part of the effort nor the budget.

It is pretty easy to see how AI can help and improve most of the stages that do not deal directly with programming and coding such as the budgeting, allocation of resources as well as maintenance and administration. These are mostly optimisation problems that can be resolved or at least supported with a myriad of existing AI technologies today. Therefore, I will not go into this here in more detail.

More tricky and much harder to automate are stages like the definition of the requirements, the design, testing and documentation. Here the potential AI approaches are quite diverse and range from the need of inventing special new specification languages to machine understanding of technical texts and documentation. These issues are in many cases not yet well understood and far from being resolved by AI. The solutions in these areas are probably best resolved by smart interactive AI systems that work together with humans and support them rather than trying complete automation.

Let's start then with a well established technology in AI:

Automation of Programming by Computational Evolution

Computational Evolution works with encoding a problem in structures that are abstract forms of biological genes. These genes represent (partial) solutions to the problem to be resolved and are usually encoded as digital arrays of numbers or binary values. The biology inspired computational evolution is part of AI since its earl days and has been used in many successful AI applications over the last decades. It is mimicking the biological evolution process on computers because biological evolution is known to be able to handle very complex and high dimensional optimisation problems efficiently. After all, evolution has created such complex organisms as us humans consisting of co-operating 10 trillion cells including our highly complex brains and many other highly complex and successful biological creatures in their ecological niches.

Along the way of doing so evolution has even created its own "programming language" and "programming tools" that allows and enables this optimisation process: our DNA ! It uses an alphabet of just 4 letters (the 4 nucleotides that make up the double helix of our DNA) to provide the blue-print and construction code for the self replication processes of our cells and the creation of proteins that we need to build up and to maintain our cells. It is a genius instruction set - i.e. program - for the working of all living organisms.

With this in mind, it is no far fetched idea to also try using evolution strategies to automate the generation of digital programs. As complex a task as this may be, it seems still way easier to resolve than generating humans.

The evolution algorithm at its core is surprisingly simple and can be written down in a just a few lines of high level code:

1. generate a random initial population of programs; define current_population as initial population
2. repeat until satisfying programs are contained in current_population - or computing resources are used up (time, memory, cost etc)

2.1 evaluate all members of the current_population; delete all members from current_population that do not reach a minimum evaluation criteria (survival of the fittest)

2.2 use the remaining current_population and recombine randomly picked pairs of programs from the current_population to create new programs (crossover simulation)

2.3 randomly modify the newly produced programs of the current population (mutation)

2.4 include new program members in current_population and goto Step 2.

At first sight, it seems like such an evolutionary approach to automate programming could never work. Especially steps 2.2 and 2.3 seem to be rather deconstructive than helping to build up working software systems step by step !

The wrong intuition here is that when you combine two programs in any automated schematic way (step 2.2) or when you randomly change parts of a program (step 2.3) the probably seems to be very high that the resulting programs won't work anymore - even if the programs in the original population did in fact work. Usual programs will crash or be unable to compile even if just a single syntactic sign is wrong or just at a wrong place. Every programmer knows this experience !

These are strong arguments at first sight, however this issue can be at least partially resolved. If a program is considered as a long sequence of syntactic sensitive symbols, then the above argument is indeed valid. The chances that a random recombination of 2 such long strings of symbols or some random mutation of symbols in the sequence would lead to a new working program are extremely slim. However, if a program is rather considered and analysed as a big decision tree (i.e. iterated and nested sequences of complex "if - then - else" statements) with more nested decisions the more complex the program is, and each key decision point is made up of further sub decision trees - then the situation changes.

Several types of mutations of such decision trees are easy to implement. Say a node of a sub tree contains the operator "+" (and hence the corresponding part of a program would be something like (a + b) or more formal (+ a, b).

This "+" operator has two arguments, two numbers say "a" and "b". A mutation could now just randomly replace the "+" with another arithmetic operator that also has 2 arguments, say ".", " - " or " / " - generating some new expression like (- a, b). However, in the case of "/" the mutation has to ensure that the second argument is not "0" or does not evaluate to "0" which is problematic as the argument may not be directly expressed as "0" in the code but say as "1+2*5-11". During run-time of the program this expression will then get evaluated as "0" which is not immediately recognisable as such for the mutation operator when it is applied to the source-code.

Also the re-combination and cross-over of two partial solutions and programs can be achieved with decision trees in a relative simple manner: just select a node in the overall decision tree of the first program and then replace this node and its complete sub-tree with a new selected node and its complete sub-tree of the second program. But here again it is important to make sure that the selected node of the first program is replaced by a node and sub-tree that fits the original node's syntactic constraints (number and type of arguments etc). This process may not be easily checked - or may take a prohibitiv amount of time.

Finally, the population dynamics are crucial. The composition and size of the initial population of (partial) programs is very important. If the population is too small and not diverse enough then the evolution process does not have enough material to work on to find a promising solution and best program. However, if the initial population is too large, the process may take forever. The art here is to start with a good population of partial and good approximations to the final best solution (if it exists) or the best known possible approximations of a solution (best know programs to solve at least some part of the overall task).

Meta-Evolution

Another major issue with computational evolution is that the performance of the algorithm depends on many optimisation parameters like the ones we have already shortly discussed and several others: the mutation steps (size, rate and frequency), the number of partial solutions in a population, the size and quality of the initial population, the cross-over mechanism, the fitness function and its evaluation criteria, the number of generations needed, the parallelisation parameters and migration factors and many other more sub parameters that need to be used and fine tuned during the evolution simulation.

The usual way to handle all these parameters is to use some outside mathematical estimation function of the best parameter settings and adjust these during the simulations to improve the results. However, since this is again a massive multi-dimensional task the idea of a meta-evolution came up early in AI research. The idea here is simple: just encode all these important control parameters also as part of the genes of the encoded problem solutions and therewith evolve and optimise the control parameters at the same time concurrently with the original encoded genes in all populations.

This can actually be done, however in many cases in which the evolution generates better results, it may not be clear anymore if this was due to a good genetic optimisation algorithm applied to the base problem or the better optimisation of the control parameters - and the same applies to the cases when the evolution fails to achieve better results. The meta evolution may increase the efficiency but may blur the view of what caused the evolution to generate a specific good or bad outcome and solution.

A complicated issue for practical purposes is the calculation of the fitness value of a solution or partial solution. This can be very expensive in terms of resources available. Often a whole program with potentially millions of lines of code has to be executed to calculate a fitness value. This can take a long time to do and needs to be done for every single member of the program population and for all generations of all populations. So, millions of iterations of these calculations are not seldom in complex problems like program automation.

Parallelisation

A big advantage of computational evolutionary methods however, is that in most cases the simulation can be easily parallelised to massively speed up the process. The common approach is to divide the initial population of initial and partial solutions into many sub-populations and then assign every sub-population generated to a different computing node (CPU, GPU, Server-farm) and do all simulations required for a specific population locally right on the assigned node itself. Within one cycle of the simulated evolution (one generation of new potential solutions) the mutation and cross-over process within the sub-population is executed and a new generation of (partial) solutions is generated.

The next step is crucial for finding optima in the highly multi-dimensional search of the program space. The simplest approach is to just run the whole simulation locally and also calculate the fitness values locally. That means that every sub-population will drive to its own local optimum. Once there is no further progress to be measured the best individuals of each sub-population will be transferred back to the original population and become part of the top level population which will be again sub-divided at some point and then again be spread out for further optimisation.

A more sophisticated and usually more efficient approach is to have some sort of a "migration scheme" between the sub-populations that allows fit individuals to switch populations during the local optimisation process and hence generate more diversity in the evolution process. This approach usually leads to a wider reach of the evolution process in high dimensional search tasks as the migration of "fresh solutions" into an existing population usually avoids the population getting trapped by too much of conformity of the partial solutions generated.

Other AI Approaches to Programming Automation

Evolutionary methods are not the only way AI can approach the automatic programming challenge. There are many more options available.

The best Way may be just to "steal" the Software needed

One way of creating programs automatically can be to simply "steal" the required code or code fragments from somewhere else and then "just" combine these code fragments into a coherent code. Rather than generating code by evolving from random scratch code fragments this method has the advantage that many standard code functions often already exist somewhere in the cloud and the main task is "just to find" them and combine them in a reasonable way to create the desired code (the combination part, however can again be done with evolutionary methods once the basic function code is found). This "smart stealing" approach is therefore more like solving a huge puzzle while finding the right matching pieces somewhere in the cloud.

Large companies (especially software producing companies) often have aggregated huge repositories of source-code internally over many years or even decades. Nevertheless, a lot of programming is often still done over and over again from scratch because software engineers often do not know that some functions have already been implemented and developed in the past somewhere else inside the company.

So, the intelligence here would be to find and search the internal programming source-code libraries for matches. This is no easy task as many needed functions may not be explicit modules but rather sub-routines of more complex code. Also, the way how to implement a specific piece of code is often not uniform and may have been done in a specific way that is unusual practise and hence hard to find and search for. It is already difficult to find the same function when it is implemented in different programming languages.

The "stealing" approach is not only interesting for large corps with big software repositories. Today billions of lines of source code are available to everyone in the cloud on open-source platforms. Many functions and useful procedures can be found there. This process has democratised to some extend the options to automate programming be re-using existing source code libraries in open-source software packages. This even applies to AI itself as most of the big players in the field (Google, Microsoft, Facebook etc) have made their source code for AI methods publicly available in such open-source libraries.

Stealing - or better - re-using code from the cloud and code repositories and using it to create new software packages will not generate genuinely new code and complete new software solutions. However, if this method helps to "just" automatically generate some substantial percentage of what would normally require massive manual coding, it will be worthwhile doing so in many cases and may save a lot of effort and cost.

New Programming Languages

One final option for AI I want to discuss here that might speed up the automation of programming dramatically is the use and invention of new or specific programming languages to solve the problem.

In the early years of AI a strong focus of the community was on inventing the best programming languages for AI itself to speed up the development of powerful AI systems and to make it easier to implement very complex intelligent functions. As a result the powerful programming languages LISP and PROLOG were created. Regrettably, in the last few decades these languages have largely been neglected even though they are still very powerful and optimised for the use in AI and its applications.

LISP was invented already in 1958 by John McCarthy, one of the pioneers of AI. It is therefore one of the oldest high level programming languages around. It was the leading AI language in the early days of AI and heavily used from the 1960s well through the 1990s even with dedicated special machines and hardware called "LISP machines".

The power of LISP comes from its extreme flexibility and simplicity. All structures within LISP are just nested lists of characters and functions. A LISP program itself is also a nested list of characters and functions. This simple list structure of LISP programs gave rise to the tree-based understanding and manipulations of programs. A LISP program is able to generate and modify LISP programs even when they occur within its own code and hence can modify itself during processing ! This feature makes LISP unique and predestined especially for AI and the automation of programming.

However, even though LISP is a very flexible and powerful programming language, it still follows the classical paradigm of programming which considers a program as a list of instructions for the computer to execute in a certain sequence. To program using this paradigm means to find the right commands and sequence of commands to execute and to write them down in the programming language.

PROLOG, introduced around a decade later in the early 1970s uses a completely different paradigm for programming. In PROLOG a programmer does not need to find the right commands and the right nesting order of these commands anymore but rather just describes in the PROLOG language all the known and relevant facts about a problem to be resolved in form of logical relations and rules that relates the facts/relations to another. That's why PROLOG is called a descriptive or declarative language rather than a command language.

A very simple PROLOG program hence looks something like this (disregarding the exact PROLOG syntax here):

Child (maria); age(maria,5); female (maria)

Child (anna), age (anna,7); female (anna)

Sisters (maria,anna)

IF Sisters (x,y) then Sisters (y,x)

IF Sisters (x,y) then female (x) and female (y)

Older-sister (x,y) : IF Sisters (x,y) and age(x,n) and age(y,m) and n>m

When asked, a PROLOG program can then automatically answer for example the query:

older-sister (anna, maria)? with : YES.

The reason why this works is that PROLOG is based an a logical proof method called "logical resolution" which automatically derives the query from the given facts and rules supplied using first order mathematical logic theorem proving mechanisms. Since the programmer of a PROLOG program can focus on collecting and generating all known and relevant facts, it can be a major reduction of effort for certain type of problems compared to a command type language like when using massive databases that contain all the relevant facts needed.

Another very interesting feature of PROLOG is that it narrows the usual wide gap between a program's specification and its final code. In PROLOG no program is to be specified. The PROLOG code is just a set of facts (expressed as logical relations) and some logical rules that define the relations. The code in PROLOG can be seen as its own specification in logical expressions. This allows a potential strong reduction of the effort to first write a program specification and then solve the "translation" problem for a program to "understand" the specification usually written in natural language for non declarative languages.

Neither LISP nor PROLOG however, are ideal languages for automating software development. Both are slow during execution and hard to parallelise. Each has its constraints and disadvantages but also some unique and helpful features to solve the automation problem.

For the AI community it is high time in my eyes to develop new, powerful programming methods and paradigms like it was done in the 60s and 70s to create more efficient and practicable programming languages. These are needed now to help us solve our modern times AI problems.

Conclusion

I have just described some very basic methods for AI based programming automation. There are many other ways to attack this problem and most of the successful approaches will somehow combine new methods with some of the methods mentioned here.

The current younger generation of AI researchers does not seem to notice the importance of these techniques. They seem to belief that Deep Learning is the climax of AI and think, the AI of the future will just learn "everything" from data sets. But this is pure nonsense and based on a lack of knowledge of AI theory and practise.

The key to success in AI is to find new and much more efficient ways how machines can improve their own programs and code. It is what will make the Singularity a reality some day.

After autonomous vehicles like self driving cars and drones have conquered our world, self programming AI systems and effective AI methods for automated programming will be the next major battleground for AI !

E.Schoneburg

Hong Kong, March 22, 2017