Skip to the Main Content

Note:These pages make extensive use of the latest XHTML and CSS Standards. They ought to look great in any standards-compliant modern browser. Unfortunately, they will probably look horrible in older browsers, like Netscape 4.x and IE 4.x. Moreover, many posts use MathML, which is, currently only supported in Mozilla. My best suggestion (and you will thank me when surfing an ever-increasing number of sites on the web which have been crafted to use the new standards) is to upgrade to the latest version of your browser. If that's not possible, consider moving to the Standards-compliant and open-source Mozilla browser.

March 29, 2021

Native Type Theory (Part 3)

Posted by John Baez

guest post by Christian Williams

We are continuing Native Type Theory. We described higher-order algebraic theories, categories with products and finite-order exponents, which present languages with (binding) operations, equations, and rewrites; from these we construct native type systems.

Now we use the wisdom of the Yoneda embedding.

Every category embeds into a topos of presheaves

y:C𝒫C=[C op,Set]y\colon C\rightarrowtail \mathscr{P}C=[C^{op},Set]

y(c)=C(,c)y(f)=C(,f):C(,c)C(,d).y(c) = C(-,c) \quad\quad y(f)=C(-,f)\colon C(-,c)\to C(-,d).

If (C,,[,])(C,\otimes,[-,-]) is monoidal closed, then the embedding preserves this structure:

y(cd)y(c)y(d)y([c,d])[y(c),y(d)]y(c\otimes d)\simeq y(c)\otimes y(d) \quad \quad y([c,d])\simeq [y(c),y(d)]

i.e. using Day convolution, yy is monoidal closed. So, we can move into a richer environment while preserving higher-order algebraic structure, or languages.

We now explore the native type system of a language, using the ρ\rho-calculus as our running example. The complete type system is in the paper, page 9.

Representables

The simplest kind of object of the native type system is a representable T(,S)T(-,\mathtt{S}). This is the set of all terms of sort S\mathtt{S}, indexed by the context of the language. Whereas many works in computer science either restrict to closed terms or lump all terms together, this indexing is natural and useful.

In the ρ\rho-calculus, y(P)=T ρ(,P)y(\mathtt{P}) = T_\rho(-,\mathtt{P}) is the indexed set of all processes.

y(P)(Γ)={p|(x 1,,x n):Γp:P}.y(\mathtt{P})(\Gamma) = \{p \;|\; (x_1,\dots,x_n):\Gamma \vdash p:\mathtt{P}\}.

The type system is built from these basic objects by the operations of TT and the structure of 𝒫T\mathscr{P}T. We can then construct predicates, dependent types, co/limits, etc., and each constructor has corresponding inference rules which can be used by a computer.

Predicates and Types

The language of a topos is represented by two fibrations: the subobject fibration gives predicate logic, and the codomain fibration gives dependent type theory. Hence the two basic entities are predicates and (dependent) types. Types are more general, and we can think of them as the “new sorts” of language TT, which can be much more expressive.

A predicate φ:y(P)Ω\varphi:y(\mathtt{P})\to \Omega corresponds to a subobject of a representable {p|φ(p)}y(P)\{p \;|\; \varphi(p)\}\rightarrowtail y(\mathtt{P}), which is equivalent to a sieve: a set of morphisms into P\mathtt{P}, closed under precomposition:

This emphasizes the idea that predicate logic over representables is actually reasoning about abstract syntax trees: here gg is some tree of operations in TT with an S\mathtt{S}-shaped hole of variables, and the predicate φ\varphi only cares about the outer shape of gg; you can plug in any term ff while still satisfying φ\varphi.

More generally, a morphism f:BAf\colon B\to A is understood as an “indexed presheaf” or dependent type

x:AB(x):Type.x:A\vdash B(x):Type.

i.e. for every element x:XAx\colon X\to A, there is a fiber B(x):=f *(x)B(x):= f^*(x) which is the “type depending on term xx”.

An example of a type in the ρ\rho-calculus is given by the input operation,

y(in):y(N×P×[N,P])y(P)y(\mathtt{in}):y(\mathtt{N\times P\times [N,P]})\to y(\mathtt{P})

where the fiber over φ\varphi is the set of all channel-context pairs (n,λx.p)(n,\lambda x.p) such that φ(in(n,λx.p))\varphi(\mathtt{in}(n,\lambda x.p)).

