  Large stochastic language models show great promise in many domains,
including programming. A promise is easy to make but hard to keep, and language
models often fail to keep their promises when applied to programming,
generating erroneous code. One promising avenue to keep models honest is to
have them generate code in a language that supports formal verification: if and
when that is adopted, the model would provide proof along with the code, and
that proof would be automatically verified. Unfortunately, existing large
language models show a severe lack of proficiency in verified programming
languages. In this paper we demonstrate how to improve two pretrained models'
proficiency in the Dafny verified programming language. Using 178 programming
problems from the MBPP dataset, we prompt two contemporary models (GPT-4 and
PaLM-2) to generate methods in Dafny. We use three different types of prompts:
a direct contextless prompt, a second one that includes a signature of the
method and test cases, and a third one that decomposes the problem into steps
and includes dynamically chosen similar examples. Our results show that GPT-4
is better than PaLM-2, but that, in both models, the third prompt greatly
improves the success of the generation task for the direct prompt. With the
third prompt, GPT-4 was able to generate verified (and human-evaluated) Dafny
methods in 58% of the cases, while the first prompt generated verified (and
human-evaluated) methods in only 19% of the cases. Surprisingly, the second
prompt had the worst performance, with only 10%. One tangible contribution of
our work is a collection of 153 MBPP problems that are implemented and formally
verified in Dafny, 50 of which were written by us and 103 were automatically
synthesized by GPT-4. Additionally, our results demonstrate that the benefits
of formal program verification (proof of correctness) are now within reach...
