HTML reading edition · 40 source pages · Open the source PDF

Denotation of contextual modal type theory (CMTT): syntax and metaprogramming

Murdoch J. Gabbay

www.gabbay.org.uk

School of Mathematical and Computer Sciences, Heriot–Watt University, Riccarton Edinburgh, EH14 4AS, United Kingdom

Aleksandar Nanevski

software.imdea.org/˜aleks/

IMDEA Software, Facultad de Informática (UPM), Campus Montegancedo, 28660 Boadilla del Monte, Madrid, Spain

Abstract

The modal logic S4 can be used via a Curry-Howard style correspondence to obtain a λ-calculus. Modal (boxed) types are intuitively interpreted as ‘closed syntax of the calculus’. This λ-calculus is called modal type theory—this is the basic case of a more general contextual modal type theory, or CMTT.

CMTT has never been given a denotational semantics in which modal types are given denotation as closed syntax. We show how this can indeed be done, with a twist. We also use the denotation to prove some properties of the system.

Key words: S4 modal logic; Curry-Howard correspondence; contextual modal type theory; meta-programming; higher-order logic; syntax

1. Introduction

The box modality □ from modal logic has proven its usefulness in logic. It admits various logical and semantic interpretations in the spirit of ‘we know that’ or ‘we can prove that’ or ‘in the future it will be the case that’. A nice historical overview of modal logic, which also considers the specific impact of computer science, is in [BdRV01, Subsection 1.7].

CMTT (contextual modal type theory) is a typed λ-calculus based via the Curry-Howard correspondence on the modal logic S4. The box modality becomes a type-former, and box types are intuitively interpreted as ‘closed syntax of’.

So CMTT has types for programs that generate CMTT syntax.

Because of this, CMTT has been applied to meta-programming, but it has independent interest as a language, designed according to rigorous mathematical principles and in harmony with modal logic, which interprets □ in a programming rather than a logical context. Box types are types of the syntax of terms.

Until now this has not been backed up by a denotational semantics in which box types really are populated by the syntax of terms. In this paper, we do that: our intuitions are realised in the denotational semantics in a direct and natural, and also unexpected, manner.

The denotation is interesting from the point of view of the interface between logic and programming. Furthermore, we exploit the denotation to prove properties of the language, showing how denotations are not only illuminating but can also serve for new proof-methods.

1.1. Keeping it simple

This paper considers two related systems:

• The purely modal system, based on box types like □A.

• The contextual modal system, based on ‘boxes containing types’ like [A1, A2]B—the reader might like to think of the contextual system as a multimodal logic [GKWZ03, Subsection 1.4] (whose modalities are themselves indexed over propositions).

Broadly speaking, the purely modal system is nicer to study but a little too simple. The contextual modal system generalises the purely modal system and gives it slightly more expressive power, but it can be a little complicated; not obscure, just long to write out.

Therefore, we open this paper with the modal system, make the main point of our denotation in the simplest and clearest possible manner—the reader who wants to jump right in and work backwards could do worse than start with the example denotations in Subsection 3.3.2 onwards—and then we consider the contextual system as the maths becomes more advanced. Section 2 presents syntax and typing of the modal system and Section 5 does the same for the contextual modal system; Section 3 gives modal denotations and Section 6 gives contextual modal denotations.

The developments are parallel, but not identical. Where proofs are not very different between the modal and contextual systems, we omit routine repetition. We consider reduction of the modal system in Section 4 but not reduction of the contextual system.1 Also, we develop the important notion of shapeliness only for the contextual system in Section 7; it is obvious how the modal case would be a special case.

1.2. Key ideas

Our main technical results are Theorems 3.14 and 6.10, and Corollary 7.8.

However, the key technical ideas that make these results work, and indeed contribute to making them interesting, occur beforehand. It might be useful to briefly enumerate some of them here, as an aid to navigating the mathematics. Exposition is in the body of the paper:

• Inflation in the case of ⟦□A⟧ in Figure 3, and the ‘tail of’ semantics of X@ in Figure 4. This is discussed in Remark 3.5.

• Proposition 2.23 and the fact that it is needed for soundness of the denotation in Theorem 3.14.

• The remarkable Proposition 3.13, in which valuations get turned into substitutions and closed syntax in the denotation interacts directly with the typing system. This is a kind of dual to the interaction seen in Proposition 2.23.

• The denotation of ⟦[Ai]A⟧ in Figure 8, which in the context of the rest of the paper is very natural.

• The notion of shapeliness in Definition 7.1 and the ‘soundness result’ Proposition 7.7.

1.3. On intuitions

1.3.1. ‘Syntax’ means syntax

One early difficulty the authors of this paper faced was in communication, because we sometimes used terms synonymously without realising that the words were so slippery.

The intuition we give to □A is self-reflectively closed syntax of the language itself. This is a distinct intuition from ‘computations’, ‘code’, ‘values’, or ‘intensions’, because these are not necessarily intended self-reflectively.

It is very important not to confuse this intuition with apparently similar intuitions expressed as ‘code of A’, ‘values of A’, ‘computations of A’, or ‘intension of A’. These are not quite the same thing. It may be useful to briefly survey them here:

• ‘Code of A’ is an ambiguous term; this is often understood as precompiled code or bytecode, rather than syntax of the original language. See [WLP98] for a system based on that intuition.

• ‘Values of A’ is a dangerous intuition and there probably should be a law against it: depending on whom one is speaking with, this could be synonymous in their mind with ‘normal forms of A’ (a syntactic notion) or ‘denotations of A’ (a non-syntactic notion). Matters become even worse if one’s interlocutor assumes that denotations may be silently added to syntax as constants (fine for mathematicians; not so fine for programmers). More than one conversation has been corrupted by the associated misunderstandings.

• For a discussion of ‘computation of A’ see the Related Work in the Conclusions, where we discuss how this intuition can lead to a notion of Moggi-style monad.

• ‘Intension of A’ is similar to ‘syntax of A’, but significantly more general: there is no requirement that the intension be syntactic, or if it is syntactic, that it be the same calculus. One could argue that ‘intension of’ should also satisfy that the denotation of □□A be identical in some strong sense—e.g. be the same set as—to that of □A, since taking an intension twice should reveal no further internal structure. (This does not match the denotation of this paper.)
An interesting (and as far as we know unexplored) model of this intuition might be partial equivalence relations (PERs), where □A takes A and forms the identity PER which is defined where A is defined.2 Famously, PERs form a cartesian-closed category [AL91, Subsection 3.4.1].

In short: where the reader sees ‘□A’, they should think ‘raw syntax in type A’.

1.3.2. ‘Functions’ means functions

It may be useful now to head off another possible confusion: where the reader sees A→B, they should think ‘graph of a function’—not ‘computable function’, ‘representable function’, ‘syntax of a function’, or ‘code of a function’.

All of these things are also possible, but in this paper our challenge is to create a type system, language, and denotation which are ‘epsilon away’ from the simply-typed λ-calculus or (since we admit a type of truth-values) higher-order logic—and it just so happens that we also have modal types making precisely its own syntax into first-class data.

So: we are considering a ‘foundations-flavoured’ theory in which A→B represents all possible functions (in whatever foundation the reader prefers) from A to B, and we do not intend this paper to be ‘programming-flavoured’ in which A→B represents only that function(-code) or normal forms that can exist inside some computational device. And, □A should represent, as much as possible, ‘the syntax of our language/logic that types as A’.

2. Syntax and typing of the system with box types

We start by presenting the types, terms, and typing relation for the modal type system. This is the simplest version of the language that we want to give a denotational semantics for.3

2.1. The basic syntax

Definition 2.1

Fix two countably infinite sets of variables A and X. We will observe a permutative convention that a, b, c, . . . will range over distinct variables in A and X, Y, Z, . . . will range over distinct variables in X. We call a, b, c atoms and X, Y, Z unknowns.

Definition 2.2

Define types inductively by:

A ::= o | N | A→A | □A
Notation 2.3

By convention, if X and Y are sets we will write Y X for the set of functions from X to Y . This is to avoid any possible confusion between A→B (which is a type) and Y X (which is a set).

Remark 2.4

• o will be a type of truth values; its denotation will be populated by truth-values {⊥, ⊤}.

• N will be a type of natural numbers; its denotation will be populated by numbers {0, 1, 2, . . . }.

• A→B is a function type; its denotation will be populated by functions.

• □A is a modal type; its denotation will be populated by syntax.

Definition 2.5

Fix a set of constants C to each of which is assigned a type type(C). We write C : A as shorthand for ‘C is a constant and type(C) = A’. We insist that constants include the following:

⊥: o ⊤: o isappA : (□A)→o

We may also assume constants for N, such as 0 : N, succ : N→N, ∗ : N→N→N and + : N→N→N, a fixedpoint combinator, we may write 1 for succ(0), and so on.4

We may omit type subscripts where they are clear from context or do not matter.

Definition 2.6

Define terms inductively by:

r ::= C | a | X@ | λa:A.r | rr | □r | let X=r in r

Constants C are, as standard in the λ-calculus, added as desired to represent logic and computational primitives. An atom a plays the role of a standard λ-calculus variable; it is λ-abstracted in a typed manner in λa:A.r. The term X@ means intuitively ‘evaluate X’ and □r means intuitively ‘the syntax r considered itself in the denotation’. Finally let X=s in r means intuitively ‘set X to be the syntax calculated by s, in r’. Examples of this in action are given and discussed in Subsection 2.3.

Remark 2.7

The effect of r@ (which is not syntax) is obtained by let X=r in X@. Likewise the effect of λX:□A.r (which is not syntax) is obtained by λa:□A.let X=a in r.

We cannot emulate let X=s in X@ using (λa:A.a@)r. The expression ‘a@’ would mean ‘evaluate the syntax a’ rather than ‘evaluate the syntax linked to a’.5

Definition 2.8

Define free atoms fa(r) and free unknowns fu(r) by:

fa(C) = ∅ fa(a) = {a}fa(λa:A.r) = fa(r) \ {a} fa(rs) = fa(r) ∪fa(s)fa(□r) = fa(r) fa(let X=s in r) = fa(r) ∪fa(s)fa(X@) = ∅ fu(C) = ∅ fu(a) = ∅fu(λa:A.s) = fu(s) fu(rs) = fu(r) ∪fu(s)fu(□r) = fu(r) fu(let X=s in r) = (fu(r)\{X}) ∪fu(s)fu(X@) = {X}

If fa(r) ∪ fu(r) = ∅ then we call r closed.

(Hyp)Γ, a : A ⊢a : A(Const)Γ ⊢C : type(C)Γ, a:A ⊢r : B(→I)Γ ⊢(λa:A.r) : A →BΓ ⊢r′ : A →B Γ ⊢r : A(→E)Γ ⊢r′r : BΓ ⊢r : A (fa(r)=∅)(□I)Γ ⊢□r : □AΓ ⊢s:□A Γ, X:□A ⊢r:B(□E)Γ ⊢let X=s in r : B(Ext)Γ, X : □A ⊢X@ : A
Figure 1: Modal type theory typing rules
Definition 2.9

We take a to be bound in r in λa:A.r and X to be bound in r in let X=s in r, and we take syntax up to α-equivalence as usual. We omit definitions but give examples:

• λa:A.a = λb:A.b.

• λa:A.(X@a) = λb:A.(X@b).

• let X=□a in X@b = let Y =□a in Y@b.

As the use of an equality symbol above suggests, we identify terms up to α-equivalence.6

2.2. Typing

Definition 2.10

• A typing is a pair a : A or X : □A.

• A typing context Γ is a finite partial function from A ∪X to types.

• A typing sequent is a tuple Γ ⊢r : A of a typing context, a term, and a type.

We use list notation for typing contexts, e.g. a:A, Y :B is the function mapping a to A and Y to B; and a:A ∈ Γ means that Γ(a) is defined and Γ(a) = A.

Define the valid typing sequents of the modal type system inductively by the rules in

Figure 1.

We discuss examples of typable terms in Subsection 2.3. The important rule is (□I), which tells us that if we have some syntax r and it has no free atoms, then we can box it as a denotation □r of box type—any free unknowns X in r/□r get linked to further boxed syntax, which is expressed by (□E).

Notation 2.11

We may write ∅⊢r : A just as r : A.

Notation 2.12

If Γ is a typing context and U ⊆A∪X then write Γ|U for Γ restricted to U. This is the partial function which is equal to Γ where it is defined, and dom(Γ|U) = dom(Γ) ∩U.

Proposition 2.13 combines Weakening and Strengthening:

Proposition 2.13

If Γ ⊢r : A and Γ′|fu(r)∪fa(r) = Γ|fu(r)∪fa(r) then Γ′ ⊢r : A.

Proof

By a routine induction on r.End of proof

2.3. Examples of terms typable in the modal system

We are now ready to discuss intuitions about this syntax; for a more formal treatment see Section 3 which develops the denotational semantics. We start with some short examples and then consider more complex terms.

2.3.1. Short examples

1. Assume constants ¬ : o→o and ∧ : o→o→o, where ∧ is written infix as usual. Then we can type

∅⊢λa:□o.let X=a in □(¬X@) : □o→□o. ∅⊢λa:□o.λb:□o.let X=a in let Y =b in □(X@ ∧Y@) : □o→□o→□o. ∅⊢λa:□o.let X=a in □(X@ ∧X@) : □o→□o.