Dependent Sum and Product

Here we use the structure described in Part I. The predicate functor 𝒫T(,Ω):𝒫T opCHA\mathscr{P}T(-,\Omega):\mathscr{P}T^{op}\to CHA is a hyperdoctrine, which for each presheaf AA gives a complete Heyting algebra of predicates Ω A\Omega^A, and for each f:BAf\colon B\to A gives adjoints fΩ f f:Ω BΩ A\exists_f\dashv \Omega^f\dashv \forall_f\colon \Omega^B\to \Omega^A for image, preimage, and secure image.

Similarly, the slice functor 𝒫T/:𝒫T opCCT\mathscr{P}T/-:\mathscr{P}T^{op} \to CCT is a hyperdoctrine into co/complete toposes with adjoints Σ fΔ fΠ f\Sigma_f\dashv \Delta^f\dashv \Pi_f. These are dependent sum, substitution, and dependent product. From these we can reconstruct all the operations of predicate logic, and much more.

As (briefly) explained in Part I, the idea of dependent sum is that indexed sums generalize products; here the codomain is the set of indices and its fibers are the sets in the family; so an element of the indexed sum is a dependent pair (a,xX a)(a,x\in X_a). Dually, indexed products generalize functions: an element of the product of the fibers is a tuple (x 1X a 1,,x nX a n)(x_1\in X_{a_1},\dots,x_n\in X_{a_n}) which can be understood as a dependent function where the codomain X aX_a depends on which aa you plug in.

Explicitly, given f:ABf\colon A\to B and p:XAp\colon X\to A, q:YBq\colon Y\to B, we have Δ f(q) S a=q S f S(a)\Delta_f(q)_\mathtt{S}^a = q_\mathtt{S}^{f_\mathtt{S}(a)} and

(1)Σ f(p) S b := a:A S f S(a)=bp S a Π f(p) S b := u:RS f R(a)=B(u)(b)p R a\begin{array}{ll} \Sigma_f(p)_\mathtt{S}^b & := \sum_{a:A_\mathtt{S}}\sum_{f_\mathtt{S}(a)=b} p_\mathtt{S}^{a} \\ \Pi_f(p)_\mathtt{S}^b & := \prod_{u:\mathtt{R}\to \mathtt{S}}\prod_{f_\mathtt{R}(a)=B(u)(b)} p_\mathtt{R}^{a} \end{array}

(letting X S=X(S)X_\mathtt{S}=X(\mathtt{S}) and p S bp_\mathtt{S}^b denote the fiber over bb). Despite the complex formulae, the intuition is essentially the same as in Set, except we need to ensure the resulting objects are still presheaves, i.e. closed under precomposition. The point is:

Σgeneralizes product, and categorifies or image; and \Sigma \;\; \text{generalizes product, and categorifies } \;\; \exists \;\; \text{ or image; and}

Πgeneralizes internal hom, and categorifies or secure image. \Pi \;\; \text{generalizes internal hom, and categorifies } \;\; \forall \;\; \text{ or secure image.}

The main examples start with just “pushing forward” operations in the theory, using \exists. Given an operation f:STf\colon \mathtt{S}\to \mathtt{T}, the image y(f):Ω y(S)Ω y(T)\exists_{y(f)}:\Omega^{y(\mathtt{S})}\to \Omega^{y(\mathtt{T})} takes a predicate (sieve) φy(S)\varphi\rightarrowtail y(\mathtt{S}) and simply postcomposes every term in φ\varphi with ff.

Hence an example predicate (leaving \exists and yy implicit) is

multi.thread=¬(0)|¬(0)y(P).\mathsf{multi.thread} = \neg(0)\vert \neg(0) \;\; \rightarrowtail y(\mathtt{P}).

This predicate determines processes which are the parallel of two non-null processes.

As an example of the distinct utility of the adjoints, recall from Part 2 that we can model computational dynamics using a graph of processes and rewrites s,t:EPs,t:\mathtt{E\to P}. Now these operations give adjunctions between sieves on E\mathtt{E} and sieves on P\mathtt{P}, which give operators for “step forward or backward”:

Σ tΩ s(φ)={q|r.r:pqφ(p)}\Sigma_t\Omega^s(\varphi) = \{q \;|\; \exists r.\; r:p\rightsquigarrow q \wedge \varphi(p)\}

