- Project 3 Extension
- Mystery tactics
- Crypto theory
- Project 3 is posted
- Runtime Checks to Type Checks
- Dependent Register File
- Bounded register file
- Array model from class
- distr_rev
- Eval on theorems

Blog

Following is the Array model of register file contents developed in class today. We will add to the model next week to capture the size of the register file.

The proofs use mostly use commands defined in class with a couple of exceptions. In some places I use `trivial`

rather than `reflexivity`

. `trivial`

does a bit more work than reflexivity and can be customized. Feel free to use it in your proofs if you woule like.

I use `unfold`

in several places where I want a function replaced by its definition. `unfold f`

expands the definition in place. If `f`

is defined:

`Definition f(x:nat):nat := x + 1.`

then `unfold`

applied to the goal `f 1 = 2`

results in the goal:

`1 + 1 = 2`

I use `unfold`

in a couple of places rather than `simpl`

when `simpl`

doesnâ€™t work or is too involved. Note that `unfold`

can be used on assumptions using the `in`

syntax to specify the assumption.

Here is the [Array] module complete with proofs:

```
Require Import Omega.
Module Array.
Fixpoint leb (m:nat) : nat -> bool :=
match m with
| O => fun _:nat => true
| S m' =>
fun n:nat => match n with
| O => false
| S n' => leb m' n'
end
end.
(** Register contents. Either a natural number value or unknown. *)
Inductive RC : Type :=
| val : nat -> RC
| unknown : RC.
Notation "??" := unknown.
(** Register file contents. Function from natural to RC. *)
Definition RFC : Type := nat -> RC.
(** Empty register file contents *)
Definition empty_rf:RFC := (fun n:nat => ??).
(** [get] applies the register file function to its argument *)
Definition get(i:nat)(f:RFC):RC := (f i).
(** [put] uses an [if] expression to modify an existing register file *)
Definition put(i:nat)(f:RFC)(v:RC):RFC :=
(fun n:nat => if (beq_nat i n) then v else f n).
(** Some tests to make sure the implementation is close to correct. *)
Example test1: (get 3 (put 3 empty_rf (val 3))) = (val 3).
Proof. reflexivity. Qed.
Example test2: (get 2 (put 3 empty_rf (val 3))) = ??.
Proof. reflexivity. Qed.
Example test3: (get 4 (put 3 empty_rf (val 3))) = ??.
Proof. reflexivity. Qed.
(** Making the test slightly more abstract by checking all contents values *)
Theorem update_position_3: forall m, (get 3 (put 3 empty_rf (val m))) = (val m).
Proof.
intros.
trivial.
Qed.
(** Lemma showing that [beq] is reflexive. Will be used in a later proof *)
Lemma beq_refl: forall i, beq_nat i i = true.
Proof.
intros.
induction i.
reflexivity.
auto.
Qed.
(** All elements of the empty register file are unknown *)
Theorem empty_empty: forall i , (get i empty_rf) = ??.
Proof.
intros. reflexivity.
Qed.
(** [get] applied to a [put] on the same index updates the register file
contents. This is correctness of the update function. *)
Theorem update_immediate: forall v i rfc,
(get i (put i rfc (val v))) = val v.
Proof.
intros.
unfold get.
unfold put.
rewrite beq_refl.
reflexivity.
Qed.
(** [get] applied to a [put] on different indexes results in the value
before updating. An invariant on update. *)
Theorem update_invariant: forall v i j rfc,
(beq_nat j i) = false -> (get i (put j rfc (val v))) = rfc i.
Proof.
intros.
unfold get.
unfold put.
rewrite H.
trivial.
Qed.
End Array.
```