Intuitively these represents the syntax transformations P↦ →¬P, P, Q↦ →P ∧Q, and P↦ →P ∧P.

2. This program takes syntax of type A and evaluates it:

∅⊢λa:□A.let X=a in X@ : □A→A

This corresponds to the modal logic axiom (T).

3. Expanding on the previous example, this program takes syntax for a function and an argument, evaluates the syntax and applies the function to the argument:

∅⊢λa:□(A→B).λb:A.(let X=a in X@)b : □(A→B) →(A→B)

4. This program takes syntax of type A tagged with □, and adds an extra □ so that it becomes syntax of type □A:

∅⊢λa:□A.let X=a in □□X@ : □A→□□A

This corresponds to the modal logic axiom (4).

2.3.2. There is no natural term of type A→□A

We can try to give λa:o.□a the type A→□A, but we fail because the typing context a:o does not satisfy fa(a) = ∅.

Our denotation of Figures 3 and 4 illustrates that it is not in general possible to invert the evaluation map from Subsection 2.3.1 and thus map A to □A. This is Corollary 3.15.7 So

• there is a canonical map □A→A (syntax to denotation)—we saw this map in part 1 of this example—but

• not in general an inverse map A→□A (denotation to syntax).

2.3.3. A term for Axiom K

Axiom K, also called the normality axiom [BdRV01, Definition 1.39, Subsection 1.6]; its type is □(A→B)→□A→□B.

We can write a term of this type. Intuitively, the term below takes syntax for a function and syntax for an argument, and produces syntax for the function applied to the argument:

∅⊢λa:□(A→B).λb:□A.let Y =b in let X=a in □(X@Y@) : □(A→B)→□A→□B
Remark 2.14

We exhibited terms of type □A→A, □A→□□A, and □(A→B)→□A→□B, so Figure 1 implements (at least) the deductive power of an intuitionistic variant of S4 [BdRV01, Subsection 4.1, page 194].8

The reader familiar with category theory may also ask whether □ can be viewed as a comonad, since □A→A and □A→□□A look like the types of a counit and comultiplication (and perhaps □(A→B)→□A→□B looks like the action of a functor). We return to this in Section 8.

2.3.4. The example of exponentiation

This is a classic example of meta-programming: write a function that takes a number n and returns syntax for the function x ∈N↦ →xn.

Assuming a combinator for primitive recursion over natural numbers and using some standard sugar, the following term implements exponentiation:

exp 0 ⇒□λb:N.1 exp (succ(n)) ⇒let X=exp n in(□λb:N.b ∗(X@b)).

However, the term above generates β-reducts. The reader can see this because of the ‘□λb:N.b∗ (X@b)’ above. This application X@b is trapped under a □ and will not reduce.

Looking ahead to the reduction relation in Figure 5, exp 2 reduces to

□(λb:N.b ∗(λb:N.b ∗((λb:N.1)b)b)) and not to □(λb:N.(b ∗b ∗1)).

Looking ahead to the denotation of Figure 4, the denotation of exp 2 will likewise be □(λb:N.b∗ (λb:N.b ∗ ((λb:N.1)b)b)) in a suitable sense. We indicate the calculation in Subsection 3.3.4.

The contextual system of Section 5 deals with this particular issue; see Subsection 6.2.2.

2.4. Substitution

Definition 2.15

An (atoms-)substitution σ is a finite partial function from atoms A to terms. σ will range over atoms-substitutions.

Write dom(σ) for the set {a | σ(a) defined}. Write id for the identity substitution, such that dom(σ) = ∅. Write [a:=t] for the map taking a to t and undefined elsewhere.

An (unknowns-)substitution θ is a finite partial function from unknowns X to terms such that for every X, if X ∈ dom(θ) then θ(X) = □r for some r with fa(r) = ∅.

θ will range over unknowns-substitutions. We write dom(θ), id, and [X:=t] just as for atoms-substitutions.

Cσ = C aσ = σ(a) (a ∈dom(σ))(rs)σ = (rσ)(sσ) aσ = a (a ∉dom(σ))(□r)σ = □(rσ) (λc:A.r)σ = λc:A.(rσ) (c ∉fa(σ))X@σ = X@(let Y =s in r)σ = let Y =sσ in rσ (Y ∉fu(σ))Cθ = C aθ = a(rs)θ = (rθ)(sθ) X@θ = s′(θ(X) = □s′)(□r)θ = □(rθ) X@θ = X@(X ∉dom(θ))(λc:A.r)θ = λc:A.(rθ) (let Y =s in r)θ = let Y =sθ in rθ (Y ∉fu(θ))
Figure 2: Substitution actions for atoms and unknowns
Definition 2.16

Define

fa(σ) = dom(σ) ∪⋃{fa(σ(a)) | a∈dom(σ)} fu(σ) = ⋃{fu(σ(a)) | a∈dom(σ)} fu(θ) = dom(θ) ∪⋃{fu(θ(X)) | X∈dom(θ)}.
Remark 2.17

Where θ is defined, it maps X specifically to terms of the form □r with fa(r) = ∅.

This is because ‘□r with fa(r) = ∅’ is the syntax inhabiting modal types. If we consider another class of syntax (e.g. in the contextual system of Section 5 onwards), then the corresponding notion of unknowns-substitution changes in concert with that.

Definition 2.18 describes how atoms and unknowns get instantiated. We discuss it in Remark 2.20 but one point is important above all others: if θ(X) = □s′ then X@θ is equal to s′. A very simple reduction/computation is built in to the substitution action for unknowns, that (□s′)@ →s′.9

Definition 2.18

Define atoms and unknowns substitution actions rσ and rθ inductively by the rules in Figure 2.

Lemma 2.19 illustrates a nice corollary of the point discussed in Remark 2.17. It will be useful later in Proposition 3.13.

Lemma 2.19

fa(rθ) = fa(r).

Proof

By a routine induction on r using our assumption of Definition 2.15 that if X ∈ dom(θ) then fa(θ(X)) = ∅.End of proof

Remark 2.20

A few comments on Definition 2.18:

• The two capture-avoidance side-conditions c ∉ fa(σ) and Y ∉ fu(θ) can always be guaranteed by renaming.

• We write (□r)σ = □(rσ). This is computationally wasteful in the sense that the side-condition fa(r) = ∅ on (□I) (Figure 1) guarantees that for typable terms (which is what we care about) rσ = r. We prefer to keep basic definitions orthogonal from such optimisations, but this is purely a design choice (and see the next item in this list).

• We write (λc:A.r)θ = λc:A.(rθ) without any side-condition that c should avoid capture by atoms in θ. This is because Definition 2.15 insists that fa(θ(X)) = ∅ always, so there can be no capture to avoid.

Recall the definition of [a:=s] from Definition 2.15. Lemma 2.21 is a standard lemma which will be useful later:

Lemma 2.21

If a ∉ fa(r) then r[a:=s] = r.

Proof

By a routine induction on r.End of proof

Definition 2.22 and Proposition 2.23 are needed for Proposition 3.13.

Definition 2.22

Suppose Γ is a typing context and θ is an unknowns-substitution. Write Γ ⊢θ when if X ∈ dom(θ) then X:□A ∈ Γ for some A and Γ ⊢θ(X) : □A.

Proposition 2.23 is needed for Theorem 3.14 (soundness of the denotation). It is slightly unusual that soundness of typing under substitution should be needed for soundness under taking denotations. But the syntax is going to be part of the denotational semantics—that is its point—and so substitution is part of how this denotation is calculated (see the case of □r in Figure 4).

Proposition 2.23

Suppose Γ is a typing context and θ is an unknowns-substitution and suppose Γ ⊢θ (Definition 2.22). Then Γ ⊢r : A implies Γ ⊢rθ : A.

Proof

By a routine induction on the typing of r. We consider four cases:

• The case of (□I). Suppose Γ ⊢r : A and fa(r) = ∅ so that Γ ⊢□r : □A by (□I). By inductive hypothesis Γ ⊢rθ : A. By Lemma 2.19 also fa(rθ) = ∅. We use (□I) and the fact that (□r)θ = □(rθ), and Proposition 2.13.

• The case of (Ext) for X ∈ dom(θ). By assumption in Definition 2.15, θ(X) = □r′ for some r′ with fa(r′) = ∅. By assumption in Definition 2.22 ∅⊢θ(X) : □A. By Definition 2.18 (X@)θ = r′. By Proposition 2.13 Γ ⊢r′: A as required.

• The case of (→I). Suppose Γ, a:A ⊢r : B so that by (→I) Γ ⊢λa:A.r : A→B. By inductive hypothesis Γ, a:A ⊢rθ : B. We use (→I).

• The case of (□E). Suppose Γ, X:□A ⊢r : B and Γ ⊢s : □A so that by (□E) Γ ⊢ let X=s in r : B. Renaming if necessary, suppose X ∉ dom(θ). By inductive hypothesis Γ, X:□A ⊢rθ : B and Γ ⊢sθ : □A. We use (□E) and the fact that (let X=s in r)θ = let X=sθ in rθ.End of proof

3. Denotational semantics for types and terms of the modal type system

We now develop a denotational semantics of the types and terms from Definitions 2.2 and 2.6. The main definitions are in Figures 3 and 4. The design is subtle, so there follows an extended discussion of the definition.

⟦o⟧ = {⊤H, ⊥H} truth-values⟦N⟧ = {0, 1, 2, . . . } natural numbers⟦A→B⟧ = ⟦B⟧⟦A⟧function-spaces⟦□A⟧ = {□r | ∅⊢□r : □A} × ⟦A⟧ closed syntax & purported denotation
Figure 3: Denotational semantics of modal types

3.1. Denotation of types

Definition 3.1

Define ⟦A⟧ the interpretation of types by induction in Figure 3.

Remark 3.2

⟦o⟧ is a pair of truth-values, and ⟦N⟧ is the set of natural numbers. ⟦B⟧⟦A⟧ is a function-space.10 No surprises here.

z ∈⟦□A⟧ is a pair (□r, x). We suggest the reader think of this as

• some syntax □r and11

• its purported denotation x.

We say ‘purported’ because there is no restriction that x actually be a possible denotation of r. For instance, it is a fact that □(0 + 1) :: 2 ∈⟦□N⟧, and □(0 + 1) :: 2 will not be the denotation of any r such that ∅⊢r : N (to check this, unpack Definition 3.11 below).

So our semantics inflates: there are usually elements in ⟦□A⟧ that are not the denotation of any closed term. The reader should remain calm; there are also usually elements in function-spaces that are not the denotation of any closed term. The inflated elements in our semantics are an important part of our design.

Notation 3.3

We will want to talk about nested pairs of the form (x1, (x2, . . . , (xn, xn+1))). Accordingly we will use list notation, writing x1:: x2 for (x1, x2) and x1:: · · · :: xn:: xn+1 for (x1, (x2, . . . , (xn, xn+1))). See for instance Remark 3.4, Figure 4, and Subsection 3.3.2.

Remark 3.4

Note that as standard, distinct syntax may have equal denotation. For instance, □(0 + 1) :: 1 and □(1 + 0) :: 1 are not equal in ⟦N⟧.

Remark 3.5

Why do we inflate? Surely it is both simpler and more intuitive to take ⟦□A⟧ to be {□r | ∅⊢□r : □A}.

We could do this, but then later on in Definition 3.11 we would not be able to give a denotation to terms by induction on their syntax.

The problem is that our types, and terms, are designed to permit generation of syntax at modal type. Thus, our design brief is to allow dynamic (runtime) generation of syntax. With the ‘intuitive’ definition above, there is no guarantee of an inductively decreasing quantity; the runtime can generate syntax of any size. To see this in detail, see Subsection 3.3.3.

The design of ⟦□A⟧ in Figure 3 gets around this by insisting, at the very moment we assert some denotation of a term r of type □A—i.e. some syntax r′ of type A—to simultaneously volunteer a denotation for r′—i.e. an element in the denotation of A. (As mentioned in Remark 3.2 this denotation might be in some sense mistaken, but perhaps surprisingly that will not matter.)

3.2. Denotation of terms

We now set about interpreting terms in the denotation for types from Definition 3.1. The main definition is Definition 3.11. First, however, we need:

• some tools to handle the ‘syntax and purported denotation’ design of ⟦□A⟧ (Definition 3.6); and

• a suitable notion of valuation (Definition 3.7).

We then discuss the design of the definitions.

Recall from Notation 3.3 that we may use list notation and write □r :: x for (□r, x).

Definition 3.6

We define hd and tl on x ∈⟦A⟧ (Definition 3.1) as follows:

• If x ∈⟦o⟧ or ⟦N⟧ or ⟦A→B⟧ then hd(x) = x and tl(x) is undefined.

• If (□r, x) ∈⟦□A⟧ then hd((□r, x)) = □r (first projection) and tl((□r, x)) = x (second projection).

Definition 3.7

A valuation ς is a finite partial function on A ∪X. Write ς[X:=x] for the valuation such that:

• (ς[X:=x])(X) = x.

• (ς[X:=x])(Y ) = ς(Y) if ς(Y) is defined, for all Y other than X.

• (ς[X:=x])(a) = ς(a) if ς(a) is defined.

• (ς[X:=x]) is undefined otherwise.

Define ς[a:=x] similarly.

Definition 3.8

Suppose Γ is a typing context and ς a valuation. Write Γ ⊢ς when:

1. dom(Γ) = dom(ς).

