How to define functions with overlapping patterns?

Question

I'm trying to define a conjunction function for 4-valued logic (false, true, null, and error):

datatype 'a maybe = Just "'a" | Nothing | Error
type_synonym bool4 = "bool maybe"

abbreviation JF :: "bool4" where "JF ≡ Just False"
abbreviation JT :: "bool4" where "JT ≡ Just True"
abbreviation BN :: "bool4" where "BN ≡ Nothing"
abbreviation BE :: "bool4" where "BE ≡ Error"

fun and4 :: "bool4 ⇒ bool4 ⇒ bool4" where
  "and4 JF b = JF"
| "and4 a JF = JF"
| "and4 BE b = BE"
| "and4 a BE = BE"
| "and4 BN b = BN"
| "and4 a BN = BN"
| "and4 a b  = JT"

I expect that the first patterns have a priority over the last patterns.

It seems that the definition is wrong. I'm trying to evaluate the following expressions:

value "and4 JF b"
value "and4 a JF"

The first one returns JF as expected. But the second one can't be simplified.

As result I can't prove commutativity of the conjunction:

lemma and4_commut:
  "and4 a b = and4 b a"

It's recomended to use function instead of fun in "Defining Recursive Functions in Isabelle/HOL" by Alexander Krauss. But I get 12 false subgoals:

function and4 :: "bool4 ⇒ bool4 ⇒ bool4" where
  "and4 JF b = JF"
| "and4 a JF = JF"
| "and4 BE b = BE"
| "and4 a BE = BE"
| "and4 BN b = BN"
| "and4 a BN = BN"
| "and4 a b  = JT"
  apply pat_completeness
  apply auto

I guess it's because the function has conflicting patterns. For example, and4 JF BE are matched by the 1st and 4th patterns. And the result of conjuction could be either JF or BE.

What is a right way to define such a functions? And how to prove its commutativity? I can use a case of construction but it complicates the function definition.

Manuel Eberl Manuel Eberl · Accepted Answer · 2017-03-22T07:52:06

The value command can usually not handle free variables (like a) very well.

You can, however, prove the theorem FooAndValue a JF = JF by case distinction:

lemma and4_JF_right [simp]: "and4 a JF = JF"
proof (cases a)
  case (Just b)
  thus ?thesis by (cases b) simp_all
qed simp_all

Or, a bit less verbose, with a custom case rule:

lemma bool4_cases [case_names JF JT BN BE]: 
  "(a = JF ⟹ P) ⟹ (a = JT ⟹ P) ⟹ (a = BN ⟹ P) ⟹ (a = BE ⟹ P) ⟹ P"
  by (cases a) auto

lemma and4_JF_right [simp]: "and4 a JF = JF"
  by (cases a rule: bool4_cases) simp_all

With this, proving commutativity can be done by a simply induction in a single line.

The reason why the fun command does not give you and4 a JF = JF as a theorem even though you literally wrote that in the definition is that indeed that you have overlapping patterns and use sequential pattern matching, i.e. the second ‘equation’ in the function definition only applies if the first one does not.

fun has to resolve the overlapping patterns in order to accomodate this sequential matching, and after this, it's not obvious (in general) that and4 a JF = JF holds. You can look at and4.simps to see exactly what fun did.

If I remember correctly, you can also use plain function to have overlapping patterns without sequential matching, but then you have to prove that the overlapping equations are compatible. In your case, I don't think that would make things any easier.

Another thing that you could do (and that may be easier to use, depending on your use case) would be not to use bool maybe, but define a 4-constructor datatype and define a linear ordering on that type, where JF < BE < BN < JT, and then and4 is equivalent to min.

How to define functions with overlapping patterns?

1 Answers