X-Git-Url: http://lambda.jimpryor.net/git/gitweb.cgi?p=lambda.git;a=blobdiff_plain;f=hints%2Fassignment_7_hint_4.mdwn;h=6b33b7a544199181d47a92a48b2ea3b06dbc1716;hp=c6a5995fcc6fcb17943ffe90e555eeb8a6b0c029;hb=eb8ac48a126c26a8195d19dfc0e1f60009198746;hpb=60fde0202775a36c5b20c370374649d2a90c6af8 diff --git a/hints/assignment_7_hint_4.mdwn b/hints/assignment_7_hint_4.mdwn index c6a5995f..6b33b7a5 100644 --- a/hints/assignment_7_hint_4.mdwn +++ b/hints/assignment_7_hint_4.mdwn @@ -1,22 +1,23 @@ -* At the top of p. 13 (this is in between defs 2.8 and 2.9), GS&V give two examples, one for \[[∃xPx]] and the other for \[[Qx]]. In fact it will be most natural to break \[[∃xPx]] into two pieces, \[[∃x]] and \[[Px]]. But first we need to get clear on expressions like \[[Qx]]. +* At the top of p. 13, GS&V give two examples, one for \[[∃xPx]] and the other for \[[Qx]]. For our purposes, it will be most natural to break \[[∃xPx]] into two pieces, \[[∃x]] and \[[Px]]. But first we need to get clear on expressions like \[[Qx]] and \[[Px]]. * GS&V say that the effect of updating an information state `s` with the meaning of "Qx" should be to eliminate possibilities in which the entity associated with the peg associated with the variable `x` does not have the property Q. In other words, if we let `q` be the function from entities to `bool`s that gives the extension of Q, then `s` updated with \[[Qx]] should be `s` filtered by the function `fun (r, h) -> let obj = List.nth h (r 'x') in q obj`. When `... q obj` evaluates to `true`, that `(r, h)` pair is retained, else it is discarded. - OK, we face two questions then. First, how do we carry this over to our present framework, where we're working with sets of `dpm`s instead of sets of discourse possibilities? And second, how do we decompose the behavior here attributed to \[[Qx]] into some meaning for "Q" and a different meaning for "x"? + OK, so we face two questions. First, how do we carry this over to our present framework, where we're working with sets of `dpm`s instead of sets of discourse possibilities? And second, how do we decompose the behavior here attributed to \[[Qx]] into some meaning for "Q" and a different meaning for "x"? * Answering the first question: we assume we've got some `bool dpm set` to start with. I won't call this `s` because that's what GS&V use for sets of discourse possibilities, and we don't want to confuse discourse possibilities with `dpm`s. Instead I'll call it `u`. Now what we want to do with `u` is to map each `dpm` it gives us to one that results in `(true, r, h)` only when the entity that `r` and `h` associate with variable `x` has the property Q. As above, I'll assume Q's extension is given by a function `q` from entities to `bool`s. Then what we want is something like this: - let eliminate_non_Qxs = (fun truth_value -> - fun (r, h) -> - let truth_value' = - if truth_value - then let obj = List.nth h (r 'x') in q obj - else false - in (truth_value', r, h)) - in bind_set u (fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs)) + let eliminator : bool -> bool dpm = + fun truth_value -> + fun (r, h) -> + let truth_value' = + if truth_value + then let obj = List.nth h (r 'x') in q obj + else false + in (truth_value', r, h) + in bind_set u (fun one_dpm -> unit_set (bind_dpm one_dpm eliminator)) The first seven lines here just perfom the operation we described: return a `bool dpm` computation that only yields `true` when its input `(r, h)` associates variable `x` with the right sort of entity. The last line performs the `bind_set` operation. This works by taking each `dpm` in the set and returning a `unit_set` of a filtered `dpm`. The definition of `bind_set` takes care of collecting together all of the `unit_set`s that result for each different set element we started with. @@ -30,7 +31,7 @@ * Now our second question: how do we decompose the behavior here attributed to \[[Qx]] into some meaning for "Q" and a different meaning for "x"? - 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: + 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 `dpm set`s; we'll leave them to our predicates to interface with. We'll just make \[[x]] be a single `entity dpm`. So what we want is: let getx : entity dpm = fun (r, h) -> let obj = List.nth h (r 'x') @@ -44,16 +45,17 @@ fun entity_dpm -> unit_set (bind_dpm entity_dpm (fun e -> unit_dpm (q e))) - Finally, we realize that we're going to have a set of `bool dpm`s to start with, and we need to compose \[[Qx]] with them. We don't want any of the monadic values in the set that wrap `false` to become `true`; instead, we want to apply a filter that checks whether values that formerly wrapped `true` should still continue to do so. + Finally, we realize that we're going to have a set of `bool dpm`s to start with, and we need to monadically bind \[[Qx]] to them. We don't want any of the monadic values in the set that wrap `false` to become `true`; instead, we want to apply a filter that checks whether values that formerly wrapped `true` should still continue to do so. This could be handled like this: fun entity_dpm -> - let eliminate_non_Qxs = fun truth_value -> - if truth_value = false - then unit_dpm false - else bind_dpm entity_dpm (fun e -> unit_dpm (q e)) - in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs) + let eliminator : bool -> bool dpm = + fun truth_value -> + if truth_value = false + then unit_dpm false + else bind_dpm entity_dpm (fun e -> unit_dpm (q e)) + in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator) Applied to an `entity_dpm`, that yields a function that we can bind to a `bool dpm set` and that will transform the doubly-wrapped `bool` into a new `bool dpm set`. @@ -63,40 +65,43 @@ let obj = List.nth h (r 'x') in (obj, r, h) in let entity_dpm = getx - in let eliminate_non_Qxs = fun truth_value -> + in let eliminator = fun truth_value -> if truth_value = false then unit_dpm false else bind_dpm entity_dpm (fun e -> unit_dpm (q e)) - in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs) + in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator) + - unpacking the definition of `bind_dpm`, that is: + If we simplify and unpack the definition of `bind_dpm`, that's equivalent to: let getx = fun (r, h) -> let obj = List.nth h (r 'x') in (obj, r, h) - in let eliminate_non_Qxs = fun truth_value -> + in let eliminator = fun truth_value -> if truth_value then (fun (r, h) -> let (a, r', h') = getx (r, h) in let u' = (fun e -> unit_dpm (q e)) a in u' (r', h') ) else unit_dpm false - in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs) + in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator) - continuing to simplify: + which can be further simplified to: - let eliminate_non_Qxs = fun truth_value -> + - let eliminate_non_Qxs = fun truth_value -> + let eliminator = fun truth_value -> if truth_value then (fun (r, h) -> let obj = List.nth h (r 'x') in (q obj, r, h) ) else unit_dpm false - in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs) + in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator) This is a function that takes a `bool dpm` as input and returns a `bool dpm set` as output. (Compare to the \[[Qx]] we had before: - let eliminate_non_Qxs = (fun truth_value -> + let eliminator = (fun truth_value -> fun (r, h) -> let truth_value' = if truth_value then let obj = List.nth h (r 'x') in q obj else false in (truth_value', r, h)) - in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs) + in fun one_dpm -> unit_set (bind_dpm one_dpm eliminator) Can you persuade yourself that these are equivalent?) @@ -144,7 +150,7 @@ or: - 
u >>=set \[[Qx]]
+	
u >>= \[[Qx]]
 	

 
 *	Can you figure out how to handle \[[∃x]] on your own? If not, here are some [more hints](/hints/assignment_7_hint_5). But try to get as far as you can on your own.