2. If a ∈ dom(ς) then a:A ∈ Γ for some A and ς(a) ∈⟦A⟧.

3. If X ∈ dom(ς) then X:□A ∈ Γ for some A and ς(X) ∈⟦□A⟧.

Remark 3.9

Unpacking Definition 3.1, clause 3 of Definition 3.8 (the one for X) means that ς(X) = □r′:: x where ∅⊢□r′: □A and x ∈⟦A⟧. Note also that by the form of the derivation rules in Figure 1, it follows that ∅⊢r′: A. So an intuition for ς(X) (cf. Remark 3.2) is this—

“ς(X) is some closed syntax r′ (presented as □r′ ∈⟦□A⟧), and a candidate denotation for it x ∈⟦A⟧”,

—or more concisely this:

“ς(X) is a pair of syntax and denotation.”

ς[a:=x] and ς[X:=x] from Definition 3.7. ςX from Definition 3.10. ⟦⊤⟧ς = ⊤H⟦⊥⟧ς = ⊥H⟦a⟧ς = ς(a) (a ∈dom(ς))⟦λa:A.r⟧ς = (x∈⟦A⟧↦ →⟦r⟧ς[a:=x]) ⟦r′r⟧ς = ⟦r′⟧ς ⟦r⟧ς ⟦□r⟧ς = (□(rςX)) :: ⟦r⟧ς ⟦X@⟧ς = tl(ς(X)) ⟦let X=s in r⟧ς = ⟦r⟧ς[X:=⟦s⟧ς] ⟦isappA⟧ς(□(r′r′′) :: x) = ⊤H⟦isappA⟧ς(□(r) :: x) = ⊥H(∀r′, r′′.r ≠ r′r′′)⟦C⟧ς = CH
Figure 4: Denotational semantics of terms of the modal type system
Definition 3.10

Write ςX for the unknowns-substitution (Definition 2.15) such that

ςX(X) = hd(ς(X))

if ς(X) is defined, and ςX is undefined otherwise.

Definition 3.11

For each constant C : A other than ⊤, ⊥, and isapp fix some interpretation CH which is an element CH ∈⟦A⟧. Suppose Γ ⊢ς and Γ ⊢r : A.

An interpretation of terms ⟦r⟧ς is defined in Figure 4.

In Subsection 3.3 we discuss the design of ⟦r⟧ς, with examples. In Subsection 3.4 we prove some results about it.

3.3. Discussion of the denotation

3.3.1. About the term-formers

The denotations of ⊤ and ⊥ are as expected. To give a denotation to an atom a, we just look it up using ς, also as expected. The definitions of λa:A.r and r′r are also as standard.

As promised in Subsection 3.1, ⟦□r⟧ς returns a pair of a syntax and its denotation.

isappA is there to illustrate concretely how we can express programming on syntax of box types: it takes a syntax argument and checks whether it is a syntactic application.12 Of course many other such functions are possible, and if we want them we can add them as further constants (just as we might add +, ∗, and/or recursion as constants, given a type for numbers).

3.3.2. Example: denotation of let X=□(1 + 2) in □□X@

To illustrate how Figure 4 works, we calculate the denotation of let X=□(1 + 2) in □□X@. We reason as follows, where for compactness and clarity we write ς for the valuation [X:=□(1+2) :: 3]:

⟦let X=□(1+2) in □□X⟧∅= ⟦□□X@⟧[X:=⟦□(1+2)⟧∅] = ⟦□□X@⟧ς = □((□X@)[X:=□(1+2)]) :: ⟦□X@⟧ς = □□(1+2) :: ⟦□X@⟧ς = □□(1+2) :: □(X@[X:=□(1+2)]) :: ⟦X@⟧ς = □□(1+2) :: □(1+2) :: ⟦X@⟧ς = □□(1+2) :: □(1+2) :: tl(□(1+2) :: 3) = □□(1+2) :: □(1+2) :: 3

We leave it to the reader to verify that ⟦□(1+2)⟧∅= □(1+2) :: 3 and that X@[X:=□(1+2)] = 1+2.

Note that ‘1 + 2’ and ‘□(1 + 2)’ are different; 1 + 2 denotes 3 whereas □(1 + 2) denotes the pair ‘The syntax 1 + 2, with associated extension 3’. In some very special cases where the set of possible denotations is rather small (finite or countable), the distinction between terms and their denotations can be hard to see, though it is still there. Usually sets of denotations are ‘quite large’ and sets of syntax are ‘quite small’, but sometimes this relationship is reversed: there are ‘somewhat more’ terms denoting numbers, than numbers13 (but much fewer terms denoting functions from numbers to numbers than functions from numbers to numbers). See Corollary 3.15 and Example 3.16.

Note also the difference between the valuation ς = [X:=□(1+2) :: 3] and the substitution [X:=□(1+2)]. The first is a valuation because it maps X to ⟦□N⟧, the second is a substitution because it makes X to a term of type □N.

Sometimes a mapping can be both valuation and substitution; for instance [a:=3] is a valuation (a maps to an element of ⟦N⟧), and is also a substitution.

3.3.3. Why the natural version does not work

Natural versions of Definitions 3.1 and 3.11 take

• the denotation of box type to be just boxed syntax rather than a pair of boxed syntax and denotation ⟦□A⟧ = {□r | ∅⊢□r : □A}, and

• ⟦□r⟧ς = □(rςX) and

• ⟦X@⟧ς = ⟦r⟧∅ where ς(X) = □r.

However, this seems not to work; ς(X) need not necessarily be a smaller term than X so the ‘definition’ above is not inductive. This is not just a hypothetical issue: a term of the form ⟦let X=s in r⟧ς may cause ς(X) to be equal to ⟦s⟧ς, and s might generate syntax of any size.

The previous paragraph is not a mathematical proof; aside from anything else we have left the notion ‘size of term’ unspecified. The reader can experiment with different candidates: obvious ‘subterm of’, ‘depth of’, and ‘number of symbols of’ are all vulnerable to the problem described above, as is a more sophisticated notion of size which gives X size ω the least infinite cardinal—since we can generate multiple copies of terms of the form let X=r in s, and even if this is closed it can contain bound copies of X.

3.3.4. Example: denotation of exp 2

Recalling Subsection 2.3.4, we calculate the denotation of ⟦exp 2⟧∅ where exp is specified by:

exp 0 ⇒□λb:N.1 exp (succ(n)) ⇒let X=exp n in □(λb:N.b ∗(X@b)).

We sketch part of the calculation:

⟦exp (succ (succ 0))⟧∅= ⟦let X=exp (succ 0) in □(λb:N.b ∗(X@b))⟧∅ = ⟦□(λb:N.b ∗(X@b))⟧[X:=⟦exp (succ 0)⟧∅] = □(λb:N.b ∗(X@b))[X:=hd⟦exp (succ 0)⟧∅] :: ⟦λb:N.b ∗(X@b)⟧[X:=⟦exp (succ 0)⟧∅]· · · = □(λb:N.b ∗(λb:N.b ∗((λb:N.1)b)b)) :: (x ∈N↦→x ∗x)

3.3.5. Example: denotation of terms for axioms (T) and (4)

In Subsection 2.3.1 we considered the terms

λa:□A.let X=a in X@ : □A→A and λa:□A.let X=a in □□X@ : □A→□□A

which implement the modal logic axioms (T) and (4). We now describe their denotations, without working:

• ⟦λa:□A.let X=a in X@⟧∅ maps □r :: tl ∈⟦□A⟧ to tl.

• ⟦λa:□A.let X=a in □□X@⟧∅ maps □r :: tl ∈⟦□A⟧ to □□r :: □r :: tl.

3.4. Results about the denotation

We need a technical result and some notation for Proposition 3.13:

Lemma 3.12

If Γ ⊢ς (Definition 3.8) then Γ ⊢ςX (Definition 2.22).

Proof

If X ∉ dom(ς) then X ∉ dom(ςX).

Suppose X ∈ dom(ς). By Definition 3.10 ςX(X) = hd(ς(X)). By Definition 3.8 ςX(X) ∈ ⟦□A⟧ for some A. Unpacking Figure 3 this implies that ςX(X) = □r for some ∅⊢r : A, and we are done.End of proof

Proposition 3.13 relies on a dual role played by syntax in ςX. It is coerced between denotation and syntax in (□I), and ‘in the other direction’ in (Ext). Proposition 3.13 expresses this important dynamic in the mathematics of the paper. Technically, the result is needed for the case of (□I) in the proof of Theorem 3.14. Recall the notation Γ|U from Notation 2.12.

Proposition 3.13

Suppose Γ ⊢r : A and Γ ⊢ς. Then Γ|A ⊢r ςX: A. (ςX is defined in Definition 3.10; its action on r is defined in Definition 2.18.)

Proof

By Lemma 3.12 Γ ⊢ςX. By Proposition 2.23 Γ ⊢r ςX: A. By Lemma 2.19 fa(rςX) = fa(r). Now it is a fact that fa(r) ⊆ dom(Γ|A), so by Proposition 2.13 Γ|A ⊢r ςX: A as required.End of proof

Theorem 3.14 (Soundness).

If Γ ⊢r : A and Γ ⊢ς then ⟦r⟧ς is defined and ⟦r⟧ς ∈⟦A⟧.

Proof

By induction on the derivation of Γ ⊢r : A. Most of the rules follow by properties of sets and functions. We consider the interesting cases:

• Rule (□I). Suppose Γ ⊢r : A and fa(r)=∅ so that by (□I) Γ ⊢□r : A. Suppose Γ ⊢ς. Then by inductive hypothesis ⟦r⟧ς ∈⟦A⟧. Also, by Proposition 3.13 ∅⊢rςX: A It follows by Definition 3.1 that

⟦□r⟧ς = (□(rςX)) :: ⟦r⟧ς ∈⟦□A⟧

as required.

• Rule (□E). Suppose Γ, X:□A ⊢r : B and Γ ⊢s : □A so that by (□E) Γ ⊢ let X=s in r : A. Suppose Γ ⊢ς. By inductive hypothesis for Γ ⊢s : □A we have ⟦s⟧ς ∈⟦□A⟧ and so there is some term s′ and some x ∈⟦A⟧ such that (□s′) :: x = ⟦s⟧ς and ∅⊢□s′ : □A. Unpacking Definition 3.8, Γ, X:□A ⊢ς[X:=(□s′) :: x]. By inductive hypothesis for Γ, X:□A ⊢r : B we have

⟦r⟧ς[X:=(□s′) :: x] ∈⟦B⟧

and using Definition 3.11 we have

⟦let X=s in r⟧ς = ⟦r⟧ς[X:=(□s′) :: x] ∈⟦B⟧

as required.

• Rule (Ext). By (Ext) Γ, X:□A ⊢X@:□A. Suppose Γ, X:□A ⊢ς. Unpacking Definition 3.8, this means that ς(X) = (□s′) :: x for some s′ and x such that ∅⊢□s′: □A and x ∈⟦A⟧. From Definition 3.11 ⟦X@⟧ς = x ∈ ⟦A⟧ as required.

• Rule (Hyp). Suppose Γ, a:A ⊢ς. By Definition 3.8 this means that ς(a) ∈⟦A⟧. By Definition 3.11 ⟦a⟧ς = ς(a). The result follows.End of proof

Corollary 3.15

There is no term s such that ∅⊢s : (N→N)→□(N→N) is typable and such that the map (x∈NN↦ → hd(⟦s⟧∅x))∈ hd(⟦□(N→N)⟧)⟦N→N⟧ is injective.

Proof

⟦N→N⟧ is an uncountable set whereas hd(⟦□(N→N)⟧) = {r | ∅⊢r : N→N} is countable. The result follows from Theorem 3.14.End of proof

Example 3.16

By Corollary 3.15 there can be no term representing a function which reifies an element of ⟦A⟧ to corresponding syntax.

Of course, there might be a term which reifies those elements of ⟦A⟧ that are representable by syntax. For specific ‘sufficiently small’ A, this might even include all of ⟦A⟧.

For example, if A = N then the following function does the job:

reifyNat 0 ⇒□0 reifyNat (succ(n)) ⇒let X=reifyNat(n) in □(X@+1).
Remark 3.17

Similar arguments to those used in Corollary 3.15 and Example 3.16 also justify why the Haskell programming language has a Show function for certain types, but not for function types.14 We chose full function-spaces in Figure 4, so that the models for which we prove soundness in Theorem 3.14 would be large, and we did that so that the proof of Corollary 3.15 would become relatively easy. Careful consideration has gone into the precise designs of ⟦B⟧⟦A⟧ and ⟦□A⟧.

We will later on in Corollary 6.11 prove a similar result for the contextual system, and then later still in Corollary 7.8 surprisingly leverage this to a result which even works for functions to all of ⟦□(N→N)⟧ rather than just to the (much smaller) hd(⟦□(N→N)⟧).

4. Reduction

We have Theorem 3.14 (soundness) and Corollary 3.15 (impossibility in general of reifying denotation to syntax). The other major property of interest is that typing and denotation are consistent with a natural notion of reduction on terms.

So we now turn our attention to the lemmas leading up to Proposition 4.10 and Theorem 4.11.

4.1. Results concerning substitution on atoms

Recall from Definition 2.18 the definition of the atoms-substitution action. Lemma 4.1 is a counterpart to Proposition 3.13. We had to prove Proposition 3.13 earlier because calculating the denotation ⟦□r⟧ς in Figure 4 involves calculating rςX (an unknowns-substitution applied to a term).15 Now we are working towards reduction, and β-reduction can generate atoms-substitution, so we need Lemma 4.1.

