hints/assignment_7_hint_4.mdwn

   1
   2 *       At the top of p. 13 (this is in between defs 2.8 and 2.9), GS&V give two examples, one for \[[&exist;xPx]] and the other for \[[Qx]]. In fact it will be most natural to break \[[&exist;xPx]] into two pieces, \[[&exist;x]] and \[[Px]]. But first we need to get clear on expressions like \[[Px]].
   3
   4 *       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 a function from entities to `bool`s, `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.
   5
   6         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 ascribed to \[[Qx]] into some meaning for "Q" and a different meaning for "x"?
   7
   8 *       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. I'll assume we have some function Q to start with that maps entities to `bool`s.
   9
  10         Then what we want is something like this:
  11
  12                 let eliminate_non_Qxs = (fun truth_value ->
  13                         fun (r, h) ->
  14                                 let truth_value' =
  15                                         if truth_value
  16                                         then let obj = List.nth h (r 'x') in Q obj
  17                                         else false
  18                                 in (truth_value', r, h))
  19                 in bind_set u (fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs))
  20
  21         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.
  22
  23         We can call the `(fun one_dpm -> ...)` part \[[Qx]] and then updating `u` with \[[Qx]] will be:
  24
  25                 bind_set u \[[Qx]]
  26
  27         or as it's written using Haskell's infix notation for bind:
  28
  29                 u >>= \[[Qx]]
  30
  31 *       Now our second question: how do we decompose the behavior here ascribed to \[[Qx]] into some meaning for "Q" and a different meaning for "x"?
  32
  33         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`. Then what we want is:
  34
  35                 let getx = fun (r, h) ->
  36                         let obj = List.nth h (r 'x')
  37                         in (obj, r, h);;
  38
  39 *       Now what do we do with predicates? As before, we suppose we have a function Q that maps entities to `bool`s. We want to turn it into a function that maps `entity dpm`s to `bool dpm`s. Eventually we'll need to operate not just on single `dpm`s but on sets of them, but first things first. We'll begin by lifting Q into a function that takes `entity dpm`s as arguments and returns `bool dpm`s:
  40
  41                 fun entity_dpm -> bind_dpm entity_dpm (fun e -> unit_dpm (Q e))
  42
  43         Now we have to transform this into a function that again takes single `entity dpm`s as arguments, but now returns a `bool dpm set`. This is easily done with `unit_set`:
  44
  45                 fun entity_dpm -> unit_set (bind_dpm entity_dpm (fun e -> unit_dpm (Q e)))
  46
  47         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.
  48
  49         This is most easily done like this:
  50
  51                 fun entity_dpm ->
  52                         fun truth_value ->
  53                                 if truth_value = false
  54                                 then empty_set
  55                                 else unit_set (bind dpm entity_dpm (fun e -> unit_dpm (Q e)))
  56
  57         Doing things this way will discard `bool dpm`s that start out wrapping `false`, and will pass through other `bool dpm`s that start out wrapping `true` but which our current filter transforms to a wrapped `false`. You might instead aim for consistency, and always pass through wrapped `false`s, whether they started out that way or are only now being generated; or instead always discard such, and only pass through wrapped `true`s. But what we have here will work fine too.
  58
  59         If we let that be \[[Q]], then \[[Q]] \[[x]] would be:
  60
  61                 let getx = fun (r, h) ->
  62                         let obj = List.nth h (r 'x')
  63                         in (obj, r, h)
  64                 in let entity_dpm = getx
  65                 in fun truth_value ->
  66                         if truth_value = false
  67                         then empty_set
  68                         else unit_set (bind_dpm entity_dpm (fun e -> unit_dpm (Q e)))
  69
  70         or, simplifying:
  71
  72                 let getx = fun (r, h) ->
  73                         let obj = List.nth h (r 'x')
  74                         in (obj, r, h)
  75                 in fun truth_value ->
  76                         if truth_value
  77                         then unit_set (bind_dpm getx (fun e -> unit_dpm (Q e)))
  78                         else empty_set
  79
  80         which is:
  81
  82                 let getx = fun (r, h) ->
  83                         let obj = List.nth h (r 'x')
  84                         in (obj, r, h)
  85                 in fun truth_value ->
  86                         if truth_value
  87                         then unit_set (
  88                                 fun (r, h) ->
  89                                         let (a, r', h') = getx (r, h)
  90                                         in let u' = (fun e -> unit_dpm (Q e)) a
  91                                         in u' (r', h')
  92                         ) else empty_set
  93
  94         which is:
  95
  96                 in fun truth_value ->
  97                         if truth_value
  98                         then unit_set (
  99                                 fun (r, h) ->
 100                                         let obj = List.nth h (r 'x')
 101                                         let (a, r', h') = (obj, r, h)
 102                                         in let u' = (fun e -> unit_dpm (Q e)) a
 103                                         in u' (r', h')
 104                         ) else empty_set
 105
 106         which is:
 107
 108                 in fun truth_value ->
 109                         if truth_value
 110                         then unit_set (
 111                                 fun (r, h) ->
 112                                         let obj = List.nth h (r 'x')
 113                                         in let u' = unit_dpm (Q obj)
 114                                         in u' (r', h')
 115                         ) else empty_set
 116
 117         This is a bit different than the \[[Qx]] we had before:
 118
 119                 let eliminate_non_Qxs = (fun truth_value ->
 120                         fun (r, h) ->
 121                                 let truth_value' =
 122                                         if truth_value
 123                                         then let obj = List.nth h (r 'x') in Q obj
 124                                         else false
 125                                 in (truth_value', r, h))
 126                 in (fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs))
 127
 128         because that one passed through every `bool dpm` that wrapped a `false`; whereas now we're discarding some of them. But these will work equally well. We can implement either behavior (or, as we said before, the behavior of never passing through a wrapped `false`).
 129
 130 *       Reviewing: now we've determined how to define \[[Q]] and \[[x]] such that \[[Qx]] can be the result of applying the function \[[Q]] to the `entity dpm` \[[x]]. And \[[Qx]] in turn is now a function that takes a `bool dpm` as input and returns a `bool dpm set` as output. We compose this with a `bool dpm set` we already have on hand:
 131
 132                 bind_set u \[[Qx]]
 133
 134         or:
 135
 136         <pre><code>u >>=<sub>set</sub> \[[Qx]]
 137         </code></pre>
 138
 139 *       Can you figure out how to handle \[[&exist;x]] on your own? If not, here are some [more hints](/hints/assignment_7_hint_5).
 140