CS Paper Radar

Lava: Foundations for Liquid Haskell via Translation to Rocq

Colin Rothgang, Loïc Peyrot, Yannick Forster, Michael Greenberg, Niki Vazou

cs.PL ·submitted 2026-10-08 18:06 UTC · v1

Abstract

Liquid Haskell is an extension of the Glasgow Haskell compiler (GHC) that adds support for refinement types: types restricted by logical predicates. Specifications are automatically checked by an SMT solver, thus offering lightweight verification directly within the language. However, the necessarily large trusted codebase behind Liquid Haskell (from GHC to the SMT solver to the refinement typechecker itself) raises the question of trust in the verification and the necessity for a formalized semantics of Liquid Haskell linked to its implementation. Grounding Liquid Haskell in theory is complicated by the interaction between two semantic levels in the language: a computational one and a logical one (for refinement predicates). While both are well understood separately, their interaction is subtle and has only been partially described. We give a semantics to Liquid Haskell by translation to Rocq. Both the computational and logical parts are translated to the same language, with a well-understood semantics; our translation makes the discrepancy between the two semantic levels explicit. The translation is implemented in Haskell and comes with a Rocq library that includes powerful proof automation standing in for the SMT solver. Thus, on the practical level, our tool Lava serves as a certificate checker for the supported subset of Liquid Haskell.

Comment
46 pages, 15 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A monadic interpreter and type-and-effect checker

cs.PL ·2026-09-07 ·Stefano Raviola, Paola Giannini, Francesco Dagnino
similarity 0.70
Abstract

We present a concrete implementation in Haskell of a monadic framework that includes both a small-step interpreter and a type-and-effect checker for the corresponding language. Our approach separates the language syntax from the semantics of its effects. This design allows the interpreter to remain parametric over the underlying monad, while the static checker approximates effects independently of their concrete implementation. The theoretical foundation of this framework-applied to a call-by-value lambda calculus with generic effects represented by operations that produce monadic values and are managed through handlers-was introduced in previous work, where the focus was on proving the soundness of the approach. In contrast, the present work leverages Haskell's support for modular programming and monads to demonstrate that the framework is practically implementable and usable. We illustrate the approach with examples using the monad of exceptions and the one of nondeterminism and expressions both with and without handlers.

0.10

CIRT: Calculus of Inductive Refinement Types

cs.PL ·2026-11-16 ·Alessio Ferrarini, Niki Vazou, G. A. Kavvos
publishedhot direction similarity 0.69
Abstract · Extended version of the POPL 2027 paper

Refinement types are a powerful mechanism for statically verifying properties of programs. They have been successfully integrated into practical languages such as Haskell, Scala, and Rust. However, their metatheory is not yet fully understood. In this paper we present the first semantic model for a refinement type system that supports the full feature combination of subtyping, SMT-style equality, impredicative polymorphism, and (stratified) inductive types. Interactions between these features have led to inconsistencies in the past, and existing formalizations of refinement type systems omit at least one of them. We present a realizability model based on partial equivalence relations (PERs) over a Scott domain, which overcomes these obstacles. We use our model to prove the consistency of a core refinement type system and to give a semantic account of the annotation-independence property of refinement types. Our semantics uses two interpretations: a refined one, which interprets types and their refinements as PERs; and an unrefined one, consisting of complete uniform PERs with a bottom element (CUPERs), which models computational behaviour independently of refinements. We extend the model to positive and stratified inductive types, showing that both are consistent in the presence of impredicativity.

0.51

SymFC: Configurable Semantics for All Paths Symbolic Execution in Haskell via Embeddings

cs.PL ·2026-11-05 ·Robin Webbers, Wind Wong, Klaus v. Gleissenthall
similarity 0.68
Abstract

