Two-level lambda-calculus
Abstract
Two-level lambda-calculus is designed to provide a mathematical model of capturing substitution, also called instantiation. Instantiation is a feature of the ‘informal meta-level’; it appears pervasively in specifications of the syntax and semantics of formal languages. The two-level lambda-calculus has two levels of variable. Lambda-abstraction and beta-reduction exist for both levels. A level 2 beta-reduct, triggering a substitution of a term for a level 2 variable, does not avoid capture for level 1 abstractions. This models meta-variables and instantiation as appears at the informal meta-level. In this paper we lay down the syntax of the two-level lambda-calculus; we develop theories of freshness, alpha-equivalence, and beta-reduction; and we prove confluence. In doing this we give nominal terms unknowns — which are level 2 variables and appear in several previous papers — a functional meaning. In doing this we take a step towards longer-term goals of developing a foundation for theorem-provers which directly support reasoning in the style of nominal rewriting and nominal algebra, and towards a mathematics of functions which can bind names in their arguments.
Keywords: Lambda Calculus, Meta-variables, Functional programming, Confluence, Nominal terms
1 Introduction
The -calculus is a syntax to express function abstraction and application which is simple, amenable to mathematical analysis, and easy to extend. Yet not everything that looks like a function fits obviously into the -calculus; examples include meta-variables, capturing substitution, and functions depending on intensional properties like free variables and freshness conditions associated with free variables.
This paper defines a -calculus which contains a model of -abstraction and -reduction for meta-variables, including capturing substitution and freshness conditions.
The idea of internalising meta-variables and capturing substitution into formal languages is a recurrent theme in the literature, though our application of nominal techniques to the problem is new and specific to our work. Models of meta-variables and capturing substitution appear in Jojgov’s thesis and subsequent work [20,22], in Munõz’s thesis [25], in work by Hashimoto and Ohori [21], by Lee and Friedman [5], and by Kahrs [23]. This is also a theme in the first author’s research [7,9,11].
Authors cite various motivations for internalising meta-variables and studying capturing substitution; each author comes to the problem with their own individual background, though the ‘convergent evolution’ — the product is always some form of capturing substitution! — suggests that an underlying mathematical entity is being uncovered. These motivations include representing intermediate proof-states (i.e. states of a theorem-prover as it builds a derivation as in the case of Muñoz [25]), and representing ‘-terms with holes’ as a foundation for describing distributed programs, modules, linking, and other manipulations of ‘program fragments’ ([21,5] belong to this camp and both cogently describe their vision). A comparison with related work is in the Conclusions.
We also think some straightforward mathematical curiosity is called for: capture-avoiding substitution is well-studied and finds expression in many formal logics and calculi, yet capturing substitution is fundamental — see the discussion of the informal meta-level in the next paragraph, or the discussions in the papers by the authors cited above — and it has received relatively less formal attention.
We come to this material from the first author’s investigation of nominal rewriting with Fernández [8] and of nominal algebra with Mathijssen [14,24] as mathematical foundations. These use nominal terms [29,8,14] (see also later in this paper) advantageously, as a syntax for rewrite rules and algebraic axioms, which very closely model rules and axioms in what we shall call the informal meta-level — the prose discourse of, for example, this paper. In the informal meta-level, capturing substitution and freshness conditions are widespread. Here are some examples:
-calculus: ()[([]) if is fresh for
-calculus: ( if is fresh for
First-order logic: ( if is fresh for
These quoted (reified) informal statements mention two levels of variable; object-variables and meta-variables . Capture-avoidance conditions are (freshness) constraints on the values that meta-variables may assume.
It seems that meta-variables are naturally substituted with capturing substitution; consider the following quote:
“Set to and to in ()[]; obtain ()[].”
Capturing substitution on syntax trees is not hard to define, yet syntax usually has semantics, which motivates the study of (amongst other things) -equivalence, unification, and -equivalence.
Nominal terms feature a two-level hierarchy of variables directly reflecting the hierarchy noted above:
level 1 variables (atoms) model object-variables;
level 2 variables (unknowns) model meta-variables.
Variables in nominal terms have no in-built functional meaning. There is no -abstraction or , and no application. In a suitable (generalised) sense, nominal terms are first-order. Indeed, until now the semantics for level 2 variables (unknowns) in nominal terms has been ‘they range over terms’. This purely syntactic meaning is acceptable for unification, matching, and rewriting [29,8], and possibly for logic-programming [3], but taking a broader view this is clearly only a partial answer. In this paper we extend nominal terms to investigate full -equivalence in the presence of level 1 and level 2 variables (thus: -equivalence in the presence of object- and meta-variables). By giving level 2 variables a notion of -abstraction and -reduction, we give them a functional operational semantics.
We present two-level -calculus. We give a syntax, reduction system, and prove confluence and consistency. The calculus contains the untyped -calculus (two copies, in fact; at level 1 and level 2), so it is not strongly normalising.
Just as the step from first-order terms to higher-order terms implies an increase in expressivity traded against the loss of some computational and mathematical properties [31], so we expect similar benefits and drawbacks moving from nominal terms to two-level -calculus — but the -calculus now expresses both capturing and capture-avoiding substitution.
We sketch with examples the kind of thing we can do, or believe should be possible in future work, using two-level -calculus. Syntax and full definitions follow.
“Set to be in ” and “set to be in ” are modelled by reductions
( is syntactic equivalence, i.e. ‘the same term’.) Capture-avoidance for (level 1) in the presence of level 2 variables is managed using permutations and freshness in nominal terms style:
“Set to and to in ()[]; obtain ()[]” is expressed by:
“(()[]) applied to twice reduces to ()[].”
It is not hard to impose a simple type system on our syntax (this should be a special case of [6]; here, should cause no essential new difficulties). An interesting application for our calculus is as the basis of a logic. Example axioms are (we indicate types with subscripts):
(#) Here is a type of truth-values. is short for where is a constant symbol. # is short for # where # is a constant symbol intended to internalise the nominal freshness judgement. This models ‘for all , if fv then ’.
Here is a constant symbol, written infix. and are intended to be arbitrary types. This models -equivalence (extensionality) at level 1.
Here is short for where is a constant symbol intended to internalise the Gabbay-Pitts ‘new’ quantifier [19]. and are constant symbols. is a ‘type of atoms’ with no term-formers. This models the self-duality of .
The reductions are real reductions in our calculus. The axioms are expressed in a logic which does not yet exist, but they still have some mathematical force because the structure they express has been studied in previous work with level 2 variables but (since nominal terms have no ) without a level 2 quantification explicitly represented in the syntax. The literature contains theories (sets of axioms) for several specific object languages, including first-order logic, the -calculus, and subsets of ML [24,19,8,11]. It also contains a study describing how to use a fragment of the calculus in this paper, as the term-language for a Curry-Howard correspondence for ‘incomplete derivations’ [13] (level 2 variables represent ‘unknown proofs’, as in Muñoz [25]). Authors mentioned above have their own reasons for considering multi-level systems [20,22,25,21,5,23] and we currently see no obvious reason why the ideas in this paper might not also be turned to other applications.
2 The syntax
Fix disjoint countably infinite sets of level 1 and level 2 variables. We let and range over level 1 and level 2 variables respectively. We use a permutative convention that these are distinct. For example, ‘ and ’ means any pair of distinct level 1 variables. 1
Level 2 variables are sometimes called meta-variables (as in for example [25]). We prefer not to do this; level 2 variables are designed to model meta-variables, but they inhabit the syntax and are objects in the formal syntax. The ‘real’ meta-level still exists — for example we are writing in it now — and mixing terminology for the real thing and our formal model of it, seems to us too great a possible source of confusion.
A permutation is a finitely supported bijection of level 1 variables. Here ‘finitely supported’ means that ( for all but finitely many level 1 variables.
Write id for the identity permutation, so id( always; write for functional composition, so
Write for inverse. Write () for the swapping such that
Let the syntax of two-level -calculus be:
Intuitively, this is two copies of the -calculus; a level 1 copy with , , and , and a level 2 copy with , , and . Both copies have capture-avoiding substitution within their own level. The challenge is to understand how these two copies interact; we discuss this in the rest of this section.
We equate terms up to -equivalence of -bound variables, but not -bound variables (this is not necessary, but it is convenient). We write for syntactic equivalence (up to -equivalence of -bound variables). For example,
There is no paradox here. We do not seek to eliminate the meta-level; we want mathematical models with which to study it. That is why we have given our calculus two levels of variable.
We may write
Define a notion of free occurrence (for level 2) by:
Define level 2 substitution [] and level 1 permutation actions by the rules in Figure 1.
Level 2 substitution avoids capture by -abstracted level 2 variables, but not by -abstracted level 1 variables. Compare the clauses for ()[] and ()[ ]:
()[] ([]) always (no condition that ‘ should be fresh for ’).
()[] ([]) provided (a freshness condition).
From the point of view of level 1 variables, level 2 variables behave like meta-variables and are instantiated. The usual apparatus of level 2 -conversion gives us the power to program ‘normally’ at level 2.
The level 1 permutation action is the general mechanism by which level 1 -renaming is managed; it is based on ideas inherited from nominal terms [29]. It is not always the case that is -equivalent with , but in specific special cases where all variables that permutes are bound, this is the case; more on this in Section 3. For example,
For a discussion of the advantages of this approach, see Cheney’s comment that permutations are ‘inherently capture-avoiding’ [2] and the surrounding discussion.
is a moderated level 2 variable; this is the point in the raw syntax where the two levels of variable interact. Moderations rename level 1 variables in uninstantiated level 2 variables; for example:
In Definition 6 we must decide how the permutation action interacts with level 2 -abstraction (this is a new issue which does not appear in nominal terms, because they do not have level 2 -abstraction). The intuition is ‘ moderates free but not bound level 2 variables’. For example:
in the clause for ()[] can be guaranteed by renaming . The definitions of [] and are intertwined. This is due to the clause for (). The proof that and [] are well-defined is routine, and we omit it. It uses a notion of depth of a term, which will be useful later:
[][] [) ]
() ()
() ()
We prove the result for ] by induction on . We consider just the case of : -converting if necessary, assume . Then:
□
depth( depth().
3 Freshness and reductions
3.1 Definition of the rules
We define some notation:
A freshness is a pair # of a level 1 variable and a term.
Call # a primitive freshness.
Call a finite set of primitive freshnesses a freshness context.
We may drop set brackets, for example writing ## as ## and writing # for #. We may also write ## as #.
Figure 2 gives freshnesses a notion of derivation.
The notion of nominal freshness is well-discussed [19,29,24]. Intuitively,
read ‘ is abstracted/not free in ’. In the presence of level 2 variables, which can be instantiated (substituted in a possibly capturing manner) to any term, the notion of ‘free variables’ is replaced by a notion of freshness which may depend on freshness assumptions on level 2 variables. For example:
We may write ‘#’ as shorthand for ‘# is derivable’. We use this shorthand for other derivable assertions including , , , , defined later.
(a#X) does not implement the denotational notion of freshness for functions from nominal sets [19], with intuition “() equals for fresh ”. Informally, is fresh for the function ‘’ in the sense of (a#X), but not fresh in the sense of nominal sets. (a#X) is a strictly weaker condition; a discussion of denotations is for a later paper.
Write - - for a binary relation on terms parameterised on . Call - - a congruence when it is closed under the rules named in Figure 3.
() builds in the nominal term notion of -equivalence for level 1 variables (see [14, Lemma 3.2]). A better name for congruence might be ‘congruent -equivalence’, but we just write ‘congruence’.
Write level( if mentions a level 2 variable, free or bound. Otherwise, write level(. For example
Write when # for all level 2 variables . Write when # for all level 1 variables .
We can now define our reduction relation:
Let - - be the least congruence closed under the rules named in Figure 3.
Recall that [] is sugar for ().
Level 2 -reduction is a single step [], level 1 -reduction is not. Definition 27 gives the single step level 1 -reduction. There are no level 3 variables in this particular calculus and therefore no special need arises to break level 2 -reduction into smaller steps.
Example reductions are in the Introduction. Note that capture-avoiding substitution is as usual within a single level:
3.2 Discussion of rules (1) and (2)
(1app) and (2app) can be viewed as two parts of a single rule (app):
If level( and # we may join (1app) and (2app) with (#), like so:
The restrictions in (1app) and (2app) are necessary. Suppose we drop them, to obtain just one rule
Then for example: 2
Thus, confluence fails in the presence of (FALSE).
Intuitively, level 2 and level 1 -reducts can ‘compete’ to instantiate variables. The side-conditions on (1app) and (2app) prevent this competition from destroying confluence. Intuitively level 2 -reductions ‘happen first’ — though note that, subject to the side-conditions, -reducts can reduce in any order in the two level -calculus.
More formally, to close a divergence in (())[] between (2) and (FALSE) we must join
where fv and fv and where the freshness context is such that #. It is not possible to join this in general, as the example above shows. It is possible to join this if level( or if #.
The interested reader might like to compare the side-conditions in (1app) and (2app) with the side-condition on the corresponding rule (p) in the lambda-context calculus [11, Figure 5]. For the reader’s convenience we reproduce it here ( denotes a variable of level ; the lambda context calculus has an infinite hierarchy of levels):
Transposing this to the two-level lambda-calculus we would obtain a rule
Clearly, (1app) and (2app) allow more reductions than (LCC). The technical reason that we are able to allow these reductions turns out to be the stronger theory of -equivalence in this paper. Specifically, we should look at the renaming to fresh in the case of ()[] if # in Definition 27. That renaming is not in general possible in the lambda-context calculus; the lambda-context calculus lacks freshness contexts and permutations, so it is not always possible to generate a fresh and rename a level 1 binding to our fresh using a permutation. More comment on the lambda-context caluclus is in the Conclusions.
3.3 Substitution and soundness
In the rest of this section we prove soundness results; that freshness and reduction are preserved under instantiating level 2 variables (Lemma 20 and Theorem 24), and that freshness is preserved under reduction (Theorem 22):
A substitution is a finitely supported map from level 2 variables to terms. ‘Finitely supported’ means that
If is a set of freshnesses write for ‘# for every #’. Lemma 20 is soundness for substitutions compatible with the freshness context:
If then # implies #().
By induction on . We consider two cases:
The case of . #() always, by (a#a).
The case of . Suppose #()# is derivable, where .
Suppose the inductive hypothesis of the derivation. Renaming if necessary, we may assume that and
□
# implies ()#.
Theorem 22 is ‘subject-reduction for freshness’:
If then # implies #.
By induction on derivations. We consider a selection of cases:
The case (2app), assuming #. Suppose # and ()[ ] ([]).
If #()[] then #, #, and #. It follows that #([]). Similarly if #()[]. Similarly for (1app).
The case (2). Suppose that ()[].
If #() then # and ##. It follows by Lemma 20 that #[] as required.
The case (). Suppose that and # and #.
# and # by assumption. If # then, by inductive hypothesis, #, and so #() by Lemma 21.
□
If level( then level(.
Theorem 24 does for what Lemma 20 did for freshness; it is a form of soundness under substitutions compatible with the freshness contexts:
If then implies .
By induction on derivations. We present a selection of cases.
The case (#). Suppose #. By Theorem 22 # if #. It follows by (#) that [] .
The case (1app). We have ()[] ()()[]. By assumption level( so by Lemma 23, level( and ()()[] ([])([]) by (1app). The result follows.
The case (1). By Theorem 22 if # then #. It follows by (1) that ()[] ([]). As ([]) ([ ]), the result follows.□
4 Confluence
Our calculus can be viewed as two -calculi (level 1, level 2) glued together by a nominal treatment of the interaction of level 1 -equivalence with level 2 variables. The proof of confluence also splits into two proofs, plus some ‘proof-glue’.
4.1 Level 1 reductions
Let (level1) be the set
(a) (#) (1app) (2app) (1) (2)
of rules from Figure 3. Let be the least congruence closed under the rules in (level1).
Write # when # is not derivable.
Choose some fixed but arbitrary order on atoms. If is a finite set of atoms say ‘for the first atom not in ’ to mean ‘for the least atom, in our fixed but arbitrary order, that is not an element of ’. 3
For a given , define a level 1 substitution action [] as below; earlier rules take priority:
[] if #.
()[] ([])([]) provided level(.
()[] [] provided #.
()[] ()[] if # and level(.
()[] ([]) provided #.
()[] ((() )[]) if #. Here is the first atom not mentioned in , , , or , such that # and #, if such a exists. Thus we -convert the level 1 to a fresh , but in the presence of level 2 variables we use an explicit permutation and explicitly fresh level 1 variable, in nominal terms style.
()[] ()[] otherwise.
()[] ([]), renaming if needed so that .
Then for that , let be defined as follows; earlier rules have priority, read left-to-right then top-to-bottom ( will always be clear from the context):
We can always rename to ensure .
Intuitively, is a canonical form of , and [] is a canonical form of [ ]. This is not necessarily a normal form (which may not exist), but garbage is collected and substitutions (level 1 -reducts) are pushed into . Level 2 -reducts are unreduced.
Call - -
reflexive when always, and
transitive when and imply .
Write - - for the least transitive reflexive relation containing - -.
Suppose that and are freshness contexts. Say freshly extends when there exists some such that:
(in words: and are disjoint),
for all # it is the case that , and for all # it is the case that .
Intuitively, ‘extends with some fresh atoms’.
For every , , , and there exists a freshly extending such that [] [] ([] calculated for .)
Each rule in Definition 27 is emulated by a rule in (level1). We may need some fresh atoms to -convert. □
depth( depth([])
We have:
(i) ()
(ii) If () for all , then ([])[]
Theorem 33 states that terms reduce to their canonical form; it enters via Lemma 30 that we may need some fresh atoms, to -convert.
For every and there exists a freshly extending such that ( calculated for .)
Fix . Then # implies #. ( calculated for .)
By induction on derivations, using Lemma 32. □
Suppose and also that ], then [] [].
If then .
Theorem 37, along with Theorem 33 above, makes up the diagram in Theorem 38:
For every , , and , there exists a freshly extending such that implies . ( and calculated for .)
By induction on the derivation of . We sketch some cases:
The case (2app) where #. We use Lemma 34 to conclude that # in the case where level(.
The case (1app) where level(.
The case (2). Suppose , which can be guaranteed. Then ()[ ] ([]). We have (()[])[] (([ ])), and we have the result.
The case (). Suppose () . Suppose and # and #. By inductive hypothesis, . By Lemma 34, # and #. By Theorem 22 it follows that # and #. By () it follows that () (). By Lemmas 8 and 36 it follows that () () . By Lemma 32, as required.
□
(level1) is confluent.
4.2 Level 2
Let (level2) be the set
of rules from Figure 3. Let be the least congruence closed under the rules in (level2).
Note that and have (2) in common. This is necessary for confluence to work, see Lemma 51.
implies .
As a corollary, implies .
implies .
As a corollary, implies
It suffices to show that every possible (level2)-reduction can be mirrored by a parallel reduction. This is routine. The second part follows from the first part and an easy proof that ( is reflexive). □
if and only if
If then .
If and ] then [][].
If then .
The proof is by induction on derivations. We present a selection of cases:
The case (PX). By inductive hypothesis, we have . From this and Lemma 45 we can obtain ()[] ()[].
Using (PX), we have .
The case (Papp). By inductive hypothesis, we have and , and also ()() , using Lemma 44. Then ()() is derivable, and the result follows.
The case (P). By inductive hypothesis, , and by Lemma 21, ()# and ()#. Then (
and imply [] [].
The proof is by induction on the derivation of (Figure 4). We assume that .
The case (PX). By Lemma 46, and by the fact that ()[] .
The case (Papp). Suppose , and . Then [] [] and [] [] are both derivable, and from Theorem 24, we have []([]) []. The result follows from (Papp).
The case (P). By inductive hypothesis, [] [], and by Lemma 20, #[] and #[]. Extending with (P), we obtain [] () ([]). The result follows from Lemma 9.□
Write
and similarly for other reduction relations later.
- - satisfies the diamond property: If then there exists some such that
We consider possible pairs of rules that can derive and , where . We present the case of (Papp) and (Papp) for (2). Suppose () ()[] using (Papp), and (Papp) for (2). By inductive hypothesis, there exists an such that and a such that . Using Lemma 47 we derive ()[ ] []. □
is confluent.
4.3 Level 1 and level 2 reductions
implies level
implies that . As a corollary,
implies .
We assume , , and so on. We present some cases:
()[] ()[] ([])([]) when level(.
This can be closed to ([])([]); by Lemma 50 level(.
()[] ()[] ([]) when #.
This can be closed to ([]).
(())[] (())[] (()[]) when #.
This can be closed to (()[]).
[][] (())[] (()[]) when #.
This can be closed to [][] where which can be guaranteed; we require (2) in (level2).
□
If , then for some suitably freshened context, . Similarly, if , then for some suitable freshened context .
- - (reduction with (level2) (level1)) is confluent, in the following sense: if and then there exists some freshly extending , and some , such that and .
By a diagrammatic argument, using Lemma 52. □
The ‘freshly extending’ part of Theorem 53 ensures we can -rename with a permutation to guarantee the freshness precondition of (1). In the presence of only a single level of variable we can ‘just rename’, and so we do not need to record the freshness of freshly generated variables relative to higher-level variables in a freshness context.
Recall Definition 28. Call - - symmetric when implies . Write - - for the least congruence closed under - - that is also transitive, reflexive, and symmetric.
- - is consistent. (There exist two terms which are not related by the transitive reflexive symmetric closure of - -.)
and are two distinct terms, and they do not rewrite to a common term. By Theorem 53 the result follows. □
5 Related and future work
Previous ‘nominal’ -calculi.
The NEW calculus of contexts and the lambda-context calculus [9,11] are -calculi with more than one level of variable. These have a weak theory of -equivalence which is less powerful than that of nominal terms. There are no permutations and it is not possible to -rename in , where has level 1 and has level 2. This problem carries through to the theory of reduction since -reductions can get stuck due to lack of -equivalence. For example, ()[] cannot reduce because we cannot -convert to for a fresh . (A similar observation goes back at least to [5].)
The NEW calculus of contexts and the lambda-context calculus retain some unique features not subsumed by this paper. They have an infinite hierarchy of levels and, arguably, are closer to the -calculus (precisely because their syntax does not include permutations). It is future work to combine -conversion for more than two levels of variable with the notion of reduction with nominal terms style -equivalence appearing in this paper.
The lambda-context calculus preserves strong normalisation. A variant of two-level -calculus which preserves strong normalisation is possible using ideas from [11]. The proof of confluence is not harder. The result in this paper is more relevant for designing logics, where we trade off more reductions against weaker computational properties.
Capture-avoiding substitution as a nominal algebra with Mathijssen [12,18] used nominal terms syntax, with permutations and freshness; substitution corresponds to level 1 -reductions. There is no level 2 -abstraction .
-calculi for capturing substitution.
The -calculus itself can emulate capturing substitution. Let and range over -terms: then the quote in the Introduction is emulated by
‘apply (()()) to ’.
However, compositionality fails in the sense that the number of ‘extra’ -abstractions needed on , and ‘extra’ applications needed on , depend non-locally on the variables for which we authorise capture at the point(s) at which occurs in . See [26, Section 2] for further discussion.
-calculi exist with more than one level of variable, or with constructions with essentially the same intent. We mentioned several in the Introduction.
Jojgov and Geuvers. Jojgov and Geuvers [20] study incomplete derivations in higher-order logic. They create o-HOL, which conservatively extends HOL with ‘open’ terms and ‘open’ (incomplete) proofs. ‘Meta-variables’ (level 2 variables in our terminology) are represented in o-HOL syntax. Their treatment of -conversion is not nominal, but neither is it ‘traditional’. The definition of meta-variable instantiation on page 546 (page 10 of the paper, just after Definition 11) in simplified form reads:
Here is a meta-variable symbol (level 2 variable), and are terms, and is a(n ordinary, level 1) variable. Meta-variable symbols are always associated either with a (list of) variable(s) or a (list of) term(s) . By this rather ingenious device Jojgov and Geuvers seem to manage -equivalence in the presence of two levels of variable. seems to correspond with what we might write ‘[- ]’ and the meta-variable instantiation [ seems to correspond with what we might write ‘[ -][]’.
Establishing the precise technical relationship between our term language and that of Jojgov and Geuvers might be the topic of future work (though the approach of Jojgov and Geuvers has not been under development for some time). However, our syntax seems to be simpler and more atomic. Level 2 variables exist ‘as is’ (not annotated by suspended substitutions). In our system level 1 substitution is managed very simply by level 1 -reducts, whereas Jojgov and Geuvers have two copies of level 1 substitution; level 1 -reducts and the variable-and-term annotations on the meta-variables.
Pfenning et al. A thread of research exemplified by [26] manages capturing vs. non-capturing substitution inside a specially-designed logical framework. Our calculus uses levels; there is no (need for a) ‘wrapping’ in formal logic and the meaning of a term is contained in the term itself, rather than in the term and its interaction with the ‘wrapping’ logical framework. Also, our level 2 variables are ‘open’ (instantiation captures unless a freshness condition forbids it) whereas context variables in [26] are ‘closed’ (variables that can be captured must be accounted for, in the type system).
Sato et al. Sato et al have investigated calculi with meta-variables. Their calculi are very similar to the lambda-context calculus but forbid -reduction if terms contain variables that are ‘too strong’. In particular (()) will not -reduce in their system [28, Subsection 3.3]. For better or for worse, this is a clearly weaker notion of reduction (there are fewer reductions) than two-level lambda-calculus (it is also weaker than the notion of reduction of the lambda-context calculus).
We also mention work by Hashimoto and Ohori [21], which annotates level 2 variables with ‘variable renamers’ similar to our permutations, and work by Lee and Friedman [5] which is more like a full meta-programming system but with an emphasis on meta-variables.
Our two-level -calculus is specifically tailored to nominal terms and so fits into our broader research programme. The syntax is relatively simple, and we may well be able to to import other nominal research, from semantics [19,10] to implementation [30]. Thus, we have not yet built semantics or a type system for two-level -calculus, but tools exist to do this in a principled way [10,6].
Future work.
The complexity of presentation of the two-level lambda-calculus compares reasonably favourably with that of the systems we find by other authors in the existing literature, for example [25,21,20]. We may be able to simplify the presentation futher, this is future work.
We intend to impose types and create a higher-order logic, as outlined in the Introduction. A discussion will follow once the logic is created. Nominal unification, nominal algebra, and one-and-a-halfth order logic [29,24,17] have already done much of the work but the universal quantification of level 2 variables (unknowns) is implicit (there is no or ). Denotations, presumably using nominal sets [19], are future work. We can also consider enriching our functional operational semantics with nominal unification, which is computationally more tractable than higher-order unification [29].
A word on terminology
We have created several multi-level systems: nominal terms [29], hierarchical nominal rewriting [7], the NEW calculus of contexts [9] and the lambda-context calculus [11], one-and-a-halfth-order logic [15] and nominal algebra [14,24]. They all have a capturing substitution but differ in complexity, scale, and detail. We need a taxonomy to describe them.
We have used ‘-and-a-halfth order’, as in ‘one-and-a-halfth order logic’ [17] or ‘two-and-a-halfth order lambda-calculus’ [16]. We have found that this sometimes causes confusion because ‘order’ is usually associated with types. Levels can be viewed as a sort system, but they are not types in the sense of simple type theory [4] (for example, in the two-level lambda-calculus and have different levels but can be substituted for exactly the same terms, namely, any terms at all).
In this paper we propose and use the following terminology:
One level system. Examples include the typed and untyped lambda-calculus, and first- and higher-order logic.
One-and-a-half level system. Two levels of variable, abstraction only for level 1 (not for level 2; i.e. , , and , but no ). Examples include nominal terms, nominal unification, nominal rewriting, nominal algebra, and one-and-a-halfth order logic (which we would now call one-and-a-half level logic).
Two level system. Two levels of variable, abstraction for both. The calculus in this paper is a two level lambda-calculus with a nominal terms style theory of level 1 alpha-equivalence (until now, we would call it ‘two-and-a-halfth order lambda-calculus’; now we call it the ‘two-level lambda-calculus’).
Multi-level system. An infinity of levels with abstraction for all levels. Examples include hierarchical nominal rewriting, the NEW calculus of contexts, and the lambda-context calculus. See [11,9] for accounts of how having more than two levels of variable can be useful.
References
[1] Mirna Bognar. Contexts in Lambda Calculus. PhD thesis, Vrije Universiteit Amsterdam, 2002.
[2] James Cheney. Nominal logic and abstract syntax. SIGACT News (logic column 14), 36(4):47– 69, 2005.
[3] James Cheney and Christian Urban. Prolog: A logic programming language with names, binding and alpha-equivalence. In Bart Demoen and Vladimir Lifschitz, editors, Proc. of the 20th Int’l Conf. on Logic Programming (ICLP 2004), number 3132 in LNCS, pages 269–283. Springer-Verlag, 2004.
[4] Alonzo Church. A formulation of the Simple Theory of Types. Journal of Symbolic Logic, 5(2):56–68, 1942.
[5] Shinn-Der Lee and Daniel P. Friedman. Enriching the lambda calculus with contexts: toward a theory of incremental program construction. In ICFP ’96: Proceedings of the first ACM SIGPLAN international conference on functional programming, pages 239–250, 1996.
[6] Maribel Fernández and Murdoch J. Gabbay. Curry-style types for nominal terms. In Types for Proofs and Programs, volume 4502/2007 of LNCS, pages 125–139, 2006.
[7] Murdoch J. Gabbay. Hierarchical nominal rewriting. In LFMTP’06: Logical Frameworks and Meta-Languages: Theory and Practice, pages 32–47, 2006.
[8] Maribel Fernández and Murdoch J. Gabbay. Nominal rewriting. Information and Computation, 205(6):917–965, 2007.
[9] Murdoch J. Gabbay. A NEW calculus of contexts. In PPDP’05, pages 94–105. ACM, 2005.
[10] Murdoch J. Gabbay. A General Mathematics of Names. Information and Computation, 205:982–1011, July 2007.
[11] Murdoch J. Gabbay and Stéphane Lengrand. The lambda-context calculus. ENTCS, 196:19–35, 2008.
[12] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra. In ICTAC, volume 4281 of LNCS, pages 198–212, 2006.
[13] Murdoch J. Gabbay and Dominic P. Mulligan. One-and-a-halfth order terms: Curry-Howard for incomplete derivations. In WoLLIC ’08: International Workshop on Logic, Language, Information and Computation, volume 5110 of LNAI, pages 180–194, 2008.
[14] Murdoch J. Gabbay and Aad Mathijssen. A formal calculus for informal equality with binding. In WoLLIC’07: 14th Workshop on Logic, Language, Information and Computation, volume 4576 of LNCS, pages 162–176, 2007.
[15] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth order Logic. In PPDP ’06: Proceedings of the 8th International ACM SIGPLAN Conference on Principles and Practice of Declarative Programming, pages 189–200, 2006.
[16] Murdoch J. Gabbay and Dominic P. Mulligan. Two-and-a-halfth order lambda-calulus. In WFLP ’08: 17th International Workshop on Functional and (Constraint) Logic Programming, preliminary proceedings, pages 107–121, 2008.
[17] Murdoch J. Gabbay and Aad Mathijssen. One-and-a-halfth-order Logic (journal version). Journal of Logic and Computation, November 2007. Online.
[18] Murdoch J. Gabbay and Aad Mathijssen. Capture-avoiding Substitution as a Nominal Algebra (journal version). Formal Aspects of Computing, 2008. Online.
[19] Murdoch J. Gabbay and A. M. Pitts. A New Approach to Abstract Syntax with Variable Binding (journal version). Formal Aspects of Computing, 13(3–5):341–363, 2001.
[20] Herman Geuvers and Gueorgui I. Jojgov. Open proofs and open terms. In CSL ’02: Proceedings of the 16th International Workshop and 11th Annual Conference of the EACSL on Computer Science Logic, pages 537–552, 2002.
[21] Masatomo Hashimoto and Atsushi Ohori. A typed context calculus. Theoretical Computer Science, 266(1-2):249–272, 2001.
[22] Gueorgui I. Jojgov. Holes with binding power. In Types for Proofs and Programs, volume 2646 of LNCS, pages 162–181. Springer, 2002.
[23] Stefan Kahrs. Context rewriting. In CTRS ’92: 3rd International Workshop on Conditional Term Rewriting Systems, volume 656 of LNCS, pages 21–35, 1992.
[24] Aad Mathijssen. Logical Calculi for Reasoning with Binding. PhD thesis, Technische Universiteit Eindhoven, 2007.
[25] César Muñoz. A Calculus of Explicit Substitutions for Incomplete Proof Representation in Type Theory. PhD thesis, INRIA Rocqencourt, Projet Coq, 1997.
[26] Aleksandar Nanevski, Frank Pfenning, and Brigitte Pientka. Contextual modal type theory. Transactions on Computational Logic, 2007.
[27] Masahiko Sato, Takafumi Sakurai, and Rod Burstall. Explicit environments. Fundamenta Informaticae, 45:1-2:79–115, 2001.
[28] Masahiko Sato, Takafumi Sakurai, Yukiyoshi Kameyama, and Atsushi Igarashi. Calculi of meta-variables. In CSL, volume 2803 of LNCS, pages 484–497, 2003.
[29] C. Urban, A. M. Pitts, and Murdoch J. Gabbay. Nominal unification. Theoretical Computer Science, 323(1–3):473–497, 2004.
[30] Christian Urban and Christine Tasson. Nominal techniques in Isabelle/HOL. In CADE ’05: Proceedings of the 20th International Conference on Automated Deduction, volume 3632 of Lecture Notes in Artificial Intelligence, pages 38–53, 2005.
[31] Johan van Benthem. Higher-order logic. In Handbook of Philosophical Logic, 2nd Edition, volume 1, pages 189–244. Kluwer, 2001.
Notes
and are meta-variables ranging permutatively over level 1 variables. and are meta-variables ranging permutatively over level 2 variables. However, we will probably just call a level 1 variable, and a level 2 variable, just as we may later call a term when in fact it is a meta-variable ranging over terms (Definition 4). ↩
2 Thanks to Stéphane Lengrand for helping develop this pithy example. ↩
3 This is not necessary for expressing the proofs to follow but it is convenient. We will never make infinitely many choices of fresh atom, and nowhere will the truth of a result depend on our choice of order. ↩