strange verification result

Mar 23, 2016 at 7:27 PM
Dafny fails to verify the following code. However, if I remove some irrelevant code, i.e. a main method to print out some text, verification succeed. Details follows:
function lcp_rec (a: seq<int>, x : int, y : int) : int
requires 0 <= x < |a| 
requires 0 <= y < |a|
{
    lcp_rec_aux (a, x, y, 0)
}

function lcp_rec_aux (a: seq<int>, x : int, y : int, l : int) : int
requires 0 <=x < |a| 
requires 0 <= y < |a|
requires 0 <= x+l <= |a|
requires 0 <= y+l <= |a| 
requires 0 <= l
ensures  0 <= x+lcp_rec_aux(a, x, y, l) <= |a| //wd
ensures  0 <= y+lcp_rec_aux(a, x, y, l) <= |a| //wd
decreases |a| - l
{
    if (x+l<|a| && y+l<|a|)
    then (
        if (a[x+l] == a[y+l]) then lcp_rec_aux(a, x, y, l+1)
        else l
    )
    else l
}

predicate prop_lcp_rec_aux (a: seq<int>, x : int, y : int, l : int)
requires 0 <=x < |a| 
requires 0 <= y < |a|
requires 0 <= x+l <= |a|
requires 0 <= y+l <= |a| 
requires 0 <= l
{
  forall i :: l <= i < lcp_rec_aux(a, x, y, l) ==> a[x+i] == a[y+i]
}

predicate prop_lcp_rec (a: seq<int>, x : int, y : int)
requires 0 <=x < |a| 
requires 0 <= y < |a|
{
    // this is very strange !! ask this in the thread
  forall i :: 0 <= i < lcp_rec_aux(a, x, y, 0) ==> a[x+i] == a[y+i]
  //prop_lcp_rec_aux (a, x, y, 0) && 
  //(prop_lcp_rec_aux (a, x, y, 0) <==> (forall i :: 0 <= i < lcp_rec(a, x, y) ==> a[x+i] == a[y+i]))
}


lemma eq_prop_lcp_rec (a: seq<int>, x : int, y : int)
requires 0 <=x < |a| 
requires 0 <= y < |a|
ensures prop_lcp_rec(a,x,y) == prop_lcp_rec_aux(a,x,y,0)
{
}

method Main ()
{
 var s:seq<int> := [1,2,4];
    print "Verify This 2012 : LCP is ", (s[1 .. 1] == s[2..2]);
}
Link: http://rise4fun.com/Dafny/JTwFB

Also, if I change the definition of the predicate prop_lcp_rec to
predicate prop_lcp_rec (a: seq<int>, x : int, y : int)
requires 0 <=x < |a| 
requires 0 <= y < |a|
{
    // this is very strange !! ask this in the thread
  prop_lcp_rec_aux (a, x, y, 0) && 
  (prop_lcp_rec_aux (a, x, y, 0) <==> (forall i :: 0 <= i < lcp_rec(a, x, y) ==> a[x+i] == a[y+i]))
}
and keep the main method, it succeed again. Any explanation ?


Thanks in advance.

Yuhui