Principal Types for Nominal Theories
Abstract. We define rank 1 polymorphic types for nominal rewrite rules and equations. Typing environments type atoms, variables, and function symbols, and since we follow a Curry-style approach there is no need to fully annotate terms with types. Our system has principal types, and we give rule and axiom formats to guarantee preservation of types under both rewriting and equality reasoning. This is non-trivial because substitution does not avoid capture, so a substituted symbol can—if we are not careful—appear in inconsistent typing contexts. Keywords: binding, polymorphism, type inference, rewriting.
1 Introduction
Suppose we want to specify -calculus -equivalence. We might well write this:
Equalities like this are typical, and appear in specifications of the -calculus (as above), substitution, logic with quantifiers, -calculus, and more. They have common features as annotated above. To formalise and reason with this kind of systems, in this paper we follow the nominal approach:
– Nominal terms directly represent syntax with binding using term-formers, two levels of variable, and freshness side-conditions [20]. The terms and side-conditions above can be represented symbol-for-symbol in a formal syntax.
– Equality on nominal terms can be formalised in nominal rewriting [10] (for oriented equality) and nominal algebra [14] (for unoriented equality).
– Nominal terms can be given Hindley-Milner style types [9]. Given a type environment, principal types for nominal terms can be automatically deduced.
This paper combines types and equality reasoning—so we type terms and equations between them. This is not trivial because equality gives terms a dynamic behaviour, and type systems must ensure types are robust with respect to it.
For a large class of closed theories, corresponding to what can be defined in higher-order rewriting and equality reasoning, nominal rewriting is sound and complete for nominal algebra [11]. The technical contributions of this paper are notions of typeable closed rewrite rule and equality axiom such that types are preserved under rewriting and equality reasoning respectively. To ensure this, closedness and principal types play a key role, as our examples will demonstrate. Related work. Nominal terms support a capturing substitution and the notation, though formal, is close to standard informal practice. For example -reduction may be represented as app(lam[] ) sub([] ) where sub([] ) is a term which may be given the behaviour of ‘non-capturing substitution’ by rewrite rules [12,10].
Now consider static semantics, i.e. types like for numbers and for functions. Assigning types to terms partitions the language into ‘numbers’, or ‘functions between numbers’, and so on. This paper will not make the case for types but the interested reader can find compelling practical and theoretical motivations elsewhere, e.g. Java [17], ML [7], and System F [16].
Two approaches have been used to give static semantics for nominal terms: In e.g. [20,19,18] atoms have a special type of atoms . But, when we write lam[] or lam[] to represent - (a term with a hole, or context) or , we might not expect to be forbidden from having any type other than . We can use explicit casting function symbols to inject into other types; but the in lam[] still has type , so we cannot infer more about until is instantiated. This notion of typing is useful for terms without variables or in systems without polymorphism. So an alternative approach was proposed in [9] which allows atoms to inhabit any type. It follows a Curry-style approach, and has rank 1 polymorphism (ML-style polymorphism or Hindley-Milner types [7]); that is, types are assigned to terms without requiring type annotations for atoms or variables. Thus, we can write lam[], or fix[], or forall[], or app(lam[] lam[]), and so on, and expect the type system to make sense of this. The syntax-directed typing rules for nominal terms given in [9] guarantee that every typeable term has a principal type (one which subsumes all others in a suitable sense) in a given environment, and types are compatible with -equivalence on nominal terms. Type inference is decidable and an algorithm to compute principal types has been implemented [8].
In [9], a notion of typed nominal rewriting rule is given, with a condition to ensure type preservation under rewriting. In this paper we consider also nominal equational axioms, and give sufficient conditions for type preservation under rewriting and equational deduction that are intuitive and easy to implement.
Overview of the paper. In Section 2 we recall nominal rewriting and equational reasoning, as well as the Curry-style type system for nominal terms. Section 3 gives examples to motivate the design of the type system for rules and equations. Section 4 contains the main results of the paper: it defines closed rules and the closed rewrite relation (which is sound and complete for nominal equational reasoning when the axioms are closed), and presents a notion of typeable rule and typeable axiom that guarantee that rewriting and equational reasoning preserve types. Finally, in Section 5 we draw conclusions and discuss future work.
2 Background
In this section we recall the main notions underlying the nominal approach to the specification of systems with binders. We focus on equational specifications.
Fix denumerable sets of atoms, variables, and term-formers. will range over distinct atoms, over distinct variables, and f g over distinct term-formers. A permutation is a bijection on atoms such that nontriv(() is finite. Nominal terms are defined by:
is a (moderated) variable; [] is an atom-abstraction. We write () for the variables in and () for the atoms in (so ([] and ( nontriv()). We write () for the swapping permutation mapping to , to , and all other to themselves; id for the identity permutation (so id(); for composition (so ()((()) and for inverse).
A substitution is a map from variables to terms. Write [] for the substitution mapping to and all other to id .
Permutation and substitutions act on terms:
-equality and freshness are defined by the following rules, where (() () is the difference set of , :
The intuition of # is ‘ is not free in ’, the intuition of is ‘ and are -equivalent’. Both are conditional on freshness assumptions on the variables . So freshness contexts , , . . . , are finite sets of freshness constraints #, and we write # when # follows from ; similarly for .
For example, [][] and (() id so ##(); see [20,10] for more examples.
We now recall the Curry-style type system from [9], which can typecheck nominal terms even if they contain variables (representing unknown subterms); see [8] for an implementation in Haskell.
Fix denumerable sets of base data types (e.g. , ), type variables (e.g. ), and type-formers (e.g. C , List). Types , type-schemes , and type-declarations (arities) are generated by:
denotes any finite set of type variables (if empty we omit ); call them bound in and call free type variables mentioned in not in . Write TV () for the set of type variables in , and for equality modulo -equivalence.1
We associate a type declaration to each term-former. E.g. we can have succ : () and 0 : () (we may write just 0 : in this case).
Type substitutions , , are finite partial functions from type variables to types. Write [] for the partial function just mapping to , and id for the identity substitution. Substitutions act on types, type schemes and arities as usual; application is written and composition (apply then ). Write when and for with domain in . may contain other type variables; only bound type variables in may be instantiated; so () () but () (). Write when for some . All variables in arities are bound, but since they are all bound we omit .
A typing context is a partial function from atoms and variables to type schemes, with finite domain. We write : for updated with : , that is, (: ) : . Similarly we write : . We write for the typing context obtained by applying to the types in . Similarly, denotes the context obtained by applying to the atoms in . TV () 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 separating ‘;’). Define derivable typing judgements by:
; : holds if, for any such that , # or : : for some . The condition f : () is shorthand for f : and (). If ; : for some then call ; typeable; otherwise call it untypeable.
represents an unknown term in which permutes atoms. The second rule ensures compatibility between this and -equivalence (see Theorem 4 below) since substitution does not avoid capture: e.g. ([])[].
We refer the reader to [9] for examples and give just the typing of one term here: ([]() [][]()) : []() [][]() ).
If ; : then []; : [].
If ;: and : for some , then ; ():.
and ; : imply ; : .
A typing problem is a triple ; , and its solution is a pair () of a type-substitution and a type such that ; :. Write for the restriction of to TV (). Solutions are naturally ordered by instantiation of substitutions; call a minimal element in a set of solutions principal.
Principal solutions for ; are unique modulo renaming type-variables. A function pt to compute principal types, generalising Hindley-Milner [7] to nominal terms, is given in [9, Definition 4]: pt(; ) is a principal solution () such that ; : , and is undefined if is untypeable in ; .
1. Type weakening: If ; : then ; : , provided that and are disjoint.
2. Type strengthening for atoms: If : ; : then ; : provided that #.
3. Type strengthening for variables: If : ; : then ; : provided does not occur in .
We now introduce nominal algebra [14] and nominal rewriting [10]. See [11] for a detailed treatment of their connections.
An equality judgement is a tuple of a freshness context and two terms. Similarly a rewrite judgement is a tuple . An equational theory T Ax) is a pair of a signature and a possibly infinite set of equality judgements Ax (axioms) in . A rewrite theory R Rw) is a pair of and a possibly infinite set of rewrite judgements Rw (rewrite rules) in . Where is clear, we identify T with Ax and R with Rw.
Write () for , . . . , . A position is a pair () of a term and a distinguished unknown that occurs precisely once in , as id. If ) then we write [] for [].
Nominal rewriting: The one-step rewrite relation is the least relation such that for every () R, freshness context , position , term , permutation , and substitution ,
The rewrite relation is the reflexive transitive closure of the one-step rewrite relation. So, in particular, implies .
Nominal algebra: is the least transitive reflexive symmetric relation such that for every () T, freshness context , position , permutation , substitution , and fresh (so if # then ()),
3 Examples
Consider a type and term-formers lam : ([]), app : () and sub : ([]), sugared to [], , and []. Then : ([]) : by Definition 2. The function pt can automatically infer this type and a most general type for , namely , since lam : ([]). Anticipating Section 4, here are rewrite rules for -reduction (note typing and freshness conditions in rules); types of abstracted atoms can be inferred and are :
And here is an equality axiom for : :; #[](:.
Rewriting and axioms are used to compute and reason with terms—not only ground terms, but also terms with variables. Types should be compatible with the resulting dynamics on terms. Since a variable might occur several times in a term, under different abstractions, the interaction between types and rewriting or equational reasoning is subtle. Closedness [10] ensures the interaction between abstractions and variables is safe. Later we leverage this to conditions on closed rewrite rules and axioms to ensure also type preservation. E.g. the rules for and (as a rewrite or an equality) preserve types. Thus, the type of : []() is preserved in the reduced term : .
We get more interesting types for -terms with a type-former of arity 2 and term-formers : ([])(), : (()), and : (([])). As before, write ([]) as []. Then the following rules preserve types:
Assume types and . Then :: (([]) ([])) : and :: (([]) ([])) () : .
[] takes different types just like in the Hindley-Milner type system; pt([]id). Our system will not type :: or []— the previous system with a unique type types the second term.
Below we show that is compatible with this notion of type: :; # []( : . A term obtained from a typeable term by typed equational reasoning is also typeable.
4 Types for (closed) nominal rewriting and algebra
We recall closed rewrite rules [10] and closed equational axioms [11], then give conditions to ensure nominal rewriting and equational reasoning preserve types.
4.1 Closed rules and closed rewriting
Intuitively, a closed term has no unabstracted atoms and all occurrences of (representing an unknown subterm) appear under the same abstracted atoms. So f([]) is not closed since is abstracted in the first but not the second, and # f([]) is closed, since the freshness constraint ensures that cannot occur in . Closedness was introduced in [12]. Definition 8 tests to check for closedness using freshened variants [10] (inductive definitions are also possible [6,13]).
A freshened variant of is in which atoms and unknowns have been replaced by ‘fresh’ atoms and unknowns (not in () and (), and perhaps also fresh for some atoms and unknowns from other syntax, which we will always specify). We omit an inductive definition. Similarly, if is a freshness context then will denote a freshened variant of (so if # then #, where and are fresh for the atoms and unknowns of ). We may extend this to other syntax, like equality and rewrite judgements. If is a freshened variant of then () (.
For example: [][] is a freshened variant of [][], # is a freshened variant of #, and is a freshened variant of .
Call closed when there exists a substitution with dom() () such that ()#() ()
Call ) and ) closed when () is closed. Given a rewrite rule ) and a term-in-context , the (one-step) closed rewriting relation holds if there are and , such that, for a freshened variant of (fresh for , , , ):
Closed rewriting is the reflexive transitive closure, as in Def. 7.
The choice of freshened variant in Definition 8 does not matter. Closed rewriting is sound and complete for nominal algebra, if all axioms are closed [11].
4.2 Typed closed rewriting
We define a notion typeable rule such that rewriting preserves types:
A typeable closed 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. pt(; id) and ; : ,
3. is closed, where is a variant of in which each abstracted atom is decorated by appending the type of that atom to its name; a renamed atom occurring in a freshness constraint in is replaced by new freshness constraints, one for each differently decorated variant of the atom.
For example, under the signature f : ([]), g: ([]), the variant of the rule : ; # f([]) g([]) : used in the third condition in Definition 9 is : ; ## f([]) g([]). The condition is satisfied: although one occurrence of is under an abstraction for and the other is under an abstraction for , we have freshness assumptions for both atoms: ##.
The type decorations for can be determined mechanically by running pt to compute principal types on the left-hand side and right-hand side of .
The first condition in the definition of typeable closed rule is standard. The second condition says that is typeable using and , and is typeable with a type at least as general. The third condition ensures that atom abstractions are typed in a consistent manner throughout the rule. To check this, we compute types for the abstracted atoms using the type inference algorithm, and annotate atom abstractions with types. In a Church-style system, we would use the type annotations provided by the user; thanks to the type inference algorithm, in our system users need not provide explicit type annotations for every abstraction.
The typed closed rewriting relation is defined using typed matching.
A (typed) matching problem (; ) (; ) is a pair of tuples ( and are typing contexts, and are freshness contexts, and are terms) such that variables and type-variables on the left are disjoint from those in , and mentions no atoms or type-schemes.
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 TV ()2, and .
2. pt(; id), pt(; id), and for each : , we have ; : , where and contains the typings for the atoms abstracted above an occurrence of in and which may occur in instances of .
That is: we want to make on the left -equivalent to on the right. The first condition defines a matching solution for untyped nominal terms [20,10]. The last condition enforces type consistency: terms should have compatible types, and the solution should instantiate the variables consistent with the typing assumptions. For typeable closed rules, the typing context is uniquely defined.
The assumption that mentions no atoms or type-schemes may seem strong, but is all we need: we give applications in Section 4.4.
For example, (:) (:) has solution ([] []), whereas (:) (:) has no solution— on the right is too general.
To see why we must check in the second condition, consider g(f True) where g: () and f : () (i.e. both functions are polymorphic and produce a result of type ) and a rule : g(f ) suc , where suc: (). Then the untyped matching problem g(f )) g(f True) has solution [True], but the typed matching problem ( : g(f )) ( g(f True)) has none: [True] fails the last condition since should have type but is instantiated with a Boolean. If matching did not fail, this rewrite would not preserve types.
Take a typeable term ; : and a typeable closed rule ; : . Assume [] and ; : is the typing of at the corresponding position in .3 We say closed rewrites with to in the context ; and write ; when there is some a freshened variant of (fresh for , , , , and ), where is the freshness context () # (), such that:
1. The typed matching problem (; ) (; ) has solution ().
2. [] .
The conditions of typed closed rewriting extend those of closed nominal rewriting, with types. The following lemma, proved by induction, is used to prove that rewriting preserves types:
Consider ; , where is either the right-hand side of a typeable closed rule ; : or a subterm of the right hand side; if is under atom abstractions in , we assume where contains the atom typings of the removed atom abstractions. Assume ; (so if ) and let () be the substitutions that solve the typed matching problem (; ) (; ). Then ; : .
Let ; : be a typeable closed rule. If ; : and ; then ; : .
It suffices to prove that if pt(; id) and ; then ; : . Suppose ; . Then (using the notation in the definition of matching and rewriting above) we know that:
1. is a freshened variant of (fresh for , , , , and ) and is the freshness context () # ().
2. [], , and # for each # in .
3. ; : is the typing of , and by the Weakening Lemma 6, also ; .
4. pt(; id) and pt(id) so there is some such that and .
5. [] .
By Theorem 4 (-equivalence respects types), and 1, 2 and 3, we deduce ; : . Since pt(; id), by our assumptions on rewrite rules also ; : , and by Lemma 3 also ; : . Since respects the context ; by definition of typed matching, then, by the auxiliary lemma 12, ; : . Hence ; [] : . By Theorem 4, also ; : , and since () (by definition of closed rewriting), then ; : as required.
Closure ensures that for each occurrence of in and , instantiation behaves uniformly with respect to abstraction. This alone does not ensure preservation of types under reduction: consider f : ([]), g : ([]), suc : (). The rule : f[] g[] : is closed, and the principal type of the left-hand side is also the type of the right-hand side, but the term f[]suc() : rewrites to g[]suc(), which is untypeable. Each in and must be under the same abstractions, typed in the same way. So condition 3 of Definition 9 annotates abstracted atoms in with types.
4.3 Typed equational reasoning
A typeable closed axiom ; : is a tuple of a type context which only types the variables in and and has no type-schemes (so mentions no atoms), a freshness context , and terms and such that pt(; pt(; id) and is closed, where is a decorated version of from Definition 11.
Typed nominal equational reasoning is defined as in Definition 7, but with the additional requirement that the substitution applied to and solves typed matching problems, that is, it must respect the types given in the typing context. Thus, using Lemma 12, equational deduction preserves types.
Let T be a nominal theory with only typeable closed axioms. If ; : and ; is in the typeable nominal equality relation generated from T by typed nominal reasoning, then ; : .
By induction on nominal algebra equality. The interesting case is the use of the rule (), for a typeable closed axiom ; : in . The conditions in Definition 14 ensure that pt(; pt(; ). Since the substitution used to instantiate and to derive ; respects ; (it solves typed matching problems), we can proceed as for Theorem 13.
4.4 Examples
Rewrites for surjective pairing cannot be implemented by compositional translation to -calculus [3]. We can define it; assume fst : () and snd : ():
Consider a type o and term-formers : o, : (o o)o, : ()o, : ([]o)o, and substitution : ([]o)o sugared as before. Rewrite rules for equality and simplification for (a fragment of) first-order logic are typeable closed; we use infix notation for the binary connectives:
Using [] as syntactic sugar for the term ([]) representing the substitution of by in , we also have the following typeable closed axioms:
We can extend this with arithmetic. Consider a type , term-formers 0 : , succ : (), ). Then []() has principal type []o, and []( 0) is typeable (with type o) whereas []( 0) is not typeable.
We can also axiomatise the -calculus by these equalities [15], using the notation introduced in Section 3:
All are typeable closed axioms except for the last, which is not closed: it contains a free atom on the left hand side and the atoms in an instance of on the left are under the scope of an abstraction for , but they escape the abstraction on the right. The results presented here do not apply to this rule. Non-closed rules are arguably rare (and the standard higher-order rewriting formalisms do not accept them), but interesting examples exist—in this case, the rule is needed for completeness with respect to the models [15]. We conjecture that an extension with essential typings [9] (type assignments need not be unique but every type assignment for an occurrence of a variable on the right must have already been made for an occurrence of on the left) would let us deal with non-closed rules or axioms like this.
5 Conclusions and future work
Type inference is well-studied for the -calculus and Curry-style systems also exist for first-order rewriting systems [1] and algebraic -calculi (which combine term rewriting and -calculus) [2]. 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 system is in Curry style; type annotations on terms are not required. We do rely on type declarations for term-formers (arities) and in future we may investigate conditions under which this assumption and the closedness assumptions could be relaxed.
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.
The function is implemented [8]. The conditions on typeable closed rules and typeable closed axioms are decidable and easily mechanisable using and nominal matching, which is also implemented [5].
Theorem 4 proves our types compatible with the powerful notion of -equivalence inherited from nominal terms [20]. Theorem 13 shows that a notion of typeable closed nominal rewrite rule exists which guarantees the preservation of types under closed nominal rewriting. Theorem 15 shows that types are also preserved under equational reasoning using a notion of typeable closed axioms.
Our type system has rank 1 polymorphism. More powerful systems, e.g. rank 2 polymorphic types or intersection types [4], should be possible. The latter have been used to characterise normalisation properties of -terms. Normalisation of nominal rewriting using type systems is a subject for future work, and one of our long-term goals is to come closer to applying logical semantics such as intersection types, to nominal rewriting.
References
1. Steffen van Bakel and Maribel Fernández, Normalization results for typeable rewrite systems, Information and Computation 133 (1997), no. 2, 73–116.
2. Franco Barbanera and Maribel Fernández, Intersection type assignment systems with higher-order algebraic rewriting, Theoretical Computer Science 170 (1996), 173–207.
3. Henk P. Barendregt, Pairing without conventional constraints, Zeitschrift für mathematischen Logik und Grundlagen der Mathematik 20 (1974), 289–306.
4. Henk P. Barendregt, Mario Coppo, and Mariangiola Dezani Ciancaglini, A filter lambda model and the completeness of type assignment, Journal of Symbolic Logic 48 (1983), no. 4, 931–940.
5. Christophe Calvès, Complexity and implementation of nominal algorithms, Ph.D. thesis, King’s College London, 2010.
6. Ranald Clouston, Closed terms (unpublished notes), http://users.cecs.anu.edu.au/~rclouston/closedterms.pdf, 2007.
7. Luis Damas and Robin Milner, Principal type-schemes for functional programs, Proceedings of the 9th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages (POPL 82), ACM, 1982, pp. 207–212.
8. Elliot Fairweather, Principal types for nominal terms: tool description, Available from http://www.inf.kcl.ac.uk/pg/elliotf/research.
9. Maribel Fernández and Murdoch J. Gabbay, Curry-style types for nominal terms, Types for Proofs and Programs (TYPES 06), Lecture Notes in Computer Science, vol. 4502, Springer, September 2007, pp. 125–139.
10., Nominal rewriting (journal version), Information and Computation 205 (2007), no. 6, 917–965.
11., Closed nominal rewriting and efficiently computable nominal algebra equality, Proceedings of the 5th International Workshop on Logical Frameworks and Meta-Languages (LFMTP 2010), 2010.
12. Maribel Fernández, Murdoch J. Gabbay, and Ian Mackie, Nominal Rewriting Systems, Proceedings of the 6th ACM SIGPLAN symposium on Principles and Practice of Declarative Programming (PPDP 2004), ACM Press, August 2004, pp. 108–119.
13. Murdoch J. Gabbay, Nominal terms and nominal logics: from foundations to meta-mathematics, Handbook of Philosphical Logic, vol. 17, Kluwer, 2011.
14. Murdoch J. Gabbay and Aad Mathijssen, Nominal universal algebra: equational logic with names and binding, Journal of Logic and Computation 19 (2009), no. 6, 1455–1508.
15., A nominal axiomatisation of the lambda-calculus, Journal of Logic and Computation 20 (2010), no. 2, 501–531.
16. Jean-Yves Girard, The system of variable types, fifteen years later, Theoretical Computer Science 45 (1986).
17. James Gosling, Bill Joy, and Guy Steele, The Java language specification, Addison-Wesley, 1996.
18. Andrew M. Pitts, Nominal system T, Proceedings of the 37th ACM SIGACT-SIGPLAN Symposium on Principles of Programming Languages (POPL 2010), ACM Press, January 2010, pp. 159–170.
19. Mark R. Shinwell, Andrew M. Pitts, and Murdoch J. Gabbay, FreshML: Programming with Binders Made Simple, Proceedings of the 8th ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), vol. 38, ACM Press, August 2003, pp. 263–274.
20. Christian Urban, Andrew M. Pitts, and Murdoch J. Gabbay, Nominal Unification, Theoretical Computer Science 323 (2004), no. 1–3, 473–497.
Acknowledgements. Thanks to the anonymous referees. Supported by grant RYC-2006-002131 at the Polytechnic University of Madrid.
Notes
1 Types could be expressed in nominal syntax; our focus here is the term language. ↩
2 So in particular, by the side-conditions on variables being disjoint between left and right of the problem, for () and for TV (). ↩
, and if contains abstractions over . ↩