betaFeedback

WorksComputer Science

On the semantics of conditional branching

Abstract

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.

2012 ACM Subject Classification Theory of computation →\to Denotational semantics; Theory of computation →\to Categorical semantics; Theory of computation →\to Axiomatic semantics; Theory of computation →\to Program verification; Theory of computation →\to Probabilistic computation

Introduction

Motivation. The ideas and results presented in this work originate from a simple observation about the semantics of probabilistic programs. If one follows the classic semantics proposed by Kozen either in terms of forward state (i.e. measure) transformer [22], or in terms of backwards predicate (i.e. function) transformer [23], one inevitably lands in a semantic world of vector spaces and operators. This naturally leads to a linear perspective on probabilistic programs where states cannot be copied, or at least not in a way that is compatible with higher order computations [10]. In other words, randomness is seen as a resource.

However, there is one fundamental construct with respect to which randomness does not behave as a resource: conditional branching, that is to say if-then-else statements. Consider for example the following simple imperative program

if x >0 then x = x +1 else x = x -1

Following [22], this program is interpreted as a linear operator on the Banach space of input distributions on xx. Given such an input state μ\mu, the semantics of the program will:

  1. split μ\mu into two subdistributions, one satisfying the guard and the other its complement,

  2. apply the if branch (+1)(+1) to the first subdistribution, the else branch (−1)(-1) to the second,

  3. finally, recombine the two branches (via pointwise addition) to produce the output.

The remarkable fact is that, despite being a fundamentally linear semantics, the initial state μ\mu is not consumed by the evaluation of the guard x>0x > 0. In fact, the guard is not evaluated at all in the sense that no boolean value or even convex combination thereof is produced. The splitting-recombining mechanism provides a linear alternative to guard evaluation that allows each branch to access the (relevant part of the) input state.

The situation is very similar in the quantum case, although it is complicated by the existence of two fundamentally different notions of conditional branching. The first is coherent or quantum branching, where the guard is itself a quantum system and no measurement is performed. A canonical example is the CNOT gate, where the control qubit determines which branch is taken while remaining available and un-measured. Semantically, this type of branching can be understood as an instance of the mechanism we have just described: the quantum state is split and then recombined as a superposition of two control paths (the if and else branches), each transformed independently. The other notion is measurement-based branching, where the guard is evaluated by measuring a quantum system and the branch is selected by the resulting classical outcome. Here the measurement irreversibly changes the observed qubits and may alter any entanglement between them and the rest of the system.

The state-splitting mechanism of probabilistic and coherent control is different both from the classical interpretation of conditional branching [15] where the state/context is copied, with one copy used to evaluate the guard and the other to continue the computation, and from the linear interpretation of conditional branching where evaluating the guard consumes the state/context making it unavailable for the rest of the computation (as is the case in measurement-based quantum control [28]). There are thus at least three incomparable ways of interpreting if-then-else statements, which raises the following questions:

  1. Can we reconcile these different interpretations of conditional branching?

  2. More generally, what is the ‘minimal’ structure needed to interpret if-then-else?

  3. What program equivalences can we expect of a general interpretation of conditionals?

Answering these questions is about a lot more than clarifying an interesting quirk of probabilistic program semantics, if-then-else statements are fundamental to the practice of programming and we should endeavour to interpret and understand them in the widest possible context. Concretely, this means that given any programming paradigm, say probabilistic hybrid computations with exceptions, we should be able to work out (a) what (if any) interpretations of conditional branching it can support, and (b) what kind of program equivalences can be shown for these interpretations. For instance does if b then p else q ≡ if not b then q else p hold? What does not even mean?

The objective of this work is to provide tools for answering these questions. As a short slogan: we aim to provide a semantic structure that does for conditional branching what traced monoidal categories did for recursion and iteration.