Lemma 4.1

Suppose Γ, a:B ⊢r : A and Γ ⊢s : B. Then Γ ⊢r[a:=s] : A.

Proof

By a routine induction on the typing of r. We consider three cases:

• The case of (□I). Suppose Γ, a:B ⊢r : A and fa(r)=∅ so that Γ, a:B ⊢□r : □A by (□I). But then by Lemma 2.21 r[a:=s] = r, and the result follows from Proposition 2.13.

• The case of (Ext) is similar to that of (□I).

• The case of (□E). Using the fact from Definition 2.18 that

(let X=s′ in r)[a:=s] = let X=s′[a:=s] in r[a:=s].End of proof
Lemma 4.2

Suppose Γ, a:B ⊢r : A and Γ ⊢s : B, and suppose Γ ⊢ς. Then ⟦r[a:=s]⟧ς = ⟦r⟧ς[a:=⟦s⟧ς].

Proof

By a routine induction on the derivation of Γ, a:B ⊢r : A (Figure 1). We consider three cases:

• The case of (□I). We use Lemma 2.21 and Proposition 2.13 (as in the case of (□I) in the proof of Lemma 4.1).

• The case of (Ext). By (Ext) Γ, a:B, X:A ⊢X@: A. By definition X@[a:=s] = X@. We use Proposition 2.13.

• The case of (Hyp) for a. By (Hyp) Γ, a:B ⊢a : B. By assumption Γ, a:B ⊢ς so unpacking Definition 3.8, ς(a) ∈⟦B⟧. By Figure 4 ς(a) = ⟦a⟧ς, and we are done.End of proof

Proposition 4.3 can be viewed as a denotational counterpart of Proposition 2.13:

Proposition 4.3

Suppose Γ ⊢r : A and Γ ⊢ς and Γ ⊢ς′. Suppose ς(a) = ς′(a) for every a ∈ fa(r) and ς(X) = ς′(X) for every X ∈ fa(r).

Then ⟦r⟧ς = ⟦r⟧ς′.

Proof

By a routine induction on r.End of proof

Lemma 4.4

Suppose Γ, a:A ⊢r : B and Γ ⊢s : A, and suppose Γ ⊢ς. Then

⟦(λa:A.r)s⟧ς = ⟦r⟧ς[a:=⟦s⟧ς].
Proof

We unpack the cases of λ and application in Definition 3.11.End of proof

4.2. Results concerning substitution on unknowns

Lemma 4.5

Suppose Γ ⊢ (let X=s in r) : A and Γ ⊢ς. Then

⟦let X=s in r⟧ς = ⟦r⟧ς[X:=⟦s⟧ς].
Proof

We just unpack the clause for let X=s in r in Figure 4 (well-definedness is from Theorem 3.14).End of proof

Lemma 4.6

Suppose θ is an unknowns-substitution (Definition 2.15). Suppose X ∉ dom(θ) and suppose fu(θ(Z)) = ∅ for every Z ∈ dom(θ).

Then r[X:=□s]θ = rθ[X:=□(sθ)].

Proof

By a routine induction on r. The interesting case is X@, for which it is easy to check that:

X@θ[X:=(□s)θ] = sθ and X@[X:=□s]θ = sθ.End of proof
Lemma 4.7

Suppose Γ, X:□B ⊢r : A and Γ ⊢□s : □B, and suppose Γ ⊢ς. Then ⟦r[X:=□s]⟧ς = ⟦r⟧ς[X:=⟦□s⟧ς].

Proof

By induction on the derivation of Γ, X:□B ⊢r : A.

• The case of (□I). Suppose Γ, X:□B ⊢r : A and fa(r) = ∅ so that by (□I) Γ, X:□B ⊢ □r : □A. We sketch the necessary reasoning:

⟦(□r)[X:=□s]⟧ς = ⟦□(r[X:=□s])⟧ςDefinition 2.18= □(r[X:=□s])ςX :: ⟦r[X:=□s]⟧ςFigure 4= □(r[X:=□s])ςX :: ⟦r⟧ς[X:=⟦□s⟧ς]Ind. Hyp.= □(rςX[X:=□(sςX)]) :: ⟦r⟧ς[X:=⟦□s⟧ς]Lemma 4.6⟦□r⟧ς[X:=⟦□s⟧ς] = (□r)(ς[X:=⟦□s⟧ς])X :: ⟦r⟧ς[X:=⟦□s⟧ς]Figure 4= (□r)ςX[X:=□(sςX)] :: ⟦r⟧ς[X:=⟦□s⟧ς]Figure 4= □(rςX[X:=□(sςX)]) :: ⟦r⟧ς[X:=⟦□s⟧ς]Definition 2.18

• The case of (Ext) for X. By (Ext) Γ, X:□B ⊢X@: B. Then we reason as follows:

⟦X@⟧ς[X:=⟦□s⟧ς] = tl(⟦□s⟧ς) Figure 4= ⟦s⟧ςFigure 4⟦X@[X:=□s]⟧ς = ⟦s⟧ςDefinition 2.18End of proof
r[a:=s] and r[X:=s] from Definition 2.18. (β)(λa:A.r)r′ →β r[a:=r′](β□)let X=□s in r →β r[X:=□s]r →β r′s →β s′(cnga)rs →β r′s′r →β r′(cngl)λa:A.r →β λa:A.r′r →β r′s →β s′(cnge)let X=s in r →β let X=s′ in r′(isapp⊤)isapp □(r′r) →β ⊤(r not of the form r′r)(isapp⊥)isapp □(r) →β ⊥
Figure 5: Reduction rules for the modal system

4.3. Reduction

Definition 4.8

Define β-reduction r →β r′ inductively by the rules in Figure 5.

Remark 4.9

We do not have a rule that if r →β r′ then □r →β □r′. This would be wrong because it does not respect the integrity of the syntax of a term; syntax, in denotation, does not inherently reduce.

We do however allow reduction under a λ. This is purely a design choice; we are interested in making as many terms as possible β-convertible, and less immediately interested in this paper in finding nice notions of β-normal form. If we did not have a denotational semantics then we might have to be more sensitive to such questions (because normal forms are important for consistency)—because we do have a denotational semantics, we obtain consistency via soundness and the precise notion of normal form is not so vital.

Proposition 4.10

If Γ ⊢r : A and r →r′ then Γ ⊢r′: A.

Proof

By a routine induction on r. The case of (β) (λa:A.r)r′ →β r[a:=r′] follows by Lemma 4.1; that of (β□) follows by Proposition 3.13.End of proof

Theorem 4.11

Suppose Γ ⊢r : A and Γ ⊢ς. Suppose r →β r′. Then ⟦r⟧ς = ⟦r′⟧ς.

Proof

By induction on the derivation of r →β r′.

• The case of (β) follows by Lemmas 4.2 and 4.4.

• The case of (β□) follows by Lemmas 4.5 and 4.7.End of proof

5. Syntax and typing of the system with contextual types

The modal type system is beautiful, but is a little too weak for some applications. The issue is that X ranges over closed syntax. If we are working under some λ-abstractions, we may well find this limiting; we want to work with open syntax so that we can refer to the enclosing binder. This really matters, because it affects the programs we can write. For instance in the example of exponentiation from Subsection 2.3.4, the issue of working under a λ-abstraction forced us to generate unwanted β-redexes.

The contextual system is one way to get around this. Syntax is still closed, but the notion of closure is liberalised by introducing a context into the modality; to see the critical difference, compare the ([]I) rule in Figure 6 with the (□I) rule from Figure 1. The interested reader can see how this allows us to write a nicer program for exponentiation, which does not generate β-redexes, in Subsection 6.2.2.

5.1. Syntax of the contextual system

Notation 5.1

The contextual system needs many vectors of types and atoms-and-types. For clarity, we write these vectors subscripted, for instance:

• (ai:Ai)n 1 is shorthand for {a1:A1, . . . , an:An}.

• [Ai]n 1A is shorthand for [A1, . . . , An]A.

• (Ai)n 1→A is shorthand for A1→(A2→. . . (An→A)).

• {ai}n 1 is shorthand for {a1, . . . , an}.

• [ai:=xi]n 1 will be shorthand for the map taking ai to xi for 1≤i≤n and undefined elsewhere (Definition 5.10).

We may omit the interval where it is understood or irrelevant, so for instance {ai} and {ai}i are both shorthand for the same thing: “{a1, . . . , an} for some n whose precise value we will never need to reference”, and (Ai)→A is shorthand for “(Ai)n 1→A for some n whose precise value we will never need to reference”.

We take atoms and unknowns as in Definition 2.1.

Definition 5.2

Define types inductively by:

A ::= o | N | A →A | [Ai]n 1A

o (truth-values), N (numbers), and A→B (functions) are as in Definition 2.2. [Ai]n 1A is a contextual type. Think of this as generalising the modal types of Definition 5.2 by ‘allowing bindings in the box’.

Definition 5.3

Fix a set of constants C to each of which is assigned a type type(C). We write C : A as shorthand for ‘C is a constant and type(C) = A’. We insist that constants include the following:

⊥: o ⊤: o isappA : ([ ]A)→o

We may omit the type subscripts where they are clear from context or do not matter.

Definition 5.4

Define terms inductively by:

r ::= C | a | λa:A.r | rr | [ai:Ai]r | X@(ri)n 1 | let X=r in r
Remark 5.5

The syntax of the modal type system in Definition 2.6 injects naturally into that of Definition 5.4, if we map □- to [ ]- (the empty context) and -@ to -@().

The important extra complexity is in X@(ri)n 1; when X is instantiated by a substitution θ, this triggers an atoms-substitution of the form [ai:=ri]n 1. See Definition 5.11.

Definition 5.6

Define free atoms fa(r) and free unknowns fu(r) by:

fa(C) = ∅ fa(a) = {a}fa(λa:A.r) = fa(r) \ {a} fa(rs) = fa(r) ∪fa(s)fa([ai:Ai]n 1r) = fa(r) \ {a1, . . . , an} fa(let X=s in r) = fa(r) ∪fa(s)fa(X@(si)i) = ⋃i fa(si)fu(C) = ∅ fu(a) = ∅fu(λa:A.r) = fu(r) fu(rs) = fu(r) ∪fu(s)fu([ai:Ai]r) = fu(r) fu(let X=s in r) = (fu(r)\{X}) ∪fu(s)fu(X@(si)i) = {X} ∪⋃i fu(si)
Definition 5.7

We take a to be bound in r in λa:A.r and a1, . . . , an to be bound in r in [ai:A]n 1r, and we take X to be bound in r in let X=s in r. We take syntax up to α-equivalence as usual. For example:

• λa:A.a = λb:A.b

• λa:A.[b:B]((X@(b))a) = λb:A.[a:B]((X@a)b) ≠ λb:A.[b:B]((X@(b))b)

• let X=[a:A]a in (X@(b))

= let Y =[a:A]a in (Y @(b)) = let Y =[b:A]b in (Y @(b))
(Hyp)Γ, a : A ⊢a : A(Const)Γ ⊢C : type(C)Γ, a:A ⊢r : B(→I)Γ ⊢(λa:A.r) : A →BΓ ⊢r′ : A →B Γ ⊢r : A(→E)Γ ⊢r′r : BΓ, (ai:Ai)i ⊢r : A (fa(r)⊆{ai}i)([ ]I)Γ ⊢[ai:Ai]r : [Ai]AΓ, X:[Ai]A ⊢r:B Γ ⊢s:[Ai]A([ ]E)Γ ⊢let X=s in r : BΓ, X : [Ai]n 1A ⊢rj : Aj(1≤j≤n)(Ext)Γ, X : [Ai]n 1A ⊢X@(ri)n 1 : A
Figure 6: Contextual modal type theory typing rules

5.2. Typing for the contextual system

Definition 5.8

A typing is a pair a : A or X : [Ai]iA. A typing context Γ is a finite partial function from A ∪X to types (as in Definition 2.10, except that unknowns have contextual types instead of just box types □A).

A typing sequent is a tuple Γ ⊢r : A of a typing context, a term, and a type.

Define the valid typing sequents of the contextual modal type system by the rules in

Figure 6.

Recall the notation Γ|U from Notation 2.12. Proposition 5.9 repeats Proposition 2.13 for the contextual system:

Proposition 5.9

If Γ ⊢r : A and Γ′|fu(r)∪fa(r) = Γ|fu(r)∪fa(r) then Γ′ ⊢r : A.

Proof

By a routine induction on r.End of proof

5.3. Substitution

Definition 5.10 reflects Definition 2.15 for the richer syntax of terms:

Definition 5.10

An (atoms-)substitution σ is a finite partial function from atoms A to terms. σ will range over atoms-substitutions.

Write dom(σ) for the set {a | σ(a) defined} Write id for the identity substitution, such that dom(σ) = ∅. Write [ai:=ti]n 1 for the map taking ai to ti for 1≤i≤n and undefined elsewhere. An (unknowns-)substitution θ is a finite partial function from unknowns X to terms such that if θ(X) is defined then θ(X) = [ai:Ai]n 1r for some r with fa(r) ⊆{a1, . . . , an} (so fa(θ(X)) = ∅ for every X ∈ dom(θ)).

θ will range over unknowns-substitutions.

