2 *       In def 3.1 on p. 14, GS&V define `s` updated with \[[not &phi;]] as:
4         >       { i &isin; s | i does not subsist in s[&phi;] }
6         where `i` *subsists* in <code>s[&phi;]</code> if there are any `i'` that *extend* `i` in <code>s[&phi;]</code>.
8         Here's how to do that in our framework. Instead of a possibility subsisting in an updated set of possibilities, we ask what is returned by extensions of a `dpm` when they're given a particular (r, h) as input.
10                 (* filter out which bool dpms in a set are true when receiving (r, h) as input *)
11                 let truths set (r, h) = List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (r, h) in truth_value) set;;
13                 let negate_op (phi : clause) : clause =
14                         fun one_dpm ->
15                 let new_dpm = fun (r, h) ->
16                                         (* we want to check the behavior of one_dpm when updated with the operation phi *)
17                                         (* bind_set (unit_set one_dpm) phi === phi one_dpm; do you remember why? *)
18                                         let truth_value' = truths (phi one_dpm) (r, h) = []
19                                         (* we return a (bool, r, h) so as to constitute a dpm *)
20                     in (truth_value', r, h)
21                                 in unit_set new_dpm
24 *       Representing \[[and &phi; &psi;]] is simple:
26                 let and_op (phi : clause) (psi : clause) : clause =
27                         fun one_dpm -> bind_set (phi one_dpm) psi;;
29 *       Here are `or` and `if`:
31                 let or_op (phi : clause) (psi : clause) =
32                         (* NOT: negate_op (and_op (negate_op phi) (negate_op psi)) *)
33             fun one_dpm -> unit_set (
34                 fun (r, h) ->
35                                         in let truth_value' = truths (phi one_dpm) (r, h) <> [] || truths (bind_set (negate_op phi one_dpm) psi) (r, h) <> []
36                     in (truth_value', r, h))
38                 let if_op (phi : clause) (psi : clause) : clause =
39                         (* NOT: negate_op (and_op phi (negate_op psi)) *)
40             fun one_dpm -> unit_set (
41               fun (r, h) ->
42                                         in let truth_value' = List.for_all (fun one_dpm ->
43                                                         let (truth_value, _, _) = one_dpm (r, h)
44                                                         in truth_value = false || truths (psi one_dpm) (r, h) <> []
45                                                 ) (phi one_dpm)
46                     in (truth_value', r, h));;
49 *       Now let's test everything we've developed:
51                 type entity = Bob | Carol | Ted | Alice;;
52                 let domain = [Bob; Carol; Ted; Alice];;
53                 type assignment = char -> int;;
54                 type store = entity list;;
55                 type 'a dpm = assignment * store -> 'a * assignment * store;;
56                 let unit_dpm (x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
57                 let bind_dpm (u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
58                         fun (r, h) ->
59                                 let (a, r', h') = u (r, h)
60                                 in let u' = f a
61                                 in u' (r', h')
63                 type 'a set = 'a list;;
64                 let empty_set : 'a set = [];;
65                 let unit_set (x : 'a) : 'a set = [x];;
66                 let bind_set (u : 'a set) (f : 'a -> 'b set) : 'b set =
67                         List.concat (List.map f u);;
69                 type clause = bool dpm -> bool dpm set;;
71                 (* this generalizes the getx function from hint 4 *)
72                 let get (var : char) : entity dpm =
73                         fun (r, h) ->
74                                 let obj = List.nth h (r var)
75                                 in (obj, r, h);;
77                 (* this generalizes the proposal for \[[Q]] from hint 4 *)
78                 let lift_predicate (f : entity -> bool) : entity dpm -> clause =
79                         fun entity_dpm ->
80                                 let eliminator = fun (truth_value : bool) ->
81                                         if truth_value = false
82                                         then unit_dpm false
83                                         else bind_dpm entity_dpm (fun e -> unit_dpm (f e))
84                                 in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
86                 (* doing the same thing for binary predicates *)
87                 let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause =
88                         fun entity1_dpm entity2_dpm ->
89                                 let eliminator = fun (truth_value : bool) ->
90                                         if truth_value = false
91                                         then unit_dpm false
92                                         else bind_dpm entity1_dpm (fun e1 -> bind_dpm entity2_dpm (fun e2 -> unit_dpm (f e1 e2)))
93                                 in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
95                 let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
96                   fun truth_value ->
97                           fun (r, h) ->
98                                 let new_index = List.length h
99                                 in let h' = List.append h [d]
100                                 in let r' = fun var ->
101                                   if var = var_to_bind then new_index else r var
102                                 in (truth_value, r', h')
104                 (* from hint 5 *)
105                 let exists var : clause = fun one_dpm ->
106                         List.map (fun d -> bind_dpm one_dpm (new_peg_and_assign var d)) domain
108                 (* include negate_op, and_op, or_op, and if_op as above *)
110                 (* some handy utilities *)
111                 let (>>=) = bind_set;;
112                 let getx = get 'x';;
113                 let gety = get 'y';;
114                 let initial_set = [fun (r,h) -> (true,r,h)];;
115                 let initial_r = fun var -> failwith ("no value for " ^ (Char.escaped var));;
116                 let run dpm_set =
117                         (* do any of the dpms in the set return (true, _, _) when given (initial_r, []) as input? *)
118                         List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (initial_r, []) in truth_value) dpm_set <> [];;
120                 (* let's define some predicates *)
121                 let male e = (e = Bob || e = Ted);;
122                 let wife_of e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
123                 let kisses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
124                 let misses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Carol));;
126                 (* "a man x has a wife y" *)
127                 let antecedent = fun one_dpm -> exists 'x' one_dpm >>= lift_predicate male getx >>= exists 'y' >>= lift_predicate2 wife_of getx gety;;
129                 (* "if a man x has a wife y, x kisses y" *)
130                 run (initial_set >>= if_op antecedent (lift_predicate2 kisses getx gety));;
131                 (* Bob has wife Carol, and kisses her; and Ted has wife Alice and kisses her; so this is true! *)
133                 (* "if a man x has a wife y, x misses y" *)
134                 run (initial_set >>= if_op antecedent (lift_predicate2 misses getx gety));;
135                 (* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)