R. Backhouse and J. N. Oliveira (Eds.): MPC 2000, LNCS 1837, pp. 230–255, 2000.
A Metalanguage for Programming with Bound Names Modulo Renaming
Cambridge University Computer Laboratory, Cambridge CB2 3QG, UK
Department of Pure Mathematics and Mathematical Statistics, Cambridge University, Cambridge CB2 1SB, UK
Abstract. This paper describes work in progress on the design of an ML-style metalanguage FreshML for programming with recursively defined functions on user-defined, concrete data types whose constructors may involve variable binding. Up to operational equivalence, values of such FreshML data types can faithfully encode terms modulo -conversion for a wide range of object languages in a straightforward fashion. The design of FreshML is ‘semantically driven’, in that it arises from the model of variable binding in set theory with atoms given by the authors in [7]. The language has a type constructor for abstractions over names ( atoms) and facilities for declaring locally fresh names. Moreover, recursive definitions can use a form of pattern-matching on bound names in abstractions. The crucial point is that the FreshML type system ensures that these features can only be used in well-typed programs in ways that are insensitive to renaming of bound names.
1 Introduction
This paper concerns the design of functional programming languages for metaprogramming, by which we mean the activity of creating software systems— interpreters, compilers, proof checkers, proof assistants, and so on—that manipulate syntactical structures. An important part of such activity is the design of data structures to represent the terms of formal languages. The nature of such an object language will of course depend upon the particular application. It might be a language for programming, or one for reasoning, for example. But one thing is certain: in all but the most trivial cases, the object language will involve variable binding, with associated notions of free and bound variables, renaming of bound variables, substitution of terms for free variables, and so on. It is this aspect of representing object languages in metaprogramming languages upon which we focus here.
Modern functional programming languages permit user-defined data types, with pattern matching in definitions of functions on these data types. For object languages without variable binding, this reduces the work involved in designing representations to a mere act of declaration: a specification of the abstract syntax of the object language gives rise more or less directly to the declaration of some algebraic data types (mutually recursive ones in general). Consider the familiar example of the language of terms of the untyped lambda calculus
and a corresponding ML data type
where ranges over some fixed countably infinite set of variable symbols which we have chosen to represent by values of the ML type of character strings. This gives a one-one representation of the abstract syntax trees of all (open or closed) untyped lambda terms as closed ML values of type . However, the ML declaration takes no account of the fact that the term former involves variable binding. Thus, if one wishes to identify terms of the object language up to renaming of bound variables (as one often does), such representations are too concrete. It is entirely up to programmers to ensure that their term manipulating programs respect the renaming discipline—an obligation which becomes irksome and error prone for complex object languages, or large programs.
A common way round this problem is to introduce a new version of the object language that eliminates variable binding constructs through the use of de Bruijn indices [4]. For example, ‘nameless’ lambda terms are given by
and a corresponding ML data type by
where the indices are natural numbers, represented by the values of a suitable ML data type . Closed ML values of type correspond to nameless terms , which in turn correspond to -equivalence classes of ordinary lambda terms (open or closed). Hence functions manipulating lambda terms modulo -conversion can be defined, and their properties proved, using structural recursion and induction for the algebraic data type . This approach has been adopted for a number of large systems written in ML involving syntax manipulation (such as HOL [8] and Isabelle [14], for example). However, it does have some drawbacks. Firstly, nameless terms are hard for humans to understand and they need translation and display functions relating them to the usual syntax with named bound variables. Secondly, some definitions (such as substitution and weakening the context of free variables) are non-intuitive and error-prone when cast in terms of de Bruijn indices. Lastly, and most importantly, the ML language does not have any built-in support that might alleviate these problems: one usually starts with a specification of an object language in terms of context free grammars and some indication of the binding constructs and has to craft its ‘name free’ representation by hand. Perhaps more can be done automatically? In this paper we describe an ML-like language with features that address these difficulties and provide improved automatic support for metaprogramming with variable binding constructs. The key innovation is to deduce at compile-time not only traditional type information, but also information about the ‘freshness’ of object-level variables. This information is used to guarantee that at run-time the observable behaviour of well-typed meta-level expressions is insensitive to renaming bound object-level variables. Thus, users are notified at compile-time if their syntax-manipulating code descends below the level of abstraction which identifies -equivalent object-level expressions.
Our language design is guided by the mathematical model of binding operations introduced in [7] using a Fraenkel-Mostowski permutation model of sets with atoms. A key feature of this model is that it provides a syntax-independent notion of a name (i.e. an atom) being fresh for a given object. For this reason the resulting programming language is called FreshML. Figure 1 gives some sample FreshML declarations which continue the running example of the untyped lambda calculus. They will be used in the rest of this paper to illustrate the features of the new language. We attempt to explain FreshML without assuming knowledge of the mathematics underlying our model of binding; for the interested reader, the intended model of FreshML is sketched in an Appendix to this paper. Sections 2–5 describe the novel features of FreshML compared with ML, namely atoms, freshness, atom abstraction/concretion and pattern matching with abstraction patterns. Sections 6–8 discuss the interaction of these features with standard ones for equality, recursive functions and types not involving atoms. It should be stressed that the design of FreshML is still evolving: section 9 discusses some of the possibilities and reviews related work.
Note (Meta-level versus object-level binding).The metalanguage FreshML provides a novel treatment of binding operations in object languages. However, in describing FreshML syntax we treat its various binding constructs in a conventional way—by first giving their abstract syntax and then defining what the free, bound and binding identifiers are in such expressions. This in turn gives rise to a conventional definition of the capture-avoiding substitution of a FreshML expression for all free occurrences of an identifier in an expression . We write for the finite set of free identifiers in .
2 Freshness
Variables of object languages are represented in FreshML by value identifiers of a special built-in type of atoms. Operationally speaking, behaves somewhat like the ML type , but the way in which dynamically created values of type (which are drawn from a fixed, countably infinite set of semantic atoms) can be used is tightly constrained by the FreshML type system, as described below. Just as addresses of references do not occur explicitly in ML programs, semantic atoms do not occur explicitly in the syntax of FreshML. Rather, they can be referred to via a local declaration of the form
where is an identifier implicitly of type . This is a binding operation: free occurrences of in the expression are bound in . Its behaviour is analogous to the Standard ML declaration
in that the expression in (5) is evaluated by associating with the first semantic atom unused by the current value environment and then evaluating in that augmented value environment. (We formulate this more precisely at the end of this section.) As in ML, evaluation in FreshML is done after type checking, and it is there that an important difference between the expressions in (5) and (6) shows up. Compared with ML’s type-checking of the expression in (6), the FreshML type system imposes a restriction on the expression in (5) which always seems to be present in uses of ‘fresh names’ in informal syntax-manipulating algorithms, namely that
expressions in the scope of a fresh name only use it in ways that are insensitive to renaming.
For example, although has type in ML, the expression is not typeable in FreshML—the meaning of is clearly sensitive to renaming . On the other hand, in the next section we introduce atom-abstraction expressions such as , whose meaning (either operationally or denotationally) is insensitive to renaming even though they contain free occurrences of , giving rise to well typed expressions such as . (Some other examples of well typed -expressions are given in Fig. 1.)
Type System. To achieve the restrictions mentioned above, the FreshML type system deduces for an expression judgments not only about its type, , but also about which atoms are fresh with respect to it,
Here is some value identifier assigned type by the typing context . FreshML typing contexts may contain both typing assumptions about value identifiers, , and freshness assumptions about them, (if contains such an assumption it must also contain and for some type ). The intended meaning of statements such as ‘’ is that, in the given value environment, the denotation of (an element of an FM-set) does not contain the semantic atom associated to in its support—the mathematical notions of ‘FM-set’ and ‘support’ are explained in the Appendix (see Definitions A.1 and A.2). Here we just give rules for inductively generating typing and freshness judgements that are sound for this notion. In fact it is convenient to give an expression’s typing and freshness properties simultaneously, using assertions of the form standing for the conjunction
Thus the FreshML type system can be specified using judgments of the form
where
and
— are distinct value identifiers which include all the free identifiers of the FreshML expression ;
— and are FreshML types ;
— and are finite sets of value identifiers with the property that each is assigned type by the typing context, i.e. is equal to one of the with .
We write as an abbreviation for . When discussing just the freshness properties of an expression, we write to mean that holds for some type .
The rule for generating type and freshness information for -expressions is (11) in Fig. 2. The notation used there indicates the context obtained from by adding the assumptions and for each value identifier declared in (where we assume does not occur in ). For example, if , then
The side condition in rule (11) is comparable to ones for more familiar binding constructs, such as function abstraction; given and , within the -equivalence class of the expression we have room to choose the bound identifier so that the side condition is satisfied.
To understand rule (11) better, consider the special case when and are empty. This tells us that a closed expression of the form has type if not only , but also . This second property guarantees that although may involve the atom , its meaning is unchanged if we rename —and hence it is meaningful to ‘anonymise’ in by forming the expression .
But how do we generate the freshness assertions needed in the hypothesis of rule (11) in the first place? One rather trivial source arises from the fact that if is fresh for all the free identifiers in an expression , then it is fresh for itself (this is a derivable property of the FreshML type system); so in particular is always fresh for closed expressions. However, it can indeed be the case that holds with occurring freely in . Section 3 introduces the principal source of such non-trivial instances of freshness.
Operational Semantics. At the beginning of this section we said that the operational behaviour of the FreshML expression is like that of the ML expression . In order to be more precise, we need to describe the operational semantics of FreshML. The current experimental version of FreshML is a pure functional programming language, in the sense that the only effects of expression evaluation are either to produce a value or to not terminate. We describe evaluation of expressions using a judgement of the form
where is a value environment (whose domain contains the free value identifiers of ) and is a semantic value. These are mutually recursively defined as follows: is a finite mapping from value identifiers to semantic values; and, for the fragment of FreshML typed in Fig. 2, we can take to be given by the grammar
where ranges over semantic atoms, over value identifiers, and over expressions. The rule for evaluating -expressions is (24) in Fig. 3. The notation used in that rule stands for the finite set of ‘synthetically’ free semantic atoms of a value environment ; this is defined by
where and
It should be emphasised that the rules in Fig. 3 are only applied to well-typed expressions. Evaluation preserves typing and freshness information in the following sense.
If , and , then and . (The definitions of ‘ ’ and ‘ ’ for the fragment of FreshML typed in Fig. 2 are given in Fig. 4)
3 Atom Abstraction
FreshML user-declared data types can have value constructors involving binding, via a type constructor for atom abstractions. The data type declared in Fig. 1 provides an example of this, with its constructor . Expressions of an atom abstraction type are introduced with a syntactic form which is written , where is a value identifier of type and an expression of type . Such atom abstraction expressions behave like pairs in which the first component is hidden, in a way comparable to hiding in abstract data types [13]. The operations for accessing the second component are discussed in Sects 4 and 5. We claim that two such expressions, and , are contextually equivalent (i.e. are interchangeable in any complete FreshML program without affecting the observable results of evaluating it) if and only if
for some (any) fresh , and are contextually equivalent expressions of type
where indicates the expression obtained by interchanging all occurrences of and in . It is for this reason that values of type correspond to -equivalence classes of lambda terms: see [7, Theorem 2.1].
Atom abstraction expressions are evaluated using rule (25) in Fig. 3; and their typing and freshness properties are given by rule (12) in Fig. 2. In that rule, the notation means the finite set ; and the side-condition means that, with as in equation (9), for some with . To understand rule (12) better, consider the special case when : then the rule tells us that provided and is typeable in context , then is always fresh for , i.e. . This is the principal source of freshness assertions in FreshML. For example:
Given the declarations in Fig. 1 and some straightforward rules for typing data type constructors (which we omit, but which are analogous to the rules (16) and (17) for and pairs in Fig. 2), from rule (12) we have
and then
Applying rule (11) to this yields
This closed expression of type is a FreshML representation of the lambda term .
Note that atom abstraction is not a binder in FreshML: the free identifiers of are and all those of . The syntactic restriction that the expression to the left of the ‘abstraction dot’ be an identifier is needed because we only consider freshness assertions ‘’ with an identifier rather than a compound expression (in order to keep the type system as simple as possible). This does not really restrict the expressiveness of FreshML, since a more general form of atom abstraction ‘ ’ (with of type ) can be simulated with the -expression . (The typing rule for -expressions is (19) in Fig. 2.)
Example 3.1 illustrates the fact that, unlike metalanguages that represent object-level binding via lambda abstraction, FreshML separates the renaming and the hiding aspects of variable binding. On the one hand is still a free identifier in , but on the other hand the fact that is a statically scoped binder can be used to hide the name of an atom (subject to the freshness conditions discussed in Sect. 2). We illustrate why this separation of the renaming and the hiding aspects of variable binding can be convenient in Example 4.1 below. To give the example we first have to discuss mechanisms for computing with expressions of atom abstraction type . FreshML offers two related alternatives: concretion expressions, , and -expressions using abstraction patterns, such as . We discuss each in turn.
4 Concretion
Values of atom abstraction type have a double nature. So far we have seen their pair-like aspect; but as noted in [7, Lemma 4.1], they also have a function-like aspect: we can choose the name of the first component in an atom abstraction as we like, subject to a certain freshness restriction, and then the second component turns out to be a function of that choice, which we write as . We call the concretion of the atom abstraction at the atom . The typing and freshness properties of concretions are given by rule (13) in Fig. 2. Note in particular (taking in the rule) that given , in order to deduce we need to know not only that , but also that . The denotational justification for this is given by Proposition A.2 of the Appendix. Operationally, the behaviour of concretion is given by rule (26) in Fig. 3. Thus evaluation of proceeds by first evaluating ; if a semantic value of the form is returned and the semantic atom associated with in the current value environment is , then the result of evaluating is the semantic value obtained from by interchanging all occurrences of and in . By analogy with -conversion for -abstraction and application, it is tempting to replace the use of transposition by substitution , but this would not be correct. The reason for this has to do with the fact that while is used to represent binding in object languages, it is not itself a binding operation in FreshML; so the substitution can give rise to capture at the object-level in a way which cannot. Here is an example to illustrate this: the result of evaluating
in the value environment is . Using instead of one would obtain the wrong value, namely , which is semantically distinct from (in as much as the two semantic values have different denotations in the FM-sets model—see Sect. A.4).
Here is an example combining atom abstraction, concretion and local freshness expressions (together with standard -expressions and function declaration).
This illustrates the use of the fact mentioned in Remark 3.2 that name abstraction and name hiding are separated in FreshML: note that in the definition of , the locally fresh atom is not used in an abstraction immediately, but rather at two places nested within its scope ( and ).
The bijection in this example can be coded even more perspicuously using pattern matching:
Expressions like ‘’ are abstraction patterns. The fact that there is a useful matching mechanism for them is one of the major innovations of FreshML and we discuss it next.
5 Matching with Atom Abstraction Patterns
It is not possible to split semantic values of type into (atom,value)-pairs uniquely, because given then for any , has the same denotation as . However, if we only use the second component in a way that is insensitive to which particular fresh is chosen, we get a well-defined means of specifying a function on atom abstractions via matching against an abstraction pattern. The simplest example of such a pattern takes the form , where and are distinct identifiers. Rule (14) in Fig. 2 gives the typing and freshness properties and rule (27) in Fig. 3 the evaluation properties for a -expression with a single match using such a pattern. (In the expression , the distinct identifiers and are binders with as their scope.)
Figure 1 gives some examples of declarations involving more complicated, nested abstraction patterns. We omit the formal definition of matching against such patterns, but the general idea is that atom identifiers to the left of an ‘abstraction dot’ in a pattern represent semantic atoms that are fresh in the appropriate sense; and by checking freshness assertions, the type system ensures that the expression to the right of ‘’ in a match uses such identifiers in a way that is insensitive to renaming. For example, this implicit freshness in matching is what ensures that in Fig. 1 implements capture-avoiding substitution—in the last match clause, is automatically fresh for and so it makes sense to apply the substitution function under . Another example is the declaration in Fig. 1, which does not type check because in the last match clause is not fresh for .
In the current experimental version of FreshML, all uses of abstraction patterns are eliminated by macro-expanding them using concretion and local freshness. For example, as rules (14) and (27) may suggest, can be regarded as an abbreviation for
(where ). However, to accommodate the more general notions of abstraction mentioned at the end of Sect. 9, we expect that matching with abstraction patterns will have to be a language primitive.
According to its Definition [12], in Standard ML during type checking a pattern elaborates in the presence of a typing context to a piece of typing context (giving the types of the identifiers in the pattern) and a type (the overall type of the pattern); then a match elaborates in the context to a function type if has type in the augmented context . Pattern elaboration is a little more complicated in FreshML. For abstraction patterns generate not only a piece of typing context , but also two kinds of freshness assumptions: ones that modify (cf. the use of in rule (14)); and ones that impose freshness restrictions on in a match (cf. the use of in rule (14)).
In Example 4.1 we gave an example where the use of abstraction patterns allows a simplification compared with code written just using the combination of -expressions and concretion. Sometimes the reverse is the case. For example, in informal practice when specifying a function of finitely many abstractions, it is convenient to use the same name for the abstracted variable (and there is no loss of generality in doing this, up to -conversion). This is not possible using FreshML patterns because, as in ML, we insist that they be linear: an identifier must occur at most once in a pattern. However, it is possible through explicit use of a locally fresh atom. Here is a specific example.
In the FM-sets model (see the Appendix), the atom abstraction set-former commutes with cartesian products up to natural bijection. We can code this bijection in FreshML using pattern-matching as follows.
Better would be
but an arguably clearer declaration (certainly a more symmetric one) uses local freshness explicitly:
Simplest of all would be the declaration
but this is not legal, because is not a linear pattern. As we discuss in the next section, is an equality type; so matching patterns with repeated occurrences of identifiers of that type is meaningful (although patterns like involve a further complication, in that the repeated identifier is in a ‘negative position’, i.e. to the left of the ‘abstraction dot’). We have insisted on linear patterns in the current version of FreshML in order not to further complicate a notion of matching which, as we have seen, is already more complicated than in ML.
6 Atom Equality
Algorithms for manipulating syntax frequently make use of the decidability of equality of names (of object level variables, for example). Accordingly, the type of atoms in FreshML admits equality. In particular if and are two expressions of type , then is a boolean expression which evaluates to if and evaluate to the same semantic atom and evaluates to if they evaluate to different ones. What more need one say? In fact, when it comes to type checking there is more to say. To see why, consider the following declaration of a function taking a list of atoms with one atom abstracted and removing it.
This makes use of a form of conditional
which branches on the equality of and —see rules (28) and (29) in Fig. 3. For the above declaration of to type-check as a function , one has to apply rule (11) to the subphrase . Amongst other things, this requires one to prove
in a typing context whose only freshness assumptions are and . For this to be possible we have to give a typing rule for which, while checking the second branch of the conditional, adds the semantically correct information to the typing context. Such a typing rule is (15) in Fig. 2. (This uses the notation to indicate the typing context obtained from by adding the assumption ; we omit the straightforward formal definition of this for the typing contexts defined as in equation (9).) Although we take account of the fact that and denote distinct atoms when checking the second branch of the conditional, we have not found a need in practice to take account of the fact that they denote the same atom when checking the first branch (by strengthening the second hypothesis of this rule to , for example.)
To get information about atom equality to where it is needed for type checking, FreshML also permits the use of guarded patterns
where and are value identifiers of type . Such guards are inter-definable with the construct, but often more convenient. Figure 1 gives several examples of their use. We omit the precise definition of matching such guarded patterns. Note also that the atom equality test expression can be regarded as a macro for
7 Functions
Recall from Sect. 2 that the intended meaning of freshness assertions in FreshML has to do with the notion of the ‘support’ of an element of an FM-set (see Definition A.1 in the Appendix). The nature of this notion is such that in any reasonable (recursively presented) type system for FreshML, the provable freshness assertions will always be a proper subset of those which are satisfied by the FM-sets model. This is because of the logical complexity of the statement
‘the semantic atom associated with the identifier is not in the support of the denotation of the function expression ’
which involves extensional equality of mathematical functions. So if ‘provable freshness’ only gives an approximation to ‘not in the support of’, we should expect that not every denotationally sensible expression will receive a type. (Of course, such a situation is not uncommon for static analyses of properties of functional languages.)
What approximation of the support of a function should be used to infer sound freshness information for function expressions in FreshML? We certainly want type-checking to be decidable. In the current experimental version of FreshML, we take a simple approach (which does ensure decidability) making use of the following general property of freshness
if is fresh for all the free identifiers in an expression , then it is fresh for itself
which is certainly sound for the denotational semantics in . Applying this in the case when is a recursive function expression
we arrive the typing rule (20) given in Fig. 2. As usual, free occurrences of and in become bound in the expression (36). We can regard non-recursive function expressions as the special case of expression (36) in which .
Consider the following FreshML declaration of a function for computing the list (possibly with repetitions) of free variables of a lambda term encoded as a value of the data type in Fig. 1.
This uses auxiliary functions for joining two lists, and for removing an atom from a list of atoms (using the fact that is an equality type), whose standard definitions we omit.
One might hope that is assigned type , but the current FreshML type system rejects it as untypeable. The problem is the last match clause,. As explained in Sect. 5, for this to type check we have to prove
This is denotationally correct, because the denotation of maps a semantic atom and a list of semantic atoms to the list ; and the support of the latter consists of all the semantic atoms in the list that are not equal to . However, the typing rules in Fig. 2 are not sufficiently strong to deduce (37).
It seems that this problem, and others like it, can be solved by using a richer notion of type in which expressions like ‘’ become first-class types which can be mixed with the other type constructors (in particular, with function types). We have made some initial investigations into the properties of such richer type systems (and associated notions of subtyping induced by making a subtype of ), but much remains to be done. However, for this particular example there is a simple work-around which involves making better use of atom-abstractions and the basic fact (12) about their support. Thus the declaration of in Fig. 1 makes use of the auxiliary function for which
can be deduced using (12). It follows that does yield a function of type (and its denotation is indeed the function returning the list of free variables of a lambda term).
Note that freshness is not a ‘logical relation’: just because a function maps all arguments not having a given atom in their support to results not having that atom in their support, it does not follow that the atom is fresh for the function itself. Thus the following rule is unsound.
To see this, consider the following example. From rule (12) we have
and so using the above rule (wrong!) we would be able to deduce
This is denotationally incorrect, because the denotation of does contain the denotation of in its support. Correspondingly, the operational behaviour of this function expression depends on which semantic atom is associated with : if we replace by in , then under the assumption we get a contextually inequivalent function expression, . For applying these function expressions to the same argument yields contextually inequivalent results (in the first case an expression equivalent to and in the second case one equivalent to ).
8 Purity
Consider the following declaration of a function for computing the number of lambda abstractions in a lambda term encoded as a value of the data type in Fig. 1.
For this to type check as a function , the last match clause requires
to be proved. The interpretation of this judgement holds in the FM-sets model because the denotation of is a ‘pure’ FM-set, i.e. one whose elements all have empty support. Accordingly, we add rule (22) in Fig. 2 to the FreshML type system; using it, we do indeed get that has type . The condition ‘’ in the hypothesis of this rule is defined by induction on the structure of the type and amounts to saying that does not involve or in its construction.
The current experimental version of FreshML is a pure functional programming language, in the sense that the only effects of expression evaluation are either to produce a value or to not terminate. This has an influence on the soundness of rule (22). For example, if we add to the language an exception mechanism in which exception packets contain values involving atoms, then it may no longer be the case that an integer expression satisfies for any atom . To restore the soundness of rule (22) in the presence of such computational effects with non-trivial support, one might consider imposing a ‘value restriction’, by insisting that the rule only applies to expressions that are non-expansive in the sense of [12, Sect. 4.7]. However, note that the rule (19) for -expressions rather undoes such a value-restriction. For using rule (19), the freshness properties of which we could have deduced from the unrestricted rule (22) can be deduced for the semantically equivalent expression from the value-restricted version. This highlights the fact that the soundness of rule (19), and also rules (14) and (18) in Fig. 2, depends upon the evaluation of not producing an effect with non-empty support. Should one try to restrict these rules as well? Probably it is better to curtail the computational effects. For example, although it is certainly desirable to add an exception-handling mechanism to the current version of the language, it may be sufficient to have one which only raises packets containing values with empty support (character strings, integers, etc). Investigation of this is a matter for future work—which brings us to our final section.
9 Related and Future Work
Related work
The model presented in [7] was one of three works on the metamathematics of syntax with binders using categories of (pre)sheaves which appeared simultaneously in 1999—the other two being [5] and [9]. The starting point for these works is a discovery, made independently by several of the authors, which can be stated roughly as follows.
The quotient by -equivalence of an inductively defined set of abstract syntax trees (for some signature involving binders) can be given an initial algebra semantics provided one works with initial algebras of functors not on sets, but on categories of ‘variable’ sets, i.e. certain categories of sheaves or presheaves.
There is a strong connection between initial algebras for functors and recursive data types, so this observation should have some consequences for programming language design, and more specifically, for new forms of user declared data type. That is what we have investigated here. For us, the notion of (finite) support, which is a key feature of the model in [7], was crucial—giving rise as it does to FreshML’s idiom of computing with freshness. While the presheaf models considered in [5] have weaker notions of support (or ‘stage’) than does the FM-sets model, it seems that they too can model languages with notions of abstraction similar to the one in FreshML (Plotkin, private communication).
Miller [10] proposed tackling the problems motivating the work in this paper by incorporating the techniques of higher order abstract syntax, HOAS [16], into an ML-like programming language, , with intentional function types . Compared with HOAS, the approach in [7] and [5] is less ambitious in what it seeks to lift to the metalevel: like HOAS we promote object-level renaming to the metalevel, but unlike HOAS we leave object-level substitution to be defined case-by-case using structural recursion. The advantage is that FreshML data types using retain the pleasant recursion/induction properties of classical first order algebraic data types: see Sect. 5 of [7]. It is also the case that names of bound variables are inaccessible to the programmer, whereas they are accessible to a FreshML programmer in a controlled way.
Formal properties of FreshML
In this paper we have mostly concentrated on explaining the ideas behind our approach and giving examples, rather than on presenting the formal properties of the language. Such properties include:
1. Decidability of type/freshness inference.
2. Correspondence results connecting the operational and denotational semantics.
3. The correctness of the encoding of the set of terms over a ‘binding signature’ [5, Sect. 2], modulo renaming of bound variables, as a suitable FreshML data type. For example, values of type in Fig. 1 modulo contextual equivalence (or equality of denotations) correspond to -equivalence classes of untyped lambda terms, with free identifiers of type corresponding to free variables.
4. Transfer of principles of structural induction for inductively defined FM-sets involving atom abstraction (cf. [7, Sect. 5]) to induction principles for FreshML data types. More generally, the ‘-quantifier’ introduced in [7] should feature in an LCF-style program logic for FreshML.
Some of the details will appear in the second author’s forthcoming PhD thesis [6]. At this stage, just as important as proving such properties is accumulating experience with programming in FreshML, to see if the idiom it provides for metaprogramming with bound names modulo renaming is a useful one.
Future work
To improve the usefulness of FreshML for programming with bound names, it is already clear that we must investigate richer syntactic forms of abstraction. At the moment we permit abstraction over a single type of atoms. We already noted in Sect. 2 that it would be a good idea to allow the declaration of distinct sorts of atoms (for example, to more easily encode distinct sorts of names in an object language). Indeed, it might be a good idea to allow atom polymorphism via Haskell-style type classes [15], with a type class for ‘types of atoms’. But even with a single sort of atoms, there is good reason to consider notions of abstraction in which the data to the left of the ‘abstraction dot’ is structurally more complicated than just single atoms. For example, some object languages use operators that bind varying numbers of variables rather than having a fixed ‘arity’ (for example, the free identifiers in an ML match , however many there may be, become bound in the function expression ). To encode such operators we can make use of the following FreshML data type construction
whose values are some finite number of atom-abstractions of a value of type . When specifying a function on by structural recursion, one has to recurse on the list of binders in such a value, whereas in practice one usually wants to recurse directly on the structure of the inner most value . Therefore it would be useful to have ‘atom-list abstraction types’ (denotationally isomorphic to ) and abstraction expressions of the form , where is a value of type and is an expression of type . But if one abstracts over atom-lists, why not over other concrete types built up from atoms? Indeed, in addition to such concrete types, it appears to be useful to abstract with respect to certain abstract types, such as finite sets of atoms, or finite mappings defined on atoms. So it may be appropriate to consider a general form of abstraction type, , for arbitrary types and . To do so would require some changes to the nature of the freshness judgement (7), whose details have yet to be worked out. In fact, the FM-sets model contains a set-former for such a general notion of abstraction, so there is a firm semantic base from which to explore this extension of FreshML. Emphasising this firm semantic base is a good note on which to finish. Having reached this far, we hope the reader agrees that FreshML has some novel and potentially useful features for metaprogramming modulo renaming of bound variables. But whatever the particularities of FreshML, we believe the real source of this potential is the FM-sets model, which appears to provide a simple, elegant and useful mathematical foundation for computing and reasoning about name binding modulo renaming. It is certainly the case that without it, we would not have reached the language design described in this paper. (So please read the Appendix!)
A Appendix: FM-Sets
speaking, ML types and expressions denote sets and functions. By contrast, FreshML types and expressions are intended to denote FM-sets and equivariant functions. This appendix gives a brief review these notions; more details can be found in [7]. Of course, the presence of recursive features and computational effects in ML means that a denotational semantics for it really involves much more complicated mathematical structures than mere sets. Similarly, to account for the recursive features of the present version of FreshML, we should really give it a denotational semantics using domains and continuous functions in the category of FM-sets. For simplicity’s sake we suppress these domain-theoretic details here.
Notation. Let be a fixed countably infinite set, whose elements we call semantic atoms. Let denote the group of all permutations of . Thus the elements of are bijections from to itself. The group multiplication takes two such bijections and and composes them—we write the composition of followed by as . The group identity is the identity function on , denoted by .
Recall that an action of the group on a set is a function mapping pairs to elements and satisfying
for all and . For example, if is the set of syntax trees of lambda terms with variable symbols from
then there is a natural action of on : for each and , is the tree which results from permuting all the atoms occurring in according to .
In general, an action of on a set gives us an abstract way of regarding the elements of as somehow ‘involving atoms from in their construction’, in as much as the action tells us how permuting atoms changes —which turns out to be all we need for an abstract theory of renaming and binding. An important part of this theory is the notion of finite support. This generalises the property of an abstract syntax tree that it only involves finitely many atoms in its construction to the abstract level of an element of any set equipped with an -action.
Given a set equipped with an action of , a set of semantic atoms is said to support an element if all permutations which fix every element of also fix :
We say that is finitely supported if there is some finite subset supporting it. It is not too hard to show that if is finitely supported, then there is a smallest finite subset of supporting it: we call this the support of , and denote it by .
An FM-set is a set equipped with an action of the permutation group in which every element is finitely supported. These are the objects of a category, , whose morphisms are equivariant functions, i.e. functions from to satisfying
for all and .
The set of untyped lambda terms, defined as in (38) and with the -action mentioned there, is an FM-set. The support of is just the finite set of all variable symbols occurring in the tree (whether free, bound, or binding). Note that if two lambda terms are -equivalent, , then for any permutation one also has . It follows that induces an action on the quotient set . It is not hard to see that this is also an FM-set, with the support of an -equivalence class of lambda terms being the finite set of free variable symbols in any representative of the class (it does not matter which). This turns out to be the denotation of the data type declared in Fig. 1 (using [7, Theorem 5.1]).
It should be emphasised that the above definitions are not novel, although the use to which we put them is. They are part of the rich mathematical theory of continuous actions of topological groups. has a natural topology as a subspace of the countably infinite product of the discrete space , which makes it a topological group. Given an action of on a set , all the elements of have finite support if and only if the action is a continuous function when is given the discrete topology. Thus is an example of a category of ‘continuous -sets’ and as such, much is known about its properties: see [7, Sect. 6] for references. Here we just recall its cartesian closed structure.
A.1 Products in
These are given by taking the cartesian product of underlying sets
The permutation action is given componentwise by that of and :
Each pair does indeed have finite support, namely .
A.2 Exponentials in
Given any function (not necessarily an equivariant one) between FM-sets and , we can make permutations of act on by defining
By applying the property (39) with in place of , it makes sense to ask whether has finite support. The subset of all functions from to which do have finite support in this sense, together with the action given by (40), forms an FM-set which is the exponential in . Note that (40) implies that for all , and
and hence evaluation determines an equivariant function . Given any in , its exponential transpose is given by the usual ‘curried’ version of , for the following reason: given any , if fixes each semantic atom in , then it is not hard to see from definition (40) and the equivariance of that fixes the function as well; so this function has finite support and hence is in . So defining to be , we get a function ; it is equivariant because is and clearly has the property required for it to be the exponential transpose of . In the rest of this appendix we indicate the structures in the category used to model the key novelties of FreshML: locally fresh atoms, atom abstraction and concretion of atom abstractions.
A.3 Locally fresh atoms
The set of atoms becomes an object of once we endow it with the action:
(The support of is just .) This FM-set is the denotation of the type of atoms in FreshML.
The meaning of in is given by the following proposition (whose straightforward proof we omit). It makes use of the following construction in the category : given an FM-set , define
This becomes an FM-set if we define a permutation action by
Given a morphism in satisfying
then there is a unique morphism such that
is satisfied.
If a typing context has denotation and if , then the denotation of the typing context used in rule (11) of Fig. 2 is the FM-set . Suppose the denotation of is the equivariant function . We can use Proposition A.1 to give a denotation to as , using the fact that the freshness part of the hypothesis of (11) means that satisfies condition (41). The soundness of rule (11) follows from the defining property (42) of .
A.4 Abstraction and Concretion
If the denotation of the FreshML type is the FM-set , the denotation of the atom abstraction type is the FM-set introduced in Sect. 4 of [7]. Its underlying set is the quotient of the cartesian product by the equivalence relation defined as follows: holds if and only if
holds for some (or equivalently, any) not in the support of , ,, or (where denotes the permutation interchanging and ). We write for the -equivalence class determined by . The action of a permutation on elements of is given by:
This does indeed determine a well-defined FM-set, with the support of being the finite set .
If is associated with the semantic atom (in some given value environment) and the denotation of is , then the denotation of the atom abstraction expression is .
On the other hand, the meaning of concretion expressions (Sect. 4) uses the following property of FM-sets.
Given an FM-set , for each atom-abstraction and semantic atom , if then there is a unique element of such that .
When then if and only if or ; and in this case . So when or , it follows from the uniqueness part of the defining property of that
holds.
The partial function is used to give the denotational semantics of concretion expressions, . The soundness of rule (13) follows from the easily verified fact that .
Acknowledgements
The authors thank members of the Cambridge University Logic and Semantics group, Mark Shinwell (who is carrying out an implementation of FreshML), Simon Peyton Jones and the anonymous referees for constructive comments on the work presented here. This research was partially supported by the ESPRIT Working Group Nr 26142 on Applied Semantics (APPSEM).
References
[1] R. Burstall, D. MacQueen, and D. Sannella. HOPE: An experimental applicative language. In Proc. LISP Conference, Stanford CA, 1980, pages 136–143. Stanford University, 1980.
[2] R. M. Burstall. Design considerations for a functional programming language. In Proc. of the Infotech State of the Art Conference, Copenhagen, 1977.
[3] G. Cousineau and M. Mauny. The Functional Approach to Programming. Cambridge University Press, 1998.
[4] N. G. de Bruijn. Lambda calculus notation with nameless dummies, a tool for automatic formula manipulation, with application to the Church-Rosser theorem. Indag. Math., 34:381–392, 1972.
[5] M. P. Fiore, G. D. Plotkin, and D. Turi. Abstract syntax and variable binding. In 14th Annual Symposium on Logic in Computer Science, pages 193–202. IEEE Computer Society Press, Washington, 1999.
[6] M. J. Gabbay. A Theory of Inductive Definitions with -Conversion: Semantics, Implementation, and Meta-Language. PhD thesis, Cambridge University, in preparation.
[7] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax involving binders. In 14th Annual Symposium on Logic in Computer Science, pages 214– 224. IEEE Computer Society Press, Washington, 1999.
[8] M. J. C. Gordon and T. F. Melham. Introduction to HOL. Cambridge University Press, 1993.
[9] M. Hofmann. Semantical analysis of higher-order abstract syntax. In 14th Annual Symposium on Logic in Computer Science, pages 204–213. IEEE Computer Society Press, Washington, 1999.
[10] D. Miller. An extension to ML to handle bound variables in data structures: Preliminary report. In Proceedings of the Logical Frameworks BRA Workshop, 1990.
[11] R. Milner. Communicating and Mobile Systems: the -Calculus. Cambridge University Press, 1999.
[12] R. Milner, M. Tofte, R. Harper, and D. MacQueen. The Definition of Standard ML (Revised). MIT Press, 1997.
[13] J. C. Mitchell and G. D. Plotkin. Abstract types have existential types. ACM Transactions on Programming Languages and Systems, 10:470–502, 1988.
[14] L. C. Paulson. Isabelle: A Generic Theorem Prover, volume 828 of Lecture Notes in Computer Science. Springer-Verlag, Berlin, 1994.
[15] S. Peyton Jones and J. Hughes, editors. Report on the Programming Language Haskell 98. A Non-strict Purely Functional Language. February 1999. Available from .
[16] F. Pfenning and C. Elliott. Higher-order abstract syntax. In Proc. ACM-SIGPLAN Conference on Programming Language Design and Implementation, pages 199–208. ACM Press, 1988.
Notes
As far as we know, this feature was introduced into functional programming by Rod Burstall: see [2, 1]. ↩
It will be seen from these declarations that the syntax of function declarations (and case expressions) in FreshML is more like that of CAML [3] than that of Standard ML [12]. ↩
In the current experimental version of FreshML, there is only one such type. Future versions will allow the programmer to declare as many distinct copies of this type as needed, for example, for the distinct sorts of names there are in a particular object language. ↩
In the current experimental version of FreshML, we just consider monomorphic types built up from basic ones like and using products, functions, recursively defined data type constructions and the atom-abstraction type constructor described in the next section. Introducing type schemes and ML-style polymorphism seems unproblematic in principle, but remains a topic for future work. ↩
The terminology is adopted from [11, Sect. 12.1]. ↩
For Theorem 2.1 to hold, in rule (22) we need that implies for any semantic value of type ; excluding the use of function types (as well as ) in pure types is a simple way of ensuring this. ↩