Lightweight methods like QuickCheck have proven to be successful in functional languages and beyond, as they let users specify properties as Boolean functions directly in code. We can replicate some of their benefits for (bounded) proofs via symbolic execution. If we can execute arbitrary functions symbolically, we can specify properties just as easily. Unfortunately, existing symbolic execution tools for Haskell are restricted to a subset of the language that excludes many real-world applications like IO; they also have a hard time scaling to larger programs, making them a poor fit for general purpose lightweight verification. One reason behind these limitations is that existing techniques only offer fixed symbolic semantics for SMT base types. This makes it hard to cover more programming constructs and libraries; it also makes it difficult to fine-tune symbolic representations for better performance. We present SymFC, a new symbolic execution method for Haskell that offers configurable semantics via embeddings. An embedding of a function in SymFC is just another Haskell function that can use arbitrary code, as well as SMT primitives. Embeddings make it easy to support new programming constructs and fine-tune symbolic representations for speed. To integrate embeddings into Haskell's type system, we make use of Haskell's coercions, which let us transparently convert between a Haskell type and the type of its embedding. We realize embeddings in SymFC, an all-paths symbolic execution engine for Haskell, which lets us symbolically represent arbitrary types and values in GHC core. We implement SymFC as a GHC plugin, and evaluate it by checking properties of Haskell's container library, and the iproute library. We build embeddings for IORef, Haskell's Ptr/ForeignPtr interface, and the hardware library Clash, and our evaluation reports a 6.25x speedup on G2's own benchmarks.

0.26

C-to-Rust Translation Validation at the LLVM IR Level via AI-Assisted Refinement Proof

cs.PL ·2026-11-13 ·Eunsu Kim, Sukyoung Ryu, Jaemin Hong
benchmarktheory similarity 0.64
Abstract · 26 pages, 10 figures, 3 tables

Migrating C codebases to Rust is a promising approach to securing legacy software, but existing translators do not guarantee that a translated Rust program preserves the behavior of the C program. Neither rule-based nor large language model (LLM)-based translators have been formally verified, and existing approaches to checking translation correctness are limited to testing and bounded checks, which cannot reason about all possible executions. In this work, we present R2C2, which validates C-to-Rust translation by proving in Rocq that the Rust program refines the C program, i.e., every behavior on the Rust side is also a behavior on the C side. Since no formal semantics defines the behaviors of C and Rust programs in the same terms, we prove refinement between the two programs compiled to the LLVM intermediate representation (LLVM IR). In addition, to resolve the discrepancies between the data representations of C and Rust, we introduce a common abstraction that relates two corresponding representations through an abstract value, and specify the behavior of each library function over abstract values. We construct the refinement proof as a chain of refinement relations, where only one relation is program-specific and proved at validation time, while the others are proved for all programs in advance. Proof construction is automated by AI agents, and since Rocq checks the proofs, the agents need not be trusted. We evaluate R2C2 on LLM translations of 519 C programs drawn from a benchmark suite used in prior work on C-to-Rust translation validation. R2C2 proves the translations of 486 programs correct without bounding their executions and discovers three incorrect translations, providing valid counterexamples that existing translation validation tools cannot find. We also conduct a case study on a small real-world image compression library and demonstrate how R2C2 can handle file operations.

0.33

Corten - Foundational Verification of Rust Programs

cs.PL ·2026-09-03 ·František Farka, Carmine Abate, Sven Linker, Sebastian Ertel
theory similarity 0.64
Abstract · 41 pages, 13 figures

We present Corten, a foundational verification framework for Rust programs in the Rocq theorem prover, built on the Iris separation logic framework. Corten provides the first semantics of surface-level Rust mechanized in a proof assistant with an attached program logic, directly grounded in the Rust Reference: it deeply embeds the Typed High-level Intermediate Representation (THIR) into Rocq and formalises Rust's dynamic semantics as a weakest-precondition predicate transformer calculus. By operating at THIR rather than on internal compiler representations, Corten proof goals display the THIR AST, which pretty-prints to surface Rust, keeping verification close to the source code and facilitating maintainability as code evolves. Atop this semantics, Corten develops a program logic and a syntax-directed proof automation layer; the program logic includes defunctionalized continuation stacks that keep proof goals first-order and compact. Soundness is established incrementally, construct by construct, against an interaction-trees denotation. A synthetic test suite demonstrates a two-to-four times reduction in proof size compared to raw semantic proofs. We further showcase Corten on a buddy allocator case study, verifying memory safety of the allocation and deallocation functions, laying the groundwork for end-to-end verification in a shared Rocq semantic foundation spanning hardware-software boundaries.

