THE -CALCULUS IN FM
ABSTRACT: FM (Fraenkel Mostowski) techniques are an approach to metaprogramming on syntax in the presence of binding. We develop novel FM theory and with it develop theory of -calculus syntax and its operational semantics. Technicalities of name binding and also of name generation in transitions are smoothly handled.
1 INTRODUCTION
Fraenkel-Mostowski (FM) techniques were introduced in [Gabbay, 2000; Gabbay and Pitts, 2001]. They were developed to allow us to reason inductively about syntax with binding. Consider a de Bruijn-style datatype of -terms:
Here -equivalence is equality and this is good but the inductive principle is ‘twisted’:
In the clause
FM techniques allow -equivalence to be logical equality, and simultaneously deliver natural induction schemes, as we shall see in this paper for the theory of the -calculus.
Process calculi abound and many of them involve term-formers for locality, encryption, and so on. These might interact with name-generation and scope extrusion in complicated ways and involve side-conditions on bound and free names. It would be interesting and useful if we could show that FM techniques could simplify these presentations, and perhaps also their proofs.
This paper starts with a brief account of basic FM theory which expands into quite a detailed account of some novel theory which we shall find useful: some improved proofs and definitions of known constructions like abstraction types, and new material on what we call abstractive functions, which turn out to be quite a powerful unifying tool in FM.
We then take a simple -calculus (without matching or replication) and indicate how to specify its syntax, operational semantics, and some standard operational and syntactic equivalence relations on it. We outline details of the proofs and see that the entire development can be made very close to normal informal practice, only that thanks to FM the treatment of names and binding in syntax and name-generation in operational semantics, is completely rigorous.
We conclude with a brief survey of other techniques, and outline possible future research.
2 -PERMUTATION
Hypothesise some set of atoms , which we shall use throughout this document to represent object-level variable names. Also write () for the set of finite subsets of . Now consider a name-carrying datatype of -terms:
Capture-avoiding name for name substitution might be defined as:
(4)
Here () takes () and returns some . The notation []() denotes the function [] : acting on , where [] for and [](.
This is almost a function which distributes through the syntax of a term and acts on the atoms inside it, only we must take account of the fact that Lam() abstracts in .
Now write (): for the function such that ()(, ()( , and ()( for , and call this a transposition. Using it we can define a form of capture-avoiding name for name substitution more simply:
For Λ and : , if
Here we write -equivalence as =.
By induction on term size using the observation that for () (but possibly occurring bound in ), () .
For example:
and Lam( Lam( Var( Lam( Lam( Var())) .
Write for the subgroup of functions generated by (). Write Id for the identity : and for the group composition, which is functional composition.
Let an FM set be a pair () of a set with an permutation action : (written infix) satisfying
We shall tend to write just for the FM set (). We call (6) the finite support property, we shall see why below.
Write FM-Sets for the category of FM sets with objects FM sets and arrows functions : such that (() )
A permutation action is a function which we write infix , satisfying Id and .
Say is equivariant when () for all .
Thus is equivariant when we can take in (6) above.
is an FM set with the natural action () )(). Any ordinary set, such as boolean truth values, the natural numbers, or the reals, can be made an FM set with the trivial action () for all , thus such that every element is equivariant.
Given FM sets and the permutation action naturally extends to functions : by conjugation, so
It is not necessarily the case that such a function satisfies (6). For example a choice function
2.1 Set-theoretic model of FM-Sets
We obtain a concrete model of FM-Sets as follows. We construct a set-theoretic cumulative hierarchy starting with atoms as base elements: in the standard notation .
Given we construct by collecting the subsets that satisfy (6). This is a model of ZF set theory with atoms ( in this case), along with the extra axiom (6), see [Gabbay, 2000; Gabbay and Pitts, 2001] for a full development.
The permutation action is given by the pointwise action on the elements: formally () and (this is clearly a permutation action).
Functions are implemented in sets as graphs . Applying a permutation according to this action, () () ()
Recall that the action on a set is pointwise on its elements. Thus an equivariant set is one such that . Equivariant sets can be seen as objects in FM-Sets and arrows as equivariant function- sets between them.
The construction above gives a model of FM-Sets.
FM-Sets is a boolean topos.
We see why permutation is better-behaved than atom-for-atom substitution []. If we try giving that a similar inductive interpretation on the set-universe, so []]() for and [] for , things do not work out smoothly. For example denotes the identity : and () . However we see that [] is not equal to and is no longer even a total function-set from to .
2.2 Support and apartness
For () write () for the set of fixing pointwise:
Say fixes : when . Say supports : when if fixes pointwise then :
Note that () is a group; this will be useful later. (6) says in this terminology that every has a finite supporting set of atoms.
Any : has a unique minimal supporting set of atoms. Write it and call it the support of .
Construct () as . The lemma below proves this supports .
If and support then so does .
Suppose fixes . We must show . Choose some injection : () and make it into a bijection by letting ( for in the image of (note that Id). Since () we know . Observe also that fixes , so . It follows by group algebra that .
In other works () is written ‘Supp()’. We prefer a more compact notation here for typographical reasons.
For : and : write
We read this as is (-)apart from .
We can verify by calculation that (
((. Write () for the set of cofinite sets of atoms. is cofinite when is finite. (. If is neither finite nor cofinite then ( so in FM-Sets (
If is a predicate we can write () for this is the FM -quantifier (pronounced ‘New’), familiar from [Gabbay and Pitts, 2001, p.8]. The observation on powersets becomes the some/any property of FM atoms:
Recall that arrows in FM-Sets are equivariant functions on underlying sets, so ((). It is then easy to show that ()
2.3 Abstractive functions and abstractions
For : and : define
At least one such always exists since is equivariant. By calculation (
For , and as above, is precisely the orbit of
under permutations (() ).
Suppose . Then . But precisely when and for , and since is a group . Therefore [].
By construction
As a corollary, ([]
Define -abstraction by
See [Gabbay and Pitts, 2001, Section 5]. The canonical map : ‘binds’ (or more properly the support of ) in . is otherwise injective:
If ] then .
By easy calculation.
:
Abstraction types with their universal properties are an example of an abstractive function.
2.4 Abstractive functions
Any : induces an inverse map :
() partitions into orbits under (()) (as well as any other subgroup of ). Write () for this particular set.
Each orbit has a breadth () the cardinality of () of a representative . Write this
Suppose is such that for all there is a unique orbit of greatest breadth:
Write () for this orbit when it exists and say has orbits of maximal breadth.
The set () is an FM set, write it just .
Say : is Barendregt abstractive or just abstractive when it has orbits of maximal breadth. When () is always a singleton set, so orbits are maximal because they are unique, say is purely abstractive.
An abstractive : induces a purely abstractive restriction : . By construction, if is surjective, so is its restriction to .
1. For : 1 the set () has just one orbit, , with breadth 1. is purely abstractive.
2. For : 1 the set () has two orbits, with breadth 2 and with breadth 1. is Barendregt abstractive.
3. For :
4. For : 1 the set () has two orbits of equal breadth. is not abstractive.
5. For :
6. For (second projection) () has one orbit of maximal breadth . is Barendregt abstractive.
7. Recall from (3) the datatype Λ. The quotient by -equivalence, write it : [] : Λ Λ, is Barendregt abstractive. is the set of Barendregt representative terms.
Abstractive functions give an abstract account of the Barendregt variable convention (amongst other things), because the orbit of maximal breadth consists of representing with the most possible different names for those ‘bound’ by the function. Abstractive functions are also related to FreshML abstraction-patterns. The interpreter generates fresh names for atoms in (possibly nested) abstraction-patterns.
If we read these example : ‘backwards’ as ‘maps’ , they do the following respectively: choose a canonical atom, choose a canonical pair of distinct atoms, choose a canonical largest finite set of atoms (there is none), choose a canonical atom in a disjoint sum (there is none), choose a fresh atom for , choose a Barendregt representative for . Theorem 21 will make this intuition formal.
If : and : have orbits of maximal breadth then so do : and : (with the obvious definitions).
If : and : have orbits of maximal breadth so does : .
(Sketch) The case of disjoint sum is very easy. For the case of products, is the (())-orbit of
The case of functional composition is also easy. () is equal to for a representative
If : and : are (Barendregt) abstractive then : is (Barendregt) abstractive and : is Barendregt abstractive. If : and : are (Barendregt) abstractive then so is : .
Using Lemma 17.
For : abstractive and surjective and :, say factors through on orbits of maximal support when there is some : such that for all , (
For and as in the previous definition, write when () ().
For and as above, if and only if factors through on orbits of maximal support.
Suppose for all , (). Then ((()) ().
Conversely suppose and . Write and let be . If then for some (()) and (). Now () () by assumption so (. So is well-defined.
As a corollary, purely abstractive surjective : universal amongst maps : such that . If is Barendregt abstractive and surjective, it is universal ‘on orbits of maximal breadth’.
For :
For : the condition is #(). Write () for the unique value of () when # (for fixed ). This is a functional version of the quantifier mentioned in the last subsection.
When the condition #() is always satisfied since ( or (, and we obtain the -quantifier mentioned in 2.3. (The makes parameters explicit.)
Now suppose that : . The universality property on orbits of maximal breadth then gives () if and only if #(), a known commutativity property between and which we shall find useful.
Recall that for Λ defined in (3) the quotient : Λ Λ is Barendregt abstractive. Therefore : Λ respects -equivalence on Barendregt representative terms precisely when for all such and
When : is abstractive and , write the we construct above as : .
We write ()() as , this is the unique value of at such that ( and is a Barendregt representative in the sense discussed above.
We call this the generalised quantifier.
3 THE -CALCULUS
3.1 An inductive datatype of -calculus terms up to binding
Define an inductive FM datatype of -calculus terms up to =:
To construct a term of the form it suffices to provide : , : Π, and apply to the abstraction []. Recall from after Corollary 14 that we can write such an abstraction namelessly as .
Π is inductively defined and has a primitive recursion scheme. For any , given
there is a unique : Π such that all of the following hold:
However abstraction : Π
Recall the notations for renamings [] from 2.
Analogously to write for the monoid generated by renamings [], and write Id for the identity .
By (12) we can define name substitution on Π by primitive recursion as follows:
We also show an induction principle derived from primitive recursion. For a predicate on Π, if
hold, then (14)
A more usual induction scheme would have clauses for input and restriction as follows:
These do not assume fresh, and since this is the only case we care about in practice it can be useful to, in effect, build it into the datatype.
If # and then
We read the second two clauses ‘for free’ off the appropriate clauses of (13) (input and restriction), because #[] always holds. Concerning the first clause, we say of many FM results in this paper that they follow ‘by (easy) calculation’. The following useful result follows by slightly involved calculation, for once we give it in full.
# if and only if is neither in the domain nor the image of as a partial function on atoms.
Suppose #. is finitely generated by renamings so cofinitely many atoms are not in the domain or image of , or formally .
By (6) also cofinitely many have #, so choose one such that both hold. Then ()() )(() , so . Also suppose that for some . Then ) (() ). So () and therefore .
Conversely, suppose is neither in the domain nor image of . Take fresh not in the domain or image as before. Write ) . We show by applying them to arbitrary .
) (() ) by definition. ) . ) . Otherwise ) . We know , so this is just .
If # and #, then #.
We shall use these results often in our proofs.
We return briefly to (13): ( )][]() the clause for input can be equivalently expressed by
(We can treat the clause for restriction similarly.) This presentation style is useful, we explore it in detail in the next subsection.
3.2 Operational semantics for Π
Define a datatype of actions by
Write
We define an early and late transition relations
inductively by the rules of Figure 1.
We elide symmetric versions (Par2), (Close2), and (Com2).
Figure 1. FM presentation of late and early -calculus transitions.
A transition in our sense is an element
By the discussion on quantifiers at the end of the previous section we can expand the quantifiers of the late (In) as # . We can expand the quantifiers of the early (In) as #.
For a more complex example, the quantifiers of (Open) expand as ##. Now recall that # is equivalent to and # equivalent to (). Here () is the free names of , we write it just because in the FM datatype there are no bound names.
Thus we see how the mix of and encodes side-conditions on free and bound names. The advantage of using is that we can assume fresh also for other parts of our context, for example a substitution , or perhaps a different process . We now consider an example.
Recall the notation : and the renaming action, defined in and after Definition 23. Recall from Lemma 24 that if # then . [Milner et al., 1992, Lemma 3] in this framework and notation becomes:
For :
Here denotes the evident inductive action of on actions .
By induction on the transition using hypothesis
The case (Close1). Suppose are such that #, and . Suppose also and . By Lemma 24 #, so by induction hypothesis . Similarly for . # so we apply (Close1) to these two new transitions.
The case (Open). Suppose we have and # and #. Suppose . By induction hypothesis . Also we know that # and #, so we can apply (Open) to this new transition.
In the proof above we deconstruct a transition choosing suitably fresh names for the bound variables, and reconstruct it with applied, verifying that the appropriate freshness conditions hold. When we deconstruct we took advantage of the FM framework to choose fresh also for , so that (capture avoidance for free).
Continuing to read [Milner et al., 1992] we see that further results become trivial or easy. Lemma 4 of [Milner et al., 1992] becomes equivariance of :
For : , and for , and , with #,
Lemma 5 part (a) and the second half of (b) for bound output of [Milner et al., 1992] disappear because Π is already up to -equivalence and because bound outputs really do bind the output name. The first half of Lemma 5 part (b) is subsumed in the FM version by Lemma 28.
We give appropriate definitions of bisimulation for the early and late calculi respectively. Early bisimulation in the early transition relation is the greatest symmetric relation closed under the rule
Late bisimulation in the late transition system is the greatest symmetric relations such that if then
We obtain an early version in the late transition system by swapping and in the last clause to , in the way we would expect.
For Π, we write for the symmetric relation defined by
is preserved by all term-formers except for input. is preserved by all term-formers.
By inductions on . We have checked the proofs in detail. They are as systematic as the proof of Lemma 28 and by simple induction.
3.3 Structural congruence
We can use FM to specify freshness constraints also for structural congruences. For example:
Define a relation on Π inductively as the smallest congruent equivalence relation closed additionally under the rules
We call this structural congruence.
(These rules are modified from [Parrow, 2001, Table 2, p.10].)
Structural congruence implies early bisimilarity: .
(Sketch) By standard FM-style induction. Let Φ : (Π Π) (ΠΠ) be the monotone operator on relations implicit in (18). Thus a relation is a bisimulation when Φ() and is the largest bisimulation.
Then
0 0 satisfies Φ() .
()# satisfies Φ() .
# satisfies Φ() .
The relations
Proofs by induction.
It is easy to prove by induction that for all : Π and substitutions , if then ; avoids variable capture as in the proof of Lemma 28.
Using all of these facts we can verify that Φ() and hence .
Symmetric versions (Par2), (Close2), and (Com2) are elided.
Figure 2. A conventional presentation of early -calculus transitions.
4 EQUIVALENCE WITH CONVENTIONAL PRESENTATION
It remains to verify that the presentation of Π with its transition system in 3 corresponds to the -calculus as we know it from elsewhere.
Define a datatype of terms of the -calculus not up to binding
Define a datatype of actions by
The transitions of are written and inductively defined in Figure 2.
Abstraction inductively induces a map : Π:
For ,
By induction on syntax for fixed using inductive hypothesis
We consider just the case of restriction. Suppose (). We verify ().
If then () precisely when (). Also, # precisely when #(). Since (() the result follows.
If then () and also #(). Since ( () the result follows.
() is surjective. Its kernel is precisely -equivalence on .
By inductions on syntax.
is also Barendregt abstractive, by Corollary 18.
In the last section we mentioned that Π is an FM datatype and has no names of bound atoms. and are a formal sense in which we can give them names.
extends pointwise to a map ( ) (Π Π) and hence to a map from a relation on to a relation, write it , on Π. It also gives rise to a map from (Π Π) to ( ), maps to .
, where is early bisimilarity or late bisimilarily on and Π respectively.
We show that is a bisimulation in the FM sense, and that is a bisimulation in the traditional sense, for a notion of bisimulation as in (18) and (19).
The transition relations Π Π and are related as shown in Figure 3.
Note that (26) refers only to Barendregt representatives. This is technically convenient for the proof. Once we have it we can take advantage of results on transitions for the standard name-carrying , such as [Milner et al., 1992, Lemma 5], to strengthen it to all .
The proof of Theorem 38 is in two parts corresponding to (25) and (26). The first part is by induction on , the second by induction on . To save space we do not re-write out the induction hypotheses in complete formality.
For any : , write . Then
For any : Π :, choosing fresh names for the bound atoms in and using ;
(Of Theorem 38, first part, (25))
The case (In) of . Suppose []. We would like to apply (In) of to (), and some #(). However to do so we must verify #, and this does not hold. We draw on the library of results for the conventional -calculus to deduce that for #, [] [][]. [] is -equivalent to so both map to We can now proceed.
The case (Par1) of . We consider only the case (). Suppose
. Suppose also () for some . Then . By the inductive hypothesis
The case (Open) of . Suppose and . By inductive
hypothesis we have
(Of Theorem 38, second part, (26)) The case (In) of . Suppose are such that # and #. We apply (In) to deduce []. Now choose distinct names fresh for and for the bound atoms in , to obtain a Barendregt representative of , so (. We wish to apply (In) of to . We can do this, there are no side conditions.
The remaining issue is whether, for example, ( and ([[]. These follow from appropriate freshness hypotheses. For example, the names for bound variables in were chosen fresh for a context which included and , so accidental capture is impossible.
The case (Par1) of . We consider only the case of a bound output. Suppose we have with #, and . By inductive hypothesis for fresh choices of bound names ((
( we have . The side-condition () follows because (() and #, so we may apply (Par1) of .
The case (Open) of . Suppose have # and #, and suppose . By inductive hypothesis for fresh choices of bound names (( we have . The side-condition follows from #.
5 CONCLUSIONS
FM techniques were developed to inductively represent syntax-with-binding, so that we can reason and program on it structurally. These ideas have been considered mathematically and logically [Gabbay and Pitts, 2001; Urban et al., 2003; Pitts, 2001] and also implemented as a dialect of ML [FreshML, 2003; Pitts and Gabbay, 2000; Shinwell et al., 2003]—yet until now FM literature has for simplicity only really considered the syntax of elementary -calculi.
The -calculus is a natural choice for a more complex study. Its binding is more complicated and includes scope extrusion, name passing, and name-generation (also called dynamic allocation).
We have seen how standard structural specifications of transition systems translate quite directly to FM, with the equivalence being in essence just the quotient map by binding which we would hope for. We have seen how side-conditions on free and bound names are taken care of by judiciously mixing and quantifiers.
In the course of this research we discovered the notion of an abstractive function and the generalised quantifier described in 2.4. We needed it first to express Theorem 38, but then realising its generality we devoted some space to developing it.
In the syntax-free mathematical context of FM sets, abstractive functions and generalised provide a unifying account of (syntax-free mathematical generalisations of) the Barendregt variable naming convention, FreshML pattern-matching, and the quantifier.
Related work. FM techniques are related to presheaf semantics for syntax, see for example [Fiore et al., 1999; Fiore and Turi, 2001]. The presheaves used there are and ( the category of finite sets and injections, that of finite sets and all maps).
Presheaves can be viewed as sets with ‘actions’ at ‘stages’, so the two presheaf categories above make injective and possibly non-injective renamings respectively intensional features of the underlying universe. An FM set gives a presheaf mapping () to () . It is a special one though, such that every element appears at a unique minimal stage: its support, this is Theorem 7. In this way FM maintains a ‘first-order set-based’ presentation which we feel is particularly clear.
Approaches based on Higher-Order Abstract Syntax (HOAS) can suffer the following three problems. First, the function spaces can be too large. For this reason the Theory of Contexts has no unique choice [Bucalo et al., 2001]. Second, function spaces can destroy inductive structure, so there can be issues with deriving inductive principles for the datatypes. Thirdly, these problems overcome, if we need to generate names we may need to index all our predicates and relations by an explicit set of known names (called or , say) see for example [Bruni et al., 2002; Honsell et al., 2001, Fig.2] and [Cattani and Sewell, 2000, Fig.1]. This is a programming analogue of the the presheaf semantics mentioned above. Other more first-order set-based presentations may do this too, for example [Cattani and Sewell, 2000]. These indexes can be cleanly presented, but it would still be better if they were not there at all.
Two advantages of HOAS are that they can be implemented in existing frameworks (wheras FM based on FM sets, cannot), and that name-passing can be modelled by function application. Name-passing in this paper is modelled by substitution defined inductively on syntax in (13).
We already discussed de Bruijn approaches in the Introduction. Their ‘twisted’ inductive principles can cause great technical difficulties. In studies by Hirschkoff [Hirschkoff, 1999; Hirschkoff, 1997] 75 per cent of the technical lemmas of a full formalisation of the -calculus regarded ‘straightening them out’.
Of all approaches to syntax, surely the benchmark is name-carrying syntax trees like the one in (3). The problems with capture-avoidance for such datatypes are well-known. This paper shows how FM approach treats names in the -calculus in a way which is close to this elementary practice, but entirely rigorous. This will hopefully serve as a model and theoretical foundation for more complex examples.
We should mention that a lot of the problems with name-carrying syntax only appear if we insist on a purely structural approach. In [Martin and Gordon, 1993] pages 24 and 25 the authors are primarily interested in expressivity (of the spi-calculus). Accordingly they adopt a ‘chemical’ presentation after [Berry and Boudol, 1990]; transitions are defined on processes modulo scope extrusion and other structural congruence rules.
Even here, FM can help. We saw in 3.3 how it takes care of side-conditions for freshness in scope extrusion. Of course this is a simple observation, but for more complex calculi with various forms of binding, it can be useful both for presentation and theory.
Future work. The models of this paper are purely syntactic, and not semantic. It is a feature of FM abstraction that we may only choose a fresh name for the bound name. Wheras in HOAS abstraction is function abstraction, and name-passing can therefore be function application, here we use the renaming (inductively!) defined in Definition 23.
There is nothing wrong with this, but it does block an obvious abstract account of name-passing based on FM abstractions instead of functions. Other semantic models based on presheaves, such as [Fiore et al., 1996; Cattani et al., 1997], also use function spaces. [Fiore and Turi, 2001] makes the same observation of models of syntax in and goes on to provide a comprehensive categorical framework to account for name and value passing. It might be interesting to carry out a similar programme using in an FM style. Even if this turns out to be equivalent to the presheaf material, which we doubt because our account would have a notion of support, it would be a different perspective and presentation.
We see the most immediate and concrete application for this work to History-Dependent (HD) Automata [Montanari and Pistore, 1997], which are a notion of model based only on syntax. An HD automaton is roughly speaking a graph of representative processes encoded in de Bruijn notation, with edges transitions annotated by permutations between the names to take care of reindexing and name-generation (the many flavours of HD automaton corresponding to different and differently-detailed implementations of this idea). This could be viewed as an FM construction and this paper is a first step towards constructing it.
A related approach to the same issue is -automata described in [Bruni et al., 2002]. Roughly, these models are obtained by adding a meta-level restriction operator to the syntax of terms, which acts only at top level and restricts certain names in a process. Name-generation is modelled by generating a name, then restricting it. This concept is clearly related to the datatype Π []( Π) developed in this paper, with restriction replaced by FM abstraction. The concept of model in that work corresponds to that of an HD automaton, only implemented using terms up to -equivalence (bound by ) instead of a de Bruijn representation.
We plan to develop an FM based structure unifying these two approaches. Since FM now comes equipped with a programming language FreshML [FreshML, 2003], datatypes and inductive definitions should translate into programs.
ACKNOWLEDGEMENTS
My grateful thanks go to Marino Miculan, Furio Honsell, and Ugo Montanari. I also recognise the support of UK EPSRC grant GR/R07615 which partly funded this research.
BIBLIOGRAPHY
[Berry and Boudol, 1990] Gerard Berry and Gerard Boudol. The chemical abstract machine. In Proceedings of the seventeenth annual ACM symposium on Principles of programming languages, pages 81–94, New York, NY, USA, 1990. ACM Press.
[Bruni et al., 2002] R. Bruni, F. Honsell, M. Lenisa, and M. Miculan. Modeling fresh names in pi-calculus using abstractions. Technical Report 21/2002, Dipartimento di Matematica e Informatica, University of Udine (Italy), April 2002.
[Bucalo et al., 2001] A. Bucalo, M. Hofmann, F. Honsell, M. Miculan, and I. Scagnetto. Consistency of the theory of contexts, 2001.
[Cattani and Sewell, 2000] Gian Luca Cattani and Peter Sewell. Models for name-passing processes: Interleaving and causal. In Logic in Computer Science, pages 322–332, 2000.
[Cattani et al., 1997] Gian Luca Cattani, Ian Stark, and Glynn Winskel. Presheaf models for the pi-calculus. In E[ugenio] Moggi and G[iuseppe] Rosolini, editors, Proceedings of the 7th International Conference on Category Theory and Computer Science (Santa Margherita Ligure, Italy, September 4–6, 1997), volume 1290 of LNCS, pages 106–126. Springer, 1997.
[Fiore and Turi, 2001] Marcelo Fiore and Daniele Turi. Semantics of name and value passing. In Proc. 16th LICS Conf., pages 93–104. IEEE, Computer Society Press, 2001.
[Fiore et al., 1996] Marcelo Fiore, Eugenio Moggi, and Davide Sangiorgi. A fully-abstract model for the -calculus (extended abstract). In Eleventh Annual Symposium on Logic in Computer Science (LICS) (New Brunswick, New Jersey), pages 43–54. IEEE, Computer Society Press, July 1996.
[Fiore et al., 1999] 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.
[FreshML, 2003] FreshML. FreshML homepage, 2003. http://www.freshml.org.
[Gabbay and Pitts, 2001] M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 13:341–363, 2001.
[Gabbay, 2000] Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
[Hirschkoff, 1997] Daniel Hirschkoff. A full formalization of pi-calculus theory in the Calculus of Constructions. In E. Gunter and A. Felty, editors, Proceedings of the 10th International Conference on Theorem Proving in Higher Order Logics (TPHOLs’97), pages 153–169, Murray Hill, New Jersey, August 1997.
[Hirschkoff, 1999] Daniel Hirschkoff. Mis en oeuvre de preuves de bisimulation. PhD thesis, École Nationale des Ponts et des Chausées (ENPC), January 1999. In French.
[Honsell et al., 2001] Furio Honsell, Marino Miculan, and Ivan Scagnetto. -calculus in (co)inductive type theory. Theoretical Computer Science, 253(2):239–285, 2001.
[Martin and Gordon, 1993] M. Martin and D. Gordon. A calculus for cryptographic protocols : the spi calculus. Technical Report SRC-RR-149, Internationales Begegnungs und Forschungszentrum Schloss Dagstuhl, Germany, 1993.
[Milner et al., 1992] Robin Milner, Joachim Parrow, and David Walker. A calculus of mobile processes, II. Information and Computation, 100(1):41–77, September 1992.
[Montanari and Pistore, 1997] Ugo Montanari and Marco Pistore. An introduction to history dependent automata. In Andrew Gordon, Andrew Pitts, and Carolyn Talcott, editors, Conference Record of the Second Workshop on Higher-Order Operational Techniques in Semantics (HOOTS II, Stanford University, December 8–12, 1997), volume 10 of ENTCS. Elsevier Science Publishers, 1997.
[Parrow, 2001] Joachim Parrow. An introduction to the pi-calculus. In Jan Bergstra, Alban Ponse, and Scott Smolka, editors, Handbook of Process Algebra, pages 479–543. Elsevier Science, 2001.
[Pitts and Gabbay, 2000] A. M. Pitts and M. J. Gabbay. A metalanguage for programming with bound names modulo renaming. In R. Backhouse and J. N. Oliveira, editors, Mathematics of Program Construction. 5th International Conference, MPC2000, Ponte de Lima, Portugal, July 2000. Proceedings, volume 1837 of Lecture Notes in Computer Science, pages 230–255. Springer-Verlag, Heidelberg, 2000.
[Pitts, 2001] A. M. Pitts. Nominal logic, a first order theory of names and binding. Information and Computation, 2001. To appear. (A preliminary version appeared in the Proceedings of the 4th International Symposium on Theoretical Aspects of Computer Software (TACS 2001), LNCS 2215, Springer-Verlag, 2001, pp 219–242.).
[Shinwell et al., 2003] M. R. Shinwell, A. M. Pitts, and M. J. Gabbay. FreshML: Programming with binders made simple. In Eighth ACM SIGPLAN International Conference on Functional Programming (ICFP 2003), Uppsala, Sweden. ACM Press, August 2003.
[Urban et al., 2003] C. Urban, A. M. Pitts, and M. J. Gabbay. Nominal unification. In M. Baaz, editor, Computer Science Logic and 8th Kurt Gödel Colloquium (CSL’03 & KGC), Vienna, Austria. Proccedings, Lecture Notes in Computer Science. Springer-Verlag, Berlin, 2003.
Notes
M.J.Gabbay, mjg1003@cl.cam.ac.uk, Computer Laboratory, Cambridge University, UK ↩