Sam Staton
YOU?
Author Swipe
View article: Modular abstract syntax trees (MAST): substitution tensors with second-class sorts
Modular abstract syntax trees (MAST): substitution tensors with second-class sorts Open
We adapt Fiore, Plotkin, and Turi's treatment of abstract syntax with binding, substitution, and holes to account for languages with second-class sorts. These situations include programming calculi such as the Call-by-Value lambda-calculus…
View article: Program Logics via Distributive Monoidal Categories
Program Logics via Distributive Monoidal Categories Open
We derive multiple program logics, including correctness, incorrectness, and relational Hoare logic, from the axioms of imperative categories: uniformly traced distributive copy-discard categories. We introduce an internal language for imp…
View article: Uncertainty-Aware Step-wise Verification with Generative Reward Models
Uncertainty-Aware Step-wise Verification with Generative Reward Models Open
Complex multi-step reasoning tasks, such as solving mathematical problems, remain challenging for large language models (LLMs). While outcome supervision is commonly used, process supervision via process reward models (PRMs) provides inter…
View article: Compositional Imprecise Probability: A Solution from Graded Monads and Markov Categories
Compositional Imprecise Probability: A Solution from Graded Monads and Markov Categories Open
Imprecise probability is concerned with uncertainty about which probability distributions to use. It has applications in robust statistics and machine learning. We look at programming language models for imprecise probability. Our desidera…
View article: Probabilistic Programming Interfaces for Random Graphs: Markov Categories, Graphons, and Nominal Sets
Probabilistic Programming Interfaces for Random Graphs: Markov Categories, Graphons, and Nominal Sets Open
We study semantic models of probabilistic programming languages over graphs, and establish a connection to graphons from graph theory and combinatorics. We show that every well-behaved equational theory for our graph probabilistic programm…
View article: Probabilistic Programming with Exact Conditions
Probabilistic Programming with Exact Conditions Open
We spell out the paradigm of exact conditioning as an intuitive and powerful way of conditioning on observations in probabilistic programs. This is contrasted with likelihood-based scoring known from languages such as Stan. We study exact …
View article: Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets
Probabilistic programming interfaces for random graphs: Markov categories, graphons, and nominal sets Open
We study semantic models of probabilistic programming languages over graphs, and establish a connection to graphons from graph theory and combinatorics. We show that every well-behaved equational theory for our graph probabilistic programm…
View article: Denotational semantics for languages for inference: semirings, monads, and tensors
Denotational semantics for languages for inference: semirings, monads, and tensors Open
Computational effects are commonly modelled by monads, but often a monad can be presented by an algebraic theory of operations and equations. This talk is about monads and algebraic theories for languages for inference, and their connectio…
View article: Proceedings of the Sixth International Conference on Applied Category Theory 2023
Proceedings of the Sixth International Conference on Applied Category Theory 2023 Open
The Sixth International Conference on Applied Category Theory took place at the University of Maryland, 31 July -- 4 August 2023. This conference follows the previous meetings at Leiden (2018), Oxford (2019), MIT (2020, fully online), Camb…
View article: A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories
A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories Open
Stochastic memoization is a higher-order construct of probabilistic programming languages that is key in Bayesian nonparametrics, a modular approach that allows us to extend models beyond their parametric limitations and compose them in an…
View article: Quantum de Finetti Theorems as Categorical Limits, and Limits of State Spaces of C*-algebras
Quantum de Finetti Theorems as Categorical Limits, and Limits of State Spaces of C*-algebras Open
De Finetti theorems tell us that if we expect the likelihood of outcomes to be independent of their order, then these sequences of outcomes could be equivalently generated by drawing an experiment at random from a distribution, and repeati…
View article: Probabilistic Programming with Exact Conditions
Probabilistic Programming with Exact Conditions Open
We spell out the paradigm of exact conditioning as an intuitive and powerful way of conditioning on observations in probabilistic programs. This is contrasted with likelihood-based scoring known from languages such as Stan . We study exact…
View article: A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories
A model of stochastic memoization and name generation in probabilistic programming: categorical semantics via monads on presheaf categories Open
Stochastic memoization is a higher-order construct of probabilistic programming languages that is key in Bayesian nonparametrics, a modular approach that allows us to extend models beyond their parametric limitations and compose them in an…
View article: $ω$PAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs
$ω$PAP Spaces: Reasoning Denotationally About Higher-Order, Recursive Probabilistic and Differentiable Programs Open
We introduce a new setting, the category of $ω$PAP spaces, for reasoning denotationally about expressive differentiable and probabilistic programming languages. Our semantics is general enough to assign meanings to most practical probabili…
View article: Affine Monads and Lazy Structures for Bayesian Programming
Affine Monads and Lazy Structures for Bayesian Programming Open
We show that streams and lazy data structures are a natural idiom for programming with infinite-dimensional Bayesian methods such as Poisson processes, Gaussian processes, jump processes, Dirichlet processes, and Beta processes. The crucia…
View article: ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs
ADEV: Sound Automatic Differentiation of Expected Values of Probabilistic Programs Open
Optimizing the expected values of probabilistic processes is a central problem in computer science and its applications, arising in fields ranging from artificial intelligence to operations research to statistical computing. Unfortunately,…
View article: Affine Monads and Lazy Structures for Bayesian Programming
Affine Monads and Lazy Structures for Bayesian Programming Open
We show that streams and lazy data structures are a natural idiom for programming with infinite-dimensional Bayesian methods such as Poisson processes, Gaussian processes, jump processes, Dirichlet processes, and Beta processes. The crucia…
View article: Concrete categories and higher-order recursion
Concrete categories and higher-order recursion Open
We study concrete sheaf models for a call-by-value higher-order language with\nrecursion. Our family of sheaf models is a generalization of many examples from\nthe literature, such as models for probabilistic and differentiable\nprogrammin…
View article: Quantum de Finetti Theorems as Categorical Limits, and Limits of State Spaces of C*-algebras
Quantum de Finetti Theorems as Categorical Limits, and Limits of State Spaces of C*-algebras Open
De Finetti theorems tell us that if we expect the likelihood of outcomes to be independent of their order, then these sequences of outcomes could be equivalently generated by drawing an experiment at random from a distribution, and repeati…
View article: Higher Order Automatic Differentiation of Higher Order Functions
Higher Order Automatic Differentiation of Higher Order Functions Open
We present semantic correctness proofs of automatic differentiation (AD). We consider a forward-mode AD method on a higher order language with algebraic data types, and we characterise it as the unique structure preserving macro given a ch…
View article: Monads for Measurable Queries in Probabilistic Databases
Monads for Measurable Queries in Probabilistic Databases Open
We consider a bag (multiset) monad on the category of standard Borel spaces, and show that it gives a free measurable commutative monoid. Firstly, we show that a recent measurability result for probabilistic database queries (Grohe and Lin…
View article: Name-passing process calculi: operational models and structural operational semantics
Name-passing process calculi: operational models and structural operational semantics Open
This thesis is about the formal semantics of name-passing process calculi. We study operational models by relating various different notions of model, and we analyse structural operational semantics by extracting a congruence rule format f…
View article: An agent architecture for simulation of end-users in programming-like tasks
An agent architecture for simulation of end-users in programming-like tasks Open
We present some motivation and technical details for a software simulation of an end-user performing programming-like tasks. The simulation uses an agent/agenda model by breaking tasks down into subgoals, based on work of A. Blackwell. Thi…
View article: Compositional Semantics for Probabilistic Programs with Exact Conditioning
Compositional Semantics for Probabilistic Programs with Exact Conditioning Open
We define a probabilistic programming language for Gaussian random variables with a first-class exact conditioning construct. We give operational, denotational and equational semantics for this language, establishing convenient properties …
View article: A Monad for Probabilistic Point Processes
A Monad for Probabilistic Point Processes Open
A point process on a space is a random bag of elements of that space. In this paper we explore programming with point processes in a monadic style. To this end we identify point processes on a space X with probability measures of bags of e…
View article: A generalization of hierarchical exchangeability on trees to directed acyclic graphs
A generalization of hierarchical exchangeability on trees to directed acyclic graphs Open
Motivated by the problem of designing inference-friendly Bayesian nonparametric models in probabilistic programming languages, we introduce a general class of partially exchangeable random arrays which generalizes the notion of hierarchica…
View article: Higher Order Automatic Differentiation of Higher Order Functions
Higher Order Automatic Differentiation of Higher Order Functions Open
We present semantic correctness proofs of automatic differentiation (AD). We consider a forward-mode AD method on a higher order language with algebraic data types, and we characterise it as the unique structure preserving macro given a ch…
View article: Probabilistic programming semantics for name generation
Probabilistic programming semantics for name generation Open
We make a formal analogy between random sampling and fresh name generation. We show that quasi-Borel spaces, a model for probabilistic programming, can soundly interpret the ν-calculus, a calculus for name generation. Moreover, we prove th…