Dafny as Verification-Aware Intermediate Language for Code Generation

Dafny as Verification-Aware Intermediate Language for Code Generation

arXiv is now an independent nonprofit! Learn more×

Dafny as Verification-Aware Intermediate Language for Code GenerationConference: ; January 19, 2025; Denver, Colorado, US

Yue Chen Li Affiliation: Massachusetts Institute of Technology , United States email: yuechen.lyc@gmail.com Note: The author worked on this project during their internship at Amazon Web Services in Boston, USA. , Stefan Zetzsche Affiliation: Amazon , United Kingdom email: stefanze@amazon.co.uk Note: Corresponding author and Siva Somayyajula Affiliation: Amazon , United States email: somayyas@amazon.com

© none

Abstract.

Using large language models (LLMs) to generate source code from natural language prompts is a popular and promising idea with a wide range of applications. One of its limitations is that the generated code can be faulty at times, often in a subtle way, despite being presented to the user as correct. In this paper, we explore ways in which formal methods can assist with increasing the quality of code generated by an LLM. Instead of emitting code in a target language directly, we propose that the user guides the LLM to first generate an opaque intermediate representation, in the verification-aware language Dafny, that can be automatically validated for correctness against agreed on specifications. The correct Dafny program is then compiled to the target language and returned to the user. All user-system interactions throughout the procedure occur via natural language; Dafny code is never exposed. We describe our current prototype and report on its performance on the HumanEval Python code generation benchmarks.

1. Introduction

Prompting large language models (LLMs) to generate code from natural language specifications has garnered significant attention from both academia and industry (Jiang et al. 2024). However, such code can either contain bugs or be counterintuitive when compared to the initial specification, despite being confidently presented as correct.

For example, a user might prompt an LLM to generate an efficient Python implementation of the Fibfib sequence (Figure 2), which is similar to the classic Fibonacci sequence. It differs in that each term is equal to the sum of the previous three terms instead of the previous two. In Figure 3 we present Python code that was generated by a state-of-the-art model in response. Despite seeming correct, it contains a subtle error that causes the code to return the wrong value for n > 2. To allow the LLM to recover from its mistake, we provided it with the observation that the test cases in the initial prompt were violated by its synthesised code. In certain instances, this was enough to obtain a correct implementation with its next response. Occasionally, however, it introduced a new bug and, worse, modified the provided test cases to fit its faulty implementation. We will revisit this example later on.

In this paper, we propose to utilise Dafny as an intermediate technology within a code-generating chatbot prototype on the way to higher quality mainstream-language code. Dafny is particularly well-suited for this purpose, because:

(1)

It allows for a clear distinction between the specification of a program—derived from a natural language prompt using an LLM—and its implementation, which can again be dialogically derived using an LLM with verification feedback in the loop.

(2)

The multiple backends supported by the Dafny compiler enable code generation in a variety of mainstream languages, which is ultimately presented to the user, while internally only requiring verification once.

  1. A Figures

For example, the Fibfib sequence described in (Figure 2) can be formalised in Dafny as the recursive function:

function fibfibFunc(n: int): int

requires n >= 0

decreases n

{

match n

case 0 => 0

case 1 => 0

case 2 => 1

case _ => fibfibFunc(n-1) + fibfibFunc(n-2) + fibfibFunc(n-3)

}

The synthesis problem faced by an LLM then can be specified as the one of finding an imperative implementation and proof hints to fill into the method below:

method fibfib(n: int) returns (result: int)

requires n >= 0

ensures result == fibfibFunc(n)

{…}

In the next section, we detail the architecture of the chatbot prototype and explain, in particular, how the use of Dafny itself can be and is opaque to the user. In the following sections, we present some initial benchmarks and the immediate next steps.

Dafny-guided code generation lies between traditional program synthesis and proof synthesis for math olympiad problems that systems like Google DeepMind’s AlphaProof target for. Work exploring the role of prompt engineering and search-based approaches for the synthesis of Dafny code include that of Misu et. al. (Misu et al. 2024) and Branfonbrener et. al. (Brandfonbrener et al. 2024). Here, we utilise few-shot prompting to improve the quality of generated code. Other work leverages Dafny to catch incorrect code, e.g., by automatically synthesizing specifications to check for program correctness (Loughridge et al. 2024) (Mugnier et al. 2024). Lastly, we utilize the idea of consistency between an implementation and its specifications as introduced by Clover (Sun et al. 2024).

2. Current Prototype

In this section, we provide an overview of a prototype chatbot that is based on Claude Sonnet 3.5 but has been modified to leverage Dafny as an opaque intermediate language for the generation of correct Python code.

2.1. Higher quality code generation with Dafny

Figure 1. Pipeline

Figure 1 depicts the high-level structure of the prototype.

We start on the left, with the natural language input of the user. The LLM formalises the prompt in Dafny and returns to the user a natural language translation of the Dafny program that captures the code synthesis task the LLM understands it is supposed to solve.

The user is able to give their feedback to the formalisation and the natural language conversation loops until both sides agree on a description of the task. This provides a transparent notion of correctness that we can validate a solution against.

