Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

saw-core-coq: Give proper definitions to genWithProof and atWithProof #1784

Closed
RyanGlScott opened this issue Dec 12, 2022 · 1 comment · Fixed by #1786
Closed

saw-core-coq: Give proper definitions to genWithProof and atWithProof #1784

RyanGlScott opened this issue Dec 12, 2022 · 1 comment · Fixed by #1786
Assignees
Labels
subsystem: saw-core-coq Issues related to converting saw-core to Gallina for use with the Coq/Rocq theorem prover type: enhancement Issues describing an improvement to an existing feature or capability

Comments

@RyanGlScott
Copy link
Contributor

When generating Coq code, Heapster frequently translates array updates to code involving updBVVec and repeatBVVec. These, in turn, are defined in terms of the genWithProof and atWithProof axioms. Because these are axioms, they do not reduce in Coq, which makes them more difficult to use in practice. There isn't any good reason for them to be axioms on the Coq side, however, as we can define them relatively easily. Something like this should suffice:

Program Fixpoint
  genWithProof
    (n : nat)
    (a : Type) :
    (forall (i : nat), IsLtNat i n -> a) -> Vec n a :=
  match n as n' return (forall (i : nat), IsLtNat i n' -> a) -> Vec n' a with
  | O   => fun _ => VectorDef.nil a
  | S m => fun f => VectorDef.cons a (f 0 _) m (genWithProof' m a (fun i prf => f (S i) _))
  end.
Next Obligation.
  apply le_n_S. apply le_0_n.
Qed.
Next Obligation.
  apply le_n_S. exact prf.
Qed.

Program Fixpoint
  atWithProof
    (n : nat)
    (a : Type)
    (v : Vec n a)
    (i : nat) :
    IsLtNat i n -> a :=
  match i as i', n as n' return Vec n' a -> IsLtNat i' n' -> a with
  | _,   O   => fun _ prf =>
                match Nat.nlt_0_r _ prf with end
  | O,   S y => fun v' prf => VectorDef.hd v'
  | S x, S y => fun v' prf => atWithProof' y a (VectorDef.tl v') x _
  end v.
Next Obligation.
  apply le_S_n. exact prf.
Qed.
@RyanGlScott RyanGlScott added type: enhancement Issues describing an improvement to an existing feature or capability subsystem: saw-core-coq Issues related to converting saw-core to Gallina for use with the Coq/Rocq theorem prover labels Dec 12, 2022
@RyanGlScott RyanGlScott self-assigned this Dec 12, 2022
@eddywestbrook
Copy link
Contributor

Yep, these both seem reasonable. Except you might want to use Defined instead of Qed if you want them to reduce.

RyanGlScott added a commit that referenced this issue Dec 12, 2022
This provides explicit Coq definitions for SAWCore's `atWithProof` and
`genWithProof` functions, which allow them to compute. It also proves the
auxiliary `at_gen_BVVec` and `gen_at_BVVec` lemmas, a feat which is now possible
thanks to the aforementioned computability.

Fixes #1784.
RyanGlScott added a commit that referenced this issue Dec 12, 2022
This provides explicit Coq definitions for SAWCore's `atWithProof` and
`genWithProof` functions, which allow them to compute. It also proves the
auxiliary `at_gen_BVVec` and `gen_at_BVVec` lemmas, a feat which is now possible
thanks to the aforementioned computability.

To make this work with the current module ordering, I needed to wire in the
definition of `IsLtNat` into `SAWCoreScaffolding`, which proves
straightforward.

Fixes #1784.
RyanGlScott added a commit that referenced this issue Dec 13, 2022
This provides explicit Coq definitions for SAWCore's `atWithProof` and
`genWithProof` functions, which allow them to compute. It also proves the
auxiliary `at_gen_BVVec` and `gen_at_BVVec` lemmas, a feat which is now possible
thanks to the aforementioned computability.

To make this work with the current module ordering, I needed to wire in the
definition of `IsLtNat` into `SAWCoreScaffolding`, which proves
straightforward.

Fixes #1784.
@mergify mergify bot closed this as completed in #1786 Dec 13, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
subsystem: saw-core-coq Issues related to converting saw-core to Gallina for use with the Coq/Rocq theorem prover type: enhancement Issues describing an improvement to an existing feature or capability
Projects
None yet
Development

Successfully merging a pull request may close this issue.

2 participants