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 x x x . Given such an input state μ \mu μ , the semantics of the program will:
split μ \mu μ into two subdistributions, one satisfying the guard and the other its complement,
apply the if branch ( + 1 ) (+1) ( + 1 ) to the first subdistribution, the else branch ( − 1 ) (-1) ( − 1 ) to the second,
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 > 0 x > 0 x > 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:
Can we reconcile these different interpretations of conditional branching?
More generally, what is the ‘minimal’ structure needed to interpret if-then-else?
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 + X X \to X + X X → X + X in § 5.1 and of the set of tests , i.e. morphisms of the shape X → 1 + 1 X \to1 + 1 X → 1 + 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 Γ ⊢ s : T interpreted as morphisms [ [ s ] ] : [ [ Γ ] ] → [ [ T ] ] [\![s]\!] : [\![\Gamma]\!] \to[\![T]\!] [ [ s ] ] : [ [ Γ ] ] → [ [ T ] ] in a category C \mathcal{C} 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 1 1 1 and coproduct types S + T S + T S + T . Term formation thus includes the typing rules:
Γ ⊢ s : S Γ ⊢ in ( 1 , s ) : S + T Γ ⊢ s : T Γ ⊢ in ( 2 , s ) : S + T Γ ⊢ s : S 1 + S 2 x : S 1 , Δ ⊢ u : T y : S 2 , Δ ⊢ 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} Γ ⊢ in ( 1 , s ) : S + T Γ ⊢ s : S Γ ⊢ in ( 2 , s ) : S + T Γ ⊢ s : T Γ , Δ ⊢ case s of ( in ( 1 , x ) ⇒ u , in ( 2 , y ) ⇒ v ) : T Γ ⊢ s : S 1 + S 2 x : S 1 , Δ ⊢ u : T y : S 2 , Δ ⊢ v : T (1)
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)} Γ , Δ ⊢ if p then s else t : T Γ ⊢ p : ( 1 + 1 ) Γ , Δ ⊢ s : T Γ , Δ ⊢ t : T (2)
where the context Γ \Gamma Γ is now used in a non-linear manner: the program p p p does not consume the context in (2), it is still available to s s s and t t t . In other words, we will not view if p then s else t \operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ t if p then s 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) Γ , Δ ⊢ case p of ( in ( 1 , x ) ⇒ s , in ( 2 , x ) ⇒ t ) with a guard Γ ⊢ p : 1 + 1 \Gamma\vdash p : 1 + 1 Γ ⊢ 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 + 1 1 + 1 1 + 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 if p then s else t , the predicate p p p will be referred to as the guard .
We assume basic knowledge of category theory and use the standard notations π 1 \pi_1 π 1 , π 2 \pi_2 π 2 and in 1 \operatorname{in}_1 in 1 , in 2 \operatorname{in}_2 in 2 for the first and second projection and coprojections respectively, ⟨ f , g ⟩ \langle f,g\rangle ⟨ f , g ⟩ and [ f , g ] [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 f × g : = ⟨ f ∘ π 1 , g ∘ π 2 ⟩ and f + g ≔ [ in 1 ∘ f , in 2 ∘ g ] f + g \coloneqq[\operatorname{in}_1 \circ f,\operatorname{in}_2 \circ g] f + g : = [ in 1 ∘ f , in 2 ∘ 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 Δ X : = ⟨ id X , id X ⟩ : X → X × X and ∇ X ≔ [ id X , id X ] : X + X → X \nabla_X \coloneqq[\operatorname{id}_X,\operatorname{id}_X] : X + X \to X ∇ X : = [ id X , id X ] : X + X → 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} C with finite products and coproducts such that for any C \mathcal{C} C -objects A , B , C A,B,C A , 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) [ id A × in 1 , id A × in 2 ] : ( A × B ) + ( A × C ) → A × ( 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) distr A , B , C : A × ( B + C ) → ( A × B ) + ( A × 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) distr A , B , C : ( B + C ) × A → ( B × A ) + ( C × A ) for the right-distributivity isomorphism. In the case that interests us the most B = C = 1 B = C = 1 B = 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 distr A : A × ( 1 + 1 ) → ( A × 1 ) + ( A × 1 ) ≅ 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)} Γ ⊢ if p then s else t : T Γ ⊢ p : ( 1 + 1 ) Γ ⊢ s : T Γ ⊢ t : T (3)
Given a distributive category C \mathcal{C} C , the conclusion of the typing rule (3) is interpreted as
⟦ Γ ⟧ → Δ ⟦ Γ ⟧ ⟦ Γ ⟧ × ⟦ Γ ⟧ → i d × ⟦ 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)} [ [ Γ ] ] Δ [ [ Γ ] ] [ [ Γ ] ] × [ [ Γ ] ] id × [ [ p ] ] [ [ Γ ] ] × ( 1 + 1 ) ldistr [ [ Γ ] ] [ [ Γ ] ] + [ [ Γ ] ] [ [ [ s ] ] , [ [ t ] ] ] [ [ T ] ] (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) 1 × ( 1 + 1 ) has three elements whereas ( 1 × 1 ) + ( 1 × 1 ) (1 \times1)+(1 \times1) ( 1 × 1 ) + ( 1 × 1 ) has four.
Example 2. Another important example is the category ω C P O \omega\mathrm{CPO} ω 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 ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ 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\} A + B = ( A ∖ { ⊥ A }) + ( B ∖ { ⊥ B }) + { ⊥ } with the order inherited from A A A , B B B (sometimes known as the coalesced sum). Products are constructed by taking the Cartesian product of the carriers together with the pointwise order. However, ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ is not distributive as a cardinality argument shows: if we consider the chain 2 2 2 then 2 × ( 2 + 2 ) 2 \times(2+2) 2 × ( 2 + 2 ) has 2 × ( ( 2 − 1 ) + ( 2 − 1 ) + 1 ) = 6 2 \times((2-1)+(2-1)+1)=6 2 × (( 2 − 1 ) + ( 2 − 1 ) + 1 ) = 6 elements but ( 2 × 2 ) + ( 2 × 2 ) (2 \times2)+(2 \times2) ( 2 × 2 ) + ( 2 × 2 ) has ( ( 2 × 2 ) − 1 ) + ( ( 2 × 2 ) − 1 ) + 1 = 7 ((2 \times2)-1)+((2 \times2)-1)+1=7 (( 2 × 2 ) − 1 ) + (( 2 × 2 ) − 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} C and a strong monad T : C → C T:\mathcal{C}\to\mathcal{C} T : C → C , we can consider predicates in the Kleisli category of T T T , i.e. C \mathcal{C} C -morphisms p : X → T ( 1 + 1 ) p:X\to T(1+1) p : X → 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) instr p : X → T ( X + X ) defined as
X → ⟨ i d , p ⟩ X × T ( 1 + 1 ) → s t r T ( X × ( 1 + 1 ) ) → T ldistr 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) X ⟨ id , p ⟩ X × T ( 1 + 1 ) str T ( X × ( 1 + 1 )) T 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} [ [ if p then s else t ] ] ≜ [ [ [ s ] ] , [ [ t ] ] ] ∘ instr [ [ p ] ] (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)} if p then s else t ≜ case p of ( in ( 1 , x ) ⇒ s , in ( 2 , x ) ⇒ t ) (5)
One can interpret (5) in any distributive monoidal category ( C , ⊗ , I , + ) (\mathcal{C},\otimes,I,+) ( C , ⊗ , I , + ) , i.e. a monoidal category that has coproducts and isomorphisms ldistr A , B , C : A ⊗ ( B + C ) → ( A ⊗ B ) + ( A ⊗ C ) \operatorname{ldistr}_{A,B,C}:A\otimes(B+C)\to(A\otimes B)+(A\otimes C) ldistr A , B , C : A ⊗ ( B + C ) → ( A ⊗ B ) + ( A ⊗ C ) and rdistr A , B , C : ( B + C ) ⊗ A → ( B ⊗ A ) + ( C ⊗ A ) \operatorname{rdistr}_{A,B,C} : (B + C) \otimes A \to(B \otimes A) + (C \otimes A) rdistr A , B , C : ( B + C ) ⊗ A → ( B ⊗ A ) + ( C ⊗ A ) via:
⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ → ⟦ p ⟧ ⊗ id ( ⟦ S 1 ⟧ + ⟦ S 2 ⟧ ) ⊗ ⟦ Δ ⟧ → rdistr ⟦ Δ ⟧ ⊗ ⟦ S 1 ⟧ + ⟦ Δ ⟧ ⊗ ⟦ S 2 ⟧ → [ ⟦ s ⟧ , ⟦ t ⟧ ] ⟦ T ⟧ (6) \llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket\xrightarrow{\llbracket p \rrbracket\otimes\operatorname{id}} (\llbracket S_1 \rrbracket+ \llbracket S_2 \rrbracket) \otimes\llbracket\Delta\rrbracket\xrightarrow{\operatorname{rdistr}} \llbracket\Delta\rrbracket\otimes\llbracket S_1 \rrbracket+ \llbracket\Delta\rrbracket\otimes\llbracket S_2 \rrbracket\xrightarrow{[\llbracket s \rrbracket,\llbracket t \rrbracket]} \llbracket T \rrbracket \tag*{(6)} [ [ Γ ] ] ⊗ [ [ Δ ] ] [ [ p ] ] ⊗ id ( [ [ S 1 ] ] + [ [ S 2 ] ] ) ⊗ [ [ Δ ] ] rdistr [ [ Δ ] ] ⊗ [ [ S 1 ] ] + [ [ Δ ] ] ⊗ [ [ S 2 ] ] [ [ [ s ] ] , [ [ t ] ] ] [ [ T ] ] (6)
Since (6) interprets an instance of (1), the variables used by the programs s , t s,t s , t are not available to the guard p p p . This is arguably not how if-then-else statements are intuitively understood or used in practice. Indeed, the point of conditional branching is typically to apply different procedures to variables depending on a predicate on these same variables. Thus whilst we acknowledge that (5) provides a possible interpretation for if-then-else statements – and as discussed in the introduction this interpretation will always be available to us – we will be concerned with the interpretation of the non-linear branching rule (2).
The mixed case. There exists a half-way house between the non-linear copy-and-distribute mechanism and the purely linear one that is used when both non-linear (duplicable) and linear (non-duplicable) types coexist. Formally, consider a distributive monoidal category ( C , ⊗ , I , + ) (\mathcal{C}, \otimes, I, +) ( C , ⊗ , I , + ) that is equipped with an exponential comonad ! ! ! satisfying the usual requirements and defining copiable types ! A !A ! A . The rule (2) can then be modified into:
! Γ , Δ ⊢ p : ( 1 + 1 ) ! Γ , E ⊢ s : T ! Γ , E ⊢ t : T ! Γ , Δ , E ⊢ if p then s else t : T (7) \frac{!\Gamma, \Delta\vdash p : (1 + 1) \qquad!\Gamma, E \vdash s : T \qquad!\Gamma, E \vdash t : T}{!\Gamma, \Delta, E \vdash\text{if }p\text{ then }s\text{ else }t : T} \tag*{(7)} ! Γ , Δ , E ⊢ if p then s else t : T ! Γ , Δ ⊢ p : ( 1 + 1 ) ! Γ , E ⊢ s : T ! Γ , E ⊢ t : T (7)
and be interpreted via the exponential’s comultiplication (i.e. copying map) δ : ! → ! ⊗ ! \delta: ! \to! \otimes! δ : ! → ! ⊗ ! as:
! ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ ⊗ ⟦ E ⟧ → ⟦ if p then s else t ⟧ ⟦ T ⟧ ↓ δ ⊗ id ⊗ id ↑ [ s , t ] ! ⟦ Γ ⟧ ⊗ ! ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ ⊗ ⟦ E ⟧ → id ⊗ ⟦ p ⟧ ⊗ id ! ⟦ Γ ⟧ ⊗ ( 1 + 1 ) ⊗ ⟦ E ⟧ → ldistr ∘ rdistr ! ⟦ Γ ⟧ ⊗ ⟦ E ⟧ + ! ⟦ Γ ⟧ ⊗ ⟦ E ⟧ \begin{aligned}
! \llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket\otimes\llbracket E \rrbracket&\xrightarrow{\llbracket\text{if }p\text{ then }s\text{ else }t \rrbracket} \llbracket T \rrbracket\\
\downarrow{\delta\otimes\operatorname{id}\otimes\operatorname{id}} \qquad&\qquad\uparrow{[s,t]} \\
! \llbracket\Gamma\rrbracket\otimes! \llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket\otimes\llbracket E \rrbracket&\xrightarrow{\operatorname{id}\otimes\llbracket p\rrbracket\otimes\operatorname{id}} ! \llbracket\Gamma\rrbracket\otimes(1+1) \otimes\llbracket E \rrbracket\xrightarrow{\operatorname{ldistr}\circ\operatorname{rdistr}} ! \llbracket\Gamma\rrbracket\otimes\llbracket E \rrbracket+ ! \llbracket\Gamma\rrbracket\otimes\llbracket E \rrbracket
\end{aligned} ! [ [ Γ ] ] ⊗ [ [ Δ ] ] ⊗ [ [ E ] ] ↓ δ ⊗ id ⊗ id ! [ [ Γ ] ] ⊗ ! [ [ Γ ] ] ⊗ [ [ Δ ] ] ⊗ [ [ E ] ] [ [ if p then s else t ] ] [ [ T ] ] ↑ [ s , t ] id ⊗ [ [ p ] ] ⊗ id ! [ [ Γ ] ] ⊗ ( 1 + 1 ) ⊗ [ [ E ] ] ldistr ∘ rdistr ! [ [ Γ ] ] ⊗ [ [ E ] ] + ! [ [ Γ ] ] ⊗ [ [ E ] ]
▶ Example 4. This is the semantics of the measurement-based branching of quantum computing, as defined for the quantum lambda calculus of [32 , 33 , 37 ] and interpreted in [28 ] and [37 ] (which specifically discusses branching). The context of the guard p p p consists of classical data that can be copied (! Γ !\Gamma ! Γ ) and quantum data (Δ \Delta Δ ) that cannot. In this model of measurement-based control, the quantum part of the input state gets collapsed by the measurement (i.e. by evaluating the guard) and is lost; only the result of the evaluation of the guard (which has type 1 + 1 1+1 1 + 1 ) is available to continue the computation.
Concretely, let us assume ground types qubit and bit ≜ 1 + 1 \triangleq1 + 1 ≜ 1 + 1 and built-in functions meas : qubit → bit \operatorname{meas} : \operatorname{qubit} \to\operatorname{bit} meas : qubit → bit and Z : qubit → qubit Z : \operatorname{qubit} \to\operatorname{qubit} Z : qubit → qubit interpreted in the category C P M ⊕ \mathrm{CPM}_{\oplus} CPM ⊕ whose objects are direct sums of finite-dimensional Hilbert spaces and whose morphisms are completely positive linear maps in the sense of [31 §3.2] . We can then consider the semantics of the instance of (7) (feed-forward correction) on two qubits x , y x,y x , y that measures the state of x x x , leaves y y y unchanged if ∣ 0 ⟩ \lvert0 \rangle ∣ 0 ⟩ is measured, or applies the Z Z Z gate to y y y if ∣ 1 ⟩ \lvert1 \rangle ∣ 1 ⟩ is measured:
x : qubit ⊢ meas ( x ) : bit y : qubit ⊢ y : qubit y : qubit ⊢ Z y : qubit x , y : qubit ⊢ if meas ( x ) then y else Z y : qubit \frac{x : \operatorname{qubit} \vdash\operatorname{meas}(x) : \operatorname{bit} \qquad y : \operatorname{qubit} \vdash y : \operatorname{qubit} \qquad y : \operatorname{qubit} \vdash Zy : \operatorname{qubit}}{x,y : \operatorname{qubit} \vdash\text{if }\operatorname{meas}(x)\text{ then }y\text{ else }Zy : \operatorname{qubit}} x , y : qubit ⊢ if meas ( x ) then y else Z y : qubit x : qubit ⊢ meas ( x ) : bit y : qubit ⊢ y : qubit y : qubit ⊢ Z y : qubit
The semantics of this program is given by (6) which yields for an input density (block) matrix
⟦ if meas ( x ) then y else Z y ⟧ ( A B C D ) ≜ [ id , ⟦ Z ⟧ ] ∘ ( ⟦ meas ⟧ ⊗ id ) ( A B C D ) = [ id , ⟦ Z ⟧ ] ( A , D ) = A + Z D Z † \begin{aligned}
\llbracket\text{if }\operatorname{meas}(x)\text{ then }y\text{ else }Zy \rrbracket\begin{pmatrix} A & B \\ C & D \end{pmatrix}
\triangleq[\operatorname{id},\llbracket Z \rrbracket]\circ(\llbracket\operatorname{meas}\rrbracket\otimes\operatorname{id})\begin{pmatrix} A & B \\ C & D \end{pmatrix} \\
&= [\operatorname{id},\llbracket Z \rrbracket](A,D)=A+ZDZ^\dagger
\end{aligned} [ [ if meas ( x ) then y else Z y ] ] ( A C B D ) ≜ [ id , [ [ Z ] ] ] ∘ ( [ [ meas ] ] ⊗ id ) ( A C B D ) = [ id , [ [ Z ] ] ] ( A , D ) = A + Z D Z †
Note the disappearance of the entanglement (represented by the blocks B , C B,C B , C ) due to the measurement of x x x . We will see in § 5.2 that the non-linear if-then-else rule (2) can alternatively be used and satisfactorily interpreted to describe measurement-based control.
Branching by splitting and merging
The motivating example presented in the introduction was that of probabilistic programs, a computational paradigm which is linear (at least in its vector-space interpretation) yet comes with a meaningful mechanism for interpreting (2).
Following [22 ] , we sketch parts of the semantics for first-order probabilistic programs in the category Ban of Banach spaces (over R \mathbb{R} R ) and linear contractions. This category is monoidal w.r.t. to the projective tensor product (which we will not need here) and has I = R I = \mathbb{R} I = R as unit object. The coproduct in this category is given by the direct sum equipped with the ℓ 1 \ell_1 ℓ 1 -norm, thus I + I I + I I + I is the vector space R 2 \mathbb{R}^2 R 2 equipped with the norm ∥ ( u , v ) ∥ 1 = ∣ u ∣ + ∣ v ∣ \lVert(u,v)\rVert_1 = |u| + |v| ∥( u , v ) ∥ 1 = ∣ u ∣ + ∣ v ∣ , and Ban is distributive monoidal for these two operations. Each ground type T T T is first associated with an object X ( T ) X(T) X ( T ) in the category Meas of measurable spaces and measurable functions. For instance the unit type 1 1 1 is associated with the singleton space X ( 1 ) = { ∗ } X(1) = \{\ast\} X ( 1 ) = { ∗ } and the numeric type Real is associated with X ( R e a l ) = R X(\mathrm{Real}) = \mathbb{R} X ( Real ) = R , with the usual Borel σ \sigma σ -algebras. Given a measurable space X X X we will write M X \mathcal{M}X M X for the Banach space of finite measures on X X X . For a context Γ = x 1 : T 1 , … , x n : T n \Gamma= x_1 : T_1, \ldots, x_n : T_n Γ = x 1 : T 1 , … , x n : T n , a judgement Γ ⊢ t : T \Gamma\vdash t : T Γ ⊢ t : T is interpreted as a linear operator
⟦ t ⟧ : ⟦ Γ ⟧ ≅ M ( X ( T 1 ) × … × X ( T n ) ) ⟶ ⟦ T ⟧ ≅ M X ( T ) \llbracket t\rrbracket: \llbracket\Gamma\rrbracket\cong\mathcal{M}\bigl(X(T_1) \times\ldots\times X(T_n)\bigr) \longrightarrow\llbracket T\rrbracket\cong\mathcal{M}X(T) [ [ t ] ] : [ [ Γ ] ] ≅ M ( X ( T 1 ) × … × X ( T n ) ) ⟶ [ [ T ] ] ≅ M X ( T )
The linear operator ⟦ t ⟧ \llbracket t\rrbracket [ [ t ] ] transforms a joint probability distribution on the input variables of the context into an output distribution on the output type. A deterministic predicate Γ ⊢ p : 1 + 1 \Gamma\vdash p : 1 + 1 Γ ⊢ p : 1 + 1 is a predicate whose interpretation is of the shape
⟦ p ⟧ = f ∗ : M ( X ( T 1 ) × … × X ( T n ) ) ⟶ M X ( 1 + 1 ) ≅ R 2 \llbracket p\rrbracket= f_* : \mathcal{M}\bigl(X(T_1) \times\ldots\times X(T_n)\bigr) \longrightarrow\mathcal{M}X(1 + 1) \cong\mathbb{R}^2 [ [ p ] ] = f ∗ : M ( X ( T 1 ) × … × X ( T n ) ) ⟶ M X ( 1 + 1 ) ≅ R 2
where f ∗ f_* f ∗ is the pushforward associated with a measurable map f : X ( T 1 ) × … × X ( T n ) → X ( 1 + 1 ) = 2 f : X(T_1) \times\ldots\times X(T_n) \to X(1 + 1) = 2 f : X ( T 1 ) × … × X ( T n ) → X ( 1 + 1 ) = 2 . From p p p we can define the linear ‘decomposition’ operator splitting a distribution into a pair of subdistributions:
⟦ p ⟧ ^ : ⟦ Γ ⟧ ⟶ ⟦ Γ ⟧ ⊕ ⟦ Γ ⟧ μ ⟼ ( μ ( − ∩ f − 1 ( 0 ) ) , μ ( − ∩ f − 1 ( 1 ) ) ) . \widehat{\llbracket p\rrbracket} : \llbracket\Gamma\rrbracket\longrightarrow\llbracket\Gamma\rrbracket\oplus\llbracket\Gamma\rrbracket\qquad\mu\longmapsto\bigl(\mu(- \cap f^{-1}(0)), \mu(- \cap f^{-1}(1))\bigr). [ [ p ] ] : [ [ Γ ] ] ⟶ [ [ Γ ] ] ⊕ [ [ Γ ] ] μ ⟼ ( μ ( − ∩ f − 1 ( 0 )) , μ ( − ∩ f − 1 ( 1 )) ) .
This operator ⟦ p ⟧ ^ \widehat{\llbracket p\rrbracket} [ [ p ] ] allows us to interpret the typing judgement ⟦ Γ ⊢ i f p t h e n s e l s e t : T ⟧ \llbracket\Gamma\vdash\mathop{\rm if}\ p\ \mathop{\rm then}\ s\ \mathop{\rm else}\ t : T\rrbracket [ [ Γ ⊢ if p then s else t : T ] ] as
⟦ Γ ⟧ → ⟦ p ⟧ ^ ⟦ Γ ⟧ ⊕ ⟦ Γ ⟧ → [ ⟦ s ⟧ , ⟦ t ⟧ ] ⟦ T ⟧ (8) \llbracket\Gamma\rrbracket\xrightarrow{\widehat{\llbracket p\rrbracket}} \llbracket\Gamma\rrbracket\oplus\llbracket\Gamma\rrbracket\xrightarrow{[\llbracket s\rrbracket,\llbracket t\rrbracket]} \llbracket T\rrbracket \tag*{(8)} [ [ Γ ] ] [ [ p ] ] [ [ Γ ] ] ⊕ [ [ Γ ] ] [ [ [ s ] ] , [ [ t ] ] ] [ [ T ] ] (8)
That this non-context-consuming branching mechanism can coexist with a linear system is remarkable and rests on the ability to define the splitting operator ⟦ p ⟧ ^ \widehat{\llbracket p\rrbracket} [ [ p ] ] as a contractive linear operator. We will show in § 5.2 that this construction can be extended to arbitrary guards for a very large class of input spaces ⟦ T ⟧ \llbracket T\rrbracket [ [ T ] ] .
Coherent branching in quantum programs
Our last example of conditional branching found in the wild is coherent/superposed control, a type of branching found in quantum computation, for example in the CNOT gate and described as the ‘elusive quantum control’ in [37 §4.2] as it is harder to account for both type-theoretically and semantically. We follow the formalism for QML [5 , 6 ] and refer the reader to [37 ] for a detailed discussion. In QML the typing rule for coherent control is
Γ ⊢ p : q u b i t Δ ⊢ s : T Δ ⊢ t : T Γ , Δ ⊢ i f ∘ p t h e n s e l s e t : T (9) \frac{\Gamma\vdash p : \mathrm{qubit}\qquad\Delta\vdash s : T\qquad\Delta\vdash t : T}{\Gamma,\Delta\vdash\mathop{\mathrm{if}}\nolimits^{\circ} p\ \mathrm{then}\ s\ \mathrm{else}\ t : T} \tag*{(9)} Γ , Δ ⊢ if ∘ p then s else t : T Γ ⊢ p : qubit Δ ⊢ s : T Δ ⊢ t : T (9)
where i f ∘ \mathop{\mathrm{if}}\nolimits^{\circ} if ∘ is meant to distinguish superposed control from measurement-based control and we have introduced the self-explanatory type qubit. The semantics of this rule assumes the existence of products, of a natural transformation δ A , B : A ⊗ B → A × B \delta_{A,B}: A \otimes B \to A \times B δ A , B : A ⊗ B → A × B , and for any pair f , g : A → B f,g : A \to B f , g : A → B a mechanism for combining them into a morphism ( f ∣ g ) : ( 1 + 1 ) × A → B (f \mid g) : (1 + 1) \times A \to B ( f ∣ g ) : ( 1 + 1 ) × A → B selecting f f f or g g g according to the value of the ‘coordinate’ 1 + 1 1+1 1 + 1 . With this structure [6 ] defines
\left\llbracket\mathop{\mathrm{if}}\nolimits^{\circ} p\ \mathrm{then}\ s\ \mathrm{else}\ t \right\rrbracket= (\llbracket s\rrbracket\mid\llbracket t\rrbracket) \circ(\llbracket p\rrbracket\times\mathrm{id}) \circ\delta_{\Gamma,\Delta}.
We refer the reader to op. cit. for the specific denotational semantics that is based on finite sets; the structural components required to define it are sufficient for our purpose. Note that neither the category C P M ⊕ \mathrm{CPM}_{\oplus} CPM ⊕ nor the category H i l b \mathrm{Hilb} Hilb of finite-dimensional vector spaces possesses this structure (there cannot exist an operator A ⊗ B → A × B A \otimes B \to A \times B A ⊗ B → A × B ), and so the semantics above does not yield the standard semantics of well-known examples of coherent control such as the CNOT or Toffoli gates. A recent approach axiomatises a notion of coherent control over Props [17 ] and shows that this corresponds to certain rig categories. We show in § 5.2 that coherent control can also be understood as an instance of (2) and interpreted accordingly.
Conditionally branching categories
In the previous section we have seen four mechanisms for interpreting if-then-else statements. None subsumes the others, they are incomparable. It is therefore natural to ask: what exactly is needed to interpret conditional branching in a general setting?
To answer this question we draw inspiration from the axiomatisation of conditional branching found in the theory of (Guarded) Kleene Algebras with Tests, i.e. (G)KATs [24 , 34 ] . From this perspective, conditional branching is a collection of binary operations + b +_b + b indexed1 by the elements b ∈ B b \in B b ∈ B of a Boolean algebra of ‘test programs’ and axiomatized by2 :
Skew-commutativity: e + b f = f + b ˉ e e +_b f = f +_{\bar{b}} e e + b f = f + b ˉ e
True test: e + 1 f = e e +_1 f = e e + 1 f = e
Idempotence: e + b e = e e +_b e = e e + b e = e
Skew-associativity: ( e + b f ) + c g = e + b c ( f + c g ) (e +_b f) +_c g = e +_{b c}(f +_c g) ( e + b f ) + c g = e + b c ( f + c g )
where b ˉ \bar{b} b ˉ stands for the negation of b b b , 1 1 1 is the top element of B B B and b c bc b c the conjunction of b , c ∈ B b,c \in B b , c ∈ B . Our first task is to adapt these ideas to typed computations with a categorical semantics. In particular, can we generalise the negation operation, the idea of a test returning ‘true’ or even the conjunction operation? As we shall see in § 6 , while we cannot replicate the full boolean structure of deterministic tests in general, the humble coproduct provides us with a lot of the necessary machinery to adapt the axioms above. We therefore assume throughout that our target semantic universe is a symmetric and distributive monoidal category ( C , ⊗ , I , + ) (\mathcal{C}, \otimes, I, +) ( C , ⊗ , I , + ) in order to interpret the pattern-matching rule (1) as (6).
Following our terminology for programs, we also call morphisms of the type X → I + I X \to I + I X → I + I predicates or tests . Note that I I I is in general not the terminal object, in contrast with [18 ] which is otherwise similar in spirit to a lot of what follows. We will call morphisms of the type X → X + X X \to X + X X → X + X branching morphisms and since the first branch of an if-then-else statement is the branch corresponding to ‘true’, we will think of the first summand of a coproduct X + X X + X X + X as corresponding to ‘true’. In particular, we will use the convention that the first summand of I + I I + I I + I represents the truth value ‘true’, somewhat contrary to convention. Given an object X X X , the following special morphisms X + X → X + X X + X \to X + X X + X → X + X will be important:
true X ≜ [ in 1 , in 1 ] false X ≜ [ in 2 , in 2 ] not X ≜ [ in 2 , in 1 ] \operatorname{true}_X \triangleq[\operatorname{in}_1,\operatorname{in}_1] \qquad\operatorname{false}_X \triangleq[\operatorname{in}_2,\operatorname{in}_2] \qquad\operatorname{not}_X \triangleq[\operatorname{in}_2,\operatorname{in}_1] true X ≜ [ in 1 , in 1 ] false X ≜ [ in 2 , in 2 ] not X ≜ [ in 2 , in 1 ]
We omit subscripts when X = I X = I X = I and write true X f \operatorname{true}_X f true X f for true X ∘ f \operatorname{true}_X \circ f true X ∘ f and similarly for false and not. Objects of the shape X + X + X + X X + X + X + X X + X + X + X will represent pairs of truth values. The four summands will intuitively correspond to, in order, (true, true), (true, false), (false, true) and (false,false). This justifies the notation for the following special morphisms X + X + X + X → X + X X + X + X + X \to X + X X + X + X + X → X + X
∨ X ≜ [ true , id 1 + 1 ] = [ in 1 , in 1 , in 1 , in 2 ] ∧ X ≜ [ id 1 + 1 , false ] = [ in 1 , in 2 , in 2 , in 2 ] \vee_X \triangleq[\operatorname{true},\operatorname{id}_{1+1}] = [\operatorname{in}_1,\operatorname{in}_1,\operatorname{in}_1,\operatorname{in}_2] \qquad\wedge_X \triangleq[\operatorname{id}_{1+1},\operatorname{false}] = [\operatorname{in}_1,\operatorname{in}_2,\operatorname{in}_2,\operatorname{in}_2] ∨ X ≜ [ true , id 1 + 1 ] = [ in 1 , in 1 , in 1 , in 2 ] ∧ X ≜ [ id 1 + 1 , false ] = [ in 1 , in 2 , in 2 , in 2 ]
We can now define the categorical structure that will interpret if-then-else statements.
Definition 5. A conditionally branching category is a symmetric distributive monoidal category ( C , ⊗ , I , + ) (\mathcal{C}, \otimes, I, +) ( C , ⊗ , I , + ) equipped with a family of functions C X : C ( X , I + I ) → C ( X , X + X ) C_X : \mathcal{C}(X, I + I) \to\mathcal{C}(X, X + X) C X : C ( X , I + I ) → C ( X , X + X ) that we will call choice functions and which satisfy for every test p : X → I + I p : X \to I + I p : X → I + I
Skew-commutativity: C X ( not p ) = not X C X ( p ) C_X(\operatorname{not}\ p) = \operatorname{not}_X C_X(p) C X ( not p ) = not X C X ( p )
True test: C X ( true p ) = true X ∘ C X ( p ) C_X(\operatorname{true}\ p) = \operatorname{true}_X \circ C_X(p) C X ( true p ) = true X ∘ C X ( p ) A conditionally branching structure will be called idempotent if it additionally satisfies
Idempotence: ∇ X ∘ C X ( p ) = id X \nabla_X \circ C_X(p) = \operatorname{id}_X ∇ X ∘ C X ( p ) = id X . Finally, it will be called commutative if for every p , q : X → I + I p, q : X \to I + I p , q : X → I + I ,
Commutative: ( C X ( q ) + C X ( q ) ) ∘ C X ( p ) = [ in 1 , in 3 , in 2 , in 4 ] ∘ ( C X ( p ) + C X ( p ) ) ∘ C X ( q ) (C_X(q) + C_X(q)) \circ C_X(p) = [\operatorname{in}_1,\operatorname{in}_3,\operatorname{in}_2,\operatorname{in}_4] \circ(C_X(p) + C_X(p)) \circ C_X(q) ( C X ( q ) + C X ( q )) ∘ C X ( p ) = [ in 1 , in 3 , in 2 , in 4 ] ∘ ( C X ( p ) + C X ( p )) ∘ C X ( q ) .
We interpret the if-then-else rule (2) in any conditionally branching category as
⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ → C ⟦ Γ ⟧ ( ⟦ p ⟧ ) ⊗ id ( ⟦ Γ ⟧ + ⟦ Γ ⟧ ) ⊗ ⟦ Δ ⟧ → rdistr ⟦ Γ , Δ ⟧ + ⟦ Γ , Δ ⟧ → [ ⟦ s ⟧ , ⟦ t ⟧ ] ⟦ T ⟧ (10) \llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket
\xrightarrow{\ C_{\llbracket\Gamma\rrbracket}(\llbracket p\rrbracket)\otimes\operatorname{id}\ }
(\llbracket\Gamma\rrbracket+\llbracket\Gamma\rrbracket)\otimes\llbracket\Delta\rrbracket
\xrightarrow{\ \operatorname{rdistr}\ }
\llbracket\Gamma,\Delta\rrbracket+\llbracket\Gamma,\Delta\rrbracket
\xrightarrow{\ [\llbracket s\rrbracket,\llbracket t\rrbracket]\ }
\llbracket T\rrbracket \tag*{(10)} [ [ Γ ] ] ⊗ [ [ Δ ] ] C [ [ Γ ] ] ( [ [ p ] ] ) ⊗ id ( [ [ Γ ] ] + [ [ Γ ] ] ) ⊗ [ [ Δ ] ] rdistr [ [ Γ , Δ ] ] + [ [ Γ , Δ ] ] [ [ [ s ] ] , [ [ t ] ] ] [ [ T ] ] (10)
Beyond the simplicity of this semantics, let us provide some justification for our definition.
Structural similarity with traces. Our definition uses the same basic data as that of a traced monoidal category: a monoidal category together with a collection of functions between hom-sets of a particular shape and satisfying certain axioms. This echoes our stated aim to do for if-then-else what traced monoidal categories did for recursion and iteration.
Connection with iteration. Our definition gives a semantic basis for the interpretation of while loops in the context of Elgot theories and Elgot monads [13 , 1 , 2 ] . To interpret x : T ⊢ p o d s : T x : T \vdash p\ o\ d\ s : T x : T ⊢ p o d s : T one first needs a morphism e : ⟦ T ⟧ → ⟦ T ⟧ + ⟦ T ⟧ e : \llbracket T\rrbracket\to\llbracket T\rrbracket+ \llbracket T\rrbracket e : [ [ T ] ] → [ [ T ] ] + [ [ T ] ] (possibly effectful) from which to compute the conditional iterate [13 ] e † : ⟦ T ⟧ → ⟦ T ⟧ e^\dagger: \llbracket T\rrbracket\to\llbracket T\rrbracket e † : [ [ T ] ] → [ [ T ] ] interpreting the while loop. This is always available in a conditionally branching category via e = ( [ [ s ] ] + id ⟦ T ⟧ ) ∘ C ⟦ T ⟧ ( p ) e = ([\![s]\!] + \operatorname{id}_{\llbracket T\rrbracket}) \circ C_{\llbracket T\rrbracket}(p) e = ([ [ s ] ] + id [ [ T ] ] ) ∘ C [ [ T ] ] ( p ) . The fact that our definition is designed to interpret the if-then-else rule (2), in which the context can be shared by the guard and the branches, makes it possible to consider iteration even in linear cases (e.g. the semantics of probabilistic iteration of [22 ] ). Thus a conditionally branching category is always ‘iteration ready’. This connects to the previous point via the well-known correspondence between iteration and traces for the cocartesian structure [16 ] .
Connection with instruments. The shape of our definition has a precedent in quantum control in the shape of the notion of instrument , later generalised in e.g. [18 , 19 ] .
Given a predicate Γ ⊢ p : b i t \Gamma\vdash p : \mathrm{bit} Γ ⊢ p : bit defining two orthogonal projections the Lüders instrument [25 ] provides a splitting operator ⟦ Γ ⟧ → ⟦ Γ ⟧ ⊕ ⟦ Γ ⟧ \llbracket\Gamma\rrbracket\to\llbracket\Gamma\rrbracket\oplus\llbracket\Gamma\rrbracket [ [ Γ ] ] → [ [ Γ ] ] ⊕ [ [ Γ ] ] allowing a semantics of measurement-based control, precisely what a conditionally branching structure provides too (see § 5.2 ).
GKAT axioms
The definition enforces the GKAT axioms (1)-(2) given above. To see this, let us define programs that are syntactic counterparts of morphisms defined above:
not ( p ) ≜ case p of ( in ( 1 , x ) ⇒ in ( 2 , x ) , in ( 2 , x ) ⇒ in ( 1 , x ) ) \operatorname{not}(p) \triangleq\operatorname{case}\ p\ \operatorname{of}\ (\operatorname{in}(1,x) \Rightarrow\operatorname{in}(2,x),\operatorname{in}(2,x) \Rightarrow\operatorname{in}(1,x)) not ( p ) ≜ case p of ( in ( 1 , x ) ⇒ in ( 2 , x ) , in ( 2 , x ) ⇒ in ( 1 , x ))
tt ( p ) ≜ case p of ( in ( 1 , x ) ⇒ in ( 1 , x ) , in ( 2 , x ) ⇒ in ( 1 , x ) ) \operatorname{tt}(p) \triangleq\operatorname{case}\ p\ \operatorname{of}\ (\operatorname{in}(1,x) \Rightarrow\operatorname{in}(1,x),\operatorname{in}(2,x) \Rightarrow\operatorname{in}(1,x)) tt ( p ) ≜ case p of ( in ( 1 , x ) ⇒ in ( 1 , x ) , in ( 2 , x ) ⇒ in ( 1 , x ))
With these programs we can state and show:
Theorem 6. The interpretation (10) of if–then–else statements in a conditionally branching category guarantees the following semantic identities:
⟦ Γ ⊢ if p then s else t : T ⟧ = ⟦ Γ ⊢ if not p then t else s : T ⟧ \llbracket\Gamma\vdash\operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ t : T \rrbracket= \llbracket\Gamma\vdash\operatorname{if}\ \operatorname{not}\ p\ \operatorname{then}\ t\ \operatorname{else}\ s : T \rrbracket [ [ Γ ⊢ if p then s else t : T ] ] = [ [ Γ ⊢ if not p then t else s : T ] ]
⟦ Γ ⊢ if tt ( p ) then s else t : T ⟧ = ⟦ Γ ⊢ s : T ⟧ \llbracket\Gamma\vdash\operatorname{if}\ \operatorname{tt}(p)\ \operatorname{then}\ s\ \operatorname{else}\ t : T \rrbracket= \llbracket\Gamma\vdash s : T \rrbracket [ [ Γ ⊢ if tt ( p ) then s else t : T ] ] = [ [ Γ ⊢ s : T ] ] .
If the conditionally branching structure is idempotent, then
⟦ Γ ⊢ if p then s else s : T ⟧ = ⟦ Γ ⊢ s : T ⟧ \llbracket\Gamma\vdash\operatorname{if}\ p\ \operatorname{then}\ s\ \operatorname{else}\ s : T \rrbracket= \llbracket\Gamma\vdash s : T \rrbracket [ [ Γ ⊢ if p then s else s : T ] ] = [ [ Γ ⊢ s : T ] ] .
If the conditionally branching structure is commutative then
⟦ Γ ⊢ if p then if q then s 1 else s 2 else if q then s 3 else s 4 : T ⟧ = ⟦ Γ ⊢ if q then if p then s 1 else s 3 else if p then s 2 else s 4 : T ⟧ \llbracket\Gamma\vdash\operatorname{if}\ p\ \operatorname{then}\ \operatorname{if}\ q\ \operatorname{then}\ s_{1}\ \operatorname{else}\ s_{2}\ \operatorname{else}\ \operatorname{if}\ q\ \operatorname{then}\ s_{3}\ \operatorname{else}\ s_{4} : T \rrbracket= \llbracket\Gamma\vdash\operatorname{if}\ q\ \operatorname{then}\ \operatorname{if}\ p\ \operatorname{then}\ s_{1}\ \operatorname{else}\ s_{3}\ \operatorname{else}\ \operatorname{if}\ p\ \operatorname{then}\ s_{2}\ \operatorname{else}\ s_{4} : T \rrbracket [ [ Γ ⊢ if p then if q then s 1 else s 2 else if q then s 3 else s 4 : T ] ] = [ [ Γ ⊢ if q then if p then s 1 else s 3 else if p then s 2 else s 4 : T ] ] .
The reader may wonder why skew-associativity has been left out of Theorem 6. The reason is that the obvious generalisation of skew-associativity does not hold in general. We will look at nested conditional branchings and skew-associativity in detail in § 6.3 , but we can give a simple example to illustrate the problem. For purely probabilistic tests like flip 1 / 2 1/2 1/2 , it is in general impossible to find an r ∈ [ 0 , 1 ] r \in[0,1] r ∈ [ 0 , 1 ] playing the role on the conjunction of guards in GKAT’s skew-associativity and making the following skew-associativity identity hold:
⟦ if flip q then ( if flip p then s 1 else s 2 ) else s 3 ⟧ = ⟦ if flip r then s 1 else ( if flip q then s 2 else s 3 ) ⟧ \llbracket\operatorname{if}\ \operatorname{flip}\ q\ \operatorname{then}\ (\operatorname{if}\ \operatorname{flip}\ p\ \operatorname{then}\ s_{1}\ \operatorname{else}\ s_{2})\ \operatorname{else}\ s_{3} \rrbracket
=
\llbracket\operatorname{if}\ \operatorname{flip}\ r\ \operatorname{then}\ s_{1}\ \operatorname{else}\ (\operatorname{if}\ \operatorname{flip}\ q\ \operatorname{then}\ s_{2}\ \operatorname{else}\ s_{3}) \rrbracket [ [ if flip q then ( if flip p then s 1 else s 2 ) else s 3 ] ] = [ [ if flip r then s 1 else ( if flip q then s 2 else s 3 ) ] ]
The reason is that, semantically, this would require the probability of reaching s 3 s_{3} s 3 to be ( 1 − q ) = ( 1 − q ) ( 1 − r ) (1-q) = (1-q)(1-r) ( 1 − q ) = ( 1 − q ) ( 1 − r ) which does not hold in general. This suggests that the skew-associativity rule from GKAT, if it is to hold in more generality, must be a special case of a more general rule ( e + b f ) + c g = e + b c ( f + b ∙ c g ) (e +_{b} f) +_{c} g = e +_{bc} (f +_{b \mathbin{\bullet} c} g) ( e + b f ) + c g = e + b c ( f + b ∙ c g ) for some operation b ∙ c b \mathbin{\bullet} c b ∙ c yet to be determined and evaluating to c c c in the case of deterministic boolean tests. We return to this question in § 6.3 .
We can however show the identity corresponding to the GKAT axiom e g + b f g = ( e + b f ) g eg +_{b} fg = (e +_{b} f)g e g + b f g = ( e + b f ) g . For this we will use the standard let -binding rule
Γ ⊢ s : S Δ , x : S ⊢ t : T Γ , Δ ⊢ let x = s in t : T \begin{aligned}
\Gamma\vdash s : S \qquad\Delta,x:S \vdash t:T \\
\Gamma,\Delta\vdash\operatorname{let}\ x=s\ \operatorname{in}\ t:T
\end{aligned} Γ ⊢ s : S Δ , x : S ⊢ t : T Γ , Δ ⊢ let x = s in t : T
Proposition 7. In any conditionally branching category, the interpretation (10) satisfies
⟦ Γ , Δ ⊢ if p then let x = s 1 in t else let x = s 2 in t : T ⟧ = ⟦ Γ , Δ ⊢ let x = ( if p then s 1 else s 2 ) in t : T ⟧ (11) \llbracket\Gamma,\Delta\vdash\operatorname{if}\ p\ \operatorname{then}\ \operatorname{let}\ x=s_{1}\ \operatorname{in}\ t\ \operatorname{else}\ \operatorname{let}\ x=s_{2}\ \operatorname{in}\ t:T \rrbracket
=
\llbracket\Gamma,\Delta\vdash\operatorname{let}\ x=(\operatorname{if}\ p\ \operatorname{then}\ s_{1}\ \operatorname{else}\ s_{2})\ \operatorname{in}\ t:T \rrbracket \tag*{(11)} [ [ Γ , Δ ⊢ if p then let x = s 1 in t else let x = s 2 in t : T ] ] = [ [ Γ , Δ ⊢ let x = ( if p then s 1 else s 2 ) in t : T ] ] (11) (where let bindings are interpreted in the usual way).
Remark 8. It would seem natural to require that choice functions satisfy some naturality condition (no pun intended). The only one that makes sense is to ask that for all f : Y → X f : Y \to X f : Y → X ,
C X ( p ) ∘ f = ( f + f ) ∘ C Y ( p ∘ f ) . (12) C_{X}(p) \circ f = (f+f) \circ C_{Y}(p \circ f). \tag*{(12)} C X ( p ) ∘ f = ( f + f ) ∘ C Y ( p ∘ f ) . (12)
Although this condition does hold for many conditionally branching categories, it does not hold in some important situations, for example non-deterministic computations. Unlike the definition of a trace, the conditionally branching structure doesn’t seem to demand any naturality conditions. However, the skew-commutativity and true test axioms do imply a kind of ‘combinatorial naturality’ in I + I I+I I + I in the sense that every ‘combinatorial’ endomorphism, that is to say the 4 endomorphisms f I : I + I → I + I f_I:I+I\to I+I f I : I + I → I + I generated by the coproduct structure, must be reflected on X + X X+X X + X via C X ( f I ∘ p ) = f X ∘ C X ( p ) C_X(f_I\circ p)=f_X\circ C_X(p) C X ( f I ∘ p ) = f X ∘ C X ( p ) .
Remark 9. It follows from Definition 5 that if a category C \mathcal{C} C is equipped with a conditional branching structure, so is every subcategory D \mathcal{D} D of C \mathcal{C} C containing I I I and closed under ⊗ \otimes ⊗ and + + + .
We conclude this section by considering the notion of short-circuiting (e.g. [29 p.222] ). Short-circuiting is a behaviour of conditional branching characterised by the fact that classically only one of the branches ever needs to be evaluated : the if-branch when the guard evaluates to true, and the else-branch otherwise. In both cases, the remaining branch is ‘short-circuited’ i.e. not evaluated.
Definition 10. A conditionally branching structure on a category C \mathcal{C} C will be called short-circuiting if for every state s : I → X s:I\to X s : I → X and every test p : X → I + I p:X\to I+I p : X → I + I , if p ∘ s p\circ s p ∘ s factors through i n 1 : I → I + I \mathrm{in}_1:I\to I+I in 1 : I → I + I , then the morphism C X ( p ) ∘ s C_X(p)\circ s C X ( p ) ∘ s factors through i n 1 : X → X + X \mathrm{in}_1:X\to X+X in 1 : X → X + X , and similarly for i n 2 \mathrm{in}_2 in 2 . Diagrammatically:
if I → s X ↓ ↓ p I → i n 1 or i n 2 I + I then I → s X ↓ ↓ C X ( p ) X → i n 1 or i n 2 X + X \begin{array}{cc}
\text{if}\quad
\begin{array}{c}
I\xrightarrow{s}X\\
\downarrow\quad\downarrow p\\
I\xrightarrow{\mathrm{in}_1\ \text{or}\ \mathrm{in}_2}I+I
\end{array}\qquad
&
\text{then}\quad
\begin{array}{c}
I\xrightarrow{s}X\\
\downarrow\quad\downarrow C_X(p)\\
X\xrightarrow{\mathrm{in}_1\ \text{or}\ \mathrm{in}_2}X+X
\end{array}
\end{array} if I s X ↓ ↓ p I in 1 or in 2 I + I then I s X ↓ ↓ C X ( p ) X in 1 or in 2 X + X
The definition guarantees that whenever a predicate factors through true in a state s s s , then the semantics of the if-then-else statement can be written by only evaluating the semantics of the if-branch (since ⟦ s ⟧ , ⟦ t ⟧ ∘ i n 1 = ⟦ s ⟧ \llbracket s\rrbracket,\llbracket t\rrbracket\circ\mathrm{in}_1=\llbracket s\rrbracket [ [ s ] ] , [ [ t ] ] ∘ in 1 = [ [ s ] ] ), and similarly for the else-branch.
Examples of conditionally branching categories
Distributive copy-categories
We first present a large class of categories in which the copy-and-distribute strategy discussed in § 2.1 can be used to define a conditionally branching structure. We do not need (Cartesian) distributive categories – as we saw in § 2.1 this excludes semantically important categories – but we do need categories that are distributive monoidal as a prerequisite to Definition 5 .
Example 11. We saw in Example 1 that the category R e l \mathrm{Rel} Rel of non-deterministic computations is not distributive w.r.t. the Cartesian product of R e l \mathrm{Rel} Rel . It is however distributive w.r.t. the monoidal structure given by the Cartesian product in S e t \mathrm{Set} Set with I = { ∗ } I=\{*\} I = { ∗ } the singleton set.
Example 12. Similarly, we showed in Example 2 that the category ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ of pointed ω \omega ω -cpos and strict morphisms is not distributive w.r.t. the Cartesian product. It is however distributive w.r.t. the smash product with carrier A ⊗ B = ( A ∖ { ⊥ A } ) × ( B ∖ { ⊥ B } ) ∪ { ⊥ } A\otimes B=(A\setminus\{\bot_A\})\times(B\setminus\{\bot_B\})\cup\{\bot\} A ⊗ B = ( A ∖ { ⊥ A }) × ( B ∖ { ⊥ B }) ∪ { ⊥ } and the pointwise order. The unit of this product is the chain { ⊥ ≤ ∗ } \{\bot\leq*\} { ⊥ ≤ ∗ } .
In order to apply the copy-and-distribute method of § 2.1 we also need to be able to copy (a functionality that comes for free with the Cartesian product). The two examples above are examples of distributive copy categories [9 ] , i.e. symmetric monoidal categories where every object comes equipped with a cocommutative and coassociative copying morphism copy A : A → A ⊗ A \operatorname{copy}_A : A \to A \otimes A copy A : A → A ⊗ A . In Rel the copy map is given by the diagonal map copy A ( x ) = ( x , x ) \operatorname{copy}_A(x) = (x, x) copy A ( x ) = ( x , x ) , in ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ it is given by copy A ( x ) = ( x , x ) \operatorname{copy}_A(x) = (x, x) copy A ( x ) = ( x , x ) if x ≠ ⊥ x \ne\perp x = ⊥ and ⊥ \perp ⊥ else.
Theorem 13. Every distributive copy category has a commutative conditionally branching structure given by the choice functions
C X : C ( X , I + I ) → C ( X , X + X ) , C_X : \mathcal{C}(X, I + I) \to\mathcal{C}(X, X + X), C X : C ( X , I + I ) → C ( X , X + X ) , p ↦ ( ρ X + ρ X ) ∘ ldistr X ∘ ( id ⊗ p ) ∘ copy X : X → X ⊗ X → X ⊗ ( I + I ) → X ⊗ I + X ⊗ I → X + X (13) p \mapsto(\rho_X + \rho_X) \circ\operatorname{ldistr}_X \circ(\operatorname{id} \otimes p) \circ\operatorname{copy}_X :
X \to X \otimes X \to X \otimes(I + I) \to X \otimes I + X \otimes I \to X + X \tag*{(13)} p ↦ ( ρ X + ρ X ) ∘ ldistr X ∘ ( id ⊗ p ) ∘ copy X : X → X ⊗ X → X ⊗ ( I + I ) → X ⊗ I + X ⊗ I → X + X (13) This structure is short-circuiting in all deterministic states s : I → X s : I \to X s : I → X (i.e. states such that copy X ∘ s = ( s ⊗ s ) ∘ copy I \operatorname{copy}_X \circ s = (s \otimes s) \circ\operatorname{copy}_I copy X ∘ s = ( s ⊗ s ) ∘ copy I , see [14 ] ).
The conditionally branching structure of (13) is in general not idempotent, therefore it does not support the rewriting schema ⟦ Γ ⊢ if p then s else s : T ⟧ = ⟦ Γ ⊢ s : T ⟧ \llbracket\Gamma\vdash\text{if } p \text{ then } s \text{ else } s : T\rrbracket= \llbracket\Gamma\vdash s : T\rrbracket [ [ Γ ⊢ if p then s else s : T ] ] = [ [ Γ ⊢ s : T ] ] . To recover this behaviour, we need more structure on C \mathcal{C} C . A copy-discard category [8 ] is a copy category such that every object also comes equipped with a deletion morphism del A : A → I \operatorname{del}_A : A \to I del A : A → I which, together with the copy morphism copy A : A → A ⊗ A \operatorname{copy}_A : A \to A \otimes A copy A : A → A ⊗ A , equips it with a comonoid structure. If the unit I I I is terminal, then a copy-delete category is called a Markov category [14 ] .
Theorem 14. The conditionally branching structure given by (13) is idempotent whenever the distributive copy category C \mathcal{C} C is Markov, in particular when it is distributive (§ 2.1).
Example 15. The category Stoch [14 §4] of measurable spaces and Markov kernels is a Markov category, and can therefore be equipped with an idempotent and commutative conditionally branching structure following (13). It sends a stochastic test p : X → G ( 1 + 1 ) p : X \to\mathcal{G}(1 + 1) p : X → G ( 1 + 1 ) , where G \mathcal{G} G is the Giry monad, to C X ( p ) : X → G ( X + X ) C_X(p) : X \to\mathcal{G}(X + X) C X ( p ) : X → G ( X + X ) given by
C X ( p ) ( x ) = p ( x ) ( 1 ) δ in 1 x + p ( x ) ( 2 ) δ in 2 x C_X(p)(x) = p(x)(1)\delta_{\operatorname{in}_1x} + p(x)(2)\delta_{\operatorname{in}_2x} C X ( p ) ( x ) = p ( x ) ( 1 ) δ in 1 x + p ( x ) ( 2 ) δ in 2 x
Example 16. The category Rel is a copy category but it is not a Markov category as the terminal object (which is also the initial object by self-duality) is the empty set which is not the unit of the monoidal product described above. Rel therefore supports a commutative conditional branching structure, but not an idempotent one. This comes from the fact that the empty relation ∅ : X → I + I \varnothing: X \to I + I ∅ : X → I + I semantically represents a crashing/divergent test, and for such a test it cannot be the case that ⟦ Γ ⊢ if p then s else s : T ⟧ = ⟦ Γ ⊢ s : T ⟧ \llbracket\Gamma\vdash\text{if } p \text{ then } s \text{ else } s : T\rrbracket= \llbracket\Gamma\vdash s : T\rrbracket [ [ Γ ⊢ if p then s else s : T ] ] = [ [ Γ ⊢ s : T ] ] .
Example 17. Similarly, the category ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ is a copy category but not a Markov category as the unit of the smash product is not terminal. The commutative conditional branching structure of ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ given by (13) cannot be idempotent for the same reason as in the previous example: predicates p : X → I + I p : X \to I + I p : X → I + I allow for divergence (that is the point of the bottom element ⊥ \perp ⊥ ) and it therefore cannot be the case that ⟦ Γ ⊢ if p then s else s : T ⟧ = ⟦ Γ ⊢ s : T ⟧ \llbracket\Gamma\vdash\text{if } p \text{ then } s \text{ else } s : T\rrbracket= \llbracket\Gamma\vdash s : T\rrbracket [ [ Γ ⊢ if p then s else s : T ] ] = [ [ Γ ⊢ s : T ] ] .
Remark 18. The example above illustrates the fact that for a call-by-value semantics allowing divergence, e.g. in the category ω C P O ⊥ \omega\mathrm{CPO}_{\perp} ω CPO ⊥ , a conditionally branching structure can never be idempotent, and ⟦ Γ ⊢ if p then s else s : T ⟧ = ⟦ Γ ⊢ s : T ⟧ \llbracket\Gamma\vdash\text{if } p \text{ then } s \text{ else } s : T\rrbracket= \llbracket\Gamma\vdash s : T\rrbracket [ [ Γ ⊢ if p then s else s : T ] ] = [ [ Γ ⊢ s : T ] ] will not hold. It is however also worth noting that even in a call-by-name semantics (where f ⊥ = ⊥ f\perp= \perp f ⊥=⊥ needn’t hold), guards behave in a call-by-value way. Specifically, the call-by-name small-step operational semantics of an if–then–else statement forces the evaluation of the guard and only starts evaluating one of the branches if the guard evaluates to true or false (in particular it is short-circuiting). This means that if the guard diverges, so does the entire if–then–else statement, in contrast with f ⊥ ≠ ⊥ f\perp\ne\perp f ⊥ = ⊥ in general. The idempotence of a conditionally branching structure is thus prevented by partiality, no matter what the evaluation strategy is.
Proposition 19. The conditionally branching structure of (13) is short-circuiting in any copy-discard category C \mathcal{C} C where the following diagram is a pullback:
X → i n 1 X + X d e l ↓ ↓ d e l + d e l I → i n 1 I + I \begin{CD}
X @>{\mathrm{in}_1}>> X+X \\
@V{\mathrm{del}}VV @VV{\mathrm{del}+\mathrm{del}}V \\
I @>{\mathrm{in}_1}>> I+I
\end{CD} X del ↓ ⏐ I in 1 in 1 X + X ↓ ⏐ del + del I + I
This result does not require the copy-discard category to be Markov. In the Cartesian case it is a special case of [18 (4.4)] and therefore holds more generally in any effectus [18 §4] . Effectful Computations interpreted in the Kleisli categories C T \mathcal{C}_T C T of monads T : C → C T:\mathcal{C}\to\mathcal{C} T : C → C provide a rich collection of examples of conditionally branching structures given by (13) . Let us start by examining when C T \mathcal{C}_T C T is distributive monoidal – the prerequisite for Definition 5 – assuming that C \mathcal{C} C is. First, C T \mathcal{C}_T C T always has coproducts when the base category C \mathcal{C} C does, with inclusions given by η T ∘ i n 1 , η T ∘ i n 2 \eta^T\circ\mathrm{in}_1,\eta^T\circ\mathrm{in}_2 η T ∘ in 1 , η T ∘ in 2 and copairings A + B → T C A+B\to T C A + B → T C built in the base category. To define a monoidal structure on C T \mathcal{C}_T C T we start by recalling that a left strength for a monad T T T on ( C , ⊗ , I ) (\mathcal{C},\otimes,I) ( C , ⊗ , I ) is a natural transformation str A , B : A ⊗ T B → T ( A ⊗ B ) \operatorname{str}_{A,B}:A\otimes T B\to T(A\otimes B) str A , B : A ⊗ T B → T ( A ⊗ B ) satisfying axioms found in e.g. [21 , 27 ] . If C \mathcal{C} C has a symmetry transformation γ A , B : A ⊗ B → B ⊗ A \gamma_{A,B}:A\otimes B\to B\otimes A γ A , B : A ⊗ B → B ⊗ A , we can define the right strength str A , B ′ = T ( γ B , A ) ∘ str B , A ∘ γ T A , B : T A ⊗ B → T ( A ⊗ B ) \operatorname{str}'_{A,B}=T(\gamma_{B,A})\circ\operatorname{str}_{B,A}\circ\gamma_{T A,B}:T A\otimes B\to T(A\otimes B) str A , B ′ = T ( γ B , A ) ∘ str B , A ∘ γ T A , B : T A ⊗ B → T ( A ⊗ B ) . Finally, a monad with a left strength is commutative whenever the following diagram commutes:
T A ⊗ T B → str T A , B T ( T A ⊗ B ) → T str A , B ′ T 2 ( A ⊗ B ) str A , T B ′ ↓ ↓ μ A ⊗ B T ( A ⊗ T B ) → T str A , B T 2 ( A ⊗ B ) → μ A ⊗ B T ( A ⊗ B ) \begin{CD}
T A\otimes T B @>{\operatorname{str}_{T A,B}}>> T(T A\otimes B) @>{T\operatorname{str}'_{A,B}}>> T^2(A\otimes B) \\
@V{\operatorname{str}'_{A,T B}}VV @. @VV{\mu_{A\otimes B}}V \\
T(A\otimes T B) @>{T\operatorname{str}_{A,B}}>> T^2(A\otimes B) @>{\mu_{A\otimes B}}>> T(A\otimes B)
\end{CD} T A ⊗ T B str A , T B ′ ↓ ⏐ T ( A ⊗ T B ) str T A , B T str A , B T ( T A ⊗ B ) T 2 ( A ⊗ B ) T str A , B ′ μ A ⊗ B T 2 ( A ⊗ B ) ↓ ⏐ μ A ⊗ B T ( A ⊗ B )
The transformation T A ⊗ T B → T ( A ⊗ B ) T A\otimes T B\to T(A\otimes B) T A ⊗ T B → T ( A ⊗ B ) makes T T T a monoidal monad (there is a one-to-one correspondence between commutative monads and symmetric monoidal monads [21 , 11 ] ). It follows that the Kleisli category of a commutative monad on a symmetric monoidal category is symmetric monoidal in a canonical way [30 Cor. 4.3] . Finally, it is not hard to check that:
Proposition 20. If ( C , ⊗ , I , + ) (\mathcal{C},\otimes,I,+) ( C , ⊗ , I , + ) is a symmetric distributive monoidal category and T : C → C T:\mathcal{C}\to\mathcal{C} T : C → C is a commutative monad, then C T \mathcal{C}_T C T is symmetric distributive monoidal with the distributivity maps given by the C \mathcal{C} C -morphisms η T ∘ ldistr \eta^T\circ\operatorname{ldistr} η T ∘ ldistr and η T ∘ rdistr \eta^T\circ\operatorname{rdistr} η T ∘ rdistr .
With this in place, we can apply the copy-and-distribute approach to defining conditionally branching structures on Kleisli categories. Assuming that ( C , ⊗ , I , copy ) (\mathcal{C},\otimes,I,\operatorname{copy}) ( C , ⊗ , I , copy ) is a distributive copy category and that T T T is commutative, we can define copy morphisms on C T \mathcal{C}_T C T by post-composition with the unit: η X T ∘ copy X : X → T ( X ⊗ X ) \eta^T_X\circ\operatorname{copy}_X:X\to T(X\otimes X) η X T ∘ copy X : X → T ( X ⊗ X ) . This gives us a commutative conditionally branching structure on C T \mathcal{C}_T C T via (13) and Theorem 13 . After some simplifications the choice function associated with a C T \mathcal{C}_T C T -predicate p : X → I + I p:X\to I+I p : X → I + I is explicitly given by
c X ( p ) = T ldistr X ∘ str X , I + I ∘ ( id X ⊗ p ) ∘ copy X : \operatorname{c}_X(p)=T\operatorname{ldistr}_X\circ\operatorname{str}_{X,I+I}\circ(\operatorname{id}_X\otimes p)\circ\operatorname{copy}_X: c X ( p ) = T ldistr X ∘ str X , I + I ∘ ( id X ⊗ p ) ∘ copy X :
X → X ⊗ X → X ⊗ T ( I + I ) → T ( X ⊗ ( I + I ) ) → T ( X + X ) (14) X\to X\otimes X\to X\otimes T(I+I)\to T(X\otimes(I+I))\to T(X+X) \tag*{(14)} X → X ⊗ X → X ⊗ T ( I + I ) → T ( X ⊗ ( I + I )) → T ( X + X ) (14)
The question of the conditionally branching structure’s idempotence is once again more subtle and we require quite a bit more structure on the base category and on the monad to establish it. This question is discussed in some detail in [19 §5] where idempotence is called side-effect-freeness and the monoidal structure is given by the Cartesian product and the terminal object. We generalise this discussion to the monoidal case. Recall that a monad on a category C \mathcal{C} C with a terminal object 1 1 1 is called affine if T 1 ≅ 1 T1\cong1 T 1 ≅ 1 .
Theorem 21 [14 ] . Let C \mathcal{C} C be a Markov category, and let T T T be a commutative monad on C \mathcal{C} C that is also affine. Then the Kleisli category C T \mathcal{C}_T C T is also a Markov category where deleting is given by del A T = del A : A → 1 ≅ T 1 \operatorname{del}^T_A=\operatorname{del}_A:A\to1\cong T1 del A T = del A : A → 1 ≅ T 1 .
Corollary 22. Let C \mathcal{C} C be a Markov category, and let T T T be a symmetric monoidal affine monad on C \mathcal{C} C , then the conditionally branching structure defined in (14) is idempotent. Most useful monads are not affine, and therefore do not support an idempotent conditionally branching structure. We can however prove idempotence for pure tests (tests factoring through the unit η T \eta^T η T ), whenever the base category is idempotent conditionally branching.
Theorem 23. Let C \mathcal{C} C be an idempotent conditionally branching category, and T : C → C T:\mathcal{C}\to\mathcal{C} T : C → C be a monad with unit η T \eta^T η T . For pure tests η T ∘ p : X → I + I → T ( I + I ) \eta^T\circ p:X\to I+I\to T(I+I) η T ∘ p : X → I + I → T ( I + I ) , the branching morphisms
C ~ X ( p ) = η X + X T ∘ C X ( p ) : X → X + X → T ( X + X ) \widetilde{C}_X(p)=\eta^T_{X+X}\circ C_X(p):X\to X+X\to T(X+X) C X ( p ) = η X + X T ∘ C X ( p ) : X → X + X → T ( X + X ) satisfy axioms (1)-(3) of Definition 5 .
Categories of Vector Spaces
In this section we present a second class of categories with a conditionally branching structure, this time based on the ability to define choice functions as ‘splitting morphisms’.
Probabilistic Program Semantics. We start with our motivating example and prove the existence of a conditionally branching structure for a large class of real Banach spaces which includes the denotation of types in [22 ] . The intuition behind the construction is that a predicate p : X → R ⊕ R p:X\to\mathbb{R}\oplus\mathbb{R} p : X → R ⊕ R defines a linear functional ev p : ∇ R ∘ p : X → R \operatorname{ev}_p:\nabla_{\mathbb{R}}\circ p:X\to\mathbb{R} ev p : ∇ R ∘ p : X → R . Using a generalisation of the Radon-Nikodym theorem, one can compute the ‘densities’ of the true and false components π 1 ∘ p , π 2 ∘ p \pi_1\circ p,\pi_2\circ p π 1 ∘ p , π 2 ∘ p w.r.t. ev p \operatorname{ev}_p ev p , and use these to split any positive input vector.
Theorem 24. Let X X X be a σ \sigma σ -order complete ordered Banach space and let p : X → R ⊕ R p:X\to\mathbb{R}\oplus\mathbb{R} p : X → R ⊕ R be a norm-preserving σ \sigma σ -order continuous positive operator. For any 0 ≤ x ∈ X 0\leq x\in X 0 ≤ x ∈ X there exist 0 ≤ x t , x f ∈ X 0\leq x_t,x_f\in X 0 ≤ x t , x f ∈ X s.th.
x = x t + x f x=x_t+x_f x = x t + x f
x ↦ ( x t , x f ) x\mapsto(x_t,x_f) x ↦ ( x t , x f ) defines a positive linear operator C X : X → X ⊕ X C_X:X\to X\oplus X C X : X → X ⊕ X
C X C_X C X satisfies the axioms (1)-(4) of Definition 5 and is short-circuiting
If X X X is an AL-space, then ∥ x t ∥ = π 1 ∘ p ( x ) \lVert x_t\rVert=\pi_1\circ p(x) ∥ x t ∥ = π 1 ∘ p ( x ) and ∥ x f ∥ = π 2 ∘ p ( x ) \lVert x_f\rVert=\pi_2\circ p(x) ∥ x f ∥ = π 2 ∘ p ( x )
This result generalises the semantics of [22 ] to arbitrary probabilistic guards (and corrects an erroneous splitting in [10 ] ). For a deterministic guard f ∗ : M ( X 1 × … × X n ) → M ( 1 + 1 ) f_*:\mathcal{M}(X_1\times\ldots\times X_n)\to\mathcal{M}(1+1) f ∗ : M ( X 1 × … × X n ) → M ( 1 + 1 ) and an input distribution μ \mu μ we recover the split μ ↦ ( 1 f − 1 ( 0 ) ⋅ μ , 1 f − 1 ( 1 ) ⋅ μ ) \mu\mapsto(\mathbf{1}_{f^{-1}(0)}\cdot\mu,\mathbf{1}_{f^{-1}(1)}\cdot\mu) μ ↦ ( 1 f − 1 ( 0 ) ⋅ μ , 1 f − 1 ( 1 ) ⋅ μ ) , where f ⋅ μ f\cdot\mu f ⋅ μ is the measure with density f f f w.r.t. to μ \mu μ . For an arbitrary guard we get the split μ ↦ ( f i f ⋅ μ , f e l s e ⋅ μ ) \mu\mapsto(f_{\mathrm{if}}\cdot\mu,f_{\mathrm{else}}\cdot\mu) μ ↦ ( f if ⋅ μ , f else ⋅ μ ) where f i f ( x 1 , … , x n ) = p ( δ x 1 ⊗ … ⊗ δ x n ) ( 1 ) f_{\mathrm{if}}(x_1,\ldots,x_n)=p(\delta_{x_1}\otimes\ldots\otimes\delta_{x_n})(1) f if ( x 1 , … , x n ) = p ( δ x 1 ⊗ … ⊗ δ x n ) ( 1 ) , the probability of ‘true’ at ( x 1 , … , x n ) (x_1,\ldots,x_n) ( x 1 , … , x n ) , and similarly for f e l s e f_{\mathrm{else}} f else . Thus ⟦ f l i p 1 / 2 ⟧ : M ( X 1 × … × X n ) → M ( 1 + 1 ) \llbracket\mathsf{flip}\ 1/2\rrbracket:\mathcal{M}(X_1\times\ldots\times X_n)\to\mathcal{M}(1+1) [ [ flip 1/2 ] ] : M ( X 1 × … × X n ) → M ( 1 + 1 ) yields μ ↦ ( μ / 2 , μ / 2 ) \mu\mapsto(\mu/2,\mu/2) μ ↦ ( μ /2 , μ /2 ) .
Measurement-based quantum control can be understood as an instance of our main if–then–else rule (2) interpreted by a conditionally branching structure on the category C P M ⊕ \mathsf{CPM}_{\oplus} CPM ⊕ provided by the notion of Lüders instrument [25 ] . Given a predicate p : X → C ⊕ C p:X\to\mathbb{C}\oplus\mathbb{C} p : X → C ⊕ C , we can define two operators X → X X\to X X → X via I p = p † π 1 p I_p=p^\dagger\pi_1p I p = p † π 1 p and E p = p † π 2 p E_p=p^\dagger\pi_2p E p = p † π 2 p where p † p^\dagger p † is the adjoint of p p p and π i : C ⊕ C → C ⊕ C \pi_i:\mathbb{C}\oplus\mathbb{C}\to\mathbb{C}\oplus\mathbb{C} π i : C ⊕ C → C ⊕ C is the projection onto the i i i th component. The notion of Lüders instrument then provides us the splitting map C X ( p ) : X → X ⊕ X C_X(p):X\to X\oplus X C X ( p ) : X → X ⊕ X , ρ ↦ ( I p ρ I p , E p ρ E p ) \rho\mapsto(\sqrt{I_p}\rho\sqrt{I_p},\sqrt{E_p}\rho\sqrt{E_p}) ρ ↦ ( I p ρ I p , E p ρ E p ) . With this, we can revisit Example 4 and type the program as
x : q u b i t ⊢ m e a s ( x ) : b i t x , y : q u b i t ⊢ x ⊗ y : q u b i t ⊗ q u b i t x , y : q u b i t ⊢ x ⊗ Z y : q u b i t ⊗ q u b i t x:\mathsf{qubit}\vdash\mathsf{meas}(x):\mathsf{bit}\qquad x,y:\mathsf{qubit}\vdash x\otimes y:\mathsf{qubit}\otimes\mathsf{qubit}\qquad x,y:\mathsf{qubit}\vdash x\otimes\mathsf{Z}y:\mathsf{qubit}\otimes\mathsf{qubit} x : qubit ⊢ meas ( x ) : bit x , y : qubit ⊢ x ⊗ y : qubit ⊗ qubit x , y : qubit ⊢ x ⊗ Z y : qubit ⊗ qubit
x , y : q u b i t ⊢ i f m e a s ( x ) t h e n x ⊗ y e l s e x ⊗ Z y : q u b i t ⊗ q u b i t x,y:\mathsf{qubit}\vdash\mathsf{if\ meas}(x)\mathsf{\ then\ }x\otimes y\mathsf{\ else\ }x\otimes\mathsf{Z}y:\mathsf{qubit}\otimes\mathsf{qubit} x , y : qubit ⊢ if meas ( x ) then x ⊗ y else x ⊗ Z y : qubit ⊗ qubit
The instrument corresponding to m e a s ( x ) \mathsf{meas}(x) meas ( x ) is given by the projections I m e a s ( x ) = ∣ 0 ⟩ ⟨ 0 ∣ I_{\mathsf{meas}(x)}=|0\rangle\langle0| I meas ( x ) = ∣0 ⟩ ⟨ 0∣ and E m e a s ( x ) = ∣ 1 ⟩ ⟨ 1 ∣ E_{\mathsf{meas}(x)}=|1\rangle\langle1| E meas ( x ) = ∣1 ⟩ ⟨ 1∣ yielding the semantics ⟦ i f m e a s ( x ) t h e n x ⊗ y e l s e x ⊗ Z y ⟧ \llbracket\mathsf{if\ meas}(x)\mathsf{\ then\ }x\otimes y\mathsf{\ else\ }x\otimes\mathsf{Z}y\rrbracket [ [ if meas ( x ) then x ⊗ y else x ⊗ Z y ] ] given by (10):
( A B C D ) ↦ [ id ⊗ id , id ⊗ Z ] ∘ ( C ( ⟦ m e a s ⟧ ) ⊗ id ) ( A B C D ) = ( A 0 0 Z D Z † ) \begin{pmatrix} A & B \\ C & D \end{pmatrix}\mapsto[\operatorname{id}\otimes\operatorname{id},\operatorname{id}\otimes\mathsf{Z}]\circ(C(\llbracket\mathsf{meas}\rrbracket)\otimes\operatorname{id})\begin{pmatrix} A & B \\ C & D \end{pmatrix}=\begin{pmatrix} A & 0 \\ 0 & \mathsf{Z}D\mathsf{Z}^{\dagger} \end{pmatrix} ( A C B D ) ↦ [ id ⊗ id , id ⊗ Z ] ∘ ( C ( [ [ meas ] ] ) ⊗ id ) ( A C B D ) = ( A 0 0 Z D Z † )
The key difference with the semantics of § 2.2 is that the qubit x x x remains accessible (in its collapsed state) to the computation. The guard modifies its context, it does not consume it.
Coherent quantum control can also be understood as an instance of rule (2) interpreted via a conditionally branching structure, but unfortunately not in the same category as above (C P M ⊕ \mathrm{CPM}_{\oplus} CPM ⊕ is in some sense designed to tackle measurements). Consider the category Hilb of finite-dimensional Hilbert spaces and bounded operators (we cannot restrict to contractions as coproducts would then not exist). We interpret coherent control in this category in much the same way as we did above: given p : X → C ⊕ C p : X \to\mathbb{C} \oplus\mathbb{C} p : X → C ⊕ C , define I p , E p I_p, E_p I p , E p as above and the choice functions C X ( p ) : X → X ⊕ X C_X(p) : X \to X \oplus X C X ( p ) : X → X ⊕ X as x ↦ ( I p x , E p x ) x \mapsto(I_p x, E_p x) x ↦ ( I p x , E p x ) . With this ‘instrument’ we can interpret the CNOT gate represented as the program
x : q u b i t ⊢ x : b i t x , y : q u b i t ⊢ x ⊗ y : q u b i t ⊗ q u b i t x , y : q u b i t ⊢ x ⊗ not y : q u b i t ⊗ q u b i t x , y : q u b i t ⊢ if x then x ⊗ y else x ⊗ not y : q u b i t ⊗ q u b i t \begin{aligned}
x : \mathrm{qubit} &\vdash x : \mathrm{bit} \qquad x,y : \mathrm{qubit} \vdash x \otimes y : \mathrm{qubit} \otimes\mathrm{qubit} \qquad x,y : \mathrm{qubit} \vdash x \otimes\operatorname{not} y : \mathrm{qubit} \otimes\mathrm{qubit}\\
x,y : \mathrm{qubit} &\vdash\operatorname{if}\ x\ \operatorname{then}\ x \otimes y\ \operatorname{else}\ x \otimes\operatorname{not} y : \mathrm{qubit} \otimes\mathrm{qubit}
\end{aligned} x : qubit x , y : qubit ⊢ x : bit x , y : qubit ⊢ x ⊗ y : qubit ⊗ qubit x , y : qubit ⊢ x ⊗ not y : qubit ⊗ qubit ⊢ if x then x ⊗ y else x ⊗ not y : qubit ⊗ qubit
where we tacitly use the trivial/identity test x : q u b i t ⊢ x : b i t x : \mathrm{qubit} \vdash x : \mathrm{bit} x : qubit ⊢ x : bit which exploits the fact that ⟦ q u b i t ⟧ = ⟦ b i t ⟧ = C 2 \llbracket\mathrm{qubit}\rrbracket= \llbracket\mathrm{bit}\rrbracket= \mathbb{C}^{2} [ [ qubit ] ] = [ [ bit ] ] = C 2 in Hilb. The semantics is then given by [ i d ⊗ i d , i d ⊗ ⟦ not ⟧ ] ∘ ⟨ I p , E p ⟩ [\mathrm{id} \otimes\mathrm{id},\mathrm{id} \otimes\llbracket\operatorname{not}\rrbracket] \circ\langle I_p,E_p\rangle [ id ⊗ id , id ⊗ [ [ not ] ] ] ∘ ⟨ I p , E p ⟩ that splits a 00 ∣ 00 ⟩ + a 01 ∣ 01 ⟩ + a 10 ∣ 10 ⟩ + a 11 ∣ 11 ⟩ a_{00}|00\rangle+ a_{01}|01\rangle+ a_{10}|10\rangle+ a_{11}|11\rangle a 00 ∣00 ⟩ + a 01 ∣01 ⟩ + a 10 ∣10 ⟩ + a 11 ∣11 ⟩ into ( a 00 ∣ 00 ⟩ + a 01 ∣ 01 ⟩ , a 10 ∣ 10 ⟩ + a 11 ∣ 11 ⟩ ) (a_{00}|00\rangle+ a_{01}|01\rangle, a_{10}|10\rangle+ a_{11}|11\rangle) ( a 00 ∣00 ⟩ + a 01 ∣01 ⟩ , a 10 ∣10 ⟩ + a 11 ∣11 ⟩) and then applies both branches in superposition to yield a 00 ∣ 00 ⟩ + a 01 ∣ 01 ⟩ + a 10 ∣ 11 ⟩ + a 11 ∣ 10 ⟩ a_{00}|00\rangle+ a_{01}|01\rangle+ a_{10}|11\rangle+ a_{11}|10\rangle a 00 ∣00 ⟩ + a 01 ∣01 ⟩ + a 10 ∣11 ⟩ + a 11 ∣10 ⟩ as expected. Note that unlike (9) , the context of the guard is shared with the branches.
Proposition 26. The choice functions defined above define a commutative and idempotent conditionally branching structure on Hilb for sharp predicates, i.e. predicates satisfying im ( I p ) = ker ( E p ) \operatorname{im}(I_p) = \operatorname{ker}(E_p) im ( I p ) = ker ( E p ) .
Remark 27. Unifying the two types of control semantically is notoriously difficult [37 ] . Hilb cannot deal with measurements and, conversely, applying the Lüders instrument of C P M ⊕ \mathrm{CPM}_{\oplus} CPM ⊕ to coherent control yields the wrong semantics, e.g. in the CNOT case it would ignore the cross-terms B , C B,C B , C . We settle for the structural unification provided by (2) and (10) .
Structure of branching morphisms and tests
Having defined conditionally branching categories as a simple categorical structure in which to interpret if–then–else statements via ‘branching morphisms’, we now turn our attention to studying the algebraic structure of branching morphisms and of tests in a conditionally branching category.
Structure of the sets (X, X+X) of branching morphisms
In § 3 we defined three special morphisms: true X , false X , not X : X + X → X + X \operatorname{true}_X,\operatorname{false}_X,\operatorname{not}_X : X + X \to X + X true X , false X , not X : X + X → X + X which can be viewed as defining unary operations on C ( X , X + X ) \mathcal{C}(X,X+X) C ( X , X + X ) by post-composition. We can also define two constants on C ( X , X + X ) \mathcal{C}(X,X+X) C ( X , X + X ) : ⊤ X = in 1 : X → X + X \top_X = \operatorname{in}_1 : X \to X + X ⊤ X = in 1 : X → X + X and ⊥ X = in 2 : X → X + X \bot_X = \operatorname{in}_2 : X \to X + X ⊥ X = in 2 : X → X + X . What about branching operations on branching morphisms? Such operations should exist if we are to understand nested if–then–else statements branching from X X X to X + X + X + X X + X + X + X X + X + X + X . If we view branching morphisms X → X + X X \to X + X X → X + X as morphisms X → T X X \to TX X → T X for the functor T = I d + I d T = \mathrm{Id} + \mathrm{Id} T = Id + Id and manage to equip T T T with a monad structure, then this would also equip the set C ( X , X + X ) \mathcal{C}(X, X + X) C ( X , X + X ) – viewed as the set C T ( X , X ) \mathcal{C}_T(X, X) C T ( X , X ) – with an operation for combining nested branchings. To see which monad structures on T = I d + I d T = \mathrm{Id} + \mathrm{Id} T = Id + Id are useful, we list all such structures in the case of the category Set.
Theorem 28. The following unit-multiplication pairs define monad structures on the functor T = I d + I d T = \mathrm{Id} + \mathrm{Id} T = Id + Id in any category with coproducts.
η = i n 1 , μ = [ i d , n o t ] \eta= \mathrm{in}_1, \mu= [\mathrm{id},\mathrm{not}] η = in 1 , μ = [ id , not ]
η = i n 1 , μ = ∧ \eta= \mathrm{in}_1, \mu= \wedge η = in 1 , μ = ∧
η = i n 2 , μ = [ n o t , i d ] \eta= \mathrm{in}_2, \mu= [\mathrm{not},\mathrm{id}] η = in 2 , μ = [ not , id ]
η = i n 2 , μ = ∨ \eta= \mathrm{in}_2, \mu= \vee η = in 2 , μ = ∨
In Set these are the only possible monad structures on T T T .
It follows that C ( X , X + X ) \mathcal{C}(X, X + X) C ( X , X + X ) can always be equipped with four monoidal structures. For f , g ∈ C ( X , X + X ) f, g \in\mathcal{C}(X, X + X) f , g ∈ C ( X , X + X ) we write f ∧ g f \wedge g f ∧ g for the branching morphism ∧ ∘ ( g + g ) ∘ f \wedge\circ(g + g) \circ f ∧ ∘ ( g + g ) ∘ f (we drop subscripts in the interest of clarity), and similarly for ∨ \vee ∨ . For branching morphisms generated by tests in a conditionally branching category ∨ , ∧ \vee,\wedge ∨ , ∧ have the following algebraic structure.
Proposition 29. For any tests p , q , r : X → I + I p, q, r : X \to I + I p , q , r : X → I + I in a conditionally branching category,
C ( p ) ∨ ( C ( q ) ∨ C ( r ) ) = ( C ( p ) ∨ C ( q ) ) ∨ C ( r ) C(p) \vee(C(q) \vee C(r)) = (C(p) \vee C(q)) \vee C(r) C ( p ) ∨ ( C ( q ) ∨ C ( r )) = ( C ( p ) ∨ C ( q )) ∨ C ( r )
C ( p ) ∧ ( C ( q ) ∧ C ( r ) ) = ( C ( p ) ∧ C ( q ) ) ∧ C ( r ) C(p) \wedge(C(q) \wedge C(r)) = (C(p) \wedge C(q)) \wedge C(r) C ( p ) ∧ ( C ( q ) ∧ C ( r )) = ( C ( p ) ∧ C ( q )) ∧ C ( r )
not ( not C ( p ) ) = C ( p ) \operatorname{not}(\operatorname{not} C(p)) = C(p) not ( not C ( p )) = C ( p )
not ( C ( p ) ∧ C ( q ) ) = C ( not p ) ∨ C ( not q ) \operatorname{not}(C(p) \wedge C(q)) = C(\operatorname{not} p) \vee C(\operatorname{not} q) not ( C ( p ) ∧ C ( q )) = C ( not p ) ∨ C ( not q )
not ( C ( p ) ∨ C ( q ) ) = C ( not p ) ∧ C ( not q ) \operatorname{not}(C(p) \vee C(q)) = C(\operatorname{not} p) \wedge C(\operatorname{not} q) not ( C ( p ) ∨ C ( q )) = C ( not p ) ∧ C ( not q )
If the conditionally branching structure is idempotent then
⊤ ∨ C ( p ) = C ( p ) ∨ ⊤ = ⊤ \top\vee C(p) = C(p) \vee\top= \top ⊤ ∨ C ( p ) = C ( p ) ∨ ⊤ = ⊤
⊥ ∧ C ( p ) = C ( p ) ∧ ⊥ = ⊥ \bot\wedge C(p) = C(p) \wedge\bot= \bot ⊥ ∧ C ( p ) = C ( p ) ∧ ⊥ = ⊥
If the conditionally branching structure is commutative then
C ( p ) ∨ C ( q ) = C ( q ) ∨ C ( p ) C(p) \vee C(q) = C(q) \vee C(p) C ( p ) ∨ C ( q ) = C ( q ) ∨ C ( p )
C ( p ) ∧ C ( q ) = C ( q ) ∧ C ( p ) C(p) \wedge C(q) = C(q) \wedge C(p) C ( p ) ∧ C ( q ) = C ( q ) ∧ C ( p )
Remark 30. Since not \operatorname{not} not is involutive and relates ∨ \vee ∨ and ∧ \wedge ∧ via de Morgan laws, ∧ \wedge ∧ can be defined in terms of ∨ \vee ∨ and vice-versa. The basic structure (items 1-5) of branching morphisms is thus that of an involutive magma. It is tempting to assume that the operators ∨ \vee ∨ and ∧ \wedge ∧ satisfy other boolean identities. Probabilistic computations provides some easy counter-examples. Let p , q , r : X → D ( 1 + 1 ) p, q, r : X \to D(1 + 1) p , q , r : X → D ( 1 + 1 ) be probabilistic tests and let us write p p p for p ( x ) ( 1 ) p(x)(1) p ( x ) ( 1 ) .
C ( p ) ∧ C ( p ) = C ( p ) C(p) \wedge C(p) = C(p) C ( p ) ∧ C ( p ) = C ( p ) doesn’t hold since it would imply p p = p pp = p pp = p which isn’t generally true.
Similarly, C ( p ) ∨ C ( p ) = C ( p ) C(p) \vee C(p) = C(p) C ( p ) ∨ C ( p ) = C ( p ) doesn’t hold since it would imply ( 1 − p ) ( 1 − p ) = ( 1 − p ) (1 - p)(1 - p) = (1 - p) ( 1 − p ) ( 1 − p ) = ( 1 − p ) .
C ( p ) ∨ C ( not p ) = ⊤ C(p) \vee C(\operatorname{not} p) = \top C ( p ) ∨ C ( not p ) = ⊤ and C ( p ) ∧ C ( not q ) = ⊥ C(p) \wedge C(\operatorname{not} q) = \bot C ( p ) ∧ C ( not q ) = ⊥ do not hold since p ( 1 − p ) ≠ 0 p(1 - p) \ne0 p ( 1 − p ) = 0 in general.
C ( p ) ∧ ( C ( q ) ∨ C ( r ) ) = ( C ( p ) ∧ C ( q ) ) ∨ ( C ( p ) ∧ C ( r ) ) C(p) \wedge(C(q) \vee C(r)) = (C(p) \wedge C(q)) \vee(C(p) \wedge C(r)) C ( p ) ∧ ( C ( q ) ∨ C ( r )) = ( C ( p ) ∧ C ( q )) ∨ ( C ( p ) ∧ C ( r )) does not hold as it would imply that
p ( 1 − ( 1 − q ) ( 1 − r ) ) = p q r p + p r ( 1 − p r ) + ( 1 − p q ) p r p(1 - (1 - q)(1 - r)) = pqrp + pr(1 - pr) + (1 - pq)pr p ( 1 − ( 1 − q ) ( 1 − r )) = pq r p + p r ( 1 − p r ) + ( 1 − pq ) p r
which does not hold in general. The other distributivity laws similarly does not hold.
Structure of the sets ( X , I + I ) (X, I + I) ( X , I + I ) of predicates
We can use the conditionally branching structure on a category C \mathcal{C} C to define binary operations on the set of tests C ( X , I + I ) \mathcal{C}(X, I + I) C ( X , I + I ) as follows. For p , q : X → I + I p, q : X \to I + I p , q : X → I + I , we overload ∨ , ∧ \vee,\wedge ∨ , ∧ and define:
p ∨ q ≜ ∨ ∘ ( q + q ) ∘ C X ( p ) (15) p \vee q \triangleq\vee\circ(q + q) \circ C_X(p) \tag*{(15)} p ∨ q ≜ ∨ ∘ ( q + q ) ∘ C X ( p ) (15)
p ∧ q ≜ ∧ ∘ ( q + q ) ∘ C X ( p ) (16) p \wedge q \triangleq\wedge\circ(q + q) \circ C_X(p) \tag*{(16)} p ∧ q ≜ ∧ ∘ ( q + q ) ∘ C X ( p ) (16)
With these operations we recover part of a familiar algebraic structure on sets of predicates.
Proposition 31. Predicates on an object X X X in a conditionally branching category form an involutive magma ( C ( X , I + I ) , ∧ , not ) (\mathcal{C}(X, I + I), \wedge, \operatorname{not}) ( C ( X , I + I ) , ∧ , not ) (resp. ( C ( X , I + I ) , ∨ , not ) (\mathcal{C}(X, I + I), \vee, \operatorname{not}) ( C ( X , I + I ) , ∨ , not ) ). If the conditionally branching structure is commutative, so is ∧ \wedge ∧ (resp. ∨ \vee ∨ ).
Example 32 (The boolean algebra of non-deterministic tests). Consider finitely branching non-deterministic computations given by the finite powerset monad P f \mathcal{P}_f P f on Set. The corresponding choice functions are given by (14) . It is straightforward to compute (15) –(16) and we get for p , q : X → P f ( 1 + 1 ) p,q:X\to\mathcal{P}_f(1+1) p , q : X → P f ( 1 + 1 ) that 1 ∈ ( p ∨ q ) ( x ) ⇔ 1 ∈ p ( x ) ∪ q ( x ) 1\in(p\mathbin{\vee}q)(x)\Leftrightarrow1\in p(x)\cup q(x) 1 ∈ ( p ∨ q ) ( x ) ⇔ 1 ∈ p ( x ) ∪ q ( x ) and 1 ∈ ( p ∧ q ) ( x ) ⇔ 1 ∈ p ( x ) ∩ q ( x ) 1\in(p\mathbin{\wedge}q)(x)\Leftrightarrow1\in p(x)\cap q(x) 1 ∈ ( p ∧ q ) ( x ) ⇔ 1 ∈ p ( x ) ∩ q ( x ) , and dually for 2 2 2 (i.e. false) 2 ∈ ( p ∨ q ) ( x ) ⇔ 2 ∈ p ( x ) ∩ q ( x ) 2\in(p\mathbin{\vee}q)(x)\Leftrightarrow2\in p(x)\cap q(x) 2 ∈ ( p ∨ q ) ( x ) ⇔ 2 ∈ p ( x ) ∩ q ( x ) and 2 ∈ ( p ∧ q ) ( x ) ⇔ 2 ∈ p ( x ) ∪ q ( x ) 2\in(p\mathbin{\wedge}q)(x)\Leftrightarrow2\in p(x)\cup q(x) 2 ∈ ( p ∧ q ) ( x ) ⇔ 2 ∈ p ( x ) ∪ q ( x ) .
Example 33 (The involutive magma of probabilistic tests). Consider now finitely branching probabilistic computations given by the distribution monad D \mathcal{D} D on Set, again with the choice functions defined by (14) . Given probabilistic tests p , q : X → D ( 1 + 1 ) p,q:X\to\mathcal{D}(1+1) p , q : X → D ( 1 + 1 ) , we compute
( p ∧ q ) ( x ) ( 1 ) = p ( x ) ( 1 ) q ( x ) ( 1 ) ( p ∨ q ) ( x ) ( 1 ) = p ( x ) ( 1 ) + q ( x ) ( 1 ) − p ( x ) ( 1 ) q ( x ) ( 1 ) \begin{aligned}
(p\mathbin{\wedge}q)(x)(1)&=p(x)(1)q(x)(1)\\
(p\mathbin{\vee}q)(x)(1)&=p(x)(1)+q(x)(1)-p(x)(1)q(x)(1)
\end{aligned} ( p ∧ q ) ( x ) ( 1 ) ( p ∨ q ) ( x ) ( 1 ) = p ( x ) ( 1 ) q ( x ) ( 1 ) = p ( x ) ( 1 ) + q ( x ) ( 1 ) − p ( x ) ( 1 ) q ( x ) ( 1 ) Thus probabilistic tests carry the standard probabilistic structure on [ 0 , 1 ] [0,1] [ 0 , 1 ] (sometimes know as product t t t -norm and sum t t t -conorm in fuzzy logic, pointwise, when evaluated at 1 1 1 , and the dual structure when evaluated at 2 2 2 .
By Definition 5 , choice functions C X : C ( X , I + I ) → C ( X , X + X ) C_X:\mathcal{C}(X,I+I)\to\mathcal{C}(X,X+X) C X : C ( X , I + I ) → C ( X , X + X ) always commute with the unary operators true, not. In some instance we can also prove that they act as monoid homomorphisms between the ∨ \vee ∨ - and ∧ \wedge ∧ -structures described in Propositions 29 and 31.
Proposition 34. If C X ( p ∨ q ) = C X ( p ) ∨ C X ( q ) C_X(p\mathbin{\vee}q)=C_X(p)\mathbin{\vee}C_X(q) C X ( p ∨ q ) = C X ( p ) ∨ C X ( q ) and C X ( p ∧ q ) = C X ( p ) ∧ C X ( q ) C_X(p\mathbin{\wedge}q)=C_X(p)\mathbin{\wedge}C_X(q) C X ( p ∧ q ) = C X ( p ) ∧ C X ( q ) then both ( C ( X , I + I ) , ∧ , not ) (\mathcal{C}(X,I+I),\wedge,\operatorname{not}) ( C ( X , I + I ) , ∧ , not ) and ( C ( X , I + I ) , ∨ , not ) (\mathcal{C}(X,I+I),\vee,\operatorname{not}) ( C ( X , I + I ) , ∨ , not ) form involutive magmas. If the conditionally branching structure is commutative, they are also commutative. This holds for the conditionally branching structures defined by (13) .
Not all the structure of C ( X , X + X ) \mathcal{C}(X,X+X) C ( X , X + X ) can carry over to C ( X , I + I ) \mathcal{C}(X,I+I) C ( X , I + I ) . The constant branching morphisms ⊤ , ⊥ \top,\bot ⊤ , ⊥ have in general no test equivalents since there is in general no distinguished morphism X → I X\to I X → I ; some objects in Ban for example have no such morphisms.
Skew-associativity
When the structure on the set of tests is sufficiently rich, we can generalise the skew-associativity rule of GKAT to more general types of computations. The extra structure needed is the following. We define the relation ≲ \lesssim ≲ on ( C ( X , I + I ) , ∧ ) (\mathcal{C}(X,I+I),\wedge) ( C ( X , I + I ) , ∧ ) by p ≲ q ⇔ ∃ r : p = q ∧ r p\lesssim q\Leftrightarrow\exists r:p=q\wedge r p ≲ q ⇔ ∃ r : p = q ∧ r . The relation is transitive whenever ∧ \wedge ∧ is associative, i.e. whenever ( C ( X , I + I ) , ∧ ) (\mathcal{C}(X,I+I),\wedge) ( C ( X , I + I ) , ∧ ) is a magma.
We will say that ( C ( X , I + I ) , ∧ ) (\mathcal{C}(X,I+I),\wedge) ( C ( X , I + I ) , ∧ ) is conditionally divisible if for all tests p , q ∈ C ( X , I + I ) p,q\in\mathcal{C}(X,I+I) p , q ∈ C ( X , I + I ) such that p ≤ q p\le q p ≤ q there exists a test p q ∈ C ( X , I + I ) \frac{p}{q}\in\mathcal{C}(X,I+I) q p ∈ C ( X , I + I ) such that q ∧ p q = p q\wedge\frac{p}{q}=p q ∧ q p = p .
Interestingly, we will need the same technical condition on the base category C \mathcal{C} C as made in [18 Eq. (4.3)] , namely that the maps [ id X , ∇ X ] , [ not X , id X ] : X + X + X → X + X [\operatorname{id}_X,\nabla_X],[\operatorname{not}_X,\operatorname{id}_X]:X+X+X\to X+X [ id X , ∇ X ] , [ not X , id X ] : X + X + X → X + X are jointly monic. This condition is satisfied in Set and therefore in any concrete category.
Theorem 35. Let C \mathcal{C} C be a conditionally branching category satisfying the condition above and the identities of Proposition 34. Whenever ( C ( X , I + I ) , ∧ ) (\mathcal{C}(X,I+I),\wedge) ( C ( X , I + I ) , ∧ ) is conditionally divisible and p ∧ not q ≲ not ( p ∧ q ) p\wedge\operatorname{not}q\lesssim\operatorname{not}(p\wedge q) p ∧ not q ≲ not ( p ∧ q ) we have:
( id + ∇ ) ∘ ( C ( q ) + C ( q ) ) ∘ C ( p ) = ( ∇ + id ) ∘ ( C ( p ∧ not q not ( p ∧ q ) ) + C ( p ∧ not q not ( p ∧ q ) ) ) ∘ C ( p ∧ q ) (\operatorname{id}+\nabla)\circ(C(q)+C(q))\circ C(p)=(\nabla+\operatorname{id})\circ\left(C\left(\frac{p\wedge\operatorname{not}q}{\operatorname{not}(p\wedge q)}\right)+C\left(\frac{p\wedge\operatorname{not}q}{\operatorname{not}(p\wedge q)}\right)\right)\circ C(p\wedge q) ( id + ∇ ) ∘ ( C ( q ) + C ( q )) ∘ C ( p ) = ( ∇ + id ) ∘ ( C ( not ( p ∧ q ) p ∧ not q ) + C ( not ( p ∧ q ) p ∧ not q ) ) ∘ C ( p ∧ q ) It is straightforward to check that the previous theorem implies that if the tests p ∧ q p\wedge q p ∧ q and p ∧ not q not ( p ∧ q ) \frac{p\wedge\operatorname{not}q}{\operatorname{not}(p\wedge q)} not ( p ∧ q ) p ∧ not q can be realised as the semantics of programs p & q p\mathbin{\&}q p & q and p ∙ q p\mathbin{\bullet}q p ∙ q then the following generalisation of GKAT’s skew-associativity rule holds:
⟦ Γ ⊢ if p then (if q then s 1 else s 2 ) else s 3 ⟧ = ⟦ Γ ⊢ if p & q then s 1 else (if p ∙ q then s 2 else s 3 ) ⟧ . \llbracket\Gamma\vdash\text{if }p\text{ then (if }q\text{ then }s_1\text{ else }s_2)\text{ else }s_3\rrbracket
=
\llbracket\Gamma\vdash\text{if }p\mathbin{\&}q\text{ then }s_1\text{ else (if }p\mathbin{\bullet}q\text{ then }s_2\text{ else }s_3)\rrbracket. [ [ Γ ⊢ if p then (if q then s 1 else s 2 ) else s 3 ] ] = [ [ Γ ⊢ if p & q then s 1 else (if p ∙ q then s 2 else s 3 ) ] ] .
Example 36. The (pointwise) boolean structure on non-deterministic tests is conditionally divisible. The relation ⪯ \preceq ⪯ is the standard lattice order, we trivially have that p ∧ not q ⪯ not ( p ∧ q ) p \wedge\operatorname{not} q \preceq\operatorname{not}(p \wedge q) p ∧ not q ⪯ not ( p ∧ q ) , and we can take p ∧ not q not ( p ∧ q ) = ( ( not ( p ∧ q ) → p ∧ not q ) \frac{p \wedge\operatorname{not} q}{\operatorname{not}(p \wedge q)} = ((\operatorname{not}(p \wedge q) \to p \wedge\operatorname{not} q) not ( p ∧ q ) p ∧ not q = (( not ( p ∧ q ) → p ∧ not q ) which is just equivalent to p p p and recover exactly the skew-associativity of GKAT stated in § 3.
Example 37. The (pointwise) involutive magma structure of probabilistic tests is conditionally divisible. The relation ⪯ \preceq ⪯ is the standard order on [ 0 , 1 ] [0,1] [ 0 , 1 ] , we trivially have p ( 1 − q ) ⪯ ( 1 − p q ) p(1-q) \preceq(1-pq) p ( 1 − q ) ⪯ ( 1 − pq ) , and we take p ∧ not q not ( p ∧ q ) = p ( 1 − q ) ( 1 − p q ) \frac{p \wedge\operatorname{not} q}{\operatorname{not}(p \wedge q)} = \frac{p(1-q)}{(1-pq)} not ( p ∧ q ) p ∧ not q = ( 1 − pq ) p ( 1 − q ) (with the convention that 0 0 = 0 \frac{0}{0}=0 0 0 = 0 , no other zeroes in the denominator are possible by definition of conditional divisibility). We then recover the skew-associativity rule of barycentric algebras discussed in e.g. [26 ] :
( e + q f ) + p g = e p q ( f + p − p q 1 − p q g ) (e +_{q} f) +_{p} g = e_{pq}\left(f +_{\frac{p-pq}{1-pq}} g\right) ( e + q f ) + p g = e pq ( f + 1 − pq p − pq g )
Conclusion
We have surveyed several inequivalent semantics for conditional branching found in the literature, covering a range of computational paradigms (classical, effectful, probabilistic, quantum). We saw that even in linear (i.e. resource-sensitive) semantics, such as those of probabilistic, quantum or effectful computations, it is possible to interpret non-linear if-then-else statements whose guards do not consume their context, cf. typing rule (2). The variety of existing semantics begs the question: is there a unifying ‘minimal’ structure required to interpret the if-then-else rule (2)?
To answer this question we have focused on the central construct required to interpret conditional branching, the coproduct . Fundamentally, this is the structure that allows us to combine the interpretations of the if-branch and of the else-branch into a single program. The question is then to construct a branching behaviour into this coproduct based on a guard. This is where we introduce our notion of conditionally branching category , a monoidal distributive category equipped with a way of turning guards – i.e. predicates – into branching behaviours. Our definition echoes that of traced monoidal category and is ‘minimal’ in the sense that it is as parsimonious as possible, with only two combinatorially obvious requirements enforcing the equivalences if p p p then s s s else t t t ≡ \equiv ≡ if not p p p then t t t else s s s and if true then s s s else t t t ≡ s \equiv s ≡ s . These are purely combinatorial in the sense that they refer only to the basic combinatorial properties of the coproduct (via the maps not, true: I + I → I + I I + I \to I + I I + I → I + I ). Additional program equivalences follow from additional demands on the conditionally branching structure (e.g. idempotence, commutativity).
We have shown that a wide range of semantically important categories possess canonical conditionally branching structures, and in particular categories supporting the two types of branching found in quantum computing: measurement-based control and coherent control. It would be nice to find a category that could cover both at the same time, either through a unifying conditionally branching structure, or through two dedicated conditionally branching structures (but defined on the same category).
We have also shown that a conditionally branching structure gives rise to algebraic structures on sets C ( X , X + X ) \mathcal{C}(X, X + X) C ( X , X + X ) of branching morphisms and on sets C ( X , I + I ) \mathcal{C}(X, I + I) C ( X , I + I ) of predicates. The richness of these structures depends on the requirements put on the conditionally branching structure, but in most cases, we obtain an involutive magma. For non-deterministic and probabilistic computations, we recover known structures and show program equivalences for nested branching corresponding to the skew-associativity rules of GKAT and barycentric algebras respectively. We believe that a lot more can be said about the structure of predicates in conditionally branching categories, both in general and in interesting special cases.
Proofs for Section 3
Lemma 38. The following diagram commutes in any distributive category
X ⊗ ( Y + Z ) → f ⊗ [ g , h ] X ⊗ W ↘ l d i s t r X , Y , Z ↗ [ f ⊗ g , f ⊗ h ] ( X ⊗ Y ) + ( X ⊗ Z ) \begin{aligned}
X \otimes(Y+Z) &\xrightarrow{f\otimes[g,h]} X \otimes W \\
&\searrow{\mathrm{ldistr}_{X,Y,Z}} \qquad\nearrow{[f\otimes g,f\otimes h]} \\
& (X\otimes Y)+(X\otimes Z)
\end{aligned} X ⊗ ( Y + Z ) f ⊗ [ g , h ] X ⊗ W ↘ ldistr X , Y , Z ↗ [ f ⊗ g , f ⊗ h ] ( X ⊗ Y ) + ( X ⊗ Z ) and similarly for right-distributivity.
Proof. We look at the inverse of l d i s t r X , Y , Z \mathrm{ldistr}_{X,Y,Z} ldistr X , Y , Z and get the following commutative diagram which proves the assertion.
X ⊗ Y → i d X ⊗ i n 1 X ⊗ Y + X ⊗ Z ← i d X ⊗ i n 2 X ⊗ Z ↘ ↑ l d i s t r − 1 ↗ X ⊗ ( Y + Z ) ↗ f ⊗ g ↑ f ⊗ [ g , h ] ↘ f ⊗ h X ⊗ W \begin{aligned}
X\otimes Y &\xrightarrow{\mathrm{id}_{X}\otimes\mathrm{in}_{1}} X\otimes Y+X\otimes Z \xleftarrow{\mathrm{id}_{X}\otimes\mathrm{in}_{2}} X\otimes Z \\
&\searrow\qquad\uparrow{\mathrm{ldistr}^{-1}} \qquad\nearrow\\
&\qquad X\otimes(Y+Z) \\
&\nearrow{f\otimes g}\qquad\uparrow{f\otimes[g,h]}\qquad\searrow{f\otimes h} \\
&\qquad X\otimes W
\end{aligned} X ⊗ Y id X ⊗ in 1 X ⊗ Y + X ⊗ Z id X ⊗ in 2 X ⊗ Z ↘ ↑ ldistr − 1 ↗ X ⊗ ( Y + Z ) ↗ f ⊗ g ↑ f ⊗ [ g , h ] ↘ f ⊗ h X ⊗ W
Proof of Theorem 6. 1. Skew-commutativity follows from the commutativity of this diagram:
⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ → C ⟦ Γ ⟧ ( ⟦ p ⟧ ) ⊗ i d ⟦ Δ ⟧ ( ⟦ Γ ⟧ + ⟦ Γ ⟧ ) ⊗ Δ → r d i s t r ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ + ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ ↘ C ⟦ Γ ⟧ ( n o t p ) ⊗ i d ⟦ Δ ⟧ ↓ n o t ⟦ Γ ⟧ ⊗ i d ⟦ Δ ⟧ ↓ [ ⟦ s ⟧ , ⟦ t ⟧ ] ( ⟦ Γ ⟧ + ⟦ Γ ⟧ ) ⊗ ⟦ Δ ⟧ → r d i s t r ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ + ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ ↘ n o t ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ ↓ [ ⟦ t ⟧ , ⟦ s ⟧ ] ⟦ T ⟧ \begin{aligned}
\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket
&\xrightarrow{C_{\llbracket\Gamma\rrbracket}(\llbracket p\rrbracket)\otimes\mathrm{id}_{\llbracket\Delta\rrbracket}}
(\llbracket\Gamma\rrbracket+\llbracket\Gamma\rrbracket)\otimes\Delta
\xrightarrow{\mathrm{rdistr}}
\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket+\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket\\
&\searrow{C_{\llbracket\Gamma\rrbracket}(\mathrm{not}\ p)\otimes\mathrm{id}_{\llbracket\Delta\rrbracket}}
\qquad\downarrow{\mathrm{not}_{\llbracket\Gamma\rrbracket}\otimes\mathrm{id}_{\llbracket\Delta\rrbracket}}
\qquad\downarrow{[\llbracket s\rrbracket,\llbracket t\rrbracket]} \\
&\qquad(\llbracket\Gamma\rrbracket+\llbracket\Gamma\rrbracket)\otimes\llbracket\Delta\rrbracket
\xrightarrow{\mathrm{rdistr}}
\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket+\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket
\searrow{\mathrm{not}_{\llbracket\Gamma\rrbracket}\otimes\llbracket\Delta\rrbracket} \\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\downarrow{[\llbracket t\rrbracket,\llbracket s\rrbracket]} \\
&\qquad\qquad\qquad\qquad\qquad\qquad\qquad\llbracket T\rrbracket
\end{aligned} [ [ Γ ] ] ⊗ [ [ Δ ] ] C [ [ Γ ] ] ( [ [ p ] ] ) ⊗ id [ [ Δ ] ] ( [ [ Γ ] ] + [ [ Γ ] ] ) ⊗ Δ rdistr [ [ Γ ] ] ⊗ [ [ Δ ] ] + [ [ Γ ] ] ⊗ [ [ Δ ] ] ↘ C [ [ Γ ] ] ( not p ) ⊗ id [ [ Δ ] ] ↓ not [ [ Γ ] ] ⊗ id [ [ Δ ] ] ↓ [ [ [ s ] ] , [ [ t ] ] ] ( [ [ Γ ] ] + [ [ Γ ] ] ) ⊗ [ [ Δ ] ] rdistr [ [ Γ ] ] ⊗ [ [ Δ ] ] + [ [ Γ ] ] ⊗ [ [ Δ ] ] ↘ not [ [ Γ ] ] ⊗ [ [ Δ ] ] ↓ [ [ [ t ] ] , [ [ s ] ] ] [ [ T ] ]
where the left-hand triangle commutes by the skew-commutativity axiom. The bottom right-hand triangle commutes trivially and the central square can also be seen to commute by considering the inverse of r d i s t r \mathrm{rdistr} rdistr , namely [ i n 1 ⊗ i d ⟦ Δ ⟧ , i n 2 ⊗ i d ⟦ Δ ⟧ ] [\mathrm{in}_{1}\otimes\mathrm{id}_{\llbracket\Delta\rrbracket},\mathrm{in}_{2}\otimes\mathrm{id}_{\llbracket\Delta\rrbracket}] [ in 1 ⊗ id [ [ Δ ] ] , in 2 ⊗ id [ [ Δ ] ] ] .
The proof for the true test is the essentially the same of the previous case but with not replaced by true.
Idempotence follows from the commutativity of the following diagram
⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ → C ⟦ Γ ⟧ ( ⟦ p ⟧ ) ⊗ i d ⟦ Δ ⟧ ( ⟦ Γ ⟧ + ⟦ Γ ⟧ ) ⊗ Δ → r d i s t r ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ + ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ ↘ ↓ ∇ ⟦ Γ ⟧ ⊗ i d ⟦ Δ ⟧ ↓ [ ⟦ s ⟧ , ⟦ s ⟧ ] ⟦ Γ ⟧ ⊗ ⟦ Δ ⟧ → [ ⟦ s ⟧ ] ⟦ T ⟧ \begin{aligned}
\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket
&\xrightarrow{C_{\llbracket\Gamma\rrbracket}(\llbracket p\rrbracket)\otimes\mathrm{id}_{\llbracket\Delta\rrbracket}}
(\llbracket\Gamma\rrbracket+\llbracket\Gamma\rrbracket)\otimes\Delta
\xrightarrow{\mathrm{rdistr}}
\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket+\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket\\
&\searrow\qquad\downarrow{\nabla_{\llbracket\Gamma\rrbracket}\otimes\mathrm{id}_{\llbracket\Delta\rrbracket}}
\qquad\downarrow{[\llbracket s\rrbracket,\llbracket s\rrbracket]} \\
&\qquad\llbracket\Gamma\rrbracket\otimes\llbracket\Delta\rrbracket
\xrightarrow{[\llbracket s\rrbracket]}
\llbracket T\rrbracket
\end{aligned} [ [ Γ ] ] ⊗ [ [ Δ ] ] C [ [ Γ ] ] ( [ [ p ] ] ) ⊗ id [ [ Δ ] ] ( [ [ Γ ] ] + [ [ Γ ] ] ) ⊗ Δ rdistr [ [ Γ ] ] ⊗ [ [ Δ ] ] + [ [ Γ ] ] ⊗ [ [ Δ ] ] ↘ ↓ ∇ [ [ Γ ] ] ⊗ id [ [ Δ ] ] ↓ [ [ [ s ] ] , [ [ s ] ] ] [ [ Γ ] ] ⊗ [ [ Δ ] ] [ [ [ s ] ] ] [ [ T ] ]
The left-hand triangle commutes by virtue of the idempotence axiom. The top triangle of the right-hand square commutes by Lemma 38, the bottom one commutes trivially.
Commutativity follows immediately from the definitions.
Proof of Proposition 7. The morphism [ Γ , Δ ⊢ if p then let x = s 1 in t else let x = s 2 in t : T ] [\Gamma,\Delta\vdash\text{if }p\text{ then let }x=s_1\text{ in }t\text{ else let }x=s_2\text{ in }t:T] [ Γ , Δ ⊢ if p then let x = s 1 in t else let x = s 2 in t : T ] is given by the top path of the diagram below whilst the morphism [ Γ ′ , Δ ′ ⊢ let x = ( if p then s 1 else s 2 ) in t : T ] [\Gamma',\Delta' \vdash\text{let }x=(\text{if }p\text{ then }s_1\text{ else }s_2)\text{ in }t:T] [ Γ ′ , Δ ′ ⊢ let x = ( if p then s 1 else s 2 ) in t : T ] follows the path below it. Commutativity follows directly from the definitions.
[ [ Γ ] ] ⊗ [ [ Δ ] ] → rdistr ∘ [ [ Γ ] ] ( p ) ⊗ id [ [ Δ ] ] ( [ [ Γ ] ] ⊗ [ [ Δ ] ] ) + ( [ [ Γ ] ] ⊗ [ [ Δ ] ] ) → [ [ let x = s 1 in t ] ] , [ [ let x = s 2 in t ] ] [ [ T ] ] ∥ ↓ [ [ s 1 ] ] ⊗ id Δ ′ , [ [ s 2 ] ] ⊗ id Δ ′ ↗ [ [ t ] ] [ [ Γ ′ ] ] ⊗ [ [ Δ ′ ] ] → [ [ if p then s 1 else s 2 ] ] [ [ S ] ] ⊗ [ [ Δ ′ ] ] \begin{aligned}
[\![\Gamma]\!] \otimes[\![\Delta]\!] &\xrightarrow{\operatorname{rdistr}_{\circ}[\![\Gamma]\!](p)\otimes\operatorname{id}[\![\Delta]\!]} ([\![\Gamma]\!]\otimes[\![\Delta]\!])+([\![\Gamma]\!]\otimes[\![\Delta]\!]) \xrightarrow{[\![\text{let }x=s_1\text{ in }t]\!],[\![\text{let }x=s_2\text{ in }t]\!]} [\![T]\!] \\
\Big\Vert&& \Big\downarrow[\![s_1]\!]\otimes\operatorname{id}_{\Delta'},[\![s_2]\!]\otimes\operatorname{id}_{\Delta'} \qquad\qquad\nearrow[\![t]\!] \\
[\![\Gamma']\!]\otimes[\![\Delta']\!] &\xrightarrow{[\![\text{if }p\text{ then }s_1\text{ else }s_2]\!]} [\![S]\!]\otimes[\![\Delta']\!]&
\end{aligned} [ [ Γ ] ] ⊗ [ [ Δ ] ] [ [ Γ ′ ] ] ⊗ [ [ Δ ′ ] ] rdistr ∘ [ [ Γ ] ] ( p ) ⊗ id [ [ Δ ] ] ([ [ Γ ] ] ⊗ [ [ Δ ] ]) + ([ [ Γ ] ] ⊗ [ [ Δ ] ]) [ [ let x = s 1 in t ] ] , [ [ let x = s 2 in t ] ] [ [ T ] ] [ [ if p then s 1 else s 2 ] ] [ [ S ] ] ⊗ [ [ Δ ′ ] ] ↓ ⏐ [ [ s 1 ] ] ⊗ id Δ ′ , [ [ s 2 ] ] ⊗ id Δ ′ ↗ [ [ t ] ]
Proofs for Section 4
Proofs of Theorems 13 and 14. To simplify the notation we will often omit the right unitors in what follows and consider X X X and X ⊗ I X\otimes I X ⊗ I interchangeably.
Skew-commutativity: This identity holds by virtue of the definition of C X C_X C X and the commutativity of the following diagram:
X ⊗ ( I + I ) ← [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X ↓ id X ⊗ not ↓ not X = [ in 2 , in 1 ] X ⊗ ( I + I ) ← [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X \begin{aligned}
X\otimes(I+I) &\xleftarrow{[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]} X+X \\
\downarrow{\operatorname{id}_X\otimes\operatorname{not}} & \qquad\downarrow{\operatorname{not}_X=[\operatorname{in}_2,\operatorname{in}_1]} \\
X\otimes(I+I) &\xleftarrow{[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]} X+X
\end{aligned} X ⊗ ( I + I ) ↓ id X ⊗ not X ⊗ ( I + I ) [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X ↓ not X = [ in 2 , in 1 ] [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X
The horizontal arrows in the other direction are ldistr X \operatorname{ldistr}_X ldistr X . which holds since
[ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ not X ∘ in 1 = [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 2 = id X ⊗ in 2 = ( id X ⊗ not ) ∘ ( id X ⊗ in 1 ) = ( id X ⊗ not ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 1 \begin{aligned}
[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]\circ\operatorname{not}_X\circ\operatorname{in}_1
&=[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]\circ\operatorname{in}_2\\
&=\operatorname{id}_X\otimes\operatorname{in}_2\\
&=(\operatorname{id}_X\otimes\operatorname{not})\circ(\operatorname{id}_X\otimes\operatorname{in}_1)\\
&=(\operatorname{id}_X\otimes\operatorname{not})\circ[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]\circ\operatorname{in}_1
\end{aligned} [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ not X ∘ in 1 = [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 2 = id X ⊗ in 2 = ( id X ⊗ not ) ∘ ( id X ⊗ in 1 ) = ( id X ⊗ not ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 1
and similarly for the pre-composition with in 2 \operatorname{in}_2 in 2 . The commutativity of the square with left-to-right horizontal arrows now follows by the universal property of the coproduct, and the commutativity of the square with right-to-left horizontal arrows follows from the fact that the horizontal arrows are inverse of one another.
True test: This identity can be shown to hold in the same way as the previous one. Consider the diagram
X ⊗ ( I + I ) ← [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X ↓ id X ⊗ true ↓ true X = [ in 1 , in 1 ] X ⊗ ( I + I ) ← [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X \begin{aligned}
X\otimes(I+I) &\xleftarrow{[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]} X+X \\
\downarrow{\operatorname{id}_X\otimes\operatorname{true}} & \qquad\downarrow{\operatorname{true}_X=[\operatorname{in}_1,\operatorname{in}_1]} \\
X\otimes(I+I) &\xleftarrow{[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]} X+X
\end{aligned} X ⊗ ( I + I ) ↓ id X ⊗ true X ⊗ ( I + I ) [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X ↓ true X = [ in 1 , in 1 ] [ id X ⊗ in 1 , id X ⊗ in 2 ] X + X
We have
[ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ true X ∘ in 1 = [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 1 = id X ⊗ in 1 = ( id X ⊗ true ) ∘ ( id X ⊗ in 1 ) = ( id X ⊗ true ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 1 \begin{aligned}
[\operatorname{id}_{X}\otimes\operatorname{in}_{1},\operatorname{id}_{X}\otimes\operatorname{in}_{2}]\circ\operatorname{true}_{X}\circ\operatorname{in}_{1}
&=[\operatorname{id}_{X}\otimes\operatorname{in}_{1},\operatorname{id}_{X}\otimes\operatorname{in}_{2}]\circ\operatorname{in}_{1}\\
&=\operatorname{id}_{X}\otimes\operatorname{in}_{1}\\
&=(\operatorname{id}_{X}\otimes\operatorname{true})\circ(\operatorname{id}_{X}\otimes\operatorname{in}_{1})\\
&=(\operatorname{id}_{X}\otimes\operatorname{true})\circ[\operatorname{id}_{X}\otimes\operatorname{in}_{1},\operatorname{id}_{X}\otimes\operatorname{in}_{2}]\circ\operatorname{in}_{1}
\end{aligned} [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ true X ∘ in 1 = [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 1 = id X ⊗ in 1 = ( id X ⊗ true ) ∘ ( id X ⊗ in 1 ) = ( id X ⊗ true ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ in 1
and similarly for the pre-composition with in 2 \operatorname{in}_{2} in 2 . The result follows as in the previous case.
3. Commutativity. The proof hinges on the commutativity of the following diagram connecting distributivity, the symmetry transformations γ A , B : A ⊗ B → B ⊗ A \gamma_{A,B}:A\otimes B\to B\otimes A γ A , B : A ⊗ B → B ⊗ A of the symmetric monoidal category, and the permutation [ in 1 , in 3 , in 2 , in 4 ] [\operatorname{in}_{1},\operatorname{in}_{3},\operatorname{in}_{2},\operatorname{in}_{4}] [ in 1 , in 3 , in 2 , in 4 ] of the commutativity definition
A ⊗ C + B ⊗ C + A ⊗ D + B ⊗ D → [ in 1 ∘ γ , in 3 ∘ γ , in 2 ∘ γ , in 4 ∘ γ ] C ⊗ A + D ⊗ A + C ⊗ B + D ⊗ B [ in 1 ⊗ in 1 , in 2 ⊗ in 1 , in 1 ⊗ in 2 , in 2 ⊗ in 2 ] ↓ ↓ ( rdistr + rdistr ∘ ldistr ) − 1 ( A + B ) ⊗ ( C + D ) → γ ( A + B ) , ( C + D ) ( C + D ) ⊗ ( A + B ) \begin{CD}
A\otimes C+B\otimes C+A\otimes D+B\otimes D @>{[\operatorname{in}_{1}\circ\gamma,\operatorname{in}_{3}\circ\gamma,\operatorname{in}_{2}\circ\gamma,\operatorname{in}_{4}\circ\gamma]}>> C\otimes A+D\otimes A+C\otimes B+D\otimes B\\
@V{[\operatorname{in}_{1}\otimes\operatorname{in}_{1},\operatorname{in}_{2}\otimes\operatorname{in}_{1},\operatorname{in}_{1}\otimes\operatorname{in}_{2},\operatorname{in}_{2}\otimes\operatorname{in}_{2}]}VV @VV{(\operatorname{rdistr}+\operatorname{rdistr}\circ\operatorname{ldistr})^{-1}}V\\
(A+B)\otimes(C+D) @>{\gamma_{(A+B),(C+D)}}>> (C+D)\otimes(A+B)
\end{CD} A ⊗ C + B ⊗ C + A ⊗ D + B ⊗ D [ in 1 ⊗ in 1 , in 2 ⊗ in 1 , in 1 ⊗ in 2 , in 2 ⊗ in 2 ] ↓ ⏐ ( A + B ) ⊗ ( C + D ) [ in 1 ∘ γ , in 3 ∘ γ , in 2 ∘ γ , in 4 ∘ γ ] γ ( A + B ) , ( C + D ) C ⊗ A + D ⊗ A + C ⊗ B + D ⊗ B ↓ ⏐ ( rdistr + rdistr ∘ ldistr ) − 1 ( C + D ) ⊗ ( A + B )
The commutativity of this diagram can be checked straightforwardly by examining each summand of the top-left-hand corner individually and using the universal property of coproducts. This establishes the commutativity of the central square in the following diagram
X → copy X X ⊗ X → copy X X ⊗ X id ⊗ p ↓ ↓ id ⊗ q X ⊗ ( I + I ) → q ⊗ id ( I + I ) ⊗ ( I + I ) ← p ⊗ id X ⊗ ( I + I ) ldistr ↓ ldistr ↓ ↓ ldistr ( X ⊗ I ) + ( X ⊗ I ) → ( q ⊗ id ) + ( q ⊗ id ) ( ( I + I ) ⊗ I ) + ( ( I + I ) ⊗ I ) ← ( p ⊗ id ) + ( p ⊗ id ) ( X ⊗ I ) + ( X ⊗ I ) ρ X + ρ X ↓ rdistr + rdistr ↓ ↓ ρ X + ρ X X + X I ⊗ I + I ⊗ I + I ⊗ I + I ⊗ I X + X q + q ↓ [ ρ , ρ ] + [ ρ , ρ ] ↓ ↓ p + p I + I + I + I → [ in 1 , in 3 , in 2 , in 4 ] I + I + I + I \begin{CD}
X @>{\operatorname{copy}_{X}}>> X\otimes X @>{\operatorname{copy}_{X}}>> X\otimes X\\
@. @V{\operatorname{id}\otimes p}VV @VV{\operatorname{id}\otimes q}V\\
X\otimes(I+I) @>{q\otimes\operatorname{id}}>> (I+I)\otimes(I+I) @<{\operatorname{p}\otimes\operatorname{id}}<< X\otimes(I+I)\\
@V{\operatorname{ldistr}}VV @V{\operatorname{ldistr}}VV @VV{\operatorname{ldistr}}V\\
(X\otimes I)+(X\otimes I) @>{(q\otimes\operatorname{id})+(q\otimes\operatorname{id})}>> ((I+I)\otimes I)+((I+I)\otimes I) @<{{(p\otimes\operatorname{id})+(p\otimes\operatorname{id})}}<< (X\otimes I)+(X\otimes I)\\
@V{\rho_{X}+\rho_{X}}VV @V{\operatorname{rdistr}+\operatorname{rdistr}}VV @VV{\rho_{X}+\rho_{X}}V\\
X+X @. I\otimes I+I\otimes I+I\otimes I+I\otimes I @. X+X\\
@V{q+q}VV @V{[\rho,\rho]+[\rho,\rho]}VV @VV{p+p}V\\
I+I+I+I @>{[\operatorname{in}_{1},\operatorname{in}_{3},\operatorname{in}_{2},\operatorname{in}_{4}]}>> I+I+I+I
\end{CD} X X ⊗ ( I + I ) ldistr ↓ ⏐ ( X ⊗ I ) + ( X ⊗ I ) ρ X + ρ X ↓ ⏐ X + X q + q ↓ ⏐ I + I + I + I copy X q ⊗ id ( q ⊗ id ) + ( q ⊗ id ) [ in 1 , in 3 , in 2 , in 4 ] X ⊗ X id ⊗ p ↓ ⏐ ( I + I ) ⊗ ( I + I ) ldistr ↓ ⏐ (( I + I ) ⊗ I ) + (( I + I ) ⊗ I ) rdistr + rdistr ↓ ⏐ I ⊗ I + I ⊗ I + I ⊗ I + I ⊗ I [ ρ , ρ ] + [ ρ , ρ ] ↓ ⏐ I + I + I + I copy X p ⊗ id ( p ⊗ id ) + ( p ⊗ id ) X ⊗ X ↓ ⏐ id ⊗ q X ⊗ ( I + I ) ↓ ⏐ ldistr ( X ⊗ I ) + ( X ⊗ I ) ↓ ⏐ ρ X + ρ X X + X ↓ ⏐ p + p
The left- and right-hand pentagons can be seen to commute by showing [ ρ I , ρ I ] ∘ rdistr = ρ I + I [\rho_{I},\rho_{I}]\circ\operatorname{rdistr}=\rho_{I+I} [ ρ I , ρ I ] ∘ rdistr = ρ I + I using the definition of rdistr as the inverse of the canonical morphism and then applying naturality of the unitor. The result now follows immediately.
4. Short-circuiting . Assume that
I → s X h ↓ ↓ p I → in i I + I \begin{CD}
I @>{s}>> X\\
@V{h}VV @VV{p}V\\
I @>{\operatorname{in}_{i}}>> I+I
\end{CD} I h ↓ ⏐ I s in i X ↓ ⏐ p I + I
with s s s deterministic. Now consider the following diagram;
I → s X copy I ↓ ↓ copy X I ⊗ I → s ⊗ s X ⊗ X s ⊗ h ↓ ↓ id X ⊗ p X ⊗ I → id X ⊗ in i X ⊗ ( I + I ) in i ↓ ↓ ldistr X X → in i X + X X → C X ( p ) X + X \begin{CD}
I @>{s}>> X\\
@V{\operatorname{copy}_I}VV @VV{\operatorname{copy}_X}V\\
I\otimes I @>{s\otimes s}>> X\otimes X\\
@V{s\otimes h}VV @VV{\operatorname{id}_X\otimes p}V\\
X\otimes I @>{\operatorname{id}_X\otimes\operatorname{in}_i}>> X\otimes(I+I)\\
@V{\operatorname{in}_i}VV @VV{\operatorname{ldistr}_X}V\\
X @>{\operatorname{in}_i}>> X+X
\end{CD}
\qquad
\begin{CD}
X @>{C_X(p)}>> X+X
\end{CD} I copy I ↓ ⏐ I ⊗ I s ⊗ h ↓ ⏐ X ⊗ I in i ↓ ⏐ X s s ⊗ s id X ⊗ in i in i X ↓ ⏐ copy X X ⊗ X ↓ ⏐ id X ⊗ p X ⊗ ( I + I ) ↓ ⏐ ldistr X X + X X C X ( p ) X + X
The top square commutes by definition of deterministic morphisms. The bottom triangle is seen to commute by using the fact that ldistr X \operatorname{ldistr}_X ldistr X is the inverse of [ id X ⊗ in 1 , id ⊗ in 2 ] [\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}\otimes\operatorname{in}_2] [ id X ⊗ in 1 , id ⊗ in 2 ] .
5. Idempotence: We now assume a Markov category, in particular I = 1 I=1 I = 1 is terminal. As the following diagram shows, it follows from the universal property of the coproduct that ( id X ⊗ ∇ 1 ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] = ∇ X (\operatorname{id}_X\otimes\nabla_1)\circ[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]=\nabla_X ( id X ⊗ ∇ 1 ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] = ∇ X :
X ⊗ I → id X ⊗ ∇ 1 X ⊗ I id X ⊗ id I = id X ⊗ I ↓ ↑ id X ⊗ id I = id X ⊗ I X ⊗ I + X ⊗ I → [ id X ⊗ in 1 , id X ⊗ in 2 ] X ⊗ ( I + I ) \begin{CD}
X\otimes I @>{\operatorname{id}_X\otimes\nabla_1}>> X\otimes I\\
@V{\operatorname{id}_X\otimes\operatorname{id}_I=\operatorname{id}_X\otimes I}VV @AA{\operatorname{id}_X\otimes\operatorname{id}_I=\operatorname{id}_X\otimes I}A\\
X\otimes I+X\otimes I @>{[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]}>> X\otimes(I+I)
\end{CD} X ⊗ I id X ⊗ id I = id X ⊗ I ↓ ⏐ X ⊗ I + X ⊗ I id X ⊗ ∇ 1 [ id X ⊗ in 1 , id X ⊗ in 2 ] X ⊗ I ⏐ ↑ id X ⊗ id I = id X ⊗ I X ⊗ ( I + I )
We now have (ignoring the trivial role of the right unitor X ⊗ I ≃ X X\otimes I\simeq X X ⊗ I ≃ X )
∇ X ∘ C X ( p ) = ( id X ⊗ ∇ 1 ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ C X ( p ) = ( id X ⊗ ∇ 1 ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ ldistr X ∘ ( id X ⊗ p ) ∘ ( copy X ⊗ id I ) = ( id X ⊗ ∇ 1 ) ∘ ( id X ⊗ p ) ∘ ( copy X ⊗ id I ) = ( id X ⊗ ! X ⊗ I ) ∘ ( copy X ⊗ id I ) ≃ id X ⊗ I \begin{aligned}
\nabla_X\circ C_X(p)
&=(\operatorname{id}_X\otimes\nabla_1)\circ[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]\circ C_X(p)\\
&=(\operatorname{id}_X\otimes\nabla_1)\circ[\operatorname{id}_X\otimes\operatorname{in}_1,\operatorname{id}_X\otimes\operatorname{in}_2]\circ\operatorname{ldistr}_X\circ(\operatorname{id}_X\otimes p)\circ(\operatorname{copy}_X\otimes\operatorname{id}_I)\\
&=(\operatorname{id}_X\otimes\nabla_1)\circ(\operatorname{id}_X\otimes p)\circ(\operatorname{copy}_X\otimes\operatorname{id}_I)\\
&=(\operatorname{id}_X\otimes!_X\otimes I)\circ(\operatorname{copy}_X\otimes\operatorname{id}_I)\\
&\simeq\operatorname{id}_{X\otimes I}
\end{aligned} ∇ X ∘ C X ( p ) = ( id X ⊗ ∇ 1 ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ C X ( p ) = ( id X ⊗ ∇ 1 ) ∘ [ id X ⊗ in 1 , id X ⊗ in 2 ] ∘ ldistr X ∘ ( id X ⊗ p ) ∘ ( copy X ⊗ id I ) = ( id X ⊗ ∇ 1 ) ∘ ( id X ⊗ p ) ∘ ( copy X ⊗ id I ) = ( id X ⊗ ! X ⊗ I ) ∘ ( copy X ⊗ id I ) ≃ id X ⊗ I
where the penultimate step follows from the fact that I I I is terminal (and thus ∇ 1 ∘ p = ! X ⊗ I \nabla_1\circ p=!_{X\otimes I} ∇ 1 ∘ p = ! X ⊗ I ) and the last step follows from the copy-discard interaction (up to a unitor, hence the ≃ \simeq ≃ ).
Proof of Proposition 19. Let us first show that if a map I → f X + X → del + del I + I I\xrightarrow{f}X+X\xrightarrow{\operatorname{del}+\operatorname{del}}I+I I f X + X del + del I + I factors through in 1 : I → I + I \operatorname{in}_1:I\to I+I in 1 : I → I + I then f f f factors through in 1 : X → X + X \operatorname{in}_1:X\to X+X in 1 : X → X + X . By the weak pullback assumption we have a unique mediating morphism
I → f X + X g ↓ ↓ d e l + d e l I → i n 1 I + I \begin{CD}
I @>{f}>> X + X \\
@V{g}VV @VV{\mathrm{del}+\mathrm{del}}V \\
I @>{\mathrm{in}_1}>> I + I
\end{CD} I g ↓ ⏐ I f in 1 X + X ↓ ⏐ del + del I + I
and similarly if ( d e l + d e l ) ∘ f = i n 2 (\mathrm{del}+\mathrm{del})\circ f=\mathrm{in}_2 ( del + del ) ∘ f = in 2 . Next we show that given a predicate p : X → I + I p:X\to I+I p : X → I + I and a any state s : I → X s:I\to X s : I → X , if p ∘ s p\circ s p ∘ s factors through i n 1 : I → I + I \mathrm{in}_1:I\to I+I in 1 : I → I + I , then so does
( d e l + d e l ) ∘ C X ( p ) ∘ s (\mathrm{del}+\mathrm{del})\circ C_X(p)\circ s ( del + del ) ∘ C X ( p ) ∘ s
and similarly for i n 2 \mathrm{in}_2 in 2 . This follows immediately from the commutativity of the diagram:
I → C X ( p ) X ⊗ X → i d ⊗ p X ⊗ ( I + I ) → l d i s t r ( X ⊗ I ) + ( X ⊗ I ) → ρ X + ρ X X + X s ↓ c o p y X ↓ d e l ⊗ ( i d I + i d I ) ↓ [ d e l ⊗ i d I , d e l ⊗ i d I ] ↓ ↓ d e l + d e l X → d e l ⊗ p I ⊗ ( I + I ) → l d i s t r ( I ⊗ I ) + ( I ⊗ I ) → ρ I + ρ I I + I \begin{CD}
I @>{C_X(p)}>> X\otimes X @>{\mathrm{id}\otimes p}>> X\otimes(I+I) @>{\mathrm{ldistr}}>> (X\otimes I)+(X\otimes I) @>{\rho_X+\rho_X}>> X+X \\
@V{s}VV @V{\mathrm{copy}_X}VV @V{\mathrm{del}\otimes(\mathrm{id}_I+\mathrm{id}_I)}VV @V{[\mathrm{del}\otimes\mathrm{id}_I,\mathrm{del}\otimes\mathrm{id}_I]}VV @VV{\mathrm{del}+\mathrm{del}}V \\
X @>{\mathrm{del}\otimes p}>> I\otimes(I+I) @>{\mathrm{ldistr}}>> (I\otimes I)+(I\otimes I) @>{\rho_I+\rho_I}>> I+I
\end{CD} I s ↓ ⏐ X C X ( p ) del ⊗ p X ⊗ X copy X ↓ ⏐ I ⊗ ( I + I ) id ⊗ p ldistr X ⊗ ( I + I ) del ⊗ ( id I + id I ) ↓ ⏐ ( I ⊗ I ) + ( I ⊗ I ) ldistr ρ I + ρ I ( X ⊗ I ) + ( X ⊗ I ) [ del ⊗ id I , del ⊗ id I ] ↓ ⏐ I + I ρ X + ρ X X + X ↓ ⏐ del + del
Note that the CD-category structure is essential for the diagram above to commute
Proof of Theorem 23. The proof follows from the fact that the copairing of f : X → Z f:X\to Z f : X → Z , g : Y → Z g:Y\to Z g : Y → Z in C ( T ) \mathcal{C}(T) C ( T ) is given by μ ∘ T [ f , g ] \mu\circ T[f,g] μ ∘ T [ f , g ] in the base category, and the commutativity of the following diagrams:
Skew-commutativity:
X → C X ( p ) X + X → η X T ( X + X ) C X ( n o t p ) ↓ ↓ [ T i n 2 ∘ η X , T i n 1 ∘ η X ] ↓ T [ T i n 2 ∘ η X , T i n 1 ∘ η X ] X + X → n o t X = [ i n 2 , i n 1 ] T ( X + X ) → η T ( X + X ) T 2 ( X + X ) → μ X + X T ( X + X ) \begin{CD}
X @>{C_X(p)}>> X+X @>{\eta_X}>> T(X+X) \\
@V{C_X(\mathrm{not}\ p)}VV @VV{[T\mathrm{in}_2\circ\eta_X,T\mathrm{in}_1\circ\eta_X]}V @VV{T[T\mathrm{in}_2\circ\eta_X,T\mathrm{in}_1\circ\eta_X]}V \\
X+X @>{\mathrm{not}_X=[\mathrm{in}_2,\mathrm{in}_1]}>> T(X+X) @>{\eta_{T(X+X)}}>> T^2(X+X) @>{\mu_{X+X}}>> T(X+X)
\end{CD} X C X ( not p ) ↓ ⏐ X + X C X ( p ) not X = [ in 2 , in 1 ] X + X ↓ ⏐ [ T in 2 ∘ η X , T in 1 ∘ η X ] T ( X + X ) η X η T ( X + X ) T ( X + X ) ↓ ⏐ T [ T in 2 ∘ η X , T in 1 ∘ η X ] T 2 ( X + X ) μ X + X T ( X + X )
The bottom-left triangle commutes by naturality of η X \eta_X η X applied to both component of the copairing. Again the right-hand-vertical path is the copairing [ i n 2 , i n 1 ] [\mathrm{in}_2,\mathrm{in}_1] [ in 2 , in 1 ] , that is to say n o t X \mathrm{not}_X not X , in the category C T \mathcal{C}_T C T .
True test: The proof is the same as for skew-commutativity with not replaced by true.
Idempotence
X → c ^ X ( p ) T ( X + X ) c X ( p ) ↓ ↑ T [ η X , η X ] X + X → η X + X T ( X + X ) ∇ X ↓ ↑ [ η X , η X ] X → η X T X → η T X T 2 X → μ X T X \begin{CD}
X @>{\widehat{c}_{X}(p)}>> T(X+X) \\
@V{c_{X}(p)}VV @AA{T[\eta_X,\eta_X]}A \\
X+X @>{\eta_{X+X}}>> T(X+X) \\
@V{\nabla_X}VV @AA{[\eta_X,\eta_X]}A \\
X @>{\eta_X}>> TX @>{\eta_{TX}}>> T^2X @>{\mu_X}>> TX
\end{CD} X c X ( p ) ↓ ⏐ X + X ∇ X ↓ ⏐ X c X ( p ) η X + X η X T ( X + X ) ⏐ ↑ T [ η X , η X ] T ( X + X ) ⏐ ↑ [ η X , η X ] T X η T X T 2 X μ X T X
Where the right-hand-side vertical path is the codiagonal morphism in C T C_T C T and the bottom path the unit in C T C_T C T .
For the following proof we must assume some familiarity with the theory of Riesz spaces, Banach lattices and positive operators, see [3 Chapters 8,9] for a gentle introduction and [4 ] or [38 ] for a more in-depth account.
Proof of Theorem 24. Let us write e v p ev_p e v p for the functional ∇ R ∘ p \nabla_{\mathbb{R}} \circ p ∇ R ∘ p (an evaluation functional in the probabilistic case), p t p_t p t for π 1 ∘ p \pi_1 \circ p π 1 ∘ p (which measures how true the guard is for a given vector) and p f p_f p f for π 2 ∘ p \pi_2 \circ p π 2 ∘ p . If p t = e v p p_t = ev_p p t = e v p (and thus p f = 0 p_f = 0 p f = 0 ) then take x = x t x = x_t x = x t and x f = 0 x_f = 0 x f = 0 and conversely if p f = e v p p_f = ev_p p f = e v p .
Now assume that p t ≜ π 1 ∘ p p_t \triangleq\pi_1 \circ p p t ≜ π 1 ∘ p and p f ≜ π 2 ∘ p p_f \triangleq\pi_2 \circ p p f ≜ π 2 ∘ p are strictly positive and proceed in steps.
X X X is Archimedean and has the countable sup property : See [3 Thm 8.22]
X X X is Dedekind complete : This follows immediately from the fact that it is σ \sigma σ -Dedekind complete and has the countable sup property.
X X X has the Principal Projection Property : Let x ∈ X x \in X x ∈ X and let B x B_x B x be the principal band generated by x x x . For 0 ≤ y 0 \le y 0 ≤ y we define the projection P x : X → B x P_x : X \to B_x P x : X → B x as follows:
P x ( y ) = ⋁ { 0 ≤ u ≤ y ∣ u ∈ B x } . P_x(y) = \bigvee\{0 \le u \le y \mid u \in B_x\}. P x ( y ) = ⋁ { 0 ≤ u ≤ y ∣ u ∈ B x } .
Since 0 is certainly in the set above, and since it is bounded from above by y y y , the sup above exists by Dedekind-completeness. Since B x B_x B x is a band, it is closed under joins of directed sets and { 0 ≤ u ≤ y ∣ u ∈ B x } \{0 \le u \le y \mid u \in B_x\} { 0 ≤ u ≤ y ∣ u ∈ B x } is certainly a directed set of elements of B x B_x B x . It follows that P x ( y ) ∈ B x P_x(y) \in B_x P x ( y ) ∈ B x and thus that P x 2 = P x P_x^2 = P_x P x 2 = P x , i.e. P x P_x P x is a projection.
To see that P x P_x P x is linear let y , z ∈ X y,z \in X y , z ∈ X and note first that since P x ( y ) , P x ( z ) ∈ B x P_x(y), P_x(z) \in B_x P x ( y ) , P x ( z ) ∈ B x then P x ( y ) + P x ( z ) ∈ B x P_x(y) + P_x(z) \in B_x P x ( y ) + P x ( z ) ∈ B x , moreover P x ( y ) ≤ y P_x(y) \le y P x ( y ) ≤ y and P x ( z ) ≤ z P_x(z) \le z P x ( z ) ≤ z thus P x ( y ) + P x ( z ) ≤ y + z P_x(y) + P_x(z) \le y + z P x ( y ) + P x ( z ) ≤ y + z and thus P x ( y ) + P x ( z ) ≤ P x ( y + z ) P_x(y) + P_x(z) \le P_x(y + z) P x ( y ) + P x ( z ) ≤ P x ( y + z ) . For the other direction we use the fact that X X X is necessarily a Riesz space (since { u , v } \{u,v\} { u , v } is bounded above by u + v u + v u + v it follows that ⋁ { u , v } \bigvee\{u,v\} ⋁ { u , v } necessarily exists) and therefore has the Riesz decomposition property: for every $0 \le w \le y + z, t h e r e e x i s t s $ 0 ≤ w 1 ≤ y , 0 ≤ w 2 ≤ z , there exists \$0 \le w_1 \le y, 0 \le w_2 \le z , t h er ee x i s t s $0 ≤ w 1 ≤ y , 0 ≤ w 2 ≤ z such that w = w 1 + w 2 w = w_1 + w_2 w = w 1 + w 2 . It follows that for any element w w w in the set defining P x ( y + z ) P_x(y + z) P x ( y + z ) we can find a pair of elements w 1 , w 2 w_1,w_2 w 1 , w 2 in the sets defining P x ( y ) P_x(y) P x ( y ) and P x ( z ) P_x(z) P x ( z ) in particular w 1 + w 2 ≤ P x ( y ) + P x ( z ) w_1 + w_2 \le P_x(y) + P_x(z) w 1 + w 2 ≤ P x ( y ) + P x ( z ) . Since this holds for every element in the set defining P x ( y + z ) P_x(y + z) P x ( y + z ) we get P x ( y + z ) ≤ P x ( y ) + P x ( z ) P_x(y + z) \le P_x(y) + P_x(z) P x ( y + z ) ≤ P x ( y ) + P x ( z ) . Finally, we need to show that y − P x ( y ) y - P_x(y) y − P x ( y ) is disjoint from P x ( y ) P_x(y) P x ( y ) . If 0 < ( y − P x ( y ) ∧ y ) ≤ P x ( y ) 0 < (y - P_x(y) \wedge y) \le P_x(y) 0 < ( y − P x ( y ) ∧ y ) ≤ P x ( y ) then 0 < ( y − P x ( y ) ∧ y ) ∈ B x 0 < (y - P_x(y) \wedge y) \in B_x 0 < ( y − P x ( y ) ∧ y ) ∈ B x and thus ( y − P x ( y ) ∧ y ) + P x ( y ) ∈ B x (y - P_x(y) \wedge y) + P_x(y) \in B_x ( y − P x ( y ) ∧ y ) + P x ( y ) ∈ B x . Since ( y − P x ( y ) ∧ y ) + P x ( y ) ≤ y − P x ( y ) + P x ( y ) = P x ( y ) ≤ y (y - P_x(y) \wedge y) + P_x(y) \le y - P_x(y) + P_x(y) = P_x(y) \le y ( y − P x ( y ) ∧ y ) + P x ( y ) ≤ y − P x ( y ) + P x ( y ) = P x ( y ) ≤ y it belongs to the set defining P X ( y ) P_X(y) P X ( y ) but also P X ( y ) < ( y − P X ( y ) ∧ y ) + P X ( y ) P_X(y) < (y - P_X(y) \wedge y) + P_X(y) P X ( y ) < ( y − P X ( y ) ∧ y ) + P X ( y ) which contradicts the definition of P X ( y ) P_X(y) P X ( y ) as the supremum of such elements.
Construction of x t x_t x t and x f x_f x f . Note first that p t ≤ e v p p_t \le ev_p p t ≤ e v p and therefore p t p_t p t belongs to the ideal E e v p E_{ev_p} E e v p generated by e v p ev_p e v p in X ∼ X^\sim X ∼ , the space of order-bounded linear functionals on X X X . Since R \mathbb{R} R is a Dedekind-complete Riesz space, X ∼ X^\sim X ∼ is a Dedekind-complete Riesz space [4 Thm.1.18] , in particular it has the principal projection property as shown above. We therefore have all the conditions required to apply Freudenthal’s Spectral Theorem [4 Thm.2.8] to p t ∈ E e v p p_t \in E_{ev_p} p t ∈ E e v p . This guarantees the existence of an increasing sequence ξ n ↑ p t \xi_n \uparrow p_t ξ n ↑ p t of e v p ev_p e v p -simple functions, that is to say linear combinations of components of e v p ev_p e v p
ξ n = ∑ i N n α i ξ n , i \xi_n = \sum_{i}^{N_n} \alpha_i \xi_{n,i} ξ n = i ∑ N n α i ξ n , i
where ∑ i ξ n , i = e v p \sum_i \xi_{n,i} = ev_p ∑ i ξ n , i = e v p and ξ n , i ∧ ξ n , j = 0 \xi_{n,i} \wedge\xi_{n,j} = 0 ξ n , i ∧ ξ n , j = 0 , i ≠ j i \ne j i = j . Since X X X is Dedekind complete we can define for every ξ n , i \xi_{n,i} ξ n , i the vector
y n , i = ⋁ { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x ) } y_{n,i} = \bigvee\{0 \le u \le x \mid\xi_{n,i}(u) = \xi_{n,i}(x)\} y n , i = ⋁ { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x )}
We now associate to ξ n \xi_n ξ n the vector
y n = ∑ i N n α i y n , i ∈ X . y_n = \sum_i^{N_n} \alpha_i y_{n,i} \in X. y n = i ∑ N n α i y n , i ∈ X .
We claim that y n ≤ x y_n \le x y n ≤ x . If this is the case, and since X X X is σ \sigma σ -Dedekind complete we can define
x t ≜ ⋁ n y n . x_t \triangleq\bigvee_n y_n. x t ≜ n ⋁ y n .
The null ideal of ξ n , i \xi_{n,i} ξ n , i is defined as the set N n , i = { x ∈ X ∣ ξ n , i ( ∣ x ∣ ) = 0 } N_{n,i} = \{x \in X \mid\xi_{n,i}(|x|) = 0\} N n , i = { x ∈ X ∣ ξ n , i ( ∣ x ∣ ) = 0 } . Its disjoint complemented N n , i d = { x ∈ X ∣ ∣ x ∣ ⊥ ∣ y ∣ for all y ∈ N n , i } N_{n,i}^{d} = \{x \in X \mid|x| \perp|y| \text{ for all } y \in N_{n,i}\} N n , i d = { x ∈ X ∣ ∣ x ∣ ⊥ ∣ y ∣ for all y ∈ N n , i } is called the carrier C n , i C_{n,i} C n , i of ξ n , i \xi_{n,i} ξ n , i . Like the disjoint complement of any subset it is a band [3 §8.9] and since every band is a projection band in a Dedekind complete Riesz [4 Thm.1.41] X = C n , 1 ⊕ C n , 1 d X = C_{n,1} \oplus C_{n,1}^{d} X = C n , 1 ⊕ C n , 1 d . We can then decompose C n , 1 d C_{n,1}^{d} C n , 1 d according to ξ n , 2 \xi_{n,2} ξ n , 2 in the same way and decompose the entire space X X X into bands
X = C n , 1 ⊕ … ⊕ C n , N n ⊕ B r e s t X = C_{n,1} \oplus\ldots\oplus C_{n,N_n} \oplus B_{\mathrm{rest}} X = C n , 1 ⊕ … ⊕ C n , N n ⊕ B rest
since ξ n , i ⊥ ξ n , j \xi_{n,i} \perp\xi_{n,j} ξ n , i ⊥ ξ n , j is equivalent to C n , i ⊥ C n , j C_{n,i} \perp C_{n,j} C n , i ⊥ C n , j [4 Thm.1.67] . Thus for any x ∈ X x \in X x ∈ X we can find 0 ≤ x i ∈ C n , i 0 \le x_i \in C_{n,i} 0 ≤ x i ∈ C n , i such that x 1 + … + x N n ≤ x x_1 + \ldots+ x_{N_n} \le x x 1 + … + x N n ≤ x and ξ n , i ( x i ) = ξ n , i ( x ) \xi_{n,i}(x_i) = \xi_{n,i}(x) ξ n , i ( x i ) = ξ n , i ( x ) . Clearly y n , i ≤ x i y_{n,i} \le x_i y n , i ≤ x i . Since ξ n = ∑ i α i ξ n , i ≤ ∑ i ξ n , i = e v p \xi_n = \sum_i \alpha_i \xi_{n,i} \le\sum_i \xi_{n,i} = ev_p ξ n = ∑ i α i ξ n , i ≤ ∑ i ξ n , i = e v p and the ξ n , i \xi_{n,i} ξ n , i are pairwise disjoint (ξ n , i ⊥ ξ n , i \xi_{n,i} \perp\xi_{n,i} ξ n , i ⊥ ξ n , i ), it follows that each α i ≤ 1 \alpha_i \le1 α i ≤ 1 . We therefore have
y n = ∑ i α i y n , i ≤ ∑ i y n , i ≤ ∑ i x i ≤ x y_n = \sum_i \alpha_i y_{n,i} \le\sum_i y_{n,i} \le\sum_i x_i \le x y n = i ∑ α i y n , i ≤ i ∑ y n , i ≤ i ∑ x i ≤ x
as claimed, i.e. x t ∈ B x x_t \in B_x x t ∈ B x .
We now define x f ≜ x − x t ∈ B x x_f \triangleq x - x_t \in B_x x f ≜ x − x t ∈ B x which proves the first two assertions. Now we need to show that the assignment x ↦ ( x t , x f ) x \mapsto(x_t, x_f) x ↦ ( x t , x f ) is linear (it is clearly positive). To do this we just need to check that x ↦ x t x \mapsto x_t x ↦ x t is linear. To define x t + x t ′ x_t + x'_t x t + x t ′ at stage n n n we consider the sets
{ 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x ) } { 0 ≤ u ′ ≤ x ′ ∣ ξ n , i ( u ′ ) = ξ n , i ( x ′ ) } \{0 \le u \le x \mid\xi_{n,i}(u) = \xi_{n,i}(x)\}
\qquad
\{0 \le u' \le x' \mid\xi_{n,i}(u') = \xi_{n,i}(x')\} { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x )} { 0 ≤ u ′ ≤ x ′ ∣ ξ n , i ( u ′ ) = ξ n , i ( x ′ )}
For any such u , u ′ u,u' u , u ′ ξ n , i ( u + u ′ ) ≤ ξ n , i ( x + x ′ ) \xi_{n,i}(u+u')\leq\xi_{n,i}(x+x') ξ n , i ( u + u ′ ) ≤ ξ n , i ( x + x ′ ) and thus these u , u ′ u,u' u , u ′ are elements in
{ 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x + x ′ ) } \{0\leq u\leq x\mid\xi_{n,i}(u)=\xi_{n,i}(x+x')\} { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x + x ′ )}
and it follows that
⋀ { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x + x ′ ) } ≤ \bigwedge\{0\leq u\leq x\mid\xi_{n,i}(u)=\xi_{n,i}(x+x')\}\leq ⋀ { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x + x ′ )} ≤
⋀ { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x ) } + ⋀ { 0 ≤ u ′ ≤ x ∣ ξ n , i ( u ′ ) = ξ n , i ( x ′ ) } = \bigwedge\{0\leq u\leq x\mid\xi_{n,i}(u)=\xi_{n,i}(x)\}+
\bigwedge\{0\leq u'\leq x\mid\xi_{n,i}(u')=\xi_{n,i}(x')\}= ⋀ { 0 ≤ u ≤ x ∣ ξ n , i ( u ) = ξ n , i ( x )} + ⋀ { 0 ≤ u ′ ≤ x ∣ ξ n , i ( u ′ ) = ξ n , i ( x ′ )} =
⋀ { 0 ≤ u + u ′ ≤ x + x ′ ∣ ξ n , i ( u + u ′ ) ≤ ξ n , i ( x + x ′ ) } \bigwedge\{0\leq u+u'\leq x+x'\mid\xi_{n,i}(u+u')\leq\xi_{n,i}(x+x')\} ⋀ { 0 ≤ u + u ′ ≤ x + x ′ ∣ ξ n , i ( u + u ′ ) ≤ ξ n , i ( x + x ′ )}
For the converse we use the Riesz decomposition property as above. Thus the sequence defining ( x + x ′ ) t (x+x')_t ( x + x ′ ) t is constructed as the sum of the sequences defining x t , x t ′ x_t,x'_t x t , x t ′ and thus
( x + x ′ ) t = ⋁ n ( y n + y n ′ ) = ⋁ n y n + ⋁ n y n ′ = x t + x t ′ . (x+x')_t=\bigvee_n(y_n+y'_n)=\bigvee_n y_n+\bigvee_n y'_n=x_t+x'_t. ( x + x ′ ) t = n ⋁ ( y n + y n ′ ) = n ⋁ y n + n ⋁ y n ′ = x t + x t ′ .
∥ x t ∥ = ∥ ⋁ n y n ∥ = ⋁ n ∥ ∑ i α i y n , i ∥ Norm is order-continuous = ⋁ n ∑ i α i ∥ y n , i ∥ AL-space = ⋁ n ∑ i α i evp ( y n , i ) evp norm-preserving = ⋁ n ∑ i α i ξ n , i ( y n , i ) y n , i ∈ C n , i = ⋁ n ∑ i α i ξ n , i ( x ) definition of y n , i , ξ n , i order-continuous = ⋁ n ξ n ( x ) = p t ( x ) \begin{aligned}
\|x_t\|&=\left\|\bigvee_n y_n\right\|\\
&=\bigvee_n\left\|\sum_i\alpha_i y_{n,i}\right\| && \text{Norm is order-continuous}\\
&=\bigvee_n\sum_i\alpha_i\|y_{n,i}\| && \text{AL-space}\\
&=\bigvee_n\sum_i\alpha_i\operatorname{evp}(y_{n,i}) && \operatorname{evp}\text{ norm-preserving}\\
&=\bigvee_n\sum_i\alpha_i\xi_{n,i}(y_{n,i}) && y_{n,i}\in C_{n,i}\\
&=\bigvee_n\sum_i\alpha_i\xi_{n,i}(x) && \text{definition of }y_{n,i},\ \xi_{n,i}\text{ order-continuous}\\
&=\bigvee_n\xi_n(x)\\
&=p_t(x)
\end{aligned} ∥ x t ∥ = n ⋁ y n = n ⋁ i ∑ α i y n , i = n ⋁ i ∑ α i ∥ y n , i ∥ = n ⋁ i ∑ α i evp ( y n , i ) = n ⋁ i ∑ α i ξ n , i ( y n , i ) = n ⋁ i ∑ α i ξ n , i ( x ) = n ⋁ ξ n ( x ) = p t ( x ) Norm is order-continuous AL-space evp norm-preserving y n , i ∈ C n , i definition of y n , i , ξ n , i order-continuous
Conditionally branching structure. The skew-commutativity, true test axioms, idempotence and short-circuiting property follow directly from the definition of x f x_f x f as x − x t x-x_t x − x t and x t = x x_t=x x t = x when p f = evp p_f=\operatorname{evp} p f = evp .
Proof of Proposition 26. Both the Hilb and CPM⊕ _\oplus ⊕ case can be treated simultaneously by reasoning directly on the if and else operators I p I_p I p and E p E_p E p .
Skew-associativity: We show that I not p = E p I_{\operatorname{not} p}=E_p I not p = E p and the result follows immediately. Note that not : C 2 → C 2 \operatorname{not}:\mathbb{C}^2\to\mathbb{C}^2 not : C 2 → C 2 is given by ( 0 1 1 0 ) \begin{pmatrix}0&1\\1&0\end{pmatrix} ( 0 1 1 0 ) , π 1 : C 2 → C 2 \pi_1:\mathbb{C}^2\to\mathbb{C}^2 π 1 : C 2 → C 2 by ( 1 0 0 0 ) \begin{pmatrix}1&0\\0&0\end{pmatrix} ( 1 0 0 0 ) , and π 2 : C 2 → C 2 \pi_2:\mathbb{C}^2\to\mathbb{C}^2 π 2 : C 2 → C 2 by ( 0 0 0 1 ) \begin{pmatrix}0&0\\0&1\end{pmatrix} ( 0 0 0 1 ) in the computational basis.
I not p ≔ ( not p ) † π 1 ( not p ) = p † not † π 1 not p = p † π 2 p = E p \begin{aligned}
I_{\operatorname{not} p}&\coloneqq(\operatorname{not}p)^\dagger\pi_1(\operatorname{not}p)\\
&=p^\dagger\operatorname{not}^\dagger\pi_1\operatorname{not}p\\
&=p^\dagger\pi_2p\\
&=E_p
\end{aligned} I not p : = ( not p ) † π 1 ( not p ) = p † not † π 1 not p = p † π 2 p = E p
True test: we show that I t r u e p = id p I_{\mathrm{true}\,p} = \operatorname{id}_p I true p = id p and E t r u e p = 0 E_{\mathrm{true}\,p} = 0 E true p = 0 and the result then follows from the fact that true ∘ ( E p , I p ) T = ( 1 1 0 0 ) ( E p I p ) = ( E p + I p 0 ) = ( id X 0 ) \operatorname{true} \circ(E_p, I_p)^{\mathsf T} = \begin{pmatrix} 1 & 1 \\ 0 & 0 \end{pmatrix} \begin{pmatrix} E_p \\ I_p \end{pmatrix} = \begin{pmatrix} E_p + I_p \\ 0 \end{pmatrix} = \begin{pmatrix} \operatorname{id}_X \\ 0 \end{pmatrix} true ∘ ( E p , I p ) T = ( 1 0 1 0 ) ( E p I p ) = ( E p + I p 0 ) = ( id X 0 ) .
I t r u e p ≜ ( true p ) † π 1 ( true p ) = p † true † π 1 true p = p † ( 1 1 1 1 ) p = id X I_{\mathrm{true}\,p} \triangleq(\operatorname{true}p)^{\dagger}\pi_1(\operatorname{true}p)
= p^{\dagger}\operatorname{true}^{\dagger}\pi_1\operatorname{true}p
= p^{\dagger}\begin{pmatrix} 1 & 1 \\ 1 & 1 \end{pmatrix}p
= \operatorname{id}_X I true p ≜ ( true p ) † π 1 ( true p ) = p † true † π 1 true p = p † ( 1 1 1 1 ) p = id X
Conversely,
E t r u e p ≜ ( true p ) † π 2 ( true p ) = p † true † π 2 true p = 0 E_{\mathrm{true}\,p} \triangleq(\operatorname{true}p)^{\dagger}\pi_2(\operatorname{true}p)
= p^{\dagger}\operatorname{true}^{\dagger}\pi_2\operatorname{true}p
= 0 E true p ≜ ( true p ) † π 2 ( true p ) = p † true † π 2 true p = 0
Idempotence for sharp predicates follows immediately from the fact that I p , E p I_p,E_p I p , E p are then orthogonal projections, and E p = id − I p E_p = \operatorname{id} - I_p E p = id − I p . The result then follows from the fact that the codiagonal map sums the two components.
Commutativity is a trivial combinatorial consequence of the choice function definitions in terms of I p , E p I_p,E_p I p , E p .
Proofs for Section 5
The following lemma is a direct consequence of the enriched Yoneda lemma [20 §1.9] .
Lemma 39. Let ( C , ⊗ , I ) (\mathcal{C}, \otimes, I) ( C , ⊗ , I ) be a closed symmetric monoidal category with coproducts which is enriched over itself and such that Id = C ( I , − ) \operatorname{Id} = \mathcal{C}(I,-) Id = C ( I , − ) , and let T = Id + Id T = \operatorname{Id} + \operatorname{Id} T = Id + Id . The set of natural transformations Id → T \operatorname{Id} \to T Id → T is in bijective correspondence with C ( I , I + I ) \mathcal{C}(I,I+I) C ( I , I + I ) . The set of natural transformations T 2 → T T^2 \to T T 2 → T is in bijective correspondence with ( C ( I , I + I ) ) 4 (\mathcal{C}(I,I+I))^4 ( C ( I , I + I ) ) 4 .
Proof of Theorem 28. It follows from Lemma 39 that there are only two possible units for T T T given respectively by η = in 1 \eta= \operatorname{in}_1 η = in 1 and η = in 2 \eta= \operatorname{in}_2 η = in 2 . Let’s consider each of these options in turn. Case η = in 1 \eta= \operatorname{in}_1 η = in 1 : again from Lemma 39 there exists 16 different possible multiplication μ : T 2 → T \mu:T^2 \to T μ : T 2 → T that are all of the shape
[ in i 1 , in i 2 , in i 3 , in i 4 ] with i 1 , i 2 , i 3 , i 4 ∈ { 1 , 2 } [\operatorname{in}_{i_1},\operatorname{in}_{i_2},\operatorname{in}_{i_3},\operatorname{in}_{i_4}]
\qquad\text{with}\qquad
i_1,i_2,i_3,i_4 \in\{1,2\} [ in i 1 , in i 2 , in i 3 , in i 4 ] with i 1 , i 2 , i 3 , i 4 ∈ { 1 , 2 }
The unit axiom μ ∘ η T = id T \mu\circ\eta_T = \operatorname{id}_T μ ∘ η T = id T implies that i 1 = 1 i_1 = 1 i 1 = 1 and i 2 = 2 i_2 = 2 i 2 = 2 . The other unit axiom μ ∘ T η = id T \mu\circ T\eta= \operatorname{id}_T μ ∘ T η = id T implies that i 1 = 1 i_1 = 1 i 1 = 1 and i 3 = 2 i_3 = 2 i 3 = 2 . This leaves two options open. The associativity axiom μ ∘ μ T = μ ∘ T μ \mu\circ\mu_T = \mu\circ T\mu μ ∘ μ T = μ ∘ T μ looks like this
( ( X + X ) + ( X + X ) ) + ( ( X + X ) + ( X + X ) ) → [ in 1 , in 2 , in i 3 , in i 4 ] ( X + X ) + ( X + X ) [ in 1 , in 2 , in i 3 , in i 4 ] + [ in 1 , in 2 , in i 3 , in i 4 ] ↓ ↓ [ in 1 , in 2 , in i 3 , in i 4 ] ( X + X ) + ( X + X ) → [ in 1 , in 2 , in i 3 , in i 4 ] X + X \begin{CD}
((X+X)+(X+X))+((X+X)+(X+X))
@>{[\operatorname{in}_1,\operatorname{in}_2,\operatorname{in}_{i_3},\operatorname{in}_{i_4}]}>> (X+X)+(X+X) \\
@V{[\operatorname{in}_1,\operatorname{in}_2,\operatorname{in}_{i_3},\operatorname{in}_{i_4}]+[\operatorname{in}_1,\operatorname{in}_2,\operatorname{in}_{i_3},\operatorname{in}_{i_4}]}VV
@VV{[\operatorname{in}_1,\operatorname{in}_2,\operatorname{in}_{i_3},\operatorname{in}_{i_4}]}V \\
(X+X)+(X+X) @>>{[\operatorname{in}_1,\operatorname{in}_2,\operatorname{in}_{i_3},\operatorname{in}_{i_4}]}> X+X
\end{CD} (( X + X ) + ( X + X )) + (( X + X ) + ( X + X )) [ in 1 , in 2 , in i 3 , in i 4 ] + [ in 1 , in 2 , in i 3 , in i 4 ] ↓ ⏐ ( X + X ) + ( X + X ) [ in 1 , in 2 , in i 3 , in i 4 ] [ in 1 , in 2 , in i 3 , in i 4 ] ( X + X ) + ( X + X ) ↓ ⏐ [ in 1 , in 2 , in i 3 , in i 4 ] X + X
Let’s consider the two different options.
i 4 = 1 i_4 = 1 i 4 = 1 . Clockwise we get the map [ i n 1 , i n 2 , i n 2 , i n 1 , i n 2 , i n 1 , i n 1 , i n 2 ] [\mathrm{in}_1,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_1,\mathrm{in}_2,\mathrm{in}_1,\mathrm{in}_1,\mathrm{in}_2] [ in 1 , in 2 , in 2 , in 1 , in 2 , in 1 , in 1 , in 2 ] . Anti-clockwise we get the map [ i n 1 , i n 2 , i n 2 , i n 1 , i n 2 , i n 1 , i n 1 , i n 2 ] [\mathrm{in}_1,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_1,\mathrm{in}_2,\mathrm{in}_1,\mathrm{in}_1,\mathrm{in}_2] [ in 1 , in 2 , in 2 , in 1 , in 2 , in 1 , in 1 , in 2 ] . These are the same maps, and thus this option is possible.
i 4 = 2 i_4 = 2 i 4 = 2 . Clockwise we get the map [ i n 1 , i n 2 , i n 2 , i n 2 , i n 2 , i n 2 , i n 2 , i n 2 ] [\mathrm{in}_1,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2] [ in 1 , in 2 , in 2 , in 2 , in 2 , in 2 , in 2 , in 2 ] . Anti-clockwise we also get the map [ i n 1 , i n 2 , i n 2 , i n 2 , i n 2 , i n 2 , i n 2 , i n 2 ] [\mathrm{in}_1,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2] [ in 1 , in 2 , in 2 , in 2 , in 2 , in 2 , in 2 , in 2 ] , and so this option is possible too.
Case η = i n 2 \eta= \mathrm{in}_2 η = in 2 : the proof is dual to the case where η = i n 1 \eta= \mathrm{in}_1 η = in 1 .
Proof of Proposition 29. 1. To see that ⊤ ∨ C ( p ) = C ( p ) ∨ ⊤ = ⊤ \top\vee C(p) = C(p) \vee\top= \top ⊤ ∨ C ( p ) = C ( p ) ∨ ⊤ = ⊤ holds, consider first the following two commutative diagrams:
X → ⊤ = i n 1 X + X → C ( p ) + C ( p ) X + X + X + X C ( p ) ↓ i n 1 + i n 1 ↓ ↓ ∨ X + X → t r u e X + X = X + X X → C ( p ) X + X → i n 1 + i n 1 X + X + X + X t r u e ↓ ↓ ∧ X + X = X + X \begin{CD}
X @>{\top=\mathrm{in}_1}>> X+X @>{C(p)+C(p)}>> X+X+X+X \\
@V{C(p)}VV @V{\mathrm{in}_1+\mathrm{in}_1}VV @VV{\vee}V \\
X+X @>{\mathrm{true}}>> X+X @= X+X
\end{CD}
\qquad
\begin{CD}
X @>{C(p)}>> X+X @>{\mathrm{in}_1+\mathrm{in}_1}>> X+X+X+X \\
@. @V{\mathrm{true}}VV @VV{\wedge}V \\
@. X+X @= X+X
\end{CD} X C ( p ) ↓ ⏐ X + X ⊤ = in 1 true X + X in 1 + in 1 ↓ ⏐ X + X C ( p ) + C ( p ) X + X + X + X ↓ ⏐ ∨ X + X X C ( p ) X + X true ↓ ⏐ X + X in 1 + in 1 X + X + X + X ↓ ⏐ ∧ X + X
Now note that thanks to idempotency we have
X → C ( p ) X + X → t r u e X + X i n 1 + i n 1 ↓ ∇ ↓ X = X → ⊤ = i n 1 X \begin{CD}
X @>{C(p)}>> X+X @>{\mathrm{true}}>> X+X \\
@V{\mathrm{in}_1+\mathrm{in}_1}VV @V{\nabla}VV @. \\
X @= X @>{\top=\mathrm{in}_1}>> X
\end{CD} X in 1 + in 1 ↓ ⏐ X C ( p ) X + X ∇ ↓ ⏐ X true ⊤ = in 1 X + X X
The proof of ⊥ ∧ C ( p ) = C ( p ) ∧ ⊥ = ⊥ \bot\wedge C(p) = C(p) \wedge\bot= \bot ⊥ ∧ C ( p ) = C ( p ) ∧ ⊥ = ⊥ is dual to the previous case.
For the identity not ( C ( p ) ∧ C ( q ) ) = C ( not p ) ∨ C ( not q ) \operatorname{not}(C(p) \wedge C(q)) = C(\operatorname{not} p) \vee C(\operatorname{not} q) not ( C ( p ) ∧ C ( q )) = C ( not p ) ∨ C ( not q ) consider the following diagram
X → C ( p ) X + X → C ( q ) + C ( q ) X + X + X + X → ∧ X + X C ( not p ) ↓ not ↓ not ↓ ↓ not X + X → C ( q ) + C ( q ) X + X + X + X → not + not X + X + X + X → ∨ X + X \begin{CD}
X @>{C(p)}>> X+X @>{C(q)+C(q)}>> X+X+X+X @>{\wedge}>> X+X \\
@V{C(\operatorname{not}p)}VV @V{\operatorname{not}}VV @V{\operatorname{not}}VV @VV{\operatorname{not}}V \\
X+X @>{C(q)+C(q)}>> X+X+X+X @>{\operatorname{not}+\operatorname{not}}>> X+X+X+X @>{\vee}>> X+X
\end{CD} X C ( not p ) ↓ ⏐ X + X C ( p ) C ( q ) + C ( q ) X + X not ↓ ⏐ X + X + X + X C ( q ) + C ( q ) not + not X + X + X + X not ↓ ⏐ X + X + X + X ∧ ∨ X + X ↓ ⏐ not X + X
To see that the right-hand side square commutes we simply compute the maps in both directions. Clockwise the map is [ i n 2 , i n 1 , i n 1 , i n 1 ] [\mathrm{in}_2,\mathrm{in}_1,\mathrm{in}_1,\mathrm{in}_1] [ in 2 , in 1 , in 1 , in 1 ] , anticlockwise it is given by ∨ ∘ [ i n 4 , i n 3 , i n 2 , i n 1 ] \vee\circ[\mathrm{in}_4,\mathrm{in}_3,\mathrm{in}_2,\mathrm{in}_1] ∨ ∘ [ in 4 , in 3 , in 2 , in 1 ] which is also equal to [ i n 2 , i n 1 , i n 1 , i n 1 ] [\mathrm{in}_2,\mathrm{in}_1,\mathrm{in}_1,\mathrm{in}_1] [ in 2 , in 1 , in 1 , in 1 ] .
The proof of not ( C ( p ) ∨ C ( q ) ) = C ( not p ) ∧ C ( not q ) \operatorname{not}(C(p) \vee C(q)) = C(\operatorname{not}p) \wedge C(\operatorname{not}q) not ( C ( p ) ∨ C ( q )) = C ( not p ) ∧ C ( not q ) is dual to the one above.
X → C ( p ) X + X → C ( q ) + C ( q ) X + X + X + X → ∨ X + X C ( not p ) ↓ not ↓ not ↓ ↓ not X + X → C ( q ) + C ( q ) X + X + X + X → not + not X + X + X + X → ∧ X + X \begin{CD}
X @>{C(p)}>> X+X @>{C(q)+C(q)}>> X+X+X+X @>{\vee}>> X+X \\
@V{C(\operatorname{not}p)}VV @V{\operatorname{not}}VV @V{\operatorname{not}}VV @VV{\operatorname{not}}V \\
X+X @>{C(q)+C(q)}>> X+X+X+X @>{\operatorname{not}+\operatorname{not}}>> X+X+X+X @>{\wedge}>> X+X
\end{CD} X C ( not p ) ↓ ⏐ X + X C ( p ) C ( q ) + C ( q ) X + X not ↓ ⏐ X + X + X + X C ( q ) + C ( q ) not + not X + X + X + X not ↓ ⏐ X + X + X + X ∨ ∧ X + X ↓ ⏐ not X + X
Again, the commutativity of the right-hand square follows by computing both morphisms which are equal to [ i n 2 , i n 2 , i n 2 , i n 1 ] [\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_2,\mathrm{in}_1] [ in 2 , in 2 , in 2 , in 1 ] .
The commutativity C ( p ) ∨ C ( q ) = C ( q ) ∨ C ( p ) C(p) \vee C(q) = C(q) \vee C(p) C ( p ) ∨ C ( q ) = C ( q ) ∨ C ( p ) follows immediately from the fact that ∨ = ∨ ∘ [ i n 1 , i n 3 , i n 2 , i n 4 ] \vee= \vee\circ[\mathrm{in}_1,\mathrm{in}_3,\mathrm{in}_2,\mathrm{in}_4] ∨ = ∨ ∘ [ in 1 , in 3 , in 2 , in 4 ] .
Similarly, the commutativity C ( p ) ∧ C ( q ) = C ( q ) ∧ C ( p ) C(p) \wedge C(q) = C(q) \wedge C(p) C ( p ) ∧ C ( q ) = C ( q ) ∧ C ( p ) follows from the fact that ∧ = ∧ ∘ [ i n 1 , i n 3 , i n 2 , i n 4 ] \wedge= \wedge\circ[\mathrm{in}_1,\mathrm{in}_3,\mathrm{in}_2,\mathrm{in}_4] ∧ = ∧ ∘ [ in 1 , in 3 , in 2 , in 4 ] .
Proof of Proposition 31. The de Morgan relations follow from the fact that C X ( not p ) = not X ∘ ( p ) C_X(\operatorname{not} p) = \operatorname{not}_X \circ(p) C X ( not p ) = not X ∘ ( p ) holds in any conditionally branching category and diagram chasing around permutations of coproducts. For commutativity the proof follows immediately from noticing that
∨ = ∨ ∘ [ i n 1 , i n 3 , i n 2 , i n 4 ] : I + I + I + I → I + I \vee= \vee\circ[\mathrm{in}_1,\mathrm{in}_3,\mathrm{in}_2,\mathrm{in}_4] : I + I + I + I \to I + I ∨ = ∨ ∘ [ in 1 , in 3 , in 2 , in 4 ] : I + I + I + I → I + I
and similarly for ∧ \wedge ∧ .
Proof of Proposition 34. For notational convenience we use a conditionally branching structure defined by (13) in the special case where ⊗ \otimes ⊗ is the Cartesian product. The general proof can then be obtained by making all copying explicit and replacing all instances of Δ \Delta Δ below with copy, although this is laborious for pairings. Consider the following diagram which encodes the property for ∨ \vee ∨ (the proof for ∧ \wedge ∧ is dual).
X → ⟨ i d , p ∨ q ⟩ X × ( 1 + 1 ) → l d i s t r X + X ⟨ i d , p ⟩ ↓ i d × ∨ ↑ ↑ i d × t r u e , i d × i d X × ( 1 + 1 ) → l d i s t r X + X → Δ + Δ X × X + X × X l d i s t r ↓ ↓ i d × q + i d × q X + X → ⟨ i d , q ⟩ + ⟨ i d , q ⟩ X × ( 1 + 1 ) + X × ( 1 + 1 ) → l d i s t r + l d i s t r X + X + X + X \begin{CD}
X @>{\langle\mathrm{id},p\vee q\rangle}>> X\times(1+1) @>{\mathrm{ldistr}}>> X+X \\
@V{\langle\mathrm{id},p\rangle}VV @A{\mathrm{id}\times\vee}AA @AA{\mathrm{id}\times\mathrm{true},\mathrm{id}\times\mathrm{id}}A \\
X\times(1+1) @>{\mathrm{ldistr}}>> X+X @>{\Delta+\Delta}>> X\times X+X\times X \\
@V{\mathrm{ldistr}}VV @. @VV{\mathrm{id}\times q+\mathrm{id}\times q}V \\
X+X @>{\langle\mathrm{id},q\rangle+\langle\mathrm{id},q\rangle}>> X\times(1+1)+X\times(1+1) @>{\mathrm{ldistr}+\mathrm{ldistr}}>> X+X+X+X
\end{CD} X ⟨ id , p ⟩ ↓ ⏐ X × ( 1 + 1 ) ldistr ↓ ⏐ X + X ⟨ id , p ∨ q ⟩ ldistr ⟨ id , q ⟩ + ⟨ id , q ⟩ X × ( 1 + 1 ) id ×∨ ⏐ ↑ X + X X × ( 1 + 1 ) + X × ( 1 + 1 ) ldistr Δ + Δ ldistr + ldistr X + X ⏐ ↑ id × true , id × id X × X + X × X ↓ ⏐ id × q + id × q X + X + X + X
The top triangle with base ⟨ i d , p ∨ q ⟩ \langle\mathrm{id},p\vee q\rangle ⟨ id , p ∨ q ⟩ commute by definition of p ∨ q p\vee q p ∨ q . The left-most triangle commutes trivially and the square to the bottom-right of it commutes by naturality of ldistr as does the other square to its right involving two ldistr-labelled vertical arrows. The lowest triangle involving Δ + Δ \Delta+\Delta Δ + Δ commutes trivially and the half-moon diagram commutes by Lemma 38. The central triangle involving only ldistr also commutes by virtue of Lemma 38 by considering the inverses of the two diagonal edges (the inverse of the long edge is [ i d X × ( i d X × i n 1 ) , i d X × ( i d X × i n 2 ) ] [\mathrm{id}_X\times(\mathrm{id}_X\times\mathrm{in}_1),\mathrm{id}_X\times(\mathrm{id}_X\times\mathrm{in}_2)] [ id X × ( id X × in 1 ) , id X × ( id X × in 2 )] ). Finally we can check explicitly that the right-most square (with the bendy vertical arrow) commutes by again considering the inverse of ldistr. Starting from the first summand of the bottom-right-hand object we get
( i d X × t r u e ) ∘ l d i s t r − 1 = ( i d X × t r u e ) ∘ [ i d X × i n 1 , i d X × i n 2 ] = [ i d X ∘ i n 1 , i d X ∘ i n 1 ] = [ i d X ∘ i n 1 , i d X ∘ i n 2 ] ∘ t r u e X = l d i s t r − 1 ∘ t r u e X \begin{aligned}
(\mathrm{id}_X\times\mathrm{true})\circ\mathrm{ldistr}^{-1}
= (\mathrm{id}_X\times\mathrm{true})\circ[\mathrm{id}_X\times\mathrm{in}_1,\mathrm{id}_X\times\mathrm{in}_2] \\
&= [\mathrm{id}_X\circ\mathrm{in}_1,\mathrm{id}_X\circ\mathrm{in}_1] \\
&= [\mathrm{id}_X\circ\mathrm{in}_1,\mathrm{id}_X\circ\mathrm{in}_2]\circ\mathrm{true}_X \\
&= \mathrm{ldistr}^{-1}\circ\mathrm{true}_X
\end{aligned} ( id X × true ) ∘ ldistr − 1 = ( id X × true ) ∘ [ id X × in 1 , id X × in 2 ] = [ id X ∘ in 1 , id X ∘ in 1 ] = [ id X ∘ in 1 , id X ∘ in 2 ] ∘ true X = ldistr − 1 ∘ true X
The identity for the second summand is trivial and the commutativity of the final square follows. ◀
Proof of Theorem 35. We prove the equality of these morphisms by showing that they are equal when post-composed with the jointly monic arrows [ i d X , ∇ X ] [\mathrm{id}_X,\nabla_X] [ id X , ∇ X ] and [ n o t X , i d X ] [\mathrm{not}_X,\mathrm{id}_X] [ not X , id X ] . In the following diagram we write r r r for the test p ∧ n o t q n o t ( p ∧ q ) \frac{p\wedge\mathrm{not}\ q}{\mathrm{not}(p\wedge q)} not ( p ∧ q ) p ∧ not q . That it commutes is a direct consequence of the fact that C ( X , 1 + 1 ) C(X,1+1) C ( X , 1 + 1 ) is residuated.
X → C ( p ) X + X → C ( q ) + C ( q ) X + X + X + X C ( p ∧ q ) ↓ ↓ C ( n o t q ) + C ( n o t ( q ) ) ↓ n o t + n o t X + X → n o t X + X → X + X + X + X C ( r ) + C ( r ) ↓ ↓ C ( r ) + C ( r ) ↓ i d + ∇ X + X + X + X → ∇ + i d X + X + X → [ n o t , i d ] X + X \begin{CD}
X @>{C(p)}>> X+X @>{C(q)+C(q)}>> X+X+X+X \\
@V{C(p\wedge q)}VV @VV{C(\mathrm{not}\ q)+C(\mathrm{not}(q))}V @VV{\mathrm{not}+\mathrm{not}}V \\
X+X @>{\mathrm{not}}>> X+X @>>> X+X+X+X \\
@V{C(r)+C(r)}VV @VV{C(r)+C(r)}V @VV{\mathrm{id}+\nabla}V \\
X+X+X+X @>{\nabla+\mathrm{id}}>> X+X+X @>{[\mathrm{not},\mathrm{id}]}>> X+X
\end{CD} X C ( p ∧ q ) ↓ ⏐ X + X C ( r ) + C ( r ) ↓ ⏐ X + X + X + X C ( p ) not ∇ + id X + X ↓ ⏐ C ( not q ) + C ( not ( q )) X + X ↓ ⏐ C ( r ) + C ( r ) X + X + X C ( q ) + C ( q ) [ not , id ] X + X + X + X ↓ ⏐ not + not X + X + X + X ↓ ⏐ id + ∇ X + X
The second equality follows from the following commutative diagram which follows from idempotence and the definition of ∧ \wedge ∧ .
X → C ( p ) X + X → C ( q ) + C ( q ) X + X + X + X C ( p ∧ q ) ↓ ↓ i d + ∇ ↓ i d + ∇ X + X = X + X ← ∧ X + X + X + X C ( r ) + C ( r ) ↓ [ i d , ∇ ] ↓ X + X + X + X → ∇ + i d X + X + X \begin{CD}
X @>{C(p)}>> X+X @>{C(q)+C(q)}>> X+X+X+X \\
@V{C(p\wedge q)}VV @VV{\mathrm{id}+\nabla}V @VV{\mathrm{id}+\nabla}V \\
X+X @= X+X @<{\wedge}<< X+X+X+X \\
@V{C(r)+C(r)}VV @V{[\mathrm{id},\nabla]}VV \\
X+X+X+X @>{\nabla+\mathrm{id}}>> X+X+X
\end{CD} X C ( p ∧ q ) ↓ ⏐ X + X C ( r ) + C ( r ) ↓ ⏐ X + X + X + X C ( p ) ∇ + id X + X ↓ ⏐ id + ∇ X + X [ id , ∇ ] ↓ ⏐ X + X + X C ( q ) + C ( q ) ∧ X + X + X + X ↓ ⏐ id + ∇ X + X + X + X