functional programming - How do I prove that two Fibonacci implementations are equal in Coq? -

-

i've 2 fibonacci implementations, seen below, want prove functionally equivalent.

i've proved properties natural numbers, exercise requires approach cannot figure out.

the textbook i'm using have introduced following syntax of coq, should possible prove equality using notation:

<definition> ::= <keyword> <identifier> : <statement> <proof>  <keyword> ::= proposition | lemma | theorem | corollary  <statement> ::= {<quantifier>,}* <expression>  <quantifier> ::= forall {<identifier>}+ : <type>                | forall {({<identifier>}+ : <type>)}+  <proof> ::= proof. {<tactic>.}* <end-of-proof>  <end-of-proof> ::= qed. | admitted. | abort.

here 2 implementations:

fixpoint fib_v1 (n : nat) : nat :=   match n   | 0 => o   | s n' => match n'             | o => 1             | s n'' => (fib_v1 n') + (fib_v1 n'')             end   end.  fixpoint visit_fib_v2 (n a1 a2 : nat) : nat :=   match n   | 0 => a1   | s n' => visit_fib_v2 n' a2 (a1 + a2)   end.

it pretty obvious these functions compute same value base case n = 0, induction case harder?

i've tried proving following lemma, i'm stuck in induction case:

lemma about_visit_fib_v2 :   forall j : nat,     visit_fib_v2 (fib_v1 (s j)) ((fib_v1 j) + (fib_v1 (s j))) = (fib_v1 (add_v1 (s j))). proof.   induction [| i' ihi'].    intro j.   rewrite -> (unfold_visit_fib_v2_0 (fib_v1 (s j)) ((fib_v1 j) + (fib_v1 (s j)))).   rewrite -> (add_v1_0_n (s j)).   reflexivity.    intro j.   rewrite -> (unfold_visit_fib_v2_s i' (fib_v1 (s j)) ((fib_v1 j) + (fib_v1 (s j)))).   admitted.

where:

fixpoint add_v1 (i j : nat) : nat :=   match   | o => j   | s i' => s (add_v1 i' j)   end.

a note of warning: in follows i'll try show main idea of such proof, i'm not going stick subset of coq , won't arithmetic manually. instead i'll use proof automation, viz. ring tactic. however, feel free ask additional questions, convert proof suit purposes.

i think it's easier start generalization:

require import arith.    (* `ring` tactic *)  lemma fib_v1_eq_fib2_generalized n : forall a0 a1,   visit_fib_v2 (s n) a0 a1 = a0 * fib_v1 n + a1 * fib_v1 (s n). proof.   induction n; intros a0 a1.   - simpl; ring.   - change (visit_fib_v2 (s (s n)) a0 a1)            (visit_fib_v2 (s n) a1 (a0 + a1)).     rewrite ihn. simpl; ring. qed.

if using ring doesn't suit needs, can perform multiple rewrite steps using lemmas of arith module.

now, let's our goal:

definition fib_v2 n := visit_fib_v2 n 0 1.  lemma fib_v1_eq_fib2 n :   fib_v1 n = fib_v2 n. proof.   destruct n.   - reflexivity.   - unfold fib_v2. rewrite fib_v1_eq_fib2_generalized.     ring. qed.

Comments

Post a Comment

Popular posts from this blog

php - How to display all orders for a single product showing the most recent first? Woocommerce -

-
i have password protected page on frontend. on page, want display full list of purchases associated single woocommerce product id. option 1: i've looked through woocommerce docs , , found: wc_cli_order , list_( $args, $assoc_args ) function lists orders. presumably, orders can filtered product id [--=] filter orders based on order property. line item fields (numeric array, started index zero): line_items.0.product_id option 2: i found article , based on customer id. i've modified code based on guesses meta_key , meta_value. $customer_orders = get_posts( array( 'numberposts' => -1, 'meta_key' => '_product', 'meta_value' => get_product_id(), 'post_type' => wc_get_order_types(), 'post_status' => array_keys( wc_get_order_statuses() ), ) ); how display orders single product showing recent order first? here solution put based on these articles: http://www.w...
Read more

asp.net - How to correctly use QUERY_STRING in ISAPI rewrite? -

-
i'm having difficult time , hope guys can help. using helicon isapi rewrite version 3.1.0.104 on our iis server. edit http.conf file , have tried , still fail. this trying do: redirect url: https://www.domain.com/switch-by-version?version=2.8.5.2594 to: https://test.domain.com/load/load.aspx?tver=2.8.5.2594 the version number @ end source url change, , need target url have same version number @ end of url example above shows. i tried following not work: rewritecond %{query_string} ^version=(\d\d?)\.(\d\d?)\.(\d\d?)\.(.*)$ [nc] rewriterule ^/switch-by-version(.*)$ https://test.domain.com/load/load.aspx?tver=%1 [r=307,nc,l] any appreciated! thanks. if it's running in equivalent context of .htaccess , rule shouldn't start / . here's simpler version: rewritecond %{query_string} ^version=(\d+\.\d+\.\d+(?:\..+)?)$ [nc] rewriterule ^switch-by-version/?$ https://test.domain.com/load/load.aspx?tver=%1 [r=307,nc,l]
Read more

angularjs - How restrict admin panel using in backend laravel and admin panel on angular? -

-
https://scotch.io/tutorials/token-based-authentication-for-angularjs-and-laravel-apps following tutorials, try write authentication restrict admin panel, didn't understood how can that. this admin panel, admin panel don't want show , request database unauthenticated users. my laravel-routes route::get('/admin',function(){ return view('index'); }); route::get('/api/v1/employees/{id?}', 'employees@index'); route::get('/api/v1/users/{id?}', 'employees@users'); route::post('/api/v1/employees', 'employees@store'); route::post('/api/v1/employees/{id}', 'employees@update'); route::delete('/api/v1/employees/{id}', 'employees@destroy'); route::group(['prefix' => 'api'], function() { route::resource('authenticate', 'authenticatecontroller', ['only' => ['index']]); route::post('authenticate', 'authentic...
Read more