Sam Staton


Sam Staton
Associate Professor and
Royal Society University Research Fellow
Department of Computer Science,
University of Oxford
Room 421
Wolfson Building, Parks Road
Oxford OX1 3QD
Hugh Price Fellow,
Jesus College, Oxford

+44 (0)1865 (2)73893 
sam.staton at cs.ox.ac.uk 

Interests: My research is in programming language theory, and I'm
also interested in logic and category theory. I've recently been especially interested in
two kinds of programming language:
 Probabilistic programming languages:
The idea is to specify statistical models using programming languages.
Our recent paper
in LICS 2017 introduces quasiBorel spaces: a setting for higher order probability theory. Our PPS
2017 abstract is about exchangeability and modules.
We have papers about semantics in LICS 2016 and
ESOP 2017.
 Quantum computing and programming languages:
I found an equational theory of quantum programs
(POPL 2015).
I've also been working on contextuality and nonlocality with
Sander Uijlen
(see our ICALP 2015 paper), and on
quantum programming languages with
Mathys Rennela
(see our MFPS 2015 paper
and our QPL 2016 paper). Mathys and Sander are
students at Radboud University in Nijmegen.
My research in this area is currently funded by my grant 'Quantum
Computation as a Programming Language' (EP/N007387/1).
Aside from these recent interests, I've been involved in various foundational
aspects of programming language theory.
One key theme has been computational monads and algebraic theories:
This line of work stems from the observation that
notions of computation can be determined by program equations
using techniques from universal algebra.
I have presented
new algebraic frameworks to analyze program equations
for quantum computation (POPL 2015), jumps (LICS 2014),
local store and picalculus (LICS 2013, FOSSACS 2010 and MFPS
2009)
and functional logic programming (FOSSACS
2013).
See WACT 2014 for a categorical perspective.
I've also been involved in game semantics
(LICS 2014) and
categorical operational semantics (e.g. LICS
2008, LICS 2006, LMCS 2011).
Quick biography:
I've been in Oxford since March 2015. Before that, I spent time
in
Nijmegen (NL) on Bart Jacobs' ERC project Quantum Computation, Logic, and
Security (2013–14), in Paris on the CHOCO project (2010–11), and in Cambridge as a
lecturer (2010–13), EPSRC research fellow (2007–10), postdoc
(2006–07), PhD student (with Marcelo Fiore, 2002–06)
and undergraduate.
Publications and preprints
 A. Ścibior, O. Kammar, M. Vákár, S. Staton, H. Yang, Y. Cai, K. Ostermann, S.K. Moss, C. Heunen, and Zoubin Ghahramani.
Denotational validation of Bayesian inference.
To appear in Proceedings of 45th ACM SIGPLAN Symposium on Principles of Programming Languages (POPL 2018).
Preprint: arxiv:1711.03219.

S. Staton.
Commutative semantics for probabilistic programming.
In Proceedings of 26th European Symposium on Programming
(ESOP
2017).
Winner of EATCS Best Paper Award.
doi:10.1007/9783662544341_32.
Preprint: [pdf]

M. Piróg and S. Staton.
Backtracking with cut
via a distributive law and leftzero monoids.
Accepted as a Theoretical Pearl for Journal of Functional Programming, 2017.
Preprint: [pdf]

S. Staton and S. Uijlen.
Effect algebras, presheaves, nonlocality and
contextuality.
Accepted for Information and Computation special issue on ICALP
2015. To appear, 2017.
Preprint: [pdf]

C. Heunen, O. Kammar, S. Staton and H. Yang.
A convenient category for higherorder probability theory.
In Proceedings of 32nd Annual ACM/IEEE Symposium on Logic
in Computer Science
(LICS 2017).
Preprint: arxiv:1701.02547.

O. Kammar, P. B. Levy, S. K. Moss and S. Staton.
A monad for full ground reference cells.
In Proceedings of 32nd Annual ACM/IEEE Symposium on Logic
in Computer Science
(LICS 2017).
Preprint: arxiv:1702.04908.