Contributions and structure of the paper. In § 2 we review the various semantics of conditional branching that can be found ‘in the wild’: the classical interpretation via copying and distributing (§ 2.1), the linear and mixed interpretations (§ 2.2), the probabilistic ‘state-splitting’ approach (§ 2.3), and coherent control (§ 2.4). In § 3 we introduce and justify the notion of conditionally branching category as a semantic structure in which if-then-else statements can be interpreted in a way that follows (some of) the standard axioms governing the behaviour of if-then-else statements. In § 4 we provide examples of conditionally branching categories including domain-theoretic models of call-by-value computations, Markov categories [14], models of effectful computations [27], and the motivating vector-space models for which we present a very general state-splitting result (§ 4.2). Finally, in § 5 we will see that a lot of structural mileage can be obtained from the humble coproduct. We study the structure of the set of branching morphisms, i.e. morphisms of the shape X→X+XX \to X + X in § 5.1 and of the set of tests, i.e. morphisms of the shape X→1+1X \to1 + 1 in § 5.2. Finally, in § 5.3 we examine the skew-associativity rule associated with one of the more complex behaviours of conditional branching that sometimes allows us to re-write nested if-then-else statements. We show that the skew-associativity axiom of Guarded Kleene Algebras with Tests [34] and the seemingly unrelated skew-associativity axiom of barycentric algebras [26] are two instances of a general skew-associativity rule.

Notation and terminology. We will be using a generic typed functional language and consider typing judgements Γ⊢s:T\Gamma\vdash s : T interpreted as morphisms [ ⁣[s] ⁣]:[ ⁣[Γ] ⁣]→[ ⁣[T] ⁣][\![s]\!] : [\![\Gamma]\!] \to[\![T]\!] in a category C\mathcal{C}. We will be concerned with such a small language fragment (just what is needed to talk about if-then-else) that we choose not to specify a full syntax and semantics but rather introduce constructs if and when needed. We assume that the type grammar contains a unit type 11 and coproduct types S+TS + T. Term formation thus includes the typing rules:

Γ⊢s:SΓ⊢in⁡(1,s):S+TΓ⊢s:TΓ⊢in⁡(2,s):S+TΓ⊢s:S1+S2x:S1,Δ⊢u:Ty:S2,Δ⊢v:TΓ,Δ⊢case⁡ s of⁡ (in⁡(1,x)⇒u,in⁡(2,y)⇒v):T(1)\begin{aligned} &\frac{\Gamma\vdash s : S}{\Gamma\vdash\operatorname{in}(1,s) : S + T} \qquad \frac{\Gamma\vdash s : T}{\Gamma\vdash\operatorname{in}(2,s) : S + T} \\ &\frac{\Gamma\vdash s : S_1 + S_2 \qquad x : S_1,\Delta\vdash u : T \qquad y : S_2,\Delta\vdash v : T} {\Gamma,\Delta\vdash\operatorname{case}\ s\ \operatorname{of}\ (\operatorname{in}(1,x) \Rightarrow u,\operatorname{in}(2,y) \Rightarrow v) : T} \tag*{(1)} \end{aligned}

The pattern-matching rule above is linear: contexts are consumed by computations. We will not assume that the categories in which programs are interpreted are Cartesian, we will only assume that they are monoidal, as is the case for vector-space models of probabilistic and quantum computations, as well as many examples of effectful computations. However, guided by the probabilistic and quantum examples given in the introduction, this paper will revolve around understanding the semantics of the following if-then-else-rule:

Γ⊢p:(1+1)Γ,Δ⊢s:TΓ,Δ⊢t:TΓ,Δ⊢if⁡ p then⁡ s else⁡ t:T(2)\frac{\Gamma\vdash p : (1 + 1) \qquad\Gamma,\Delta\vdash s : T \qquad\Gamma,\Delta\vdash t : T} {\Gamma,\Delta\vdash\operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ t : T} \tag*{(2)}