Π t(Ω s(φ))={q|r.r:pqφ(p)}\Pi_t(\Omega^s(\varphi)) = \{q \;|\; \forall r.\; r:p\rightsquigarrow q \Rightarrow \varphi(p)\}

While “image” step-forward gives all possible next terms, the “secure” step-forward gives terms which could only have come from φ\varphi. For security protocols, this can be used to filter processes by past behavior.

Image / Comprehension and Subtyping

Predicates and types are related by an adjunction between the fibrations.

To convert a predicate φ:AΩ\varphi:A\to \Omega to a type, apply comprehension to construct the subobject of terms c(φ)\mathrm{c}(\varphi) which satisfy φ\varphi. To convert a type p:XAp:X\to A to a predicate, apply image factorization to construct the predicate i(p)\mathrm{i}(p) for whether each fiber is inhabited.

We implicitly use the comprehension direction all the time (thinking of predicates as their subobjects); and while taking the image is more destructive, it can certainly be useful for the sake of simplification. For example, rather than thinking about the type y(out):y(N×P)y(P)y(\mathtt{out}):y(\mathtt{N\times P})\to y(\mathtt{P}), we may simply want to consider the image i(y(out))\mathrm{i}(y(\mathtt{out})), the set of all output processes.

Internal Hom and Reification

While the Grothendieck construction is relatively known, there is less awareness about how the local structure of an indexed category (complete Heyting algebras for predicates) can often be converted to a global structure on the total category of the corresponding fibration. The total category of the predicate functor Ω𝒫T\Omega\mathscr{P}T is cartesian closed, allowing us to construct predicate homs.

The construction can be understood in the category of sets. Given φ:2 A\varphi:2^A and ψ:2 B\psi:2^B, we can define

[φ,ψ]:[A,B]2[φ,ψ](f)=aA.φ(a)ψ(f(a)).[\varphi,\psi]:[A,B]\to 2 \quad \quad [\varphi, \psi](f) = \forall a\in A.\; \varphi(a)\Rightarrow \psi(f(a)).

Hence it constructs “contexts which ensure implications”.

For example, we can construct the “wand” of separation logic: let T hT_h be the theory of a commutative monoid (H,,e)(H,\cup,e), with a set of constants {h}:1H\{h\}:1\to H adjoined as the elements of a heap. If we define

(φψ)=Ω λx.x[φ,ψ](\varphi \multimap \psi) = \Omega^{\lambda x.x\cup-}[\varphi, \psi]

then h 1:(φψ)h_1:(\varphi \multimap \psi) asserts that h 2:φh 1h 2:ψh_2:\varphi\Rightarrow h_1\cup h_2:\psi.

There is a much more expressive way of forming homs which we call reification (p7); we do not know if it has been explored, and we have yet to determine its relation to dependent product.

co/Induction

Similarly, the fibers of Ω𝒫T𝒫T\Omega\mathscr{P}T\to \mathscr{P}T are co/complete, and this can be assembled into a global co/complete structure on the total category. Hence, we can use this to construct co/inductive types.

For example, given a predicate on names α\alpha, we may construct a predicate for “liveness and safety” on α\alpha:

sole.in(α)=μX.in(α,N.X)¬in(¬α,N.P)\mathsf{sole.in}(\alpha) = \mu X. \mathtt{in}(\alpha,\mathtt{N}.X)\wedge \neg\mathtt{in}(\neg\alpha,\mathtt{N.P})

where μ\mu denotes the initial algebra, which is constructed as a colimit. This determines whether a process inputs on α\alpha, does not input on ¬α\neg\alpha, and continues as a process which satisfies this same predicate. This can be understood as a static type for a firewall.

Applications

Once these type constructors are combined, they can express highly useful and complex ideas about code. The best part is that this type system can be generated from any language with product and function types, which includes large chunks of many popular programming languages.

To get a feel for more applications, check out the final section of Native Type Theory. Of course, check out the rest of the paper, and let me know what you think! Thank you for reading.

Posted at March 29, 2021 4:57 AM UTC

TrackBack URL for this Entry:   https://golem.ph.utexas.edu/cgi-bin/MT-3.0/dxy-tb.fcgi/3308

0 Comments & 0 Trackbacks

Post a New Comment