Skip to content

Instantly share code, notes, and snippets.

@kinoh
Created February 22, 2015 14:01
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kinoh/79fe12c8ff439110e9c8 to your computer and use it in GitHub Desktop.
Save kinoh/79fe12c8ff439110e9c8 to your computer and use it in GitHub Desktop.
Fstar says "An unknown assertion in the term at this location was not provable"?
module Range
val length: list 'a -> Tot nat
let rec length l =
match l with
| [] -> 0
| _::tl -> 1 + length tl
val range: a:nat -> b:nat -> Tot (list nat)
(decreases (b-a))
let rec range a b =
if b-a <= 0
then []
else a :: (range (a+1) b)
(*
induction_hyp := length (range (a+1) b) = b-(a+1)+1
length (range a b)
= length (a :: (range (a+1) b)) (range)
= 1 + length (range (a+1) b) (length)
= 1 + b-a (induction_hyp)
*)
val range_correctness: a:nat -> b:nat{b>=a}
-> Lemma (length (range a b) = b-a+1)
(decreases (b-a))
let rec range_correctness a b =
if b-a = 0
then ()
else range_correctness (a+1) b
(* my fstar(fdbbead) says:
Error range.fst(27,0-30,31): An unknown assertion in the term at this location w
as not provable
Verified module: Prims
Verified module: Range
Error: 1 errors were reported (see above)
*)
@kinoh
Copy link
Author

kinoh commented Mar 6, 2015

I've finally found L25 "b-a+1" interpreted as "b-(a+1)" (right associative!?!?!!?!???!!!!).

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment