跳到正文
研踪PaperTrail

论文库

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

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

全站更新概况

+197新增论文
+151其中 AI 相关
+16已有论文修订
+91新增 AI 导读

arXiv 最近完成扫描:2026-11-22 08:44 · 全站最近入库:2026-11-21 12:19各信源进度 →

统计口径与数据新鲜度

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

最近完成检查:2026-11-22 08:44最近发现新增版本:2026-11-21 12:19库内论文最新更新时间:2026-11-20 02:59

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

29,158 已收录论文24,181 AI 相关8,992 有修订112 HF 社区发现

浏览论文库

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

找到 185 篇论文 · 按版本更新时间排序上轮扫描起点 2026-11-22 08:42(北京时间)
新论文 · v1arXiv:2611.26563

你有邮件:面向Actor的集合论类型

You Have Mail: Set-Theoretic Types for Actors

Giuseppe Castagna, Luca Padovani, Daniele Varacca, Amine Nasri

AI 速读 基于摘要

为Elixir的Actor进程提出一种静态类型系统,通过推断函数可用的邮箱类型边界,支持高阶函数在消息中传递并引用self()和receive,且仅需标注进程接口。

cs.PL

查看原文摘要

We present a type system for the processes of Elixir, a dynamic language based on the actor model whose static type system covers only its functional core. Each process is typed by $\mathtt{pid}(t)$, where the ``interface'' $t$ is the type of the messages the process expects in its mailbox: sends are checked against the recipient's interface, and receives rely on the interface of the process that performs them. One of the difficulties of typing Elixir is that mailboxes are implicit: a function shipped in a message may evaluate $\mathtt{self()}$ and execute receive instructions, and both refer to whichever process eventually runs the function---$\mathtt{self()}$ returns that process's pid, receive reads that process's mailbox---so the mailbox they act on is not known where the function is written. We solve this problem by inferring, for every function, bounds on the type of the mailboxes it can be used with; as a result, the system types higher-order functions that travel in messages even when they contain reference to $\mathtt{self()}$ and receive instructions. The only new annotation the programmer writes is the interface of each spawned process; everything else is inferred by reusing the existing subtyping and constraint-resolution machinery of Elixir, and the system is proved sound. For legacy code, the interface can be reconstructed from the receive clauses: what the branches do with their messages bounds it from above, and the most permissive solution is sharp enough to recover received pids and closures.

新论文 · v1arXiv:2611.26507

重温简单类型的遗传置换:大学代数的一个婴儿案例

Hereditary permutations for simple types revisited: A baby case for University Algebra

Thorsten Altenkirch

AI 速读 基于摘要

在β-正规η-长类型项内重新证明简单类型λ演算的可定义同构恰为遗传置换,并证明这些同构的群胚由一组显式方程呈现,全部结果在Agda中形式化。

cs.LO · cs.PL

查看原文摘要

It is a classical result that the definable isomorphisms of the simply typed lambda-calculus with function types are exactly the hereditary permutations, and that they are generated by $A \to B \to C \cong B \to A \to C$ and congruence. We give a new proof of this result that stays inside beta-normal eta-long typed terms and uses no completeness theorem: an induction that descends through both components of an isomorphism at once. We then go one level up and prove a coherence theorem: two derivations of an isomorphism denote the same isomorphism if and only if they are equal modulo an explicit list of equations (groupoid laws, functoriality, involution, naturality and the braid equation), so these equations present the groupoid of isomorphisms, a hereditary version of the Coxeter presentation of the symmetric groups. All results are formalised in Agda, on intrinsically typed syntax with hereditary substitution, without postulates. The work is a case study for the syntactic completeness conjecture of University Algebra, a proposed solution of Tarski's high school algebra problem using dependent types, whose semantic counterpart is open. We explain the motivation and which parts of the method we expect to carry over.

新论文 · v1arXiv:2611.26400

论条件分支的语义

On the semantics of conditional branching

Fredrik Dahlqvist

AI 速读 基于摘要

受概率与量子程序中if-then-else非标准解释的启发,作者提出一个统一的条件分支范畴结构,并揭示GKAT与重心代数的斜结合律是同一规则的两个实例。

cs.LO · cs.PL

查看原文摘要

Motivated by the non-standard interpretations of if-then-else in probabilistic and quantum programs we review the different semantics of conditional branching and propose a unifying categorical structure for the interpretation of if-then-else. We show that many semantically important categories possess this structure, covering inter alia classical, probabilistic, quantum or non-deterministic computations. We examine algebraic structures related to and generated by this categorical structure, in particular on collections of predicates. In this setting we show that the skew-associativity rules of GKATs and barycentric algebras are two instances of a common skew-associativity rule.

版本更新 · v2arXiv:2610.34548

归纳基础算术:Goodstein、九头蛇与Γ₀

Inductive Grounded Arithmetic: Goodstein, the Hydra, and $Γ_0$

Bryan Ford

AI 速读 基于摘要

作者提出归纳基础算术(IGA),在基础逻辑中统一处理递归定义,并证明Goodstein定理、九头蛇游戏及Peano算术一致性,同时刻画Γ₀与排中律的精确关系。

math.LO · cs.LO · cs.PL

查看原文摘要