where the context Γ\Gamma is now used in a non-linear manner: the program pp does not consume the context in (2), it is still available to ss and tt. In other words, we will not view if⁡ p then⁡ s else⁡ t\operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ t as syntactic sugar for instances of the pattern-matching rule (1) of the shape Γ,Δ⊢case⁡ p of⁡ (in⁡(1,x)⇒s,in⁡(2,x)⇒t)\Gamma,\Delta\vdash\operatorname{case}\ p\ \operatorname{of}\ (\operatorname{in}(1,x) \Rightarrow s,\operatorname{in}(2,x) \Rightarrow t) with a guard Γ⊢p:1+1\Gamma\vdash p : 1 + 1. Note that this context-consuming type of branching will nevertheless always be available to us as well, by virtue of the existence of (1). We will call programs of type 1+11 + 1 predicates [18] or tests [24]. In the context of a program if⁡ p then⁡ s else⁡ t\operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ t, the predicate pp will be referred to as the guard.

We assume basic knowledge of category theory and use the standard notations π1\pi_1, π2\pi_2 and in⁡1\operatorname{in}_1, in⁡2\operatorname{in}_2 for the first and second projection and coprojections respectively, ⟨f,g⟩\langle f,g\rangle and [f,g][f,g] for the pairing and copairing of morphisms, f×g≔⟨f∘π1,g∘π2⟩f \times g \coloneqq\langle f \circ\pi_1,g \circ\pi_2\rangle and f+g≔[in⁡1∘f,in⁡2∘g]f + g \coloneqq[\operatorname{in}_1 \circ f,\operatorname{in}_2 \circ g], and finally ΔX≔⟨id⁡X,id⁡X⟩:X→X×X\Delta_X \coloneqq\langle\operatorname{id}_X,\operatorname{id}_X\rangle: X \to X \times X and ∇X≔[id⁡X,id⁡X]:X+X→X\nabla_X \coloneqq[\operatorname{id}_X,\operatorname{id}_X] : X + X \to X for the diagonal and codiagonal morphisms respectively.

Semantics of if-then-else in the wild

Classical branching by copying and distributing

Vanilla flavour. The standard way of interpreting the if-then-else rule (2) involves copying the context, using one copy to evaluate the guard and the other to continue the computation. This can be formalised in any distributive category [15], that is to say in any category C\mathcal{C} with finite products and coproducts such that for any C\mathcal{C}-objects A,B,CA,B,C the canonical morphism

[id⁡A×in⁡1,id⁡A×in⁡2]:(A×B)+(A×C)→A×(B+C)[\operatorname{id}_A \times\operatorname{in}_1,\operatorname{id}_A \times\operatorname{in}_2] : (A \times B) + (A \times C) \to A \times(B + C)

is an isomorphism. We write distr⁡A,B,C:A×(B+C)→(A×B)+(A×C)\operatorname{distr}_{A,B,C} : A \times(B + C) \to(A \times B) + (A \times C) for its inverse. Similarly, we will write distr⁡A,B,C:(B+C)×A→(B×A)+(C×A)\operatorname{distr}_{A,B,C} : (B + C) \times A \to(B \times A) + (C \times A) for the right-distributivity isomorphism. In the case that interests us the most B=C=1B = C = 1 and we will therefore simply write distr⁡A:A×(1+1)→(A×1)+(A×1)≅A+A\operatorname{distr}_A : A \times(1 + 1) \to(A \times1) + (A \times1) \cong A + A. In this non-linear/Cartesian context (2) simplifies to

Γ⊢p:(1+1)Γ⊢s:TΓ⊢t:TΓ⊢if⁡ p then⁡ s else⁡ t:T(3)\frac{\Gamma\vdash p : (1 + 1) \qquad\Gamma\vdash s : T \qquad\Gamma\vdash t : T} {\Gamma\vdash\operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ t : T} \tag*{(3)}

Given a distributive category C\mathcal{C}, the conclusion of the typing rule (3) is interpreted as

