ocaml-gospel / ortac

Runtime assertion checking based on Gospel specifications
https://ocaml-gospel.github.io/ortac/
MIT License
36 stars 10 forks source link

[wrapper] Add support for models #224

Open n-osborne opened 4 months ago

n-osborne commented 4 months ago

Gospel is moving towards talking only of logical models in the specifications (not OCaml values).

Ortac/QCheck-STM is already using relational postconditions to propose model-based testing (maintaining an implementation of the logical model in parallel of the OCaml value).

There are some clearly identified limitations on taking this approach for Ortac/Wrapper (see section 7.1 of Clément Pascutto PhD dissertation

I propose to take another approach with Ortac/Wrapper, inspired by bisimulation (see also Section 5 of this paper)

A bisimulation is a property on labeled transition systems.

We can see function calls (and the corresponding relational postconditions) as such labels.

We then want to check that:

   a   ~  m
   |      |
 φ |      | σ
   V      V
   a' ~   m'

Where:

Obviously, we can't generate the projection for the user (we mainly deal with abstract types).

Following the same idea as #214, I propose that the user provides these projections in a module-based configuration, relying on a naming convention.

Then, when/before translating the Gospel terms, we will substitute access to a logical model (it is coded as the access to a field in current Gospel) with a call to the right projection.

Whenever a projection is not available, we can skip the Gospel term.

That way, given an interface like this one (in queue.mli file):

type 'a t
(*@ mutable model contents : 'a list *)

val create : unit -> 'a t
(*@ q = create ()
    ensures q.contents = [] *)

val push : 'a -> 'a t -> unit
(*@ push a q
    modifies q.contents
    ensures q.contents = a :: old q.contents *)

Ortac/Wrapper would generate something along the line of:

include Queue

let contents = .... (* taken from the configuration module *)

let create () =
  let q = create () in
  assert (contents q = []);
  q

let push a q =
  let q' = copy q in
  push a q;
  assert (contents q = a :: contents q')