S. Staton, H. Yang, N. L.. Ackerman, C. Freer, D. Roy.
Exchangeable random process and data abstraction.
Workshop on probabilistic programming semantics
(PPS
2017). Extended abstract: [pdf]

R. Furber, M. Rennela and S. Staton.
Infinitedimensionality in quantum foundations: W*algebras as
presheaves over matrix algebras.
In Proceedings of 13th International Conference on Quantum
Physics and Logic
(QPL 2016).
Electronic Proceedings in Theoretical Computer Science vol 236 pages
161–173.
doi:10.4204/EPTCS.236.11

S. Staton, H. Yang, C. Heunen,
O. Kammar and F. Wood.
Semantics for probabilistic programming: higherorder
functions, continuous distributions, and soft constraints.
In Proceedings of 31st Annual ACM/IEEE Symposium on Logic
in Computer Science (LICS 2016).
doi:10.1145/2933575.2935313.
Preprint: arXiv:1601.04943.

M. Rennela and S. Staton.
Complete positivity and natural representation of quantum computations.
In Proceedings of
31st Conference on Mathematical Foundations of Programming Semantics
(MFPS 2015).
Electr. Notes Theor. Comput. Sci. 319:
369385. doi:10.1016/j.entcs.2015.12.022.

S. Staton and S. Uijlen.
Effect algebras, presheaves, nonlocality and contextuality.
In Proceedings of
42nd International Colloquium on Automata, Languages and Programming
(ICALP 2015),
pages 401413.
doi:10.1007/9783662476666_32.
[preprint: pdf]

R. Atkey, N. Ghani, F. Nordvall Forsberg, T. Revell and S. Staton.
Models for polymorphism over physical dimensions.
In Proceedings of
13th International Conference on Typed Lambda Calculi and
Applications
(TLCA
2015),
pages 4559.
doi:10.4230/LIPIcs.TLCA.2015.45.
[preprint: pdf]

S. Staton.
Algebraic effects, linearity, and quantum programming languages.
In proceedings of
42nd ACM SIGPLANSIGACT Symposium on Principles of Programming Languages
(POPL 2015),
pages 395406.
doi:10.1145/2676726.2676999.
[preprint: pdf]

M. P. Fiore and S. Staton.
Substitution, jumps, and algebraic effects.
In proceedings of
Joint meeting of
the TwentyThird EACSL Annual Conference on
Computer Science Logic
and
the TwentyNinth Annual ACM/IEEE Symposium on
Logic in Computer Science
(CSLLICS14).
doi:10.1145/2603088.2603163.
[preprint: pdf]

P. B. Levy and S. Staton.
Transition systems over games.
In proceedings of
Joint meeting of
the TwentyThird EACSL Annual Conference on
Computer Science Logic
and
the TwentyNinth Annual ACM/IEEE Symposium on
Logic in Computer Science
(CSLLICS14).
doi:10.1145/2603088.2603150.
[preprint: pdf]

R. E. Møgelberg and S. Staton.
Linear usage of state.
Logical Methods in Computer Science, Vol 10, Issue 1.
Special issue on Algebraic and Coalgebraic Methods in Computer Science
.
doi:10.2168/LMCS10(1:17)2014.
arxiv:1403.1477.


D. Ahman and S. Staton.
Normalization by evaluation and algebraic effects.
In Proceedings of TwentyNinth Conference on Mathematical Foundations of Programming Semantics (MFPS 2013).
Electron. Notes Theor. Comput. Sci. 298:5169. 2013.
doi:10.106/j.entcs.2013.09.007.

S. Staton.
Instances of computational effects.
In Proceedings of TwentyEighth Annual ACM/IEEE Symposium on
Logic in Computer Science
(LICS 2013).
doi:10.1109/LICS.2013.58.
[preprint: pdf
 errata: txt]