⟦Γ⟧→Δ⟦Γ⟧⟦Γ⟧×⟦Γ⟧→id×⟦p⟧⟦Γ⟧×(1+1)→ldistr⁡⟦Γ⟧⟦Γ⟧+⟦Γ⟧→[⟦s⟧,⟦t⟧]⟦T⟧(4)\llbracket\Gamma\rrbracket\xrightarrow{\Delta_{\llbracket\Gamma\rrbracket}} \llbracket\Gamma\rrbracket\times\llbracket\Gamma\rrbracket\xrightarrow{\mathrm{id}\times\llbracket p\rrbracket} \llbracket\Gamma\rrbracket\times(1+1) \xrightarrow{\operatorname{ldistr}_{\llbracket\Gamma\rrbracket}} \llbracket\Gamma\rrbracket+\llbracket\Gamma\rrbracket\xrightarrow{[\llbracket s\rrbracket,\llbracket t\rrbracket]} \llbracket T\rrbracket \tag*{(4)}

Whilst this is a natural and intuitive semantics, many categories that are important for the semantics of programs fail to be distributive.

Example 1. Non-deterministic computations are often interpreted in the Kleisli category of the powerset monad on Set, which is equivalent to the category Rel of sets and relations. In Rel, products and coproducts are both given by disjoint union [7 §5.4.7] and the category is therefore not distributive: 1×(1+1)1 \times(1+1) has three elements whereas (1×1)+(1×1)(1 \times1)+(1 \times1) has four.

Example 2. Another important example is the category ωCPO\omega\mathrm{CPO} of pointed ω\omega-complete partial order, or ω\omega-cpos, and monotone maps. This category does not have coproducts [35] and in particular cannot be distributive. If we restrict ourselves to the sub-category ωCPO⊥\omega\mathrm{CPO}_{\perp} of ω\omega-cpos and strict morphisms, then coproducts do exist and are given by the carriers A+B=(A∖{⊥A})+(B∖{⊥B})+{⊥}A+B=(A\setminus\{\perp_A\})+(B\setminus\{\perp_B\})+\{\perp\} with the order inherited from AA, BB (sometimes known as the coalesced sum). Products are constructed by taking the Cartesian product of the carriers together with the pointwise order. However, ωCPO⊥\omega\mathrm{CPO}_{\perp} is not distributive as a cardinality argument shows: if we consider the chain 22 then 2×(2+2)2 \times(2+2) has 2×((2−1)+(2−1)+1)=62 \times((2-1)+(2-1)+1)=6 elements but (2×2)+(2×2)(2 \times2)+(2 \times2) has ((2×2)−1)+((2×2)−1)+1=7((2 \times2)-1)+((2 \times2)-1)+1=7 elements.

Example 3. Real-weighted (including probabilistic) computations can be interpreted in the category Vec of vector spaces and linear maps. Vec is not distributive for a reason that is similar to Rel, namely because the coproduct is given by the direct sum which is isomorphic to the Cartesian product in finite dimensions.

We show in § 4 that these non-distributive examples do support a semantics for if-then-else.

Monadic flavour. The copy-and-distribute approach can be extended straightforwardly to effectful computations à la Moggi [27]. This is done in [18, 19] which is probably the line of research that is closest to this work, although it focuses exclusively on Cartesian categories. Given a distributive category C\mathcal{C} and a strong monad T:C→CT:\mathcal{C}\to\mathcal{C}, we can consider predicates in the Kleisli category of TT, i.e. C\mathcal{C}-morphisms p:X→T(1+1)p:X\to T(1+1). Given such a predicate, [18, 19] defines the associated instrument as the morphism instr⁡p:X→T(X+X)\operatorname{instr}_p:X\to T(X+X) defined as

X→⟨id,p⟩X×T(1+1)→strT(X×(1+1))→Tldistr⁡T(X+X)X \xrightarrow{\langle\mathrm{id},p\rangle} X \times T(1+1) \xrightarrow{\mathrm{str}} T(X \times(1+1)) \xrightarrow{T\operatorname{ldistr}} T(X+X)

With this special morphism (that we generalise in § 3), the semantics of (3) is given by ⟦if p then s else t⟧≜[⟦s⟧,⟦t⟧]∘instr⁡⟦p⟧\llbracket\text{if }p\text{ then }s\text{ else }t\rrbracket\triangleq[\llbracket s\rrbracket,\llbracket t\rrbracket]\circ\operatorname{instr}_{\llbracket p\rrbracket} (where composition is taken in the Kleisli category). We return to this construction in more detail in § 4.1.

