* In def 3.1 on p. 14, GS&V define `s` updated with \[[not φ]] as: > { i ∈ s | i does not subsist in s[φ] } where `i` *subsists* in s[φ] if there are any `i'` that *extend* `i` in s[φ]. 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. (* 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;; let negate_op (phi : clause) : clause = fun one_dpm -> 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 set_bind (set_unit 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 set_unit new_dpm;; **Thanks to Simon Charlow** for catching a subtle error in previous versions of this function. Fixed 1 Dec. * Representing \[[and φ ψ]] is simple: let and_op (phi : clause) (psi : clause) : clause = fun one_dpm -> set_bind (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.) let or_op (phi : clause) (psi : clause) = fun one_dpm -> set_unit ( fun (r, h) -> let truth_value' = ( truths (phi one_dpm) (r, h) <> [] || truths (set_bind (negate_op phi one_dpm) psi) (r, h) <> [] ) in (truth_value', r, h)) let if_op (phi : clause) (psi : clause) : clause = fun one_dpm -> set_unit ( 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));; * Now let's test everything we've developed: type entity = Bob | Carol | Ted | Alice;; let domain = [Bob; Carol; Ted; Alice];; type assignment = char -> int;; type store = entity list;; type 'a dpm = assignment * store -> 'a * assignment * store;; let dpm_unit (x : 'a) : 'a dpm = fun (r, h) -> (x, r, h);; let dpm_bind (u: 'a dpm) (f : 'a -> 'b dpm) : 'b dpm = fun (r, h) -> let (a, r', h') = u (r, h) in let u' = f a in u' (r', h') type 'a set = 'a list;; let set_empty : 'a set = [];; let set_unit (x : 'a) : 'a set = [x];; let set_bind (u : 'a set) (f : 'a -> 'b set) : 'b set = List.concat (List.map f u);; 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);; (* 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 -> if truth_value = false then dpm_unit false else dpm_bind entity_dpm (fun e -> dpm_unit (f e)) in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator);; (* 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 -> if truth_value = false then dpm_unit false else dpm_bind entity1_dpm (fun e1 -> dpm_bind entity2_dpm (fun e2 -> dpm_unit (f e1 e2))) in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator);; let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm = fun truth_value -> fun (r, h) -> let new_index = List.length h in let h' = List.append h [d] in let r' = fun var -> if var = var_to_bind then new_index else r var in (truth_value, r', h') (* from hint 5 *) let exists var : clause = let extend one_dpm (d : entity) = dpm_bind 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 *) * More: (* some handy utilities *) let (>>=) = set_bind;; 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 = (* 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;; (* "if a man x has a wife y, x kisses y" *) 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));; (* Bob has wife Carol, and misses her; but Ted misses only Carol, not his wife Alice; so this is false! *)