We write dom(θ), id, and [Xi:=ti]n 1 just as for atoms-substitutions (we will be most interested in the case that n = 1).

We also reflect Definition 2.16 and write fa(σ) and fu(θ), but using the notions of ‘free atoms’ and ‘free unknowns’ from Definition 5.6. The definition is formally identical:

fa(σ) = dom(σ) ∪{fa(σ(a)) | a ∈dom(σ)} andfu(θ) = dom(θ) ∪{fu(θ(X)) | X ∈dom(θ)}
Cσ = C aσ = σ(a) (a ∈dom(σ))(rs)σ = (rσ)(sσ) aσ = a (a ∉dom(σ))(X@(ri)i)σ = X@(riσ)i(λc:A.r)σ = λc:A.(rσ) (c ∉fa(σ))(let Y =s in r)σ = let Y =sσ in rσ ([ai:Ai]r)σ = [ai:Ai](rσ) (ai ∉fa(σ) all i)Cθ = C aθ = a(rs)θ = (rθ)(sθ) (X@(ri))θ = s′[ai:=riθ] (θ(X)=[ai:Ai]s′)([ai:Ai]r)θ = [ai:Ai](rθ) (X@(ri))θ = X@(riθ) (X ∉dom(θ))(λc:A.r)θ = λc:A.(rθ) (let Y =s in r)θ = let Y =sθ in rθ (Y ∉fu(θ))
Figure 7: Substitution actions for atoms and unknowns (contextual syntax)
Definition 5.11

Define substitution actions rσ and rθ by the rules in Figure 7.

Remark 5.12

The capture-avoidance side-conditions of Definition 5.11 (of the form ‘∗∉ fa(σ)’ or ‘∗∉ fu(θ)’) can be guaranteed by α-renaming.

The case of (X@(ri)n 1)θ may generate an atoms-substitution s′[ai:=riθ]. In the case n = 0 it is easy to check that this collapses the the previous case of X@ from Figure 2, because the substitution becomes empty.

Note that rσ and rθ are both defined by straightforward induction on r; even if s′ is larger than X@(ri)n 1—so that apparently the inductive quantity gets larger—still s′[ai:=riθ] is an atoms-substitution, not an unknowns-substitution. Meanwhile, atoms-substitution never triggers unknowns-substitution so circularity is avoided.

Strictly speaking the case of (X@(ri)n 1)θ introduces a partiality into the notion of substitution action; we assume that θ(X) = [ai:Ai]m 1 s′ and for this to make sense it must be that n = m; if n ≠ m then the definition is not well-defined. However, for well-typed syntax this is guaranteed not to happen, and since this is the only case we will care about, we will never notice this.

We conclude this section with some important definitions and results about the interaction of substitution and typing, which will be needed for Theorem 6.10.

Definition 5.13 reflects Definition 2.22, but we need Γ ⊢σ as well as Γ ⊢θ:

Definition 5.13

Write Γ ⊢θ when if X ∈ dom(θ) then X:[Ai]A ∈ Γ for some [Ai]A and Γ ⊢θ(X) : [Ai]A.

Similarly write Γ ⊢σ when if a ∈ dom(σ) then a:A ∈ Γ for some A and Γ ⊢σ(a) : A.

Lemma 5.14

fa(rθ) = fa(r) where rθ is defined.

⟦o⟧ = {⊤H, ⊥H} ⟦N⟧ = {0, 1, 2, . . . } ⟦A→B⟧ = ⟦B⟧⟦A⟧⟦[Ai]n 1A⟧ = {[ai:Ai]n 1r | ∅⊢[ai:Ai]n 1r : [Ai]n 1A} × ⟦A⟧Πn i=1⟦Ai⟧
Figure 8: Denotational semantics for CMTT types
Proof

By a routine induction on r using our assumption of Definition 5.10 that if X ∈ dom(θ) then fa(θ(X)) = ∅.End of proof

Lemma 5.15 reflects Lemma 4.1. However, unlike was the case for the modal system, it is needed for Proposition 5.16/2.23 because the case of (X@(ri))θ in Definition 5.11 triggers an atoms-substitution.

Lemma 5.15

Suppose Γ ⊢r : A and Γ ⊢σ. Then Γ ⊢rσ : A.

Proof

By routine inductions on the derivation of Γ ⊢r : A.End of proof

Proposition 5.16 reflects Proposition 2.23 and is needed for soundness of the denotation. The proof is significantly more complex, because of the atoms-substitution that can be introduced by the case of (X@(sj))θ. This is handled in the proof below using Lemma 5.15.

Proposition 5.16

Suppose Γ ⊢r : A and Γ ⊢θ. Then Γ ⊢rθ : A.

Proof

By a routine induction on the typing of r. We consider two cases:

• The case of ([ ]I). Suppose Γ, (bj:Bj) ⊢r : A and fa(r)⊆{bj | j} so that Γ ⊢ [bj:Bj]r : [Bj]A by ([ ]I). By inductive hypothesis Γ, (bj:Bj) ⊢rθ : A. By Lemma 5.14 fu(rθ)⊆{bj | j}. We use ([ ]I) and the fact that ([bj:Bj]r)θ = [bj:Bj](rθ).

• The case of (Ext) for X ∈ dom(θ). Suppose Γ, X:[Aj]m 1 A ⊢sj : Aj for each 1≤j≤m so that by (Ext) Γ, X:[Aj]m 1 A ⊢X@(sj)m 1 :A. By inductive hypothesis Γ ⊢sjθ : Aj for each j. By assumption θ(X) = [aj:Aj]r′ for some r′ such that (aj:Aj)m 1 ⊢r′ : A. By Lemma 5.15 Γ ⊢r′[aj:=sjθ] : A. By the definitions (X@(sj))θ = r′[aj:=sjθ], so we are done.End of proof

We could now give a theory of reduction for the contextual system, following the definition of reduction for the modal system in Subsection 4.3. However, we will skip over this; the interested reader is referred elsewhere [NP05]. What is more interesting, from the point of view of this paper, is the models we define for the contextual system, which we come to next.

6. Contextual models

6.1. Denotational semantics

Definition 6.1 is like Definition 3.1, except that instead of box types, we have contextual types:

Definition 6.1

Define ⟦A⟧ the interpretation of types by induction in Figure 8.

⟦⊤⟧ς = ⊤H⟦⊥⟧ς = ⊥H⟦a⟧ς = ς(a) ⟦λa:A.r⟧ς = (x∈⟦A⟧↦ →⟦r⟧ς[a:=x]) ⟦r′r⟧ς = ⟦r′⟧ς ⟦r⟧ς ⟦[ai:Ai]n 1r⟧ς = [ai:Ai]n 1(r ςX) ::((xi∈⟦Ai⟧)n 1↦ →⟦r⟧ς[ai:=xi]n 1)⟦X@(ri)n 1⟧ς = tl(ς(X)) (⟦ri⟧ς)n 1⟦let X=s in r⟧ς = ⟦r⟧ς[X:=⟦s⟧ς] ⟦isappA⟧ς([ai:Ai](r′r)) = ⊤H⟦isappA⟧ς([ai:Ai](r)) = ⊥Hotherwise⟦C⟧ς = CH
Figure 9: Denotational semantics for terms of the contextual system
Definition 6.2

A valuation ς is a finite partial function on A ∪X.

We define ς[X:=x] and ς[a:=x] just as in Definition 3.7.

Definition 6.3

Write ςX for the substitution (Definition 5.10) such that ςX(X) = hd(ς(X)) if ς(X) is defined, and ςX(X) is undefined if ς(X) is undefined.

Definition 6.4

If Γ is a typing context then write Γ ⊢ς when:

1. dom(Γ) = dom(ς).

2. If a ∈ dom(ς) then Γ(a) = A for some A and ς(a) ∈⟦A⟧.

3. If X ∈ dom(ς) then Γ(X) = [Ai]A and ς(X) ∈⟦[Ai]A⟧.

Remark 6.5

Unpacking Definition 6.1, clause 3 (the one for X) means that ς(X) = [ai:Ai]r′ and ∅⊢ [ai:Ai]r′: [Ai]A. Following the typing rules of Figure 6, this is equivalent to (ai:Ai)i ⊢ r′: A.

Definition 6.6

For each constant C : A other than ⊤, ⊥, and isapp fix some interpretation CH which is an element CH ∈⟦A⟧. Suppose Γ ⊢ς and Γ ⊢r : A.

An interpretation of terms ⟦r⟧ς is defined in Figure 9.
Remark 6.7

Definition 6.6 is in the same spirit as Definition 3.11, but now the modal types are contextual; the modal box contains a context a1:A1, . . . , an:An. When we calculate ⟦X@(ri)n 1⟧ς the denotation of X@(ri)n 1, the denotations of the terms ri provide denotations for the variables in that context.

Lemma 6.8

If Γ ⊢ς then Γ ⊢ςX.

Proof

If X ∉ dom(ς) then X ∉ dom(ςX).

Suppose X ∈ dom(ς). By Definition 6.3 ςX(X) = hd(ς(X)). By Definition 6.4 ςX(X) ∈ ⟦[Ai]n 1A⟧ for some [Ai]n 1A. Unpacking Figure 8 this implies that ςX(X) = [ai:Ai]n 1r for some ∅⊢ [ai:Ai]n 1r : [Ai]n 1A, and we are done.End of proof

Lemma 6.9

Suppose Γ ⊢r : A and Γ ⊢ς. Then Γ|A ⊢rςX: A.

Proof

By Lemma 6.8 Γ ⊢ςX. By Proposition 5.16 Γ ⊢r ςX: A. By Lemma 5.14 fa(rςX) = fa(r). It is a fact that fa(r) ⊆ dom(Γ|A), so by Proposition 2.13 Γ|A ⊢r ςX: A as required.End of proof

Theorem 6.10 (Soundness).

If Γ ⊢r : A and Γ ⊢ς then ⟦r⟧ς ∈⟦A⟧.

Proof

By induction on the the derivation of Γ ⊢r : A. Most of the rules follow by properties of sets and functions. We consider the interesting cases:

• Rule ([ ]I). Suppose Γ, (ai:Ai)n 1 ⊢r : A so that by ([ ]I) Γ ⊢ [ai:Ai]r : [Ai]A. Suppose fa(r)⊆{a1, . . . , an} and Γ ⊢ς. Using Lemma 6.9 ∅⊢ [ai:Ai](rςX) : [Ai]A. Suppose xi ∈⟦Ai⟧ for 1≤i≤n. By Definition 6.4

Γ, (ai:Ai)n 1 ⊢ς[ai:=xi]n 1

so by inductive hypothesis for the derivation of Γ, (ai:Ai)n 1 ⊢r : A it follows that

⟦r⟧ς[ai:=xi]n 1 ∈⟦A⟧.

Now this was true for arbitrary xi and it follows from Definition 6.1 that ⟦[ai:Ai]r⟧ς ∈ ⟦[Ai]A⟧ as required.

• Rule ([ ]E). Suppose Γ, X:[Ai]A ⊢r : B and Γ ⊢s : [Ai]A so that by ([ ]E) Γ ⊢ let X=s in r : B. Suppose Γ ⊢ς. By inductive hypothesis for Γ ⊢s : [Ai]A we have ⟦s⟧ς ∈⟦[Ai]A⟧. It follows by Definition 6.4 that Γ, X:[Ai]A ⊢ς[X:=⟦s⟧ς] so by inductive hypothesis for Γ, X:[Ai]A ⊢r : B we have ⟦r⟧ς[X:=⟦s⟧ς] ∈⟦B⟧. We now observe by Definition 6.6 that

⟦let X=s in r⟧ς = ⟦r⟧ς[X:=⟦s⟧ς] ∈⟦B⟧.

• Rule (Ext). Suppose Γ, X:[Ai]n 1A ⊢ri : Ai for 1≤i≤n so that by (Ext) Γ, X:[Ai]n 1A ⊢ X@(ri)n 1:A. By inductive hypothesis for the typings Γ, X:[Ai]n 1A ⊢ri : Ai we have ⟦ri⟧ς ∈⟦Ai⟧ for 1≤i≤n. Suppose Γ, X:[Ai]A ⊢ς. By Definitions 6.4 and 6.6 this means that ς(X) = ([ai:Ai]n 1r′) :: f for some ∅⊢ [ai:Ai]r′ : [Ai]A and some f ∈ (Πn i=1⟦Ai⟧)→⟦A⟧. It follows that f (⟦ri⟧ς)n 1 ∈⟦A⟧ as required.

• Rule (Hyp). Suppose Γ, a:A ⊢ς. By Definition 6.4 this means that ς(a) ∈⟦A⟧. By Definition 6.6 ⟦a⟧ς = ς(a). The result follows.

• Rule (→I). Suppose Γ, a:A ⊢r : B so that by (→I) Γ ⊢λa:A.r : A→B. Suppose Γ ⊢ς and choose any x ∈⟦A⟧. It follows that Γ, a:A ⊢ς[a:=x] and so by inductive hypothesis that ⟦r⟧ς[a:=x] ∈⟦B⟧. Since x ∈⟦A⟧ was arbitrary, by Definition 6.6 we have that

⟦λa:A.r⟧ς = (x ∈⟦A⟧↦ →⟦r⟧ς[a:=x]) ∈⟦A→B⟧.

End of proof

Corollary 6.11

