Automating Fraenkel-Mostowski Syntax
Computer Laboratory, Cambridge University, UK
Abstract. Work with Pitts and others has led to FM (Fraenkel-Mostowski) theory, a fresh understanding of modelling syntax in the presence of variable binding. We discuss the design and other issues encountered implementing these techniques in the mechanised theorem-prover Isabelle.
1 Introduction
It is easy to declare a datatype of terms of some language, for example the untyped λ-calculus,
where is the natural numbers. Problems famously arise defining program transformations in the presence of variable binding. For example a substitution function on above should avoid “accidental variable capture” in for Thus we rename in to some , but then is no longer syntactically a subterm of and we have made an arbitrary choice about the value of . The former point causes difficulty with structural induction, the latter because we may have to formally prove irrelevance of the choice made.
All this we could do without, especially in the unforgiving structure of a computer proof assistant such as Isabelle, HOL98, or COQ, or even programming in some language with datatypes. There is much research in this area, for example explicit substitutions ([2]), de Bruijn indices ([3]), and HOAS ([11], [4], [9]).
FM theories are another approach with a pleasingly elementary mathematical foundation. See [7] (my thesis), [5] and [6] (set theory), [8] (higher-order logic), [13] (programming languages), [12] (first-order logic). The label “Fraenkel-Mostowski” honours the creators of set theories designed to prove the independence of the axiom of choice, see [15]: a very special Fraenkel-Mostowski set theory was the first FM theory in the sense of this paper to be created.
In this paper we discuss principles of formally implementing a theory of FM syntax, based on experience doing so in Isabelle [14].
The first design decision of the implementation is the choice of system, Isabelle. We chose Isabelle for its paradigm of constructing arbitrary useable theories (Isabelle/Pure/FOL, Isabelle/Pure/HOL, Isabelle/Pure/CCL, ..., see [14]) in a fixed weak meta-language Isabelle/Pure. This meta-language is a very weak higher-order logic (HOL) containing little more than modus ponens, but to which we may add new types, constants of those types, and axioms on those constants. Thus we may axiomatise a theory in Isabelle/Pure and then work inside that theory. This is good for prototyping a new foundational system such as FM.
2 FM
‘FM’ may differ depending on whether we do computation or logic. For example compare the typed λ-calculus (a theory of computable functions) to higher-order logic (a theory of all functions). This paper is about logic, FM in computation (programming languages, unification) is under development, see [13,1].
‘FM’ is a set of techniques for -equivalence with inductive definitions and not a particular theory. We shall now present FM in the style of a higher-order logic. This is not an axiomatic presentation (see [8]) but a ‘sketch of salient features, in the style of higher-order logic’. First, three preliminary remarks
1 (Types). We shall write type annotations in two styles and both mean “ of type
2 (HOL sets). Higher-order logic has a notion of set, where ‘-sets’ is predicates also written We borrow set notation, for example writing for for , and for and for
3 (Meaning of infinite). In FM theories not all types can be well-ordered (bijected with an ordinal, see [8, Lemma 4.10(5)]). Therefore, a reading of ‘ is infinite’ as is suspect. In FM we use where is the inductively defined type of finite subsets of .
An FM theory has
4 (Atoms). An infinite type of atoms to model variable names. For example in an inductively defined type of expressions for types,
type variables are represented as for
5 (Transposition). There is a (polymorphically indexed class of) constant(s)
read “transposition”. Write as . The intuitive meaning of is as transposing a and in . For example if then should equal . This is made formal by the following equational axioms which must satisfy, and equivariance below:
where is Isabelle-like notation meaning “
6 (Equivariance). For a term with free variables
In the case that has no free variables we have the special case that
We say the language is equivariant. An equivariant element is one such that for all From (8) for it follows that closed terms denote equivariant elements.
Write for the HOL set of finite subsets of . Say a set is cofinite when its complement is finite. Write for the HOL set of cofinite subsets of . For write ‘ ’ or ‘ ’ for
is infinite from remark 4 so we can read as “for all but finitely many ”, or more loosely as “for most We may call finite small and their complements, cofinite sets, large. Thus is large precisely when , and small precisely when
Define and read this as “ is not ‘in’ ” or “ is apart from ”. The intuition is that, since transposition transposes for in and since is fresh, if then certainly is not in .
We have an axiom stating that ‘most’ atoms are not ‘in’
Expanding definition 8 this becomes Write
Then (Small) is equivalent to
and we can also read (Small) as “ has finite support”.
9 (Some observations). ‘In’ does not correspond to (HOL-)set membership. For example,
We might think of as an object-level notion of those atoms occurring in some meta-level term which denotes.
Datatypes of syntax certainly satisfy (9). Terms are finite so mention only finitely many atoms, and cofinitely many satisfy
10 excellent properties). Higher types such as also satisfy (9). Observe that (using some sets notation)
It follows from (8) that
We can verify by calculation that if and only if or When we combine this with (9) it follows that either ‘most’ atoms are in or most are not in
We can rewrite this as Now the full set is clearly cofinite so . Combining this with other properties of cofinite and finite sets we obtain the algebraic commutativity properties:
that is, distributes over and . These strong properties make convenient to work with in a mechanised context. They also place in an interestingly ‘in between’ and , the equations being informally
3 α-equivalence on a simple datatype
11. is how an FM theory renames object-level variables. It interacts with object-level syntax better than atom-substitution . For example applied to ) raises all the usual problems with capture avoidance, whereas is -equivalent to itself. Similarly, wheras
We can define an -equivalence relation by cases on inductive types. For example:
Here is intended to be a type of expressions for types. The definition of above might be written in more familiar style as
and sugared to (writing for a type and for a type variable)
We shall use , , and defined below in (18), as a running object of study in the rest of this paper. In the rest of this section and elsewhere the proofs given are semi-formal accounts of the formal proofs as they might be conducted in Isabelle.
This machinery allows us to quite easily prove some nice properties for , for example transitivity
is transitive.
Proof. By induction on syntax using hypothesis
The significant case is of So suppose , and . Then and ), and
We now equationally apply (11) to deduce
Now we assumed , not But we can apply equivariance (8) to to deduce , which allows us to complete the proof.
We can also define a more traditional -equivalence :
in terms of an inductively defined names-of function
and an inductively defined atom-for-atom substitution function
and are simple and make no allowance for free variables or capture-avoidance, but they suffice for our needs.
Suppose we want to prove . A pleasing and clean method would be to prove
Proof (of (21)) We can use structural induction for fixed with hypothesis
Suppose By definition from (20), ), and by equivariance (8), By hypothesis we know
By (11) and applying the equalities under we obtain the result.
The cases of and are no different. Each time, equivariance of as illustrated in (8) allows us to push transposition down through the structure of a term and replicate the inductive behaviour of . This is a general pattern.
Note from this proof how transposition with equivariance has provided a ‘general axiomatic theory of (purely inductive) renaming’
Proof (of (22)) The proof of (22) is rather more involved. It is best to work from the following lemmas
The proof now proceeds as follows. We must prove
Write and use (25) (proved from (23) and (24)) and to rewrite this to
where denotes the conjunction
Left-right implication. We must prove
We eliminate the existential quantifier and obtain
We resolve against (29) to obtain
which simplifies to We repeatedly resolve against (26) to reduce to and finish this off with (28).
Right-to-left implication. We must prove
Now here we have a problem. Clearly we would like to eliminate using (30) to obtain
identify the in the conclusion with the in the hypotheses, and simplify. But we obtain
This implication does not follow for general , nor even for our particular if were injective we could apply (27) repeatedly, but it is a predicate mapping into and is not injective.
However we can use (32) to introduce into the context some fresh for any , so instantiate to the 3-tuple
Now we can apply (27) repeatedly to obtain
(Here there is also a hypothesis but this gives us no information since we get it for free from (28), so we drop it.) This simplifies to
But now we have another problem. If we eliminate using (30) we obtain for a variable symbol
We need a different elimination rule for which does not introduce a new variable into the context, and this is provided by (31), with which we can finish off the proof.
4 Morals from the proofs
In the previous section we have seen the beginnings of the automated theory of , introducing a fresh name, and We now bring it out explicitly.
14 (Theory of transposition). Given a conclusion of the form , use (8) to simplify the RHS by drawing transposition down to the variables on the right hand side. Similarly for other binary predicates such as or also . So for example
This algorithm can fail, for example on the goal . Call it , because it ‘pushes’ transposition into the structure of the term on the right of an equality. In an implementation would denote a tactic. We shall continue to give such names to algorithms which would denote tactics.
15 (Theory of ). Given a goal of the form repeatedly apply (26) and (28) to simplify it to component parts. So for example
reduces to , and then to . This algorithm can also fail, for example in we should perform -reduction first, otherwise we finish up with , which is untrue. Call the algorithm
Inductive proof on inductive types can, with proper handling and properly coordinated automated procedures, be made to produce very uniform proof-obligations which are amenable to this kind of treatment, with only slightly more sophisticated algorithms.
16 (Introducing a fresh name). (32) allows us to introduce a new variable into the context, fresh for for any given the proof-state
we can reduce to
for any .
We can now take to be the -tuple . Repeated applications of (27) reduce to ). It is a lemma that , so we obtain
In other words, “we can always invent a fresh ”. We applied this technique ad-hoc in (34). Call the algorithm
17 (Theory of ). The treatment of is more complex. There are two broad styles of reasoning on equational reasoning using for example properties such as (11) and (16), and directed reasoning using intro- and elim- rules such as (29), (30), and (31). Both are useful. For example equations in (17), and intro- and elim- rules in the proof of (22).
A further complication of the treatment of intro- and elim- rules is that seems to have two pairs of them. In full, they are
For practical purposes these pair off naturally as (35) with (38) and (37) with (36). The first pair requires we find in the context a fresh . The second pair introduces that fresh , but only fresh for We can do better than this using (32) as in remark 16, so this latter pair seems less useful.
The complete algorithm is therefore: simplify using (11) to collect all quantifiers in the hypotheses into one single quantifier. Also use (13) to draw negations under the quantifier. Finally, apply the intro- and elim- rules (35) with (38), possibly augmented with remark 16 to generate a fresh name where necessary. Thus for example
simplifies to
a fresh is introduced
the intro- and elim- rules reduce this to
and proof-search proceeds as normal. In the case that the fresh is already in the context, as happened in (33), we use that supplied instead. Call this algorithm
5 Difficulties implementing the algorithms
There are many technical difficulties putting the ideas of section 4 into practice.
18 is described in remark 15. The steps of the algorithm are:
1. repeated resolution with (26) followed by, when this fails,
2. resolution with (28).
There are difficulties with both steps.
1. Isabelle resolution with Isabelle unification is higher-order. unifies with a goal for matches and matches the identity, and we have a non-terminating loop. The solution is to write ML code to only allow this step when is syntactically an application term , and package this up as an Isabelle wrapper. An Isabelle wrapper, simplistically put, is an Isabelle theorem ‘wrapped’ in ML code which provides some intelligent control on how it may be applied, see remark 20.
2. It is impossible at object level to decide whether a term of the meta-level is closed or not. Again, we need an ML wrapper.
The algorithm described in remark 14 is similar and also requires wrappers.
19 . To introduce a fresh fresh for all variables in the context, as we saw in remark 16, we must examine those names. This is, as in the previous remark, an operation on the meta-level syntax and must be implemented by an ML wrapper which examines that syntax.
20 (Isabelle wrappers). We observed in remarks 19 and 18 that three significant FM features require ML wrappers in implementation , , and ).
Isabelle proof proceeds imperatively by applying tactics to a proof-state. Simple tactics may apply a particular transformation to the state. More complex tactics will carry out some kind of proof-search. These automated tactics (written in ML) give Isabelle proving much of its power. They are all essentially tree-search algorithms of various kinds based on a library of Isabelle theorems which may be equalities, intro-rules, elim-rules, as the case may be. In inductive reasoning we use this automation to automatically handle the dozens if not hundreds and thousands of separate cases which a proof may entail. Wrappers are applied in between proof-steps and perform well as intelligent agents which may examine the way the proof-state is developing and perform for example some kind of garbage-collection.
But consider the example of . This is implemented as a wrapper as discussed above in remark 18 but morally it is clearly a pair of intro-resolution rules
In proof-search however will only be applied if none of the standard Isabelle theorems is applicable. We cannot, using wrappers, interleave it ‘horizontally’ with the standard Isabelle theorems, only ‘vertically’ with lower precedence, and in consequence proof-search is inefficient. Unfortunately there seems no cure other than dedicated FM proof-search ML code, or to hack existing code to hardwire algorithms such as , and
Now consider our treatment of the logic of . This consists of equational theory such as (11) and (16), of intro- and elim- rules
and of discussed in remark 17
In this and in the equations immediately following we introduce two items of notation. here is not a conjunction (as previously used written ) but a meta-level IsabellePure universal quantification )). Also, a comma , denotes meta-level conjunction. I shall not be completely strict about distinguishing meta-level Pure from object-level HOL, but and where used will definitely denote the former.
As a simple example of a proof involving consider a proof of
Inductive reasoning tends to be resolution-based, so we prefer an algorithm in that style. Accordingly we apply the intro- and elim- rules above, along with the conjunction intro-rule , to obtain
Here ) and ) are unknowns which may be instantiated to any expression with free variables at most . The two freshness subgoals cannot be proved. We can use to introduce a fresh parameter into the context, but that only gives us
and ) cannot be instantiated to because is a new free variable not amongst . Thus we need to apply before the resolution steps and then the proof succeeds.
In another situation such as proving (31) the fresh name may be provided by the previous proof-context and we certainly do not want to apply it will cause unknowns to be instantiated to an irrelevant fresh parameter. It seems difficult to express a sensible and efficient compromise algorithm for this kind of proof-search.
In the rest of this section we step back and take a high-level view of these problems. In Isabelle and other theorem provers there are actually two kinds of variables. Free variables and unknowns Free variables are ‘universal’: they have an arbitrary value which ranges over all possible values. Unknowns are ‘existential’: they should, by the end of the proof-search, be instantiated to some specific term . With these built into the meta-level of IsabellePure the intro- and elim- rules for universal and existential quantification are easy to write. This need not be the case. For example in second-order λ-calculus existential quantification can be expressed using universal quantification. Theorem provers do not use this because it is nasty to work with in implementation.
It seems that the underlying problem may be that we are trying to encode using both and a kind of ‘freshness’ variable corresponding to the ‘new’ quantifier . The fact that we need both reflects the duality of mentioned in remark 10. Like unknowns, a freshness variable depends on a context, for which it is fresh, and two sufficiently fresh freshness variables may be assumed equal, ‘instantiated to each other’, where convenient (think for instance of proving (11) or (12)). Like universals, freshness variables when introduced extend the context, and other terms and variables may depend on them if they are introduced later (e.g. other freshness variables). Trying to usefully express this in a dedicated logic belongs to future work.
6 The technical lemmas
This section can be skipped. For the interested reader we show a simple algorithm in action, constructed using the tactics developed in section 4. The point is that it neatly settles most of (23) to (32), which means we have a decent algorithm. We skip to the fourth one (26)
Unfold definition 8 and apply . We obtain
Apply
then to obtain
It is now simple to instantiate ) and to , but we cannot apply to the conclusion and finish the proof because ) is on the left, not the right. I had elided the following detail: transposition is invertible on each type by (5) so . applies this as an intro-rule, to “draw transposition to the right”. With this elaboration the proof runs smoothly.
The proof of (27) runs along similar lines. To prove (28) we unfold definitions and use to obtain
If is a closed term solves this completely (otherwise proof fails, as it should).
(29), (30), (31), are proved by the same script as (26). In fact, the script also proves (27) though its behaviour for that goal, the path outlined in the previous paragraph, is a little special.
(32) underlies . The proof is best tailor-made. We rewrite it as and intro-resolve against (36) for , we now have , an instance of the axiom (9).
7 The state of the implementation
An IsabelleFM implementation exists but it is based on set theory rather than higher-order logic. This creates technical difficulties which ultimately proved insurmountable for the following reason. Consider the theorem
In HOL this is rendered as
where we include all type annotations. In sets the same theorem is
The difference is that when we intro-resolve against the HOL version we get one subgoal, whereas the sets version produces five (one each for each hypothesis of the implication, which must be established in order to apply it). A sets-based treatment of inductive datatypes overcomes this by implementing by some constructor which is is injective on the entire sets universe “by coincidence”, probably . In FM this is not possible for various reasons which we now sketch.
Atoms must be marked as belonging to atomic type, the quantifier introduces fresh variables of atomic type which must be marked as such, and atom-abstraction (which we have not discussed in this paper, see [8, Section 6] or [6, Section 5]) is fundamentally non-injective so that the typing conditions can actually get quite complex.
Considerable ingenuity went into minimising the impact of these typing conditions in a sets environment (this should soon be the subject of a technical report). The price of using a HOL environment is precisely its benefit, the relative rigidity the typing gives the theory relative to sets, with both theoretical and practical consequences. In the recently-published [8] we provide what we hope is an elegant solution to the theoretical difficulties which will also be implementable, and it remains to try implementing the approach.
8 Conclusions
This paper has given a very simplified account of the problem of producing an implementation of a new foundational system FM with new and unfamiliar predicates and constructors. We considered two simple examples
– Some theory of a datatype of types with universal types and relations of -equivalence for it (defined using FM structure) and (defined in a more traditional style).
– Some technical FM lemmas (23) to (32).
These examples illustrated a fairly rich and representative selection of problems. We presented solutions to these problems and discussed their limitations. Another contribution of this paper is in what it elides there are complications to automating FM which this paper has tried to bring out, but the short, slick, parts in between are the proof of how far we have already come.
References
. FreshML homepage. http://www .cl.cam .ac.uk/~amp12/research/freshml/index.html
2. Abadi, Luca Cardelli, Pierre-Louis Curien, and Jean-Jacques . Explicit substitutions. In Conference Record of the Seventeenth Annual ACM Symposium on Principles of Programming Languages, San Francisco, California, pages 31–46. ACM, 1990.
3. H. P. Barendregt. The Lambda Calculus: its Syntax and Semantics (revised ed.), volume 103 of Studies in Logic and the Foundations of Mathematics. North-Holland, Amsterdam, 1984.
4. 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.
5. 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.
6. M. J. Gabbay and A. M. Pitts. A new approach to abstract syntax with variable binding. Formal Aspects of Computing, 2001. Special issue in honour of Rod Burstall. To appear.
7. Murdoch J. Gabbay. A Theory of Inductive Definitions with alpha-Equivalence. PhD thesis, Cambridge, UK, 2000.
8. Murdoch J. Gabbay. FM-HOL, a higher-order theory of names. In 35 Years of Automath. Heriot-Watt University, Edinburgh, Scotland, April 2002.
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. James McKinna and Robert Pollack. Some lambda calculus and type theory formalized. Journal of Automated Reasoning, 23(3-4):373–409, 1999.
11. Frank Pfenning and Conal Elliot. Higher-order abstract syntax. In SIGPLAN Conference on Programming Language Design and Implementation, pages 199–208, 1988.
12. A. M. Pitts. Nominal logic: A first order theory of names and binding. In N. Kobayashi and B. C. Pierce, editors, Theoretical Aspects of Computer Software, 4th International Symposium, TACS 2001, Sendai, Japan, October 29-31, 2001, Proceedings, volume 2215 of Lecture Notes in Computer Science, pages 219–242. Springer-Verlag, Berlin, 2001.
13. 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.
. Isabelle Projects. http://www.cl.cam.ac.uk/users/lcp/Isabelle/projects.html
15. J. Truss. Permutations and the axiom of choice. In H.D.Macpherson R.Kaye, editor, Automorphisms of first order structures, pages 131–152. OUP, 1994.
Notes
The author gratefully acknowledges the funding of UK EPSRC grant GR/R07615 and thanks Andrew Pitts for his suggestions for improvements.
Cf. the work of McKinna and Pollack in the LEGO system, e.g. [10]. FM is quite different but sometimes echoes this work.
Extending FM to infinitary syntax is possible and interesting.