--- layout: fc_discuss_archives title: Message 56 from Frama-C-discuss on March 2009 ---
[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