Program synthesis promises to help software developers with everyday tasks by generating code snippets automatically from input-output examples and other high-level specifications. The conventional wisdom is that a synthesizer must always satisfy the specification exactly. We conjecture that this all-or-nothing paradigm stands in the way of adopting program synthesis as a developer tool: in practice, the user-written specification often contains errors or is simply too hard for the synthesizer to solve within a reasonable time; in these cases, the user is left with a single over-fitted result or, more often then not, no result at all. In this paper we propose a new program synthesis paradigm we call \emph{best-effort program synthesis}, where the synthesizer returns a ranked list of partially-valid results, i.e., programs that satisfy some part of the specification.

To support this paradigm, we develop \emph{best-effort enumeration}, a new synthesis algorithm that extends a popular program enumeration technique with the ability to accumulate and return multiple partially-valid results with minimal overhead. We implement this algorithm in a tool called Bester, and evaluate it on $79$ synthesis benchmarks from the literature. Contrary to the conventional wisdom, our evaluation shows that Bester returns useful results even when the specification is flawed or too hard: i) for all benchmarks with an error in the specification, the top three Bester results contain the correct solution, and ii) for most hard benchmarks, the top three results contain non-trivial \emph{fragments} of the correct solution. We also performed a small user study, which confirms our intuition that partially-valid results are useful: the study shows that programmers use the output of the synthesizer for comprehension and often incorporate it into their solutions.