跳到正文
研踪PaperTrail

论文库

检索计算机领域论文,按研究方向、作者或关键词筛选。

部分采集异常
正在读取账号与研究记录…

全站更新概况

+479新增论文
+361其中 AI 相关
+64已有论文修订
+95新增 AI 导读

arXiv 最近完成扫描:2026-11-16 01:34 · 全站最近入库:2026-11-16 21:56各信源进度 →

统计口径与数据新鲜度

统计 2026-11-16 01:51 — 2026-11-17 01:51(北京时间) · 点击数字查看对应简报;AI 相关包含在新增论文内。

最近完成检查:2026-11-16 01:34最近发现新增版本:2026-11-16 21:56库内论文最新更新时间:2026-11-14 02:59

每分钟刷新已保存的数据。空检查不代表采集异常;新收录可能包含历史论文。AI 导读按新增版本计数。

23,827 已收录论文19,941 AI 相关6,922 有修订112 HF 社区发现

浏览论文库

时间范围跟随排序:版本更新、本站收录或首次发表。最新收录可能包含历史论文。部分信源异常,查看状态 →

找到 125 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-16 01:33(北京时间)
版本更新 · v3arXiv:2607.11352

Cover Semantics for Intuitionistic Modalities

Nachiappan Valliappan

原文摘要

Intuitionistic modal logic (IML) has inspired several developments in programming languages including modal type systems for staging, computational effects and language-based security. IMLs are typically studied using Kripke-style relational semantics, which simplifies proofs of meta-theoretic properties, such as completeness and consistency, by making it easy to construct models. Kripke-style relational semantics, however, relies upon classical reasoning principles, which makes it unappealing from a computational perspective and unsuitable for formalization in a constructive type theory. Goldblatt provides an alternative semantics for IMLs by extending Beth-Kripke-Joyal-style "cover" semantics for intuitionistic propositional logic with relations to support modalities. Goldblatt's "relational cover" semantics overcomes classical reasoning but introduces a new limitation: it relies upon a "modal localization" condition that restricts the class of models and complicates model construction. Goldblatt bypasses this restriction by using intricate order-theoretic completion arguments to prove completeness. In this article, we present a conservative extension of relational cover semantics that alleviates this restriction and is amenable to simpler and standard model construction techniques. We formalize our semantics in Agda and prove completeness constructively in the style of Normalization by Evaluation for a variety of IMLs featuring independent box and diamond modalities.

cs.LO · cs.PL

新论文 · v1arXiv:2611.02345

MBUndo: Sound, Automatic, and Efficient Measurement-Based Uncomputation for Quantum Circuits

Shengyuan Yang, Charles Yuan

原文摘要

Quantum programs that use temporary values, known as \emph{ancilla} qubits, must explicitly \emph{uncompute} each ancilla back to zero to ensure that the program produces correct outputs. Conventional uncomputation uses unitary quantum gates, whereas leading quantum algorithms now leverage \emph{measurement-based uncomputation} (MBU), which replaces costly unitary $T$ gates with cheaper measurements and phase corrections. Current quantum programming frameworks can use measurement to uncompute specific gates such as Toffoli. No automatic transformation, however, accepts an arbitrary circuit whose ancillas are computed and uncomputed via the standard approach and converts the circuit to use MBU\@. Researchers instead apply MBU to individual circuit designs by hand, which limits algorithm development and compiler optimization. Such a transformation has not existed due to two fundamental unknowns: where MBU applies and which gates realize MBU for an arbitrary computation. To solve these, we first present a static analysis that identifies, for each ancilla qubit, each circuit position where measurement is sound --- subsuming basic assumptions that MBU only applies at the end of a circuit. Next, we present circuit transformations that soundly turn unitary uncomputation gates into efficient phase corrections after measurement --- generalizing rewrite rules from prior literature that are either limited to a single gate or not applicable to a general circuit. We present \textsf{MBUndo}, an integrated compiler pass that automatically converts circuits to measurement-based uncomputation. It requires no user annotations other than which qubits are ancillas, the same as needed by existing uncomputation synthesizers, and can enhance their output circuits. We evaluate \textsf{MBUndo} on 22 benchmarks to reveal \emph{T} gate reductions of ${>}36.5\%$ over uncomputation synthesizers.

cs.PL · quant-ph

版本更新 · v2arXiv:2610.22061

FAOPs: Normal Forms and an Algebra for AI Agent Workflows

Ali Mohammadi Shanghooshabad

原文摘要

Organizations increasingly encode operational procedures as multi-step agent skills, here called Agent Operating Procedures (AOPs), that must be traceable, auditable, reproducible, access-controlled, and bounded in time and cost, as regulated sectors require. Yet AOPs are typically kept as coarse-grained files, in which steps bundle actions, copied procedures drift apart, any step may reach any tool, and refactoring goes unchecked. We present Functional Agent Operating Procedures (FAOP), a formal theory that brings database-grade discipline to AI agent workflows. FAOP recasts each workflow as a typed function over scoped state and subjects an entire library to four progressive normal forms: Decomposed (FNF-1) splits a workflow into atomic steps, Typed (FNF-2) makes its data flow explicit and type-checked, Factored (FNF-3) gives each shared sub-workflow a single canonical definition so a change propagates instead of drifting, and Scoped (FNF-4) checks that each FAOP lists resources used by its own actions and the FAOPs it calls, while guardrails declared by it and by FAOPs that call it remain attached to their sources. A FAOP algebra of provably sound equalities turns refactoring and parallelization into compiler rewrites; orthogonal extensions add optimization (+O), bounded completion with time and cost limits (+B), and reachability checks (+R); and an architectural-level classifier (0-3) determines whether a workflow needs AI at all. Together, these make integrity, isolation, typing, stopping limits, cost, and optimization compile-time concerns across the whole library, not runtime hopes. We implement the theory in SkillBase, an AOP management system (what PostgreSQL is to data, SkillBase is to AOPs), and a separate executor that loads FAOPs from SkillBase and enforces these guarantees at run time. A worked financial workflow illustrates the approach end to end.

