Editing Program synthesis (section)

{{Short description|Task to construct a program meeting a formal specification}}
In [[computer science]], '''program synthesis''' is the task to construct a [[computer program|program]] that [[provably correct|provably]]{{sic|hide=y}} satisfies a given high-level [[formal specification]]. In contrast to [[program verification]], the program is to be constructed rather than given; however, both fields make use of formal proof techniques, and both comprise approaches of different degrees of automation. In contrast to [[automatic programming]] techniques, specifications in program synthesis are usually non-[[algorithm]]ic statements in an appropriate [[formal system|logical calculus]].<ref>{{cite book |last1= Basin |first1= D. |last2= Deville |first2= Y. |last3= Flener |first3 = P. |last4= Hamfelt |first4= A. |last5= Fischer Nilsson |first5= J. |chapter= Synthesis of programs in computational logic |editor=M. Bruynooghe and K.-K. Lau | publisher=Springer | series=LNCS | volume=3049 | pages=30&ndash;65 |citeseerx=10.1.1.62.4976 |title= Program Development in Computational Logic | year = 2004 }}</ref>

The primary application of program synthesis is to relieve the programmer of the burden of writing correct, efficient code that satisfies a specification. However, program synthesis also has applications to [[superoptimization]] and inference of [[loop invariant]]s.<ref>{{harv|Alur|Singh|Fisman}}</ref>