The standard approach to solving large sets of related problems is to choose a canonical language for describing all of them, and then write a translator that will reduce them to some other canonical language which is then solved.

The descriptive language has to be easy for humans to understand, and the solver language has to be easy for solvers to handle.

The basic idea that all problems are written in a human language and then translated to a low-level language is of course how all computers work; think Java –> Opteron machine language.

OK so what does this have to do with automatic programming? I’m going to make a short detour into a related problem and then circle back to this.

It has to do with methods for solving NP problems. A central idea in the theory of NP-completeness is the concept of reduction. Reduction is a procedure for showing that a given problem is related to another problem in a specific way. The concept is usually used in an academic context for proving that a problem is NP-complete, but there is a recent move to using reduction in practical contexts.

Here’s an example: A very interesting result called Fagin’s theorem shows that any NP problem can be posed in something like SQL with some extensions. So for the NP version of automatic programming, we can use logical declarations to define the specification, and have an automatic translater to a canonical solver language, like SAT (or the two-dimensional Ising model in a magnetic field for those of you paying attention :) ) for example.

If the solvers used on the canonical solver language are good enough, the cost of doing the translation can in principle be overcome. For NP problems it has usually been assumed that each individual problem is better treated by a heuristic designed specifically for its solution, and that in reducing it to something else (like SAT) you will lose more than you gain.

There are two obvious loopholes in this view. The first is that if a particular solver of a particular NP problem is much better than any other, the cost of reduction may be swamped by the gain you get in converting. The second is that having a universal language in which any NP problem can be posed would be extremely useful for programmers and application development, and even if you take a performance hit the added flexibility and generality could be worth it.

Alright back to automatic programming. Let’s assume that we have a set of problem specifications making up the desired product specifications for a software product. Let’s further assume that all of these problems are no worse than NP-complete. Further assume that we can divide these problems into two categories: those in P, and those not in P. If we have a declarative language that allows us to program by specifying only what a solution looks like, with automatic conversion to some canonical solver language, then I think this is sufficient for automatic programming.

The reduction for P problems we already have (P problem stated in Java–>matrix multiplication for example). In this framework we’d need a high level declarative language for problems in P (declare the solution specs, and an automatic process converts to a canonical problem in P (like matrix multiplication), which is then solved by conventional hardware, probably specifically optimized for that problem).

I’m going to speculate that if we had a machine that could do the same automatic reduction with a general and flexible NP-complete solver, taken together with the P solver above we’d have an automatic programming system for nearly all human-related software engineering projects.

OK so I’m going to tentatively put automatic programming into the applications section. Specifically I’m going to assume the following:

- A black box solver of two-dimensional Ising model in magnetic field (ISING), which was extremely fast and accurate, could be used as a solver for a high level declarative programming language for all problems that can be polynomially reduced to ISING.
- The lack of a high-level declarative language that returns highly accurate solutions quickly even for extremely large NP-complete problems is the main barrier to automatic programming; all of the other knowledge and technology to solve this problem already exists.

It’s pretty clear that automatic programming meets the requirements for a good application–this one would definitely be over $1B/year in revenue.

This line of reasoning has been pursued at least for 6 years or so.

There is a number of very impressive SAT solvers, and they have

been improving by a factor of two since year 2000. A good example

is http://www.cs.chalmers.se/Cs/Research/FormalMethods/MiniSat/

which you can download in source code (only 700 lines in C).

There have been attempts at high-level languages to describe

NP problems and reduce them to SAT. One example is NP-spec

(but I am not aware of working software that you can download).

Roughly speaking, this is where the buck stops. A number of

papers published point out the difficulties of automatic conversion.

A case in point would a paper that I co-authored (yes, this is

a shameless plug)

A. Ramani, F. A. Aloul, I. L. Markov and K. A. Sakallah, “Breaking Instance-Independent Symmetries in Exact Graph Coloring.”

Journal of Artificial Intelligence Research, vol. 26, pp. 191-224, 2006.

http://www.eecs.umich.edu/~imarkov/pubs/jour/jair06-graphcol.pdf

It shows that reducing to SAT a specific problem (graph coloring)

that looks fairly close to SAT is non-trivial because it introduces

symmetries. If you start working with integers (e.g.. in the Traveling

Salesman Problem), you are opening a whole new box of worms.

Best of luck,

Igor Markov

This might be of interest (it’s an Automatic Programming tutorial at ICML’06):

http://et.evannai.inf.uc3m.es/icml06/aiptutorial.htm

Pingback: augmentin 500

Pingback: Amorrosea Just Love Pink