A Sequent Calculus for Nominal Logic
Abstract
Nominal logic is a theory of names and binding based on the primitive concepts of freshness and swapping, with a self-dual - (or “new”)-quantifier, originally presented as a Hilbert-style axiom system extending first-order logic. We present a sequent calculus for nominal logic called Fresh Logic, or FL, admitting cut-elimination. We use FL to provide a proof-theoretic foundation for nominal logic programming and show how to interpret , another logic with a self-dual quantifier, within FL.
1 Introduction
Names are ubiquitous in logic, theoretical computer science, and practical programming. Names appear as variable symbols in programs and logical formulae, channel names in -calculus processes, nonces in security protocols, and in many other situations. The ability to reason about names is therefore important to many areas of computer science.
Though integers, strings, or other concrete data are often used as representations of such names, usually the representation does not matter; we take the characteristic properties of names to be:
1. Renaming (or Equivariance). Properties concerning names are invariant up to permutative renaming (either globally, or for bound names, locally).
2. Freshness. Fresh names can always be generated.
For example, to distribute a substitution under a -abstraction (), it is necessary first to generate a fresh variable name , and rename to in the body of the abstraction. Similarly, to extrude the scope of a -calculus restriction in it is necessary to generate a fresh channel name and rename in the body of the restriction. When Microsoft Windows loads a DLL, it rebases it to avoid an address space conflict. The situation is worse when we have an unknown which may be instantiated after we have finished our calculation: how is it possible to choose fresh names, or rename existing names, in an unknown which will be instantiated after the fact of our calculations?
We give a proof-theoretic account of these phenomena based on a First-Order logic Fresh Logic (FL). It includes primitive swappings () on terms for renaming, a quantifier (‘New’ quantifier) that quantifies over sufficiently fresh names, and rules expressing the facts that fresh names can always be chosen and that all formulae are invariant under permutative renamings.
Related work includes Nominal Logic [10] and FM-HOL [7], Hilbert-style axiom systems both concentrating on expressiveness, and a natural-deduction presentation of Fresh Logic , concentrating on semantics. Nominal Unification [12] and Nominal Rewriting [3] use the same techniques of swapping and freshness in their respective domains, to good effect.
The Fresh Logic of this paper is presented as a Gentzen-style intuitionistic sequent calculus with cut-elimination. As such it provides a direct reading of logical connectives (including ) as proof-search techniques, suitable both for human reasoning and automated deduction. We discuss other innovative design features in the course of the paper. The quantifier possesses interesting proof-theoretic properties, notably self-duality: it has both a and character, and . This duality is reflected directly in the symmetric structure of the -rules of FL.
In addition to presenting our calculus and proving cut-elimination, we also present two applications: we give a uniform proof-theoretic semantics to a logic programming language with -quantified goals and program clauses, and we relate FL to a similar calculus [9] which also has a self-dual quantifier. A semantics for Fresh Logic is not presented in this paper, but previous work [5] describes a Kripke-style semantics based on FM sets [4, 6] and gives details of proof-normalization for a natural-deduction version of Fresh Logic.
2 Fresh Logic
Fix a set of sorts Sorts and distinguish a sort of atoms A Sorts. We assume function sorts .
Fix countably infinite sets of variables and c d of constants. Constants and variables are inherently sorted and we may indicate this as c : , :. We assume a constant : AA exists for each sort . Variable names like , etc. are typically used for variables of sort A.
Terms are simply-typed -terms constructed according to the grammar:
Well-formedness is defined in the usual way; terms are always assumed to be well-formed at appropriate sorts and identified up to -equivalence ( or just ). We introduce the notion () of ‘free variables of ’, defined in the usual way. We introduce a substitution action defined in the standard (capture-avoiding) way. We introduce the shorthand for a list of terms and () for applied to the list of arguments .
Terms of sort A are often called atoms and written (as above) as , etc. A term of the form (from now on abbreviated () ) is called a swapping of and applied to . Square brackets are used when necessary to avoid ambiguity between ordinary parentheses and swappings. We consider the addition of constants for FM abstraction [12, 4, 3] in 6.1.
We assume predicate constant symbols , each with an arity (i.e., a list of sorts of the arguments of the predicate). For each Sorts we assume distinguished constants equality and # : A freshness. Propositions or formulae are generated by the grammar
is shorthand for and is shorthand for .
Like terms, propositions have notions of free variables () and substitution defined as usual. We also adopt the notation () abbreviating () () , where (. That is, () is the result of applying () to each free variable of . For example,
Formulae are considered equal up to consistent renaming of bound identifiers.
A (logical) context is a multiset of propositions, usually written Γ. Write (Γ) for the obvious extension of () to many formulae. We may also write Γ and () Γ.
2.1 Judgments and Derivation Rules
A judgment is a pair Γ of a context and predicate written Γ . Elements of Γ are called hypotheses and the conclusion. The valid or derivable judgments are inductively defined by the rules of Figure 1, Figure 2, and Figure 3.
In (new) (Γ) denotes all variables free in Γ or , that is () in Γ or . # denotes a list of assumptions # # .
In (R) and (L), we assume (as usual) that the bound variable is not already present in the conclusion. In (L) and (R) we assume and are of the same sort.
Note that the (L) rule may be used to add an instance of any of the swapping axioms listed in to Γ (read bottom-up). We write () to abbreviate an inference following from some collection of (L), (#) (#), and equality laws. For example,
2.2 The nonlogical rules
The rules (#) (case) (new) (#) (L), and the swapping axioms are referred to as nonlogical rules, because they deal with atomic formulae rather than logical connectives. In this section we give some intuition for the meanings and purposes of these rules.
(#): No atom is fresh for itself.
(case): For atoms, freshness coincides with inequality and is decidable (even though FL is intuitionistic).
(new): Read bottom-up this rule says we can always generate a new atom fresh for any terms . This embodies the Freshness principle mentioned in the introduction.
(#): If atoms are fresh for then swapping them in has no effect.
(L): This is Equivariance for predicates, also mentioned in the introduction. Validity of is independent of the particular values of atoms mentioned in ; only equalities or inequalities among atoms matter. For example if # () holds for some atoms , then # () holds for any . This can be proved using (L) to swap for and for .
(L) and swapping axioms: These axioms describe the behavior of swapping. The first three axioms imply swapping with itself has no effect; swapping is its own inverse; and swapping acts as expected on atoms, respectively. The remaining three axioms imply that swapping is is homomorphic with respect to -term structure. Note that in our system, axiom (E1) of [10] becomes derivable:
() [() ) ] [() ]) [() ] (3)
The axiom involving is particularly interesting: to see why the added substitution is needed, consider applying a swapping to the -equivalent terms () and .
2.3 The -quantifier rules
The rules (R) and (L) are symmetric; we consider just (R). As discussed starting from Prop. 4.10 in [4], the -quantifier satisfies the “some/any” equivalences
where () is a list of all free variables of except for . So at first sight a sequent rule such as
(where () might seem appropriate. A deduction rule should be closed under substitution; this is necessary to prove the substitution property which is needed in cut-elimination for and . But (5) is not closed under substitution, for substituting a non-variable term such as c() for one of the results in a non-instance.
To make the deduction rules for closed under substitution, we use slices. Caires and Cardelli have a similar notion of ‘free term’ [1].
A slice of over is a tuple () of , a variable symbol , and:
1. Variable symbols which we write , not appearing in
2. A proposition with (.
3. Terms which we write , such that () and .
There is a natural notion of minimal slice, the (unique up to renaming the ) slice such that is as small and the are as large as possible. We omit the formal definition. For example, the minimal slice of (()) over is ((()) ()(()) ()), and the minimal slice of the same term with respect to is ((()) ()()()).
We write [] as shorthand for “the minimal slice of over is () for some ”. The following are useful technical results:
If [] then for any term , . Also, for any and such that (), [].
Thus a substitution for in does not affect the , and minimality of slices over is not affected by substitutions that do not introduce free occurrences of .
3 Example deductions
(D1) connects and # within Fresh Logic. In the instance of (L), ( # )[]. (D2) derives an equivalent of (#) within Fresh Logic. In (D3) () and () are the variables of and and # () is a list of freshness assumptions # for each () ().
The reverse entailment () is similarly derivable. We can also derive similar equivalences for the other connectives such as and .
(D4) is one direction of a well-known commutativity property ( # ) .
(D5) and (D6) are another well-known relation between #, , and equality, specifically # () (see [4, Prop. 4.10]).
4 Metatheoretic Properties
Some basic metatheoretic properties include: Substitution: If Γ is derivable then so is Γ , assuming and are sort-compatible. Weakening: If Γ is derivable then so is Γ. Moreover, these transformations are all height-preserving. Uses of (Ax) can be restricted to atomic : If Γ is derivable then it is derivable using only instances of (Ax) where the principal formula is atomic. This follows by induction on . When the rule (new) is required to obtain a fresh atom for (L) and (R). A right-hand form (R) of (L) is admissible: If Γ is derivable, then there is also a derivation of Γ () . The proof is a straightforward induction on derivations. Uses of (L) can be restricted to atomic : If Γ is derivable, then it has a derivation using only atomic instances of (L). This is proved by a stronger induction on the size of that an occurrence of (R) or (L) with a non-atomic principal formula can be converted to a derivation using only atomic (L) and (R) rules. This stronger invariant is needed for cases such as (L) and (R) where -rules are needed on both sides of . Finally, the atomic (R) rule can be derived from (Ax), (L), and the other nonlogical rules. General (L)/(R)slice rules: Generalized versions of the rules (L) and (R) which permit arbitrary slices instead of minimal ones are admissible. The proof requires showing that the nonlogical rules can be used to infer # for [] minimal from # for any slice () of . Soundness/Completeness: A Nominal Logic formula is a theorem if and only if is derivable in FL. This just requires checking that all the axioms of Nominal Logic are derivable and all the rules of FL are valid proof principles in Nominal Logic.
The most important property is, of course, cut-elimination.
If Γ has a derivation in FL, then it has a cut-free derivation.
This is proved as usual by first proving that (Cut) is admissible and then using admissibility finitely many times to remove all (Cut) instances from a derivation.
If Γ and Γ have cut-free derivations, then so does Γ .
Proof is by induction on , derivation Π of Γ , and derivation of Γ. In each case we either reduce the size of or stays the same but Π or is smaller. There are many cases, which can be classified into
1. base cases: Π or is (Ax), (L), or (R)
2. left-commutative cases: is not principal in Π.
3. right-commutative cases: is not principal in .
4. principal cases: is principal in both Π and .
We may assume that all instances of (Ax) and (L) are atomic in Π . Many of the cases involve only standard first-order logic rules, and their proofs are as usual. The additional left- and right-commutative cases for the new rules of FL are also straightforward. If is principal in both derivations, then there are potentially many new cases to consider. One obvious such case is when Π starts with (R) and with (L). Except for (L) and (R), all the additional rules act only on atomic formulae on the left. There are no rules with atomic formulae principal on the right, so the only new combination of rules that leads to a principal cut is (R) and (L).
Suppose the derivations Π, are respectively of the forms
where # # , and []. If and are the same term then this case is immediate. Otherwise, by appealing to the induction hypothesis twice we can conclude
The middle judgment follows by
where the () step follows because if () then
using swapping axioms and Lemma 1.
5 Variations
5.1 Global vs. Local
(new) is nondeterministic since is arbitrary. Nominal Logic has the similar axiom ( 4), which is # . Though convenient for humans this may be undesirable for search space in automated deduction. Note that a logically equivalent global variant of (new insists be “maximally fresh”; must include all variable symbols in the sequent.
where (Γ). Certainly every instance of (new is an instance of (new); the converse follows using weakening.
5.2 Substitutive vs. Parametric
(L) (R) are substitutive in that the principal formula in the lower sequent is instantiated with a specific term in the upper sequent. (R) (R) are parametric in that the principal formula in the upper sequent contains an eigenvariable (a syntactically new parameter). In this terminology (L) and (R) as given are both substitutive.
Parametric versions are possible as self-duality (4) suggests:
where [].
Call the logic FL minus (L) (R) and plus (L) (R). Clearly (L) (R) are derivable in FL using (new) and (L) (R). The converse uses (R):
Similarly for (L). Thus FL and have the same consequence relation.
5.3 Sequents vs. Natural Deduction
Two versions of Fresh Logic exist: the one in this paper which we temporarily call , and another is a Natural Deduction system [5], call it , which we mentioned previously. is better for proof-search and suggests notions of logic programming which we consider below. Conversely, is (arguably) easier to give a semantics to and we do that in [5]. We do not discuss semantics in this paper but we see no barrier to applying the same Kripke-style model in FM sets [4, 5] as we used for .
5.4 Atoms as Constants vs. Variables
Another basic design decision is whether to treat atoms as constants (AAC) or atoms as variables (AAV). Nominal Unification [12], , and recent work on Nominal Rewriting [3] make the former choice. Nominal Logic [10], FM-HOL [7], and this paper make the latter choice. Atoms-as-constants makes it much easier to test for term equality and unifiability, since equality and syntactic equality coincide for atoms. For example, the nominal unification problem () ? has multiple incomparable nominal unifiers if are variables, but only one if and are atom-constants.
Any Fresh Logic AAC proof certainly be converted to an AAV proof, by mapping atom constants injectively to new variables and augmenting the hypotheses of all judgments with freshness assertions of the form # . For example, an AAC judgment like () (), where , , and are distinct atoms and is a variable, would be translated to an AAV sequent # # # () ().
AAV is strictly more expressive than the AAC used in the works cited above: () c() is not an AAC term, because in AAC swappings are always attached directly to free variables. However if a derivable sequent in the Fresh Logic here is expressible as a sequent in the Fresh Logic in [5], then it is derivable. The derivation uses a case-analysis rule (Const) [5, Fig.3] which we apply over all possible equalities and inequalities between variables of sort atoms in the sequent.
Thus many interesting variations on the rules of FL are possible, in most cases without changing the essence of the logic. The design decisions made in this paper seem useful for manual reasoning in FL; other applications may find advantage in the alternatives.
6 Uniform Proofs in FL
The following grammars define a core logic programming language, consisting of first-order nominal Horn clause goals and program clauses:
The -free fragment is the Horn clause logic programming language. An important property of such a language is completeness of uniform proof search [8]. This is goal-directed proof search which decomposes the goal with right-rules until it is atomic, then uses just left-rules. A language of goals and program clauses is an abstract logic programming language when uniform proof search is complete; if then a uniform derivation exists.
This may fail in the presence of disjunctive program clauses: has a trivial proof using (Ax) but no uniform proof. If we decompose the goal to (or symmetrically ), then is unprovable. And indeed, and for similar reasons are not allowed in above.
Miller et al. showed uniform provability complete for first- and higher-order variants of Horn clause languages as well as for hereditary Harrop formulae, which include additional goal forms including implication and universal quantification. We now develop nominal logic programming languages which generalize first-order Horn clauses and hereditary Harrop formulae and for which an appropriate notion of uniform proof is complete. This provides a solid proof-theoretic foundation for a nominal logic programming languages such as Prolog [2].
A uniform proof in FL is a sequent proof such that for all subderivations Π concluding a non-atomic goal , the final inference rule is either an -rule or (new). A language of goals and program clauses is an abstract logic programming language if for any set Γ of program clauses and goal , the judgment Γ has a proof if and only if it has a uniform proof.
Note that (new) may be applied at any point. This is technically necessary because it cannot be permuted up past (R): the witness may mention the fresh variable generated by (new). The (L) rule also increases proof-search complexity since (modulo the other swapping laws) any two atoms may be swapped. These are important considerations for implementations. Some lessons may be drawn from previous work in FM machine deduction [7].
Call an fnhc judgment, where is a set of atomic formulae. An fnhc derivation is one all of whose judgments are fnhc. The atomic formula context is necessary because atomic equality and freshness formulae are not considered program clauses, but many rules (such as (new) (L) (R)) manipulate atomic formulae in Γ.
fnhc is an abstract logic programming language.
We must show that if Γ is derivable in FL then there is a uniform proof. It suffices to check that (1) Whenever a fnhc sequent Γ has a proof, it has a proof involving only fnhc sequents, and (2) For proofs of fnhc sequents, all of the left-rules can be permuted above the right-rules and (new). Given these facts, we can transform any proof of a fnhc sequent into a fnhc derivation and permute -rules up past -rules for a uniform proof.
The first part is a straightforward induction based on an existing model by Miller et al. [8]; note that this is where is needed. For the second part, many of the cases (and their proofs) carry over from the proof for first-order Horn clauses. It is easy to verify that (L) and the nonlogical left-rules commute up past right rules and (new). This makes sense because behaves like on the left and like on the right, and and are well-behaved on the left and right respectively.
We now consider the language of first-order nominal hereditary Harrop goals and program clauses :
Call this language fnhh. Define fnhh sequents and derivations similarly to the case for fnhc.
As with Horn clauses, Miller et al. proved that uniform proofs are complete with respect to intuitionistic provability for both first- and higher-order hereditary Harrop programs. We will show that uniform proofs are complete for fnhh programs as well.
The language fnhh is an abstract logic programming language.
As for fnhc, before, this theorem follows from two observations. First, if a fnhh sequent has any proof, then it has one in which every sequent is fnhh. This is straightforward to prove by induction. Second, any left-rule that can arise in such a proof commutes with every right-rule.
The only cases that were not already checked for fnhc involve commuting (L) and nonlogical rules upwards past (R), (), and (R). These cases are all straightforward, since behaves like on the left and nonlogical rules are generally well-behaved.
Adding atomic freshness and equality goals to fnhc or fnhh is no problem for uniform proof search since it does not comment on how atomic goals are to be derived. We have already noted that the search space for or # may be large, but this is a separate issue. In addition, adding program clauses denoting orthogonal (possibly conditional) rewriting rules as in functional logic programming seems unlikely to pose problems.
6.1 Examples
Abstractions (as developed in [4, 11]) may be incorporated into FL by adding an abstraction sort constructor A and constants : AA for each . We write for . The following additional laws are needed for abstractions (cf. axioms (A1) and (A2) of [10]):
Let Lam be a sort with constructors v : ALam, a : LamLamLam, and l : ALamLam (not to be confused with !). Then for closed terms, equality coincides with -equivalence in the usual sense: for example, l(v( l(v()).
Capture-avoiding substitution : LamALamLam can be defined using fnhc clauses in what is now a standard FM way [4]. A higher-order version : (ALam)LamLam may be defined as follows:
is total despite the precondition on the third clause: by (new), (absL), for any abstraction it is always possible to find an such that # and .
Note that this suggests an essentially algebraic approach to substitution. For any with an injection , it is possible to directly axiomatise capture-avoiding substitution as an algebraic system of equalities for a ternary operator : A, using # to avoid capture. These give ‘boiler-plate’ substitution actions similar to those offered by higher-order encodings. -conversion, typechecking, and evaluation relations can also be encoded using fnhc clauses. For example, # l( a( v())) defines -conversion.
Let Pi, Act be sorts for -calculus process/action terms with channel names encoded using A and abstraction. Transition rules can be encoded using fnhc clauses, for example:
(#) ()
(###) ()
Bisimulation can be encoded using an fnhh clause:
Also, we can reason effectively using this definition using additional proof rules for stratified definitions such as those of [9]; as discussed at the end of the next section adding such rules to FL appears to be straightforward, but is beyond the scope of this paper.
7 Encoding Generic Judgments
Miller and Tiu’s sequent calculus (a sublanguage of [9]) is first-order logic over simply-typed -terms with an additional quantifier . Like , has symmetric left- and right-introduction rules and is self-dual.
sequents have the form Σ : Γ , where is a formula in a local context , and Γ is a multiset of hypotheses with local contexts. Σ is a global context containing eigenvariables introduced by (R) and (L). The more interesting rules of are shown in Figure 5; the remaining rules are essentially ordinary sequent rules except for the presence of local contexts. The local contexts are used for the parameters introduced by the (L) and (R) rules. Local and global environments bind the names they mention, and formulae- and judgments-in-context are considered equal up to -renaming. Thus () ().
Dependence of global parameters on local parameters is encoded using raising. Thus, if the local context of the principal formula is , then the parametric rules (R) and (R) introduce a parameter of type to represent a parameter of type , where is the sequence of types of parameters in , and the application (shorthand for ) is substituted for the quantified variable.
In the substitutive rules (L) (R), the substituted term must be well-formed in the context Σ where is the local context of the principal formula. Together, these rules ensure that a formula’s validity is independent of the values of any -quantified variables.
Miller and Tiu showed how to use , an extension of with rules for definitions, as a metalanguage to encode object languages and properties of interest, including a late transition system and simulation/bisimulation for the -calculus and a simple Horn clause logic programming language interpreter.
and satisfy several common properties, for example both are self dual and commute with all propositional connectives, and
for .
However, and are not identical:
(where ()), none of these are valid for .
We now give a translation of into FL. This translation combines two essential ideas:
1. :-quantified local parameters can be modeled with -quantified atoms suitably injected into .
2. -quantified global parameters can be modeled with -quantified equivariant parameters suitably raised out of the local context .
We introduce a constructor A for each sort that provides the injection required for part (1). For part (2), we introduce a predicate () (read “ is equivariant”) for each sort which is defined as :A # . Equivariance is equivalent to invariance under arbitrary swapping.
The translation of into FL, written [[ - ]] , is given as follows:
In the cases for and , is shorthand for , where the types of the local parameters of are . The translation of a multiset Γ is the multiset containing translations of all the elements Γ. In addition, we translate term-variable environments : : to to additional hypotheses ()(). This set of assumptions helps maintain the invariant that any -quantified variable corresponds to an equivariant -quantified FL variable. The translation of a judgment Σ : Γ is [[ Σ ]] [[ Γ ]] [[ ]] .
We first state without proof that well-formed entities (contexts, propositions, terms) are transformed to corresponding well-formed FL entities. We write to distinguish the well-formedness judgments of system from the consequence judgment .
If Σ then Σ in FL and [[ Σ ]] . If Σ : then Σ [[ ]] : . If Σ then Σ [[ ]] . If Σ Γ then Σ [[ Γ ]]
Two additional important facts are the invertibility of the -rules and the fact that well-formed terms are translated to equivariant terms modulo [[ Σ ]] . We use the notations [] for the appropriate generalization of minimal slices to multiple atom-variables; the notation # indicates that all the variables among are fresh for each other and each .
Assume the variables of are distinct from (Γ). If Γ then Γ # . If Γ then Γ # .
Straightforward induction.
If Σ : then [[ Σ ]] ().
By induction on the definition of term well-formedness. For the base case , must appear in Σ, so (() is a hypothesis in [[ Σ ]] . The remaining cases follow from these easily verified properties of : (c) for any constant c; () () () for any such that Σ : , Σ : ; and (() ()) () for any such that Σ : : .
If Σ : Γ then [[ Σ ]] [[ Γ ]] [[ ]]
The proof is by induction on the structure of a -derivation. All of the cases for propositional connectives and initial sequents are straightforward induction steps. The interesting cases are those for the quantifiers. We illustrate the representative cases of (R), (R), and (R); the other three cases are symmetric.
For (R), we have
By induction we have [[ Σ ]] [[ Γ ]] [[ () ]] . Since [[ () ]] [[ ]] n [[ ]] n ]] , this derivation suffices.
For (R), we have
By induction we have a derivation of [[ (Σ) ]] [[ Γ ]] [[ ]] , or, unwinding definitions, [[ Σ ]] () [[ Γ ]] [[ ]] . Then by the right-inversion lemma for , we may derive
Then applying (R) finitely many times we obtain a derivation of [[ Σ ]] [[ Γ ]] () [[ ]] , as required for the definition of [[ ]] .
For (R), we have
Since Σ : , by Lemma 5, we have [[ Σ ]] (). Moreover is well-formed at type since Σ : . By induction, we have [[ Σ ]] [[ Γ ]] ([[ ]] ). Note that since is new, [[ ]] [[ ]] . Using right -inversion, then deriving
and using (R) finitely many times and applying the definition of [[ ]] , we see that we can derive the desired sequent.
This completes the proof.
Completeness does not hold. However, this is for no deep reason: for example, because does not allow weakening on local signatures, the judgment () is not derivable and neither is for (), whereas its translation [[ ]] [[ ]] is derivable in FL. On the other hand, the translation is at least consistent (that is, [[ Σ : Γ [[ Γ ]] is underivable, since it has no cut-free proof).
Miller and Tiu designed as one of a number of related logics. They are concerned with effectively expressing their case studies and not with relative proof-theoretic strength or semantics; there may be obvious translations between variants of , which may fail to be complete. Despite its incompleteness, therefore, the translation of into FL sheds light on the meaning of and the relation between and .
Note that is not necessarily useful by itself. Either definition rules () or equality rules () permitting case analysis are necessary for a useful metalogic. We have translations to similar extensions of FL and they pose little difficulty. The important insight is that and use -abstractions to ensure that the distinct locally-scoped parameters of cannot be unified, and FL-based extensions use freshness constraints forbidding distinct any globally-scoped atoms from being unified.
8 Conclusions
This paper has presented Fresh Logic as a modular extension of a conventional first-order sequent calculus with equality. It seems to have a good proof-theory, which we have discussed here, and a good semantics, which we discuss elsewhere [5] for a related logic. Fresh Logic is part of a growing body of work including Nominal Unification and Rewriting [12, 3], all of which use the same techniques to incorporate names and binding into existing first-order frameworks. As such FL is a useful part of an ‘FM toolkit’ for handling names and binding.
We have used FL to develop a proof-theoretic foundation for nominal logic programming with -quantified goals and program clauses and freshness and equality goals. We have shown that the concept of uniform proofs can be extended to this setting and that uniform proof search is complete for appropriate generalizations of Horn clause and hereditary Harrop formulae. We have given some examples of encoding languages and properties thereof using nominal logic programming. Much remains to be done in developing the semantics and implementation techniques needed for nominal logic programming.
Fresh Logic (and related FM work) and agree in having self-dual quantifiers and to explicitly choose fresh names, as in for example -calculus bisimulation in 6.1. This choice cannot be modeled using or quantification, because we often need to switch from considering all fresh names to some fresh name and back. Our encoding of in FL highlights the following contributions of this work: 1. We have for the first time related to ; their relationship had previously been a mystery. 2. required substantial changes to the structure of first-order judgments and rules; FL is a modular extension of traditional first-order sequent calculus. 3. The translation gives an interesting semantics to and suggests how others might be found. This is possible future work. The translation also suggests developing a logic similar in spirit and expressiveness to , but using freshness # in place of local signatures -. This may be of interest to users and designers of logical frameworks who would like to implement Miller-Tiu-like logics with a minimum of changes.
Additional directions for future work include exploring algebraic theories possible in FL, such as that of capture-avoiding substitution; applying the Curry-Howard correspondence to obtain a dependent type theory with names; and adding definitions (along the lines of ) and structural induction principles to obtain a first-order FL-based metalogic for reasoning about abstract syntax with binding. Higher-order syntax encodings either lack straightforward structural induction principles or require additional well-formedness constraints to exclude exotic terms, whereas these problems do not arise for encodings via freshness, , abstraction, and swapping, since they are essentially first-order [4, 6]; thus, we believe a metalogic based on FL would be very powerful and useful.
References
[1] Luís Caires and Luca Cardelli. A spatial logic for concurrency (part II). In CONCUR’2002 Proceedings, number 2421 in Lecture Notes in Computer Science, 2002.
[2] J. Cheney and C. Urban. System description: Alpha-Prolog, a fresh approach to logic programming modulo alpha-equivalence. In Proc. UNIF’03, pages 15–19. Universidad Politecnica de Valencia, 2003. DSIC-II/12/03.
[3] Maribel Fernández, Murdoch Gabbay, and Ian Mackie. Nominal rewriting. Submitted, January 2004.
[4] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13:341–363, 2001.
[5] Murdoch Gabbay. Fresh logic. Submitted, July 2003.
[6] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[7] Murdoch J. Gabbay. Automating fraenkel-mostowski syntax. In TPHOLs, 15th International Conference on Theorem Proving in Higher Order Logics, August 2002.
[8] Dale Miller, Gopalan Nadathur, Frank Pfenning, and Andre Scedrov. Uniform proofs as a foundation for logic programming. Annals of Pure and Applied Logic, 51:125–157, 1991.
[9] Dale Miller and Alwen Tiu. A proof theory for generic judgments: An extended abstract. In Proceedings of LICS 2003, pages 118–127. IEEE, June 2003.
[10] A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 186:165–193, 2003.
[11] M. R. Shinwell, A. M. Pitts, and M. J. Gabbay. FreshML: Programming with binders made simple. In Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden, pages 263–274. ACM Press, August 2003.
[12] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. In M. Baaz, editor, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings, volume 2803 of Lecture Notes in Computer Science, pages 513–527. Springer-Verlag, Berlin, 2003.