X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=hints%2Fassignment_7_hint_6.mdwn;h=a371b21c71280a29614f516895747a76fc4f0bba;hp=0859706b47b47beb5360ec6f9acdef0799aa6130;hb=60fde0202775a36c5b20c370374649d2a90c6af8;hpb=85784b8965db9b0daf0c03f043bc68bd9b41a18c
diff --git a/hints/assignment_7_hint_6.mdwn b/hints/assignment_7_hint_6.mdwn
index 0859706b..a371b21c 100644
--- a/hints/assignment_7_hint_6.mdwn
+++ b/hints/assignment_7_hint_6.mdwn
@@ -5,40 +5,46 @@
where `i` *subsists* in s[φ] if there are any `i'` that *extend* `i` in s[φ].
------- wrong....
+ 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.
- In our framework, we just have to convert the operation >>= \[[ψ]] into another operation >>= \[[ψ]] >>= neg, 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) = List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (r, h) in truth_value) 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) ->
+ (* we want to check the behavior of one_dpm when updated with the operation phi *)
+ (* bind_set (unit_set one_dpm) phi === phi one_dpm; do you remember why? *)
+ let truth_value' = truths (phi one_dpm) (r, h) = []
+ (* we return a (bool, r, h) so as to constitute a dpm *)
+ in (truth_value', r, h)
+ in unit_set new_dpm
* Representing \[[and φ ψ]] 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;;
-* We define the other connectives in terms of `not` and `and`:
+* Here are `or` and `if`:
- let or_op (phi : clause_op) (psi : clause_op) =
- negate_op (and_op (negate_op phi) (negate_op psi))
+ let or_op (phi : clause) (psi : clause) =
+ (* NOT: negate_op (and_op (negate_op phi) (negate_op psi)) *)
+ fun one_dpm -> unit_set (
+ fun (r, h) ->
+ in 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 if_op (phi : clause) (psi : clause) : clause =
+ (* NOT: negate_op (and_op phi (negate_op psi)) *)
+ fun one_dpm -> unit_set (
+ fun (r, h) ->
+ in 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:
@@ -60,14 +66,16 @@
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;;
+ (* 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) ->
if truth_value = false
@@ -75,7 +83,8 @@
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) ->
if truth_value = false
@@ -92,25 +101,27 @@
if var = var_to_bind then new_index else r var
in (truth_value, r', h')
- let exists var : clause_op = fun one_dpm ->
+ (* from hint 5 *)
+ let exists var : clause = fun one_dpm ->
List.map (fun d -> bind_dpm one_dpm (new_peg_and_assign var d)) domain
- (* negate_op, and_op, or_op, and if_op as above *)
+ (* include negate_op, and_op, or_op, and if_op as above *)
+ (* 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;;
-
- 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';;
+ (* 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'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;;