  This article is concerned with the application of the program extraction
technique to a new class of problems: the synthesis of decision procedures for
the classical satisfiability problem that are correct by construction. To this
end, we formalize a completeness proof for the DPLL proof system and extract a
SAT solver from it. When applied to a propositional formula in conjunctive
normal form the program produces either a satisfying assignment or a DPLL
derivation showing its unsatisfiability. We use non-computational quantifiers
to remove redundant computational content from the extracted program and
translate it into Haskell to improve performance. We also prove the equivalence
between the resolution proof system and the DPLL proof system with a bound on
the size of the resulting resolution proof. This demonstrates that it is
possible to capture quantitative information about the extracted program on the
proof level. The formalization is carried out in the interactive proof
assistant Minlog.