1. There is no term s such that ∅⊢s : (N→N)→[ ](N→N) is typable and such that the map (x∈NN↦ → hd(⟦s⟧∅x))∈ hd(⟦[ ](N→N)⟧)⟦N→N⟧ is injective.

2. There is no term s such that ∅⊢s : (N→N)→[N]N is typable and such that the map (x∈NN↦ → hd(⟦s⟧∅x))∈ hd(⟦[N]N⟧)⟦N→N⟧ is injective.

Proof

hd⟦[](N→N)⟧ and hd⟦[N]N⟧ are both countable sets whereas ⟦N→N⟧ = NN is uncountable.End of proof

6.2. Typings and denotations in the contextual system

The examples from Subsection 2.3 transfer to the contextual system if we translate □- to [ ]- and -@ to -@() (cf. Remark 5.5). So the reader can look to Subsection 2.3 for some simpler examples.

We now consider some slightly more advanced ideas.

6.2.1. Moving between [A]B and [ ](A→B)

We can move between the types [A]B and [ ](A→B) using terms f : [A]B→[ ](A→B) and g : [ ](A→B)→[A]B defined as follows:

∅⊢f = λc:[A]B.let X=c in [ ]λa:A.X@(a) : [A]B→[ ](A→B) ∅⊢g = λc:[ ](A→B).let X=c in [a:A]((X@())a) : [ ](A→B)→[A]B

It is routine to check that the typings above are derivable using the rules in Figure 6.

Intuitively, we can write the following:

• f maps [a:A]r to [ ]λa:A.r.

• g maps [ ]λa:A.r to [a:A]((λa:A.r)a) (so g introduces a β-redex).

This can be made formal as follows:

hd⟦f ([a:A]r)⟧ς = [ ]λa:A.(rςX) and hd⟦g ([ ]λa:A.r)⟧ς = [a:A]((λa:A.(rςX))a)

The fact that g introduces a β-redex reflects the fact that we have given our language facilities to build up syntax—but not to destroy it. We can build a precise inverse to f if we give ourselves an explicit destructor for λ-abstraction.

So for instance, we can give ourselves option types and then admit a constant symbol match lam : [ ](A→A)→option([A]B) with intended behaviour as follows:

