Isabelle: Unsupported recursive occurrence of a datatype via type constructor "Set.set"

Question

The problem

I am wondering if is there a natural way of encoding in Isabelle a grammar like this:

 type_synonym Var = string
 datatype Value = VInt int | ...
 datatype Cmd = Skip | NonDeterministicChoice "Cmd set" | ...

The motivation would be to give definition a few specification commands in terms of Non deterministic choice, e.g.:

 Magic == NonDeterministicChoice {}
 Rely c r z = Defined using set compreehension and NonDeterministicChoice

Isabelle complains about the recursive occurrence of type "Cmd" in "Cmd set", i.e.:

Unsupported recursive occurrence of type "Cmd" via type constructor "Set.set" in type expression "Cmd set". Use the "bnf" command to register "Set.set" as a bounded natural functor to allow nested (co)recursion through it

Looking the Isabelle error message when I use set, I couldn't figure out how to register the bounded natural functor for the type 'set' in this context, so I decided to try a speculative solution.

Speculative solution

Instead, if I use an inductively defined datatype such as list, Isabelle does not complain e.g.

datatype Cmd = Skip | NonDeterministicChoice "Cmd list" | ...

Lists are not the right abstraction here, but I give it a go to see if it would work or not. The immediate effect of using lists is that, instead of use set comprehension I need to use sequence filtering, and the problem then become to assume the existence of two lists: one containing all elements of Cmd, and other containing all elements of Value.

I declared two uninterpreted constants:

consts Values :: "Value list"
consts Programs :: "Cmd list"

Because lists are finite, it makes more sense to explain the constants as "all elements (of interest) of Cmd" and "all values (of interest)". Say, all elements of interest are those that can be represented in the memory of a computer.

By the same argument, I could just declare a constant NonDeterministicChoiceSet

consts NonDeterministicChoiceSet :: "Cmd set ⇒ Cmd"

and explain it (informally) as a function that receives a set of Cmd, and returns the correspondent NonDeterministicChoice fed with the list containing all the elements of the set given as argument, ordered by some criteria, say lexicographic order. Then, rather than use "NonDeterministicChoice" when giving a semantics, I would give a semantics for "NonDeterministicChoiceSet" and only use "NonDeterministicChoiceSet" in the theory.

Questions

1. Does this modelling makes sense?
2. Is there a better way of represent this grammar?
3. Is Isabelle the appropriated theorem-prover if I want to represent this grammar? I experimented define this grammar in Z/Eves, for example, and it raised no complains.

Thanks! :-)

Answer 1

The theoretical explanation

First of all, the notion of a datatype of commands that allow non-deterministic choice from an arbitrary set of commands is deeply problematic. I will explain why.

Suppose you had a datatype

datatype Cmd = Skip | NonDeterministicChoice "Cmd set"

like you wanted. Let A := (UNIV :: Cmd), i.e. the set of all valid commands. Then, surely, the function

f: P(A) → A, X ↦ NonDeterministicChoice X

is an injective function from the power set of A into A. By Cantor's diagonalisation theorem, this is impossible. What does that mean? It means that there can be no such thing as the ‘set of all commands’ for the programming language you defined. This makes your language very difficult to work with. I do not know anything about Z/EVES, but if it allows such a datatype definition, I am very sceptical of its consistency.

The technical explanation

That was the theoretical reason for why what you want to do is problematic. The precise technical reason why your datatype definition fails is, as the error message suggests, that set is not a bounded natural functor (BNF). I am hardly an expert for BNFs, but as far as I know, the problem here is that, as illustrated above, allowing nested datatype recursion with set can make datatypes ‘too large’.

How to get around it

You already noted that lists work but are not ideal. What you can use instead of lists is finite sets (fset) or countable sets (cset). These are bounded natural functors. I have not worked with either of them myself, but a quick look suggests that fset is probably nicer to work with, so if you only want to select non-deterministically from a finite set of commands, fset is the way to go. If you need a countable number of alternatives, use cset. Both of them can be found in ~~/src/HOL/Library/, the theories are called FSet and Countable_Set_Type, respectively.

fset has a lot of syntax that makes it look a lot like normal sets ({||} instead of {}, |∈| instead of ∈); cset supports pretty much the same operations, but without the nice syntax. You can, of course, convert fset/cset to set and, if the set is finite/countable, also vice versa. This means that you can use set comprehensions ranging over all valid commands, filtering out the ones you do not want, but the resulting set must be finite/countable.

Note that the problem mentioned in the beginning still remains. When you use fset, you can non-deterministically choose from a finite set of commands, but the set of all commands will not be finite. If you use cset, you can choose from any finite or countably infinite set of commands, but the set of all commands will not be countable. This is a deeply-rooted logical problem that I do not think you can get around. (although logicians can be surprisingly inventive when it comes to these things)

Other modelling approaches

I do not understand what your NonDeterministicChoiceSet does or is supposed to do. The construction of ‘all programs/values of interest’ strikes me as somewhat strange and artificial. The way I have seen non-determinism modelled formally was always that you either choose non-deterministically between two programs, not an entire set, or that you do not choose between programms at all, but non-deterministically choose a value from a set of values and then depend on that value. Both variants obviously do not cause the problem I mentioned above.

Without knowing more about what exactly it is that you want to do, it is difficult to say what approach is best for your problem, but the one I outlined before with fset/cset is probably the one that is closest to your original intent.

Analysing the cardinality of the set of commands

Since it was asked in the comment below, I will now attempt to show how ‘big’ the set of commands is in terms of the bound imposed upon the size of the sets in the non-deterministic choice operator. Disclaimer: I know very little about cardinals, so I am not absolutely sure that all of my reasoning here is completely correct.

Let A be the set of all commands and let [A]^κ denote the set of all subsets of A with cardinality at most κ (e.g. in your case, κ = ℵ₀, where ℵ₀ is the cardinality of the natural numbers). Through your nondeterministic choice operator, you have an injection [A]^κ → A, i.e. |A| ≥ |[A]^κ|.

If κ ≥ |A|, then [A]^κ is simply 2^A (the powerset of A) and therefore |A| ≥ |2^A|, which contradicts Cantor's theorem. We therefore know that κ < |A|. (Practically, this is what I said before: you must restrict your non-deterministic choice to sets of commands of some bounded cardinality κ that is smaller than the cardinality of all commands)

Now, since |A| ≥ κ, we can pick a set K with |K| = κ and injectively map any subset of K to a set from [A]^κ, i.e. we have an injection 2^K → [A]^κ and therefore |A| ≥ |[A]^κ| ≥ |2^K| = 2^κ.

In conclusion, if you allow non-deterministic choice over a set of commands of cardinality at most κ, the set of commands will at least have cardinality 2^κ, which is strictly more than κ by Cantor's theorem. In particular, if you let κ = ℵ₀, this means that if you allow choice from any countable set of commands, your set of commands will be uncountable.