cs.AI · cs.DB · cs.PL

版本更新 · v2arXiv:2605.16897

Beyond Callbacks: A Developer-friendly Programming Paradigm for Network Simulation

Yuanyi Zhu, Zijian Li, Xin Ai, Zixuan Chen, Sen Liu, Yang Xu

原文摘要

Network simulation plays a crucial role in both networking research and industry. Existing commonly-used Discrete Event Simulations (DES) are based on the callback mechanism for discrete events. However, as network functions grow in complexity, callbacks reveal a fundamental structural limitation: a callback can only represent a single point in a blocking operation and cannot capture the full operation as a coherent whole. This forces developers to manually decompose sequential network logic into scattered callback fragments, leading to stack ripping, callback hell, and heavy development and debugging burdens. We propose CoDES (\textbf{Co}routine-based \textbf{DES}), a coroutine-based programming paradigm for network simulation that addresses this structural limitation. CoDES targets development productivity rather than execution performance. Realizing CoDES in existing DES simulators is non-trivial, as coroutine suspension must be coordinated with the event scheduler, introducing challenges in coroutine resource conflicts, operation-level computation requirements, compatibility with existing callback-based simulators, and overhead. We implement a CoDES-based framework in ns-3, address all four challenges, and release it as open source. We evaluate CoDES by implementing Message Passing Interface (MPI), High Precision Congestion Control (HPCC), and Routing Information Protocol (RIP) in ns-3, spanning the transport, congestion control, and routing layers. Compared with callback-based counterparts, CoDES reduces lines of code by up to 51.4% and nesting depth by up to 50%, with no accuracy loss and negligible runtime and memory overhead.

cs.NI · cs.PL

版本更新 · v2arXiv:2610.30168

Finitely Verifiable Segmentation: Decidability for Every Tokenizer with a Finite-State Verifier

Nicklas Nidhögg

原文摘要

A segmentation policy assigns to each byte string at most one segmentation into tokens. Call it finitely verifiable when a finite automaton over marked strings, bytes paired with boundary bits, accepts exactly the policy's own segmentations. The automaton judges a proposed segmentation and need not compute one. From a supplied verifier the paper gives constructive decisions for four questions, whether a window certifies a token boundary, whether the boundary gap is bounded, whether a mask can keep generation from dead-ending, and whether two policies are equivalent. The last three specialize limitedness, co-accessibility and the equivalence of single-valued transducers. The first refines the synchronizing cut of code theory, and two more ask whether a certified cut, or the cuts of an inventory, let each piece scan alone. The class sits strictly between the online-scannable policies and those with regular domains, and online scannability is decidable in polynomial time through Choffrut's theorem. Markings are length-preserving, so the class is exactly the rational segmentation policies, a normal form rather than a restriction. The class is closed under four pipeline operations, composition over a labeled stage, restriction to a regular schema, splitting at character-class changes, and byte-fallback union of literal policies. Each composite inherits the six decisions, and certificates transfer between stages under four laws. Under rational, unifilar, almost surely stopping finite-state sources, each mass of the weighted section is an exact rational, and so is each rate where expected length is positive. Maximal-munch lexing, canonical byte-pair encoding and two-mode WordPiece instantiate the interface, and the munch library implements all six decisions. Every theorem carries an executable check, and every reported statistic is a program's own output.

cs.FL · cs.CL · cs.PL

版本更新 · v2arXiv:2610.08854

Certified Splitting: Decidability and Anchor Supply for Maximal-Munch Tokenization

Nicklas Nidhögg

原文摘要

A certificate is a window of bytes with an origin inside it such that, wherever the window occurs in a completely tokenizable input, the token covering the window's final byte begins at that origin. Certification is decided from the token set alone, and a certificate's occurrences mark where work may soundly begin. This paper decides certification and applies it to cuts, edits and audits. It is decided two ways, online with a completeness cutoff for literal vocabularies and offline through an armed-run verifier for arbitrary regular token sets. Either route, under a declared window budget, yields the anchor inventory, with a counterexample on each refutation. Cutting a completely tokenizable input at certified anchors and scanning the chunks independently reproduces the sequential segmentation, with no speculation or fixup pass. A tokenizability-preserving byte substitution moves boundaries only strictly between the certified anchors witnessed in the unchanged bytes on either side of it. For tokens of length at most L, an edit at p moves no boundary at or below p - L + 1. Cutting at every occurrence of a delimiter is sound exactly when it occurs only at token starts, and cutting after every occurrence exactly when it occurs only at token ends. Two instruments follow. The anchor-free span of a finite certified inventory is decided bounded or not with its exact supremum, three for the UTF-8 shape; and a differential auditor decides whether two token sets place different boundaries on an input both tokenize, with a differing input. Every theorem carries an executable check. Every measurement is a named program's output or arithmetic on such outputs, and each program ships with the paper or is pinned by commit in the munch library. That library's threaded scanner splits the archived campaign corpus at certified anchors and reproduces the sequential boundary stream byte for byte.

cs.FL · cs.DC · cs.PL

新论文 · v1arXiv:2611.01414

