index ed3828b..e513284 100644 (file)
@@ -5,40 +5,58 @@

where `i` *subsists* in <code>s[&phi;]</code> if there are any `i'` that *extend* `i` in <code>s[&phi;]</code>.

------- wrong....
+       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.

-       In our framework, we just have to convert the operation <code>>>= \[[&psi;]]</code> into another operation <code>>>= \[[&psi;]] >>= neg</code>, where `neg` flips the truth-value of all the `bool dpm`s it operates on:
+               (* filter out which bool dpms in a set are true when receiving (r, h) as input *)
+               let truths set (r, h) =
+                       let test one_dpm =
+                               let (truth_value, _, _) = one_dpm (r, h)
+                               in truth_value
+                       in List.filter test set;;

-               type clause_op = bool dpm -> bool dpm set;;
-
-               let negate_op (phi : clause_op) : clause_op =
-                       let neg : clause_op = fun one_dpm ->
-                                               unit_set (fun (r, h) ->
-                                                       let (truth_value, r', h') = one_dpm (r, h)
-                                                       in (not truth_value, r', h'))
-                       in fun one_dpm -> bind_set (phi one_dpm) neg;;
-
-
-               let negate_op (phi : clause_op) : clause_op =
+               let negate_op (phi : clause) : clause =
fun one_dpm ->
-                               if blah
-                               then unit_set one_dpm
-                               else empty_set
-------
+                let new_dpm = fun (r, h) ->
+                                       (* if one_dpm isn't already false at (r, h),
+                                          we want to check its behavior when updated with phi
+                                          bind_set (unit_set one_dpm) phi === phi one_dpm; do you remember why? *)
+                                   let (truth_value, r', h') = one_dpm (r, h)
+                                       in let truth_value' = truth_value && (truths (phi one_dpm) (r, h) = [])
+                                       (* new_dpm must return a (bool, r, h) *)
+                    in (truth_value', r', h')
+                               in unit_set new_dpm;;
+

+       **Thanks to Simon Charlow** for catching a subtle error in previous versions of this function. Fixed 1 Dec.

*      Representing \[[and &phi; &psi;]] is simple:

-               let and_op (phi : clause_op) (psi : clause_op) : clause_op =
+               let and_op (phi : clause) (psi : clause) : clause =
fun one_dpm -> bind_set (phi one_dpm) psi;;
+               (* now u >>= and_op phi psi === u >>= phi >>= psi; do you remember why? *)
+
+
+*      Here are `or` and `if`:
+
+       (These probably still manifest the bug Simon spotted.)

-*      We define the other connectives in terms of `not` and `and`:
+               let or_op (phi : clause) (psi : clause) =
+            fun one_dpm -> unit_set (
+                fun (r, h) ->
+                                       let truth_value' = (
+                                               truths (phi one_dpm) (r, h) <> [] ||
+                                               truths (bind_set (negate_op phi one_dpm) psi) (r, h) <> []
+                                       ) in (truth_value', r, h))

-               let or_op (phi : clause_op) (psi : clause_op) =
-                       negate_op (and_op (negate_op phi) (negate_op psi))
+               let if_op (phi : clause) (psi : clause) : clause =
+            fun one_dpm -> unit_set (
+              fun (r, h) ->
+                                       let truth_value' = List.for_all (fun one_dpm ->
+                                                       let (truth_value, _, _) = one_dpm (r, h)
+                                                       in truth_value = false || truths (psi one_dpm) (r, h) <> []
+                                               ) (phi one_dpm)
+                    in (truth_value', r, h));;

-               let if_op (phi : clause_op) (psi : clause_op) =
-                       negate_op (and_op phi (negate_op psi));;

*      Now let's test everything we've developed:

let bind_set (u : 'a set) (f : 'a -> 'b set) : 'b set =
List.concat (List.map f u);;

-               type clause_op = bool dpm -> bool dpm set;;
+               type clause = bool dpm -> bool dpm set;;

+*      More:
+
+               (* this generalizes the getx function from hint 4 *)
let get (var : char) : entity dpm =
fun (r, h) ->
let obj = List.nth h (r var)
in (obj, r, h);;

-               let lift_predicate (f : entity -> bool) : entity dpm -> clause_op =
+               (* this generalizes the proposal for \[[Q]] from hint 4 *)
+               let lift_predicate (f : entity -> bool) : entity dpm -> clause =
fun entity_dpm ->
-                               let eliminator = fun (truth_value : bool) ->
+                               let eliminator = fun truth_value ->
if truth_value = false
then unit_dpm false
else bind_dpm entity_dpm (fun e -> unit_dpm (f e))
in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator);;

-               let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause_op =
+               (* doing the same thing for binary predicates *)
+               let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause =
fun entity1_dpm entity2_dpm ->
-                               let eliminator = fun (truth_value : bool) ->
+                               let eliminator = fun truth_value ->
if truth_value = false
then unit_dpm false
else bind_dpm entity1_dpm (fun e1 -> bind_dpm entity2_dpm (fun e2 -> unit_dpm (f e1 e2)))
if var = var_to_bind then new_index else r var
in (truth_value, r', h')

-               let exists var : clause_op = fun one_dpm ->
-                       List.map (fun d -> bind_dpm one_dpm (new_peg_and_assign var d)) domain
+               (* from hint 5 *)
+               let exists var : clause =
+                       let extend one_dpm (d : entity) =
+                               bind_dpm one_dpm (new_peg_and_assign var d)
+                       in fun one_dpm -> List.map (fun d -> extend one_dpm d) domain
+
+               (* include negate_op, and_op, or_op, and if_op as above *)

-               (* negate_op, and_op, or_op, and if_op as above *)
+*      More:

+               (* some handy utilities *)
let (>>=) = bind_set;;
+               let getx = get 'x';;
+               let gety = get 'y';;
let initial_set = [fun (r,h) -> (true,r,h)];;
-
let initial_r = fun var -> failwith ("no value for " ^ (Char.escaped var));;
let run dpm_set =
-                       let bool_set = List.map (fun one_dpm -> let (value, r, h) = one_dpm (initial_r, []) in value) dpm_set
-                       in List.exists (fun truth_value -> truth_value) bool_set;;
+                       (* do any of the dpms in the set return (true, _, _) when given (initial_r, []) as input? *)
+                       List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (initial_r, []) in truth_value) dpm_set <> [];;

-               let male obj = obj = Bob || obj = Ted;;
-               let wife_of x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Alice);;
-               let kisses x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Alice);;
-               let misses x y = (x,y) = (Bob, Carol) || (x,y) = (Ted, Carol);;
-               let getx = get 'x';;
-               let gety = get 'y';;
+               (* let's define some predicates *)
+               let male e = (e = Bob || e = Ted);;
+               let wife_of e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
+               let kisses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
+               let misses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Carol));;

(* "a man x has a wife y" *)
let antecedent = fun one_dpm -> exists 'x' one_dpm >>= lift_predicate male getx >>= exists 'y' >>= lift_predicate2 wife_of getx gety;;

(* "if a man x has a wife y, x kisses y" *)
-               run (initial_set >>= if_op antecedent lift_predicate2 kisses getx gety);;
+               run (initial_set >>= if_op antecedent (lift_predicate2 kisses getx gety));;
(* Bob has wife Carol, and kisses her; and Ted has wife Alice and kisses her; so this is true! *)

(* "if a man x has a wife y, x misses y" *)
-               run (initial_set >>= if_op antecedent lift_predicate2 misses getx gety);;
+               run (initial_set >>= if_op antecedent (lift_predicate2 misses getx gety));;
(* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)