2012 ACM Subject Classification Theory of computation → \rightarrow → Lambda calculus; Theory of computation → \rightarrow → Probabilistic computation
Keywords and phrases probabilistic lambda-calculus, type systems, almost-sure termination
Acknowledgements We thank Georgina Majury for her efforts on a precursor to this work, and the anonymous referees for their comments, in particular those leading to the observations in § 10 .
Introduction
We are interested in applying the toolset of the λ \lambda λ -calculus, in particular confluent reduction and type systems, to probabilistic computation. In [12 ] we restored confluence to a probabilistic λ \lambda λ -calculus, the probabilistic event λ \lambda λ -calculus (PEL), by decomposing probabilistic choice into a sampling construct and a conditional . Then in [1 ] and [26 ] , from different inspirations we converged on essentially the same probabilistic type system for the PEL to give lower bounds on the probability of termination. In this paper we further extend the calculus, and develop a type system for almost-sure termination (AST): termination with probability one. In doing so, our objective differs from that of many existing works in this area, which aim to capture as many AST programs as possible [11 , 10 ] , or even to study the feasibility of capturing all such programs [28 ] . Instead, we seek to understand the extent to which almost-sure termination can be obtained and explained in a natural manner, possibly using well-established methods, and guaranteed by a minimal extension to simple types. More powerful methods such as dependent types and intersection types may later build on this along standard lines.
We start from the following observation. Iteration , generally represented by while-loops, repeats a given function f f f until a condition is fulfilled. In the typed case, illustrated below, the function f f f is required to return a sum B + A B + A B + A , where the choice between returning a value A A A or B B B represents the condition. Then iter f \operatorname{iter} f iter f evaluates f f f , exits on B B B , and repeats on A A A [6 ] .
f : A → B + A iter f : A → B \frac{f:A\to B+A}{\operatorname{iter} f:A\to B} iter f : A → B f : A → B + A
With the above rule, as with typed fixed-point combinators, typing no longer guarantees termination. However, we observe that if we replace B + A B+A B + A by a probabilistic sum B ⊕ p A B\mathbin{\oplus_p}A B ⊕ p A with a fixed probability p ∈ ( 0 , 1 ] p\in(0,1] p ∈ ( 0 , 1 ] , i.e. the probability of choosing B B B is non-zero and does not depend on the input, then iter f \operatorname{iter} f iter f is almost-surely terminating (provided of course that f f f is itself terminating). This opens a way to approach almost-sure termination via type systems. A crucial question arises: how can we handle a type constructor such as B ⊕ p A B\mathbin{\oplus_p}A B ⊕ p A within a λ \lambda λ -calculus with probabilistic choice in a compositional and elegant manner?
These considerations illustrate how probabilistic choice is connected to other imperative features such as sequentiality and iteration. Derived from the PEL, the second author has developed a new approach to unifying the λ \lambda λ -calculus with imperative computation and effects, the Functional Machine Calculus (FMC) [24 ] . Its most recent instance [25 ] features branching sequential computation and iteration, providing an ideal vehicle for our present study. In the FMC each branch of the computation is labelled with a choice label i , j , k , … i,j,k,\ldots i , j , k , … , which takes the rôle of a constant, an exception, a case label, or an exit status. For example, the boolean constants ⊥ \bot ⊥ and ⊤ \top ⊤ are choice labels. Iteration of a term M M M is written M i M^i M i , which evaluates M M M and repeats if M M M chooses i i i , terminating for any other choice. The calculus encodes a fair probabilistic choice, which we write as M ⊕ N M\mathbin{\oplus}N M ⊕ N .
Example 1 (Bernoulli Factory). The term ( h ⊕ ( t ⊕ i ) ) i (h\mathbin{\oplus}(t\mathbin{\oplus}i))^i ( h ⊕ ( t ⊕ i ) ) i chooses heads , the choice h h h , with probability 1 2 \frac{1}{2} 2 1 , tails t t t with probability 1 4 \frac{1}{4} 4 1 , and iterates with probability 1 4 \frac{1}{4} 4 1 , to give an overall probability of 2 3 \frac{2}{3} 3 2 for h h h and 1 3 \frac{1}{3} 3 1 for t t t . We illustrate it as follows; it will remain a running example.
( h ⊕ ( t ⊕ i ) ) i = (h\mathbin{\oplus}(t\mathbin{\oplus}i))^i= ( h ⊕ ( t ⊕ i ) ) i =
Figure 5.
The type system we introduce in this paper, simplified for this introduction to omit inputs and return values, records the probability of terminating with each given choice. A term M M M is typed as follows, indicating that it may choose i k i_k i k with probability p k p_k p k from the choices i 1 i_1 i 1 through i n i_n i n . For simplicity, we restrict ourselves to rational probabilities, p , q ∈ [ 0 , 1 ] ∩ Q p,q\in[0,1]\cap\mathbb{Q} p , q ∈ [ 0 , 1 ] ∩ Q .
M : p 1 i 1 ⊕ ⋯ ⊕ p n i n M:p_1i_1\mathbin{\oplus}\cdots\mathbin{\oplus}p_ni_n M : p 1 i 1 ⊕ ⋯ ⊕ p n i n
The type is a probability (sub-)distribution over the choices { i 1 , … , i n } \{i_1,\ldots,i_n\} { i 1 , … , i n } , written as a formal sum. If the sum probability over p 1 p_1 p 1 through p n p_n p n is one, the term is AST. For greater generality, and since our formalism readily incorporates it, we allow probabilities to sum to less than one, with the remainder representing an upper bound to the probability of divergence. We note here that, as a λ \lambda λ -calculus, the full calculus will have two means of non-termination: iteration with probability one, and higher-order non-terminating terms such as Ω = ( λ x . x x ) ( λ x . x x ) \Omega=(\lambda x.xx)(\lambda x.xx) Ω = ( λ x . xx ) ( λ x . xx ) . The type system will address both, and a term is almost-surely terminating if the sum probability of its type is exactly one.
Example 2. The body of our example term, without the loop, has the following type.
h ⊕ ( t ⊕ i ) : 1 2 h ⊕ 1 4 t ⊕ 1 4 i h\mathbin{\oplus}(t\mathbin{\oplus}i):\frac{1}{2}h\mathbin{\oplus}\frac{1}{4}t\mathbin{\oplus}\frac{1}{4}i h ⊕ ( t ⊕ i ) : 2 1 h ⊕ 4 1 t ⊕ 4 1 i
Iteration M i M^i M i removes the choice i i i from the possible return choices. In the probabilistic setting, the remaining probabilities must then be renormalized to form a distribution. That is, if i i i has probability q q q (with q < 1 q < 1 q < 1 ), the remaining choices (including divergence) have a total probability of 1 − q 1-q 1 − q , and must be multiplied by 1 1 − q \frac{1}{1-q} 1 − q 1 to return the total to one. Typing for iteration is then as follows.
M : p 1 i 1 ⊕ ⋯ ⊕ p n i n ⊕ q j M j : p 1 1 − q i 1 ⊕ ⋯ ⊕ p n 1 − q i n \begin{aligned}
M &: p_1i_1 \oplus\cdots\oplus p_ni_n \oplus qj\\
M^j &: \frac{p_1}{1-q}i_1 \oplus\cdots\oplus\frac{p_n}{1-q}i_n
\end{aligned} M M j : p 1 i 1 ⊕ ⋯ ⊕ p n i n ⊕ q j : 1 − q p 1 i 1 ⊕ ⋯ ⊕ 1 − q p n i n
▶ Example 3. The type for our example term is given by taking the type 1 2 h ⊕ 1 4 t ⊕ 1 4 i \frac{1}{2}h \oplus\frac{1}{4}t \oplus\frac{1}{4}i 2 1 h ⊕ 4 1 t ⊕ 4 1 i of the body of the loop, removing the element 1 4 i \frac{1}{4}i 4 1 i , and then multiplying the remaining sub-distribution 1 2 h ⊕ 1 4 t \frac{1}{2}h \oplus\frac{1}{4}t 2 1 h ⊕ 4 1 t by 4 3 \frac{4}{3} 3 4 to renormalize it, which yields the following.
( h ⊕ ( t ⊕ i ) ) i : 2 3 h ⊕ 1 3 t (h \oplus(t \oplus i))^i : \frac{2}{3}h \oplus\frac{1}{3}t ( h ⊕ ( t ⊕ i ) ) i : 3 2 h ⊕ 3 1 t
Types for iteration then correctly give the probabilities for each choice. Consider M j M^j M j where j j j has probability q q q in M M M . For any other choice i i i with probability p p p in M M M the chance of M j M^j M j choosing i i i is given by the following geometric series, generated by choosing i i i immediately, after one iteration, after two iterations, and so forth. The limit of this series is the probability given by the type system.
p + p q + p q 2 + p q 3 + ⋯ = p 1 − q p + pq + pq^2 + pq^3 + \cdots= \frac{p}{1-q} p + pq + p q 2 + p q 3 + ⋯ = 1 − q p
Typed Term Calculus for Finite Markov Chains
Further introducing the calculus, we first consider the fragment of ground terms , as follows:
Ground terms: M , N : : = i ∣ M ; i → N ∣ M i ∣ a . a \textit{Ground terms:}\qquad M, N ::= i \mid M\,;\,i\to N \mid M^i \mid\boxed{a}.a Ground terms: M , N ::= i ∣ M ; i → N ∣ M i ∣ a . a
The first three are the control constructs, introduced in [25 ] , which implement branching and iterating computation. The first (a choice i i i ) and the third (a loop M i M^i M i ), we have seen. The second is a case M ; i → N M\,;\,i\to N M ; i → N which first evaluates M M M , and if M M M terminates with i i i then continues with N N N , otherwise discarding it. The control constructs reduce by the following rules:
i ; i → M → M j ; i → M → j ( i ≠ j ) M i → M ; i → M i i\,;\,i\to M \;\to\; M
\qquad
j\,;\,i\to M \;\to\; j\quad(i\ne j)
\qquad
M^i \;\to\; M\,;\,i\to M^i i ; i → M → M j ; i → M → j ( i = j ) M i → M ; i → M i
These constructions generalise sequential computation, which uses a single choice ⋆ \star ⋆ , with imperative skip as ⋆ \star ⋆ and sequencing as M ; N = M ; ⋆ → N M\,;\,N = M\,;\,\star\to N M ; N = M ; ⋆ → N . The choice and case constructs are essentially throw and try/catch of exception handling, with exceptions e e e as choices:
throw e = e try M catch e N = M ; e → N \operatorname{throw}\ e = e
\qquad
\operatorname{try}\ M\ \operatorname{catch}\ e\ N = M\,;\,e\to N throw e = e try M catch e N = M ; e → N
Since cases are fall-through, they may be iterated to give a standard case switch. A conditional then encodes as below, where cases associate left, M ; i → N ; j → P = ( M ; i → N ) ; j → P M\,;\,i\to N\,;\,j\to P = (M\,;\,i\to N)\,;\,j\to P M ; i → N ; j → P = ( M ; i → N ) ; j → P . We do need to keep constants ( ⊤ , ⊥ ) (\top,\bot) ( ⊤ , ⊥ ) and exceptions ( e ) (e) ( e ) apart: for the conditional below, if M M M were to use ⊥ \bot ⊥ as an exception, it would be caught by N N N . A while-loop, below that, is as follows: if B B B returns ⊥ \bot ⊥ , then M M M is skipped, the loop exited, and ⊥ \bot ⊥ caught to return ⋆ \star ⋆ (success); if B B B returns ⊤ \top ⊤ , then M M M is evaluated, iterating upon ⋆ \star ⋆ .
if B then M else N = B ; ⊤ → M ; ⊥ → N \operatorname{if}\ B\ \operatorname{then}\ M\ \operatorname{else}\ N = B\,;\,\top\to M\,;\,\bot\to N if B then M else N = B ; ⊤ → M ; ⊥ → N
while B do M = ( B ; ⊤ → M ) ∗ ; ⊥ → ⋆ \operatorname{while}\ B\ \operatorname{do}\ M = (B\,;\,\top\to M)^*\,;\,\bot\to\star while B do M = ( B ; ⊤ → M ) ∗ ; ⊥ → ⋆
The fourth construct a . M \boxed{a}.M a . M is the generator a . M \boxed{a}.M a . M of the probabilistic event λ \lambda λ -calculus [12 ] restricted to a variable a a a . The generator reduces as below: it flips a coin and binds the result, ⊤ \top ⊤ or ⊥ \bot ⊥ , to the variable a a a in M M M .
a . M → { ⊤ / a } M ⊕ { ⊥ / a } M \boxed{a}.M \mathbin{\to} \{\top/a\}M \mathbin{\oplus} \{\bot/a\}M a . M → { ⊤/ a } M ⊕ { ⊥/ a } M
The restricted construct a . a \boxed{a}.a a . a thus reduces to ⊤ \top ⊤ or ⊥ \bot ⊥ with equal probability. Using it, a probabilistic sum encodes as follows.
M ⊕ N = a . a ; ⊤ → M ; ⊥ → N M \mathbin{\oplus} N = \boxed{a}.a;\top\mathbin{\to}M;\bot\mathbin{\to}N M ⊕ N = a . a ; ⊤ → M ; ⊥ → N
Example 4. Our running example term unfolds as a ground term as follows.
( h ⊕ ( t ⊕ i ) ) i = ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i (h\mathbin{\oplus}(t\mathbin{\oplus}i))^{i} = (\boxed{a}.a;\top\mathbin{\to}h;\bot\mathbin{\to}(\boxed{b}.b;\top\mathbin{\to}t;\bot\mathbin{\to}i))^{i} ( h ⊕ ( t ⊕ i ) ) i = ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i
Remark 5. The generator a . M \boxed{a}.M a . M represents a fair coin toss, with equal probability for ⊤ \top ⊤ and ⊥ \bot ⊥ . We write a p . M \boxed{a}_{p}.M a p . M for an unfair coin with probability p p p for ⊤ \top ⊤ and 1 − p 1-p 1 − p for ⊥ \bot ⊥ . This may either be considered a primitive construct generalising a . M \boxed{a}.M a . M , or constructed from fair coin tosses with iteration in the way our running example term generates 2 3 \frac{2}{3} 3 2 and 1 3 \frac{1}{3} 3 1 .
We now turn to types. Deterministic types for the control constructs record the possible terminating choices for a term, as is standard for exception handling. Types are finite sets of choices, written as formal sums I = i 1 + ⋯ + i n I=i_1+\cdots+i_n I = i 1 + ⋯ + i n ; semantically, these are coproducts. We have the following typing rules:
i : i + I M : I + i N : J M ; i → N : I ∪ J M : I + i M i : I \begin{aligned}
&i:i+I && M:I+i \qquad N:J && M; i\mathbin{\to}N:I\cup J \qquad M:I+i && M^i:I
\end{aligned} i : i + I M : I + i N : J M ; i → N : I ∪ J M : I + i M i : I
As in the previous, in the probabilistic setting types become (sub-)distributions p I = p 1 i 1 ⊕ ⋯ ⊕ p n i n p_I=p_1i_1\oplus\cdots\oplus p_ni_n p I = p 1 i 1 ⊕ ⋯ ⊕ p n i n over a set I I I of choices. Ground terms are then typed by the rules in Figure 1, where we write p I + q I p_I+q_I p I + q I for the pointwise addition of two distributions over I I I and p ⋅ q I p\cdot q_I p ⋅ q I for the multiplication of each probability in q I q_I q I by p p p . A type p I p_I p I implicitly assigns probability zero to any choice not in I I I , corresponding to the weakened I I I in the first rule above. Observe that the probabilistic type system is a direct generalization of the deterministic one.
In Section 6 we will return to ground terms and prove a Kleene theorem for them: ground terms are equivalent to finite Markov chains, given as probabilistic automata, where states correspond to choices. Then types compute the return distribution of an encoded Markov chain, while type inference is decidable, and terms typed with total distributions are positive AST.
The Probabilistic FMC
The FMC combines the control constructs with the λ \lambda λ -calculus via the Krivine abstract machine (KAM) [30 ] , which evaluates terms in the context of an argument stack: application M N M\ N M N pushes N N N and continues as M M M ; abstraction λ x . M \lambda x.M λ x . M pops (say) N N N and continues as { N / x } M \{N/x\}M { N / x } M . This gives a canonical interpretation to the (call-by-name) λ \lambda λ -calculus in terms of stateful and sequential computation, where the stack is the state and computation proceeds sequentially via pop- and push-actions . Together with the control constructs, the FMC then features branching and iterating computation that inputs and outputs a stack.
Emphasizing this perspective, the FMC uses [ N ] . M [N].M [ N ] . M for application M N M\ N M N and ⟨ x ⟩ . M \langle x\rangle.M ⟨ x ⟩ . M for abstraction λ x . M \lambda x.M λ x . M . With the control constructs and generator as above, the probabilistic FMC is as follows.
M , N : : = x ∣ ⟨ x ⟩ . M ∣ [ N ] . M ∣ i ∣ M ; i → N ∣ M i ∣ a . M M,N ::= x \mid\langle x\rangle.M \mid[N].M \mid i \mid M;i\mathbin{\to}N \mid M^i \mid\boxed{a}.M M , N ::= x ∣ ⟨ x ⟩ . M ∣ [ N ] . M ∣ i ∣ M ; i → N ∣ M i ∣ a . M
Figure 1 (PDF p. 5). Typing rules for ground terms, with illustrating diagrams. The double arrows represent multiple branches. In the second rule, the types for M M M and N N N divide into overlapping parts p J p_J p J and r J r_J r J , and non-overlapping parts p I p_I p I and r K r_K r K , where I I I , J J J , and K K K are pairwise disjoint sets of choices.
Example 6. Consider the following example term.
⟨ x ⟩ . x ; h → ⟨ y ⟩ . ⋆ ; t → ⟨ y ⟩ . [ y ] . [ y ] . ⋆ \langle x\rangle.x\mathbin{;}^{h\to}\langle y\rangle.\star\mathbin{;}^{t\to}\langle y\rangle.[y].[y].\star ⟨ x ⟩ . x ; h → ⟨ y ⟩ . ⋆ ; t → ⟨ y ⟩ . [ y ] . [ y ] . ⋆
It takes a (fair or unfair) coin from the stack as x x x , such as our 1 3 \frac{1}{3} 3 1 probability running example term, and tosses it. On heads, it deletes the top element on the stack; on tails, it duplicates it. Both branches return with the default choice ⋆ \star ⋆ (“skip”).
Remark 7. The notion of sequencing in the FMC is fundamentally the same as that of Moggi’s computational metalanguage [34 ] and Levy’s call–by–push–value [32 ] :
M ≫ N = M ; N M \mathbin{\gg} N = M\mathbin{;}N M ≫ N = M ; N
The difference is that the latter return a single value, while the FMC returns the whole stack: return M = [ M ] . ⋆ \operatorname{return} M=[M].\star return M = [ M ] . ⋆ . This notion of sequencing further allows the encoding of call–by–value behaviour, both in a deterministic and probabilistic setting; see [24 ] , respectively [26 ] .
For the full calculus, the distribution types of ground terms are extended with types for the input stack and for the return stack of each branch. Types (or computation types ) τ \tau τ and stack types τ ‾ \overline{\tau} τ are given below; the latter are vectors giving a type for each term, and the former an implication from an input stack type σ ‾ \overline{\sigma} σ to a formal sum of triples τ ‾ ⋅ p i i \overline{\tau}\mathbin{\cdot}p_i^{i} τ ⋅ p i i of an output stack type τ ‾ \overline{\tau} τ , a probability p p p , and a choice i i i , where the restriction to p i p_i p i forms a (sub-)distribution.
Types: σ , τ : : = σ ‾ ⇒ τ ‾ 1 ⋅ p 1 i 1 ⊕ ⋯ ⊕ τ ‾ n ⋅ p n i n \sigma,\tau::=\overline{\sigma}\Rightarrow\overline{\tau}_1\mathbin{\cdot}p_1^{i_1}\mathbin{\oplus}\cdots\mathbin{\oplus}\overline{\tau}_n\mathbin{\cdot}p_n^{i_n} σ , τ ::= σ ⇒ τ 1 ⋅ p 1 i 1 ⊕ ⋯ ⊕ τ n ⋅ p n i n
Stack types: τ ‾ : : = τ 1 … τ n \overline{\tau}::=\tau_1\ldots\tau_n τ ::= τ 1 … τ n
Since stacks are last-in-first-out, identity terms are of the form ⟨ x ⟩ . ⟨ y ⟩ . [ y ] . [ x ] . ⋆ \langle x\rangle.\langle y\rangle.[y].[x].\star ⟨ x ⟩ . ⟨ y ⟩ . [ y ] . [ x ] . ⋆ , reversing the order of variables (and returning the default choice ⋆ \star ⋆ ). Type vectors follow the order of terms, implicitly reversing on the left of an implication, so that identity terms have type τ ˉ ⇒ τ ˉ ⋅ 1 ⋆ \bar{\tau} \Rightarrow\bar{\tau}\cdot1\star τ ˉ ⇒ τ ˉ ⋅ 1 ⋆ ; for the given example, ⟨ x ⟩ . ⟨ y ⟩ . [ y ] . [ x ] . ⋆ : σ ⇒ τ ⋅ 1 ⋆ \langle x\rangle.\langle y\rangle.[y].[x].\star:\sigma\Rightarrow\tau\cdot1\star ⟨ x ⟩ . ⟨ y ⟩ . [ y ] . [ x ] . ⋆ : σ ⇒ τ ⋅ 1 ⋆ . Types for ground terms as distributions abbreviate computation types with empty type vectors, written ε \varepsilon ε .
p 1 i 1 ⊕ ⋯ ⊕ p n i n = ε ⇒ ε ⋅ p 1 i 1 ⊕ ⋯ ⊕ ε ⋅ p n i n p_1 i_1 \oplus\cdots\oplus p_n i_n = \varepsilon\Rightarrow\varepsilon\cdot p_1 i_1 \oplus\cdots\oplus\varepsilon\cdot p_n i_n p 1 i 1 ⊕ ⋯ ⊕ p n i n = ε ⇒ ε ⋅ p 1 i 1 ⊕ ⋯ ⊕ ε ⋅ p n i n
Example 8. In the sequential setting, with a single branch ⋆ \star ⋆ , composition of two terms M : ρ ˉ ⇒ σ ˉ ⋅ p ⋆ M:\bar{\rho}\Rightarrow\bar{\sigma}\cdot p\star M : ρ ˉ ⇒ σ ˉ ⋅ p ⋆ and N : σ ˉ ⇒ τ ˉ ⋅ q ⋆ N:\bar{\sigma}\Rightarrow\bar{\tau}\cdot q\star N : σ ˉ ⇒ τ ˉ ⋅ q ⋆ multiplies their probabilities, M ; N : ρ ˉ ⇒ τ ˉ ⋅ ( p q ) ⋆ M;N:\bar{\rho}\Rightarrow\bar{\tau}\cdot(pq)\star M ; N : ρ ˉ ⇒ τ ˉ ⋅ ( pq ) ⋆ .
Example 9. The term of Example 6 cannot be typed because it features two branches with the same choice ⋆ \star ⋆ but different output stacks (one empty, the other holding two copies of the input y y y ). Adapting it to use distinct choices i i i and j j j instead, and choosing the type for the first input to match our running example, we get the type below (for any type τ \tau τ for y y y ).
⟨ x ⟩ . x ; h → ⟨ y ⟩ . i ; t → ⟨ y ⟩ . [ y ] . [ y ] . j : ( ε ⇒ ε ⋅ 2 3 h ⊕ ε ⋅ 1 3 t ) τ ⇒ ε ⋅ 2 3 i ⊕ τ τ ⋅ 1 3 j \langle x\rangle.x;h\to\langle y\rangle.i;t\to\langle y\rangle.[y].[y].j:(\varepsilon\Rightarrow\varepsilon\cdot\frac{2}{3}h\oplus\varepsilon\cdot\frac{1}{3}t)\tau\Rightarrow\varepsilon\cdot\frac{2}{3}i\oplus\tau\tau\cdot\frac{1}{3}j ⟨ x ⟩ . x ; h → ⟨ y ⟩ . i ; t → ⟨ y ⟩ . [ y ] . [ y ] . j : ( ε ⇒ ε ⋅ 3 2 h ⊕ ε ⋅ 3 1 t ) τ ⇒ ε ⋅ 3 2 i ⊕ τ τ ⋅ 3 1 j
The term expects two inputs: the unfair coin and some argument τ \tau τ for the abstractions ⟨ y ⟩ \langle y\rangle ⟨ y ⟩ of each branch (note that since both branches pop from the same input stack, both variables y y y get the same type). It then produces two possible outputs: with probability 2 3 \frac{2}{3} 3 2 the branch i i i with the empty stack, and with probability 1 3 \frac{1}{3} 3 1 the branch j j j with two copies of y y y on the stack.
As the example demonstrates, the type system is quite restrictive: probabilities are fixed, even on inputs. However, the potential of lifting these restrictions is clear, for example by introducing polymorphism (variables) for probabilities, or generalising to dependent types. The purpose of the present paper is not just to establish the basic system of probabilistic simple types for AST, but to offer a clear way forward in probabilistic type systems.
After exploring related work in the next section, we will define the calculus (§ 5 ) and the type system (§ 6 ), and give our main result, Theorem 28: the probability given by the type of a term is a lower bound on the probability of termination, which implies almost-sure termination if that probability is one (§ 7 ). The final sections explore the expressiveness of the calculus, demonstrating that ground terms are equivalent to finite Markov chains and thus positive AST (§ 8 ), and that the full calculus is null AST : while the probability of termination is one, expected runtime is infinite (§ 9 ).
Related Work
Our type system is a conservative extension of our previous systems in [1 ] and [26 ] (see Remark 24). While those systems already feature higher-order functions, they do not account for either iteration or recursion.
The literature on semantics and termination properties of probabilistic computation is extensive and includes a wide range of techniques. We mention semantic domains [9 , 29 , 40 ] , bisimulations and trace semantics [22 , 35 , 36 ] , probabilistic automata [18 , 19 ] , probabilistic coherence spaces [8 , 14 , 17 ] , program logics [20 , 33 ] , and separation logic [4 , 27 ] .
Type systems for probabilistic calculi are numerous and diverse as well. We distinguish two kinds. Firstly, there are deterministic or monadic types, which do not feature explicit probabilities at the type level (see Remark 10 ). These tend to play a supporting role, with probabilistic properties such as AST then guaranteed by construction. Examples are [39 ] , [37 ] which features coproduct-typed (but not probabilistic) iteration, and [7 ] which extends Gödel’s T with probabilistic generators and iterators that are inherently AST.
Secondly, there are several formal methodologies enforcing AST or PAST in probabilistic λ \lambda λ -calculi with recursion. These are generally highly expressive, but complex, using involved techniques such as refinement types [3 , 31 ] , size types [11 ] , non well founded type systems [13 , 15 ] , intersection types [5 , 10 ] , guarded refinements [23 ] , or CPS transformations [2 ] . Such complexity is largely unavoidable: unlike in the deterministic case, probabilistic termination is undecidable even for higher-order programs operating over finite datatypes [28 ] , as exemplified by probabilistic variants of the λ Y \lambda Y λY -calculus and higher-order recursion schemes. Expressiveness thus comes at the expense of simplicity; here, we prioritize simplicity, obtaining a system that constitutes a minimal extension of simple types.
Our approach sets itself apart in two ways. Firstly, from the FMC we inherit the combination of higher-order functions with iteration , rather than recursion (we comment on typing recursion in our system in Appendix A). Secondly, as a direct probabilistic generalisation of coproducts, our probabilistic types are a notion of simple types . We are thus taking a “bottom-up” approach, consciously trading expressiveness for simplicity and extensibility: our simple types are highly restricted in the algorithms they may express, but they arise naturally from typed iteration, and we expect they will extend to more powerful type systems such as polymorphic types, intersection types, and dependent types along standard lines.
It would be interesting to consider continuation-passing translations from our calculus into one with recursion. Generally, these require higher types; for instance, the simply-typed FMC, when translated this way into λ \lambda λ -calculus, requires System F types. With such a translation for the probabilistic FMC, it would then become possible to compare the expressive power of our system against the approaches mentioned above. This is however out of scope for the present publication.
The Probabilistic FMC
For the formal development, we first recall the terms of the probabilistic FMC from the introduction, and then give its operational semantics. The FMC further features a confluent reduction relation [25 ] , which we omit here.
Definition 12. The terms of the PFMC are given by the following grammar.
M , N : : = x ∣ ⟨ x ⟩ . M ∣ [ N ] . M ∣ i ∣ M ; i → N ∣ M i ∣ [ α ] . M M, N \mathrel{::=} x \mid\langle x\rangle.M \mid[N].M \mid i \mid M;i\mathbin{\to}N \mid M^{i} \mid[\alpha].M M , N ::= x ∣ ⟨ x ⟩ . M ∣ [ N ] . M ∣ i ∣ M ; i → N ∣ M i ∣ [ α ] . M
Figure 2. The Abstract Machine
The constructs are: a variable x x x ; a pop ⟨ x ⟩ . M \langle x\rangle.M ⟨ x ⟩ . M that binds x x x in M M M ; a push [ N ] . M [N].M [ N ] . M ; a choice i i i ; a case M ; i → N M;i\to N M ; i → N ; a loop M i M^{i} M i ; and a generator a . M a.M a . M which binds the variable a a a in M M M .
The small-step semantics is given by the Krivine machine [30 ] , which evaluates the λ \lambda λ -calculus via a single argument stack, with the following extensions. The generator a . M a.M a . M will pop from a stack of boolean values, called a trace, which we will model as being probabilistically generated. Branching computation is implemented via a continuation stack of conditional continuations i → N i\to N i → N , where M ; i → N M;i\to N M ; i → N pushes the continuation i → N i\to N i → N , and a choice term i i i discards non-matching continuations j → M j\to M j → M where i ≠ j i\ne j i = j until it pops a matching i → N i\to N i → N . The machine terminates successfully when it reaches a choice i i i and the continuation stack is empty, at which point it returns the argument stack.
Definition 13. The functional abstract machine is given by the following data. Traces r , s , t r,s,t r , s , t , argument stacks R , S , T R,S,T R , S , T , and continuation stacks K , L K,L K , L are as follows.
r , s , t : : = ε ∣ ⊥ t ∣ ⊤ t R , S , T : : = ε ∣ S M K , L : : = ε ∣ ( i → M ) K r,s,t ::= \varepsilon\mid\bot t \mid\top t \qquad R,S,T ::= \varepsilon\mid S M \qquad K,L ::= \varepsilon\mid(i\to M)K r , s , t ::= ε ∣ ⊥ t ∣ ⊤ t R , S , T ::= ε ∣ S M K , L ::= ε ∣ ( i → M ) K
The states of the machine are four-tuples ( t , S , M , K ) (t,S,M,K) ( t , S , M , K ) . Its steps or transitions are given in Figure 2. A run is a sequence of steps, written as below. A run is successful if it terminates in a final state ( ε , T , i , ε ) (\varepsilon,T,i,\varepsilon) ( ε , T , i , ε ) with a choice term i i i and empty trace and continuation stack.
( s , S , M , K ) ( t , T , N , L ) \frac{(s,S,M,K)}{(t,T,N,L)} ( t , T , N , L ) ( s , S , M , K )
Appendix B demonstrates a successful run of the machine for our running example term.
In addition to the machine we give a big-step operational semantics, in the form of an inductively defined evaluation relation ( ⇓ ) (\Downarrow) ( ⇓ ) that describes the successful runs of the machine directly. Where the machine implements branching computation via the continuation stack, the big-step semantics gives a more abstract view as conditional sequential composition.
Definition 14. The evaluation relation has statements t , S , M ⇓ T , i t,S,M\Downarrow T,i t , S , M ⇓ T , i and is defined induct-
ively by the following rules.
ε , S , i ⇓ S , i a x r , R , M ⇓ S , i s , S , N ⇓ T , j r s , R , M ; i → N ⇓ T , j s e l r , R , M ⇓ S , j ( i ≠ j ) r , R , M ; i → N ⇓ S , j r e j s , S N , M ⇓ T , i s , S , [ N ] . M ⇓ T , i p u s h r , R , M ⇓ S , i s , S , M i ⇓ T , j r s , R , M i ⇓ T , j l o o p r , R , M ⇓ S , j ( i ≠ j ) r , R , M i ⇓ S , j e x i t t , S , { N / x } M ⇓ T , i t , S N , ⟨ x ⟩ . M ⇓ T , i p o p t , S , { ⊥ / a } M ⇓ T , i ⊥ t , S , a . M ⇓ T , i s m p l t , S , { ⊤ / a } M ⇓ T , i ⊤ t , S , a . M ⇓ T , i s m p l \begin{aligned}
&\frac{}{ \varepsilon,S,i \Downarrow S,i}\ \mathrm{ax}
&&\frac{r,R,M \Downarrow S,i \quad s,S,N \Downarrow T,j}{rs,R,M\mathbin{;}i\to N \Downarrow T,j}\ \mathrm{sel}
&&\frac{r,R,M \Downarrow S,j\quad(i\ne j)}{r,R,M\mathbin{;}i\to N \Downarrow S,j}\ \mathrm{rej}\\
&\frac{s,S\,N,M \Downarrow T,i}{s,S,[N]\mathbin{.}M \Downarrow T,i}\ \mathrm{push}
&&\frac{r,R,M \Downarrow S,i \quad s,S,M^{i}\Downarrow T,j}{rs,R,M^{i}\Downarrow T,j}\ \mathrm{loop}
&&\frac{r,R,M \Downarrow S,j\quad(i\ne j)}{r,R,M^{i}\Downarrow S,j}\ \mathrm{exit}\\
&\frac{t,S,\{N/x\}M \Downarrow T,i}{t,S\,N,\langle x\rangle\mathbin{.}M \Downarrow T,i}\ \mathrm{pop}
&&\frac{t,S,\{\bot/a\}M \Downarrow T,i}{\bot\,t,S,a\mathbin{.}M \Downarrow T,i}\ \mathrm{smpl}
&&\frac{t,S,\{\top/a\}M \Downarrow T,i}{\top\,t,S,a\mathbin{.}M \Downarrow T,i}\ \mathrm{smpl}
\end{aligned} ε , S , i ⇓ S , i ax s , S , [ N ] . M ⇓ T , i s , S N , M ⇓ T , i push t , S N , ⟨ x ⟩ . M ⇓ T , i t , S , { N / x } M ⇓ T , i pop r s , R , M ; i → N ⇓ T , j r , R , M ⇓ S , i s , S , N ⇓ T , j sel r s , R , M i ⇓ T , j r , R , M ⇓ S , i s , S , M i ⇓ T , j loop ⊥ t , S , a . M ⇓ T , i t , S , { ⊥/ a } M ⇓ T , i smpl r , R , M ; i → N ⇓ S , j r , R , M ⇓ S , j ( i = j ) rej r , R , M i ⇓ S , j r , R , M ⇓ S , j ( i = j ) exit ⊤ t , S , a . M ⇓ T , i t , S , { ⊤/ a } M ⇓ T , i smpl
The machine and the big-step evaluation relation can be put in correspondence as follows.
Proposition 15 [25 Proposition 5.4] . Evaluation characterizes successful machine termination:
t , S , M ⇓ T , i ⟺ ( t , S , M , ε ) ( ε , T , i , ε ) t,S,M \Downarrow T,i \Longleftrightarrow\frac{(t,S,M,\varepsilon)}{(\varepsilon,T,i,\varepsilon)} t , S , M ⇓ T , i ⟺ ( ε , T , i , ε ) ( t , S , M , ε )
The calculus as defined above is deterministic: it externalises the probabilistic component of evaluation to the input trace t t t . To give a probabilistic semantics, we will define an evaluation relation S , M ⇓ T S,M \Downarrow T S , M ⇓ T which takes a stack S S S and a term M M M to a certain kind of distribution T T T , a return family . This is a set of traces with for each t t t an associated pair ( T , i ) (T,i) ( T , i ) of a return stack and choice such that t , S , M ⇓ T , i t,S,M \Downarrow T,i t , S , M ⇓ T , i (effectively, we are only shifting where the trace t t t is considered as a parameter, on the machine versus in the return distribution). Since the probability of a trace t t t is 1 2 n \frac{1}{2^n} 2 n 1 where n n n is the length of t t t , a return family readily gives rise to a probability (sub-)distribution.
A return family collects evaluation results for distinct probabilistic choices, not further evaluation along the same trace: if it has t t t , it should not have any prefix of t t t , nor any trace extending t t t . A return family will therefore be defined over a frontier F F F : a (possibly infinite) set of traces such that no element in F F F is a prefix of another. The probability pr ( F ) \operatorname{pr}(F) pr ( F ) of a frontier F F F is the sum probability of its traces; observe that by definition, pr ( F ) ≤ 1 \operatorname{pr}(F)\le1 pr ( F ) ≤ 1 .
pr ( t ) = ( 1 2 ) ∣ t ∣ where ∣ t ∣ is the length of t pr ( F ) = ∑ t ∈ F pr ( t ) \begin{aligned}
\operatorname{pr}(t)&=\left(\frac{1}{2}\right)^{|t|} &&\text{where } |t| \text{ is the length of }t\\
\operatorname{pr}(F)&=\sum_{t\in F}\operatorname{pr}(t)
\end{aligned} pr ( t ) pr ( F ) = ( 2 1 ) ∣ t ∣ = t ∈ F ∑ pr ( t ) where ∣ t ∣ is the length of t
Example 16. The set of traces { ( ⊥ n ) ⊤ ∣ n ∈ N } = { ⊤ , ⊥ ⊤ , ⊥ ⊥ ⊤ , … } \{(\bot^n)\top\mid n\in\mathbb{N}\}=\{\top,\bot\top,\bot\bot\top,\ldots\} {( ⊥ n ) ⊤ ∣ n ∈ N } = { ⊤ , ⊥⊤ , ⊥⊥⊤ , … } is a frontier with probability 1.
A return family S S S then collects a return stack and choice, as a pair ( S t , i t ) t (S_t,i_t)_t ( S t , i t ) t , for every trace t t t in a frontier F F F , as below. The frontier F F F over which S S S is defined is written ⌊ S ⌋ = F \lfloor S\rfloor=F ⌊ S ⌋ = F , and the probability of a return family is that of its frontier, pr ( S ) = pr ( ⌊ S ⌋ ) \operatorname{pr}(S)=\operatorname{pr}(\lfloor S\rfloor) pr ( S ) = pr (⌊ S ⌋) .
S , T : : = { ( S t , i t ) t } t ∈ F S,T ::= \{(S_t,i_t)_t\}_{t\in F} S , T ::= {( S t , i t ) t } t ∈ F
Definition 17. A probabilistic evaluation S , M ⇓ T S,M\Downarrow T S , M ⇓ T of a term M M M and stack S S S to a return family T T T is given by the evaluation of M M M and S S S with each t ∈ F t\in F t ∈ F , as follows.
S , M ⇓ { ( T t , i t ) } t ∈ F ⟺ ∀ t ∈ F . ( t , S , M ⇓ T t , i t ) S,M\Downarrow\{(T_t,i_t)\}_{t\in F}\Longleftrightarrow\forall t\in F.\ (t,S,M\Downarrow T_t,i_t) S , M ⇓ {( T t , i t ) } t ∈ F ⟺ ∀ t ∈ F . ( t , S , M ⇓ T t , i t )
Example 18. For our running example term we have ε , ( h ⊕ ( t ⊕ t ) ) ⇓ T \varepsilon,(h\oplus(t\oplus t))\Downarrow T ε , ( h ⊕ ( t ⊕ t )) ⇓ T for the following return family T T T over the frontier of Example 16.
T = { ( ε , h ) t ∣ t = ( ⊥ 2 n ) ⊤ , n ∈ N } ∪ { ( ε , t ) t ∣ t = ( ⊥ 2 n + 1 ) ⊤ , n ∈ N } T=\{(\varepsilon,h)_t\mid t=(\bot^{2n})\top,\ n\in\mathbb{N}\}\cup\{(\varepsilon,t)_t\mid t=(\bot^{2n+1})\top,\ n\in\mathbb{N}\} T = {( ε , h ) t ∣ t = ( ⊥ 2 n ) ⊤ , n ∈ N } ∪ {( ε , t ) t ∣ t = ( ⊥ 2 n + 1 ) ⊤ , n ∈ N }
Observe that evaluation is closed under inclusion: if R , M ⇓ T R, M \Downarrow T R , M ⇓ T and S ⊆ T S \subseteq T S ⊆ T then R , M ⇓ S R, M \Downarrow S R , M ⇓ S . An evaluation S , M ⇓ T S, M \Downarrow T S , M ⇓ T gives a lower bound of pr ( T ) \operatorname{pr}(T) pr ( T ) for the probability of termination of a term M M M in the context of a stack S S S .
Definition 19. The probability of termination of a term M M M in the context of a stack S S S is the largest probability pr ( T ) \operatorname{pr}(T) pr ( T ) for any T T T such that S , M ⇓ T S, M \Downarrow T S , M ⇓ T .
To work with return families we use the following notation. The sum of two return families S + T S + T S + T is defined if they have disjoint frontiers, ⌊ S ⌋ ∩ ⌊ T ⌋ = ∅ \lfloor S \rfloor\cap\lfloor T \rfloor= \varnothing ⌊ S ⌋ ∩ ⌊ T ⌋ = ∅ , and is the union of their underlying sets S ∪ T S \cup T S ∪ T . Likewise, inclusion between families S ⊆ T S \subseteq T S ⊆ T is inclusion as sets. We define the following notions below. On the left, s ⋅ F s \cdot F s ⋅ F and s ⋅ S s \cdot S s ⋅ S add s s s as a prefix to every trace t t t in F F F , respectively in S S S , and S T S T S T prefixes every stack in T T T with S S S . On the right, S ∣ i S \mathbin{|}_i S ∣ i restricts a family to the choice i i i while S \ i S \mathbin{\backslash}_i S \ i excludes the choice i i i , and stk ( S ) \operatorname{stk}(S) stk ( S ) collects the stacks in S S S as a set.
s ⋅ F = { s t ∣ t ∈ F } S ∣ i = { ( S , j ) t ∈ S ∣ j = i } s ⋅ S = { ( S , i ) s t ∣ ( S , i ) t ∈ S } S \ i = { ( S , j ) t ∈ S ∣ j ≠ i } S T = { ( S T , i ) t ∣ ( T , i ) t ∈ T } stk ( S ) = { S ∣ ( S , i ) t ∈ S } \begin{aligned}
s \cdot F &= \{st \mid t \in F\} & S \mathbin{|}_i &= \{(S,j)t \in S \mid j=i\} \\
s \cdot S &= \{(S,i)st \mid(S,i)t \in S\} & S \mathbin{\backslash}_i &= \{(S,j)t \in S \mid j \ne i\} \\
S T &= \{(S T,i)t \mid(T,i)t \in T\} & \operatorname{stk}(S) &= \{S \mid(S,i)t \in S\}
\end{aligned} s ⋅ F s ⋅ S S T = { s t ∣ t ∈ F } = {( S , i ) s t ∣ ( S , i ) t ∈ S } = {( S T , i ) t ∣ ( T , i ) t ∈ T } S ∣ i S \ i stk ( S ) = {( S , j ) t ∈ S ∣ j = i } = {( S , j ) t ∈ S ∣ j = i } = { S ∣ ( S , i ) t ∈ S }
We will freely use the following equations.
⌊ s ⋅ S ⌋ = s ⋅ ⌊ S ⌋ pr ( s ⋅ S ) = pr ( s ) × pr ( S ) pr ( S + T ) = pr ( S ) + pr ( T ) \lfloor s \cdot S \rfloor= s \cdot\lfloor S \rfloor\qquad\operatorname{pr}(s \cdot S) = \operatorname{pr}(s) \times\operatorname{pr}(S) \qquad\operatorname{pr}(S + T) = \operatorname{pr}(S) + \operatorname{pr}(T) ⌊ s ⋅ S ⌋ = s ⋅ ⌊ S ⌋ pr ( s ⋅ S ) = pr ( s ) × pr ( S ) pr ( S + T ) = pr ( S ) + pr ( T )
Types
Types for the FMC describe the input/output behaviour of the machine. In the deterministic case, a type τ \tau τ is of the form below left, where the type vector σ ‾ = σ 1 … σ k \overline{\sigma} = \sigma_1 \ldots\sigma_k σ = σ 1 … σ k types the input stack on the machine, and the type vectors τ ‾ m \overline{\tau}_m τ m type the return stack for each choice i m i_m i m . The type indicates that given an input stack S : σ ‾ S : \overline{\sigma} S : σ the machine will return some choice i m i_m i m and stack T : τ ‾ m T : \overline{\tau}_m T : τ m . For the probabilistic case we replace the formal sum of the return type with a probability distribution, adding a probability p m p_m p m for each summand as below right.
σ ‾ ⇒ τ ‾ 1 ⋅ i 1 + … + τ ‾ n ⋅ i n \overline{\sigma} \Rightarrow\overline{\tau}_1 \cdot i_1 + \ldots+ \overline{\tau}_n \cdot i_n σ ⇒ τ 1 ⋅ i 1 + … + τ n ⋅ i n
σ ‾ ⇒ τ ‾ 1 ⋅ p 1 i 1 ⊕ … ⊕ τ ‾ n ⋅ p n i n \overline{\sigma} \Rightarrow\overline{\tau}_1 \cdot p_1 i_1 \oplus\ldots\oplus\overline{\tau}_n \cdot p_n i_n σ ⇒ τ 1 ⋅ p 1 i 1 ⊕ … ⊕ τ n ⋅ p n i n
We will formalize the return type as a distribution type , a family in a finite set I I I of choice labels, with a type vector τ ‾ i \overline{\tau}_i τ i and a probability p i p_i p i for each i ∈ I i \in I i ∈ I such that the sum probability over all p i p_i p i is at most one. It is thus a combination of a deterministic sum type (the family of type vectors τ ‾ i \overline{\tau}_i τ i ) and a probability (sub-)distribution over I I I (the family of probabilities p i p_i p i ).
Definition 20. Types, stack types, and distribution types are given as follows.
types σ , τ : : = τ ‾ ⇒ δ stack types τ ‾ : : = τ 1 … τ n distribution types γ , δ : : = { ( τ ‾ i , p i ) } i ∈ I where ∑ i ∈ I p i ≤ 1 \begin{aligned}
\text{types} &\qquad\sigma, \tau::= \overline{\tau} \Rightarrow\delta\\
\text{stack types} &\qquad\overline{\tau} ::= \tau_1 \ldots\tau_n \\
\text{distribution types} &\qquad\gamma, \delta::= \{(\overline{\tau}_i,p_i)\}_{i \in I}\quad\text{where}\quad\sum_{i \in I} p_i \le1
\end{aligned} types stack types distribution types σ , τ ::= τ ⇒ δ τ ::= τ 1 … τ n γ , δ ::= {( τ i , p i ) } i ∈ I where i ∈ I ∑ p i ≤ 1
Recall from the introduction that stack types on the left of an implication ⇒ \Rightarrow ⇒ are implicitly reversed. Distribution types may implicitly expand with zero-probability summands when required by the typing rules (we will highlight the relevant cases in the discussion of the typing rules).
of the default choice ⋆ \star ⋆ . The type arrow ρ → τ \rho\to\tau ρ → τ becomes the operation of adding one further input type ρ \rho ρ to the inputs of τ \tau τ ; i.e. letting τ = σ ‾ ⇒ δ \tau= \overline{\sigma} \Rightarrow\delta τ = σ ⇒ δ then ρ → ( σ ‾ ⇒ δ ) = ρ σ ‾ ⇒ δ \rho\to(\overline{\sigma} \Rightarrow\delta) = \rho\overline{\sigma} \Rightarrow\delta ρ → ( σ ⇒ δ ) = ρ σ ⇒ δ . Together, we may view the embedding also as below.
τ 1 → … → τ n → o = τ 1 … τ n ⇒ ε ⋅ 1 ⋆ \tau_1 \to\ldots\to\tau_n \to o = \tau_1 \ldots\tau_n \Rightarrow\varepsilon\cdot1_{\star} τ 1 → … → τ n → o = τ 1 … τ n ⇒ ε ⋅ 1 ⋆
We introduce the following notation to work with distribution types. The basis ⌊ δ ⌋ \lfloor\delta\rfloor ⌊ δ ⌋ of a distribution type δ \delta δ is the set of choices ⌊ δ ⌋ = I \lfloor\delta\rfloor= I ⌊ δ ⌋ = I over which it is defined. To recover the informal notation of the introduction, we define the following: the singleton distribution type τ ‾ ⋅ p i = { ( τ ‾ , p ) i } \overline{\tau}\cdot p_i = \{(\overline{\tau},p)_i\} τ ⋅ p i = {( τ , p ) i } , the empty distribution type 0 0 0 with ⌊ 0 ⌋ = ∅ \lfloor0\rfloor= \varnothing ⌊ 0 ⌋ = ∅ , and the (disjoint) sum γ ⊕ δ = γ ∪ δ \gamma\oplus\delta= \gamma\cup\delta γ ⊕ δ = γ ∪ δ of two distribution types γ \gamma γ and δ \delta δ with no choice in common, ⌊ γ ⌋ ∩ ⌊ δ ⌋ = ∅ \lfloor\gamma\rfloor\cap\lfloor\delta\rfloor= \varnothing ⌊ γ ⌋ ∩ ⌊ δ ⌋ = ∅ . The probability pr ( δ ) \operatorname{pr}(\delta) pr ( δ ) of a distribution type is the sum over its probabilities p i p_i p i . Below left, the notation σ ‾ δ \overline{\sigma}\delta σ δ prefixes the type vector σ ‾ \overline{\sigma} σ to each τ ‾ \overline{\tau} τ in δ \delta δ , and q ⋅ δ q\cdot\delta q ⋅ δ multiplies each probability p i p_i p i in δ \delta δ by the probability q q q . Below right, δ ∣ I \delta\mathbin{|}I δ ∣ I restricts δ \delta δ to the choices in I I I , and δ ∖ I \delta\setminus I δ ∖ I removes them.
q ⋅ δ = { ( τ ‾ , q p ) i ∣ ( τ ‾ , p ) i ∈ δ } δ ∣ I = { ( τ ‾ ⋅ p ) i ∈ δ ∣ i ∈ I } σ ‾ δ = { ( σ ‾ τ ‾ , p ) i ∣ ( τ ‾ , p ) i ∈ δ } δ ∖ I = { ( τ ‾ ⋅ p ) i ∈ δ ∣ i ∉ I } \begin{aligned}
q\cdot\delta&= \{(\overline{\tau},qp)_i \mid(\overline{\tau},p)_i \in\delta\} & \delta\mathbin{|}I &= \{(\overline{\tau}\cdot p)_i \in\delta\mid i \in I\} \\
\overline{\sigma}\delta&= \{(\overline{\sigma}\overline{\tau},p)_i \mid(\overline{\tau},p)_i \in\delta\} & \delta\setminus I &= \{(\overline{\tau}\cdot p)_i \in\delta\mid i \notin I\}
\end{aligned} q ⋅ δ σ δ = {( τ , q p ) i ∣ ( τ , p ) i ∈ δ } = {( σ τ , p ) i ∣ ( τ , p ) i ∈ δ } δ ∣ I δ ∖ I = {( τ ⋅ p ) i ∈ δ ∣ i ∈ I } = {( τ ⋅ p ) i ∈ δ ∣ i ∈ / I }
Finally, the merger γ ⊔ δ \gamma\sqcup\delta γ ⊔ δ of two distribution types is defined if for every i ∈ ⌊ γ ⌋ ∩ ⌊ δ ⌋ i \in\lfloor\gamma\rfloor\cap\lfloor\delta\rfloor i ∈ ⌊ γ ⌋ ∩ ⌊ δ ⌋ they have the same type vector τ ‾ i \overline{\tau}_i τ i , and is as follows.
γ ⊔ δ = { ( τ ‾ , p + q ) i ∣ i ∈ ⌊ γ ⌋ ∪ ⌊ δ ⌋ , ( τ ‾ , p ) i ∈ γ , ( τ ‾ , q ) i ∈ δ } ⊕ γ ∖ ⌊ δ ⌋ ⊕ δ ∖ ⌊ γ ⌋ \gamma\sqcup\delta= \{(\overline{\tau},p+q)_i \mid i \in\lfloor\gamma\rfloor\cup\lfloor\delta\rfloor,\;(\overline{\tau},p)_i \in\gamma,\;(\overline{\tau},q)_i \in\delta\} \oplus\gamma\setminus\lfloor\delta\rfloor\oplus\delta\setminus\lfloor\gamma\rfloor γ ⊔ δ = {( τ , p + q ) i ∣ i ∈ ⌊ γ ⌋ ∪ ⌊ δ ⌋ , ( τ , p ) i ∈ γ , ( τ , q ) i ∈ δ } ⊕ γ ∖ ⌊ δ ⌋ ⊕ δ ∖ ⌊ γ ⌋
Definition 22. The typed PFMC (PFMC⇒ ⊕ \Rightarrow\oplus ⇒ ⊕ ) is given by the typing rules in Figure 3 , where a context Γ = x 1 : τ 1 , … , x n : τ n \Gamma= x_1 : \tau_1, \ldots, x_n : \tau_n Γ = x 1 : τ 1 , … , x n : τ n is a finite function from variables to types written as a sequence, and typing judgment Γ ⊢ M : τ \Gamma\vdash M : \tau Γ ⊢ M : τ assigns a term M M M the type τ \tau τ in the context Γ \Gamma Γ .
Figure 3. The typed probabilistic FMC
We will first discuss the typing rules in detail, skipping the variable rule as it is standard.
The zero rule allows to type any term M M M with a type ε ⇒ 0 \varepsilon\Rightarrow0 ε ⇒ 0 , returning the empty sub-distribution, which has sum probability zero. This is necessary to type terms such as ⋆ ⊕ Ω \star\oplus\Omega ⋆ ⊕ Ω , which returns immediately or diverges with equal probability, where we type Ω \Omega Ω with the zero rule.
The pop and push rules add, respectively remove, the first stack input. With the embedding of the type arrow → \to → of the simply-typed λ \lambda λ -calculus by ρ → ( σ ˉ ⇒ δ ) = ρ σ ˉ ⇒ δ \rho\to(\bar{\sigma} \Rightarrow\delta) = \rho\bar{\sigma} \Rightarrow\delta ρ → ( σ ˉ ⇒ δ ) = ρ σ ˉ ⇒ δ , these are the standard rules for abstraction and application.
The sequence rule reflects that M ; i → N M\mathbin{;}_{i\to}N M ; i → N first evaluates M M M , with input ρ ˉ \bar{\rho} ρ ˉ and output either σ ˉ \bar{\sigma} σ ˉ on branch i i i with probability p p p , or a different branch in γ \gamma γ . In the former case, then N N N is evaluated, with input σ ˉ \bar{\sigma} σ ˉ and output δ \delta δ . The overall term inputs ρ ˉ \bar{\rho} ρ ˉ and outputs γ ⊔ p ⋅ δ \gamma\sqcup p\cdot\delta γ ⊔ p ⋅ δ , where the merge ⊔ \sqcup ⊔ requires that whenever γ \gamma γ and δ \delta δ have a common branch j j j , the associated stack types are the same. For the special case where p = 0 p=0 p = 0 , i.e. M M M chooses i i i with probability zero, p ⋅ δ p\cdot\delta p ⋅ δ is the empty sub-distribution, and the rule becomes as follows.
Γ ⊢ M : ρ ˉ ⇒ γ ( i ∉ ⌈ γ ⌉ ) Γ ⊢ M ; i → N : ρ ˉ ⇒ γ \frac{\Gamma\vdash M : \bar{\rho} \Rightarrow\gamma\quad(i \notin\lceil\gamma\rceil)}
{\Gamma\vdash M\mathbin{;}_{i\to}N : \bar{\rho} \Rightarrow\gamma} Γ ⊢ M ; i → N : ρ ˉ ⇒ γ Γ ⊢ M : ρ ˉ ⇒ γ ( i ∈ / ⌈ γ ⌉)
The expand rule implements a key principle of stack calculi, stack expansion : if M M M evaluates successfully with a stack σ ˉ \bar{\sigma} σ ˉ , then if there are further inputs ρ ˉ \bar{\rho} ρ ˉ on the stack, these will be returned unchanged. Recall that input type vectors are reversed, so that in the return type σ ˉ ρ ˉ ⇒ ρ ˉ δ \bar{\sigma}\bar{\rho} \Rightarrow\bar{\rho}\delta σ ˉ ρ ˉ ⇒ ρ ˉ δ the stack ρ ˉ \bar{\rho} ρ ˉ is below σ ˉ \bar{\sigma} σ ˉ and below each stack in δ \delta δ .
The iterate rule requires that the input types σ ˉ \bar{\sigma} σ ˉ of M M M match the output types on branch i i i exactly, and that the probability p p p of choosing i i i is less than one. As with sequence there is a special case where p = 0 p=0 p = 0 , where the rule becomes as follows.
Γ ⊢ M : σ ˉ ⇒ δ ( i ∉ ⌈ δ ⌉ ) Γ ⊢ M i : σ ˉ ⇒ δ \frac{\Gamma\vdash M : \bar{\sigma} \Rightarrow\delta\quad(i \notin\lceil\delta\rceil)}
{\Gamma\vdash M^{i} : \bar{\sigma} \Rightarrow\delta} Γ ⊢ M i : σ ˉ ⇒ δ Γ ⊢ M : σ ˉ ⇒ δ ( i ∈ / ⌈ δ ⌉)
The sample rule reflects that a . M a.M a . M behaves like an abstraction which may receive one of two values, ⊤ : ε ⇒ ε ⋅ 1 ⊤ \top: \varepsilon\Rightarrow\varepsilon\cdot1_{\top} ⊤ : ε ⇒ ε ⋅ 1 ⊤ or ⊥ : ε ⇒ ε ⋅ 1 ⊥ \bot: \varepsilon\Rightarrow\varepsilon\cdot1_{\bot} ⊥ : ε ⇒ ε ⋅ 1 ⊥ , which it binds to the variable a a a . The term M M M is typed separately for each possibility, with the same input stack ρ ˉ \bar{\rho} ρ ˉ . The return type ( 1 2 ⋅ γ ) ⊔ ( 1 2 ⋅ δ ) (\frac{1}{2}\cdot\gamma)\sqcup(\frac{1}{2}\cdot\delta) ( 2 1 ⋅ γ ) ⊔ ( 2 1 ⋅ δ ) again requires that γ \gamma γ and δ \delta δ have the same stack type for any choice they share.
Example 23. The probabilistic sum M ⊕ N = a . M ; ⊤ → M ; ⊥ → N M\oplus N = a.M; \top\to M; \bot\to N M ⊕ N = a . M ; ⊤ → M ; ⊥ → N is typed as follows.
a : ε ⇒ ε ⋅ 1 ⊤ ⊢ a : ε ⇒ ε ⋅ 1 ⊤ a : ε ⇒ ε ⋅ 1 ⊥ ⊢ a : ε ⇒ ε ⋅ 1 ⊥ \frac{a:\varepsilon\Rightarrow\varepsilon\cdot1_{\top}\ \vdash\ a:\varepsilon\Rightarrow\varepsilon\cdot1_{\top}
\qquad
a:\varepsilon\Rightarrow\varepsilon\cdot1_{\bot}\ \vdash\ a:\varepsilon\Rightarrow\varepsilon\cdot1_{\bot}}
{} a : ε ⇒ ε ⋅ 1 ⊤ ⊢ a : ε ⇒ ε ⋅ 1 ⊤ a : ε ⇒ ε ⋅ 1 ⊥ ⊢ a : ε ⇒ ε ⋅ 1 ⊥
⊢ a . M : ε ⇒ ε ⋅ 1 2 ⊤ ⊕ ε ⋅ 1 2 ⊥ \vdash\ a.M:\varepsilon\Rightarrow\varepsilon\cdot\tfrac{1}{2}\top\oplus\varepsilon\cdot\tfrac{1}{2}\bot ⊢ a . M : ε ⇒ ε ⋅ 2 1 ⊤ ⊕ ε ⋅ 2 1 ⊥
⊢ a . M : τ ˉ ⇒ τ ˉ ⋅ 1 2 ⊤ ⊕ τ ˉ ⋅ 1 2 ⊥ \frac{\vdash\ a.M:\bar{\tau}\Rightarrow\bar{\tau}\cdot\tfrac{1}{2}\top\oplus\bar{\tau}\cdot\tfrac{1}{2}\bot}
{} ⊢ a . M : τ ˉ ⇒ τ ˉ ⋅ 2 1 ⊤ ⊕ τ ˉ ⋅ 2 1 ⊥
⊢ a . M ; ⊤ → M : τ ˉ ⇒ 1 2 ⋅ γ ⊕ τ ˉ ⋅ 1 2 ⊥ ⊢ M : τ ˉ ⇒ γ \frac{\vdash\ a.M;\top\to M:\bar{\tau}\Rightarrow\tfrac{1}{2}\cdot\gamma\oplus\bar{\tau}\cdot\tfrac{1}{2}\bot
\qquad
\vdash M:\bar{\tau}\Rightarrow\gamma}
{} ⊢ a . M ; ⊤ → M : τ ˉ ⇒ 2 1 ⋅ γ ⊕ τ ˉ ⋅ 2 1 ⊥ ⊢ M : τ ˉ ⇒ γ
⊢ a . M ; ⊤ → M ; ⊥ → N : τ ˉ ⇒ 1 2 ⋅ γ ⊔ 1 2 ⋅ δ ⊢ N : τ ˉ ⇒ δ \frac{\vdash\ a.M;\top\to M;\bot\to N:\bar{\tau}\Rightarrow\tfrac{1}{2}\cdot\gamma\sqcup\tfrac{1}{2}\cdot\delta
\qquad
\vdash N:\bar{\tau}\Rightarrow\delta}
{} ⊢ a . M ; ⊤ → M ; ⊥ → N : τ ˉ ⇒ 2 1 ⋅ γ ⊔ 2 1 ⋅ δ ⊢ N : τ ˉ ⇒ δ
Using this as an admissible typing rule, our running example is typed as follows.
⊢ h : ε ⇒ ε ⋅ 1 h \frac{\vdash h:\varepsilon\Rightarrow\varepsilon\cdot1_h}
{} ⊢ h : ε ⇒ ε ⋅ 1 h
⊢ t : ε ⇒ ε ⋅ 1 t ⊢ i : ε ⇒ ε ⋅ 1 i \frac{\vdash t:\varepsilon\Rightarrow\varepsilon\cdot1_t
\qquad
\vdash i:\varepsilon\Rightarrow\varepsilon\cdot1_i}
{} ⊢ t : ε ⇒ ε ⋅ 1 t ⊢ i : ε ⇒ ε ⋅ 1 i
⊢ t ⊕ i : ε ⇒ ε ⋅ 1 2 t ⊕ ε ⋅ 1 2 i \frac{\vdash t\oplus i:\varepsilon\Rightarrow\varepsilon\cdot\tfrac{1}{2}t\oplus\varepsilon\cdot\tfrac{1}{2}i}
{} ⊢ t ⊕ i : ε ⇒ ε ⋅ 2 1 t ⊕ ε ⋅ 2 1 i
⊢ h ⊕ ( t ⊕ i ) : ε ⇒ ε ⋅ 1 2 h ⊕ ε ⋅ 1 4 t ⊕ ε ⋅ 1 4 i \frac{\vdash h\oplus(t\oplus i):\varepsilon\Rightarrow\varepsilon\cdot\tfrac{1}{2}h\oplus\varepsilon\cdot\tfrac{1}{4}t\oplus\varepsilon\cdot\tfrac{1}{4}i}
{} ⊢ h ⊕ ( t ⊕ i ) : ε ⇒ ε ⋅ 2 1 h ⊕ ε ⋅ 4 1 t ⊕ ε ⋅ 4 1 i
⊢ ( h ⊕ ( t ⊕ i ) ) i : ε ⇒ ε ⋅ 2 3 h ⊕ ε ⋅ 1 3 t \frac{\vdash(h\oplus(t\oplus i))^{i}:\varepsilon\Rightarrow\varepsilon\cdot\tfrac{2}{3}h\oplus\varepsilon\cdot\tfrac{1}{3}t}
{} ⊢ ( h ⊕ ( t ⊕ i ) ) i : ε ⇒ ε ⋅ 3 2 h ⊕ ε ⋅ 3 1 t
Remark 24. The type system is a conservative extension of those of our previous work on probabilistic termination in [1 ] and [26 ] . Using the notation of the latter, these feature probabilistic simple types as simple types with the rationals between 0 and 1 as the set of base types, as below left. They embed as below right, where ⋆ \star ⋆ is again the single available choice label.
σ , τ : : = p ∣ σ → τ τ 1 → … → τ n → p = τ 1 … τ n ⇒ ε ⋅ p ⋆ \sigma,\ \tau::= p \mid\sigma\to\tau
\qquad
\tau_1 \to\ldots\to\tau_n \to p
=
\tau_1 \ldots\tau_n \Rightarrow\varepsilon\cdot p\star σ , τ ::= p ∣ σ → τ τ 1 → … → τ n → p = τ 1 … τ n ⇒ ε ⋅ p ⋆
The sequential probabilistic types of [26 ] are the restriction of the present system to the default choice ⋆ \star ⋆ .
p σ ‾ ⇒ τ ‾ = σ ‾ ⇒ τ ‾ ⋅ p ⋆ \frac{p}{\overline{\sigma}} \Rightarrow\overline{\tau}
=
\overline{\sigma} \Rightarrow\overline{\tau} \cdot p\star σ p ⇒ τ = σ ⇒ τ ⋅ p ⋆
Remark 25. An element τ ‾ ⋅ p i \overline{\tau}\cdot p_i τ ⋅ p i of a distribution type gives a lower bound p p p on the probability of terminating with branch i i i . Since our types are a probabilistic form of simple types, which cannot type all normalizing λ \lambda λ -terms, the bound is necessarily not exact. Consider a term M M M which is terminating but not typeable, for example [ ⟨ y ⟩ . [ y ] . ⋆ ] . ⟨ x ⟩ . [ x ] . x [\langle y\rangle.[y].\star].\langle x\rangle.[x].x [⟨ y ⟩ . [ y ] . ⋆ ] . ⟨ x ⟩ . [ x ] . x , a variant of Ω = ( λ x . x x ) ( λ y . y y ) \Omega=(\lambda x.xx)(\lambda y.yy) Ω = ( λ x . xx ) ( λ y . y y ) that replaces the function y y y with ⋆ \star ⋆ . Then M M M terminates with probability 1 1 1 , but can only be typed by the zero-rule as M : ε ⇒ 0 M:\varepsilon\Rightarrow0 M : ε ⇒ 0 , giving a sum probability of zero. The zero-rule allows such terms to be combined with others, and express for instance that M ⊕ ⋆ M\oplus\star M ⊕ ⋆ terminates with probability at least 1 2 \frac{1}{2} 2 1 . To obtain exact bounds, one would need a type system that can type all terminating λ \lambda λ -terms, such as intersection types.
Almost-Sure Termination
The intended meaning of the type system is that if ⊢ M : ε ⇒ δ \vdash M:\varepsilon\Rightarrow\delta ⊢ M : ε ⇒ δ (i.e. M M M is closed and requires no inputs to run on the machine) then the probability of termination for M M M is at least pr ( δ ) \operatorname{pr}(\delta) pr ( δ ) . We will establish this using a reducibility argument in the style of Tait [38 ] , called runnability as it uses the machine rather than reduction. The runnability predicate directly interprets the meaning of types: a runnable term of type M : σ ‾ ⇒ δ M:\overline{\sigma}\Rightarrow\delta M : σ ⇒ δ , given a stack S S S of runnable terms for the types in σ ‾ \overline{\sigma} σ , will probabilistically evaluate to a runnable return family T T T for the type δ \delta δ , with the key property that pr ( T ) ≥ pr ( δ ) \operatorname{pr}(T)\geq\operatorname{pr}(\delta) pr ( T ) ≥ pr ( δ ) .
Definition 26. The set RUN ( τ ) \operatorname{RUN}(\tau) RUN ( τ ) of runnable terms for a type τ \tau τ is defined as the set of closed terms
RUN ( σ ‾ ⇒ δ ) = { M ∣ ∀ S ∈ RUN ( σ ‾ ) . ∃ T ∈ RUN ( δ ) . S , M ⇓ T } \operatorname{RUN}(\overline{\sigma}\Rightarrow\delta)
=
\{M \mid\forall S\in\operatorname{RUN}(\overline{\sigma}).\ \exists T\in\operatorname{RUN}(\delta).\ S,M\Downarrow T\} RUN ( σ ⇒ δ ) = { M ∣ ∀ S ∈ RUN ( σ ) . ∃ T ∈ RUN ( δ ) . S , M ⇓ T }
where the runnable sets for stack types τ ‾ \overline{\tau} τ and distribution types δ \delta δ are as follows.
RUN ( τ 1 … τ n ) = { ε M 1 … M n ∣ M i ∈ RUN ( τ i ) } \operatorname{RUN}(\tau_1\ldots\tau_n)
=
\{\varepsilon M_1\ldots M_n \mid M_i\in\operatorname{RUN}(\tau_i)\} RUN ( τ 1 … τ n ) = { ε M 1 … M n ∣ M i ∈ RUN ( τ i )}
RUN ( { ( τ ‾ i , p i ) i ∈ I } ) = { T ∣ ∀ i ∈ I . stk ( T ∣ i ) ⊆ RUN ( τ ‾ i ) ∧ pr ( T ∣ i ) ≥ p i } \operatorname{RUN}(\{(\overline{\tau}_i,p_i)_{i\in I}\})
=
\{T \mid\forall i\in I.\ \operatorname{stk}(T\mathbin{|}_i)\subseteq\operatorname{RUN}(\overline{\tau}_i)\ \land\ \operatorname{pr}(T\mathbin{|}_i)\geq p_i\} RUN ({( τ i , p i ) i ∈ I }) = { T ∣ ∀ i ∈ I . stk ( T ∣ i ) ⊆ RUN ( τ i ) ∧ pr ( T ∣ i ) ≥ p i }
To work with open terms, a substitution map μ \mu μ is a finite function from variables to terms, applied to a term as μ M \mu M μ M which replaces every free variable x x x in M M M that is in the domain of μ \mu μ with the term μ ( x ) \mu(x) μ ( x ) . For a context Γ = x 1 : τ 1 , … , x n : τ n \Gamma=x_1:\tau_1,\ldots,x_n:\tau_n Γ = x 1 : τ 1 , … , x n : τ n the set RUN ( Γ ) \operatorname{RUN}(\Gamma) RUN ( Γ ) is a set of substitution maps μ \mu μ that assigns each x i x_i x i a runnable term M ∈ RUN ( τ i ) M\in\operatorname{RUN}(\tau_i) M ∈ RUN ( τ i ) , as follows.
RUN ( Γ ) = { μ ∣ ∀ x : τ ∈ Γ . μ ( x ) ∈ RUN ( τ ) } \operatorname{RUN}(\Gamma)
=
\{\mu\mid\forall x:\tau\in\Gamma.\ \mu(x)\in\operatorname{RUN}(\tau)\} RUN ( Γ ) = { μ ∣ ∀ x : τ ∈ Γ. μ ( x ) ∈ RUN ( τ )}
We are now ready to prove the runnability lemma , that typed terms are runnable.
Lemma 27. If Γ ⊢ M : τ \Gamma\vdash M:\tau Γ ⊢ M : τ and μ ∈ RUN ( Γ ) \mu\in\operatorname{RUN}(\Gamma) μ ∈ RUN ( Γ ) then μ M ∈ RUN ( τ ) \mu M\in\operatorname{RUN}(\tau) μ M ∈ RUN ( τ ) .
Proof. See Appendix D.
The runnability lemma directly gives the main theorem of typed almost-sure termination.
Theorem 28. If ⊢ M : ε ⇒ δ \vdash M : \varepsilon\Rightarrow\delta ⊢ M : ε ⇒ δ then M M M terminates with probability at least pr ( δ ) \operatorname{pr}(\delta) pr ( δ ) .
Proof. Let δ = { ( τ i , p i ) } i ∈ I \delta= \{(\tau_i,p_i)\}_{i\in I} δ = {( τ i , p i ) } i ∈ I . By Lemma 27 we have ε , M ⇓ T \varepsilon,M \Downarrow T ε , M ⇓ T with T ∈ run ( δ ) T \in\operatorname{run}(\delta) T ∈ run ( δ ) , which means that pr ( T ∣ i ) ≥ p i \operatorname{pr}(T\mid i) \ge p_i pr ( T ∣ i ) ≥ p i for every i ∈ I i \in I i ∈ I , so that pr ( T ) ≥ pr ( δ ) \operatorname{pr}(T) \ge\operatorname{pr}(\delta) pr ( T ) ≥ pr ( δ ) .
Ground Terms and Finite Markov Chains
We have shown that the calculus introduced in this paper enjoys all the expected properties, in particular guaranteeing almost-sure termination. Several natural questions concerning the expressive power of the calculus remain open. Notably, it is of interest to investigate the behavior of the calculus under restrictions to low-order types, or when stronger termination properties than AST, such as positive almost-sure termination (PAST), can be proved. In this section we resume our discussion of ground terms from the introduction.
Ground terms: M , N : : = i ∣ M ; i → N ∣ M i ∣ [ a ] . a M,N ::= i \mid M\,;\,_{i\to}N \mid M^i \mid[a].a M , N ::= i ∣ M ; i → N ∣ M i ∣ [ a ] . a
We will show the following properties: one, typing of ground terms is decidable; two, ground terms readily encode as finite Markov chains; and three, finite Markov chains may be encoded as ground terms. These then have the following consequences. The last two properties imply that ground terms are equivalent to finite Markov chains. Next, since finite Markov chains are PAST (if they are AST), also typed ground terms are PAST. Finally, combining the first and last property, for the encoding of a Markov chain as a ground term, type inference calculates the probability of terminating with each final state.
As in the introduction, we may restrict types for ground terms to sub-distributions over choice labels, and abbreviate them by omitting input and return types.
M : p 1 i 1 ⊕ ⋯ ⊕ p n i n M : p_1i_1 \oplus\cdots\oplus p_ni_n M : p 1 i 1 ⊕ ⋯ ⊕ p n i n abbreviates M : ε ⇒ ε ⋅ p 1 i 1 ⊕ ⋯ ⊕ ε ⋅ p n i n M : \varepsilon\Rightarrow\varepsilon\cdot p_1i_1 \oplus\cdots\oplus\varepsilon\cdot p_ni_n M : ε ⇒ ε ⋅ p 1 i 1 ⊕ ⋯ ⊕ ε ⋅ p n i n
Since ground terms are closed, the typing rules may further omit contexts. Thus restricted, we recover the typing rules from the introduction (with new notation).
i : 1 i M : γ ⊕ p i N : δ M ; i → N : γ ⊔ ( p ⋅ δ ) M : δ ⊕ p i ( p ≠ 1 ) M i : 1 1 − p ⋅ δ [ a ] . a : 1 2 ⊤ ⊕ 1 2 ⊥ \begin{aligned}
i &: 1_i \\
M : \gamma\oplus p_i \qquad N &: \delta\\
M\,;\,_{i\to}N &: \gamma\sqcup(p\cdot\delta) \\
M : \delta\oplus p_i \qquad&(p\ne1) \\
M^i &: \frac{1}{1-p}\cdot\delta\\
[a].a &: \frac{1}{2}\top\oplus\frac{1}{2}\bot
\end{aligned} i M : γ ⊕ p i N M ; i → N M : δ ⊕ p i M i [ a ] . a : 1 i : δ : γ ⊔ ( p ⋅ δ ) ( p = 1 ) : 1 − p 1 ⋅ δ : 2 1 ⊤ ⊕ 2 1 ⊥
Proposition 29. Typing for ground terms is decidable.
Proof. Immediate by induction on the term.
We will define Markov chains as probabilistic automata, as follows. We write D X D_X D X for the set of probability distributions over a set X X X , and write a distribution over X = { x 1 , x 2 , … } X=\{x_1,x_2,\ldots\} X = { x 1 , x 2 , … } as { p 1 x 1 , p 2 x 2 , … } \{p_1x_1,p_2x_2,\ldots\} { p 1 x 1 , p 2 x 2 , … } .
Definition 30. A Markov chain C = ( S , s , F , δ ) C=(S,s,F,\delta) C = ( S , s , F , δ ) is given by a set of states S S S , a starting state s ∈ S s\in S s ∈ S , a set of final states F ⊆ S F\subseteq S F ⊆ S , and a stochastic transition function δ : S ∖ F → D S \delta:S\setminus F\to D_S δ : S ∖ F → D S from non-final states to states.
The translation ⟦ M ⟧ \llbracket M\rrbracket [ [ M ] ] from ground terms to Markov chains will take M M M to a chain
⟦ M ⟧ = ( S M , s M , F M , δ M ) \llbracket M\rrbracket= (S_M,s_M,F_M,\delta_M) [ [ M ] ] = ( S M , s M , F M , δ M )
where internal states S M ∖ F M S_M \setminus F_M S M ∖ F M represent subformulas and final states represent choices not captured by a later case construct. We consider chains modulo renaming of internal states, and when combining the translations of two terms we assume their internal states to be disjoint, but final states may overlap. To connect two chains, we use the notation s { t / i } s\{t/i\} s { t / i } to rename a state, and the notation δ { s / i } \delta\{s/i\} δ { s / i } which replaces all transitions to a (final) state i i i with transitions to s s s .
δ { s / i } ( r ) = { p ( t { s / i } ) ∣ p t ∈ δ ( r ) } i { t / i } = t s { t / i } = s ( s ≠ i ) \delta\{s/i\}(r)=\{p(t\{s/i\})\mid pt\in\delta(r)\}
\qquad
\begin{aligned}
i\{t/i\}&=t\\
s\{t/i\}&=s\quad(s\ne i)
\end{aligned} δ { s / i } ( r ) = { p ( t { s / i }) ∣ pt ∈ δ ( r )} i { t / i } s { t / i } = t = s ( s = i )
The translation ⟦ − ⟧ \llbracket\mathord{-}\rrbracket [ [ − ] ] is then as follows.
⟦ i ⟧ = ( { s , i } , s , { i } , s ↦ { i ⋅ 1 } ) \llbracket i\rrbracket=(\{s,i\},s,\{i\},s\mapsto\{i\cdot1\}) [ [ i ] ] = ({ s , i } , s , { i } , s ↦ { i ⋅ 1 })
⟦ M ; i → N ⟧ = ( S M ∖ { i } ∪ S N , s M , F M ∖ { i } ∪ F N , δ M { s N / i } ∪ δ N ) \llbracket M;i\to N\rrbracket=(S_M\setminus\{i\}\cup S_N,s_M,F_M\setminus\{i\}\cup F_N,\delta_M\{s_N/i\}\cup\delta_N) [ [ M ; i → N ] ] = ( S M ∖ { i } ∪ S N , s M , F M ∖ { i } ∪ F N , δ M { s N / i } ∪ δ N )
⟦ M i ⟧ = ( S M ∖ { i } , s M , F M ∖ { i } , δ M { s M / i } ) \llbracket M^i\rrbracket=(S_M\setminus\{i\},s_M,F_M\setminus\{i\},\delta_M\{s_M/i\}) [ [ M i ] ] = ( S M ∖ { i } , s M , F M ∖ { i } , δ M { s M / i })
⟦ [ a ] p . a ⟧ = ( { s , ⊤ , ⊥ } , s , { ⊤ , ⊥ } , s ↦ { 1 2 ⊤ , 1 2 ⊥ } ) \llbracket[a]_p.a\rrbracket=(\{s,\top,\bot\},s,\{\top,\bot\},s\mapsto\{\tfrac{1}{2}\top,\tfrac{1}{2}\bot\}) [ [ [ a ] p . a ] ] = ({ s , ⊤ , ⊥ } , s , { ⊤ , ⊥ } , s ↦ { 2 1 ⊤ , 2 1 ⊥ })
Example 31. For our running example term M M M the translation is as follows.
M = ( [ a ] 1 / 2 . a ; ⊤ → h ; ⊥ → [ b ] 1 / 2 . b ; ⊤ → t ; ⊥ → i ) i M=\bigl([a]_{1/2}.a;\top\to h;\bot\to[b]_{1/2}.b;\top\to t;\bot\to i\bigr)^i M = ( [ a ] 1/2 . a ; ⊤ → h ; ⊥ → [ b ] 1/2 . b ; ⊤ → t ; ⊥ → i ) i
⟦ M ⟧ = ( { a , b , r , s , u , h , t } , r , { h , t } , a ↦ { 1 2 r , 1 2 b } r ↦ { 1 h } b ↦ { 1 2 s , 1 2 u } s ↦ { 1 t } u ↦ { 1 r } ) \llbracket M\rrbracket=
\left(\{a,b,r,s,u,h,t\},r,\{h,t\},
\begin{aligned}
a&\mapsto\{\tfrac{1}{2}r,\tfrac{1}{2}b\} & r&\mapsto\{1h\}\\
b&\mapsto\{\tfrac{1}{2}s,\tfrac{1}{2}u\} & s&\mapsto\{1t\}\\
u&\mapsto\{1r\}
\end{aligned}
\right) [ [ M ] ] = { a , b , r , s , u , h , t } , r , { h , t } , a b u ↦ { 2 1 r , 2 1 b } ↦ { 2 1 s , 2 1 u } ↦ { 1 r } r s ↦ { 1 h } ↦ { 1 t }
Figure 1 (PDF p. 15).
In the other direction, we give an interpretation ⟦ C ⟧ \llbracket C\rrbracket [ [ C ] ] of a finite Markov chain as a ground term. The translation operates as follows, using states as choice labels. Given C C C with starting state s s s and transition s ↦ { p 1 t 1 , … , p n t n } ∈ δ s\mapsto\{p_1t_1,\ldots,p_nt_n\}\in\delta s ↦ { p 1 t 1 , … , p n t n } ∈ δ , we remove this transition and consider the sub-chains C ( t i ) C(t_i) C ( t i ) for i ≤ n i\le n i ≤ n with new starting state t i t_i t i , in which s s s becomes a final state. These are translated inductively to M i M_i M i . Then ⟦ C ⟧ \llbracket C\rrbracket [ [ C ] ] is given by a term M s M^s M s , iterating on s s s , where M M M is a probabilistic sum that chooses M i M_i M i with probability p i p_i p i . We formalize this below.
For C = ( S , s , F , δ ) C=(S,s,F,\delta) C = ( S , s , F , δ ) and t ∈ S t\in S t ∈ S let C ( t ) = ( S , t , F ∪ { s } , δ ∖ { s } ) C(t)=(S,t,F\cup\{s\},\delta\setminus\{s\}) C ( t ) = ( S , t , F ∪ { s } , δ ∖ { s }) where δ ∖ X \delta\setminus X δ ∖ X is the transition function δ \delta δ restricted to the domain dom ( δ ) ∖ X \operatorname{dom}(\delta)\setminus X dom ( δ ) ∖ X . Write p 1 M 1 ⊕ ⋯ ⊕ p n M n p_1M_1\oplus\cdots\oplus p_nM_n p 1 M 1 ⊕ ⋯ ⊕ p n M n for the term that chooses M i M_i M i with probability p i p_i p i , given inductively below; recall that [ a ] p [a]_p [ a ] p represents an unfair coin toss, given either as primitive or encoded with [ a ] [a] [ a ] and iteration.
p M ⊕ q 1 N 1 ⊕ ⋯ ⊕ q n N n = [ a ] p . a ; ⊤ → M ; ⊥ → ( q 1 1 − p N 1 ⊕ ⋯ ⊕ q n 1 − p N n ) pM\oplus q_1N_1\oplus\cdots\oplus q_nN_n=[a]_p.a;\top\to M;\bot\to\left(\frac{q_1}{1-p}N_1\oplus\cdots\oplus\frac{q_n}{1-p}N_n\right) pM ⊕ q 1 N 1 ⊕ ⋯ ⊕ q n N n = [ a ] p . a ; ⊤ → M ; ⊥ → ( 1 − p q 1 N 1 ⊕ ⋯ ⊕ 1 − p q n N n )
Then the interpretation of a Markov chain C = ( S , s , F , δ ) C=(S,s,F,\delta) C = ( S , s , F , δ ) as a term is as follows.
⟦ C ⟧ = { s if s ∈ F ( p 1 ⟦ C ( t 1 ) ⟧ ⊕ ⋯ ⊕ p n ⟦ C ( t n ) ⟧ ) s where δ ( s ) = { p 1 t 1 , … , p n t n } \llbracket C\rrbracket=
\begin{cases}
s & \text{if }s\in F\\
\left(p_1\llbracket C(t_1)\rrbracket\oplus\cdots\oplus p_n\llbracket C(t_n)\rrbracket\right)^s & \text{where }\delta(s)=\{p_1t_1,\ldots,p_nt_n\}
\end{cases} [ [ C ] ] = { s ( p 1 [ [ C ( t 1 ) ] ] ⊕ ⋯ ⊕ p n [ [ C ( t n ) ] ] ) s if s ∈ F where δ ( s ) = { p 1 t 1 , … , p n t n }
Example 32. Consider the following Markov chain C C C , where each arrow has probability 1 3 \frac{1}{3} 3 1 , and its typed interpretation ⟦ C ⟧ \llbracket C\rrbracket [ [ C ] ] , writing M ⊕ N ⊕ P M\oplus N\oplus P M ⊕ N ⊕ P for the term 1 3 M ⊕ 1 3 N ⊕ 1 3 P \frac{1}{3}M\oplus\frac{1}{3}N\oplus\frac{1}{3}P 3 1 M ⊕ 3 1 N ⊕ 3 1 P . A fully worked version is in Appendix C.
Figure 2 (PDF p. 15).
C = ( { a , b , c , i , j , k } , a , { i , j , k } , a ↦ { 1 3 b , 1 3 c , 1 3 i } b ↦ { 1 3 a , 1 3 c , 1 3 j } c ↦ { 1 3 a , 1 3 b , 1 3 k } ) C=\left(\{a,b,c,i,j,k\},a,\{i,j,k\},
\begin{aligned}
a&\mapsto\{\tfrac{1}{3}b,\tfrac{1}{3}c,\tfrac{1}{3}i\}\\
b&\mapsto\{\tfrac{1}{3}a,\tfrac{1}{3}c,\tfrac{1}{3}j\}\\
c&\mapsto\{\tfrac{1}{3}a,\tfrac{1}{3}b,\tfrac{1}{3}k\}
\end{aligned}
\right) C = { a , b , c , i , j , k } , a , { i , j , k } , a b c ↦ { 3 1 b , 3 1 c , 3 1 i } ↦ { 3 1 a , 3 1 c , 3 1 j } ↦ { 3 1 a , 3 1 b , 3 1 k }
⟦ C ⟧ = ( ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ i ) b ⊕ k ) c ⊕ i ) a ⊕ 1 2 i ⊕ 1 4 j ⊕ 1 4 k \llbracket C\rrbracket=
\left((a\oplus(a\oplus b\oplus k)^c\oplus j)^b\oplus(a\oplus(a\oplus c\oplus i)^b\oplus k)^c\oplus i\right)^a\oplus\tfrac{1}{2}i\oplus\tfrac{1}{4}j\oplus\tfrac{1}{4}k [ [ C ] ] = ( ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ i ) b ⊕ k ) c ⊕ i ) a ⊕ 2 1 i ⊕ 4 1 j ⊕ 4 1 k
The translations ⟦ − ⟧ \llbracket-\rrbracket [ [ − ] ] and ⟦ − ⟧ \llbracket-\rrbracket [ [ − ] ] above demonstrate the following.
Proposition 33. Ground terms of the PFMC are equivalent to finite Markov chains.
Markov chains are PAST if they are AST, i.e. if any path may eventually reach a final state.
For typed ground terms, which are AST, we then have the following.
Proposition 34. Typed ground terms with sum probability 1 of the PFMC⇒ ⊕ _{\Rightarrow\oplus} ⇒ ⊕ are PAST.
Combining type inference for ground terms (Proposition 29) and the translation ⟦ − ⟧ \llbracket-\rrbracket [ [ − ] ] , we have the following result.
Proposition 35. Encoding and typing a finite Markov chain computes its return distribution: if ⟦ C ⟧ : p 1 s 1 ⊕ ⋯ ⊕ p n s n \llbracket C\rrbracket: p_1s_1 \oplus\cdots\oplus p_ns_n [ [ C ] ] : p 1 s 1 ⊕ ⋯ ⊕ p n s n then C C C terminates in the state s i s_i s i with probability p i p_i p i .
Proof. By construction.
Moving past PAST
Further exploring the expressive power of the calculus, in this section we demonstrate that typed terms in general might be null AST (NAST), i.e. AST, but not PAST. We will give an example term with infinite expected running time, despite terminating with probability one. Our example relies crucially on higher-order functions. Consider the following term, for a given M M M , using the default choice ⋆ \star ⋆ as imperative skip and its case as sequential composition, M ; N = M ; ⋆ → N M;N = M;\star\to N M ; N = M ; ⋆ → N .
[ M ] . ( ( ⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ ) [M].((\langle f\rangle.[f;f].i)\oplus\star) [ M ] . ((⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ )
With probability 1 2 \frac{1}{2} 2 1 it composes the term on the stack with itself and iterates, or it terminates. Evaluating this term on the machine gives the following return family, for the sequence of terms M n M_n M n given by M 0 = M M_0=M M 0 = M and M n + 1 = M n ; M n M_{n+1}=M_n;M_n M n + 1 = M n ; M n .
{ ( M n , ⋆ ) ⊤ n ⊥ ∣ n ∈ N } = { ( M , ⋆ ) ⊥ , ( M ; M , ⋆ ) ⊤ ⊥ , ( ( M ; M ) ; ( M ; M ) , ⋆ ) ⊤ ⊤ ⊥ , … } \{(M_n,\star)_{\top^n\perp}\mid n\in\mathbb{N}\}=\{(M,\star)_{\perp},(M;M,\star)_{\top\perp},((M;M);(M;M),\star)_{\top\top\perp},\ldots\} {( M n , ⋆ ) ⊤ n ⊥ ∣ n ∈ N } = {( M , ⋆ ) ⊥ , ( M ; M , ⋆ ) ⊤ ⊥ , (( M ; M ) ; ( M ; M ) , ⋆ ) ⊤⊤ ⊥ , … }
We may then evaluate the term M n M_n M n left on the stack by post-composing with ⟨ g ⟩ . g \langle g\rangle.g ⟨ g ⟩ . g , which pops and runs it, possibly using further base values further down on the stack. If M M M terminates successfully with ⋆ \star ⋆ in m m m steps, M n M_n M n takes m × 2 n m\times2^n m × 2 n steps. For example, assuming a natural numbers type N \mathbb{N} N with primitives zero 0 : N 0:\mathbb{N} 0 : N and addition + : N N ⇒ N ⋅ 1 ⋆ +:\mathbb{N}\mathbb{N}\Rightarrow\mathbb{N}\cdot1\star + : NN ⇒ N ⋅ 1 ⋆ , we let M M M be the successor function [ 1 ] . + : N ⇒ N ⋅ 1 ⋆ [1].+:\mathbb{N}\Rightarrow\mathbb{N}\cdot1\star [ 1 ] . + : N ⇒ N ⋅ 1 ⋆ . The term below left then gives the return family below right, taking m × 2 n m\times2^n m × 2 n machine steps (for some small constant m m m ) to compute the number 2 n : N 2^n:\mathbb{N} 2 n : N from zero and successor. Since the probability of returning 2 n 2^n 2 n is 1 2 n + 1 \frac{1}{2^{n+1}} 2 n + 1 1 , the expected evaluation time on the machine is infinite: the term is not PAST.
[ 0 ] . [ [ 1 ] . + ] . ( ( ⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ ) i ; ⟨ g ⟩ . g : ε ⇒ N ⋅ 1 ⋆ [0].[[1].+].((\langle f\rangle.[f;f].i)\oplus\star)^i;\langle g\rangle.g:\varepsilon\Rightarrow\mathbb{N}\cdot1\star [ 0 ] . [[ 1 ] . + ] . ((⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ ) i ; ⟨ g ⟩ . g : ε ⇒ N ⋅ 1 ⋆
{ ( 2 n , ⋆ ) ⊤ n ⊥ ∣ n ∈ N } \{(2^n,\star)_{\top^n\perp}\mid n\in\mathbb{N}\} {( 2 n , ⋆ ) ⊤ n ⊥ ∣ n ∈ N }
The term is typed: for any τ \tau τ , if M M M is typed M : τ ⇒ τ ⋅ 1 ⋆ M:\tau\Rightarrow\tau\cdot1\star M : τ ⇒ τ ⋅ 1 ⋆ then we have M n : τ ⇒ τ ⋅ 1 ⋆ M^n:\tau\Rightarrow\tau\cdot1\star M n : τ ⇒ τ ⋅ 1 ⋆ , such as in the case above where τ = N \tau=\mathbb{N} τ = N . For the loop we then have the following.
⊢ ( ⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ : σ ⇒ σ ⋅ 1 2 ⋆ ⊕ σ ⋅ 1 2 ⋆ ⊢ ( ( ⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ ) i : σ ⇒ σ ⋅ 1 ⋆ \frac{\vdash(\langle f\rangle.[f;f].i)\oplus\star:\sigma\Rightarrow\sigma\cdot\frac{1}{2}\star\oplus\sigma\cdot\frac{1}{2}\star}{\vdash((\langle f\rangle.[f;f].i)\oplus\star)^i:\sigma\Rightarrow\sigma\cdot1\star} ⊢ ((⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ ) i : σ ⇒ σ ⋅ 1 ⋆ ⊢ (⟨ f ⟩ . [ f ; f ] . i ) ⊕ ⋆ : σ ⇒ σ ⋅ 2 1 ⋆ ⊕ σ ⋅ 2 1 ⋆
where σ = τ ⇒ τ ⋅ 1 ⋆ \sigma=\tau\Rightarrow\tau\cdot1\star σ = τ ⇒ τ ⋅ 1 ⋆ .
The term ⟨ g ⟩ . g : ( τ ‾ ⇒ τ ‾ ⋅ 1 ⋆ ) τ ‾ ⇒ τ ‾ ⋅ 1 ⋆ \langle g\rangle.g:(\overline{\tau}\Rightarrow\overline{\tau}\cdot1\star)\,\overline{\tau}\Rightarrow\overline{\tau}\cdot1\star ⟨ g ⟩ . g : ( τ ⇒ τ ⋅ 1 ⋆ ) τ ⇒ τ ⋅ 1 ⋆ takes M n : τ ‾ ⇒ τ ‾ ⋅ 1 ⋆ M^n:\overline{\tau}\Rightarrow\overline{\tau}\cdot1\star M n : τ ⇒ τ ⋅ 1 ⋆ off the stack and evaluates it with an appropriate remaining stack of type τ ‾ \overline{\tau} τ . The existence of a typed term that is not PAST then demonstrates the following.
Proposition 36. The typed probabilistic FMC is not positive almost-surely terminating.
Limitations and Prospects
The key to our type system is that it enforces a fixed probability of exiting or continuing for each iteration of a loop. Naturally, this limits expressiveness, as it prevents the typing of iteration with growing or shrinking probabilities, which might nevertheless be AST. Here, we explore how to express such algorithms in the untyped calculus, examine why they cannot be typed, and consider the prospects of lifting this restriction.
Consider an unfair coin toss M : ⊤ ⊕ p ⊥ M : \top\mathbin{\oplus_{p}} \bot M : ⊤ ⊕ p ⊥ , using a (further) abbreviated notation ⊤ ⊕ p ⊥ \top\mathbin{\oplus_{p}} \bot ⊤ ⊕ p ⊥ for the type ε ⇒ ε ⋅ p ⊤ ⊕ ε ⋅ ( 1 − p ) ⊥ \varepsilon\Rightarrow\varepsilon\cdot p\top\oplus\varepsilon\cdot(1-p)\bot ε ⇒ ε ⋅ p ⊤ ⊕ ε ⋅ ( 1 − p ) ⊥ . We may construct terms with modified probabilities for example as follows.
[ a ] q ⋅ a ; ⊤ → M : ⊤ ⊕ p q ⊥ M ; ⊤ → M : ⊤ ⊕ p 2 ⊥ [a]_{q} \cdot a \mathbin{;} \top\to M : \top\mathbin{\oplus_{pq}} \bot\qquad M \mathbin{;} \top\to M : \top\mathbin{\oplus_{p^{2}}} \bot [ a ] q ⋅ a ; ⊤ → M : ⊤ ⊕ pq ⊥ M ; ⊤ → M : ⊤ ⊕ p 2 ⊥
To alter the probability of exiting a loop during iteration, we make essential use of the higher-order nature of the calculus: we store the intended loop body on the stack, and modify it during iteration. Using the second construction above:
[ M ] . ( ⟨ x ⟩ . ( x ; ⊥ → [ x ; ⊤ → x ] . ⋆ ) ) ⋆ [M] \mathbin{.} \left(\langle x\rangle\mathbin{.} \left(x \mathbin{;} \bot\to[x \mathbin{;} \top\to x] \mathbin{.} \star\right) \right)^{\star} [ M ] . ( ⟨ x ⟩ . ( x ; ⊥ → [ x ; ⊤ → x ] . ⋆ ) ) ⋆
The term starts with M M M on the stack; pops and evaluates it; on ⊤ \top ⊤ , it exits the loop; on ⊥ \bot ⊥ , it pushes M ; ⊤ → M M \mathbin{;} \top\to M M ; ⊤ → M to the stack and iterates. The probability to exit the loop squares at each iteration, from p p p to p 2 p^{2} p 2 , p 4 p^{4} p 4 , p 8 p^{8} p 8 , p 16 p^{16} p 16 , etc. The probability of non-termination is ∏ n ∈ N ( 1 − p 2 n ) \prod_{n\in\mathbb{N}}(1-p^{2^{n}}) ∏ n ∈ N ( 1 − p 2 n ) , which is non-zero e.g. for p = 1 2 p=\frac{1}{2} p = 2 1 : the term is not AST.
The reason why the term cannot be typed is subtle: it is because the loop body changes the probability on the stack. The body itself can be typed, for any probability q q q :
⟨ x ⟩ . ( x ; ⊥ → [ x ; ⊤ → x ] . ⋆ ) : ( ⊤ ⊕ q ⊥ ) ⇒ ε ⋅ q ⊤ ⊕ ( ⊤ ⊕ q 2 ⊥ ) ⋅ ( 1 − q ) ⋆ \langle x\rangle\mathbin{.} \left(x \mathbin{;} \bot\to[x \mathbin{;} \top\to x] \mathbin{.} \star\right) : (\top\mathbin{\oplus_{q}} \bot) \Rightarrow\varepsilon\cdot q\top\oplus(\top\mathbin{\oplus_{q^{2}}} \bot) \cdot(1-q)\star ⟨ x ⟩ . ( x ; ⊥ → [ x ; ⊤ → x ] . ⋆ ) : ( ⊤ ⊕ q ⊥ ) ⇒ ε ⋅ q ⊤ ⊕ ( ⊤ ⊕ q 2 ⊥ ) ⋅ ( 1 − q ) ⋆
But to type the loop requires the same input and output types on the stack, while ⊤ ⊕ q ⊥ \top\mathbin{\oplus_{q}} \bot ⊤ ⊕ q ⊥ and ⊤ ⊕ q 2 ⊥ \top\mathbin{\oplus_{q^{2}}} \bot ⊤ ⊕ q 2 ⊥ are distinct.
This observation explains how the type system enforces fixed probabilities during iteration: the probabilities of all inputs—the stack—need to remain fixed. This remains a main limitation of the type system, as it also prevents typing similar terms to the above example that are AST, for example one that increases (rather than decreases) the probability of exiting the loop. Finally, the above considerations indicate how the type system might be extended to accommodate iteration with changing probability: by introducing variables for probabilities, and arithmetic functions over them, into the type system, approaching a form of dependent types.
Conclusion
We have demonstrated a type system for almost-sure termination in a probabilistic λ \lambda λ -calculus with iteration, the PFMC ⇒ ⊕ \Rightarrow_{\oplus} ⇒ ⊕ . As a direct probabilistic generalization of the FMC and typed iteration, we believe this to be a natural account of AST. essive power beyond positive AST.
In future work, we intend to further analyse the expressive power of the calculus and fragments of it. At present, being an extension of simple types with fixed probabilities of iteration, it is clear that the expressive power of the typed calculus for real algorithms is limited. Addressing this, we expect that the type system will generalize with polymorphism, dependent types, and intersection types along standard lines. A dependently typed generalisation would be akin to Hoare logic, and might facilitate reasoning about probabilistic termination in theorem provers and give natural ways to include termination evidence in typed imperative programming languages.
On function composition and recursion
As the introduction set out, typed almost-sure termination arises naturally by replacing the sum in the standard typed iterator with a probabilistic sum. The probabilistic FMC integrates iteration into the λ \lambda λ -calculus, giving AST in a higher-order setting. The λ \lambda λ -calculus is however more commonly associated with recursion than iteration. A pertinent question is then whether typed AST is also possible for recursion. Here, we consider the obstacles to typing probabilistic termination in a probabilistic λ \lambda λ -calculus without branching and iteration. We will use the type system for the probabilistic event λ \lambda λ -calculus, given by arrow types over probabilities p ∈ Q ∩ [ 0 , 1 ] p \in\mathbb{Q} \cap[0,1] p ∈ Q ∩ [ 0 , 1 ] .
σ , τ : : = p ∣ σ → τ \sigma, \tau::= p \mid\sigma\to\tau σ , τ ::= p ∣ σ → τ
First, we compare function composition,
g ∘ f = λ x . g ( f x ) g \circ f = \lambda x. g(f x) g ∘ f = λ x . g ( f x )
against sequencing f ; g f ; g f ; g . The particular problem is to type self-composition, f ∘ f f \circ f f ∘ f (the Church numeral two). Suppose we have f : 1 → 1 2 f : 1 \to\frac{1}{2} f : 1 → 2 1 , i.e. f f f returns with probability 1 2 \frac{1}{2} 2 1 , so that we need f ∘ f : 1 → 1 4 f \circ f : 1 \to\frac{1}{4} f ∘ f : 1 → 4 1 . For input x : 1 x : 1 x : 1 we get f x : 1 2 f x : \frac{1}{2} f x : 2 1 , as expected, but to apply f f f again we need to modify its type to f : 1 2 → 1 4 f : \frac{1}{2} \to\frac{1}{4} f : 2 1 → 4 1 . This may be approached in several ways.
Using intersection types : we assign f f f a collection of multiple types f : { 1 → 1 2 , 1 2 → 1 4 } f : \{1 \to\frac{1}{2}, \frac{1}{2} \to\frac{1}{4}\} f : { 1 → 2 1 , 2 1 → 4 1 } . This is used in [1 ] , among others.
Using subtyping : we may introduce a subtyping relation that coerces f : 1 → 1 2 f : 1 \to\frac{1}{2} f : 1 → 2 1 to f : 1 2 → 1 4 f : \frac{1}{2} \to\frac{1}{4} f : 2 1 → 4 1 by multiplying all probabilities by a fixed factor, in this case 1 2 \frac{1}{2} 2 1 . This is a rather coarse approach, since it ignores the actual flow of computation in a term, and only works as long as the type system does not multiply any probabilities.
Using polymorphic types : with probabilistic type variables we may assign the type f : p → 1 2 p f : p \to\frac{1}{2}p f : p → 2 1 p , which instantiates to f : 1 → 1 2 f : 1 \to\frac{1}{2} f : 1 → 2 1 and f : 1 2 → 1 4 f : \frac{1}{2} \to\frac{1}{4} f : 2 1 → 4 1 .
While these are all reasonable ideas, they are not as simple and natural as our current approach using sequential composition and iteration, which has the intrinsic ability to multiply the probabilities of sequential computations:
f : τ ⇒ τ ⋅ 1 2 ⋆ and f ; f : τ ⇒ τ ⋅ 1 4 ⋆ f : \tau\Rightarrow\tau\cdot\frac{1}{2}^{\star}
\qquad\text{and}\qquad
f ; f : \tau\Rightarrow\tau\cdot\frac{1}{4}^{\star} f : τ ⇒ τ ⋅ 2 1 ⋆ and f ; f : τ ⇒ τ ⋅ 4 1 ⋆
Turning to recursion, consider the following two recursive terms f f f and g g g , where 1 : 1 1 : 1 1 : 1 is a terminating constant and Ω = ( λ x . x x ) ( λ x . x x ) : 0 \Omega= (\lambda x.xx)(\lambda x.xx) : 0 Ω = ( λ x . xx ) ( λ x . xx ) : 0 diverges.
f = 1 ⊕ ( Ω ⊕ f ) g = g ⊕ g f = 1 \oplus(\Omega\oplus f)
\qquad
g = g \oplus g f = 1 ⊕ ( Ω ⊕ f ) g = g ⊕ g
Analogous to our running example from the introduction, f f f should return with probability 2 3 \frac{2}{3} 3 2 , and indeed we are able to assign that as its type:
f : 2 3 ⊢ 1 ⊕ ( Ω ⊕ f ) : 2 3 f : \frac{2}{3} \vdash1 \oplus(\Omega\oplus f) : \frac{2}{3} f : 3 2 ⊢ 1 ⊕ ( Ω ⊕ f ) : 3 2
However, we are also able to type g g g , which diverges, with any probability p p p :
g : p ⊢ g ⊕ g : p g : p \vdash g \oplus g : p g : p ⊢ g ⊕ g : p
The key problem is that with recursion, termination happens through weakening , i.e. discarding the recursive function call. In f f f , the terminating branch 1 1 1 discards the recursive call,
( ⊥ ⊥ ⊤ , ε , ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i , ε ) ( ⊥ ⊥ ⊤ , ε , a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) , ( i → M ) ) ( ⊥ ⊥ ⊤ , ε , a . a ; ⊤ → h , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ⊥ ⊥ ⊤ , ε , a . a , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ⊥ ⊤ , ε , ⊥ , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ⊥ ⊤ , ε , ⊥ , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ⊥ ⊤ , ε , b . b ; ⊤ → t ; ⊥ → i , ( i → M ) ) ( ⊥ ⊤ , ε , b . b ; ⊤ → t , ( ⊥ → i ) ( i → M ) ) ( ⊥ ⊤ , ε , b . b , ( ⊤ → t ) ( ⊥ → i ) ( i → M ) ) ( ⊤ , ε , ⊥ , ( ⊤ → t ) ( ⊥ → i ) ( i → M ) ) ( ⊤ , ε , ⊥ , ( ⊥ → i ) ( i → M ) ) ( ⊤ , ε , i , ( i → M ) ) ( ⊤ , ε , ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i , ε ) ( ⊤ , ε , a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) , ( i → M ) ) ( ⊤ , ε , a . a ; ⊤ → h , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ⊤ , ε , a . a , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ε , ε , ⊤ , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ε , ε , h , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) ( i → M ) ) ( ε , ε , h , ( i → M ) ) ( ε , ε , h , ε ) \begin{aligned}
&(\bot\bot\top,\varepsilon,(\boxed{a}.a;\top\to h;\bot\to(\boxed{b}.b;\top\to t;\bot\to i))^{i},\varepsilon)\\
&(\bot\bot\top,\varepsilon,\boxed{a}.a;\top\to h;\bot\to(\boxed{b}.b;\top\to t;\bot\to i), (i\to M))\\
&(\bot\bot\top,\varepsilon,\boxed{a}.a;\top\to h,(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\bot\bot\top,\varepsilon,\boxed{a}.a,(\top\to h)(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\bot\top,\varepsilon,\bot,(\top\to h)(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\bot\top,\varepsilon,\bot,(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\bot\top,\varepsilon,\boxed{b}.b;\top\to t;\bot\to i,(i\to M))\\
&(\bot\top,\varepsilon,\boxed{b}.b;\top\to t,(\bot\to i)(i\to M))\\
&(\bot\top,\varepsilon,\boxed{b}.b,(\top\to t)(\bot\to i)(i\to M))\\
&(\top,\varepsilon,\bot,(\top\to t)(\bot\to i)(i\to M))\\
&(\top,\varepsilon,\bot,(\bot\to i)(i\to M))\\
&(\top,\varepsilon,i,(i\to M))\\
&(\top,\varepsilon,(\boxed{a}.a;\top\to h;\bot\to(\boxed{b}.b;\top\to t;\bot\to i))^{i},\varepsilon)\\
&(\top,\varepsilon,\boxed{a}.a;\top\to h;\bot\to(\boxed{b}.b;\top\to t;\bot\to i),(i\to M))\\
&(\top,\varepsilon,\boxed{a}.a;\top\to h,(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\top,\varepsilon,\boxed{a}.a,(\top\to h)(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\varepsilon,\varepsilon,\top,(\top\to h)(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\varepsilon,\varepsilon,h,(\bot\to(\boxed{b}.b;\top\to t;\bot\to i))(i\to M))\\
&(\varepsilon,\varepsilon,h,(i\to M))\\
&(\varepsilon,\varepsilon,h,\varepsilon)
\end{aligned} ( ⊥⊥⊤ , ε , ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i , ε ) ( ⊥⊥⊤ , ε , a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) , ( i → M )) ( ⊥⊥⊤ , ε , a . a ; ⊤ → h , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ⊥⊥⊤ , ε , a . a , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ⊥⊤ , ε , ⊥ , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ⊥⊤ , ε , ⊥ , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ⊥⊤ , ε , b . b ; ⊤ → t ; ⊥ → i , ( i → M )) ( ⊥⊤ , ε , b . b ; ⊤ → t , ( ⊥ → i ) ( i → M )) ( ⊥⊤ , ε , b . b , ( ⊤ → t ) ( ⊥ → i ) ( i → M )) ( ⊤ , ε , ⊥ , ( ⊤ → t ) ( ⊥ → i ) ( i → M )) ( ⊤ , ε , ⊥ , ( ⊥ → i ) ( i → M )) ( ⊤ , ε , i , ( i → M )) ( ⊤ , ε , ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i , ε ) ( ⊤ , ε , a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) , ( i → M )) ( ⊤ , ε , a . a ; ⊤ → h , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ⊤ , ε , a . a , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ε , ε , ⊤ , ( ⊤ → h ) ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ε , ε , h , ( ⊥ → ( b . b ; ⊤ → t ; ⊥ → i )) ( i → M )) ( ε , ε , h , ( i → M )) ( ε , ε , h , ε )
while in g g g neither branch does, but this difference is invisible to the type system. Whether a subterm will be discarded during computation is an undecidable property typically tracked using intersection types, and not usually registered in a system of simple types.
A solution, therefore, would need to register the multiple branches of a computation, and which variables are weakened or not. For example, with polymorphism we might have the following types,
f : p ⊢ 1 ⊕ ( Ω ⊕ f ) : 1 2 ⊕ 1 4 p f : p \vdash1 \oplus(\Omega\oplus f) : \frac{1}{2} \oplus\frac{1}{4}p f : p ⊢ 1 ⊕ ( Ω ⊕ f ) : 2 1 ⊕ 4 1 p
and solve p = 1 2 + 1 4 p p=\frac{1}{2}+\frac{1}{4}p p = 2 1 + 4 1 p for p = 2 3 p=\frac{2}{3} p = 3 2 in the rule for fixed points.
This is an interesting direction to explore, and we may do so in future. However, unlike our approach for iteration, it requires moving beyond simple types, and is beyond the scope of the present work.
Running the machine
In Figure 4 we give a successful run of the machine for our running example term, unfolded to its primitives, and the trace ⊥ ⊥ ⊤ \bot\bot\top ⊥⊥⊤ .
Figure 4. A complete run of the machine
M = ( h ⊕ ( t ⊕ i ) ) i = ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i M=(h\oplus(t\oplus i))^{i}=(\boxed{a}.a;\top\to h;\bot\to(\boxed{b}.b;\top\to t;\bot\to i))^{i} M = ( h ⊕ ( t ⊕ i ) ) i = ( a . a ; ⊤ → h ; ⊥ → ( b . b ; ⊤ → t ; ⊥ → i ) ) i
Encoding Markov chains
We elaborate on Example 32, encoding the following Markov chain C C C , where each arrow has probability 1 3 \frac{1}{3} 3 1 .
Figure 1 (PDF p. 23).
S = { a , b , c , i , j , k } s = a F = { i , j , k } δ = a ↦ { 1 3 b , 1 3 c , 1 3 i } b ↦ { 1 3 a , 1 3 c , 1 3 j } c ↦ { 1 3 a , 1 3 b , 1 3 k } \begin{aligned}
S &= \{a,b,c,i,j,k\}\\
s &= a\\
F &= \{i,j,k\}\\
\delta&= a \mapsto\left\{\frac{1}{3}b,\frac{1}{3}c,\frac{1}{3}i\right\}\\
&\quad b \mapsto\left\{\frac{1}{3}a,\frac{1}{3}c,\frac{1}{3}j\right\}\\
&\quad c \mapsto\left\{\frac{1}{3}a,\frac{1}{3}b,\frac{1}{3}k\right\}
\end{aligned} S s F δ = { a , b , c , i , j , k } = a = { i , j , k } = a ↦ { 3 1 b , 3 1 c , 3 1 i } b ↦ { 3 1 a , 3 1 c , 3 1 j } c ↦ { 3 1 a , 3 1 b , 3 1 k }
The interpretation, in stages, is as follows, again writing M ⊕ N ⊕ P M \oplus N \oplus P M ⊕ N ⊕ P for 1 3 M ⊕ 1 3 N ⊕ 1 3 P \frac{1}{3}M \oplus\frac{1}{3}N \oplus\frac{1}{3}P 3 1 M ⊕ 3 1 N ⊕ 3 1 P .
⟦ C ⟧ = ( ⟦ C ( b ) ⟧ ⊕ ⟦ C ( c ) ⟧ ⊕ i ) a = ( ( a ⊕ ⟦ C ( b ) ( c ) ⟧ ⊕ j ) b ⊕ ( a ⊕ ⟦ C ( c ) ( b ) ⟧ ⊕ k ) c ⊕ i ) a = ( ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c ⊕ i ) a \begin{aligned}
\llbracket C\rrbracket&= \left(\llbracket C(b)\rrbracket\oplus\llbracket C(c)\rrbracket\oplus i\right)^{a}\\
&= \left((a\oplus\llbracket C(b)(c)\rrbracket\oplus j)^{b}\oplus(a\oplus\llbracket C(c)(b)\rrbracket\oplus k)^{c}\oplus i\right)^{a}\\
&= \left((a\oplus(a\oplus b\oplus k)^{c}\oplus j)^{b}\oplus(a\oplus(a\oplus c\oplus j)^{b}\oplus k)^{c}\oplus i\right)^{a}
\end{aligned} [ [ C ] ] = ( [ [ C ( b ) ] ] ⊕ [ [ C ( c ) ] ] ⊕ i ) a = ( ( a ⊕ [ [ C ( b ) ( c ) ] ] ⊕ j ) b ⊕ ( a ⊕ [ [ C ( c ) ( b ) ] ] ⊕ k ) c ⊕ i ) a = ( ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c ⊕ i ) a
The type is built up as follows.
( a ⊕ b ⊕ k ) c : 1 3 a ⊕ 1 3 b ⊕ 1 3 k (a\oplus b\oplus k)^{c}:\frac{1}{3}a\oplus\frac{1}{3}b\oplus\frac{1}{3}k ( a ⊕ b ⊕ k ) c : 3 1 a ⊕ 3 1 b ⊕ 3 1 k
a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j : 4 9 a ⊕ 1 9 b ⊕ 1 9 k ⊕ 1 3 j a\oplus(a\oplus b\oplus k)^{c}\oplus j:\frac{4}{9}a\oplus\frac{1}{9}b\oplus\frac{1}{9}k\oplus\frac{1}{3}j a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j : 9 4 a ⊕ 9 1 b ⊕ 9 1 k ⊕ 3 1 j
( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b : 1 2 a ⊕ 1 8 k ⊕ 3 8 j (a\oplus(a\oplus b\oplus k)^{c}\oplus j)^{b}:\frac{1}{2}a\oplus\frac{1}{8}k\oplus\frac{3}{8}j ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b : 2 1 a ⊕ 8 1 k ⊕ 8 3 j
( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c : 1 2 a ⊕ 1 8 j ⊕ 3 8 k (a\oplus(a\oplus c\oplus j)^{b}\oplus k)^{c}:\frac{1}{2}a\oplus\frac{1}{8}j\oplus\frac{3}{8}k ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c : 2 1 a ⊕ 8 1 j ⊕ 8 3 k
( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c ⊕ i : 3 8 a ⊕ 1 6 k ⊕ 1 6 j ⊕ 1 3 i (a\oplus(a\oplus b\oplus k)^{c}\oplus j)^{b}\oplus(a\oplus(a\oplus c\oplus j)^{b}\oplus k)^{c}\oplus i:\frac{3}{8}a\oplus\frac{1}{6}k\oplus\frac{1}{6}j\oplus\frac{1}{3}i ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c ⊕ i : 8 3 a ⊕ 6 1 k ⊕ 6 1 j ⊕ 3 1 i
( ( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c ⊕ i ) a : 1 4 k ⊕ 1 4 j ⊕ 1 2 i ((a\oplus(a\oplus b\oplus k)^{c}\oplus j)^{b}\oplus(a\oplus(a\oplus c\oplus j)^{b}\oplus k)^{c}\oplus i)^{a}:\frac{1}{4}k\oplus\frac{1}{4}j\oplus\frac{1}{2}i (( a ⊕ ( a ⊕ b ⊕ k ) c ⊕ j ) b ⊕ ( a ⊕ ( a ⊕ c ⊕ j ) b ⊕ k ) c ⊕ i ) a : 4 1 k ⊕ 4 1 j ⊕ 2 1 i
The interpretation may be illustrated as follows, where the solid edges represent the tree-shape of the probabilistic sums, while the dashed edges represent the loops.
Figure 2 (PDF p. 23).
M = ( N ⊕ P ⊕ i ) a N = ( a ⊕ Q ⊕ j ) b P = ( a ⊕ R ⊕ k ) c Q = ( a ⊕ b ⊕ k ) c = a ⊕ b ⊕ k R = ( a ⊕ c ⊕ j ) b = a ⊕ c ⊕ j \begin{aligned}
M &= (N\oplus P\oplus i)^{a}\\
N &= (a\oplus Q\oplus j)^{b}\\
P &= (a\oplus R\oplus k)^{c}\\
Q &= (a\oplus b\oplus k)^{c}=a\oplus b\oplus k\\
R &= (a\oplus c\oplus j)^{b}=a\oplus c\oplus j
\end{aligned} M N P Q R = ( N ⊕ P ⊕ i ) a = ( a ⊕ Q ⊕ j ) b = ( a ⊕ R ⊕ k ) c = ( a ⊕ b ⊕ k ) c = a ⊕ b ⊕ k = ( a ⊕ c ⊕ j ) b = a ⊕ c ⊕ j
As the illustration suggests, the formalism may express any probabilistic tree with backpointers. It may also express directed acyclic graphs, which yields a smaller interpretation of the Markov chain above, though still exponential, in the following term.
( b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j ; c → ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c ) a (b\oplus c\oplus i;b\to a\oplus c\oplus j;c\to(a\oplus b\oplus k;b\to a\oplus c\oplus j)^{c})^{a} ( b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j ; c → ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c ) a
The types work out the same way.
b ⊕ c ⊕ i : 1 3 b ⊕ 1 3 c ⊕ 1 3 i b \oplus c \oplus i : \tfrac{1}{3}b \oplus\tfrac{1}{3}c \oplus\tfrac{1}{3}i b ⊕ c ⊕ i : 3 1 b ⊕ 3 1 c ⊕ 3 1 i
b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j : 1 9 a ⊕ 4 9 c ⊕ 1 3 i ⊕ 1 9 j b \oplus c \oplus i\,;\, b \to a \oplus c \oplus j : \tfrac{1}{9}a \oplus\tfrac{4}{9}c \oplus\tfrac{1}{3}i \oplus\tfrac{1}{9}j b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j : 9 1 a ⊕ 9 4 c ⊕ 3 1 i ⊕ 9 1 j
( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c : 1 2 a ⊕ 1 8 j ⊕ 3 8 k (a \oplus b \oplus k\,;\, b \to a \oplus c \oplus j)^{c} : \tfrac{1}{2}a \oplus\tfrac{1}{8}j \oplus\tfrac{3}{8}k ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c : 2 1 a ⊕ 8 1 j ⊕ 8 3 k
b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j ; c → ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c : 1 3 a ⊕ 1 3 i ⊕ 1 6 j ⊕ 1 6 k b \oplus c \oplus i\,;\, b \to a \oplus c \oplus j\,;\, c \to(a \oplus b \oplus k\,;\, b \to a \oplus c \oplus j)^{c} : \tfrac{1}{3}a \oplus\tfrac{1}{3}i \oplus\tfrac{1}{6}j \oplus\tfrac{1}{6}k b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j ; c → ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c : 3 1 a ⊕ 3 1 i ⊕ 6 1 j ⊕ 6 1 k
( b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j ; c → ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c ) a : 1 2 i ⊕ 1 4 j ⊕ 1 4 k (b \oplus c \oplus i\,;\, b \to a \oplus c \oplus j\,;\, c \to(a \oplus b \oplus k\,;\, b \to a \oplus c \oplus j)^{c})^{a} : \tfrac{1}{2}i \oplus\tfrac{1}{4}j \oplus\tfrac{1}{4}k ( b ⊕ c ⊕ i ; b → a ⊕ c ⊕ j ; c → ( a ⊕ b ⊕ k ; b → a ⊕ c ⊕ j ) c ) a : 2 1 i ⊕ 4 1 j ⊕ 4 1 k
Proving the runnability lemma
Here we prove Lemma 27, the runnability lemma. Recall the statement of the Lemma:
Runnability lemma: If Γ ⊢ M : τ \Gamma\vdash M : \tau Γ ⊢ M : τ and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) then μ M ∈ run ( τ ) \mu M \in\operatorname{run}(\tau) μ M ∈ run ( τ ) .
Proof. By induction on the typing derivation.
Variable:
Γ , x : τ ⊢ x : τ \frac{\Gamma, x : \tau\vdash x : \tau}{} Γ , x : τ ⊢ x : τ
By the definition of run ( Γ ) \operatorname{run}(\Gamma) run ( Γ ) we have μ x ∈ run ( τ ) \mu x \in\operatorname{run}(\tau) μx ∈ run ( τ ) .
Choice:
Γ ⊢ i : ε ⇒ ε ⋅ 1 i \frac{\Gamma\vdash i : \varepsilon\Rightarrow\varepsilon\cdot1_i}{} Γ ⊢ i : ε ⇒ ε ⋅ 1 i
Note that run ( ε ) = { ε } \operatorname{run}(\varepsilon) = \{\varepsilon\} run ( ε ) = { ε } and μ i = i \mu i = i μ i = i for any μ \mu μ . We have the evaluation ε , ε , i ⇓ ε , i \varepsilon,\varepsilon,i \Downarrow\varepsilon,i ε , ε , i ⇓ ε , i for the empty trace and the empty stack. Then for the frontier { ε } \{\varepsilon\} { ε } we have ε , i ⇓ { ( ε , i ) ε } \varepsilon,i \Downarrow\{(\varepsilon,i)_{\varepsilon}\} ε , i ⇓ {( ε , i ) ε } , with the singleton return family of ε \varepsilon ε and i i i for the empty trace. Since p ( ε ) = 1 p(\varepsilon) = 1 p ( ε ) = 1 it follows that { ( ε , i ) ε } ∈ run ( ε ⋅ 1 i ) \{(\varepsilon,i)_{\varepsilon}\} \in\operatorname{run}(\varepsilon\cdot1_i) {( ε , i ) ε } ∈ run ( ε ⋅ 1 i ) .
Zero
Γ ⊢ M : ε ⇒ 0 \frac{\Gamma\vdash M : \varepsilon\Rightarrow0}{} Γ ⊢ M : ε ⇒ 0
For any μ \mu μ we have ε , μ M ⇓ ∅ \varepsilon,\mu M \Downarrow\varnothing ε , μ M ⇓ ∅ . Vacuously, ∅ ∈ run ( 0 ) \varnothing\in\operatorname{run}(0) ∅ ∈ run ( 0 ) , since membership is defined by the quantification ∀ i ∈ ⌊ 0 ⌋ \forall i \in\lfloor0 \rfloor ∀ i ∈ ⌊ 0 ⌋ while the latter is empty.
Expand:
Γ ⊢ M : σ ‾ ⇒ δ ‾ Γ ⊢ M : σ ‾ ρ ‾ ⇒ ρ ‾ δ ‾ \frac{\Gamma\vdash M : \overline{\sigma} \Rightarrow\overline{\delta}}{\Gamma\vdash M : \overline{\sigma}\,\overline{\rho} \Rightarrow\overline{\rho}\,\overline{\delta}} Γ ⊢ M : σ ρ ⇒ ρ δ Γ ⊢ M : σ ⇒ δ
Let R ∈ run ( ρ ‾ ) R \in\operatorname{run}(\overline{\rho}) R ∈ run ( ρ ) , S ∈ run ( σ ‾ ) S \in\operatorname{run}(\overline{\sigma}) S ∈ run ( σ ) , and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) . The inductive hypothesis gives the evaluation S , μ M ⇓ T S,\mu M \Downarrow T S , μ M ⇓ T . For each ( T , i ) t ∈ T (T,i)_t \in T ( T , i ) t ∈ T we have the evaluation below left. By induction on the evaluation relation ⇓ \Downarrow ⇓ we get the evaluation below right.
t , S , μ M ⇓ T , i t , R S , μ M ⇓ R T , i t,S,\mu M \Downarrow T,i
\qquad
t,RS,\mu M \Downarrow RT,i t , S , μ M ⇓ T , i t , R S , μ M ⇓ R T , i
This gives R S , μ M ⇓ R T RS,\mu M \Downarrow RT R S , μ M ⇓ R T . Since R ∈ run ( ρ ‾ ) R \in\operatorname{run}(\overline{\rho}) R ∈ run ( ρ ) and stk ( T ∣ i ) ⊆ run ( τ i ‾ ) \operatorname{stk}(T\mathbin{|}i) \subseteq\operatorname{run}(\overline{\tau_i}) stk ( T ∣ i ) ⊆ run ( τ i ) , where τ i ‾ \overline{\tau_i} τ i is the type for i i i in δ ‾ \overline{\delta} δ , we have stk ( R T ∣ i ) ⊆ run ( ρ ‾ τ i ‾ ) \operatorname{stk}(RT\mathbin{|}i) \subseteq\operatorname{run}(\overline{\rho}\,\overline{\tau_i}) stk ( R T ∣ i ) ⊆ run ( ρ τ i ) . Since also pr ( R T ∣ i ) = pr ( T ∣ i ) ≥ p i \operatorname{pr}(RT\mathbin{|}i) = \operatorname{pr}(T\mathbin{|}i) \ge p_i pr ( R T ∣ i ) = pr ( T ∣ i ) ≥ p i we have R T ∈ run ( ρ ‾ δ ‾ ) RT \in\operatorname{run}(\overline{\rho}\,\overline{\delta}) R T ∈ run ( ρ δ ) . Push:
Γ ⊢ N : ρ Γ ⊢ M : ρ σ ‾ ⇒ δ Γ ⊢ [ N ] . M : σ ‾ ⇒ δ \frac{\Gamma\vdash N:\rho\qquad\Gamma\vdash M:\rho\overline{\sigma}\Rightarrow\delta}{\Gamma\vdash[N].M:\overline{\sigma}\Rightarrow\delta} Γ ⊢ [ N ] . M : σ ⇒ δ Γ ⊢ N : ρ Γ ⊢ M : ρ σ ⇒ δ
Let S ∈ run ( σ ‾ ) S \in\operatorname{run}(\overline{\sigma}) S ∈ run ( σ ) and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) . By induction we have μ N ∈ run ( ρ ) \mu N \in\operatorname{run}(\rho) μ N ∈ run ( ρ ) and μ M ∈ run ( ρ σ ‾ ⇒ δ ) \mu M \in\operatorname{run}(\rho\overline{\sigma}\Rightarrow\delta) μ M ∈ run ( ρ σ ⇒ δ ) , and for the latter the evaluation S , μ N , μ M ⇓ T S,\mu N,\mu M \Downarrow T S , μ N , μ M ⇓ T . Then for every ( T , i ) t ∈ T (T,i)t \in T ( T , i ) t ∈ T we have the evaluation below left, from which we construct the derivation below right.
t , S , μ N , μ M ⇓ T , i t,S,\mu N,\mu M \Downarrow T,i t , S , μ N , μ M ⇓ T , i
t , S , μ N , μ M ⇓ T , i t , S , μ ( [ N ] . M ) ⇓ T , i push \frac{t,S,\mu N,\mu M \Downarrow T,i}{t,S,\mu([N].M) \Downarrow T,i}\ \text{push} t , S , μ ([ N ] . M ) ⇓ T , i t , S , μ N , μ M ⇓ T , i push
Then S , μ ( [ N ] . M ) ⇓ T S,\mu([N].M) \Downarrow T S , μ ([ N ] . M ) ⇓ T and μ ( [ N ] . M ) ∈ run ( σ ‾ ⇒ δ ) \mu([N].M) \in\operatorname{run}(\overline{\sigma}\Rightarrow\delta) μ ([ N ] . M ) ∈ run ( σ ⇒ δ ) .
Pop:
Γ , x : ρ ⊢ M : σ ‾ ⇒ δ Γ ⊢ ⟨ x ⟩ . M : ρ σ ‾ ⇒ δ \frac{\Gamma,x:\rho\vdash M:\overline{\sigma}\Rightarrow\delta}{\Gamma\vdash\langle x\rangle.M:\rho\overline{\sigma}\Rightarrow\delta} Γ ⊢ ⟨ x ⟩ . M : ρ σ ⇒ δ Γ , x : ρ ⊢ M : σ ⇒ δ
Let S ∈ run ( σ ‾ ) S \in\operatorname{run}(\overline{\sigma}) S ∈ run ( σ ) , N ∈ run ( ρ ) N \in\operatorname{run}(\rho) N ∈ run ( ρ ) , and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) . Let μ ′ = μ { N / x } \mu'=\mu\{N/x\} μ ′ = μ { N / x } , the substitution map that sends x x x to N N N and every other variable y y y to μ y \mu y μ y , so that μ ′ ∈ run ( Γ , x : ρ ) \mu' \in\operatorname{run}(\Gamma,x:\rho) μ ′ ∈ run ( Γ , x : ρ ) . By induction we have S , μ ′ M ⇓ T S,\mu'M \Downarrow T S , μ ′ M ⇓ T , given by the evaluation below for every ( T , i ) t ∈ T (T,i)t \in T ( T , i ) t ∈ T , from which we construct the evaluation below right.
t , S , μ ′ M ⇓ T , i t,S,\mu'M \Downarrow T,i t , S , μ ′ M ⇓ T , i
t , S , μ ′ M ⇓ T , i t , S N , μ ( ⟨ x ⟩ . M ) ⇓ T , i pop \frac{t,S,\mu'M \Downarrow T,i}{t,SN,\mu(\langle x\rangle.M) \Downarrow T,i}\ \text{pop} t , S N , μ (⟨ x ⟩ . M ) ⇓ T , i t , S , μ ′ M ⇓ T , i pop
Then S N , μ ( ⟨ x ⟩ . M ) ⇓ T SN,\mu(\langle x\rangle.M) \Downarrow T S N , μ (⟨ x ⟩ . M ) ⇓ T and μ ( ⟨ x ⟩ . M ) ∈ run ( ρ σ ‾ ⇒ δ ) \mu(\langle x\rangle.M) \in\operatorname{run}(\rho\overline{\sigma}\Rightarrow\delta) μ (⟨ x ⟩ . M ) ∈ run ( ρ σ ⇒ δ ) .
Sample:
Γ , a : ε ⇒ ε ⋅ 1 ⊤ ⊢ M : ρ ‾ ⇒ γ Γ , a : ε ⇒ ε ⋅ 1 ⊥ ⊢ M : ρ ‾ ⇒ δ Γ ⊢ a . M : ρ ‾ ⇒ ( 1 2 ⋅ γ ) ⊔ ( 1 2 ⋅ δ ) \frac{\Gamma,a:\varepsilon\Rightarrow\varepsilon\cdot1^{\top}\vdash M:\overline{\rho}\Rightarrow\gamma\qquad\Gamma,a:\varepsilon\Rightarrow\varepsilon\cdot1^{\perp}\vdash M:\overline{\rho}\Rightarrow\delta}{\Gamma\vdash a.M:\overline{\rho}\Rightarrow\left(\frac{1}{2}\cdot\gamma\right)\sqcup\left(\frac{1}{2}\cdot\delta\right)} Γ ⊢ a . M : ρ ⇒ ( 2 1 ⋅ γ ) ⊔ ( 2 1 ⋅ δ ) Γ , a : ε ⇒ ε ⋅ 1 ⊤ ⊢ M : ρ ⇒ γ Γ , a : ε ⇒ ε ⋅ 1 ⊥ ⊢ M : ρ ⇒ δ
Let R ∈ run ( R ) R \in\operatorname{run}(R) R ∈ run ( R ) and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) . Define μ ⊤ = μ { ⊤ / a } \mu_{\top}=\mu\{\top/a\} μ ⊤ = μ { ⊤/ a } and μ ⊥ = μ { ⊥ / a } \mu_{\perp}=\mu\{\perp/a\} μ ⊥ = μ { ⊥ / a } so that μ ⊤ ∈ run ( Γ , a : ε ⇒ ε ⋅ 1 ⊤ ) \mu_{\top} \in\operatorname{run}(\Gamma,a:\varepsilon\Rightarrow\varepsilon\cdot1^{\top}) μ ⊤ ∈ run ( Γ , a : ε ⇒ ε ⋅ 1 ⊤ ) and μ ⊥ ∈ run ( Γ , a : ε ⇒ ε ⋅ 1 ⊥ ) \mu_{\perp} \in\operatorname{run}(\Gamma,a:\varepsilon\Rightarrow\varepsilon\cdot1^{\perp}) μ ⊥ ∈ run ( Γ , a : ε ⇒ ε ⋅ 1 ⊥ ) . By induction we have return families S S S and T T T where R , μ ⊤ M ⇓ S R,\mu_{\top}M \Downarrow S R , μ ⊤ M ⇓ S and R , μ ⊥ M ⇓ T R,\mu_{\perp}M \Downarrow T R , μ ⊥ M ⇓ T , given by the following evaluations for every ( S , i ) s ∈ S (S,i)s \in S ( S , i ) s ∈ S and ( T , j ) t ∈ T (T,j)t \in T ( T , j ) t ∈ T .
s , R , μ ⊤ M ⇓ S , i t , R , μ ⊥ M ⇓ T , j s,R,\mu_{\top}M \Downarrow S,i \qquad t,R,\mu_{\perp}M \Downarrow T,j s , R , μ ⊤ M ⇓ S , i t , R , μ ⊥ M ⇓ T , j
For these we have the following derivations.
s , R , μ ⊤ M ⇓ S , i ⊤ s , R , μ ( a . M ) ⇓ S , i smpl t , R , μ ⊥ M ⇓ T , j ⊥ t , R , μ ( a . M ) ⇓ T , j smpl \frac{s,R,\mu_{\top}M \Downarrow S,i}{\top\ s,R,\mu(a.M) \Downarrow S,i}\ \text{smpl}
\qquad
\frac{t,R,\mu_{\perp}M \Downarrow T,j}{\perp\ t,R,\mu(a.M) \Downarrow T,j}\ \text{smpl} ⊤ s , R , μ ( a . M ) ⇓ S , i s , R , μ ⊤ M ⇓ S , i smpl ⊥ t , R , μ ( a . M ) ⇓ T , j t , R , μ ⊥ M ⇓ T , j smpl
Then for U = ( ⊤ ⋅ S ) ∪ ( ⊥ ⋅ T ) U=(\top\cdot S)\cup(\perp\cdot T) U = ( ⊤ ⋅ S ) ∪ ( ⊥ ⋅ T ) we have S , μ ( a . M ) ⇓ U S,\mu(a.M) \Downarrow U S , μ ( a . M ) ⇓ U . It remains to show that U ∈ run ( 1 2 ⋅ γ ⊔ 1 2 ⋅ δ ) U \in\operatorname{run}\left(\frac{1}{2}\cdot\gamma\sqcup\frac{1}{2}\cdot\delta\right) U ∈ run ( 2 1 ⋅ γ ⊔ 2 1 ⋅ δ ) . For any indexed pair in 1 2 ⋅ γ ⊔ 1 2 ⋅ δ \frac{1}{2}\cdot\gamma\sqcup\frac{1}{2}\cdot\delta 2 1 ⋅ γ ⊔ 2 1 ⋅ δ , by the definition of ( ⊔ ) (\sqcup) ( ⊔ ) we have three cases.
( τ ‾ , 1 2 p + 1 2 q ) i \left(\overline{\tau},\frac{1}{2}p+\frac{1}{2}q\right)_i ( τ , 2 1 p + 2 1 q ) i where i ∈ ∣ γ ∣ ∩ ∣ δ ∣ i\in\lvert\gamma\rvert\cap\lvert\delta\rvert i ∈ ∣ γ ∣ ∩ ∣ δ ∣ , ( τ ‾ , p ) i ∈ γ (\overline{\tau},p)_i\in\gamma ( τ , p ) i ∈ γ and ( τ ‾ , q ) i ∈ δ (\overline{\tau},q)_i\in\delta ( τ , q ) i ∈ δ . Then since stk ( S ∣ i ) ⊆ run ( τ ‾ ) \operatorname{stk}(S|_i)\subseteq\operatorname{run}(\overline{\tau}) stk ( S ∣ i ) ⊆ run ( τ ) and stk ( T ∣ i ) ⊆ run ( τ ‾ ) \operatorname{stk}(T|_i)\subseteq\operatorname{run}(\overline{\tau}) stk ( T ∣ i ) ⊆ run ( τ ) we have stk ( U ∣ i ) ⊆ run ( τ ‾ ) \operatorname{stk}(U|_i)\subseteq\operatorname{run}(\overline{\tau}) stk ( U ∣ i ) ⊆ run ( τ ) , and since pr ( S ∣ i ) ≥ p \operatorname{pr}(S|_i)\geq p pr ( S ∣ i ) ≥ p and pr ( T ∣ i ) ≥ q \operatorname{pr}(T|_i)\geq q pr ( T ∣ i ) ≥ q we have pr ( U ∣ i ) = pr ( ⊤ ⋅ S ∣ i ) + pr ( ⊥ ⋅ T ∣ i ) ≥ 1 2 p + 1 2 q \operatorname{pr}(U|_i)=\operatorname{pr}(\top\cdot S|_i)+\operatorname{pr}(\perp\cdot T|_i)\geq\frac{1}{2}p+\frac{1}{2}q pr ( U ∣ i ) = pr ( ⊤ ⋅ S ∣ i ) + pr ( ⊥ ⋅ T ∣ i ) ≥ 2 1 p + 2 1 q .
( τ ‾ , 1 2 p ) i (\overline{\tau},\frac{1}{2}p)_i ( τ , 2 1 p ) i in 1 2 ⋅ γ ∖ ∣ δ ∣ \frac{1}{2}\cdot\gamma\setminus\lvert\delta\rvert 2 1 ⋅ γ ∖ ∣ δ ∣ . Since stk ( S ∣ i ) ⊆ run ( τ ‾ ) \operatorname{stk}(S|_i)\subseteq\operatorname{run}(\overline{\tau}) stk ( S ∣ i ) ⊆ run ( τ ) we have stk ( U ∣ i ) ⊆ run ( τ ‾ ) \operatorname{stk}(U|_i)\subseteq\operatorname{run}(\overline{\tau}) stk ( U ∣ i ) ⊆ run ( τ ) , and since pr ( S ∣ i ) ≥ p \operatorname{pr}(S|_i)\geq p pr ( S ∣ i ) ≥ p we have pr ( U ∣ i ) = pr ( ⊤ ⋅ S ∣ i ) ≥ 1 2 p \operatorname{pr}(U|_i)=\operatorname{pr}(\top\cdot S|_i)\geq\frac{1}{2}p pr ( U ∣ i ) = pr ( ⊤ ⋅ S ∣ i ) ≥ 2 1 p .
Γ ⊢ M : ρ ‾ ⇒ γ ‾ ⊕ σ ‾ ⋅ p i Γ ⊢ N : σ ‾ ⇒ δ ‾ Γ ⊢ M ; i → N : ρ ‾ ⇒ γ ‾ ⊔ p ⋅ δ ‾ \frac{\Gamma\vdash M : \overline{\rho} \Rightarrow\overline{\gamma} \oplus\overline{\sigma} \cdot p_i \qquad\Gamma\vdash N : \overline{\sigma} \Rightarrow\overline{\delta}}{\Gamma\vdash M ;_{i \to} N : \overline{\rho} \Rightarrow\overline{\gamma} \sqcup p \cdot\overline{\delta}} Γ ⊢ M ; i → N : ρ ⇒ γ ⊔ p ⋅ δ Γ ⊢ M : ρ ⇒ γ ⊕ σ ⋅ p i Γ ⊢ N : σ ⇒ δ
Let R ∈ run ( ρ ‾ ) R \in\operatorname{run}(\overline{\rho}) R ∈ run ( ρ ) and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) . By induction we have μ M ∈ run ( ρ ‾ ⇒ γ ‾ ⊕ σ ‾ ⋅ p i ) \mu M \in\operatorname{run}(\overline{\rho} \Rightarrow\overline{\gamma} \oplus\overline{\sigma} \cdot p_i) μ M ∈ run ( ρ ⇒ γ ⊕ σ ⋅ p i ) and R , μ M ⇓ S R, \mu M \Downarrow S R , μ M ⇓ S . Let this be given by an evaluation for each ( S , j ) s ∈ S (S,j)_s \in S ( S , j ) s ∈ S of the form below left. For each ( S , j ) s (S,j)_s ( S , j ) s where j = i j = i j = i we have S ∈ run ( σ ‾ ) S \in\operatorname{run}(\overline{\sigma}) S ∈ run ( σ ) , and by induction on N N N a return family T s T_s T s such that S , μ N ⇓ T s S, \mu N \Downarrow T_s S , μ N ⇓ T s . Let this be given by the evaluation below right for each ( T , k ) t ∈ T s (T,k)_t \in T_s ( T , k ) t ∈ T s .
s , R , μ M ⇓ S , j t , S , μ N ⇓ T , k s, R, \mu M \Downarrow S,j \qquad t,S,\mu N \Downarrow T,k s , R , μ M ⇓ S , j t , S , μ N ⇓ T , k
For each ( S , j ) s (S,j)_s ( S , j ) s , if j ≠ i j \ne i j = i we construct the derivation below left, and if j = i j = i j = i then for each ( T , k ) t ∈ T s (T,k)_t \in T_s ( T , k ) t ∈ T s we construct that below right.
s , R , μ M ⇓ S , j s , R , μ ( M ; i → N ) ⇓ S , j \frac{s,R,\mu M \Downarrow S,j}{s,R,\mu(M ;_{i \to} N) \Downarrow S,j} s , R , μ ( M ; i → N ) ⇓ S , j s , R , μ M ⇓ S , j
s , R , μ M ⇓ S , j t , S , μ N ⇓ T , k s t , R , μ ( M ; i → N ) ⇓ T , k \frac{s,R,\mu M \Downarrow S,j \qquad t,S,\mu N \Downarrow T,k}{st,R,\mu(M ;_{i \to} N) \Downarrow T,k} s t , R , μ ( M ; i → N ) ⇓ T , k s , R , μ M ⇓ S , j t , S , μ N ⇓ T , k
Then we have R , μ ( M ; i → N ) ⇓ T R,\mu(M ;_{i \to} N) \Downarrow T R , μ ( M ; i → N ) ⇓ T where T T T is given as follows.
T = ( S ∖ i ) ∪ ⋃ s ∈ ⌊ S ∣ i ⌋ s ⋅ T s T = (S \setminus i) \cup\bigcup_{s \in\lfloor S \mid i \rfloor} s \cdot T_s T = ( S ∖ i ) ∪ s ∈ ⌊ S ∣ i ⌋ ⋃ s ⋅ T s
It remains to show that T ∈ run ( γ ‾ ⊔ p ⋅ δ ‾ ) T \in\operatorname{run}(\overline{\gamma} \sqcup p \cdot\overline{\delta}) T ∈ run ( γ ⊔ p ⋅ δ ) .
First, for the return types, for all j ∈ ⌊ γ ⌋ ∪ ⌊ δ ⌋ j \in\lfloor\gamma\rfloor\cup\lfloor\delta\rfloor j ∈ ⌊ γ ⌋ ∪ ⌊ δ ⌋ we need that stk ( T ∣ j ) ⊆ run ( τ ‾ ) \operatorname{stk}(T \mid j) \subseteq\operatorname{run}(\overline{\tau}) stk ( T ∣ j ) ⊆ run ( τ ) where τ ‾ \overline{\tau} τ is the type for j j j in γ \gamma γ and δ \delta δ (the definition of ( ⊔ ) (\sqcup) ( ⊔ ) requires that they agree). By definition any indexed pair in T T T is either ( S , j ) s ∈ S ∖ i (S,j)_s \in S \setminus i ( S , j ) s ∈ S ∖ i or ( T , k ) t ∈ T s (T,k)_t \in T_s ( T , k ) t ∈ T s . The former case follows since S ∈ run ( γ ) S \in\operatorname{run}(\gamma) S ∈ run ( γ ) and so stk ( S ∣ j ) ⊆ run ( τ ‾ ) \operatorname{stk}(S \mid j) \subseteq\operatorname{run}(\overline{\tau}) stk ( S ∣ j ) ⊆ run ( τ ) and S ⊆ run ( τ ‾ ) S \subseteq\operatorname{run}(\overline{\tau}) S ⊆ run ( τ ) . The latter case follows since T s ∈ run ( δ ) T_s \in\operatorname{run}(\delta) T s ∈ run ( δ ) , so that stk ( S ∣ j ) ⊆ run ( τ ‾ ) \operatorname{stk}(S \mid j) \subseteq\operatorname{run}(\overline{\tau}) stk ( S ∣ j ) ⊆ run ( τ ) and T ∈ run ( τ ‾ ) T \in\operatorname{run}(\overline{\tau}) T ∈ run ( τ ) .
Second, for the probabilities, for all j ∈ ⌊ γ ⌋ ∪ ⌊ δ ⌋ j \in\lfloor\gamma\rfloor\cup\lfloor\delta\rfloor j ∈ ⌊ γ ⌋ ∪ ⌊ δ ⌋ it must be shown that pr ( T ∣ j ) ≥ p j + p q j \operatorname{pr}(T \mid j) \ge p_j + p q_j pr ( T ∣ j ) ≥ p j + p q j where p j p_j p j is the probability of j j j in γ \gamma γ and q j q_j q j that in δ \delta δ . We compute as follows.
pr ( T ∣ j ) = pr ( ( ( S ∖ i ) ∪ ⋃ s ∈ ⌊ S ∣ i ⌋ s ⋅ T s ) ∣ j ) = pr ( ( S ∖ i ) ∣ j ) + ∑ s ∈ ⌊ S ∣ i ⌋ ( pr ( s ) × pr ( T s ∣ j ) ) ≥ p j + ∑ s ∈ ⌊ S ∣ i ⌋ ( pr ( s ) × q j ) ≥ p j + p q j \begin{aligned}
\operatorname{pr}(T \mid j) &= \operatorname{pr}\left(((S \setminus i) \cup\bigcup_{s \in\lfloor S \mid i \rfloor} s \cdot T_s) \mid j\right) \\
&= \operatorname{pr}((S \setminus i) \mid j) + \sum_{s \in\lfloor S \mid i \rfloor} \left(\operatorname{pr}(s) \times\operatorname{pr}(T_s \mid j)\right) \\
&\ge p_j + \sum_{s \in\lfloor S \mid i \rfloor} \left(\operatorname{pr}(s) \times q_j\right) \\
&\ge p_j + p q_j
\end{aligned} pr ( T ∣ j ) = pr (( S ∖ i ) ∪ s ∈ ⌊ S ∣ i ⌋ ⋃ s ⋅ T s ) ∣ j = pr (( S ∖ i ) ∣ j ) + s ∈ ⌊ S ∣ i ⌋ ∑ ( pr ( s ) × pr ( T s ∣ j ) ) ≥ p j + s ∈ ⌊ S ∣ i ⌋ ∑ ( pr ( s ) × q j ) ≥ p j + p q j
For the third step (the first inequality), since S ∖ i ∈ run ( γ ) S \setminus i \in\operatorname{run}(\gamma) S ∖ i ∈ run ( γ ) we have pr ( S ∣ j ) ≥ p j \operatorname{pr}(S \mid j) \ge p_j pr ( S ∣ j ) ≥ p j for all j ∈ ⌊ γ ⌋ j \in\lfloor\gamma\rfloor j ∈ ⌊ γ ⌋ . For the last step, since T s ∈ run ( δ ) T_s \in\operatorname{run}(\delta) T s ∈ run ( δ ) for all s s s we have pr ( T s ∣ j ) ≥ q j \operatorname{pr}(T_s \mid j) \ge q_j pr ( T s ∣ j ) ≥ q j for all j ∈ ⌊ δ ⌋ j \in\lfloor\delta\rfloor j ∈ ⌊ δ ⌋ . Then since S ∣ i ∈ run ( σ ‾ ⋅ p i ) S \mid i \in\operatorname{run}(\overline{\sigma} \cdot p_i) S ∣ i ∈ run ( σ ⋅ p i ) we have pr ( S ∣ i ) ≥ p \operatorname{pr}(S \mid i) \ge p pr ( S ∣ i ) ≥ p .
It follows that T ∈ run ( γ ‾ ⊔ p ⋅ δ ‾ ) T \in\operatorname{run}(\overline{\gamma} \sqcup p \cdot\overline{\delta}) T ∈ run ( γ ⊔ p ⋅ δ ) and hence μ ( M ; i → N ) ∈ run ( ρ ‾ ⇒ γ ‾ ⊔ p ⋅ δ ‾ ) \mu(M ;_{i \to} N) \in\operatorname{run}(\overline{\rho} \Rightarrow\overline{\gamma} \sqcup p \cdot\overline{\delta}) μ ( M ; i → N ) ∈ run ( ρ ⇒ γ ⊔ p ⋅ δ ) .
Γ ⊢ M : σ ‾ ⇒ δ ‾ + σ ‾ ⋅ p i ( p ≠ 1 ) Γ ⊢ M i : σ ‾ ⇒ 1 1 − p ⋅ δ ‾ \frac{\Gamma\vdash M : \overline{\sigma} \Rightarrow\overline{\delta} + \overline{\sigma} \cdot p_i \qquad(p \ne1)}{\Gamma\vdash M^i : \overline{\sigma} \Rightarrow\frac{1}{1-p} \cdot\overline{\delta}} Γ ⊢ M i : σ ⇒ 1 − p 1 ⋅ δ Γ ⊢ M : σ ⇒ δ + σ ⋅ p i ( p = 1 )
Let S ∈ run ( σ ‾ ) S \in\operatorname{run}(\overline{\sigma}) S ∈ run ( σ ) and μ ∈ run ( Γ ) \mu\in\operatorname{run}(\Gamma) μ ∈ run ( Γ ) . We construct a series of return families T n T_n T n for all n ∈ N + n \in\mathbb{N}^{+} n ∈ N + by induction on n n n , and show the following.
T n ∈ run ( ( q n ⋅ δ ‾ ) + σ ‾ ⋅ p i n ) where q n = 1 + p + p 2 + p 3 + ⋯ + p n − 1 T_n \in\operatorname{run}((q_n \cdot\overline{\delta}) + \overline{\sigma} \cdot p^n_i) \quad\text{where} \quad q_n = 1 + p + p^2 + p^3 + \cdots+ p^{n-1} T n ∈ run (( q n ⋅ δ ) + σ ⋅ p i n ) where q n = 1 + p + p 2 + p 3 + ⋯ + p n − 1
The case T 1 \mathcal{T}_1 T 1 is given by induction on M M M by S , μ M ⇓ T 1 S,\mu M\Downarrow\mathcal{T}_1 S , μ M ⇓ T 1 .
For the case T n + 1 \mathcal{T}_{n+1} T n + 1 , for each ( R , i ) r ∈ T n (R,i)_r\in\mathcal{T}_n ( R , i ) r ∈ T n , by induction on M M M let R , μ M ⇓ T r R,\mu M\Downarrow\mathcal{T}_r R , μ M ⇓ T r and define T n + 1 \mathcal{T}_{n+1} T n + 1 as follows.
T n + 1 = ( T n ∖ i ) ∪ ⋃ r ∈ ⌈ T n ∣ i ⌋ r ⋅ T r \mathcal{T}_{n+1}=(\mathcal{T}_n\setminus i)\cup\bigcup_{r\in\lceil\mathcal{T}_n\mid i\rfloor}r\cdot\mathcal{T}_r T n + 1 = ( T n ∖ i ) ∪ r ∈ ⌈ T n ∣ i ⌋ ⋃ r ⋅ T r
By induction we have T n ∈ run ( q n ⋅ δ + σ ‾ ⋅ p n i ) \mathcal{T}_n\in\operatorname{run}(q_n\cdot\delta+\overline{\sigma}\cdot p^{n}i) T n ∈ run ( q n ⋅ δ + σ ⋅ p n i ) . By similar reasoning to the previous sequencing case we have the following.
T n + 1 ∈ run ( q n ⋅ δ + p n ⋅ ( δ + σ ‾ ⋅ p i ) ) = run ( q n + 1 ⋅ δ + σ ‾ ⋅ p n + 1 i ) \mathcal{T}_{n+1}\in\operatorname{run}(q_n\cdot\delta+p^n\cdot(\delta+\overline{\sigma}\cdot p_i))=\operatorname{run}(q_{n+1}\cdot\delta+\overline{\sigma}\cdot p^{n+1}i) T n + 1 ∈ run ( q n ⋅ δ + p n ⋅ ( δ + σ ⋅ p i )) = run ( q n + 1 ⋅ δ + σ ⋅ p n + 1 i )
Observe that by definition T n ∖ i ⊆ T n + 1 ∖ i \mathcal{T}_n\setminus i\subseteq\mathcal{T}_{n+1}\setminus i T n ∖ i ⊆ T n + 1 ∖ i . Then we define T \mathcal{T} T as the following supremum.
T = sup n ∈ N + T n ∖ i \mathcal{T}=\sup_{n\in\mathbb{N}^{+}}\mathcal{T}_n\setminus i T = n ∈ N + sup T n ∖ i
It remains to show that S , μ ( M i ) ⇓ T S,\mu(M^i)\Downarrow\mathcal{T} S , μ ( M i ) ⇓ T and T ∈ run ( 1 1 − p ⋅ δ ) \mathcal{T}\in\operatorname{run}\left(\frac{1}{1-p}\cdot\delta\right) T ∈ run ( 1 − p 1 ⋅ δ ) .
If ( T , j ) t ∈ T (T,j)_t\in\mathcal{T} ( T , j ) t ∈ T , then by definition ( T , j ) t ∈ T n ∖ i (T,j)_t\in\mathcal{T}_n\setminus i ( T , j ) t ∈ T n ∖ i for some n n n . Assume this is the least such n n n . Then by induction, going backwards from n n n , we give a sequence of stacks S m S_m S m and traces s m s_m s m and t m t_m t m for all m < n m<n m < n such that S 0 = S S_0=S S 0 = S , s 0 = ε s_0=\varepsilon s 0 = ε , s m t m = t s_mt_m=t s m t m = t , and t m , S m , μ ( M i ) ⇓ T , j t_m,S_m,\mu(M^i)\Downarrow T,j t m , S m , μ ( M i ) ⇓ T , j , and ( S m , i ) s m ∈ T m (S_m,i)_{s_m}\in\mathcal{T}_m ( S m , i ) s m ∈ T m for $m\ne0.
For the case m = n − 1 m=n-1 m = n − 1 , since ( T , j ) t ∈ T n (T,j)_t\in\mathcal{T}_n ( T , j ) t ∈ T n , by definition it is either in T n − 1 ∖ i \mathcal{T}_{n-1}\setminus i T n − 1 ∖ i , which is ruled out by assumption, or it is given by an evaluation R , μ M ⇓ T r R,\mu M\Downarrow T_r R , μ M ⇓ T r with R = S R=S R = S if n = 1 n=1 n = 1 , and otherwise ( R , i ) s ∈ T n − 1 (R,i)_s\in\mathcal{T}_{n-1} ( R , i ) s ∈ T n − 1 and t = s r t=sr t = sr , with the evaluation below left. Let S n − 1 = R S_{n-1}=R S n − 1 = R , s n − 1 = s s_{n-1}=s s n − 1 = s , and t n − 1 = r t_{n-1}=r t n − 1 = r . Since i ≠ j i\ne j i = j , this gives the derivation below right.
r , R , μ M ⇓ T , j t n − 1 , S n − 1 , μ ( M i ) ⇓ T , j r , R , μ M ⇓ T , j t n − 1 , S n − 1 , μ ( M i ) ⇓ T , j e x i t \frac{r,R,\mu M\Downarrow T,j}{t_{n-1},S_{n-1},\mu(M^i)\Downarrow T,j}\mathop{\vphantom{\frac{r,R,\mu M\Downarrow T,j}{t_{n-1},S_{n-1},\mu(M^i)\Downarrow T,j}}}_{\mathrm{exit}} t n − 1 , S n − 1 , μ ( M i ) ⇓ T , j r , R , μ M ⇓ T , j t n − 1 , S n − 1 , μ ( M i ) ⇓ T , j r , R , μ M ⇓ T , j exit
For the cases 0 < m < n 0<m<n 0 < m < n , by induction let ( S m , i ) s m ∈ T m (S_m,i)_{s_m}\in\mathcal{T}_m ( S m , i ) s m ∈ T m with t = s m t m t=s_mt_m t = s m t m and the evaluation below left. By the definition of T m \mathcal{T}_m T m , ( S m , i ) s m (S_m,i)_{s_m} ( S m , i ) s m is given by an evaluation R , μ M ⇓ S m , i R,\mu M\Downarrow S_m,i R , μ M ⇓ S m , i with R = S R=S R = S if m = 1 m=1 m = 1 and otherwise ( R , i ) s ∈ T m − 1 (R,i)_s\in\mathcal{T}_{m-1} ( R , i ) s ∈ T m − 1 with s m = s r s_m=sr s m = sr , giving the evaluation below right.
t m , S m , μ ( M i ) ⇓ T , j r , R , μ M ⇓ S m , i t_m,S_m,\mu(M^i)\Downarrow T,j
\qquad
r,R,\mu M\Downarrow S_m,i t m , S m , μ ( M i ) ⇓ T , j r , R , μ M ⇓ S m , i
To show the statement for m − 1 m-1 m − 1 , let S m − 1 = R S_{m-1}=R S m − 1 = R , s m − 1 = s s_{m-1}=s s m − 1 = s , and t m = r t m − 1 t_m=rt_{m-1} t m = r t m − 1 , and construct the derivation below.
s m − 1 , S m − 1 , μ M ⇓ S m , i t m , S m , μ ( M i ) ⇓ T , j t m − 1 , S m − 1 , μ ( M i ) ⇓ T , j s m − 1 , S m − 1 , μ M ⇓ S m , i t m , S m , μ ( M i ) ⇓ T , j t m − 1 , S m − 1 , μ ( M i ) ⇓ T , j l o o p \frac{s_{m-1},S_{m-1},\mu M\Downarrow S_m,i\qquad t_m,S_m,\mu(M^i)\Downarrow T,j}{t_{m-1},S_{m-1},\mu(M^i)\Downarrow T,j}\mathop{\vphantom{\frac{s_{m-1},S_{m-1},\mu M\Downarrow S_m,i\qquad t_m,S_m,\mu(M^i)\Downarrow T,j}{t_{m-1},S_{m-1},\mu(M^i)\Downarrow T,j}}}_{\mathrm{loop}} t m − 1 , S m − 1 , μ ( M i ) ⇓ T , j s m − 1 , S m − 1 , μ M ⇓ S m , i t m , S m , μ ( M i ) ⇓ T , j t m − 1 , S m − 1 , μ ( M i ) ⇓ T , j s m − 1 , S m − 1 , μ M ⇓ S m , i t m , S m , μ ( M i ) ⇓ T , j loop
It follows that for every ( T , j ) t ∈ T (T,j)_t\in\mathcal{T} ( T , j ) t ∈ T there is an evaluation t , S , μ ( M i ) ⇓ T t , j t t,S,\mu(M^i)\Downarrow T_t,j_t t , S , μ ( M i ) ⇓ T t , j t , and hence S , μ ( M i ) ⇓ T S,\mu(M^i)\Downarrow\mathcal{T} S , μ ( M i ) ⇓ T .
For all n ∈ N + n\in\mathbb{N}^{+} n ∈ N + we have T n ∈ run ( q n ⋅ δ + σ ‾ ⋅ p n i ) \mathcal{T}_n\in\operatorname{run}(q_n\cdot\delta+\overline{\sigma}\cdot p^ni) T n ∈ run ( q n ⋅ δ + σ ⋅ p n i ) and hence T n ∖ i ∈ run ( q n ⋅ δ ) \mathcal{T}_n\setminus i\in\operatorname{run}(q_n\cdot\delta) T n ∖ i ∈ run ( q n ⋅ δ ) . Since each T T T in stk ( T ∣ j ) \operatorname{stk}(T\mid j) stk ( T ∣ j ) is in some stk ( T ∣ j ) \operatorname{stk}(\mathcal{T}\mid j) stk ( T ∣ j ) we have T ∈ run ( τ ‾ ) T\in\operatorname{run}(\overline{\tau}) T ∈ run ( τ ) where τ ‾ \overline{\tau} τ is the stack for j j j in δ \delta δ . Next, for j ≠ i j\ne i j = i we have pr ( T ∣ j ) ≥ q n p j \operatorname{pr}(T\mid j)\ge q_np_j pr ( T ∣ j ) ≥ q n p j where q n = 1 + p + p 2 + ⋯ + p n − 1 q_n=1+p+p^2+\cdots+p^{n-1} q n = 1 + p + p 2 + ⋯ + p n − 1 and p j p_j p j is the probability for j j j in δ \delta δ . This gives the following.
pr ( T ∣ j ) ≥ ( 1 + p + p 2 + p 3 … ) × p j = 1 1 − p p j \operatorname{pr}(T\mid j)\ge(1+p+p^2+p^3\ldots)\times p_j=\frac{1}{1-p}p_j pr ( T ∣ j ) ≥ ( 1 + p + p 2 + p 3 … ) × p j = 1 − p 1 p j
It follows that T ∈ run ( 1 1 − p ⋅ δ ) \mathcal{T}\in\operatorname{run}\left(\frac{1}{1-p}\cdot\delta\right) T ∈ run ( 1 − p 1 ⋅ δ ) and hence μ ( M i ) ∈ run ( σ ‾ ⇒ 1 1 − p ⋅ δ ) \mu(M^i)\in\operatorname{run}\left(\overline{\sigma}\Rightarrow\frac{1}{1-p}\cdot\delta\right) μ ( M i ) ∈ run ( σ ⇒ 1 − p 1 ⋅ δ ) .