CS Paper Radar

Handling JAX

Oghenevwogaga Ebresafe, Daniel Zheng, Gordon Plotkin, Ningning Xie

cs.PL ·submitted 2026-11-02 20:23 UTC · v1

Abstract

Languages that target hardware accelerators typically expose a restricted, first-order core without recursion or first-class functions, leaving programmers without a principled way to express computational effects. This paper presents a technique for compiling effect handlers to such a constrained target. We introduce a novel translation that statically eliminates effect handlers, and prove that it preserves both typing and semantics. Moreover, we address the challenges of integrating effect handlers with structured control flow, where continuations cannot be constructed statically. The calculus and all our results are fully mechanized in the Lean 4 proof assistant. Finally, we implement our design as a library for JAX, a Python domain-specific language for accelerator programming, and demonstrate its expressiveness through practical case studies.

Closest papers

Nearest neighbours by meaning across the whole index.

Cambria: Resource Abstraction for Parametrized Algebraic Effects and Handlers

cs.PL ·2026-08-28 ·Jack Liell-Cock, Sam Staton
theory similarity 0.65
Abstract

The algebraic effects and handlers paradigm separates the concerns of the interface and implementation of computational effects in programming languages. We present Cambria, a language that extends this framework to the parametrized setting. Effect signatures may use abstract parameter types that are instantiated by the handler along with the operation implementations. Parameters abstract over resources, such as memory locations or thread IDs, permitting algebraic effects to encode dynamic allocation. They are first-class in the type system but erased at runtime, requiring no coercions or type-directed reduction. We prove parametricity via a step-indexed logical relation, formalizing the abstraction guarantee provided by parametrized handlers. We also establish type safety and classify the annotations needed for completeness of the type inference algorithm. We demonstrate Cambria's practicality with a working implementation and provide examples including local state, Pólya's urn, and concurrent thread management. The last is a parametrized effect whose abstract thread IDs are shared between concurrent computations, going beyond standard instances. Cambria is the first calculus with user-defined resource-allocating effects that guarantees, via parametricity, that client code cannot depend on how a handler represents its resources.

0.10

Verification of Compiler-to-Accelerator Mappings for Machine Learning Accelerators

cs.PL ·2026-09-25 ·Akash Gaonkar, Mike He, Yi Li, Bo-Yuan Huang, Andrew Cheung +6 more
code/data similarity 0.65
Abstract

To meet the performance needs of modern machine learning (ML) applications, ML compiler frameworks support compiler-to-accelerator mappings that offload parts of application code to operations in specialized hardware accelerators. However, most of these frameworks do not verify these mappings down to the hardware level, potentially resulting in functional mismatches. In this paper we propose BOLT, the first framework for formally verifying the correctness of compiler-to-accelerator mappings for coarse-grained intrinsics in ML accelerators, with respect to a formal hardware semantics. BOLT does not require additional information from the compiler, and verifies the functional equivalence of the application code and the code for the mapped hardware accelerator intrinsic, including handling of complex loop nests and tensor data layouts in hardware. It effectively utilizes a pattern of *aligning* software loops with the hardware, followed by *relating* corresponding data layouts, to enable verification using well-aligned product programs. To support these steps, we propose two custom templates --- the sync-skeleton and the layout-sketch --- to guide users in aligning loops and specifying data layout relationships, respectively. We have developed a proof-of-concept prototype for BOLT and use it to successfully verify the correctness of several complex mappings for two recent open-source ML accelerators.

0.49

Compiling Imperative Hardware Protocol Specifications to Hardware

cs.PL ·2026-11-14 ·Nikil V. Shyamsunder, Ernest Ng, Adrian Sampson, Kevin Laeufer
similarity 0.65
Abstract · 28 pages, 16 figures

Correct modular composition in hardware depends on interfaces with subtle multi-cycle timing behavior, yet such protocols remain difficult to specify, test, and debug. Recent work has demonstrated that hardware communication specifications can take the form of compact imperative programs that describe the cycle-by-cycle behavior of each logical transaction. However, prior tools only use these specifications for simulation-based testing and debugging, and their semantics remain informal. In this work, we develop a theory of hardware protocol specifications using automata. In addition to making the specifications' meaning precise, the automaton representation lets us compile them into synthesizable hardware. We implement a compiler that produces RTL modules for driving hardware interfaces and for reconstructing logical transactions from low-level I/O signals. We demonstrate a variety of use cases for synthesizable protocol drivers and reconstructors, including runtime monitors that check security properties in the Wishbone protocol and a binding generator that synthesizes interfaces between RTL modules and programs in the Calyx intermediate language.

0.32

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

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

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

0.26

Garlene: Guarded Recursion in Lean

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

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

0.24

A monadic interpreter and type-and-effect checker

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

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

0.10

Write Once, Run Everywhere: The Axon DSL for Shape-Safe and Framework-Agnostic LLM Architectures

cs.AI cs.PL ·2026-08-20 ·Jacob Nielsen, Danial Namazifard, Lukas Galke Poech, Peter Schneider-Kamp
code/data similarity 0.62
Abstract

The entire ecosystem of open-source language models effectively relies on a single platform. What if this platform was forced to shut down tomorrow? Implementing and maintaining efficient model definitions and translating them between different training and inference regimes is a resource-heavy task that severely limits model efficiency and portability, hindering both scaling and deployment. Here, we present Axon, a strongly typed domain-specific language with Haskell-like syntax, that enables a write-once, run everywhere paradigm for LLM architectures. By basing collaboration on a language specification rather than a specific framework's vision, Axon fosters open cooperation and empowers researchers to implement highly specialized architectures without giving up optimization infrastructure or accepting deployment lock-in. Axon allows for concise, auditable specifications that can be automatically compiled to standalone implementations for leading frameworks: PyTorch, PyTorch with Triton, JAX, MLX and vLLM. In 467 inference benchmarking experiments on models ranging from 135M to 32B parameters, we demonstrate median speedups of 7% on PyTorch, 12% on PyTorch with Triton, 91% on JAX, and 107% on MLX, compared to the reference implementations from Transformers. When deployed as native vLLM architectures with PagedAttention and KV-cache, Axon models achieve a 58% median speedup over Transformers implementations.

0.40

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

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

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

0.26