https://github.com/EasyCrypt/easycrypt
Tip revision: 0e369749080b67c4ca4b0693da61afa7d69c118d authored by Pierre-Yves Strub on 15 October 2019, 08:38:08 UTC
Merge branch '1.0' into deploy-derandomize
Merge branch '1.0' into deploy-derandomize
Tip revision: 0e36974
FoldProc.eca
(* --------------------------------------------------------------------
* Copyright (c) - 2012--2016 - IMDEA Software Institute
* Copyright (c) - 2012--2018 - Inria
* Copyright (c) - 2012--2018 - Ecole Polytechnique
*
* Distributed under the terms of the CeCILL-B-V1 license
* -------------------------------------------------------------------- *)
require import Core List.
require (*--*) IterProc.
type in_t, state_t.
module type Orcl = {
proc f (s : state_t, x : in_t) : state_t
}.
module Fold (O:Orcl) = {
proc fold(s : state_t, l : in_t list) = {
while (l <> []) {
s <@ O.f(s,head witness l);
l <- drop 1 l;
}
return s;
}
proc fold_12 (s : state_t, t1 : in_t, t2 : in_t) = {
s <@ O.f(s,t1);
s <@ O.f(s,t2);
return s;
}
proc fold_21 (s : state_t, t1 : in_t, t2 : in_t) = {
s <@ O.f(s,t2);
s <@ O.f(s,t1);
return s;
}
}.
lemma fold_ll (O<:Orcl): islossless O.f => islossless Fold(O).fold.
proof.
move=> O_ll; proc; inline Fold(O).fold.
while true (size l); auto=> /=.
+ call O_ll; skip=> /= ? [#] Hl <-.
smt w=(size_eq0 size_ge0 size_drop).
smt w=(size_eq0 size_ge0).
qed.
section.
declare module O:Orcl.
axiom fold_swap12:
equiv [Fold(O).fold_12 ~ Fold(O).fold_21 : ={t1,t2,glob O,s} ==> ={glob O,res}].
local clone import IterProc as IP with
type t <- in_t.
local module O' = {
var s : state_t
proc f (x : in_t): unit = {
s <@ O.f(s,x);
}
}.
local equiv Fold_Iter: Fold(O).fold ~ Iter(O').iter:
={glob O,l} /\ s{1} = O'.s{2} ==> ={glob O} /\ res{1} = O'.s{2}.
proof.
proc; while (={glob O,l} /\ s{1} = O'.s{2}); last by auto.
by inline O'.f; wp; call (_: true); auto.
qed.
local equiv iter_swap1 :
Iter(O').iter_12 ~ Iter(O').iter_21 :
={glob O', t1, t2} ==> ={glob O'}.
proof.
transitivity Fold(O).fold_12
(={glob O,t1,t2} /\ s{2} = O'.s{1} ==> ={glob O} /\ res{2} = O'.s{1})
(={glob O,t1,t2} /\ s{1} = O'.s{2} ==> ={glob O} /\ res{1} = O'.s{2})=> //.
+ by move=> /> &1 &2 <- <-; exists ((glob O){2}) (O'.s{2},t1{1},t2{1}).
+ by proc;inline *;sim.
transitivity Fold(O).fold_21
(={glob O,s,t1,t2} ==> ={glob O, res})
(={glob O,t1,t2} /\ s{1} = O'.s{2} ==> ={glob O} /\ res{1} = O'.s{2})=> [/#|//||].
+ by conseq fold_swap12.
by proc;inline *;sim.
qed.
equiv fold_perm : Fold(O).fold ~ Fold(O).fold :
={glob O,s} /\ perm_eq l{1} l{2} ==> ={glob O,res}.
proof.
transitivity Iter(O').iter
(={glob O,l} /\ s{1} = O'.s{2} ==> ={glob O} /\ res{1} = O'.s{2})
(={glob O} /\ O'.s{1} = s{2} /\ perm_eq l{1} l{2} ==>
={glob O} /\ O'.s{1} = res{2})=> [/#|//||].
+ by conseq Fold_Iter.
transitivity Iter(O').iter
(={glob O'} /\ perm_eq l{1} l{2} ==> ={glob O'})
(={glob O,l} /\ O'.s{1} = s{2} ==> ={glob O} /\ O'.s{1} = res{2})=> [/#|//||].
+ by conseq (iter_perm O' _)=>//=; conseq iter_swap1.
by symmetry; conseq Fold_Iter.
qed.
end section.