Pleasant Imperative Program Proofs with GallinaC

Frédéric Fort 1, David Nowak 1, Vlad Rusu 2 · 2025

Read Pleasant Imperative Program Proofs with GallinaC by Frédéric Fort 1, David Nowak 1, Vlad Rusu 2 (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-13019.txt.

Introduction

Frederic Fort, David Nowak and Vlad Rusu embed a command tongue inside a proof tool in 2025. Command code still runs kernels and low layers. Proofs in real tongues drown in admin detail due to loose rules.

GallinaC sits inside Gallina, the tongue of the Rocq proof tool. It is complete and has a true free while loop. Proofs can use the same moves as pure code proofs. A test proof checks list flip for lists of unknown size. Work now links the mid form to Cminor, the entry tongue of the CompCert back end. First results look strong.

Catalog record

CREATORFrédéric Fort 1, David Nowak 1, Vlad Rusu 2
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE22 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-13019

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Pleasant Imperative Program Proofs with GallinaC Frédéric Fort 1, David Nowak 1, Vlad Rusu 2 Abstract 1 Introduction Even with the increase of popularity of functional programming, imperative programming remains a key programming paradigm, especially for programs operating at lower levels of abstraction. When such software offers key components of a Trusted Computing Base (TCB), e.g. an operating system kernel, it becomes desirable to provide mathematical correctness proofs. However, current real-world imperative programming languages possess “expressive”, i.e. overly permissive, semantics. Thus, producing correctness proofs of such programs becomes tedious and error-prone, requiring to take care of numerous “administrative” details. Ideally, a proof-oriented imperative language should feature well-behaved semantics while allowing typical imperative idioms. To obtain a high-degree of confidence in the correctness of such a language, its tools should be developed inside a proof-assistant such that program proofs, be it that the compiler passes preserve semantics or any proof written by language users, are machine checked. Such an embedding of a programming language may either be deep or shallow [ 20 ] . With deep embedding , the language is defined using the available data structures of the implementation language, e.g. inductive types in the Rocq proof assistant [ 16 ] . With shallow embedding , the programming language is directly a subset of the implementation language. Historically, deep embedding has been considered the preferred approach for sufficiently complex languages. Indeed, deep embedding allows to define arbitrary complex languages independent from the limitations of implementation language. For instance, Gallina, the functional programming language of the Rocq proof assistant is total for soundness reasons, excluding turing-completeness. Yet, inductive proposition may define the semantics of a turing-complete language, such as C [ 9 ] . However our experience has shown that, deep embedding poses practicability issues. Indeed, since the language is completely constructed bottom-up, every property, theorem, proof tactic has to be defined and proven from the ground up. On the opposite, since shallow embedding uses a subset of the implementation language, if the language is sound, certain theorems are for free and the usual proof tactics are available. Previous work using shallow embedding has produced substantial programs and their correctness proofs such as a hypervisor with formally-proven isolation guarantees [ 5 , 6 ] or a real-time scheduler using the Earliest-Deadline First policy [ 17 ] . However, their source languages were not turing-complete. In particular, they lacked a generic recursion mechanism: Their while loop construct used fuel, i.e. an at compile time defined maximum iteration count. Recent work [ 3 ] has shown how to define partial (co-)recursive functions directly inside the Gallina language. This enables us to define a shallow embedding of a potentially unbounded while loop, bringing turing-completeness to the Gallina language. Contributions In this paper, we present GallinaC , a shallow embedding of a Turing-complete imperative language directly inside the functional programming language of the Rocq proof assistant, Gallina. In particular, it features a truly generic and unbounded while loop. Having a functional core means proofs about GallinaC programs may use the same tactics as proofs about pure functional ones. Compilation from GallinaC to binary is possible through the CompCert certified compiler. A chain of forward simulations guarantees that compilation passes preserve semantics. Work on GallinaC is still under progress, but we present first promising results. A prototype implementation has shown the viability of GallinaC with the correctness proof of a list reversal procedure for linked-lists of unknown size. We currently focus on the forward simulation between the GallinaC intermediate representation (IR) and Cminor, the entry language of the CompCert back-end. The GallinaC sources are available online ( https://gitlab.cristal.univ-lille.fr/ffort/gallinac ). 2 Motivational Example ⬇ Definition reverse ptr := var node <- ptr ; var new_next <- NULL ; let deref_next := do ptr <- read_var node ; do val <- read_ptr ( ptr + 1); ret val in let cond := do curr <- read_var node ; ret ( negb ( curr =? NULL )) in while cond {{ do curr <- read_var node ; do next <- deref_next ; do prev <- read_var new_next ; write_ptr ( ptr + 1) prev ;; write_var node next ;; write_var new_next curr }};; read_var new_next Figure 1 : List reversal in GallinaC As a motivational example, let us consider the program from Figure 1 . Provided a pointer that points to a member of a simply-linked list, it performs an in-place list reversal by swapping pointers. Linked list nodes are composed of two memory words, one holding the value and one holding the pointer to the next list node. The first two lines declare mutable variables which hold respectively the list node currently under consideration and the node’s new next pointer. Obviously, at program start these are initialized to the list’s entry pointer and the typical sentinel value NULL . Next, two helper functions are declared. The first, deref_next , loads the list node pointed to by the current node’s next pointer. The second, cond , is the while loop’s invariant: the pointer to the next node to consider is not NULL . The remainder is the “main” function of the program. The core is a while loop that breaks once node holds the NULL pointer. At each loop iteration, the current node’s next field is updated. For the next iteration, node and new_next are set respectively to the current node’s next field and the current node. The program terminates by returning the address of the list’s new first node. This program illustrates GallinaC’s new while loop. Note that the loop is not annotated with a fuel amount or any other kind of restriction: a programming error could produce an infinite loop. 3 Language Design GallinaC programs are Gallina terms with type program S A . The program monad incorporates state, failure and non-termination effects. While it could theoretically be constructed using monad transformers, its current implementation is a custom monad. The type parameter S is the type of the state, i.e. the heap and store of the program. The type parameter A is the return type of the monadic computation, assuming it doesn’t fail. The non-termination monad is adapted from [ 3 ] . The monad functor is the option type where None encodes bottom, i.e. non-termination. We first define the while functional : ⬇ Definition whileF { S : Type } ( cond : program S bool ) ( W : program S unit -> program S unit ) ( body : program S unit ) : program S unit := If cond then ( body ;; W body ) else ret tt . As can be seen, the recursive, non-guarded, call is replaced by a call to an additional argument W . We then leverage Kleene’s fixed-point theorem stating that a continuous function with signature A\rightarrow A where A is equipped with a CPO has a least fixed-point. For our whileF this fixed-point is the “true” while . Continuity itself is proven using Haddock’s theorem [ 3 ] . \displaystyle e \displaystyle=id \displaystyle\mathord{\makebox[0.0pt]{$\hskip 4.30554pt|\quad$}}tt \displaystyle\mathord{\makebox[0.0pt]{$\hskip 4.30554pt|\quad$}}true\ |\ false\ |\ !e\ |\ ... \displaystyle\mathord{\makebox[0.0pt]{$\hskip 4.30554pt|\quad$}}0\ |\ 1\ |\ 2\ |\ ... \displaystyle\mathord{\makebox[0.0pt]{$\hskip 4.30554pt|\quad$}}NULL \displaystyle\mathord{\makebox[0.0pt]{$\hskip 4.30554pt|\quad$}}e+e\ |\ e=e\ |\ ... (a) GallinaC expressions \displaystyle cmd \displaystyle=\hskip 4.30554pt\mathtt{ret}\ e

Read the complete text