S. Staton.
An algebraic presentation of predicate logic.
In Proceedings of Sixteenth International Conference on Foundations of Software Science and Computation Structures
(FOSSACS 2013),
Lecture Notes in Comput. Sci. 7794:401417. Springer, 2013.
doi:10.1007/9783642370755_26.
[preprint: pdf]

S. Staton and P. Levy.
Universal properties for impure programming languages.
In Proceedings of Fortieth ACM SIGPLANSIGACT Symposium on Principles of Programming Languages
(POPL 2013),
pages 179192.
doi:10.1145/2429069.2429091.
[preprint: pdf]

R. E. Møgelberg and S. Staton.
Linearlyused state in models of callbyvalue.
In Proceedings of Fourth International Conference on Algebra and Coalgebra in Computer Science
(CALCO 2011).
Lecture Notes in Comput. Sci. 6859:293313.
doi:10.1007/9783642229442_21.
[preprint: pdf]

S. Staton.
Relating coalgebraic notions of bisimulation.
Logical Methods in Computer Science
Vol 7, Issue 1 (March 2011).
doi:10.2168/LMCS7(1:13)2011.
arXiv:1101.4223.

S. Staton and G. Winskel.
On the expressivity of symmetry in event structures.
In Proceedings of 25th Annual IEEE Symposium on Logic in Computer Science (LICS 2010), pages 392401.
doi:10.1109/LICS.2010.37.
[preprint: pdf]

R. E. Møgelberg and S. Staton.
Full abstraction in a metalanguage for state.
In Workshop on Syntax and Semantics of Low Level Languages (LOLA 2010).
Satellite workshop of LICS 2010.

T. Altenkirch, P. Levy and S. Staton.
Higher order containers.
In Proceedings of Computability in Europe (CiE 2010).
Lecture Notes in Comput. Sci. 6158:1120.
doi:10.1007/9783642139628_2.
[preprint: pdf]

M. P. Fiore and S. Staton.
Positive structural operational semantics and monotone distributive laws.
Short contribution for 10th International Workshop on Coalgebraic Methods in Computer Science (CMCS 2010). CWI Technical report SEN1004.
[preprint: pdf]

S. Staton.
Completeness for algebraic theories of local state.
Proceedings of 13th International Conference on Foundations of Software Science and Computation Structure (FOSSACS 2010). Lecture Notes in Comput. Sci. 6014:4863.
doi:10.1007/9783642120329_5.
[preprint: pdf
 errata: txt]

S. Staton.
Relating coalgebraic notions of bisimulation, with applications to namepassing process calculi.
Proceedings of 3rd Conference on Algebra and Coalgebra in Computer Science (CALCO 2009).
Lecture Notes in Comput. Sci. 5728:191205.
doi:10.1007/9783642037412_14.
[preprint: pdf]

S. Staton.
Two cotensors in one:
Presentations of algebraic theories for
local state and fresh names.
Proceedings of 25th Conference on the Mathematical Foundations of Programming Semantics (MFPS 25). Electron. Notes Theor. Comput. Sci. 249:471490. 2009. doi:10.1016/j.entcs.2009.07.103.
[preprint: pdf]

S. Staton.
Substitution in Structural Operational Semantics and valuepassing process calculi.
Proceedings of 2nd International Workshop on Theory and Applications of Abstraction, Substitution and Naming (TAASN 2009).
[preprint: pdf]

M. Fiore and S. Staton.
A Congruence Rule Format for NamePassing Process Calculi.
Information and Computation Vol 207, Issue 2 (February 2009), Pages 209236. Special Issue on Structural Operational Semantics. doi:10.1016/j.ic.2007.12.005. [preprint: pdf]

S. Staton.
General Structural Operational Semantics through Categorical Logic.
Proceedings of 23rd Annual IEEE Symposium on Logic in Computer Science (LICS 2008), pages 166177. doi:10.1109/LICS.2008.43.
[preprint: pdf]

