Discussion:
[isabelle] a question of formalization of parameterized-word (bit-vector)
(too old to reply)
Li Yongjian
2016-09-11 05:30:48 UTC
Permalink
Raw Message
Dear experts:
Now I meet a problem of formalization of a parameterized bit-vector.
Here a parameterized bit-vector. means that the width of the bit vector is
a parmeterize, for instance a variable in a program (hardware design) is a
word of some length k. I want to prove that some property P on the varaible
is correct for any k.

I notice that the examples usually are on a fixed-length word such as 32
word, 8 word. For instance, a lemma
lemma "0b110 AND 0b101 = (0b100 :: 5 word)" by simp

I want to have a lemma such as
lemma lemmaTest: "0b110 AND 0b101 = (0b100 :: k word)" by simp, where k is
any natural number which is greater than or equal to 3.

But obviously lemmaTest is not allowed in Isabelle.

How to formalize such a lemma? Or I can be shown some examples which
formalize the parameterized-word problems.

regards!
C. Diekmann
2016-09-11 10:38:08 UTC
Permalink
Raw Message
Hi,
Post by Li Yongjian
How to formalize such a lemma? Or I can be shown some examples which
formalize the parameterized-word problems.
We did something quite similar:

https://github.com/diekmann/Iptables_Semantics/blob/master/thy/IP_Addresses/Lib_Word_toString.thy#L100

But once you have an assumption, in your case "len_of TYPE('k) >= 3",
proofs get really hard because Word_Lib cannot help you much. Those
restrictions about a minimum length for a word probably only come from
hard-coded constants, maybe you can rephrase the complicated lemma without
the use of hard-coded constants?

Best,
Cornelius

Loading...