0.12

Garlene: Guarded Recursion in Lean

cs.LO cs.PL ·2026-09-21 ·Sergei Stepanenko, Patrick Bahr, Rasmus Ejlers Møgelberg
theoryhot direction similarity 0.63
Abstract

Extending the recursion principles of a formal system is an enticing but dangerous endeavour with a well-documented history of leading to consistency bugs. Nakano's guarded recursion is an elegant, type-based approach to soundly extend type theory with a powerful recursion principle. This makes guarded recursion useful for many applications, from programming with infinite structures such as streams to reasoning about advanced programming language features using synthetic guarded domain theory. Sadly, guarded recursion is not directly supported by any major interactive theorem prover, which leaves users of guarded recursion with unmechanised pen-and-paper proofs or mechanisations that depend on unmaintained theorem provers. In this paper, we present an implementation of guarded recursion as an embedded language in Lean consisting of a simply-typed lambda calculus for definitions and a higher-order logic for reasoning. Using Lean's excellent support for metaprogramming, our language allows users to write guarded recursive definitions in an intuitive syntax and to prove properties about them using a dedicated proof mode. We give our language a presheaf model, which we use to prove the soundness of our language and to allow users to export guarded recursive definitions and their theorems into standard Lean developments. To demonstrate the usefulness of our language, we present several case studies for programming and reasoning with guarded recursion.

0.24

More Powerful Constant Value Checking with SMT Solving

cs.PL ·2026-10-04 ·Jonas Mittnacht, Florian Lanzinger
similarity 0.63
Abstract

Pluggable type systems extend the basic type system of a programming language by introducing additional type hierarchies to specify more complex properties and dependencies between variables. We consider the Constant Value Checker, a pluggable type checker for Java implemented using the Checker Framework, which provides various pluggable type systems and corresponding checkers. The Constant Value Checker lets users specify restrictions on the values a primitive integer or boolean variable can hold using a set or range of constant values. However, the current implementation of the Value Checker makes use of a limited set of syntactic typing rules that, in practice, often fail to verify well-typedness of more complex code. In this paper, we introduce an extension to the Checker Framework using Satisfiability Modulo Theories (SMT) solvers to address these limitations by creating corresponding first-order logic formulas for expressions whose type checks fail with the current syntactic typing rules and determining their well-typedness based on the satisfiability of these formulas. Furthermore, we introduce new dependent types for specifying allowed values with expressions that can depend on other variables in the program.

0.22

Statically Typed Purely Functional Definitional Interpreters for {\it Essentials of Programming Languages}

cs.PL ·2026-11-17 ·Kwanghoon Choi
hot direction similarity 0.63
Abstract · The 24th Asian Symposium on Programming Languages and Systems (APLAS 2026)

Definitional interpreters provide an executable and pedagogically effective way to explain programming language semantics. However, when implemented in a dynamically typed and effectful metalanguage, semantic components such as stores, continuations, handlers, substitutions, and scheduling states may remain implicit in the host-language implementation, making it harder to see how language extensions affect interpreter structure. This paper reconstructs the family of interpreters from \textit{Essentials of Programming Languages} (EOPL) in Haskell, a statically typed and purely functional metalanguage, for pedagogical use. We preserve the object languages, examples, and tests of EOPL while making their semantic components explicit through algebraic data types, evaluator signatures, and explicit semantic domains. Across 15 interpreters and 6 type checkers, language extensions are exposed as systematic type-directed changes. The reconstruction is currently used in undergraduate and graduate programming language courses, where students learn interpreter construction through incremental and test-driven development. We further illustrate its pedagogical use through three case studies that progressively extend students' experience: composing mutable state and exception handling, deriving an actor-based interpreter from the typed structure of the EOPL thread interpreter, and translating the CHECKED interpreter and type checker into Rocq to mechanize type safety. Together, the classroom experience and case studies suggest that the reconstruction provides a concrete bridge from learning programming language concepts through executable interpreters to language design and mechanized reasoning.

0.34