CCGRID26_code/dlls_simple.ath at main · FLAGlab/CCGRID26_code · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
load "lst-in"
load "lst-toset"
load "dlist.ath"
load "function.ath"
open Function
module DL_L_S {
    define [f]     := [?f:(fn 'S N)]
    define [lsts]  := [?lsts:(Lst 'S)]
    define [s htv v head]          := [?s:'S ?htv:'S ?v:'S ?head:(Lst 'S)]
    define [n rv rv0 bucket]  := [?n:N ?rv:N ?rv0:N ?bucket:N]
    define [dlls tail_dlls o_dlls]  :=
           [?dlls:(DLst (Lst 'S)) ?tail_dlls:(DLst (Lst 'S)) ?o_dlls:(DLst (Lst 'S))]
    define [l l0 lh htl htl0 ll tail_l tail_l0] :=
           [?l:Location ?l0:Location ?lh:Location ?htl:Location ?htl0:Location
            ?ll:(Lst Location) ?tail_l:(Lst Location) ?tail_l0:(Lst Location)]

    ### initDPrList
    ### Purpose:
    ###     Initialize a distributed list of buckets, one bucket per input location. Each
    ###     bucket is initialize as an empty list. You might notice that f is never use,
    ###     the reason being that is the way to have information about 'S in the parameter
    ###     input list.
    ###
    ### Parameters:
    ###     f::(fn S N)         : A hash function
    ###     htl0::Location      : default tail location (for dempty)
    ###     lsts:(Lst Location) : list of locations to initialize
    ###
    ### Returns:
    ###     A (DLst (Lst S)) where every location in lsts
    ###     corresponds to an empty bucket (list).
    declare initDPrList: (S) [(fn S N) Location (Lst Location)] -> (DLst (Lst S))
    assert  initDPrList_axioms :=
         (fun [
            (initDPrList f htl0 empty) = (dempty htl0)
            (initDPrList f htl0 (lst l tail_l)) = (dlst l empty (initDPrList f htl0 tail_l))
        ])

    # TODO: need a proof for this.. should be easy
    assert initDPrList_characterization :=
    (forall f htl lsts . (
                          ((initDPrList f htl lsts) = (dempty htl))
                        | (exists l tail_l . (initDPrList f htl lsts) = (dlst l empty (initDPrList f htl tail_l) ))))

    ### in
    ### Purpose:
    ###     Replication aware membership predicate for distributed bucket lists.
    ###     Determines whether a value `v` is stored in the bucket indexed by `bucket`,
    ###     or in any of the next `rv` replica buckets, with a wrap around semantics.
    ###
    ### Parameters:
    ###     bucket::N              : primary bucket index to inspect
    ###     rv::N                  : replication factor, number of successor buckets to check
    ###     dlls::(DLst (Lst S))   : current suffix of the distributed list to traverse
    ###     o_dlls::(DLst (Lst S)) : original distributed list (used when wrap-around is required)
    ###     v::S                   : value to search for
    ###
    ### Returns:
    ###     Boolean indicating whether `v` appears in the bucket at position `bucket` or
    ###      within the next `rv` buckets modulo the length of the list.
    declare in: (S) [N N (DLst (Lst S)) (DLst (Lst S)) S] -> Boolean
    assert in_axioms := (fun [
        (in bucket rv dlls (dempty htl) htv) <==> false
        (in zero zero (dempty htl) o_dlls htv) <==> false
        (in zero zero (dlst lh lsts tail_dlls) o_dlls htv) <==> (Lst.in htv lsts)
        (in zero (S rv) (dlst lh lsts tail_dlls) o_dlls htv) <==>
            [
                true
                    when (Lst.in htv lsts)
                (in zero rv tail_dlls o_dlls htv)
                    when (~ Lst.in htv lsts)
            ]
        (in zero (S rv) (dempty htl) o_dlls htv) <==> (in zero (S rv) o_dlls o_dlls htv)
        (in (S bucket) rv dlls o_dlls htv) <==> (in bucket rv dlls o_dlls htv)
    ])

    define in_init_false_lsts :=
        (forall  lsts f v htl .
            (~ in zero zero (initDPrList f htl lsts) (initDPrList f htl lsts) v ))
    by-induction in_init_false_lsts {
        empty =>
        pick-any f v htl
            let {
                predicate := (in zero zero (initDPrList f htl empty) (initDPrList f htl empty) v);
                init_empty_case := (!chain [ (initDPrList f htl empty)
                                            = (dempty htl) [initDPrList_axioms] ]) ;
                in_false :=
                    (!chain [
                        predicate
                        ==> (in zero zero (dempty htl) (initDPrList f htl empty) v)    [init_empty_case]
                        ==> false                                                      [in_axioms]
                    ])
            }
            (!by-contradiction (~ predicate) in_false)
        | (lst l0 tail_l) =>
        # TODO: In this case I do not use the IH... this means that this proof can be done
        # without by-induction?... I think that no, rather it should be done with
        # datatype-cases
        pick-any f v htl
        let {
            predicate   := (in zero zero (initDPrList f htl (lst l0 tail_l)) (initDPrList f htl (lst l0 tail_l)) v);
            init_lsts   := (!chain [ (initDPrList f htl (lst l0 tail_l))
                                    = (dlst l0 empty (initDPrList f htl tail_l)) [initDPrList_axioms] ]);
            in_false    := (!chain [
                   predicate
                ==> (in zero zero (dlst l0 empty (initDPrList f htl tail_l)) (dlst l0 empty (initDPrList f htl tail_l)) v) [init_lsts]
                ==> (Lst.in v empty)                   [in_axioms]
                ==> false                              [Lst.in_axioms]
            ])}
        (!by-contradiction (~predicate) in_false)
    }

    define in_init_false_rv :=
        (forall rv lsts f v htl .
            (~ in zero rv (initDPrList f htl lsts) (initDPrList f htl lsts) v ))
    by-induction in_init_false_rv {
        zero =>
        pick-any lsts f v htl
            (!chain<- [
                (~ in zero zero (initDPrList f htl lsts) (initDPrList f htl lsts) v )
                <== true [in_init_false_lsts]
            ])
        | (S rv0) =>
        let {
        IH := (forall lsts f v htl .  (~ in zero rv0 (initDPrList f htl lsts) (initDPrList f htl lsts) v ))
        }
        pick-any lsts f:(fn 'S N) v:'S htl
        (!cases (!uspec* initDPrList_characterization [f htl lsts])
            assume  empty_dlst := ((initDPrList f htl lsts) = (dempty htl))
            (!by-contradiction
                (~ in zero (S rv0) (initDPrList f htl lsts) (initDPrList f htl lsts) v)
                (!chain [
                        (in zero (S rv0) (initDPrList f htl lsts) (initDPrList f htl lsts) v)
                    ==> (in zero (S rv0) (initDPrList f htl lsts) (dempty htl) v) [empty_dlst]
                    ==> false                                                     [in_axioms]
                ]))
            assume no_empty_dlst :=
                (exists l tail_l .
                    (initDPrList f htl lsts) = (dlst l empty (initDPrList f htl tail_l)))
            pick-witnesses l0 tail_l0 for no_empty_dlst init_characterization
            let {
                ih := (!uspec* IH [tail_l0 f v htl]);
                _ := (write ih)}
            (!by-contradiction
                (~ in zero (S rv0) (initDPrList f htl lsts) (initDPrList f htl lsts) v)
                (!chain [
                        (in zero (S rv0) (initDPrList f htl lsts) (initDPrList f htl lsts) v)
                    ==> (in zero (S rv0) (dlst l0 empty (initDPrList f htl tail_l0)) (initDPrList f htl lsts) v) [init_characterization]
                    # This step is force... but the justification should be in_axioms,
                    # just do not know at first glance how to make it work, this step does
                    # not worry me
                    ==> (in zero rv0 (initDPrList f htl tail_l0) (initDPrList f htl tail_l0) v) [force]
                    ==> ((~in zero rv0 (initDPrList f htl tail_l0) (initDPrList f htl tail_l0) v) and (in zero rv0 (initDPrList f htl tail_l0) (initDPrList f htl tail_l0) v)) [augment]

                    # This is the step that really worries me, in theory the justification
                    # should be ih (Line 141) but that is not quiet the ih for this
                    # induction. Thus, is there a way to make this work? or what should I do?
                    ==> false                                                                [prop-taut]
                ])
            )
        )
    }

}