Extensible Programmatic Specification of Finite Element Methods

Theadora Fields Collin, Oded Stein, Gilbert Bernstein, Saman Amarasinghe

原文摘要

Finite element methods (FEMs) are a powerful and ubiquitous tool for solving engineering problems. Experimenting with different finite elements can improve the quality and efficiency of solutions. In some cases, the wrong (but nonetheless most common) choice of finite element will produce solutions which converge to the wrong answer regardless of mesh resolution. However, in practice, the choice of finite element is not explored due to the complexity of re-deriving and re-implementing finite element methods. Trying a new finite element is challenging because practitioners must manually deduce formulas to use these elements and implement them within a potentially complex system. We address this problem by introducing ElementForge, a finite element system that is parametric over the literate mathematical specification of a finite element in a domain-specific language (DSL). The ElementForge compiler reasons about tensor spaces, tensors, and tensor bases from first principles to derive implementations of finite elements. The ElementForge compiler is able to automatically derive implementations of finite elements previously only derived by hand. Further, ElementForge minimally couples several key mathematical concepts, mainly tensor fields, mesh topologies, sparse tensors, and assembled finite element operators, to produce a complete finite element system that is parametric over the choice of element. Consequently, the elements derived by the compiler can be applied parametrically to new meshes, PDEs, and boundary conditions. We evaluate our system by implementing several simulations with different finite elements, demonstrating that our system can explore tradeoffs in generality, accuracy, speed, and representational complexity. For example, we are able to implement the Morley, Bell, Argyris, and Hermite like elements with less than 50 lines of code and use them all in a single simulation.

cs.MS · cs.GR · cs.PL

新论文 · v1arXiv:2611.01358

WFDB-x: Conformance-Tested Implementations of the WFDB Software Package in Seven Programming Languages

Reza Sameni

原文摘要

The WFDB format is widely used to store and exchange physiological waveforms and annotations. However, existing software implementations are limited to C, Python, and MATLAB/Octave, can produce different results in corner cases and checksum calculations, and have defaults such as sampling frequency and gain, that can lead to silent misinterpretation of recordings. We developed WFDB-x, a cross-language, performance-optimized reimplementation of WFDB in seven programming languages, with extensive unit tests, to provide consistent WFDB processing across programming languages. We reimplemented the WFDB Software Package 10.7.0 natively in Python, C++, Rust, Julia, R, MATLAB/Octave, and Kotlin, using AI-assistance under human direction and review. Each implementation has library functions, a high-level interface, and command-line tools. We compared their outputs with those of the original C programs using 1098 conformance cases, 877 legacy-mode cases, unit tests, and differential fuzzing. Deliberate changes remove implicit waveform parameters, restrict file and network access, and prevent annotation loss. A legacy mode retains the original behavior. All seven implementations passed every conformance and legacy-mode case on the tested Linux platform, with matching outputs. The unit tests contain 9353 assertions. C++, Rust, and Julia read records 1.5-6.9 times faster than the original C library, while the Python implementation wrote records 9.2 times faster than the existing wfdb-python library in the benchmark. WFDB-x provides a tested, open-source basis for reading and writing physiological recordings consistently across seven languages, supporting reproducible research and software development without requiring a shared programming environment. We also share details of the AI-assisted development process and token utilization, which may be useful for other applications.

cs.SE · cs.DL · cs.PL

新论文 · v1arXiv:2610.40538

crush:面向 Lean 的可扩展证明自动化

crush: Extensible Proof Automation for Lean

Mike He, Dexin Zhang, Aarti Gupta

AI 速读 基于摘要

提出一个基于 SMT 的可扩展 Lean 证明自动化框架 crush,用去函数化桥接高阶构造与一阶求解器,并支持可扩展的翻译与证明重建。

cs.LO · cs.PL

查看原文摘要

Lean's rich expressiveness supports higher-order functions, inductive datatypes, and user-defined abstractions, making it challenging to translate proof obligations into first-order Satisfiability Modulo Theory (SMT) queries and reconstruct kernel checked proofs. We present crush, an extensible SMT-backed proof automation framework for Lean. To bridge the gap between Lean's higher-order constructs and the solver's first-order logic, crush uses defunctionalization to encode function values and their applications. We formalize this translation for a supported higher-order fragment and prove its soundness. Moreover, crush provides metaprogramming interfaces for extending both Lean-to-SMT translation and the reconstruction of Lean proofs from solver certificates without modifying the translation pipeline. We implement crush as both a tactic and a backend for other third-party automation systems. We show that across four such use cases that target verification and general proof automation, crush discharges more obligations than the competing backends and reconstructs more kernel-checked proofs than the baselines.

新论文 · v1arXiv:2610.39723

Countable Nondeterminism in Weighted Programming with an Application to Mechanized Foundations for Probabilistic Program Verification

Sebastian Körner, Oliver Emil Bøving, Christoph Matheja

原文摘要

Weighted programming is a framework by Batz et al. for describing mathematical models or optimization problems as imperative programs parametrized over semirings and then analyzing them with program verification techniques like weakest precondition calculi. Applications include reasoning about expected outcomes of probabilistic programs and competitive analysis of online algorithms. We extend weighted programming with (1) countable nondeterminism and (2) user-defined additive rewards, where programs are parametrized over modules instead of semirings. The resulting framework enables reasoning about expected resource consumption of probabilistic programs and about optimal scores of combinatorial games. A technical challenge is that wp-calculi for weighted programs with (1) and (2) over arbitrary modules can be unsound, because it is well-known that continuity properties commonly used in program semantics break in the presence of countable nondeterminism. We study conditions under which a wp-style transformer for reasoning about weighted programs is sound with respect to an operational ground truth defined in terms of weighted decision processes (WDPs) - transition systems that generalize Markov decision processes by drawing transition weights and state rewards from a module. Based on those conditions, we show that a range of concrete instances of the weighted programming framework enjoy sound weakest precondition reasoning. We demonstrate the usefulness of our wp-semantics through case studies for different modules. We mechanized our extended weighted programming framework and our main soundness results in the interactive theorem prover Lean. Instantiating these results for probabilistic programming yields, to the best of our knowledge, the first mechanized proof of a fixed point characterization of minimal expected rewards in Markov decision processes with countable nondeterminism.

cs.PL · cs.LO

新论文 · v1arXiv:2610.39491

Automated Verification of Hamiltonian Simulation by Quantum Signal Processing

Min Lai, Yu-Fang Chen, Shih-Han Hung

原文摘要

We present, to the best of our knowledge, the first fully automated verification framework for QSP-based Hamiltonian simulation. Our framework exploits the structure of the simulation algorithm: Hamiltonians are given as weighted sums of Pauli strings, embedded into larger unitaries through block encodings, and transformed into time-evolution operators by quantum signal processing (QSP). Using a symbolic Pauli-sum semantics for ancilla-indexed circuit blocks, our verifier proves that the distinguished all-zero ancilla block is proportional to the target Hamiltonian and infers the subnormalization factor automatically. It then verifies the QSP layer by extracting the implemented polynomial transformation and certifying its approximation error. This structure-aware abstraction is essential for scalability. Composing our verified block encoding and QSP wrapper yields an estimated macro-expanded size of about 1.52 million gates. The verifier certifies the block encoding once and checks the QSP layer through its abstract interface, without expanding the oracle calls. Our implementation verifies block encodings of structured Pauli-sum Hamiltonians with up to 256 system qubits and verifies QSP Hamiltonian-simulation instances by extracting their implemented polynomials and checking the resulting approximation bounds. These results show that fully automated verification can handle common Hamiltonian-simulation circuits at substantial scale when it exploits their algorithmic structure.

cs.PL · cs.LO · quant-ph

新论文 · v1arXiv:2610.39374

DualGuard: Comprehensive and Efficient Memory Safety across Sequential and Speculative Execution

Sixuan Dang, Quan Zhou, Kaiming Huang, Jianan Zhu, Anitha Gollamudi, Trent Jaeger, Danfeng Zhang

原文摘要

Although decades of research have yielded sophisticated mechanisms for enforcing memory safety, speculative execution can subvert these protections through transient memory operations. Conversely, defenses designed specifically for speculative safety, such as Speculative Load Hardening (SLH), cannot enforce memory safety during non-speculative execution. A naive combination of defenses from both domains raises two fundamental challenges: (1) which combination of otherwise fragmented defenses can ensure dual memory safety under speculative and non-speculative executions? (2) whether such combinations introduce redundant protections that incur unnecessary performance overhead? We present DualGuard, a unified framework for dual memory protection under non-speculative and speculative executions. DualGuard systematically analyzes memory behaviors, classifying them into four categories, and further identifies the minimal composition requirements for dual memory safety, which allow us to strategically combine existing mitigations and design new ones to avoid redundant or excessive protections. We implement DualGuard through a combination of static analysis and runtime enforcement within the LLVM infrastructure. Our evaluation demonstrates that DualGuard reduces overhead by 3%-72% compared to naive compositions of fragmented defenses. In some cases, it even incurs lower overhead than approaches that guarantee memory safety solely under either non-speculative or speculative execution.

cs.CR · cs.PL

新论文 · v1arXiv:2610.38682

Write Once, Instrument Anywhere: Portable, Sandboxed Tooling with WebAssembly Components

Elizabeth Gilbert, Chris Fallin, Heather Miller, Ben L. Titzer

原文摘要

Monitoring and debugging deployed software is crucial for scalability, performance, and robustness. Cross-cutting concerns are pervasive across software ecosystems, yet engineers must address them with a fragmented toolbox. While high-level frameworks exist to offer application-level types and semantics, they often lock a solution into specific languages, runtimes, or hardware architectures. Portability often forces engineers to choose lower-level instrumentation mechanisms. For example, in-language frameworks can trace a request across processes, but multi-language contexts require instrumentation at the boundary, for example using eBPF. While these frameworks provide powerful capabilities, they often result in 1) a tradeoff between application-level types or low-level bytes and packets, 2) non-composable domain-specific tools, 3) feature fragmentation across frameworks, and 4) tools that often run with unrestricted access to the program and its environment. We address these problems with Splicer, a WebAssembly component interposition framework that 1) provides semantically rich application-level types, 2) enables pluggable tooling with powerful capabilities, 3) reduces ecosystem fragmentation through porting across languages and hardware, and 4) confines each tool to a sandbox with explicitly granted permissions. We evaluate Splicer on a suite of benchmarks demonstrating the pluggability of non-trivial tooling written in multiple source languages and their performance.

cs.SE · cs.PL

新论文 · v1arXiv:2610.38329

A Case Study of a Multi-Agent Kernel-Optimization Loop That Learns a New AI Accelerator

Byonggon Chun

原文摘要

Frontier large language models write correct CUDA kernels for most single-operator benchmark tasks, yet their accuracy collapses on accelerators whose architecture and programming language they have rarely seen. We present a case study of an LLM agent loop built for such accelerators. Our example is the FuriosaAI RNGD NPU, programmed in a recent, sparsely documented Rust DSL, where the loop optimized three Gemma-4-12B decode kernels over 12 days on a shared, scarce device. The loop builds its own target knowledge: it writes and checks a summary of the DSL documentation, measures the chip with microbenchmarks, records compiler-derived legality rules, and revisits this knowledge when the toolchain changes, rechecking rules and measurements where it can. A role-based search over per-kernel Design Trees explores whole-kernel designs and accumulates small accepted changes in the best version of each kernel. Because device time is scarce and readings are noisy, cheap checks screen new designs before any device run, and late in the run a change was accepted only after repeated comparisons with the best kernel on the device. The final kernels reach a 9.293x geomean speedup over the official baseline, each within 1.25x of the cycles needed just to move its weights. Our prompts, profiler and acceptance test are available at https://github.com/bgchun-fs/multi-agent-kernel-gen-loop.

cs.LG · cs.AI · cs.AR · cs.PL

新论文 · v1arXiv:2610.37244

Preserving Separation Logic Specifications through Compilation

Carmine Abate, Kleio Liotati, František Farka, Sebastian Ertel

原文摘要

Program specifications in separation logic describe ownership of resources and serve as logical interfaces for local reasoning. Compiler correctness, expressed as semantics preservation, does not by itself supply such an interface for compiled code, because it does not explicitly relate source and target resources and assertions. We investigate WP-preserving compilation: when a compiler translates a source program, the weakest preconditions that the program satisfies in a separation logic carry over to the compiled program. Our proof technique consists of a resource-aware simulation over interaction trees: it relates the resources required by corresponding source and target events, and tracks ownership through target operations, such as register accesses, that have no source counterpart. We apply the approach to a compiler from a structured imperative language to an assembly-like language, first for closed programs and then extended with modules and function calls. In the extended setting, each module can be verified in the source logic and compiled separately; its specifications carry over to the compiled module and are preserved when compiled modules are linked. All results are mechanized in Rocq.

cs.PL

新论文 · v1arXiv:2610.37006

Abstract Lipschitz Continuity

Marco Campion, Isabella Mastroeni, Michele Pasqua, Caterina Urban

原文摘要

We introduce Abstract Lipschitz Continuity (ALC), an extensional property of functions, in particular of program semantics, requiring that bounded differences between properties of two inputs yield proportionally bounded differences between properties of the corresponding outputs. ALC explicitly discerns between two complementary forms of approximation: property-based (or qualitative) approximations, which retain a property of the data and are formalized by upper closure operators as in abstract interpretation, and quantitative approximations, which measure the closeness of data and are formalized by pre-metrics, a weakening of metrics that covers the distances arising in program analysis. Keeping the two forms of approximation explicit has two main benefits. First, it allows us to precisely relate ALC to established extensional properties: ALC is a sufficient condition for partial completeness in abstract interpretation, for partial abstract non-interference in language-based security and, with a null Lipschitz constant, for abstract robustness in machine learning. Second, it supports reasoning about ALC of program semantics by induction on the syntax of programs: we present a sound deductive system, parametric in the property-based approximations and in the pre-metric of interest, that reduces a proof of ALC for a program to proofs for its basic commands and to some explicit side conditions, which isolate what makes ALC compositional across sequential composition, non-deterministic choice and iteration.

cs.PL

新论文 · v1arXiv:2610.36798

Polymorphic First-Class Environments

Jinhao Tan, Jam Kabeer Ali Khan, Bruno C. d. S. Oliveira

原文摘要

First-class environments expose runtime environments as ordinary values and support a substitution-free, environment-based operational semantics. They also support applications such as first-class modules, dynamic composition of environment fragments, and sandboxing via local environments. Existing environment-based calculi, however, are mostly studied in a simply typed setting and stop short of System F and polymorphism. We present $F_E$, a polymorphic calculus with first-class environments that conservatively extends System F with a small-step environment semantics. $F_E$ eliminates all forms of substitution in System F. Term and type abstractions evaluate to closures, boxes run code under local environments, and box types expose the local typing assumptions of both. Manifest types, together with a two-sided type equivalence, play a dual role: they model type-level instantiation, and enable transparent type components in environments and modules. We prove type soundness, normalization, decidability, and standard properties of type equivalence, and conservativity over System F. The metatheory of $F_E$ is based on instantiation lemmas rather than substitution lemmas. This foundation supports polymorphic first-class modules with dynamic composition and sandboxing. We study $F_E$ in two forms. Our main presentation is an explicit, type-passing calculus that follows conventional System F. We also develop an implicitly-typed variant aligned with the semantics of polymorphic functional languages. All metatheory is mechanized in the Rocq theorem prover.

cs.PL

新论文 · v1arXiv:2610.36669

Proof Repair and (Co)algebra Equivalences

E. G Plante, Eric Paul, Cosmo Viola, G. A. Kavvos, Talia Ringer

原文摘要

Maintaining formal proofs in response to breaking changes in their dependencies is a major challenge of proof engineering. Proof repair is a kind of proof automation that lessens the burden of this challenge by automatically adapting proofs in response to those changes. While proof repair is well understood through an algorithmic lens, it has, until now, been poorly understood through a theoretical lens. We address this gap by giving the first foundational treatment of proof repair, focusing in particular on type-theoretic proof repair in response to changes in datatypes. Our key insight is that the core component of a proof repair algorithm---a ``configuration''---is exactly an algebra isomorphism. We formalize and prove this insight, answering open questions from prior work. We then take this one step further and show that, by taking the dual of this representation, we obtain proof repair over coinductive types. All of our results are formalized in Agda.

cs.PL

版本更新 · v2arXiv:2610.26599

A Type System for Communication-Safe Hardware Design

Aditya Ranjan Jha, Jason Zhijingcheng Yu, Umang Mathur, Prateek Saxena

原文摘要

Hardware components communicate through clock-cycle-sensitive protocols. Hardware Description Languages (HDLs), however, provide limited support for expressing these protocols or for checking that independently developed components agree on them. When components disagree, the composed design can perform unsynchronized exchanges or stop making progress. We call these failures communication-safety violations. Communication safety is thus a global property, determined by interactions between components. This makes it difficult to check modularly. This paper presents Pact, a typed extension of Anvil for modular verification of communication safety in synchronous hardware. Pact types describe message-passing, control-flow, and clock-cycle behaviour. Each component is checked against its type. Compatible types guarantee that the components compose into a communication-safe system. Pact also supports incremental design. It can check a subsystem before the rest of the system exists. The check produces a summary type that captures the communication behaviour left for future compositions. To reduce annotation burden, Pact infers types by abstracting payload values while preserving communication, timing, control, and fairness. These inferred types are optimal for the checker: whenever some checker-accepted types can prove compatibility, the inferred types can prove it as well. Type inference and type checking are decidable, and compatibility is decided by a sound and complete algorithm. We implement Pact by extending the Anvil compiler and evaluate it along five dimensions: detecting communication errors in incremental design, expressiveness on ten clock-cycle-accurate translations of open-source hardware IPs, compatibility-checking time, generated hardware overhead, and annotation burden. Pact expresses realistic protocols and verifies all ten benchmarks in reasonable time.

cs.PL · cs.AR · cs.LO

新论文 · v1arXiv:2610.36499

ProCerDCL: Query-Efficient Black-Box Probabilistic Verification of Deep Learning Compiler Optimization

Zexin Li, Weibo Zhang, Linyi Li, Arvind Easwaran, Simin Chen

原文摘要

We present \tool, a query-efficient framework for black-box probabilistic verification. Given a fixed, sampleable input distribution and a binary property oracle, \tool assesses the property's violation probability $p$ against a threshold $θ$. Under independent sampling and stateless oracle behavior, acceptance asserts $p\leθ$, rejection asserts $p>θ+η$ for a user-specified separation margin, and an inconclusive verdict indicates insufficient evidence for either conclusion. The probability of each type of erroneous verdict is bounded by its specified error budget. To support this three-valued contract efficiently, \tool uses a single sequential test, eliminating the interval family required by the baseline. The test accounts for repeated sampling checks through either corrected exact binomial confidence intervals or an anytime-valid confidence sequence. We apply \tool to probabilistic local model semantic consistency, where the property oracle detects decision-level inconsistencies between reference and compiled executions under a specified perturbation distribution. Our evaluation covers 24 tasks across TorchInductor and TensorRT and examines sampling efficiency, conclusiveness, and diagnostic behavior. For sampling efficiency, we use paired one-model clean-label radius searches: the baseline requires 3.6-4.2 times as many unique samples under matched numerical parameters while providing a weaker decision contract. For model semantic consistency, checks at $θ=10^{-3}$ yield 817 acceptances, 19 inconclusive verdicts, and 4 rejections across 840 input--backend instances from 21 tasks. Case studies of two documented compiler faults further demonstrate what these local verdicts can diagnose.

cs.SE · cs.AI · cs.PL

新论文 · v1arXiv:2610.36341

Executable Archaeology of Programs That Model Programming: Reanimating the Heuristic Compiler (1961) and KBEmacs (1984)

Jeff Shrager, Kent M. Pitman, Mia Golec

原文摘要

Early AI programs were often also theories of how people think, and programs that wrote programs were, in part, theories of how people program. Here we report on the reanimation of two such programs that offer two seemingly different theories of programming and were developed for quite different purposes. The first, Herbert Simon's Heuristic Compiler (1961), was an experimental model of programming as problem-solving, applying the means-ends analysis methods of the General Problem Solver to investigate the nature of the programming task. The second, KBEmacs (1984), was a working prototype of an intelligent programming assistant developed by MIT's Programmer's Apprentice project, built on the view that expert programmers recognize and combine familiar patterns, or "cliches." It let a programmer build up programs by combining cliches through a stylized English command language. We approach both through the methodology of Executable Archaeology, the study of historical computational systems by running their original code, a process we call "reanimation." Our reanimation of the Heuristic Compiler reproduces the compiled code appearing in Simon's 1963 paper, and our reanimation of KBEmacs reproduces the SQRT sequence of its December 1984 self-test. Examined side by side, the two theories turn out to have much in common: the Heuristic Compiler also works by adapting existing routines, and Simon later argued that search alone requires a large body of programming knowledge. To highlight the reflexivity of this project, we deliberately used a modern AI-assisted programming tool, Anthropic's Claude Code (Opus 5.5), to carry out much of the detailed reanimation work, building on a significant base of existing software. The explicit, executable theories of programming that both systems embodied are largely absent from today's far more capable AI coding assistants.

cs.AI · cs.HC · cs.PL

版本更新 · v3arXiv:2609.10600

Certified Panic Mode: Repair-Invariant Error Recovery for Maximal-Munch Lexing

Nicklas Nidhögg

原文摘要