Linear and mixed branching

The linear case. In the context of a linear language equipped with the injections and pattern-matching rules (1), if-then-else is often understood in the context-consuming sense described in § 1, that is to say as syntactic sugar for pattern-matching (e.g. [28, 36]):

if p then s else t≜case p of (in⁡(1,x)⇒s,in⁡(2,x)⇒t)(5)\text{if }p\text{ then }s\text{ else }t \triangleq\text{case }p\text{ of }(\operatorname{in}(1,x)\Rightarrow s,\operatorname{in}(2,x)\Rightarrow t) \tag*{(5)}

References

  1. [1]Jiří Adámek, Stefan Milius, and Jiří Velebil. Iterative algebras at work. Mathematical Structures in Computer Science, 16(6):1085–1131, 2006.DOI
  2. [2]Jiří Adámek, Stefan Milius, and Jiří Velebil. Elgot theories: a new perspective of iteration theories. Electronic Notes in Theoretical Computer Science, 249:407–427, 2009.DOI
  3. [3]Charalambos D Aliprantis and Kim C Border. Infinite dimensional analysis: a hitchhiker’s guide. Springer, 2006.
  4. [4]Charalambos D Aliprantis and Owen Burkinshaw. Positive operators, volume 119. Springer Science & Business Media, 2006.
  5. [5]Thorsten Altenkirch and Jonathan Grattage. A functional quantum programming language. In 20th Annual IEEE Symposium on Logic in Computer Science (LICS’05), pages 249–258. IEEE, 2005.
  6. [6]Thorsten Altenkirch, Jonathan Grattage, Juliana K Vizzotto, and Amr Sabry. An algebra of pure quantum programming. Electronic Notes in Theoretical Computer Science, 170:23–47, 2007.DOI
  7. [7]Michael Barr and Charles Wells. Category theory for computing science, volume 1. Prentice Hall New York, 1990.
  8. [8]Kenta Cho and Bart Jacobs. Disintegration and bayesian inversion via string diagrams. Mathematical Structures in Computer Science, 29(7):938–971, 2019.DOI
  9. [9]J Robin B Cockett and Stephen Lack. Restriction categories i: categories of partial maps. Theoretical computer science, 270(1-2):223–259, 2002.DOI
  10. [10]Fredrik Dahlqvist and Dexter Kozen. Semantics of higher-order probabilistic programs with conditioning. In Proc. 47th ACM SIGPLAN Symp. Principles of Programming Languages (POPL’20), pages 57:1–29, New Orleans, January 2020. ACM.arxiv.org/abs/1902.11189
  11. [11]Fredrik Dahlqvist, Louis Parlant, and Alexandra Silva. Layer by layer–combining monads. In Theoretical Aspects of Computing – ICTAC 2018: 15th International Colloquium, Stellenbosch, South Africa, October 16–19, 2018, Proceedings 15, pages 153–172. Springer, 2018.arxiv.org/abs/1712.01113
  12. [12]Fredrik Dahlqvist, Alexandra Silva, Vincent Danos, and Ilias Garnier. Borel kernels and their approximation, categorically. Electronic Notes in Theoretical Computer Science, 341:91–119, 2018.
  13. [13]Calvin C Elgot. Monadic computation and iterative algebraic theories. In Studies in Logic and the Foundations of Mathematics, volume 80, pages 175–230. Elsevier, 1975.
  14. [14]Tobias Fritz. A synthetic approach to markov kernels, conditional independence and theorems on sufficient statistics. Advances in Mathematics, 370:107239, 2020.DOI
  15. [15]Jeremy Gibbons. Conditionals in distributive categories. Technical report, CMS-TR-97-01, School of Computing and Mathematical Sciences, Oxford Brookes, 1997.
  16. [16]Masahito Hasegawa. The uniformity principle on traced monoidal categories. Publications of the Research Institute for Mathematical Sciences, 40(3):991–1014, 2004.
  17. [17]Chris Heunen, Robin Kaarsgaard, and Louis Lemonnier. One rig to control them all. arXiv preprint arXiv:2510.05032, 2025.DOI
  18. [18]Bart Jacobs. New directions in categorical logic, for classical, probabilistic and quantum logic. Logical Methods in Computer Science, 11, 2015.DOI
  19. [19]Bart Jacobs. Affine monads and side-effect-freeness. In Coalgebraic Methods in Computer Science: 13th IFIP WG 1.3 International Workshop, CMCS 2016, Colocated with ETAPS 2016, Eindhoven, The Netherlands, April 2-3, 2016, Revised Selected Papers 13, pages 53–72. Springer, 2016.DOI
  20. [20]Gregory Maxwell Kelly. Basic concepts of enriched category theory, volume 64. CUP Archive, 1982.
  21. [21]Anders Kock. Strong functors and monoidal monads. Archiv der Mathematik, 23:113–120, 1972.DOI
  22. [22]Dexter Kozen. Semantics of probabilistic programs. In Proc. 20th Symp. Found. Comput. Sci., pages 101–114. IEEE, October 1979.
  23. [23]Dexter Kozen. A probabilistic PDL. J. Comput. Syst. Sci. 30(2):162–178, April 1985.
  24. [24]Dexter Kozen. Kleene algebra with tests. ACM Transactions on Programming Languages and Systems (TOPLAS), 19(3):427–443, 1997.DOI
  25. [25]Gerhart Lüders. Concerning the state-change due to the measurement process. Annalen der Physik, 518(9):663–670, 2006.
  26. [26]Radu Mandara, Prakash Panangaden, and Gordon Plotkin. Quantitative algebraic reasoning. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, pages 700–709, 2016.
  27. [27]Eugenio Moggi. Notions of computation and monads. Information and computation, 93(1):55–92, 1991.DOI
  28. [28]Michele Pagani, Peter Selinger, and Benoît Valiron. Applying quantitative semantics to higher-order quantum computing. In Proceedings of the 41st ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, pages 647–658, 2014.
  29. [29]Benjamin C Pierce. Types and programming languages. MIT press, 2002.
  30. [30]John Power and Edmund Robinson. Premonoidal categories and notions of computation. Mathematical structures in computer science, 7(5):453–468, 1997.DOI
  31. [31]Peter Selinger. Towards a semantics for higher-order quantum computation. In Proceedings of the 2nd International Workshop on Quantum Programming Languages, TUCS General Publication, volume 33, pages 127–143, 2004.
  32. [32]Peter Selinger and Benoît Valiron. A lambda calculus for quantum computation with classical control. Mathematical Structures in Computer Science, 16(3):527–552, 2006.
  33. [33]Peter Selinger, Benoit Valiron, et al. Quantum lambda calculus. Semantic techniques in quantum computation, pages 135–172, 2009.DOI
  34. [34]Steffen Smolka, Nate Foster, Justin Hsu, Tobias Kappé, Dexter Kozen, and Alexandra Silva. Guarded Kleene algebra with tests: Verification of uninterpreted programs in nearly linear time. In Proc. 47th ACM SIGPLAN Symp. Principles of Programming Languages (POPL’20), pages 61:1–28, New Orleans, January 2020. ACM.
  35. [35]Michael B Smyth and Gordon D Plotkin. The category-theoretic solution of recursive domain equations. SIAM Journal on Computing, 11(4):761–783, 1982.
  36. [36]Sam Staton. Commutative semantics for probabilistic programming. In Programming Languages and Systems: 26th European Symposium on Programming, ESOP 2017, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2017, Uppsala, Sweden, April 22–29, 2017, Proceedings 26, pages 855–879. Springer, 2017.DOI
  37. [37]Benoît Valiron. Semantics of quantum programming languages: Classical control, quantum control. Journal of Logical and Algebraic Methods in Programming, 128:100790, 2022.
  38. [38]Adriaan C Zaanen. Introduction to operator theory in Riesz spaces. Springer Science & Business Media, 2012.

Paper details

vlnc:W_4mqvfwx6
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 10

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents