From 60fde0202775a36c5b20c370374649d2a90c6af8 Mon Sep 17 00:00:00 2001 From: Jim Pryor Date: Sat, 20 Nov 2010 09:09:45 -0500 Subject: [PATCH] assignment7 tweaks Signed-off-by: Jim Pryor --- assignment7.mdwn | 1 + hints/assignment_7_hint_2.mdwn | 4 +-- hints/assignment_7_hint_3.mdwn | 20 ++++++++----- hints/assignment_7_hint_4.mdwn | 2 +- hints/assignment_7_hint_5.mdwn | 38 ++++++++++++++---------- hints/assignment_7_hint_6.mdwn | 66 +++++++++++++++++++++++------------------- index.mdwn | 2 +- 7 files changed, 75 insertions(+), 58 deletions(-) diff --git a/assignment7.mdwn b/assignment7.mdwn index 0d5d45af..9f83b009 100644 --- a/assignment7.mdwn +++ b/assignment7.mdwn @@ -1,3 +1,4 @@ +**The hints for problem 2 were being actively developed until early Saturday morning. They're pretty stable now. Remember you have a grace period until Sunday Nov. 28 to complete this homework.** 1. Make sure that your operation-counting monad from [[assignment6]] is working. Modify it so that instead of counting operations, it keeps track of the last remainder of any integer division. You can help yourself to the functions: diff --git a/hints/assignment_7_hint_2.mdwn b/hints/assignment_7_hint_2.mdwn index 02f3b158..9c1079c3 100644 --- a/hints/assignment_7_hint_2.mdwn +++ b/hints/assignment_7_hint_2.mdwn @@ -20,9 +20,9 @@ Since `dpm`s are to be a monad, we have to define a unit and a bind. These are just modeled on the unit and bind for the state monad: - let unit_dpm (x : 'a) = fun (r, h) -> (x, r, h);; + let unit_dpm (value : 'a) : 'a dpm = fun (r, h) -> (value, r, h);; - let bind_dpm (u : 'a dpm) (f : 'a -> 'b dpm) = + let bind_dpm (u : 'a dpm) (f : 'a -> 'b dpm) : 'b dpm = fun (r, h) -> let (a, r', h') = u (r, h) in let u' = f a diff --git a/hints/assignment_7_hint_3.mdwn b/hints/assignment_7_hint_3.mdwn index bfac14e3..cbcc5a0b 100644 --- a/hints/assignment_7_hint_3.mdwn +++ b/hints/assignment_7_hint_3.mdwn @@ -9,8 +9,8 @@ type 'a set = 'a list;; let empty_set : 'a set = [];; - let unit_set (x: 'a) : 'a set = [x];; - let bind_set (u: 'a set) (f: 'a -> 'b set) = + let unit_set (value: 'a) : 'a set = [value];; + let bind_set (u: 'a set) (f: 'a -> 'b set) : 'b set = List.concat (List.map f u);; @@ -27,15 +27,19 @@ > \[[expression]] in possibility `(r, h, w)` - we'll just talk about \[[expression]] and let that be a monadic value, implemented in part by a function that takes `(r, h)` as an argument. + we'll just talk about \[[expression]] and let that be a monadic operation, implemented in part by a function that takes `(r, h)` as an argument. + + In particular, the meaning of sentential clauses will be an operation that we monadically bind to an existing `bool dpm set`. Here is its type: + + type clause = bool dpm -> bool dpm set;; * In def 2.7, GS&V talk about an operation that takes an existing set of discourse possibilities, and *extends* each member in the set by (i) allocating a new location in the store, (ii) putting some entity `d` from the domain in that location, and (iii) assigning variable `x` to that location in the store. It will be useful to have a shorthand way of referring to this operation: - let new_peg_and_assign (var_to_bind : char) (d : entity) = - (* we want to return a function that we can bind to a bool dpm *) - fun (truth_value : bool) -> - fun ((r, h) : assignment * store) -> + (* we want to return a function that we can bind to a bool dpm *) + let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm = + fun truth_value -> + fun (r, h) -> (* first we calculate an unused index *) let new_index = List.length h (* next we store d at h[new_index], which is at the very end of h *) @@ -45,7 +49,7 @@ It will be useful to have a shorthand way of referring to this operation: in let r' = fun var -> if var = var_to_bind then new_index else r var (* we pass through the same truth_value that we started with *) - in (truth_value, r', h') + in (truth_value, r', h');; * Is that enough? If not, here are some [more hints](/hints/assignment_7_hint_4). But try to get as far as you can on your own. diff --git a/hints/assignment_7_hint_4.mdwn b/hints/assignment_7_hint_4.mdwn index cef57737..c6a5995f 100644 --- a/hints/assignment_7_hint_4.mdwn +++ b/hints/assignment_7_hint_4.mdwn @@ -32,7 +32,7 @@ Well, we already know that \[[x]] will be a kind of computation that takes an assignment function `r` and store `h` as input. It will look up the entity that those two together associate with the variable `x`. So we can treat \[[x]] as an `entity dpm`. We don't worry here about sets of `dpm`s; we'll leave that to our predicates to interface with. We'll just make \[[x]] be a single `entity dpm`. So what we want is: - let getx = fun (r, h) -> + let getx : entity dpm = fun (r, h) -> let obj = List.nth h (r 'x') in (obj, r, h);; diff --git a/hints/assignment_7_hint_5.mdwn b/hints/assignment_7_hint_5.mdwn index a0ac32a3..120c1fdb 100644 --- a/hints/assignment_7_hint_5.mdwn +++ b/hints/assignment_7_hint_5.mdwn @@ -1,7 +1,7 @@ * How shall we handle \[[∃x]]? As we said, GS&V really tell us how to interpret \[[∃xPx]], but what they say about this breaks naturally into two pieces, such that we can represent the update of our starting set `u` with \[[∃xPx]] as: - 
u >>=set \[[∃x]] >>=set \[[Px]]
+	
u >>= \[[∃x]] >>= \[[Px]]
 	

 
 	What does \[[∃x]] need to be here? Here's what they say, on the top of p. 13:
@@ -15,17 +15,16 @@
 	Deferring the "property P" part, this corresponds to:
 
 	
u updated with \[[∃x]] ≡
-		let extend_one = fun (one_dpm : bool dpm) ->
+		let extend_one : clause = fun one_dpm ->
 			List.map (fun d -> bind_dpm one_dpm (new_peg_and_assign 'x' d)) domain
 		in bind_set u extend_one
 	

 
 	where `new_peg_and_assign` is the operation we defined in [hint 3](/hints/assignment_7_hint_3):
 
-		let new_peg_and_assign (var_to_bind : char) (d : entity) =
-			(* we want to return a function that we can bind to a bool dpm *)
-			fun (truth_value : bool) ->
-				fun ((r, h) : assignment * store) ->
+		let new_peg_and_assign (var_to_bind : char) (d : entity) : bool -> bool dpm =
+			fun truth_value ->
+				fun (r, h) ->
 					(* first we calculate an unused index *)
 					let new_index = List.length h
 					(* next we store d at h[new_index], which is at the very end of h *)
@@ -35,7 +34,7 @@
 					in let r' = fun var ->
 						if var = var_to_bind then new_index else r var
 					(* we pass through the same truth_value that we started with *)
-					in (truth_value, r', h')
+					in (truth_value, r', h');;
 	
 	What's going on in this representation of `u` updated with \[[∃x]]? For each `bool dpm` in `u`, we collect `dpm`s that are the result of passing through their `bool`, but extending their input `(r, h)` by allocating a new peg for entity `d`, for each `d` in our whole domain of entities, and binding the variable `x` to the index of that peg.
 
@@ -57,23 +56,31 @@
 		type assignment = char -> entity;;
 		type 'a reader = assignment -> 'a;;
 
-		let unit_reader (x : 'a) = fun r -> x;;
+		let unit_reader (value : 'a) : 'a reader = fun r -> value;;
 
-		let bind_reader (u : 'a reader) (f : 'a -> 'b reader) =
+		let bind_reader (u : 'a reader) (f : 'a -> 'b reader) : 'b reader =
 			fun r ->
 				let a = u r
 				in let u' = f a
 				in u' r;;
 
-		let getx = fun r -> r 'x';;
+	Here the type of a sentential clause is:
+
+		type clause = bool reader;;
+
+	Here are meanings for singular terms and predicates:
 
-		let lift (predicate : entity -> bool) =
+		let getx : entity reader = fun r -> r 'x';;
+
+		type lifted_unary = entity reader -> bool reader;;
+
+		let lift (predicate : entity -> bool) : lifted_unary =
 			fun entity_reader ->
 				fun r ->
 					let obj = entity_reader r
 					in unit_reader (predicate obj)
 
-	`lift predicate` converts a function of type `entity -> bool` into one of type `entity reader -> bool reader`. The meaning of \[[Qx]] would then be:
+	The meaning of \[[Qx]] would then be:
 
 	
\[[Q]] ≡ lift q
 	\[[x]] ≡ getx
@@ -85,10 +92,9 @@
 
 	Recall also how we defined \[[lambda x]], or as [we called it before](/reader_monad_for_variable_binding), \\[[who(x)]]:
 
-		let shift (var_to_bind : char) (clause : bool reader) =
-			(* we return a lifted predicate, that is a entity reader -> bool reader *)
+		let shift (var_to_bind : char) (clause : clause) : lifted_unary =
 			fun entity_reader ->
-				fun (r : assignment) ->
+				fun r ->
 					let new_value = entity_reader r
 					(* remember here we're implementing assignments as functions rather than as lists of pairs *)
 					in let r' = fun var -> if var = var_to_bind then new_value else r var
@@ -96,7 +102,7 @@
 
 	Now, how would we implement quantifiers in this setting? I'll assume we have a function `exists` of type `(entity -> bool) -> bool`. That is, it accepts a predicate as argument and returns `true` if any element in the domain satisfies that predicate. We could implement the reader-monad version of that like this:
 
-		fun (lifted_predicate : entity reader -> bool reader) ->
+		fun (lifted_predicate : lifted_unary) ->
 			fun r -> exists (fun (obj : entity) ->
 				lifted_predicate (unit_reader obj) r)
 			
diff --git a/hints/assignment_7_hint_6.mdwn b/hints/assignment_7_hint_6.mdwn
index 740eba2b..a371b21c 100644
--- a/hints/assignment_7_hint_6.mdwn
+++ b/hints/assignment_7_hint_6.mdwn
@@ -5,42 +5,43 @@
 
 	where `i` *subsists* in s[φ] if there are any `i'` that *extend* `i` in s[φ].
 
-	Here's how to do that in our framework:
+	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.
 
-		type clause_op = bool dpm -> bool dpm set;;
-		
 		(* filter out which bool dpms in a set are true when receiving (r, h) as input *)
-		let extensions set (r, h) = List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (r, h) in truth_value) set;;
-
-		let negate_op (phi : clause_op) : clause_op =
-			fun one_dpm -> unit_set (
-                fun (r, h) ->
-					let truth_value' = extensions (phi one_dpm) (r, h) = []
+		let truths set (r, h) = List.filter (fun one_dpm -> let (truth_value, _, _) = one_dpm (r, h) in truth_value) set;;
+
+		let negate_op (phi : clause) : clause =
+			fun one_dpm ->
+                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;;
 
 *	Here are `or` and `if`:
 
-		let or_op (phi : clause_op) (psi : clause_op) =
+		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' = extensions (phi one_dpm) (r, h) <> [] || extensions (bind_set (negate_op phi one_dpm) psi) (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_op) (psi : clause_op) : clause_op =
+		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 || extensions (psi one_dpm) (r, h) <> []
+							in truth_value = false || truths (psi one_dpm) (r, h) <> []
 						) (phi one_dpm)
                     in (truth_value', r, h));;
 
@@ -65,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
@@ -80,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
@@ -97,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;;
diff --git a/index.mdwn b/index.mdwn
index ac9ce98a..804dbe83 100644
--- a/index.mdwn
+++ b/index.mdwn
@@ -55,7 +55,7 @@ preloaded is available at [[assignment 3 evaluator]].
 
 (8 Nov) Lecture notes for [[Week8]].
 
-(15 Nov) Lecture notes are coming; [[Assignment7]] is here.
+(15 Nov) Lecture notes are coming; [[Assignment7]] is here. Everyone auditing in the class is encouraged to do this assignment, or at least work through the substantial "hints".
 
 
 [[Upcoming topics]]
-- 
2.11.0