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

document FC role in unrolling, validate_induct #152

Open
Bronsa opened this issue Apr 12, 2021 · 0 comments
Open

document FC role in unrolling, validate_induct #152

Bronsa opened this issue Apr 12, 2021 · 0 comments

Comments

@Bronsa
Copy link
Member

Bronsa commented Apr 12, 2021

e.g. given

type t = { x : unit list; y : unit list }
let length a = List.length a.x + List.length a.y
let rec g xs =
  match xs.x, xs.y with
  | _::x, y when List.length xs.x > List.length xs.y ->
    Some {x;y}
  | x,_::y ->
    g {x;y}
  | _ -> None

we can do

lemma g_len xs =
  match g xs with
  | None -> true
  | Some xs' ->
    length xs' < length xs
[@@fc] [@@auto]
let rec f xs =
  match g xs with
  | None -> ()
  | Some xs ->
    f xs
[@@measure Ordinal.of_int (length xs)]
[@@disable length]

or

let rec f xs =
  match g xs with
  | None -> ()
  | Some xs ->
    f xs
[@@measure Ordinal.of_int (length xs)]
[@@validate_induct]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

No branches or pull requests

1 participant