match lam (t) ={ some ([a:A] r) if ⟦t⟧ = ([ ]λa:A.r)::

none otherwise

Using match lam we could map from [ ](A→B) to [A]B in a manner that is inverse to f.16

6.2.2. The example of exponentiation, revisited

Recall from Subsection 2.3.4 the discussion of exponentiation and how in the modal system the natural term to meta-program exponentiation introduced β-reducts.

The following term implements exponentiation:

exp 0 ⇒[b:N]1 exp (succ n) ⇒let X=[b:N]exp n in [b:N](b ∗(X@(b)))

This term does not generate β-reducts in the way we noted of the corresponding term from Subsection 2.3.4. For instance,

hd⟦exp 2⟧∅= [b:N](b ∗b ∗1).

Compare this with Subsection 3.3.4.

Think of the [b:N] in [b:N]r as a ‘translucent lambda’, and think of X@(ri) as a corresponding application. We can use these to carry out computation—a rather weak computation; just a few substitutions as formalised in the clause for X@(ri)i in Figure 7—but this computation occurs inside a modality, which we could not do with an ordinary λ-abstraction.

Now might be a good moment to return to the clause for [ai:Ai]r in Figure 9:

⟦[ai:Ai]n 1r⟧ς = [ai:Ai]n 1(r ςX) ::((xi∈⟦Ai⟧)n 1↦ →⟦r⟧ς[ai:=xi]n 1)

We see the λ-abstraction in the semantics, and we also see its ‘translucency’: the λ-abstraction appears in the extension, but is also associated with a non-functional intension.

6.2.3. Syntax to denotation

There is a schema of unpack programs, parameterised over (ai:Ai)n 1 which evaluates syntax with n free atoms:

unpack = λb:[Ai]n 1B.let X=b in λ(ai:Ai)n 1.X@(ai)n 1: [Ai]n 1B→((Ai)n 1→B)

We can express the following connection between unpack (which is a term) and tl (which is a function on denotations):

Lemma 6.12

Suppose Γ ⊢ [ai:Ai]s : [Ai]A and Γ ⊢ς. Then

⟦unpack [ai:Ai]s⟧ς = tl⟦[ai:Ai]s⟧ς.
Proof

By long but routine calculations unpacking Figure 9.End of proof

As an aside, note that if we have diverging terms ωi: Ai then we can combine this with unpack to obtain a term ∅⊢λa:[Ai]A.unpack a (ωi) : [Ai]A→A. In a call-by-name evaluation strategy, this loops forever if evaluation tries to refer to one of the (diverging) arguments.

6.2.4. Modal-style axioms

As in Subsection 2.3.1 we can write functions corresponding to axioms from the necessity fragment of S4:

T = λa:[ ]A.let X=a in X@() : [ ]A→A4 = λx.let X=x in [ ][ ]X@() : [ ]A→[ ][ ]AK = λf.λx.let F=f in let X=x in F@() X@() : [ ](A→B)→[ ]A→[ ]B

(Of course, T is just a special case of unpack above.)

6.2.5. More general contexts

Versions of the terms 4 and K exist for non-empty contexts. For example, we can have a schema of 4Γ axioms, for any context Γ:

4Γ = λx:[Γ]A.let X=x in [ ][Γ]X@(idΓ) : [Γ]A→[ ][Γ]A

Here and below we abuse notation by putting [Γ] in the type; we intend the types in Γ, with the variables removed.

Above, idΓ is the identity substitution defined inductively on Γ by

id· = · and idΓ,x:A = idΓ, x.

Note that the terms realising 4Γ are not uniform, because the substitution idΓ is not a term in the language; it is a meta-level concept, producing different syntax depending on Γ.

Similarly, we have a schema of KΓ terms:

KΓ = λf.λx.let F=f in let X=x in [Γ]F @idΓ X@idΓ: [Γ](A→B)→[Γ]A→[Γ]B

...and terms exposing the structural rules of contexts:

weakenΓ1,Γ2 = λz.let Z=z in [Γ1, Γ2](Z@(idΓ1)) : [Γ1]A→[Γ1, Γ2]AcontractB = λz.let Z=z in [x:B](Z@(x, x)) : [B, B]A→[B]AexchangeB,C = λz.let Z=z in [y:C, x:B](Z@(x, y)) : [B, C]A→[C, B]A

We give weaken in full generality and then for brevity contract and exchange only for two-element contexts. If we think in terms of multimodal logic [GKWZ03] these terms ‘factor’, ‘fuse’, and ‘rearrange’ contexts/modalities.

7. Shapeliness

We have seen semantics to both the modal and contextual type systems. We have also noted that, like function-spaces, our semantics inflates. We discussed why in Remark 3.5 and Subsection 3.3.3.

In this section we delve deeper into the fine structure of the denotation to isolate a property of those parts of the denotation that can be described by syntax (Definition 7.1). This is an attractive well-formedness/well-behavedness property in its own right, and furthermore, we can exploit it to strengthen Corollaries 3.15 and 6.11 (see Corollary 7.8).

Definition 7.1

Define the shapely x ∈⟦A⟧ inductively by the rules in Figure 10.

Call ς shapely when:

• ς(X) is shapely for every X ∈ dom(ς).

• ς(a) is shapely for every a ∈ dom(ς).

Remark 7.2

In words, the condition x = ⟦hd(x)⟧∅ in (Shape[ ]) reads: “x is equal to the extension/denotation of the intension/syntax of x”. So, if x is in ⟦[Ai]A⟧ and we extract the syntax from this, which is hd(x), then if we calculate the denotation of that syntax we get x back again.

Elements in ⟦B⟧, ⟦N⟧, or ⟦N→N⟧ are automatically shapely, because they carry no intension/syntax.

Conversely, x is not shapely when it has an intension and an extension—and they do not match up. The paradigmatic non-shapely element is [ ]0 :: 1, since the intension ‘the syntax 0’ does not match the extension ‘the number 1’.

tl(x) ∈⟦(Ai)n 1→A⟧ is shapely x = ⟦hd(x)⟧∅(Shape[ ])x ∈⟦[Ai]n 1A⟧ is shapely ∀y ∈⟦B⟧.y is shapely ⇒xy ∈⟦A⟧ is shapely(ShapeFun)x ∈⟦B→A⟧ is shapely (x ∈⟦B⟧)(ShapeB)x ∈⟦B⟧ is shapely(x ∈⟦N⟧)(ShapeN)x ∈⟦N⟧ is shapely
Figure 10: Shapeliness
Lemma 7.3

1. If x ∈⟦B→A⟧ is shapely and y ∈⟦B⟧ is shapely, then so is xy ∈⟦A⟧.

2. If x ∈⟦[Ai]A⟧ is shapely then x = ⟦hd(x)⟧∅.

3. Every f ∈NN is shapely.

Proof

The first two parts follow from the form of the inductive definition in Figure 10. The third part is a simple application of (ShapeFun), noting that by (ShapeN) every n ∈N is shapely.End of proof

We can combine Lemmas 7.3 and 6.12 to get a nice corollary of shapeliness (unpack is from Subsection 6.2.3):

Corollary 7.4

If x ∈⟦[Ai]A⟧ is shapely then tl(x) = ⟦unpack hd(x)⟧∅.

Proof

Suppose x ∈⟦[Ai]A⟧ is shapely, so that by part 2 of Lemma 7.3 x = ⟦hd(x)⟧∅. We apply tl to both sides and use Lemma 6.12.End of proof

Lemma 7.5

Suppose Γ, X : [Bi]B ⊢r : A, Γ ⊢ [ai:Bi]s : [Bi]B, and Γ ⊢ς. Then ⟦r[X:=[ai:Bi]s]⟧ς = ⟦r⟧ς[X:=⟦[Bi]s⟧ς].

Proof

By a routine induction on the derivation of Γ ⊢r : A, similar to the proof of Lemma 4.7.End of proof

Corollary 7.6

Suppose Γ ⊢r : A, Γ ⊢ς, and ς is shapely. Then ⟦r⟧ς = ⟦r ςX⟧ς|A.

Proof

First, we note that the effect of ςX can be obtained by concatenating [X:=hd(ς(X))] for every X ∈ fu(r). The order does not matter because by construction hd(ς(X)) is closed syntax (no free variables). Furthermore since ς is shapely, ς(X) = ⟦hd(ς(X))⟧∅ so we can write ς as

ς|A ∪[X:=⟦hd(ς(X))⟧ς | X ∈dom(ς)],

where here [X:=xX | X ∈X] is the map taking X to xX for every X ∈X.17 We now use Lemma 7.5 for [X:=ς(X)] for each X ∈ fu(r), and Proposition 5.9.End of proof

Proposition 7.7

Suppose Γ ⊢r : A and suppose Γ ⊢ς. Then if ς is shapely then so is ⟦r⟧ς.

Proof

By induction on the typing Γ ⊢r : A (Figure 6).

• The case of (Hyp) is immediate because by assumption ς(a) is shapely.

• The case of (Const) is also immediate (provided that all semantics for constants are shapely).

• The case of (→I). Suppose Γ, a:A ⊢r : B so that by (→I) Γ ⊢λa:A.r : A→B. Suppose x ∈⟦A⟧ is shapely. Then so is ς[a:=x] and by inductive hypothesis so is ⟦r⟧ς[a:=x]. It follows by (ShapeFun) that

⟦λa:x.r⟧ς =(x ∈⟦A⟧↦ →⟦r⟧ς[a:=x])

is shapely.

• The case of (→E). Suppose Γ ⊢r′ : A→B and Γ ⊢r : A so that by (→E) Γ ⊢r′r : B. By inductive hypothesis ⟦r′⟧ς and ⟦r⟧ς are both shapely. By part 1 of Lemma 7.3 so is ⟦r′r⟧ς = ⟦r′⟧ς⟦r⟧ς.

• The case of ([ ]I). Suppose Γ, (ai:Ai) ⊢r : A and fa(r) ⊆{ai} so that by ([ ]I) Γ ⊢ [ai:Ai]r : [Ai]A. By inductive hypothesis ⟦r⟧ς′ is shapely for every shapely ς′ such that Γ, (ai:Ai) ⊢ς′ and it follows that tl⟦[ai:Ai]r⟧ς = ⟦λ(ai:Ai).r⟧ς is shapely. Also unpacking definitions

hd⟦[ai:Ai]r⟧ς = [ai:Ai](rςX).

So it suffices to verify that ⟦[ai:Ai]r⟧ς = ⟦[ai:Ai](rςX)⟧∅. This follows from Corollary 7.6.End of proof

Corollary 6.11 proved that denotations cannot be reified to syntax in general, by general arguments on cardinality. But our denotational semantics is inflated; ⟦[ ](A→B)⟧ and ⟦A→B⟧ have the same cardinality even if hd(⟦[ ](A→B)⟧) and ⟦A→B⟧ do not. Corollary 7.8 tells us that we cannot in general even reify denotation to the ‘inflated’ denotations, even if they are large enough. In this sense, inflation is ‘not internally detectable’:

Corollary 7.8

1. There is no term s such that ∅⊢s : (N→N)→[ ](N→N) is typable and such that ⟦s⟧∅∈⟦[ ](N→N)⟧⟦N→N⟧ is injective.

2. There is no term s such that ∅⊢s : (N→N)→[N]N is typable and such that ⟦s⟧∅∈ ⟦[N]N⟧⟦N→N⟧ is injective.

Proof

By Proposition 7.7 s is shapely, so by part 1 of Lemma 7.3 it maps shapely elements of NN = ⟦N→N⟧ to shapely elements of ⟦[ ](N→N)⟧/⟦[N]N⟧. By part 3 of Lemma 7.3 and the fact that NN is uncountable, the number of shapely elements of NN is uncountable. By part 2 of Lemma 7.3 and the fact that syntax is countable, the number of shapely elements of ⟦[ ](N→N)⟧ and ⟦[N]N⟧ is countable. The result follows.End of proof

It is clear that part 1 of Corollary 7.8 can be directly adapted to the modal system from Section 2.

8. □ as a (relative) comonad

We noted as early as Remark 2.14 that □ looks like a comonad. In this section, we show that this is indeed the case.

Before doing this, we would like to convince the reader that this is obviously impossible. True, we have natural maps □A →A (evaluation) and □A →□□A (quotation). However, if □ is a comonad then it has to be a functor on some suitable category, so we would expect some natural map in (A→B) → (□A→□B). This seems unlikely because if we had this, then we could take A to be a unit type (populated by one element) and B = (N→N) and thus generate a natural map from N→N to □(N→N). But how would we do this in the light of Corollaries 6.11 and Corollary 7.8? Even where closed syntax exists for a denotation, there may be many different choices of closed syntax to represent the same denotation, further undermining our chances of finding natural assignments. ‘□ as a comonad’ seems doomed.

This problem is circumvented by the ‘trick’ of considering a category in which each denotation must be associated with syntax; we do not insist that the syntax and denotation match. This is essentially the same idea as inflation in Remark 3.2 (but applied in the other direction; in Remark 3.2 we inflated by adding a purported denotation to every syntax; here we are inflating by adding a purported syntax to every denotation). In the terminology of Definition 7.1 we can say that we do not insist on shapeliness. We simply insist that some syntax be provided.

Modulo this ‘trick’, □ becomes a well-behaved comonad after all.

8.1. □ as a comonad

Notation 8.1

Write π1 for first projection and π2 for second projection.

That is, π1(x, y) = x and π2(x, y) = y.

Definition 8.2

Suppose f ∈⟦□B⟧⟦□A⟧. Define a function ⊡f ∈⟦□□B⟧⟦□□A⟧ by sending

□□s :: x to □π1(f(□s :: ⟦s⟧∅)) :: f(x)

where x ∈⟦□A⟧ and s : A.

Remark 8.3

It may be useful to unpack what ⊡f does. Suppose

f(□r :: x) = □r′ :: x′and f(□s :: y) = □s′ :: y′

where x ∈⟦A⟧ and y = ⟦s⟧∅. Then □f sends □□s :: □r :: x to □□s′:: □r′:: x′.

Definition 8.4

Define a category J by:

• Objects are types A.18

• Arrows from A to B are functions from ⟦□A⟧ to ⟦□B⟧ (not from ⟦A⟧ to ⟦B⟧; as promised above, some syntax must be provided).

Composition of arrows is given by composition of functions.

Definition 8.5

Define an endofunctor ⊡ on J mapping

• an object A to ⊡A = □A and

• an arrow f : A →B to ⊡f : ⊡A →⊡B from Definition 8.2. So □ is a type-former acting on types and ⊡ is a functor acting on objects and arrows. Objects happen to be types, and ⊡ acts on objects just by prepending a □. Arrows are functions on sets, and the action on ⊡ on these functions is more complex as defined above.

Definition 8.6

• Write idA for the identity on ⟦□A⟧ for each A.

• Write δA for the arrow from ⊡A to A given by the function mapping ⟦□□A⟧ to ⟦□A⟧ taking □□r :: x to x (where x ∈⟦□A⟧). This will be the counit of our comonad.

• Write ϵA for the arrow from ⊡A to ⊡⊡A given by the function mapping ⟦□□A⟧ to ⟦□□□A⟧ taking □□r :: x to □□□r :: □□r :: x (where x ∈⟦□A⟧). This will be the comultiplication of our comonad.

Lemma 8.7

⊡ from Definition 8.5 is a functor.

Proof

It is routine to verify that ⊡idA = id⊡A and if f : A →B and g : B →C then ⊡g ◦⊡f = ⊡(g ◦f).End of proof

Lemma 8.8

• δA is a natural transformation from ⊡ to idJ (the identity functor on J ).

• ϵA is a natural transformation from ⊡ to ⊡⊡.

Proof

Suppose f : A →B. For the first part, we need to check that f ◦δA = δB ◦⊡f. This is routine:

(f ◦δA)(□□r :: x) = f(x) andδB ◦⊡f = π2(□π1(f(□r :: ⟦r⟧∅)) :: f(x))= f(x)

The second part is similar and no harder.End of proof

Note that ⊡δA is an arrow from ⊡⊡A to ⊡A.

Lemma 8.9

⊡δA maps □□□s :: □□r :: x ∈⟦□□□A⟧ to □□s :: x ∈⟦□□A⟧.

Proof

By a routine calculation on the definitions:

□δA(□□□s :: □□r :: x) = □π1(δA(□□□s :: ⟦□□s⟧∅)) :: δA(□□r :: x) Definition 8.2= □π1(δA(□□□s :: ⟦□□s⟧∅)) :: x Definition 8.6= □π1(⟦□□s⟧∅) :: x Definition 8.6= □□s :: x Figure 4End of proof
Proposition 8.10

⊡ is a comonad.

Proof

We need to check that

• ⊡ϵA ◦ϵA = ϵ⊡A ◦ϵA and

• δ⊡A ◦ϵA = idA = ⊡δA ◦ϵA.

Both calculations are routine. We consider just the second one. Consider □□s :: □r :: x ∈ ⟦□□A⟧. Then

(δ⊡A ◦ϵA)(□□s :: □r :: x) = δ⊡A( □□□s :: □□s :: □r :: x) = □□s :: □r :: x (⊡δA ◦ϵA)(□□s :: □r :: x) = ⊡δA(□□□s :: □□s :: □r :: x) = □□s :: □r :: x

The shaded part is the part that gets ‘deleted’. In the second case we use Lemma 8.9.End of proof

8.2. □ as a relative comonad

Recall that in the previous subsection we represented □ as a comonad on a category with the ‘trick’ of associating syntax to every denotation.

It is possible to put this in a broader context using the notion of relative comonad.

Definition 8.11

Following [ACU10, Definition 1], a relative comonad consists of the following information:

• Two categories J and C and a functor J : J →C.19

• A functor T : J →C.

• For every X ∈J an arrow δX : TX →JX ∈C (the unit).

• For every X, Y ∈J and arrow k : TX →JY ∈C, an arrow k∗ : TX →TY (the Kleisli extension).

Furthermore, we insist on the following equalities:

• If X, Y ∈J and k : X →Y ∈J then k = k∗◦δ.

• If X ∈J then δ∗ X = idTX.

• If X, Y, Z ∈J and k : TX →JY and l : TY →JZ then l∗◦k∗= (l∗◦k)∗.

Definition 8.12

Take C to have objects types A and arrows elements of ⟦B⟧⟦A⟧ = ⟦A→B⟧— this is simply the natural category arising from the denotational semantics of Figure 3.

Take J to be the category of Definition 8.4. Take J to map A ∈J to □A ∈C and to map f ∈⟦□B⟧⟦□A⟧ to itself. Take T to map A ∈J to □□A ∈C and to map f ∈⟦□B⟧⟦□A⟧ to ⊡f from Definition 8.2.

Proposition 8.13

Definition 8.12 determines a relative comonad on C.

It is slightly simplified, but accurate, to describe relative (co)monads as being for the case where we have an operator that is nearly (co)monadic but the category in question has ‘too many objects’. By that view, □ is a comonad on the full subcategory of C over modal types.

Now the intuition of modal types □A is ‘closed syntax’, so it may be worth explicitly noting here that this full subcategory is not just a category of syntax. Each ⟦□A⟧ contains for each term ∅⊢r : A also a copy of ⟦A⟧, because we inflate.

9. Conclusions

The intuition realised by the denotation of □A in this paper is ‘typable closed syntax of the same language, of type A’. This is difficult to get right because it is self-referential; the denotation of a term of modal type can be the syntax of another term, which might have larger size than the term that denoted it. If we are careless, then this fact might make it impossible to define denotation by induction on syntax. We noted this in Subsection 3.3.3.

For that reason we realised this intuition by an ‘inflated’ reading of □A as ‘closed syntax, and purported denotation of that syntax’. If the system constructs a term inhabiting the denotation of a modal type, then it is required to provide at the same time some denotation for that term—even if that denotation is ‘silly’. As noted in Remark 3.2, there is no restriction that □r :: x ∈⟦□A⟧ needs to match up, in that r must have denotation x.

When r and x do match up we say that □r :: x is shapely. This is Definition 7.1, and we use this notion for our culminating result in Corollary 7.8, which entails that there is no uniform family of terms of type A→□A.

The proof of this involves a beautiful interplay between syntax and denotation, which also illustrates the usefulness of denotational techniques; we can use a sound model to show that certain things cannot happen in the syntax, because if they did, they would have to happen in the model.

Future work. One avenue for future work is to note that our denotation is sets based, and so this invites generalisation to nominal sets semantics [GP01].

Perhaps we could leverage this to design a language which combines the simplicity of the purely modal system with the expressivity of contextual terms. Specifically, nominal sets are useful for giving semantics to open terms [GM11, Gab11] and we hope to develop a language in which we can retain the modal type system but relax the condition that fa(r) = ∅ in (□I) in Figure 1 (much as the contextual system does, but in the ‘nominal’ approach we would not add types to the modality).

The underlying motivation here is that the contextual system is ‘eager’ in accounting for free variables—we need to express all the variables we intend to use in the contextual modal type, by putting their types in the modality. We might prefer to program on open syntax in a ‘lazy’ fashion, by stating that the syntax may be open, but not specifying its free variables explicitly in the type.

Note that this is not the same thing as programming freely on open syntax. Free variables would still be accounted for in the typing context (leading to some form of dynamic linking as and when open syntax is unboxed and evaluated; for an example of a λ-calculus view of dynamic linking, though not meta-programming, see [AFZ03]). So all variables would be eventually accounted for in the typing context, but they would not need to be listed in the type.

This is another reason for the specific design of our denotational semantics and taking the denotation of □A to be specifically closed syntax; we hope to directly generalise this using nominal techniques so that □A can also denote (atoms-)open syntax. This is future work.

On the precise meaning of Corollary 7.8. Corollary 7.8 depends on the fact that we admitted no constants of type (N→N)→□(N→N). We may be able to admit such a constant, representing a function that takes denotation and associates to it some ‘dummy syntax’ chosen in some fixed but arbitrary manner.

So Corollary 7.8 does not (and should not) prove that terms of type (N→N)→□(N→N) are completely impossible—only that they do not arise from the base system and cannot exist unless we explicitly choose to put them in there.

Technical notes on the jump in complexity from modal to contextual system. We noted in the introduction that Sections 2 and 5, and Sections 3 and 6 are parallel developments of the syntax and examples of the modal and contextual systems.

We briefly survey technical details of how these differences manifest themselves.

• The contextual system enriches the modal system with types in the modality. The increase in expressivity is exemplified in Subsection 6.2.2.

• In the contextual system and not in the modal system, instantiation of unknowns can trigger an atoms-substitution (see Definition 5.11) leading to a kind of ‘cascade effect’. This turns out to be terminating, well-behaved, and basically harmless—but this has to be verified, and that brings some specific technical material forward in the proofs for the contextual case that is not so prominent in the purely modal case (notably, Lemma 5.15).

• A clear view of exactly where the extra complexity of the contextual system ‘lives’ in the denotation can be obtained by comparing the denotational semantics of □A and [Ai]A in Figures 3 and 8.

Related work □ and monads. Famously, Moggi proposed to model computation using a monad [Mog91]. Let us write it as ⃝A. This type is intuitively populated by ‘computations of type A’. The unit arrow A→⃝A takes a value of type A and returns the trivial computation that just returns A.

Pfenning and Davies [PD01, Section 7, page 21] have shown that the type ⃝A can be encoded in the modal system as ♦□A, while the function-space A ⇒B of a monadic system is encoded as □A →B of the modal system.

The difference from the comonad of this paper in that our □A is populated by closed syntax, and not by computation.

If we have an element of NN then it is easy to build a computation that just returns that value; it is however not easy—and may be impossible—to exhibit closed syntax to represent this computation.

We could add a constant to our syntax for each of the uncountably many functions from natural numbers to natural numbers. This would be mathematically fine—but not particularly implementable. We do not assume this.

Closed syntax is of course related to computation, and we can make this formal: Given an element in □(N→N) we can map it to a computation, just by executing it. So intuitively there is an arrow □A →⃝A.

See also [Kob97, BdP00, AMdPR01], where the □ operator of several constructive variants of S4 (not equivalent to the version we presented here) is modeled as comonads.

Brief survey of applications of □ calculi. Logic and denotation, not implementation, are the focus of this paper, but the ‘□-calculi’ considered in this paper have their motivation in implementation and indeed they were specifically designed to address implementational concerns. We therefore give a brief survey of how (contextual) modal types have been useful in the more applied end of computer science.

The connection of the modal □ calculus with partial evaluation and staged computation was noticed by Davies and Pfenning [DP01, PD01], and subsequently used as a language for run-time code generation by Wickline et al. [WLP98]. The contextual variant of □ as a basis for meta-programming and modeling of higher-order abstract syntax was proposed by Nanevski and Pfenning [NP05], and subsequently used to reason about optimised implementation of higher-order unification in Twelf [PP03], which could even be scaled to dependent types [NPP08].

Recently, the contextual flavor of the system has been used in meta-programming applications for reasoning and programming with higher-order abstract syntax by Pientka and collaborators [Pie08, PD08, FP10, CP12].

Relationship between the formulation with meta-variables and labeled natural deductions. The syntax of terms from Definition 2.6 does not follow instantly from the syntax of types from Definition 2.2; in particular, the use of a two-level syntax (also reminiscent of the two levels of nominal terms [UPG04]) is a design choice, not an inevitability.

The usual way to present inference systems based on modal logic is to have a propositional (or variable) context where each proposition is labeled by the ‘world’ at which it is true [Sim94].

When S4 is considered, we take advantage of reflexivity and transitivity of the Kripke frame to simplify the required information to two kinds of facts:

1. What holds at the current world, but not necessarily in all future worlds.

2. What holds in the current world and also in all future worlds.

By this view, the first kind of fact corresponds to atoms a, and the second kind of fact corresponds to unknowns X. So this can be seen as the origin of the two-level structure of our syntax in this paper.

The interested reader can find the modal (non-contextual) version of our type system presented using the labeled approach in a paper by Davies and Pfenning [DP01], and each stage of computation is indeed viewed as world in a Kripke frame.

CMTT and nominal terms. Nominal terms were developed in [UPG03, UPG04] and feature a two-level syntax, just like CMTT. That is made very clear in this paper, where the first author imported the nominal terms terminology of atoms and unknowns.

The syntax of this paper is not fully nominal—the [ai]r of the contextual system may look like a nominal abstraction, but there are no suspended permutation π·X (instead, we have types in the modality). One contribution of this paper is to make formal, by a denotation, the precise status of the two levels of variable in CMTT.

So we can note that the abstraction for atoms is functional abstraction in CMTT whereas the abstraction for atoms in nominal terms is nominal atoms-abstraction;20 unknowns of nominal terms range over elements of nominal sets, whereas unknowns of CMTT range over ordinary sets functionally abstracted over finitely many arguments; the notion of equivariance (symmetry up to permuting atoms) characteristic of all nominal techniques is absent in CMTT (the closest we get is a term like exchangeB,C in Subsection 6.2.4); and in contrast the self-reflective character of CMTT is absent from nominal terms and the logics built out of it [Gab12]. So in spite of some structural parallels between CMTT and nominal terms in that both are two-level, there are also significant differences.

As noted above, there is a parallel between CMTT and Kripke structures, that is made more explicit in [DP01]. A direct connection between nominal terms and Kripke semantics has never been made, but the first author at least has been aware of it as a possibility, where ‘future worlds’ corresponds to ‘more substitutions arriving’. Also as discussed above, an obvious next step is to develop a modified modal syntax which takes on board more ‘nominal’ ideas, applied to the modal intuitions which motivate the λ-calculus of this paper. This is future work.

The syntax of this paper, and previous work. The modal and contextual systems which we give semantics to in this paper, are taken from previous work. Specifically, Definition 2.6 corresponds to [PD01, Subsection 2.2], Definition 5.4 corresponds to the term section opening [NPP08, Subsection 4.1], Figure 1 corresponds to [PD01, Subsection 2.3] and Figure 6 to [NPP08, Figure 3].

We feel that this paper does make some contribution in terms of presentation, and the exposition and definitions here may be tailored to a slightly different community.

Acknowledgements

This paper was supported by Spanish MICINN Project TIN2010-20639 Paran10; AMAROUT grant PCOFUND-GA-2008-229599; Ramon y Cajal grants RYC-2010-0743 and RYC-2006-002131; and the Leverhulme Trust.

References

[ACU10] Thorsten Altenkirch, James Chapman, and Tarmo Uustalu. Monads need not be endo-functors. In Foundations of software science and computation structures, 13th International Conference (FOSSACS 2010), volume 6014 of Lecture Notes in Computer Science, pages 297–311. Springer, 2010.

[AFZ03] Davide Ancona, Sonia Fagorzi, and Elena Zucca. A calculus for dynamic linking. In ICTCS, pages 284–301, 2003.

[AL91] Andréa Asperti and Giuseppe Longo. Categories, types, and structures: an introduction to category theory for the working computer scientist. Foundations of computing. MIT Press, 1991. Available online from the University of Michigan, digitised November 2007.

[AMdPR01] Natasha Alechina, Michael Mendler, Valeria de Paiva, and Eike Ritter. Categorical and Kripke semantics for Constructive S4 modal logic. In Computer Science Logic, CSL’01, volume 2142 of Lecture Notes in Computer Science, pages 292–307, 2001.

[BdP00] Gavin M. Bierman and Valeria C. V. de Paiva. On an intuitionistic modal logic. Studia Logica, 65(3):383–416, 2000.

[BdRV01] Patrick Blackburn, Maarten de Rijke, and Yde Venema. Modal Logic. Cambridge University Press, 2001.

[CP12] Andrew Cave and Brigitte Pientka. Programming with binders and indexed data-types. In Proceedings of the 39th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’12), pages 413–424. ACM Press, 2012.

