Curry-Style Types for Nominal Terms
Abstract. We define a rank 1 polymorphic type system for nominal terms, where typing environments type atoms, variables and function symbols. The interaction between type assumptions for atoms and substitution for variables is subtle: substitution does not avoid capture and so can move an atom into multiple different typing contexts. We give typing rules such that principal types exist and are decidable for a fixed typing environment. -equivalent nominal terms have the same types; a non-trivial result because nominal terms include explicit constructs for renaming atoms. We investigate rule formats to guarantee subject reduction. Our system is in a convenient Curry-style, so the user has no need to explicitly type abstracted atoms. Keywords: binding, polymorphism, type inference, rewriting.
1 Introduction
Nominal terms are used to specify and reason about formal languages with binding, such as logics or programming languages. Consider denumerable sets of atoms , variables , and term-formers or function symbols . Following previous work [10, 21], nominal terms are defined by:
and called respectively atoms, abstractions, function applications, tuples, and moderated variables (or just variables). We call a permutation and read () as ‘swap and in ’. We say that permutations suspend on variables. is not a term but Id is and we usually write it just as . Similarly we omit the final Id in , writing () instead of (() Id).
For example, suppose term-formers and . Then the nominal terms [] and ([]) represent -terms and (), and [] and ([]) represent -term ‘contexts’ - and (-)-. Note how occurs under different abstractions. Substitution for is grafting of syntax trees, it does not avoid capture of atoms by abstractions; we may call it instantiation.
Nominal terms differ from other treatments of syntax-with-binding because they support a capturing substitution, and the notation, although formal, is close to standard informal practice; for example -reduction may be represented simply but explicitly as ([] ) ([] ) where ([] ) is a term which may be given the behaviour of ‘non-capturing substitution’ (once we instantiate and ) by rewrite rules [10, 12].
Now consider static semantics, i.e. types like where we read as numbers and as function types. Assigning types to terms partitions the language into ‘numbers’, or ‘functions between numbers’, and so on. Java [16], ML [9], and System F [15] demonstrate how this is commercially useful and theoretically interesting.
Existing static semantics for nominal terms type atoms with a special type of atoms [21, 20]. But when we write [] or [], our intention is -or and we do not expect to be forbidden from having any type other than . We can use explicit casting function symbols to inject into other types; however the in [] still has type , so we cannot infer more about until is instantiated. This notion of typing can only usefully type terms without variables and in the presence of polymorphism such strategies break down entirely.
We now present a Curry-style system with rank 1 polymorphism (ML-style polymorphism or Hindley-Milner types [9]). Atoms can inhabit any type. We can write [], or [], or [], or ([][]), and so on, and expect the type system to make sense of these terms, even though these terms explicitly feature context holes representing unknown terms and abstractions over those holes. Different occurrences of may be under different numbers of abstractions, and for different atoms. This means that, when we instantiate with , the atoms in may move into different type contexts and so receive different types. At the same time, the entire type system is consistent with a functional intuition, so of type manages to simultaneously behave like an ‘unknown number’ and an ‘unknown term’.
We give syntax-directed typing rules and show that every typable term has a principal type (one which subsumes all others in a suitable sense) in a given environment. Type inference is decidable and types are compatible with -equivalence on nominal terms. We give a notion of typable rewrite rule such that rewriting preserves types. In future, we plan to extend the system with intersection types, to derive a system with principal typings (a type and a type environment which subsume all others). With this system we will study normalisation of nominal terms.
2 Background
We continue the notation from the Introduction. Write () for the variables in and () for the atoms in (e.g., ([][]()), ([][]())). We define , the permutation action of on , inductively by:
Id and (() ) ()(), where
Define [], the (term-)substitution of for in , by:
[] ()[] ([]) ()[] ()
Term-substitutions are defined by Id [] and have an action given by Id and ([]) ([]). We write substitutions postfix, and write for composition of substitutions: () ().
Nominal syntax represents systems with binding, closely following informal notation. See [21, 10, 11] for examples and discussions of nominal terms and nominal rewriting. It has the same applications as higher-order systems such as Klop’s CRSs, Khasidashvili’s ERSs, and Nipkow’s HRSs [18, 17, 19]. Intuitively, the distinctive features of nominal syntax are:
– is an ‘unknown term’; the substitution action [] which does not avoid capture, makes this formal. Therefore behaves differently from ‘free variables’ of systems such as HRSs [19] or meta-variables of CRSs [18].
– [] denotes ‘ with abstracted in ’. We do not work modulo -equivalence and [] and [] are not equal in any sense; for example ([])[] [] and ([])[] [], and we certainly expect from the intuition ‘’ and ‘’ that [] and [] should not be equal. Therefore atoms in nominal terms also behave differently from ‘bound variables’ of systems such as HRSs, ERSs and CRSs.
We call occurrences of abstracted when they are in the scope of []-, and otherwise we may call them unabstracted.
– () represents ‘ with and swapped’. So [] [], and ()[][] [][](). Therefore this permutation action is distinct from De Bruijn’s transformers and other explicit substitutions, which avoid capture as they distribute under abstractions, and which do not satisfy the same simple algebraic laws [7]. We now come to some of the more technical machinery which gives nominal terms their power.
We call # a freshness constraint, and an equality constraint. We will use letters to range over constraints. We introduce a notion of derivation as follows (below denote two different atoms):
Here we write (the inverse of ) for the permutation obtained by reversing the order of the list of swappings; for example (() ())-1 ) (). Here () () () is the difference set. For example (() Id so () follows from # and #. Also [] [] and [] [] but not [] []; this is what we would expect.
Write for sets of freshness constraints of the form # and call these freshness contexts. We write for an arbitrary set of freshness and equality constraints; we may call a problem. Substitutions act on constraints and problems in the natural way. Write when a derivation of exists using elements of as assumptions, and extend this notation elementwise to for deducibility of all (see [21, 11] for algorithms to check constraints). For example, means that the constraints obtained by applying the substitution to each term in can be derived from . We will use this notation in the definition of matching in Section 4.1.
The following result is one of the main technical correctness properties of nominal terms, and we should compare it with Theorem 8.
If # and then #.
Proofs, and further properties of nominal terms, are in [21, 12].
3 Typing
3.1 Types and type schemes
We consider denumerable sets of
– base data types (write a typical element ), e.g. is a base data type for numbers;
– type variables (write a typical variable );
– type-formers (write a typical element ), e.g. is a type-former.
Types , type-schemes , and type-declarations (or arities) are defined by:
denotes any finite set of type variables (if empty we omit the entirely); we call them bound in and call free any type variables mentioned in and not in . We write () for the set of type variables in , and for equality modulo -equivalence for bound variables.1
We call a product and [] an abstraction type. We say that is a constructed type, and we associate a type declaration to each term-former. For example, we can have : () and 0 : () (we may write just 0 : in this case).
Basic type substitution [] is the usual inductive replacement of for every in ; base cases are [] and [] . We extend the action elementwise to arities , for example (())[] []([]), and to type-schemes in the usual capture-avoiding manner. For example:
Type substitutions , , are defined by Id [] where Id is the identity substitution: Id by definition (we also use Id for the identity substitution on terms, but the context will always indicate which one we need). has an action on types , schemes , and arities , given by the action of Id and by extending the basic action of the last paragraph. We write application on the right as , and write composition of substitutions just as , meaning apply then apply . The domain of a substitution , denoted (), is the set of type variables such that .
Substitutions are partially ordered by instantiation. Write mgu() (most general unifier) for a least element such that (if one exists). We refer the reader to [1] for detailed definitions and algorithms for calculating mgu.
Write when and for some which instantiates only type variables in . may contain other type variables; only bound type variables in may be instantiated, for example () () but () ().
Also write when for some . In effect all variables in arities are bound, but since they are all bound we do not write the . For example () () ().
The following useful technical result follows by an easy induction:
If then [] []. Also if then [].
3.2 Typing judgements
A typing context is a set of pairs ( : ) or ( : ) subject to the condition that if ( : ) ( : ) then , similarly for .
We write : for updated with (: ), where this means either (: ) or ((: )) (: ) as well-formedness demands. Similarly we write : . For example, if : then : denotes the context : . We say that (or rather its association with a type) is overwritten in . We write for the typing context obtained by applying to the types in . Similarly, denotes the context obtained by applying to the atoms in . () denotes the set of type variables occurring free in .
A typing judgement is a tuple ; : where is a typing context, a freshness context, a term and a type (when is empty we omit the ;).
We inductively define derivable typing judgements as follows:
Here ; : holds if, for any such that , # or : : for some . The condition : () is shorthand for : and (). The way we set things up, the arity of is fixed and is independent of . In the rule for abstractions the type environment is updated.
We may write ‘; : ’ for ‘; : is derivable’.
To understand the condition in the second rule, note that represents an unknown term in which permutes atoms. Unlike non-nominal -equivalence, -equivalence on nominal terms exists in the presence of unknowns for which substitution does not avoid capture, as ([])[] demonstrates and as the rules and show. Our typing system is designed to be compatible with this relation and so must be sophisticated in its treatment of permutations acting on unknowns. For concreteness take ) and any term . If : then () : should hold when at least one of the following conditions is satisfied:
1. () so that cannot ‘tell the difference between and in ’.
2. If and occur in then they are abstracted, so that what says about and gets overwritten.
Given , and , if there exists such that ; : is derivable, then we say ; is typable. Otherwise say ; is untypable.
The following are examples of derivable typing judgements:
The first line of examples just illustrates some basic typings, and the use of . The second line illustrates typing abstractions and how this overwrites in . The third line illustrates how permutations are typed. The last three illustrate interactions between typing and (multiple) abstractions and free occurrences of atoms. Note that : : () : and : : ; # () : .
If ; : then []; : [].
By induction on the derivation, using Lemma 2 for the side-conditions.
If ;: and : for some , then (); ():.
By induction on the type derivation: The case for atoms is trivial. In the case of a variable, the side condition holds since and have the same type in . The other cases follow directly by induction.
3.3 Principal types
A typing problem is a triple (), written: ; :?. A solution to ; :? is a pair () of a type-substitution and a type such that ; :. We write for the restriction of to ().
For example, solutions to ::: ():? are (Id) and ([]). Note that a solution may instantiate type-variables in .
Solutions have a natural ordering given by instantiation of substitutions:
we call () an instance of () using . A minimal element in a set of solutions is called a principal solution. By our definitions there may be many principal solutions; (Id) and (Id) are both principal for : :?. As in the case of most general unifiers, principal solutions for a typable ; are unique modulo renamings of type-variables. In a moment we show that the following algorithm calculates principal solutions:
The partial function (; ) is defined inductively by:
– (:; Id), where are assumed fresh (not in ) without loss of generality.
– (:; ) (again are assumed fresh) provided that for each in such that , we have #, or otherwise : : for some that are unifiable. The substitution is the mgu of those pairs, or Id if all such are fresh for .
– (; () where (; ), (; ), . . . , (; ).
– (; ) where (; ), : () where the type variables in are chosen distinct from those in and , and ().
– (; [] []) where (:; ), is chosen fresh, . Here : denotes with any type information about overwritten to :, as discussed in Subsection 3.2.
(; ) may be undefined; Theorem 5 proves that is untypable in the environment ; .
The definition above generalises the Hindley-Milner system [9] for the -calculus with arbitrary function symbols , as is standard in typing algorithms for rewrite systems [2], and with atoms and variables (representing ‘unknown terms’) with suspended atoms-permutations.
The treatment of typing for atoms, abstraction and moderated variables is new; for example if : : : , then []() : [] but not []() : []. However, [] : [] as expected.
(; ) gives a static semantics in the form of a most general type to , given a typing of atoms and variables mentioned in , and information about what atoms may be forbidden from occurring in some variables.
1. If (; ) is defined and equal to () then ; : is derivable.
2. Let be a substitution such that () (). If ; : is derivable then (; ) is defined and () is one of its instances.
That is: (1) “(; ) solves (; :?)”, and (2) “any solution to (; :?) is an instance of (; )”.
The first part is by a routine induction on the derivation of (; ) (using Lemma 3), which we omit. The second part is by induction on the syntax of :
– Suppose ; : . Examining the typing rules, we see that : and : , that ; : , and that for some acting only on ( acts trivially on because we assume was chosen fresh). Hence, for each such that , we have #, or, for some , : : , that is, : : . Let be the mgu of all such pairs , so (we take Id if there are no pairs to consider). Thus, (; ). Therefore, ().
– Suppose ; : . Clearly is typable in the context ; so (examining the typing rules) : must occur in and (; Id). It is now not hard to satisfy ourselves that (Id) is principal.
– Suppose ; []:. This may happen if and only if [] and ([]) solves : ; :?, where is fresh for . By inductive hypothesis ([]) is an instance of (( : ; ), that is, there is a substitution such that [, . By definition, (; [] []) where . So () and . Therefore ( []) is an instance of ( []).
– The cases for () and are long, but routine.
; is typable if and only if (; Id) for some .
3.4 -equivalence and types
We now prove that -equivalence respects types; so our static semantics correctly handles swappings and variables whose substitution can move atoms into new abstracted (typing) contexts. We need some definitions: Given two type contexts and , write for that context obtained by updating with typings in , overwriting the typings in if necessary. For example if : and : : then : : . If and mention disjoint sets of atoms and variables (we say they are disjoint) then is just a set union.
1. If ; : then ; : , provided that and are disjoint. Call this type weakening.
2. If : ; : then ; : provided that #. Call this type strengthening (for atoms).
3. If : ; : then ; : provided does not occur in . Call this type strengthening (for variables).
By induction on the derivation. For the second part, if occurs in under an abstraction, then : is overwritten whenever is used.
and ; : imply ; : .
By induction on the size of (). The form of is rather restricted by our assumption that — for example if then for some . We use this information without commment in the proof.
– Suppose and ; : . There is nothing to prove.
– Suppose [] [] and ; [] : . Then , and [], and : ; : . We use the inductive hypothesis to deduce that : ; : and concluce that ; [] : [].
– Suppose [] [] and ; [] : . Then by properties of [21, Theorem 2.11] we know ()# ()#. Also [] and : ; : . By Lemma 7 (Weakening) also : : ; : . By equivariance (Lemma 4) () : :
has on and is overwritten). So : : ; : . We conclude that : : ; [] : []. Since #[] and #[] by Lemma 7 (strengthening for atoms) we have ; [] : [].
– Suppose and suppose ; : . Then ()#, and : , and , and ; : .
– The cases of and () follow easily.
implies (; (; ) modulo renamings of type variables, for all such that either side of the equality is defined.
4 Rewriting
We now consider how to make a notion of nominal rewriting (i.e., a theory of general directed equalities on nominal terms [12]) interact correctly with our type system. We start with some definitions taken from [12].
A nominal rewrite rule is a tuple of a freshness context , and terms and such that () (). Write for that rule obtained by swapping and in throughout. For example, if # [] () then # [] (). Let and ). Let range over (possibly infinite) sets of rewrite rules. Call equivariant when if then for all distinct atoms . A nominal rewrite system is an equivariant set of nominal rewrite rules.
Say a term has a position at when it mentions once, with the permutation Id. We may call a hole. Write [] for [].2 We would usually call a ‘context’ but we have already used this word so we will avoid it. For example, and [] have positions at , but () and () do not. We may make nameless and write it just -.
Suppose (; Id) and suppose that mentions no type-schemes. All the recursive calls involved in calculating (; ) have the form (; ) where is a subterm of and contains only type assumptions for atoms. We will call recursive calls of the form (; ) variable typings of ; : .
Note that there is one variable typing for each occurrence of a variable in , and they are uniquely defined modulo renaming of type variables. Also, may affect but not since we assume that (; Id).
Let (; ) be a variable typing of ; : , and let be the subset of such that ()#. We call ; : an essential typing of ; : .
So the essential typings of : : : (() []): [] are:
The essential typings of : : : ; # (() []): [] are:
We will talk about the typing at a position in a term; for example the typing at in ( [])[ ()] in the first example above (with hole named ) is : : : () : .
4.1 Matching problems
A (typed) matching problem (; ) (; ) is a pair of tuples ( and are typing contexts, and are freshness contexts, and are terms) such that the variables and type-variables mentioned on the left-hand side are disjoint from those mentioned in , and such that mentions no atoms or type-schemes.
Below, will be the left-hand side of a rule and will be a term to reduce. The condition that mentions no atoms or type-schemes may seem strong, but is all we need: we give applications in Section 4.3.
Intuitively, we want to make the term on the left-hand side of the matching problem -equivalent to the term on the right-hand side. Formally, a solution to this matching problem, if it exists, is the least pair () of a type- and term-substitution (the ordering on substitutions extends to pairs component-wise) such that:
1. for (), for ()3, and .
2. (; Id), (; Id), and for each ; : an essential typing in ; : , we have (); () : .
The first condition defines a matching solution for untyped nominal terms (see [21, 12] for more details on untyped nominal matching algorithms). The last condition enforces type consistency: the terms should have compatible types, and the solution should instantiate the variables in a way that is compatible with the typing assumptions. When the latter holds, we say that () respects the essential typings of ; : in the context ; .
For example, (:) (:) has solution ([] []), whereas (:) (:) has no solution — on the right is too general.
To see why we need to check in the second condition, consider the term () where : () and : (), that is both functions are polymorphic, and produce a result of type . Then the untyped matching problem ()) () has a solution (Id), but the typed matching problem ( : ()) (()) has none: fails the last condition since is required to have type but it is instantiated with a boolean.
4.2 Typed rewriting
A (typed) rewrite rule ; : is a tuple of a type context which only types the variables in and has no type-schemes (in particular, mentions no atoms), a freshness context , and terms and such that
1. () (),
2. (; Id) and ; : .
3. Essential typings of ; : are also essential typings of ; : .
The first condition is standard. The second condition says that is typable using and , and is typable with a type at least as general. The third condition ensures a consistency best explained by violating it: Let : ([]), then : ([]) : passes the first two conditions, but fails the third because in the right-hand side we have an essential typing : : whereas in the left-hand side we have : : : . For comparison, : ([]) [] : [] with : ([])[] passes all three conditions and is a valid rewrite rule, as well as : ; #([]) .
The rewrite relation is defined on terms-in-context: Take ; and ; , and a rule ; : , such that () (, and () ( (renaming variables in if necessary). Assume ; is typable: (; Id), [] and ; : is the typing of at the corresponding position. We say that rewrites with to in the context ; and write ; when:
1. (; ) (; ) has solution ().
2. [] . These conditions are inherited from nominal rewriting [10, 12] and extended with types. Instantiation of does not avoid capture, so an atom introduced by a substitution may appear under different abstractions in different parts of a term. We must pay attention to the typing at the position of the variable in the rewrite; essential typings do just this. For example if : (), : ()[] and : [] : [] then ( : Id []) and : [] : []. satisfies the first two conditions in the definition of typed rule but fails the third: the only essential typing in the left-hand side is : : , whereas in the right-hand side we have : : : . Notice that : () : [] and the typed matching problem ( : ) (: ()) has a solution (Id). So, if we ignore the third condition in the definition of typed rule, we have a rewriting step : () []() which does not preserve types: : () : [] but : []() : [].
We need a lemma to prove Subject Reduction (Theorem 11):
Suppose that ; : , where types only variables in (it mentions no atoms) and has no type schemes. Let be a substitution instantiating all variables in , and such that () respects the essential typings of ; : in the context , that is, for each essential typing ; : of ; : , it is the case that ; () : . Then ; : .
(Subject Reduction) Let ; : . If ; : and ; then ; : .
It suffices to prove that if (; Id) and ; then ; : . Suppose ; . Then (using the notation in the definition of matching and rewriting above) we know that:
1. [], , and .
2. acts nontrivially only on the variables in , not those in .
3. Assuming ; : is the typing of , then ; () : for each essential typing ; : in ; : (therefore also for each essential typing in ; : since they are a subset).
4. (; Id) and (Id) so there is some such that and .
5. [] .
By Theorem 8, from 3, 4 and 1 we deduce ; : . Since (; (Id), by our assumptions on rewrite rules also ; : , and by Lemma 3 also ; : . By Lemma 10, ; : . Since , by Lemma 3 also ; : . Hence ; [] : as required.
4.3 Examples
Untyped -calculus. Suppose a type and term-formers : ([]), : (), and : ([]), sugared to [], , and []. Rewrite rules satisfying the conditions in Definition 8 are:
The freshness conditions are exactly what is needed so that no atom moves across the scope of an abstraction (which might change its type). For instance, in rule :; #[] :, is under an abstraction for in the left-hand side and not in the right-hand side, but we have #.
The typed -calculus Suppose a type-former of arity 2 and term-formers : ([])(), : (), and : ([]). Sugar as in the previous example, so, instead of ([]) we write []. Then the following rewrite rules satisfy the conditions in Definition 8:
For the -reduction rule we mention two variants; they give the same rewrites:
:[] : ()() : : : ([])([]) :
Assume types and . Then : : (([]) ([])) : and
[] takes different types just like in the Hindley-Milner type system; ([]Id). Our system will not type : : or [] — the system for the untyped -calculus above, types the second term.
Surjective pairing Rewrites for surjective pairing cannot be implemented by a compositional translation to -calculus terms [4]. Our system deals with rules defining surjective pairing directly; assume : () and : ():
Higher-order logic. Extend the typed -calculus above with a type and term-formers : , : ), : ([]), : (), and so on. Rewrite rules include:
Arithmetic Extend further with a type , term-formers 0 : , : (), ) and =: (). Observe that []() has principal type whereas []0 has principal type . Likewise, []( = 0) is typable (with type ) whereas []([]() = 0) is not typable.
5 Conclusions and future work
We have defined a syntax-directed type inference algorithm for nominal terms. It smoothly resolves the tension between the denotational intuition of a type as a set, and the syntactic intuition of a variable in nominal terms as a term which may mention atoms. The algorithm delivers principal types (our function ). The types produced resemble the Hindley-Milner polymorphic type system for the -calculus, but are acting on nominal terms which include variables representing context holes as well as atoms representing program variables, and such that the same atom may occur in many different abstraction contexts and thus may acquire different types in different parts of the term.
Theorem 8 proves our types compatible with the powerful notion of -equivalence inherited from nominal terms [21]. Theorem 11 shows that a notion of typed nominal rewrite rule exists which guarantees preservation of types.
Our system is in Curry style; type annotations on terms are not required. We do rely on type declarations for function symbols (arities) and in future we may investigate inferring the type of a function from its rewrite rules.
Type inference is well-studied for the -calculus and Curry-style systems also exist for first-order rewriting systems [2] and algebraic -calculi (which combine term rewriting and -calculus) [3]. We know of no type assignment system for the standard higher-order rewriting formats (HRSs use a typed metalanguage, and restrict rewrite rules to base types).
Our type system has only rank 1 polymorphism (type-variables are quantified, if at all, only at the top level of the type). It should be possible to consider more powerful systems, for instance using rank 2 polymorphic types, or intersection types [6]. The latter have been successfully used to provide characterisations of normalisation properties of -terms. Normalisation of nominal rewriting using type systems is itself a subject for future work, and one of our long-term goals in this work is to come closer to applying logical semantics such as intersection types, to nominal rewriting.
References
1. F. Baader and W. Snyder, Unification Theory, Handbook of Automated Reasoning, volume I, chapter 8, 445–532. A. Robinson and A. Voronkov (eds.), Elsevier Science, 2001.
2. S. van Bakel and M. Fernández. Normalization results for typable rewrite systems. Information and Computation, 133(2):73–116, 1997.
3. F. Barbanera and M. Fernández. Intersection type assignment systems with higher-order algebraic rewriting. Theoretical Computer Science, 170:173–207, 1996.
4. H. P. Barendregt, Pairing without conventional constraints, Zeitschrift für mathematischen Logik und Grundlagen der Mathematik 20 (1974), 289–306.
5. H. P. Barendregt, Lambda Calculi With Types, Handbook of Logic in Computer Science, Oxford University Press, S. Abramsky, D. Gabbay and T. S. E. Maibaum (eds.), 1992.
6. H. P. Barendregt, M. Coppo and M. Dezani-Ciancaglini, A filter lambda model and the completeness of type assignment. Journal of Symbolic Logic, 48(4):931–940, 1983.
7. S. Berghofer and C. Urban, A Head-to-Head Comparison of de Bruijn Indices and Names. LFMTP’06, 46–59, 2006.
8. H. B. Curry and R. Feys, Combinatory Logic, volume 1. North Holland,1958.
9. L. M. M. Damas and R. Milner, Principal Type Schemes for Functional programs, Conference Record of the Ninth Annual ACM Symposium on Principles of Programming Languages, 1982.
10. M. Fernández, M. J. Gabbay and I. Mackie, Nominal Rewriting Systems, ACM Symposium on Principles and Practice of Declarative Programming (PPDP’04), ACM Press, 2004.
11. M. Fernández and M. J. Gabbay, Nominal Rewriting with Name Generation: Abstraction vs. Locality, ACM Symposium on Principles and Practice of Declarative Programming (PPDP’05), ACM Press, 2005.
12. M. Fernández and M. J. Gabbay, Nominal Rewriting, Information and Computation, to appear, available from http://dx.doi.org/10.1016/j.ic.2006.12.002.
13. M. J. Gabbay and A. M. Pitts, A New Approach to Abstract Syntax with Variable Binding. Formal Aspects of Computing, vol. 13, pp. 341–363, 2002.
14. M. J. Gabbay. A Theory of Inductive Definitions with Alpha-Equivalence. PhD Thesis, Cambridge University, 2000.
15. J-Y. Girard, The System of Variable Types, Fifteen Years Later, Theoretical Computer Science, 45, 1986.
16. J. Gosling, B. Joy, and G. Steele. The Java Language Specification. Addison-Wesley, Reading, MA, 1996.
17. Z. Khasidashvili, Expression reduction systems, Proceedings of I.Vekua Institute of Applied Mathematics (Tbisili), vol. 36, 1990, pp. 200–220.
18. J.-W. Klop, V. van Oostrom, and F. van Raamsdonk, Combinatory reduction systems, introduction and survey, Theoretical Computer Science 121 (1993), 279– 308.
19. R. Mayr and T. Nipkow, Higher-order rewrite systems and their confluence, Theoretical Computer Science 192 (1998), 3–29.
20. M. R. Shinwell, A. M. Pitts, and Murdoch Gabbay, FreshML: Programming with binders made simple, ICFP 2003, pp. 263–274.
21. C. Urban, A. M. Pitts, and M. J. Gabbay, Nominal unification, Theoretical Computer Science, 323, pp. 473–497, 2004.
Notes
Research partially supported by the EPSRC (EP/D501016/1 “CANS”). ↩
1 We could express types too using nominal syntax. We use the standard informal treatment because we focus on the term language in this paper. ↩
2 Here ‘positions’ are based on substitution and not paths in the abstract syntax tree as in [10]. The equivalence is immediate since substitution is grafting. ↩
3 So in particular, by the side-conditions on variables being disjoint between left and right of the problem, for () and for (). ↩