On the algorithmic structure of Dialectica realisers

Davide Barbarossa, Thomas Powell · 2025

Read On the algorithmic structure of Dialectica realisers by Davide Barbarossa, Thomas Powell (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-2501-16208.txt.

Introduction

Davide Barbarossa and Thomas Powell recast a classic proof tool as a programming language. Their paper is from two thousand twenty-five. The tool, due to Godel, pulls concrete programs out of abstract proofs. It is a workhorse of the proof mining field, which extracts useful data from mathematical arguments.

Their version presents the tool as rules in the style of program verification logic. Programs in this view run in two directions at once, forward and backward. That view captures how the extracted programs pass information back through a proof. The authors define a backpropagation-like meaning for a fragment of the language. They intend the frame to support future tools that automate such extraction. Open directions are sketched at the end.

Catalog record

CREATORDavide Barbarossa, Thomas Powell
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE118 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2501-16208

Browse the full library · About the Tower of Babel

Full text

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

On the algorithmic structure of Dialectica realisers Davide Barbarossa, Thomas Powell Abstract Gödel’s Dialectica interpretation is a fundamental tool for the extraction of computational content from proofs, and plays a central role in today’s proof mining program. In the past decades, it has also been studied from the perspective of programming languages, and our contribution is in that direction. Specifically, we present Dialectica as a collection of rules in the style of Hoare logic, where Dialectica is now viewed as a language for specifying procedural programs that come with a forward and backward direction. This viewpoint captures the interesting dynamics of realisers extracted by the Dialectica interpretation, and we illustrate this by defining a generalised backpropagation semantics for a fragment of this language. We envisage this work as providing a base for several future developments, both theoretical and practical, which we outline at the end. Department of Computer Science, University of Bath, UK and https://davidebarbarossa12.github.io/ [email protected]://orcid.org/0000-0003-4608-8282Department of Computer Science, University of Bath, UK and https://t-powell.github.io/ [email protected]://orcid.org/0000-0002-2541-4678 The authors thank Ulrich Berger (who first suggested looking at the frame rule) and Marie Kerjean (who among other things helped clarify several points from [ 16 ] ). ccs Theory of computation Proof theory ccs Theory of computation Constructive mathematics keywords Dialectica interpretation, Hoare logic, Programs from proofs. † † runningauthor: D. Barbarossa and T. Powell † † copyright: Davide Barbarossa and Thomas Powell † † related-version: Full Version : https://arxiv.org/abs/2501.16208 † † funding: This work was funded by the Engineering and Physical Sciences Research Council, grant number EP/W035847/1. † † editors: Stefano Guerrini and Barbara König † † event-title: 34th EACSL Annual Conference on Computer Science Logic (CSL 2026) † † event-shorttitle: CSL 2026 † † event-acronym: CSL † † year: 2026 † † event-date: February 23–28, 2026 † † event-location: Paris, France † † series-volume: 363 † † articleno: 48 1 Introduction Gödel’s Dialectica interpretation [ 12 ] (which we will often refer to as just “Dialectica”) is one of the most important methods for extracting computational content from proofs. Interest in this technique has grown rapidly in recent years, partially due to increased activity in two distinct strands of research. The first is the proof mining program (an overview of which can be found in the monograph [ 18 ] or the survey papers [ 19 , 20 ] ), in which methods from proof theory are applied to obtain both quantitative and qualitative improvements of theorems in mainstream mathematics through the analysis of their proofs. Here, the Dialectica interpretation is used in particular to formulate so-called logical metatheorems, which involve extensions of Dialectica to sophisticated proof systems designed to explain the extractability of quantitative information in a specific setting (see e.g. the classic works [ 17 , 11 ] , or the most recent metatheorem in probability theory [ 26 ] ). The second, somewhat orthogonal strand, is represented by a variety of works that approach Dialectica from a programming or categorical point of view, where the focus is on its structural properties as a logical and program transformation, rather than on its concrete applications to mathematics. A crucial ingredient here is de Paiva’s Dialectica categories and the discovery of the links between Dialectica and linear logic [ 8 ] (recent developments of the categorical viewpoint can be found in e.g. [ 39 ] ). Most relevant to this paper is the recent reformulation of Dialectica as a genuine higher-order functional program transformation [ 33 ] , which also led to the discovery of its links with automatic differentiation and the differential \lambda -calculus [ 16 ] . This paper is a study of the Dialectica interpretation that can be related to both of these perspectives: We consider Dialectica in its traditional form as used in proof mining, but with a focus on the algorithmic structure of the terms it extracts (referred to here as “Dialectica realisers”). More specifically, we give an alternative presentation of the standard Dialectica interpretation, through a set of rules that that manipulate programs rather than logical formulas. The rules are set up in the style of Hoare logic [ 14 ] , and act on what we call Dialectica triples , which are for now just realizing terms for implications between formulas (the characterising feature of Dialectica), but which we later connect with Hoare triples in the usual sense. Our rules formulate the standard soundness theorem for Dialectica by focusing on properties of extracted realizers, and in this way we seek to expose some of the elegant patterns and symmetries that govern programs extracted by the Dialectica. We build on this perspective in two ways. First, we introduce a while loop for Dialectica into our term language, and show that it interprets a corresponding rule. We argue that this can be used to neatly describe iterative programs that arise from nonconstructive proofs in mathematics, where it is connected to the idea of interpreting classical proofs via learning or backtracking , a notion that dates back to Hilbert’s substitution method [ 1 ] . The fact that Dialectica admits a Hoare Logic presentation or, dually, that Hoare logic admits an extension as a logic for Dialectica realisers, raises the question of whether we can understand them from a procedural perspective. We take a first step in this direction in Section 4 , where we consider a restricted set of proof rules whose Dialectica realisers can be regarded as stateful in a suitable sense (though we hesitate to characterise them as truly imperative due to the lack of variable assignment for now, discussed further in Section 5 ). We describe an operational semantics which demonstrates that our programs perform a generalised backpropagation algorithm, comprising a conventional forward part together with a backward pass that computes the reverse witness. Our aim in all of this is to provide a perspective that can be properly developed in future work, and in that spirit, we conclude by discussing several concrete ideas, covering both theory and applications. Our choice of formal system. We will generally privilege a standard presentation of the Dialectica, over more program theoretic ones as found in e.g. [ 33 ] . In particular, we work in a higher-order version of Heyting arithmetic rather than a “modern” type theory. Extensions of the former have proven to be more than capable of capturing the application of Dialectica to a great variety of subsystems of ordinary mathematics: An instructive recent example is probability theory, which a-priori requires strong set-theoretic principles to carry out even the most basic tasks, but which is nevertheless amenable to program extraction via the Dialectica as set out in [ 26 ] and as exemplified by the numerous case studies that have appeared in the last years. It is open whether alternative systems based on e.g. dependent type theory are better suited to the very precise task of capturing applications of Dialectica to tame proofs in ordinary mathematics (see [ 21 ] for a discussion of “proof theoretic tameness” in this context), or can be as easily combined with logical relations such as majorizability [ 15 ] that are essential for capturing uniformities in extracted programs. Finally, even though as shown in [ 33 ]

Read the complete text