Frama-C-discuss mailing list archives

This page gathers the archives of the old Frama-C-discuss archives, that was hosted by Inria's gforge before its demise at the end of 2020. To search for mails newer than September 2020, please visit the page of the new mailing list on Renater.

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Frama-c-discuss] Verifying recursive functions

Hello Boris,

the language specification of ACSL (http://frama-c.cea.fr/download/acsl_1.4.pdf 
) contains on page 38
the faculty function with the follwing specification.

/*@ requires n <= 12;
   @ decreases n;
   @*/
int fact(int n)
{
     if (n <= 1) return 1;
     return n * fact(n-1);
}

When I run jessie on this example, then it can verify
that the call of "fact" inside the function body satisfies the  
"precondition for user call".
This is of course much less then you asked for.

Let's keep trying...

Regards Jens


Am 18.03.2009 um 11:56 schrieb Hollas Boris (CR/AEY1):

> Hello,
>
> I use Spec# with Boogie and the Z3 SMT-solver as back-end. Yet, I  
> haven't found a way to verify recursive functions. Therefore, I  
> wonder whether this is possible with frama-c and the Jessie plugin.
>
> For example, consider the following recursive implementation of the  
> factorial function:
>
>     static int fac(int n)
>     requires n >= 0;
>     ensures result == product {int i in (1..n); i};
>     {
>         if(n==0) return 1;
>         else return n*fak(n-1);
>     }
>
> Spec# is not able to prove the postcondition using default settings.  
> Furthermore, I don't know if I can instruct Spec# or the provers to  
> induce on n.
>
> Would frama-c be able to verify the function above?
>
> Cheers,
> Boris
>
> _______________________________________________
> Frama-c-discuss mailing list
> Frama-c-discuss at lists.gforge.inria.fr
> http://lists.gforge.inria.fr/cgi-bin/mailman/listinfo/frama-c-discuss


-- 

Dr.-Ing. Jens Gerlach
Eingebettete Systeme - EST

Fraunhofer-Institut f?r Rechnerarchitektur und Softwaretechnik, FIRST
Kekul?stra?e 7
12489 Berlin
Germany
http://www.first.fraunhofer.de


-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.gforge.inria.fr/pipermail/frama-c-discuss/attachments/20090319/406a1437/attachment.htm