Classical panic-mode recovery skips a failed scan forward by convention, promising progress but no repair-universal boundary guarantee for where it lands. We choose the resume position by theorem, via a committed-prefix lemma over certificates posted for parallel lexing (arXiv:2608.03473, arXiv:2608.09761): a position is a sound recovery point when every prefix repair whose scan commits through the certificate's returned evidence places a token boundary there. This quantifier is strictly stronger than its complete-repair special case, and at a sound recovery point the inclusion is strict precisely when no repair completes while some scan commits through the evidence. The evidence-returning interface pairs each answer with the interval it rests on, so a caller who knows what the scanner cannot check decides whether the boundary transfers to the intended input. The search provably terminates; the guarantee is relative to the active mode's automaton. For an automaton of n states the quantifier is decided exactly from the preserved tail by at most n + 1 representative repairs, and a shortest reaching repair has at most n - 1 symbols and a shortest counterrepair at most n, both tight. Every anchor of an m-byte input is profiled in $O(nm + n|Σ|)$ time. The shipped repair routines are the complete-repair case, which proves their contracts. In a deterministic corruption study of munch's procedure beside skip-one and delimiter recovery, every certified answer whose evidence survives the damage passes its landing check on every move, 40,885 of 40,885, while the 5,595 first answers resting on evidence the damage reached land 1,589 times, reported, not asserted. Of the 16,808 trials labeled beyond repair, 13,522 resume on a suffix that tokenizes whole, where both quantifiers are provably empty, and 3,286 stay undetermined, their damaged inputs not archived.

cs.PL

新论文 · v1arXiv:2610.36288

BUSTA: Teaching Small Language Models to Reason About Binary Execution

Ritika Poddar, Aidan Fennelly, Deirdre Murphy, Eric Wolos, Corre L. Steele, Michael Doyle

原文摘要

Large Language Models (LLM) are increasingly applied to Reverse Engineering (RE) workflows. RE, however, differs from common LLM coding tasks as it requires models to reason about low-level program behavior. Furthermore, the deployment of tooling in resource-constrained sandboxed RE environments limits the ability to use frontier-scale solutions. We examine whether a targeted LLM training approach can transfer distinct RE skills to open models via inverse basic-block execution: given an x86-64 basic block and a desired output register state, the model predicts the input register values that produce it. Fine-tuning \texttt{Qwen3-1.7B} and \texttt{Nemotron-3-Nano} with Group Relative Policy Optimization (GRPO) raises knowable-register prediction accuracy from 73.2\% to 85.3\% and from 63.3\% to 95.2\%, respectively. Frontier models still score highest (up to 99.2\%), but our fine-tuned \texttt{Nemotron-3-Nano} comes within four points at a fraction of the parameter count. We release both fine-tuned models and the training dataset.

cs.CR · cs.AI · cs.LG · cs.PL

新论文 · v1arXiv:2610.36105

AGDecode: Semantic Attribute Grammar Derivatives for Safety-Constrained Decoding of Large Language Models

Rajan Maghera, Asher Tempest Arya, Aren A. Babikian, Marsha Chechik, Maryam Mehri Dehnavi

原文摘要

Large language models (LLMs) are increasingly used for code generation, motivating techniques that guarantee the structural and semantic correctness of generated programs. Constrained decoding enforces correctness during generation by restricting token choices to those that admit at least one valid completion. While existing approaches can enforce syntactic constraints and selected semantic properties such as type safety, they either target specific properties or rely on operational pruning mechanisms that are difficult to generalize to data-dependent, inductive program properties. We present AGDecode, a programmable framework for semantic constrained decoding based on least-fixed-point semantics. AGDecode extends attribute grammars to partially constructed syntax trees, and reduces semantic constrained decoding to a realizability problem over such trees. The framework compiles semantic specifications into systems of relational constraints that are discharged by external verification oracles, such as SMT and CHC solvers, cleanly separating language semantics from constraint-solving machinery. We prove that our approach is sound and complete relative to an ideal verification oracle. In practice, solvers inevitably encounter uncertain queries; conservatively, our system can reject tokens for soundness or speculatively continue to generate until later queries resolve the entire generation. We mechanize the core metatheory in Rocq and evaluate the framework on semantic-constrained generation of C programs, enforcing path-sensitive safety properties including null-pointer safety, division-by-zero freedom, and initialized-variable usage. Our results demonstrate that solver-backed semantic constrained decoding can enforce rich semantic guarantees while incurring modest computational overhead at regular program boundaries.

cs.SE · cs.PL

版本更新 · v3arXiv:2601.01638

Interaction Improvement

Adrienne Lancelot, Giulio Manzonetto, Guy McCusker, Gabriele Vanoni

原文摘要

The relational semantics of linear logic is a powerful framework for defining resource-aware models of the $λ$-calculus. However, its quantitative aspects are not reflected in the preorders and equational theories induced by these models. Indeed, they can be characterized in terms of (in)equalities between Böhm trees up to extensionality, which are qualitative in nature. We employ the recently introduced checkers calculus to define a quantitative contextual preorder on $λ$-terms, and demonstrate that it coincides with the preorder associated to the relational semantics.

cs.LO · cs.PL

新论文 · v1arXiv:2610.35999

safeL4: Rethinking Safe-Language-Based Single Address Space Microkernels

Zheyuan Xu, Xiaobei Zhang, Zihan Li, Zekai Nie, Guangtao Zhu, Zhuang Lu, Qianying Zhang, Shijun Zhao 等 10 位作者

原文摘要

