Program synthesis is a special form of automatic programming

Automatic programming

In computer science, the term automatic programming identifies a type of computer programming in which some mechanism generates a computer program to allow human programmers to write the code at a higher abstraction level....

 that is most often paired with a technique for formal verification

Formal verification

In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...

. The goal is to automatically construct a program that provably satisfies a given high-level specification. In contrast to other automatic programming techniques, the specifications are usually non-algorithm

Algorithm

In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...

ic statements of an appropriate logical calculus

Formal system

In formal logic, a formal system consists of a formal language and a set of inference rules, used to derive an expression from one or more other premises that are antecedently supposed or derived . The axioms and rules may be called a deductive apparatus...

.

Origin

The idea originated in the 60s with the aim of using techniques
from artificial intelligence

Artificial intelligence

Artificial intelligence is the intelligence of machines and the branch of computer science that aims to create it. AI textbooks define the field as "the study and design of intelligent agents" where an intelligent agent is a system that perceives its environment and takes actions that maximize its...

to build an automatic programmer,
exploiting deep connections between mathematics and the theory of programming.
Lack of early success meant that the mathematical approach soon fell out of favour, along with enthusiasm for AI, in general. Although some researchers still
work on formal approaches, more success has been obtained by combining pure deductive techniques with powerful heuristics, and limiting their application to specific domains.

Problems and Limitations

Some feel that the concept of automated program generation often results in poor "factoring" of information. Known redundancy should be factored out, not introduced, it is said . However, sometimes specific programming languages are limited such that one has to introduce repetition of a concept or pattern in order to keep using the same language. Here is a simplified illustration of factoring:

Poor Factoring: x = a + a + a + a + a

Good Factoring: x = a * 5 (where the asterisk means "multiply")

Program generation tends to focus on automating the repetition seen in the first example, when a better approach is perhaps to find a higher-order abstraction, which is multiplication in this case. Other examples include putting parameters into a file or database instead of inside application code.