Neural network DeepCoder learns to program, borrowing code from other programs

Conditional inaccuracy matrix for a neural network and a test set of 500 programs with a length of 3 lines. Each cell contains the average probability of a false-positive result (large print) and the number of test programs from which this value is derived (in smaller font, in parentheses). The saturation of the color correlates with the probability of a false-positive result.

Programmers will soon have a good helper: a smart neural network that is capable of performing routine tasks. Moreover, with the help of such a neural network, people can create programs without even knowing the syntax of a specific language and in fact not knowing how to program. You need to create an algorithm and set tasks - and the neural network will write code to solve them.

As a result, the entire work will become much more productive: “People will be able to create systems that could not be created earlier,” says independent expert Armando Solar-Lesama from the Massachusetts Institute of Technology, in a commentary for New Scientist .

Researchers from Microsoft and the University of Cambridge have developed a system called DeepCoder , which now correctly solves simple problems from school programming contests. DeepCoder uses a technique called “software synthesis” (Inductive Program Synthesis), which is known to many developers. It borrows code lines from other programs — and makes up its own unique program. It is important to keep in mind that DeepCoder, like other software synthesis systems, uses a domain-specific language (DSL) specialized for a particular application. It can be called a "mini-language" or a "curtailed programming language." It contains only nine first-order functions:
')
HEAD, LAST, TAKE, DROP, ACCESS, MINIMUM, MAXIMUM, REVERSE, SORT, SUM

and five higher order functions:

MAP, FILTER, COUNT, ZIPWITH, SCANL1

The scope of a domain-specific language is limited with respect to general purpose programming languages.

The selection of lines for the compilation of the program is carried out after analyzing the input and output values ​​of each code fragment. In scientific work, you can study nine examples of 5-line programs that are written by the DeepCoder neural network. For example, here is the solution to the candy problem (left) with a text description (right) and incoming values ​​(in the center):



In search of suitable lines of code, DeepCoder is superior to man: he is able to index and analyze much more sources than man is capable of. The machine learning system learns to understand how to use these patterns — and makes up the base in advance. In addition, the neural network connects the found lines in such a way that it would never occur to connect them to a living person. Through trial and error, a neural network gradually learns to achieve its goal. This implementation of software synthesis in the DeepCoder system is called the Learning Inductive Program Synthesis (LIPS).


Schematic representation of a direct link encoder and DeepCoder decoder

The illustration below shows how the DeepCoder neural network predicts the likelihood of each function appearing in the source code.



All these advantages allow DeepCoder to write programs much faster than its predecessors. She writes a program of three lines in a fraction of a second, while previous systems took several times or ten times more time to try all possible options. For example, the table shows the rate at which programs are generated from three lines of code with different tasks.



Programs from five lines of code are generated an order of magnitude slower. The graph on the right shows the dependence of speed on the length of the program.



As you learn, the system understands which code combinations work and which do not. It is being improved in programming with each new task.

The technology can potentially be used to refactor and search for bugs in programs. It will find incorrect lines and replace them with the correct lines from other programs. The authors believe that using it is easy to create routine programs in the style of the famous IFTTT - to automate basic interactions between different web services. Even a non-programmer can write simple instructions, such as selecting photos from Facebook and sorting according to specified criteria. Such simple programs can be created in minutes without programming knowledge.

Of course, such tools can not replace a real programmer. They are considered only as an auxiliary tool. DeepCoder developers themselves will be very useful in the future: it will remove the burden of routine operations and allow you to concentrate on more complex and important tasks.

At the moment, DeepCoder is able to solve programming problems, working with approximately five lines of codes. Of course, in advanced programming languages, five lines of code allow you to write a very useful program, but it's still quite simple, basic things. Experts believe that it is impossible to generate a complex program with a large amount of code using software synthesis. On the other hand, with human help this is possible. In the end, large programs consist of a large number of small fragments.

At least in the next few years, most programmers are not threatened with job loss due to automation of coding. But machine learning techniques are improving very quickly. It is amazing how much has been done in this area lately.