What does a recursive definition mean in a grounded logic, where a sentence is true only if a terminating process makes it so? This paper takes Kripke's answer for truth, the least fixed point, as a rule. Reflective Grounded Arithmetic (RGA) writes any recursive definition as one self-referential term; Inductive Grounded Arithmetic (IGA) adds the elimination rule for every positive one, making each an inductive definition. IGA is omega-sound and proof-grounded: sound and complete for a semantics whose certificates are its own proofs. IGA proves Goodstein's theorem, the Kirby-Paris hydra game for primitive recursive strategies, and, along Gentzen's route, the consistency of Peano Arithmetic. IGA certifies the Veblen notation below every $\varphi(n,0)$: its accessibility ordinal there is $\varphi(ω,0)$, that of the paracomplete truth theory PKF. Every theorem is machine-checked in Isabelle/HOL; order types and PKF's ordinal are cited. IGA proves the Veblen notation well-founded exactly when it admits bivalence of accessibility for it, which it does not, and that bivalence is sound exactly when the order is well-founded. So $Γ_0$ lies exactly one instance of excluded middle away, and that instance, the well-foundedness sentence and one membership claim in an internal form of Kleene's $\mathcal{O}$ are interderivable over IGA. Bivalence at the Bachmann-Howard order keeps proof-groundedness. One such claim buys well-foundedness of the countable part of Buchholz's notation at every finite level, of type $ψ_0(Ω_ω)$, and $k$ stratified bivalence rules give a proof-grounded system proving the countable part up to level $k$ well-founded; $k$ iterated closings-off of truth do too, sound only for a closed-off model. Unrestricted conditional proof is inconsistent (Curry's paradox); the purchase is implication at a hypothesis not provably decided.

新论文 · v1arXiv:2611.26221

Sightline: Calibrated Data-Flow Summaries for LLM-Integrated Applications

Zihao Xu, Yuekang Li, Ruitao Feng, Haifeng Shen

原文摘要

Programs increasingly call large language models (LLMs), filling prompt placeholders with program values and consuming the output. Such a call crosses the boundary between natural language and programming language (NL/PL). To follow data across it, an analysis needs a data-flow summary of which placeholders the output uses, but no code describes what the model does. Analyses of these LLM-integrated applications therefore taint every output with every input, creating spurious flows, or ask a second model to label each call, which is costly. We prove, and mechanize in Lean 4, that a placeholder flows to the output of a transformer, to first order, only through the attention that reads it (no reading, no flow), and that a faint reading or sensitivity cannot certify that a placeholder does not flow. Unlike reading, the log-probability gradients and Fisher signals of existing methods vanish on confident outputs, and single-span removal fails on duplicated content. Our tool, Sightline, reads a recorded call in one forward pass, learns from labels which reads are uses, and calibrates the pruning to miss at most a chosen fraction $α$ of true flows, on average over call sites, when deployment is exchangeable with calibration. On 2,103 unseen repository families and four models, Sightline is the most accurate summary against the seven closest methods and a hidden-state probe. Calibrated at $α$ = 1%, it misses about 1% of true flows and prunes 43.9-65.6% of spurious flows, 1.6 to 2.6 times as many as the best baseline, and still 43.8-60.1% when calibrated on another collection. Through an open surrogate, it reads models treated as closed about as accurately as they read themselves, without their labels. In the information-flow control of an LLM agent, it removes about half of the labels from inputs that do not flow.

cs.PL · cs.AI

版本更新 · v4arXiv:2601.22978

Triosecuris: Formally Verified Protection Against Speculative Control-Flow Hijacking

Jonathan Baumann, Yonghyun Kim, Yan Farba, Catalin Hritcu, Julay Leatherman-Brooks

原文摘要

This paper introduces Triosecuris, a formally verified defense against Spectre BTB, RSB, and PHT that combines CET-style hardware-assisted control-flow integrity with compiler-inserted speculative load hardening (SLH). Triosecuris is based on the novel observation that in the presence of CET-style protection, we can precisely detect BTB misspeculation for indirect calls and RSB misspeculation for returns and set the SLH misspeculation flag. We formalize Triosecuris as a transformation in Rocq and provide a machine-checked proof that it achieves relative security: any transformed program running with speculation leaks no more than what the source program leaks without speculation. This strong security guarantee applies to arbitrary programs, even those not following the cryptographic constant-time programming discipline.

cs.CR · cs.PL

版本更新 · v2arXiv:2609.40119

Function Contracts and Beyond: Machine-Checked Assurance Cases for Conformance of C Libraries to Their Requirements

Haokun Li, Zhongyi Wang, Mingshuai Chen, Ling Zhang, Guanyan Li, Depeng Liu, Xiao Yi, Shengchao Qin 等 9 位作者

原文摘要

Large language models (LLMs) have shown promise in automating interactive theorem proving, yet verification of real-world C codebases requires more than discharging individual proof goals. The task involves jointly constructing expressive function specifications and their proofs, and ensuring that library interfaces compose along intended call sequences even without a designated client. We present Accord, an LLM-assisted framework for building machine-checked assurance cases: structured, auditable artifacts supporting the claim that a C codebase meets its intended requirements. To model intended cross-interface use in open libraries, Accord constructs an interface protocol that exposes permitted call sequences and resource assumptions for review, with a conditional safety guarantee under verified contracts and caller obligations. Accord coordinates two complementary phases: (i) requirement-guided analysis and bottom-up construction of candidate specifications and protocols; and (ii) modular proof construction with feedback that revises the specifications and proofs. Implemented using VST in Rocq, Accord establishes memory safety for 259 function definitions across seven implementation cases from six benchmark families, including industrial cryptographic modules, and additional functional correctness for red--black trees and ML-DSA. Human review took an estimated 0.17--8.00 hours per case. The guarantees depend on disclosed contracts and assumptions; human review supplies the conformance judgments connecting the formal artifacts to the intended requirements.

cs.PL · cs.SE

新论文 · v1arXiv:2611.25636

Tenon: A Unified Programming Framework for Retargetable PIM Compilation

Niansong Zhang, Shiran Guo, Zhiru Zhang

原文摘要

Processing-in-memory (PIM) is emerging as a building block of heterogeneous systems for memory-bound workloads, and commercial prototypes now span near-bank SIMD engines, bank-level GDDR accelerators, programmable DRAM cores, and bit-level in-SRAM processors. Their programming stacks are fragmented: no abstraction or compiler is shared across vendors, and per-device models range from instruction sequences to C-like languages. Data layout further complicates the problem: tight compute-memory integration makes data layout a first-order optimization, yet existing PIM compilers lack a unified way to represent and optimize it. A key observation is that PIM compilation targets can be modeled as nested grids of compute and storage units connected by legal data-transfer paths. We present Tenon, a unified programming framework for retargetable PIM compilation. It decouples workload, compilation target, and cost specifications, so a workload is expressed once and compiled through a unified programming framework. Tenon generalizes the $\mathbb{F}_2$ linear layout algebra from GPU compilers to map logical work and data onto these compute and storage grids. It automatically constructs a minimum-movement data layout given a workload and a target specification. We evaluate Tenon on six PIM backends: five commercial backends and AttAcc, a state-of-the-art academic HBM-based PIM architecture. Across the commercial backends, it matches or outperforms vendor, expert, and compiler baselines, with geometric-mean speedups of up to $1.20\times$ and individual speedups up to $3.65\times$. For end-to-end GPT-13B decoding on AttAcc, Tenon-compiled workloads run $1.2$--$1.3\%$ faster than those compiled by DCC, a state-of-the-art PIM compiler, across all three batch-4 configurations. Together, these results demonstrate Tenon's performance portability across diverse PIM target families.

cs.PL

版本更新 · v2arXiv:2611.23555

MetaphIR: Corpus-Scale Applicability Analysis for LLVM Peephole Optimizations

Hongxu Xu, Xintong Zhou, Chunhao Liao, Chengnian Sun

原文摘要

Peephole optimizations replace short source instruction sequences with more efficient equivalents, typically guarded by preconditions such as requiring a constant operand to be a power of two. Since every new rewrite adds maintenance burden and compile-time cost, compiler developers need to know how often real-world programs both match the source pattern and satisfy its preconditions before committing to an implementation. Existing workflows fall short: structural search over an intermediate representation (IR) corpus of 4.8 million functions ignores preconditions and therefore overcounts, whereas implementing the rewrite and recompiling the corpus yields exact counts only after paying the engineering cost, with each run of the corpus's on-demand recompilation pipeline taking a median of 47 minutes. This delay is especially limiting when generalizing a rewrite, as developers often iterate over multiple variants to trade off coverage against complexity. We introduce MetaphIR, a system pairing a domain-specific language for expressing LLVM peephole optimizations with an indexed search engine over large IR corpora. Using a syntax modeled on LLVM's C++ matchers, MetaphIR patterns augment LLVM IR with holes and Boolean preconditions over matched values. To answer queries at interactive speed, MetaphIR builds compact per-function summaries ahead of time and uses abstract interpretation over those summaries to soundly filter out functions that cannot satisfy a query's constraints. Across twenty recent peephole optimizations from LLVM's InstCombine pass, MetaphIR recovers the exact set of functions where each rewrite applies in isolation, achieving 100% precision and recall. Queries complete in a median of 1.27 seconds---a 22x speedup over a full corpus scan---enabling developers to quickly gauge an optimization's reach and generality prior to implementation.

cs.PL · cs.SE

版本更新 · v2arXiv:2609.37233

DatalogBench: Evaluating Large Language Models on Text-to-Datalog Synthesis

Yuan Li, Hanyun Jiang, Guowei Tian, Chengpeng Wang, Peisen Yao

原文摘要

Datalog underpins reasoning tasks such as program analysis, but its programs are hard to write. Existing synthesizers automate this task but require users to state their intent as input-output examples. Large language models (LLMs) suggest a more natural route, text-to-Datalog synthesis from a natural-language question, yet how well they do so has not been systematically evaluated. We present DatalogBench, a benchmark of 136 text-to-Datalog synthesis tasks curated from existing Datalog-based artifacts. Synthesized programs are graded by execution on held-out inputs against an oracle validated by mutation analysis. Across six LLMs and four prompting configurations, exact match peaks at 75.7%; an input-output example raises it by about six points, while relation descriptions add little. Under direct prompting, most failures occur at compile time, typically because a model invents auxiliary predicates that it never declares or types consistently. Two coding agents reach up to 86.8% and eliminate nearly all such failures, leaving mostly semantic errors concentrated in recursive tasks. DatalogBench thus identifies recursive reasoning and decomposition as open challenges for current LLMs and agents, and offers a reliable, execution-grounded measure of both.

cs.PL · cs.AI

新论文 · v1arXiv:2611.24649

A Principled Approach to Concurrency, Nondeterminism, and Asynchrony in Choreographies

Xueying Qin, Marco Peressotti, Fabrizio Montesi

原文摘要

Choreographic programming (CP) describes a distributed system as a global program and compiles it into communicating network programs via endpoint projection (EPP). Asynchrony captures the independent progress of communicating processes, while nondeterminism captures the range of behaviours that can arise from their interactions. However, the integration of both features into a theory of CP is absent. We present Nyarlathotep, the first asynchronous nondeterministic CP framework. We define its operational semantics of choreographies and networks using labelled transition systems. Besides asynchrony and choreographic nondeterminism, Nyarlathotep supports expressive features including general branching, out-of-order execution, and general recursion with parameterised procedures that processes can enter independently. We prove EPP sound and complete, establishing strong behavioural equivalence between the semantics of choreographies and their projected networks. We prove that projected networks are communication-safe and deadlock-free. We mechanised all our results in Lean 4.

cs.PL

版本更新 · v2arXiv:2611.19113

Composable Rewrites for Layouts of Algebraic Data Types

Christophe Gyurgyik, Alexander J Root, Benjamin Driscoll, Gabriel Radanne, Fredrik Kjolstad, Clément Pit-Claudel

原文摘要

Algebraic data types (ADTs) decouple the logical structure of data from physical layout choices that affect performance. For example, packing small fields into a word improves spatial locality, while storing co-accessed fields contiguously can enable vectorization. Such choices reinforce or undermine one another, with ramifications for compiler optimizations and memory management. Their interplay creates a combinatorial space of layouts with different runtime costs and memory footprints. The most favorable layout depends on the program's construction and destruction patterns, the characteristics of input data, and the target machine. Exploring this space requires control over layout decisions and a way to compose them while preserving program semantics. We provide both through rewrite rules over layouts, independent of any particular source language or bit-level encoding. Starting from a canonical layout derived from the ADT, these rules transform its representation while leaving the source program intact. We identify a local refinement criterion for proving each rewrite rule correct, so that layouts continue to represent every value and keep distinct values apart. Adding a new rule therefore only requires a proof satisfying this local criterion. We realize these rules in Isomer, a new pure functional programming language whose compiler specializes construction, pattern matching, and memory management to the chosen layouts. Using a default layout for all ADTs, Isomer achieves competitive performance against established functional compilers that automatically select layouts. Our rewrites further improve performance by tailoring layouts to each workload, permitting representations that prior work cannot attain or can only achieve through explicit changes to the source code.

cs.PL

新论文 · v1arXiv:2611.24169

Matching-Logic-Based Understanding of Polynomial Functors and their Initial/Final Models Revisited

Dorel Lucanu

原文摘要

Many data types used in programming are initial algebras or final coalgebras of polynomial functors. We show how to specify them uniformly in matching logic, using the representation of polynomial functors as unary container functors $X\mapsto\sum_{a:A}X^{B[a]}$. For each container functor, we give a matching logic theory of its initial algebra and one of its final coalgebra. Besides the no-junk and no-confusion axioms and their duals, these theories include axioms about the elements that represent functions, for the initial algebra, and a bisimilarity axiom and a realisation axiom, for the final coalgebra; the existence axioms use free set variables to range over all subsets of a model. We prove that, in every model, the algebra extracted from the model is an initial algebra (a W-type) and the extracted coalgebra is a final coalgebra (an M-type) of the container extracted from the model, i.e., the one given by the model's interpretation of the shapes and positions, and that such models exist. So the data types are captured relative to the interpretation of the sorts of shapes and positions, and absolutely whenever these sorts are fixed by auxiliary specifications, which we show for finite sets, products, dependent sums, and (co)inductive sorts built from them. We derive the induction, coinduction, and bisimulation principles as theorems, and illustrate the approach on lists and on Moore machines. This paper revises and substantially extends a paper published in EPTCS 389 (FROM 2023): several axioms are corrected, and the adequacy and satisfiability proofs are new.

cs.LO · cs.PL

新论文 · v1arXiv:2611.23811

Stephen: Verifying Sequencer-Aided Coordination Systems with Cross-View Prophecy

Jinkun Geng, Muhammad Haseeb, Daniel Qian, Joseph Tassarotti, Shuai Mu, Anirudh Sivaraman

原文摘要

Many distributed systems achieve high performance by relying on dedicated sequencers to order requests, leaving replicas to commit them in that order. Despite more than a decade of such sequencer-aided coordination (SAC) systems, from Corfu and NOPaxos to LazyLog and SwitchBFT, their correctness has been argued only with pen-and-paper proofs or bounded model checking at the protocol level. In this paper, we formally verify implementations of SAC protocols. The sequencer seems to make this easy: it decides the order of all requests, so the proof can place each request's linearization point at the sequencer using a well-known technique, prophecy variables. Yet a linearization point placed at the sequencer is not durable, because the sequencer orders a request before any replica commits it. Crashes and other rare events may trigger a view change that discards the request, nullifying the earlier decision and the proof that rests on it. Our framework, Stephen, extends prophecy variables to handle view changes, and we make three contributions. (1) We develop cross-view prophecy peek, which lets the proof follow a request across view changes until it is either committed or permanently discarded. (2) Our verification uncovered bugs in existing SAC implementations, including one that can lose committed requests. We fix them and prove the fixes correct. (3) We apply Stephen to NOPaxos, Corfu and LazyLog. We build verified implementations with machine-checked proofs of linearizability. They perform within 17% of their open-source, unverified counterparts. The verified implementations and proofs will be open-sourced.

cs.DC · cs.PL · cs.SE

新论文 · v1arXiv:2611.23792

Validating Concurrent Correctness Witnesses with Ghosts by Thread-Modular Abstract Interpretation

Michael Schwarz, Zhendong Ang, Umang Mathur

原文摘要

Concurrent programs are notoriously difficult to write and to reason about, and even tools based on sound theoretical foundations can produce incorrect results due to implementation bugs. Correctness witnesses have been proposed as a way to increase the confidence in the verdicts of software verifiers by enabling independent validation. Recently, correctness witnesses have been extended to the concurrent setting, by introducing ghost variables to allow encoding more expressive invariants. While different approaches to producing witnesses with ghosts exist, validation techniques are still lacking; instead of leveraging the information encoded in the ghosts to guide the validation process, validators merely treat ghost instrumentation and invariants over ghost variables as additional proof obligations. We propose a novel framework for the validation of concurrent correctness witnesses that exploits the semantic information encoded in ghost variables. It combines a checking phase, which establishes the semantic content of the ghost instrumentation, with an exploitation phase making use of this information. Both phases are formulated as thread-modular abstract interpretation. In particular, we consider two different classes of ghost variables and techniques for exploiting them, one based on resource invariants and one based on phases. Phase ghosts guide the degree to which the abstract interpretation considers interleavings instead of always abstracting them coarsely. In this way, the abstract interpreter can validate witnesses containing invariants beyond the reach of unguided thread-modular analysis, while still retaining its scalability benefits. We have implemented our framework in a static analyzer and evaluate it on witnesses encoding resource invariants obtained from a state-of-the-art software verifier, as well as on hand-crafted witnesses encoding phase information.

cs.PL · cs.SE

新论文 · v1arXiv:2611.24984

Mode Inference for Substructural Adjoint Types

Sophia Roshal, Frank Pfenning

原文摘要

Adjoint types [Jang et al. 2024] provide a method of mixing substructural modes (for example, linear, affine, strict, or unrestricted) in a type system while preserving the proof-theoretic and computational properties of each mode. Uses of such a system include performing compiler optimizations or providing safety guarantees on parts of a program whose modes support them, while not restricting the programmer's ability to write other code as they usually do. However, Jang et al.'s algorithmic type system is monomorphic in the modes, requiring the programmer to anticipate a potentially large number of combinations of modes, and possibly copy code to conform to each of them. In this paper we define a mode inference algorithm for programs with adjoint types that produces principal modes, summarizing all possible substructural modes of a function in a simple constraint language. This removes the burden from the programmer to a priori analyze the substructural properties of their code, and, furthermore, allows a single function definition to subsume all its instances at different modes. We show that our system is sound and complete with respect to a mild restriction of Jang et al.'s monomorphic version.

cs.PL

新论文 · v1arXiv:2611.23584

Detecting Empty Abstractions and Pruning Dead Paths in the Linux eBPF Verifier with Abstract Step Functions

Harishankar Vishwanatha, Srinivas Narayana, Santosh Nagarakatte

原文摘要

The Linux kernel's eBPF verifier uses abstract interpretation to ensure the safety of user-provided programs before execution. It tracks each register with multiple interval domains and a bitwise domain (tristate numbers). Refining the abstract state at conditional branches can produce mutually contradictory constraints across domains, indicating an unreachable path. However, the verifier lacks an empty-set ($\bot$) representation and cannot detect when these domains have an empty intersection, causing it to analyze dead paths. Passing such contradictory states into domain reduction or downstream operators violates their implicit non-emptiness precondition, triggering domain invariant violations. This has been a multi-year issue in the Linux kernel causing production outages, false rejections, and state explosion. This paper presents a sound and complete constant-time emptiness check across the eBPF verifier's abstract domains to prune dead branches. We introduce abstract step functions, a general framework that tests whether intervals and non-convex domains intersect in O(1) time without scanning individual values. We develop tnum_step, a formally verified constant-time operator that jumps to the next integer satisfying a tristate bitmask. Using tnum_step, we design a multi-domain emptiness check that detects contradictory states during branch refinement and immediately prunes unreachable branches, eliminating the root cause of dead-branch invariant violations. Our technique prevents invariant violations, state explosion, and false rejections while incurring negligible (1.48%) overhead across Linux kernel selftests and production suites such as Cilium. Our tnum_step operator has been upstreamed into the mainline Linux kernel.

cs.PL

新论文 · v1arXiv:2611.24979

Trace2ST: Recovering PLC Structured Text from I/O Traces with LLM Generation and Verification

Hsi Chang, Irfan Khan

原文摘要

Programmable logic controllers (PLCs), the industrial computers that operate power and process plants, often run programs whose source code is no longer available; however, every input and output of the controller is logged continuously. This paper therefore asks whether a large language model (LLM) can recover an executable program in Structured Text (ST), the standard PLC language of IEC 61131-3, from such input/output records (traces) alone and, equally important, how the recovered program can be verified. To answer this question, we build a generate-replay-feedback pipeline. First, the LLM writes a candidate program from a compressed summary of the trace, without ever seeing the original program. The candidate is then executed one control cycle (scan) at a time and compared with the recording, and whenever a mismatch occurs the corresponding part of the trace is returned to the LLM, for at most three revisions. Because every result depends on the software that executes the candidates, we first validate it against two independent open-source PLC runtimes and find no unexplained difference. On this basis, we evaluate 47 third-party programs from two public benchmarks. The recovered programs reproduce the recorded trace exactly in 43 cases and agree with the original on 94% of scans for unseen inputs. The remaining errors, however, lie mostly in program branches that the trace never exercised; once a trace that targets these branches is added, agreement on unseen adversarial inputs rises from 0.80 to 0.98. By contrast, a classical automata-learning baseline without an LLM fits the recording but falls to 0.40 on unseen inputs, which indicates that recovering program structure is the hard part. Finally, on real data from a public water-treatment testbed, the recovered control laws match unseen measurements closely ($R^2 > 0.99$) and expose the only actuator attack in the dataset.

cs.SE · cs.AI · cs.CY · cs.PL · eess.SY

版本更新 · v2arXiv:2607.25361

The Best of Times, the Worst of Times: Moment-Based Analysis of Probabilistic Cost Structures

Chenyu Zhou, Di Wang, Thomas Reps

原文摘要

Many practical costs---such as the completion time of a quantum repeater, the rounds of an RFID collision-resolution protocol, or the response time of a fork--join computation---are described by hierarchical cost expressions: a tree of independent subcomputations with nonnegative integer costs, combined by addition, max, and min. We compute their moments with sound error bounds. Moment-based analyses for additive costs do not apply, because the moments of $\max(X,Y)$ are not determined by those of $X$ and $Y$; propagating full distributions becomes expensive as trees grow; and scalable approximations are hand-derived for specific structures and lack error bounds. Our analysis proceeds bottom-up, summarizing each subtree by a surrogate distribution: an exact short-horizon prefix plus a compact parametric tail fitted to preserve the queried moment. Each prefix is computed exactly from the children's prefixes---for a retry, whose cost sums an unbounded number of attempts, by solving a local recurrence equation---so all approximation is confined to the tails. Abstraction introduces shape error but no moment error; nonlinear operators, such as max and min, convert shape error into moment error. The analysis tracks two bounds, one on shape error and one on moment error. Tracking both lets it report a sound interval for the mean, the second moment, and the variance. Lengthening the prefix, or solving subtrees exactly, narrows the interval at the cost of additional computation. For quantum-repeater chains of up to 4096 links with high swap-success probability, our Dickens tool bounds the mean completion time within 1%, whereas the exact Markov-chain solution exhausts memory with 16 links, and the best hand-derived approximation we evaluated has 47% error with 64 links. Dickens also bounds second moments, variances, and deadline-miss probabilities, and handles RFID and fork--join costs.

cs.PL

版本更新 · v2arXiv:2502.06293

RustMC: Automated Verification of Real-World Concurrent Rust

Oliver Pearce, Julien Lange, Dan O'Keeffe

原文摘要

RustMC is a stateless model checker that targets push-button verification of unmodified concurrent Rust programs. As both Rust and C/C++ compile to LLVM IR, RustMC builds on GenMC which provides a verification framework for LLVM IR. This allows verification of Rust code and any foreign function dependencies. In this tool paper we present key implementation challenges, use-cases, and an empirical evaluation of RustMC. The challenges include intercepting threading operations, promoting memory intrinsics, and handling uninitialised accesses, all stemming from Rust's unique compilation strategy. Case studies adapted from real-world programs show RustMC finds concurrency bugs in unsafe Rust code, FFI calls to C/C++, and atomic operations. We evaluate our tool's functionality on the Loom model checker test suite and a set of production-level Rust concurrent data structures.

cs.PL · cs.CR

新论文 · v1arXiv:2611.22844

How well does graph superoptimization transfer? Adapting tensor-graph superoptimizer to a Triton-based NPU

Weronika Hryniewska-Guzik, Mateusz Comblik, Daniel Murawski, Jakub Schmiegel, Maciej Świetlik, Maciej Kokociński, Tadeusz Kobus

原文摘要

For automatic optimization systems, performance portability across increasingly diverse AI accelerators remains a challenge. We investigate how well graph-level superoptimization transfers across architectures by adapting Mirage from its CUDA-oriented design to the Huawei Ascend 910B3 through a Triton-based compilation stack. We evaluate the adapted system on transformer-relevant workloads, including matrix multiplication, softmax, RMSNorm+MatMul, gated MLP, FNN, and attention. The results show that graph-level optimization can successfully transfer and outperform available reference implementations by up to 87.0% on fused workloads. However, performance is highly dependent on tensor shape and workload structure, with substantial regressions for other configurations. We identify target-specific tensor partitioning, execution-resource modeling, backend lowering and fusion, and search and verification costs as key limitations. Our findings demonstrate that a portable graph representation and programming model do not imply a portable optimization space, motivating modular target-specific mechanisms within otherwise reusable compiler infrastructure.

cs.PF · cs.AR · cs.PL

新论文 · v1arXiv:2611.22748

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

Kwanghoon Choi

原文摘要

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.

cs.PL

新论文 · v1arXiv:2611.22663

A Unifying Metatheorem on Weak-Memory Robustness

Giovanna Kobus Conrado, Stephan Spengler, Mohamed Faouzi Atig, Andreas Pavlogiannis

原文摘要

Memory models specify the behaviors that concurrent programs may exhibit under compiler and hardware optimizations, which often deviate from Sequential Consistency (SC). Robustness is the property of a program P not exhibiting any weak behaviors when executing under a weak memory model MM, compared to SC. As such, the algorithmic problem of deciding whether $P$ is robust against MM has been studied extensively, and has been repeatedly shown to be in PSPACE for many memory models, such as TSO, PSO, and Release/Acquire. However, each model has required its own, dedicated proof, raising the natural question of whether robustness admits a unifying treatment across memory models. In this work, we answer this question affirmatively for a broad class of memory models definable in Kleene Algebra with Tests (KAT). We prove that robustness against any prefix-closed, KAT-definable memory model is in PSPACE. This metatheorem recovers nearly all prior PSPACE robustness results, and establishes PSPACE membership for several new models, including the full RC11 and the OCaml memory model. We have further formalized the correctness of our approach in Lean. On the other hand, we prove that robustness against the KAT-definable Relaxed model is undecidable, and thus prefix-closedness cannot be dropped, in general. Finally, we implement our algorithm in a prototype tool RoboKAT, and demonstrate its flexibility by checking robustness against nine memory models, several of which are not handled by prior work.

cs.PL · cs.LO

新论文 · v1arXiv:2611.22613

Python Code Generation for Isabelle/HOL

Nikolaus Huber, Roly Perera, Dominic Orchard

原文摘要

The Isabelle theorem prover provides an environment for formalising mathematics and reasoning about programs. To make verified implementations practically usable, its code generator translates functions expressed in the executable fragment of its logic into conventional programming languages. Its targets have traditionally been functional languages (Standard ML, OCaml, Haskell, and Scala), recently joined by Go. Python, which is becoming the dominant language of scientific computing, data science, and education, has remained out of reach. In this work, we close this gap with a Python backend for Isabelle's code generator. This generator enables verified algorithms to be used in Python applications, or to serve as verified references against which established Python libraries can be differentially tested, without leaving the Python ecosystem. We validate the backend on regression suites covering large parts of the HOL library and by testing six verified data structures and algorithms against established Python libraries. The generated code is slower than hand-written libraries, but well suited as a verified reference.

cs.PL · cs.LO · cs.SE

新论文 · v1arXiv:2611.22572

Datatypes In, Zippers Out!

Smayan Agarwal, Aalok Thakkar

原文摘要

A zipper represents a focused position in an algebraic data structure together with the context needed to reconstruct the whole. Datatype derivatives determine one-hole context types, but do not by themselves choose a zipper's concrete representation or specify navigation costs and demands. We present Kamot, a tool that converts regular algebraic datatype declarations in a restricted Haskell fragment into zipper implementations with operational contracts. Navigation, replacement, and reconstruction are proved correct against a reference traversal. Kamot supports mutual recursion and regular containers inside containers. A compositional analysis derives sound bounds on transitions and constructor demands for certified traversal directions. These bounds are affine in trail depth (the number of saved frames) and guarantee termination of each move on productive, potentially infinite inputs. For inhabited families the analysis is complete: when no move certificate is emitted, no bound depending only on trail depth exists, and some productive input makes a move diverge. We prove that the generated code preserves results and the reference order of constructor matches, including finite prefixes of divergent searches. Lean 4 verifies simulation, bounds, and completeness for finite values of single self-recursive datatypes, in both directions. On 19 datatype models and 81 generated families, every generated module passes Haskell type checking, and independent checkers validate certificates, traces, and bounds. In a prefetching workload, starting only searches whose bounds fit a budget answers every local query and avoids discarded source evaluations on long returns, but conservative bounds can lose answers that fuelled search delivers.

cs.PL

新论文 · v1arXiv:2611.22397

SkiNet-Sim: Simulating Petri Nets with Data for the Verification and Validation of Controllers for Autonomous Systems

Baptiste Pelletier, Karen Godary

原文摘要

A large amount of high-level Petri net formalisms has been investigated and deployed in academic settings over the past decades, but these deployments fail to reach practical applications, despite the strong guarantees they can bring to stakeholders. In particular, the lack of direct benefits from end-users reduces the appeal of Petri nets, both due to the overly simple classical Petri net formalism, and the overly specialized high-level formalisms, on top of state-space explosion issues. In this work, we investigate how a middle-ground could be reached, by separating the implementation-specific aspects of software or hardware behaviors, from the classical Petri net semantics. The goal is to benefit from the sought-after aspects of Petri nets, namely their simple firing semantic and model-checking capabilities, while still being able to augment their behavior to best reflect the modelled system. We present a formal model of Interpreted Petri nets with data-aware transitions and tokens. We illustrate this formalism by modelling the executive layer of a robotic system, and provide a lightweight tool to augment classical Petri nets for general purpose applications, as well as data-aware state-space exploration for model-checking. Their specialization in the context of autonomous robotics is showcased, with a complete industrial inspection mission use-case, to compare simulation and model-checking results between the classical and the new data-aware Petri net semantic.

cs.RO · cs.LO · cs.PL

新论文 · v1arXiv:2611.22183

A Compilation Model for Divergent Parallel Workloads

Alexander J Root, Christophe Gyurgyik, Devanshu Ladsaria, Rohan Sawhney, Jonathan Ragan-Kelley, Andrew Adams, Matt Pharr, Kayvon Fatahalian 等 9 位作者

原文摘要

Efficient execution on modern parallel machines requires more than abundant parallelism; it demands instruction coherence, memory coherence, and load balance to maximize SIMD utilization and memory bandwidth. Efficiently mapping \textit{divergent} parallel workloads to modern machines, where control flow, memory accesses, and unbounded iteration depend on per-thread runtime values, often requires global program restructuring that trades off increased coherence with reduced locality, parallelism, or extra work. We observe that the key optimizations used to accelerate divergent parallel programs can be expressed as compositions of well-known program transformations from the functional programming and loop optimization communities. We operationalize this insight through \textit{parallel dispatch graphs}: a compilation model that represents divergent programs by representing control flow, data flow between logical stages, and parallel loops within a single abstraction. To facilitate rapid exploration of points in the optimization space, we provide a scheduling language that includes composable transformations of data-dependent control flow and data flow, together with standard loop transformations and hardware bindings. This separation of concerns allows the core algorithm to remain portable, while the execution schedule can be specialized to the specifics of target hardware and input data values. We evaluate our system using popular applications from the domain of spatial computing, and show that the optimization strategies of hand-optimized parallel tree traversals, path tracers, and Monte Carlo PDE solvers can be reproduced as schedules in our system. Our generated code matches or outperforms the hand-optimized implementations (geomeans $1.02$--$2.95\times$ faster). Additionally, we demonstrate empirically that the best schedule varies across programs, machines, and inputs.

cs.PL

版本更新 · v2arXiv:2611.04331

Warpline: Binary-Level Tracing and Unified Evidence for Agentic GPU Kernel Optimization

Junyu Yin, Vinod Grover, Keren Zhou

原文摘要

LLM agents are becoming GPU kernel engineers, but they still tune kernels without seeing where the time goes. Hardware profilers report how busy each unit was, not where each warp's time went; intra-kernel tracers can show it, but only with hand-placed probes and a recompilation that alters the very kernel being measured. We present Warpline, which gives agents this view automatically while leaving the kernel essentially unchanged. Warpline analyzes the binary to decide which events to record and inserts probes into the binary itself without recompilation or any manual step. It then aligns the trace with hardware profiling data on one unified timeline. Because it needs only the binary, it can regenerate this evidence for every new version of the kernel at whatever level the agent edits it (source, IR, or PTX), closing the optimization loop without human intervention. On NVIDIA B200, across 35 kernels in Triton, CuTe DSL, and CUDA C++, Warpline adds a median overhead of 1.2% and leaves a median 99.9% of executed instructions unchanged, whereas existing tracers have median overheads of 1.6% to 13.2% and leave only 4.6% to 32.7% unchanged. Warpline also traces closed-source kernels, which these tracers cannot. On 10 SOL-ExecBench problems, agents using Warpline spend less time and fewer model requests than a bare coding agent and NVIDIA's Kernel Design Agents (KDA), yet lead both after every round in geometric mean and reach a 7.69$\times$ geometric-mean speedup, against 6.94$\times$ and 6.13$\times$. Two case studies further demonstrate that Warpline reveals hidden bottlenecks and provides actionable optimization insights.

cs.PF · cs.PL

版本更新 · v2arXiv:2606.26525

Theory-Scale Auto-Formalization of Logic for Computer Science

Yuming Feng, Frederick Pu, One An, Osbert Bastani, Li Zhang, Jiani Huang, Xujie Si, Ziyang Li

原文摘要

Auto-formalization is critical for scalable formal verification, but existing progress largely focuses on isolated statements, while theory-scale auto-formalization, which coherently translates hundreds of interdependent definitions, lemmas, and theorems, remains open due to challenges in consistency, faithfulness, scalability, and correctness. In this paper, we introduce LCS-Bench, a stand-alone, theory-scale benchmark based on Logic for Computer Science. LCS-Bench is built through a novel semi-automated agentic pipeline that leverages concept graphs, formal signature planning, issue tracking, sorry-filling with counter-example search, complemented by faithfulness review from human experts. The resulting artifact covers 327 textbook items, over 4,076 Lean declarations, and more than 85K lines of Lean code. The dataset supports broad evaluation through a data engine that automatically derives five tracks of evaluation benchmarks, measuring different aspects of auto-formalization and theorem-proving capabilities. We also introduce a novel evaluation protocol featuring definitional equivalence checkers, enabling more fine-grained and faithful assessment. Through extensive evaluation on 17 models, we demonstrate that (1) LCS-Bench is of high quality, consistent, and faithful; (2) the benchmark is challenging, with state-of-the-art models achieving only 20.3% on auto-formalization tasks; and (3) our analysis reveals key findings regarding theory-scale auto-formalization and suggests promising directions for future work.

cs.LG · cs.LO · cs.PL

版本更新 · v2arXiv:2605.23031

Step in Tine: Forking Processes in Functional Choreographies

Ashley Samuelson, Zonghao Zou, Andrew K. Hirsch, Ethan Cecchetti

原文摘要

Choreographic programming allows a concurrent programmer to write one centralized program and compile it to individual programs for each system participant. This approach simplifies critical properties like deadlock freedom, but it complicates forking new processes, a core concurrent primitive. This work addresses that gap with the choreographic fork calculus $λ{\pitchfork}$, the first functional choreographic language with process spawning. $λ{\pitchfork}$ provides a deadlock-freedom guarantee while allowing programs to dynamically determine when to spawn new processes, what they will do, and who will communicate with them. All results are formalized in Lean.

cs.PL