hints/assignment_7_hint_6.mdwn

   1
   2 *       In def 3.1 on p. 14, GS&V define `s` updated with \[[not &phi;]] as:
   3
   4         >       { i &isin; s | i does not subsist in s[&phi;] }
   5
   6         where `i` *subsists* in <code>s[&phi;]</code> if there are any `i'` that *extend* `i` in <code>s[&phi;]</code>.
   7
   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.
   9
  10                 (* filter out which bool dpms in a set are true when receiving (r, h) as input *)
  11                 let truths set (r, h) =
  12                         let test one_dpm =
  13                                 let (truth_value, _, _) = one_dpm (r, h)
  14                                 in truth_value
  15                         in List.filter test set;;
  16
  17                 let negate_op (phi : clause) : clause =
  18                         fun one_dpm ->
  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                                            set_bind (set_unit one_dpm) phi === phi one_dpm; do you remember why? *)
  23                                     let (truth_value, r', h') = 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')
  27                                 in set_unit new_dpm;;
  28
  29
  30         **Thanks to Simon Charlow** for catching a subtle error in previous versions of this function. Fixed 1 Dec.
  31
  32 *       Representing \[[and &phi; &psi;]] is simple:
  33
  34                 let and_op (phi : clause) (psi : clause) : clause =
  35                         fun one_dpm -> set_bind (phi one_dpm) psi;;
  36                 (* now u >>= and_op phi psi === u >>= phi >>= psi; do you remember why? *)
  37
  38
  39 *       Here are `or` and `if`:
  40
  41         (These probably still manifest the bug Simon spotted.)
  42
  43                 let or_op (phi : clause) (psi : clause) =
  44             fun one_dpm -> set_unit (
  45                 fun (r, h) ->
  46                                         let truth_value' = (
  47                                                 truths (phi one_dpm) (r, h) <> [] ||
  48                                                 truths (set_bind (negate_op phi one_dpm) psi) (r, h) <> []
  49                                         ) in (truth_value', r, h))
  50
  51                 let if_op (phi : clause) (psi : clause) : clause =
  52             fun one_dpm -> set_unit (
  53               fun (r, h) ->
  54                                         let truth_value' = List.for_all (fun one_dpm ->
  55                                                         let (truth_value, _, _) = one_dpm (r, h)
  56                                                         in truth_value = false || truths (psi one_dpm) (r, h) <> []
  57                                                 ) (phi one_dpm)
  58                     in (truth_value', r, h));;
  59
  60
  61 *       Now let's test everything we've developed:
  62
  63                 type entity = Bob | Carol | Ted | Alice;;
  64                 let domain = [Bob; Carol; Ted; Alice];;
  65                 type assignment = char -> int;;
  66                 type store = entity list;;
  67                 type 'a dpm = assignment * store -> 'a * assignment * store;;
  68                 let dpm_unit (x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);;
  69                 let dpm_bind (u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm =
  70                         fun (r, h) ->
  71                                 let (a, r', h') = u (r, h)
  72                                 in let u' = f a
  73                                 in u' (r', h')
  74
  75                 type 'a set = 'a list;;
  76                 let set_empty : 'a set = [];;
  77                 let set_unit (x : 'a) : 'a set = [x];;
  78                 let set_bind (u : 'a set) (f : 'a -> 'b set) : 'b set =
  79                         List.concat (List.map f u);;
  80
  81                 type clause = bool dpm -> bool dpm set;;
  82
  83 *       More:
  84
  85                 (* this generalizes the getx function from hint 4 *)
  86                 let get (var : char) : entity dpm =
  87                         fun (r, h) ->
  88                                 let obj = List.nth h (r var)
  89                                 in (obj, r, h);;
  90
  91                 (* this generalizes the proposal for \[[Q]] from hint 4 *)
  92                 let lift_predicate (f : entity -> bool) : entity dpm -> clause =
  93                         fun entity_dpm ->
  94                                 let eliminator = fun truth_value ->
  95                                         if truth_value = false
  96                                         then dpm_unit false
  97                                         else dpm_bind entity_dpm (fun e -> dpm_unit (f e))
  98                                 in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator);;
  99
 100                 (* doing the same thing for binary predicates *)
 101                 let lift_predicate2 (f : entity -> entity -> bool) : entity dpm -> entity dpm -> clause =
 102                         fun entity1_dpm entity2_dpm ->
 103                                 let eliminator = fun truth_value ->
 104                                         if truth_value = false
 105                                         then dpm_unit false
 106                                         else dpm_bind entity1_dpm (fun e1 -> dpm_bind entity2_dpm (fun e2 -> dpm_unit (f e1 e2)))
 107                                 in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator);;
 108
 109                 let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
 110                   fun truth_value ->
 111                           fun (r, h) ->
 112                                 let new_index = List.length h
 113                                 in let h' = List.append h [d]
 114                                 in let r' = fun var ->
 115                                   if var = var_to_bind then new_index else r var
 116                                 in (truth_value, r', h')
 117
 118                 (* from hint 5 *)
 119                 let exists var : clause =
 120                         let extend one_dpm (d : entity) =
 121                                 dpm_bind one_dpm (new_peg_and_assign var d)
 122                         in fun one_dpm -> List.map (fun d -> extend one_dpm d) domain
 123
 124                 (* include negate_op, and_op, or_op, and if_op as above *)
 125
 126 *       More:
 127
 128                 (* some handy utilities *)
 129                 let (>>=) = set_bind;;
 130                 let getx = get 'x';;
 131                 let gety = get 'y';;
 132                 let initial_set = [fun (r,h) -> (true,r,h)];;
 133                 let initial_r = fun var -> failwith ("no value for " ^ (Char.escaped var));;
 134                 let run dpm_set =
 135                         (* do any of the dpms in the set return (true, _, _) when given (initial_r, []) as input? *)
 136                         List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (initial_r, []) in truth_value) dpm_set <> [];;
 137
 138                 (* let's define some predicates *)
 139                 let male e = (e = Bob || e = Ted);;
 140                 let wife_of e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
 141                 let kisses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Alice));;
 142                 let misses e1 e2 = ((e1,e2) = (Bob, Carol) || (e1,e2) = (Ted, Carol));;
 143
 144                 (* "a man x has a wife y" *)
 145                 let antecedent = fun one_dpm -> exists 'x' one_dpm >>= lift_predicate male getx >>= exists 'y' >>= lift_predicate2 wife_of getx gety;;
 146
 147                 (* "if a man x has a wife y, x kisses y" *)
 148                 run (initial_set >>= if_op antecedent (lift_predicate2 kisses getx gety));;
 149                 (* Bob has wife Carol, and kisses her; and Ted has wife Alice and kisses her; so this is true! *)
 150
 151                 (* "if a man x has a wife y, x misses y" *)
 152                 run (initial_set >>= if_op antecedent (lift_predicate2 misses getx gety));;
 153                 (* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)
 154