Skip to content

Instantly share code, notes, and snippets.

@hacklex
Created November 4, 2022 17:17
Show Gist options
  • Select an option

  • Save hacklex/eaec473662d4644f8a38f435f3549b76 to your computer and use it in GitHub Desktop.

Select an option

Save hacklex/eaec473662d4644f8a38f435f3549b76 to your computer and use it in GitHub Desktop.
Performance issue
module FStarFreeze
let unbounded (f: nat -> int) = forall (m: nat). exists (n:nat). abs (f n) > m
assume val f : (z:(nat -> int){unbounded z})
let g : (nat -> int) = fun x -> f (x+1)
let find_above_for_g (m:nat) : Lemma(exists (i:nat). abs(g i) > m) =
assert (unbounded f); // apply forall to m
eliminate exists (n:nat). abs(f n) > m
returns exists (i:nat). abs(g i) > m with _. begin
let m1 = abs(f n) in
assert (m1 > m); //prover hint
if n>=1 then assert (abs(g (n-1)) > m)
else begin
assert (n<=0); //arithmetics hint
eliminate exists (n1:nat). abs (f n1) > m1
returns exists (i:nat). abs(g i) > m with _.
begin
assert (n1>0);
assert (abs (g (n1-1)) > m);
()
end
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment