2 * In def 3.1 on p. 14, GS&V define `s` updated with \[[not φ]] as:
4 > { i ∈ s | i does not subsist in s[φ] }
6 where `i` *subsists* in <code>s[φ]</code> if there are any `i'` that *extend* `i` in <code>s[φ]</code>.
8 Here's how to do that in our framework. Instead of asking whether a possibility subsists 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) =
13 let (truth_value, _, _) = one_dpm (r, h)
15 in List.filter test set;;
17 let negate_op (phi : clause) : clause =
19 let new_dpm = fun (r, h) ->
20 (* if one_dpm isn't already false at (r, h),
21 we want to check its behavior when updated with phi
22 bind_set (unit_set one_dpm) phi === phi one_dpm; do you remember why? *)
23 let (truth_value, _, _) = one_dpm (r, h)
24 in let truth_value' = truth_value && (truths (phi one_dpm) (r, h) = [])
25 (* new_dpm must return a (bool, r, h) *)
26 in (truth_value', r, h)
30 **Note: Simon pointed out a subtle error in this code, which we will look into fixing. At the moment, the subtle error is still there.**
32 * Representing \[[and φ ψ]] is simple:
34 let and_op (phi : clause) (psi : clause) : clause =
35 fun one_dpm -> bind_set (phi one_dpm) psi;;
36 (* now u >>= and_op phi psi === u >>= phi >>= psi; do you remember why? *)
39 * Here are `or` and `if`:
41 let or_op (phi : clause) (psi : clause) =
42 fun one_dpm -> unit_set (
45 truths (phi one_dpm) (r, h) <> [] ||
46 truths (bind_set (negate_op phi one_dpm) psi) (r, h) <> []
47 ) in (truth_value', r, h))
49 let if_op (phi : clause) (psi : clause) : clause =
50 fun one_dpm -> unit_set (
52 let truth_value' = List.for_all (fun one_dpm ->
53 let (truth_value, _, _) = one_dpm (r, h)
54 in truth_value = false || truths (psi one_dpm) (r, h) <> []
56 in (truth_value', r, h));;
59 * Now let's test everything we've developed:
61 type entity = Bob | Carol | Ted | Alice;;
62 let domain = [Bob; Carol; Ted; Alice];;
63 type assignment = char -> int;;
64 type store = entity list;;
65 type 'a dpm = assignment * store -> 'a * assignment * store;;
66 let unit_dpm (x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
67 let bind_dpm (u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
69 let (a, r', h') = u (r, h)
73 type 'a set = 'a list;;
74 let empty_set : 'a set = [];;
75 let unit_set (x : 'a) : 'a set = [x];;
76 let bind_set (u : 'a set) (f : 'a -> 'b set) : 'b set =
77 List.concat (List.map f u);;
79 type clause = bool dpm -> bool dpm set;;
83 (* this generalizes the getx function from hint 4 *)
84 let get (var : char) : entity dpm =
86 let obj = List.nth h (r var)
89 (* this generalizes the proposal for \[[Q]] from hint 4 *)
90 let lift_predicate (f : entity -> bool) : entity dpm -> clause =
92 let eliminator = fun truth_value ->
93 if truth_value = false
95 else bind_dpm entity_dpm (fun e -> unit_dpm (f e))
96 in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
98 (* doing the same thing for binary predicates *)
99 let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause =
100 fun entity1_dpm entity2_dpm ->
101 let eliminator = fun truth_value ->
102 if truth_value = false
104 else bind_dpm entity1_dpm (fun e1 -> bind_dpm entity2_dpm (fun e2 -> unit_dpm (f e1 e2)))
105 in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;
107 let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
110 let new_index = List.length h
111 in let h' = List.append h [d]
112 in let r' = fun var ->
113 if var = var_to_bind then new_index else r var
114 in (truth_value, r', h')
117 let exists var : clause =
118 let extend one_dpm (d : entity) =
119 bind_dpm one_dpm (new_peg_and_assign var d)
120 in fun one_dpm -> List.map (fun d -> extend one_dpm d) domain
122 (* include negate_op, and_op, or_op, and if_op as above *)
126 (* some handy utilities *)
127 let (>>=) = bind_set;;
130 let initial_set = [fun (r,h) -> (true,r,h)];;
131 let initial_r = fun var -> failwith ("no value for " ^ (Char.escaped var));;
133 (* do any of the dpms in the set return (true, _, _) when given (initial_r, []) as input? *)
134 List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (initial_r, []) in truth_value) dpm_set <> [];;
136 (* let's define some predicates *)
137 let male e = (e = Bob || e = Ted);;
138 let wife_of e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
139 let kisses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
140 let misses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Carol));;
142 (* "a man x has a wife y" *)
143 let antecedent = fun one_dpm -> exists 'x' one_dpm >>= lift_predicate male getx >>= exists 'y' >>= lift_predicate2 wife_of getx gety;;
145 (* "if a man x has a wife y, x kisses y" *)
146 run (initial_set >>= if_op antecedent (lift_predicate2 kisses getx gety));;
147 (* Bob has wife Carol, and kisses her; and Ted has wife Alice and kisses her; so this is true! *)
149 (* "if a man x has a wife y, x misses y" *)
150 run (initial_set >>= if_op antecedent (lift_predicate2 misses getx gety));;
151 (* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)