[DP01] Rowan Davies and Frank Pfenning. A modal analysis of staged computation. Journal of the ACM, 48(3):555–604, 2001.

[FP10] Amy Felty and Brigitte Pientka. Reasoning with higher-order abstract syntax and contexts: A comparison. In Interactive Theorem Proving, volume 6172 of Lecture Notes in Computer Science, pages 227–242, 2010.

[Gab11] Murdoch J. Gabbay. Stone duality for First-Order Logic: a nominal approach. In Howard Barringer Festschrift. December 2011.

[Gab12] Murdoch J. Gabbay. Nominal terms and nominal logics: from foundations to meta-mathematics. In Handbook of Philosophical Logic, volume 17. Kluwer, 2012.

[GKWZ03] Dov M. Gabbay, Agnes Kurucz, Frank Wolter, and Michael Zakharyaschev. Many-dimensional modal logics: theory and applications, volume 148 of Studies in Logic and the Foundations of Mathematics. Elsevier, 2003.

[GM09] Murdoch J. Gabbay and Dominic P. Mulligan. Universal algebra over lambda-terms and nominal terms: the connection in logic between nominal techniques and higher-order variables. In Proceedings of the 4th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2009), pages 64–73. ACM, August 2009.

[GM11] Murdoch J. Gabbay and Dominic Mulligan. Nominal Henkin Semantics: simply-typed lambda-calculus models in nominal sets. In Proceedings of the 6th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2011), volume 71 of EPTCS, pages 58–75, September 2011.

[GP01] Murdoch J. Gabbay and Andrew M. Pitts. A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, 13(3–5):341–363, July 2001.

[Kob97] Satoshi Kobayashi. Monad as modality. Theoretical Computer Science, 175(1):29–74, 1997.

[Mit96] John C. Mitchell. Foundations for Programming Languages. MIT Press, 1996.

[Mog91] Eugenio Moggi. Notions of computation and monads. Information and Computation, 93(1):55–92, 1991.

[NP05] Aleksandar Nanevski and Frank Pfenning. Staged computation with names and necessity. Journal of Functional Programming, 15(6):893–939, 2005.

[NPP08] Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. ACM Transactions on Computational Logic, 9(3):1–49, 2008.

[PD01] Frank Pfenning and Rowan Davies. A judgmental reconstruction of modal logic. Mathematical Structures in Computer Science, 11(4), 2001.

[PD08] Brigitte Pientka and Joshua Dunfield. Programming with proofs and explicit contexts. In Proceedings of the 10th International ACM SIGPLAN Symposium on Principles and Practice of Declarative Programming (PPDP 2008), pages 163–173, 2008.

[Pie08] Brigitte Pientka. A type-theoretic foundation for programming with higher-order abstract syntax and first-class substitutions. In Proceedings of the 35th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL’08), pages 371–382. ACM Press, 2008.

[PP03] Brigitte Pientka and Frank Pfenning. Optimizing higher-order pattern unification. In Proceedings of the International Conference on Automated Deduction (CADE’03), volume 2741 of Lecture Notes in Computer Science, pages 473–487, 2003.

[Sim94] Alex K. Simpson. The Proof Theory and Semantics of Intuitionistic Modal Logic. PhD thesis, University of Edinburgh, 1994.

[UPG03] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. In CSL, volume 2803 of Lecture Notes in Computer Science, pages 513–527. Springer, December 2003.

[UPG04] Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay. Nominal Unification. Theoretical Computer Science, 323(1–3):473–497, September 2004.

[WLP98] Philip Wickline, Peter Lee, and Frank Pfenning. Run-time code generation and Modal-ML. In Programming Language Design and Implementation (PLDI’98), pages 224–235. ACM Press, 1998.

Notes

1We choose not to do this, not because it is hard, but because it is easy (apologies to John F. Kennedy). ↩

2Alex Simpson and Paul Levy both independently suggested PERs when the first author sketched the ideas of this paper, and Simpson went further and suggested the specific model discussed above. We are grateful to Levy and Simpson for their comments, which prompted us to be specific about the intuition behind the particular denotation in this paper. ↩

3This section follows the ideas presented in [PD01]; Definition 2.6 corresponds to [PD01, Subsection 2.2] and Figure 1 corresponds to [PD01, Subsection 2.3]. We use a different syntax and make some other superficial changes to ordering and presentation. So the material is just slightly rewritten, reorganised, and represented from previous work. We also concentrate some examples in Subsection 2.3. There is one small but interesting technical difference: we write X@ where Pfenning and Davies would just write X (or u, in their notation; the point is there is no -@). This propagates to our definition of substitution, where the -@ must be explicitly stripped off in Figure 2. There are two reasons for this: when we come to the contextual system the -@ generalises to the more non-trivial -@(r1)n 1 so even though every X occurs as X@ here we prefer to keep the -@; and also, in our denotation -@ corresponds to the non-trivial operation of ‘take the tail of the list’, see Figure 4. ↩

4...so we follow the example of PCF [Mit96]. A fixedpoint combinator cannot be interpreted in the denotational semantics of Section 3, which adopts a ‘sets-and-functions’ flavour following semantics for Higher-Order Logic (type theory). ↩

5In addition even if a@ were syntax, it would not type in the typing system of Figure 1, because fa(a@) would be equal to {a} ≠ ∅ (Definition 2.8). Modal types are inhabited by closed syntax (Definition 2.8). ↩

6Using nominal abstract syntax [GP01] this identification can be made consistent with the use of names for bound atoms and the inductive definition in Definition 2.6. However, studying how best to define syntax is not the emphasis of this paper. ↩

7For sufficiently ‘small’ types this may be possible by specific constructions; see Example 3.16. ↩

8The list of axioms of [BdRV01, page 194] uses ♦ instead of □. A most remarkable family of theorems of Kripke semantics for modal logic relates geometric properties of the Kripke frame’s accessibility relation with logical properties of the modalities. Axiom (K) is satisfied by all frames. Axiom (T) expresses geometrically that accessibility is reflexive. Axiom (4) expresses that accessibility is transitive. ↩

9(□s′)@ is not actually syntax, but if it were, then (□s′)@ →s′ would be its reduction. ↩

10We could restrict this to computable functions or some other smaller set but we have our logician’s hat on here, not our programmer’s hat on: we want the larger set. This will make Corollary 3.15 work. If we chose a smaller, more sophisticated, and more complex notion of function-space here, then this would actually weaken the results we then obtain from the semantics. ↩

11We could drop the □ and just write (r, x), but when we build the contextual system in Section 5 the □ will fill with bindings (see Definition 5.4) and cannot be dropped, so we keep it here. ↩

12We know non-trivial pattern-matching on applications exists in our meta-logic because our meta-logic is English; ⟦isapp⟧ς is a function on a set of syntax and we can define whatever operation we can define, on that set. ↩

136 + 5 and 5 + 6 denote the same number, whose calculation we leave as an exercise to the energetic reader. ↩

14See haskell.org/haskellwiki/Show_instance_for_functions, retrieved on January 20, 2012. ↩

15In the contextual system, calculating the denotation will involve atoms-substitution as well. ↩

16We do not promote this language directly as a practical programming language, any more than one would promote the pure λ-calculus. We should add constants for the operations we care about. The point is that in this language, there are things we can do using the modal types that cannot be expressed directly in the pure λ-calculus, no matter how many constants we might add. ↩

17Strictly speaking we also need a version of Proposition 4.3 for the contextual system; this is not hard. ↩

18The reader might prefer to take objects to be ⟦A⟧. This is fine; the assignment A↦ −→⟦A⟧ is injective, so it makes no difference whether we take objects to be A or ⟦A⟧. ↩

19The clash with the J from Definition 8.4 is deliberate: this is the only J we will care about in this paper. The definition of relative comonad from [ACU10] is general in the source category. ↩

20In [GM09] we translate nominal terms to higher-order terms, and atoms-abstraction gets translated to functional abstraction. However, this does not mean that atoms-abstraction is a ‘special case’ of functional abstraction, any more than translating e.g. Java to machine binary means that method invocation is a special case of logic gates. ↩