S. Staton.
NamePassing Process Calculi: Operational Models and Structural Operational Semantics.
PhD thesis. Girton College, Cambridge.
Supervised by Marcelo Fiore,
and examined by Gordon Plotkin and Andrew Pitts.
Computer Laboratory Technical Report UCAMCLTR688.
[Thesis summary: pdf]

M. P. Fiore and S. Staton.
A Congruence Rule Format for NamePassing Process Calculi from Mathematical Operational Semantics.
Proceedings of 21st Annual IEEE Symposium on Logic in Computer Science (LICS 2006), pages 4958. doi:10.1109/LICS.2006.7.
[preprint: pdf]

M. P. Fiore and S. Staton.
Comparing operational models of namepassing process calculi.
Information and Computation Vol 204, Issue 4 (April 2006),
Pages 524560. doi:10.1016/j.ic.2005.08.004.
[preprint: pdf].
Preliminary version in Proceedings of
7th International Workshop on Coalgebraic Methods
in Computer Science (CMCS'04).
Electron. Notes Theor. Comput. Sci. 106:91104. doi:10.1016/j.entcs.2004.02.025.
[preprint: pdf]
Students and RAs
Courses taught:
Principles of Programming Languages.
A course
on coalgebra jointly
with Alexandra Silva in Nijmegen;
Courses on
Discrete mathematics I,
Semantics of programming languages, and
Category theory and logic in Cambridge.
Responsibilities and events
I currently coorganize
the OASIS
seminars in Oxford.
Steering committees:
IEEE Symposium on Logic in Computer Science
(LICS);
Formal Structures in Computation and Deduction
(FSCD).
Programme committee member:
34th Conference on Mathematical Foundations of Programming Semantics (MFPS XXXIV), PC chair;
42nd International Symposium on Mathematical Foundations of Computer
Science
(MFCS 2017);
44th ACM SIGPLANSIGACT Symposium on Principles of Programming
Languages
(POPL 2017);
26th European Symposium on Programming
(ESOP 2017);
Workshop on Syntax and Semantics of Lowlevel Languages
(LOLA 2016);
10th International Workshop on Fixed Points in Computer Science
(FICS 2015);
6th Conference on Algebra and Coalgebra in Computer Science (CALCO 2015);
30th Conference on Mathematical Foundations of Programming Semantics (MFPS XXX), PC cochair;
3rd ACMSIGPLAN Workshop on HigherOrder Programming with Effects (HOPE 2014);
Combined 21st International Workshop on Expressiveness in Concurrency and 11th Workshop on Structured Operational Semantics
(EXPRESS/SOS 2014);
11th International Workshop on Domain Theory and Applications (Domains XI);
18th ACM SIGPLAN International Conference on Functional Programming (ICFP 2013);
Workshop on Syntax and Semantics of LowLevel Languages (LOLA 2013);
5th Conference on Algebra and Coalgebra in Computer Science (CALCO 2013);
21st Conference
on Computer Science Logic (CSL 2012), 4th Workshop on Mathematically
Structured Functional Programming (MSFP 2012); 11th International
Workshop on Coalgebraic Methods in Computer Science (CMCS 2012); 9th
Asian Symposium on Programming Languages and Systems (APLAS 2011);
4th Conference on Algebra and Coalgebra (CALCO 2011); 8th
International Workshop on Structural Operational Semantics (SOS 2011);
7th International Workshop on Structural Operational Semantics (SOS 2010). External review committee of 39th ACM SIGPLANSIGACT Symposium
on Principles of Programming Languages (POPL 2012).
Organizing committees:
Local organizer:
LICS 2018;
FSCD 2017;
CALCO 2015
and MFPS XXXI;
International Conference on Category Theory (CT 2014);
Informal Workshop on Programming with Handlers (Cambridge June 2013).
Some recent/upcoming invited talks:
ICALP 2018;
Logic and learning 2018;
British Logic Colloquium 2017;
Uncertainty
in Computation, 2016;
QSLC 2016;
WIP 2016;
MFPS 2016;
CHOCOLA, Jan 2016;
SREPLS2, Nov 2015;
MFPS 2015.