Microkernels provide good features such as high security, safety, and flexibility, but their reliance on hardware-based isolation leads to heavy performance overhead, limiting their widespread adoption. Although constructing single-address-space microkernels based on safe language-based isolation is a promising approach to addressing the performance issue, this approach still faces challenges in maintaining the principle of minimality and enforcing capability-based, fine-grained access control over system resources. We propose safeL4, an approach to constructing microkernels based on safe languages. It guarantees minimality through low-level abstractions for unsafe operations, and implements a capability system based on the safe language's object capabilities to achieve fine-grained access control over all operations on system resources. We implement a prototype system in Rust, and our evaluation results show that the primitives provided by safeL4 are, on average, 1.9$\times$ faster than those of seL4.

cs.OS · cs.CR · cs.PL

版本更新 · v2arXiv:2610.32925

On the Expressive Power of Hook-Indexed State: Comprehending State in the React UI Library (Extended Version)

Toby Ueno, Ezra Cooper, Simon Fowler, Sam Lindley

原文摘要

React is currently the most popular JavaScript library for front-end web development. It endows UI components with state via the useState construct, through a mechanism that we name hook-indexed state. However, React's implementation of hook-indexed state is both fragile and poorly understood. Programmers frequently experience unexpected behavior, and the benefits of programming in this paradigm are wholly unclear. We define $λ^\mathsf{react}_\mathsf{hook}$, a core calculus that captures the essence of hook-indexed state, and give it a type system to statically rule out unexpected behavior. We then translate $λ^\mathsf{react}_\mathsf{hook}$ into a calculus $λ^\mathsf{react}_\mathsf{ref}$ based on ML-style references, and prove that this translation preserves typability and semantics, thus showing that hook-indexed state is expressible in terms of standard references. The translation is local and admits a compositional definition, but involves significant code duplication. As well as illuminating the essence of state in React, our observations can inform the design of future reactive programming systems.

cs.PL

版本更新 · v2arXiv:2604.22361

Ownership Refinement Types for Pointer Arithmetic and Nested Arrays

Yusuke Fujiwara, Yusuke Matsushita, Kohei Suenaga, Atsushi Igarashi

原文摘要

Tanaka et al. proposed a type system for verifying functional correctness properties of programs that use arrays and pointer arithmetic. Their system extends ConSORT--a type system combining fractional ownership and refinement types for imperative program verification--with support for pointer arithmetic. Their idea was to extend fractional ownership so that it can depend on an array index. Their formulation, however, does not handle nested arrays, which are essential for representing practical data structures such as matrices. We extend Tanaka et al.'s type system to support nested arrays by allowing ownership to depend on the indices of enclosing arrays. We formalize the extended calculus in Rocq using a mixed embedding and provide a machine-checked proof of type soundness. We have implemented a verifier based on the proposed type system and demonstrated that it can verify the correctness of programs that manipulate nested arrays, which were beyond the reach of Tanaka et al.

cs.PL

新论文 · v1arXiv:2610.34723

Connecting Quantum Proof Systems and Hoare Logic

Liyi Li, Zoukarneini Difaizi Tagba, Alex Potanin

原文摘要

Verifying quantum programs today requires specialized proof systems built on interactive theorem provers such as Rocq, Lean, Isabelle, or Why3, and even modest quantum algorithms cost substantial human effort to verify. Because quantum programs cannot be effectively checked by runtime testing, formal verification is the only viable path to correctness, making the cost of these bespoke systems the chief barrier to scalable quantum software assurance. We show that verifying a quantum program should be no harder than verifying a classical array program, a paradigm commonly used in parallel programming: the Qafny quantum proof system translates into Hoare logic with array theory completely (every Qafny proof becomes a valid Hoare triple) and soundly (a valid translated triple certifies only true quantum specifications), and we mechanize the completeness direction in Rocq. The embedding determinizes quantum proof obligations and exposes the full machinery of classical automated verifiers (e.g. Dafny and SMT-based separation logic) to quantum code, removing the need for dedicated quantum proof system infrastructure. In particular, the embedding supplies the correctness argument that the existing compilation of Qafny into Dafny lacks.

cs.LO · cs.PL

版本更新 · v5arXiv:2306.12935

Special Delivery: Programming with Mailbox Types (Extended Version)

Simon Fowler, Duncan Paul Attard, Danielle Marshall, Simon J. Gay, Phil Trinder

原文摘要

The asynchronous and unidirectional communication model supported by mailboxes is a key reason for the success of actor languages like Erlang and Elixir for implementing reliable and scalable distributed systems. Although actors eliminate many of the issues stemming from shared memory concurrency, they remain vulnerable to communication errors such as protocol violations and deadlocks. Behavioural types make it possible to detect communication errors early in the development process, but most work has addressed channel-based languages rather than actor languages. Mailbox types are a novel behavioural type system for actors first introduced for a process calculus, and capture the contents of a mailbox as a commutative regular expression. Due to aliasing and nested evaluation contexts, moving from a process calculus to a programming language is challenging. This paper presents Pat, the first programming language incorporating mailbox types, and describes an algorithmic type system. Pat is a higher-order functional language with sums, products, and lists, along with interfaces that allow finer-grained reasoning about mailbox contents. Typechecking in Pat detects four classes of behavioural error: protocol violation, unexpected message, forgotten reply and self-deadlock, as well as the usual data type errors. The Pat type system makes essential use of quasi-linear typing to tame some of the complexity introduced by aliasing. We make use of a co-contextual algorithmic type system, achieved through a novel use of backwards bidirectional typing, and we prove it sound and complete with respect to our declarative type system. We implement a type checker, and use it to demonstrate the expressiveness of Pat on a factory automation case study and a series of examples from the Savina actor benchmark suite. This establishes a foundation for applying mailbox typing to practical actor languages.

cs.PL