The LLM then generates an attempt at a solution and a proof of its correctness. The Dafny verifier either accepts the candidate solution or rejects it and allows the LLM to refine it or start from scratch again. The process then continues in a loop until a solution appears. This step is completely automated.

Once the loop has converged, Dafny generates additional unit tests for the solution and then the prototype uses its compiler to translate the solution to the target language. In our case the target is Python, but it could also be Java, etc. The compiler output then may be further optimised and verified for equivalence.

Finally, on the right, the user is presented a specification of the problem in the target language, an implementation, and unit tests. The correctness of the solution is implicit as it was present in Dafny and has been preserved with high assurance by the translation.

2.2. A demo run

To illustrate the interactive nature of the pipeline, we prompt the chatbot with a variation of Figure 2 that contains a typo: in the inductive step, we incorrectly write n-4 instead of n-3.

After a few seconds, the modified chatbot responds with a natural language summary of the underlying Dafny specification of the problem it’s been served. Dafny itself is never mentioned in the conversation. There is a slight delay that comes from a loop in the background that ensures only code that is run-time safe and verifiable is returned. At the end of the summary, the LLM points out a few key differences between the initial prompt and the Dafny specification, such as that the input must in fact be non-negative. Most interestingly, it presents a fourth base case fibfib(3) == 1 that it says has been implicit in the initial prompt. During the opaque synthesis of the problem specification in Dafny, the verifier seems to have realised that with the typo the recursive definition of fibfib is not well-defined. To solve the issue, the LLM then seems to have synthesised a missing base case, with which the program verified! While the new specification is well-defined, it does not represent our initial intent. Therefore, we respond to the summary by pointing out the typo in our initial prompt.

The LLM comes back with a new specification of the problem which now looks correct, so we accept it and continue with target language code generation. After a few moments, we are presented a Python programs that contains an imperative method fibfib, a recursive function fibfibFunc, and a Main method with user provided test cases as well as additional tests that check the equivalence between fibfib and fibfibFunc at runtime (Figure 4). Under the hood, the LLM has generated an intermediate Dafny program and a proof that it satisfies the agreed on specification, before translating it to Python. The returned Python program now looks good, so we skip on prompting further modifications. A transcript of the full conversation is given in Figure 9.

Figure 2. A user prompting a chatbot to generate an efficient Python implementation of the Fibfib sequence

Please write a Python function ‘fibfib(n: int)‘ to efficiently

compute the n-th element of the FibFib number sequence.

The FibFib number sequence is a sequence similar to the Fibbonacci

sequence that’s defined as follows:

fibfib(0) == 0

fibfib(1) == 0

fibfib(2) == 1

fibfib(n) == fibfib(n-1) + fibfib(n-2) + fibfib(n-3).

The function ‘fibfib‘ should satisfy the following test cases:

fibfib(1)

0

fibfib(5)

4

fibfib(8)

24

Figure 3. A faulty Python implementation of the fibfib sequence generated by an LLM

def fibfib(n: int) -> int:

if n <= 1:

return 0

elif n == 2:

return 1

else:

fib_values = [0, 0, 1]

for i in range(3, n+1):

next_value = sum(fib_values)

fib_values = [fib_values[1], fib_values[2], next_value]

return fib_values[0]

2.3. Comparison of native and compiled solutions

Figure 3 shows the Python code that was generated directly by an LLM without utilising Dafny in any way. It incorrectly returns fib_values[0] instead of fib_values[2].

Figure 4 shows the Python program that was generated by our prototype with Dafny in the loop. The program consists of the following components:

•

An imperative implementation (fibfib)

•

A functional specification (fibfib_func)

•

Tests that were provided by the user (Default.fibfib(1) == 0)

•

Additional tests generated by Dafny (Default.fibfib(3) == Default.fibfib_func(3))

The program is run-time safe and its correctness is implicit through a proof in Dafny.

Figure 4. The Python implementation of the fibfib sequence generated by our prototype.

class Default:

@staticmethod

def fibfib(n):

if n <= 1:

return 0

if n == 2:

return 1

a, b, c = 0, 0, 1

for _ in range(3, n+1):

a, b, c = b, c, a + b + c

return c

@staticmethod

def fibfib_func(n):

if n 0 or n 1:

return 0

if n == 2:

return 1

return (Default.fibfib_func(n-1) + Default.fibfib_func(n-2) +

Default.fibfib_func(n-3))

@staticmethod

def main():

assert Default.fibfib(1) == 0, “expectation␣violation”

assert Default.fibfib(5) == 4, “expectation␣violation”

assert Default.fibfib(8) == 24, “expectation␣violation”

assert Default.fibfib(3) == Default.fibfib_func(3), “expectation␣violation”

assert Default.fibfib(2) == Default.fibfib_func(2), “expectation␣violation”

assert Default.fibfib(1) == Default.fibfib_func(1), “expectation␣violation”

assert Default.fibfib(0) == Default.fibfib_func(0), “expectation␣violation”

if name == “main”:

Default.main()

2.4. Overview of Dafny code generation strategies

Prompts provide rules for output generation

To help the LLM with generating a Dafny specification from natural language, we provide it with a system prompt (Figure 5). The prompt states the LLM’s role on a