Editing Program synthesis (section)

=== Counter-example guided inductive synthesis ===

Counter-example guided inductive synthesis (CEGIS) is an effective approach to building sound program synthesizers.<ref>{{harv|Solar-Lezama}}</ref><ref>{{harv|David|Kroening}}</ref> CEGIS involves the interplay of two components: a ''generator'' which generates candidate programs, and a ''verifier'' which checks whether the candidates satisfy the specification.

Given a set of inputs {{var|I}}, a set of possible programs {{var|P}}, and a specification {{var|S}}, the goal of program synthesis is to find a program {{var|p}} in {{var|P}} such that for all inputs {{var|i}} in {{var|I}}, {{var|S}}({{var|p}}, {{var|i}}) holds. CEGIS is parameterized over a generator and a verifier:

* The ''generator'' takes a set of inputs {{var|T}}, and outputs a candidate program {{var|c}} that is correct on all the inputs in {{var|T}}, that is, a candidate such that for all inputs {{var|t}} in {{var|T}}, {{var|S}}({{var|c}}, {{var|t}}) holds.
* The ''verifier'' takes a candidate program {{var|c}} and returns ''true'' if the program satisfies {{var|S}} on all inputs, and otherwise returns a ''counterexample'', that is, an input {{var|e}} in {{var|I}} such that {{var|S}}({{var|c}}, {{var|e}}) fails.

CEGIS runs the generator and verifier run in a loop, accumulating counter-examples:

 '''algorithm''' cegis '''is'''
     '''input''': Program generator ''generate'',
            verifier ''verify'',
            specification ''spec'',
     '''output''': Program that satisfies ''spec'', or failure
 
     ''inputs'' := empty set
     '''loop'''
         ''candidate'' := ''generate''(''spec'', ''inputs'')
         '''if''' ''verify''(''spec'', ''candidate'') '''then'''
             '''return''' ''candidate''
         '''else''' ''verify'' yields a counterexample ''e''
             add ''e'' to ''inputs''
         '''end if'''

Implementations of CEGIS typically use [[SMT solver]]s as verifiers.

CEGIS was inspired by [[counterexample-guided abstraction refinement]] (CEGAR).<ref>{{harv|Solar-Lezama}}</ref>