2 * 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 \[[Px]].
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.
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"?
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 apply a filter that only lets through those `bool dpm`s whose outputs are `(true, r, h)`, where the entity that `r` and `h` associate with variable `x` has the property P. So what we want is:
10 let test = (fun (truth_value, r, h) ->
11 truth_value && (let obj = List.nth h (r 'x') in Q obj))
14 Persuade yourself that in general:
16 List.filter (test : 'a -> bool) (u : 'a set) : 'a set
20 bind_set u (fun a -> if test a then unit_set a else empty_set)
22 Hence substituting in our above formula, we can derive:
24 let test = (fun (truth_value, r, h) ->
25 truth_value && (let obj = List.nth h (r 'x') in Q obj))
26 in bind_set u (fun a -> if test a then unit_set a else empty_set)
30 bind_set u (fun (truth_value, r, h) ->
31 if truth_value && (let obj = List.nth h (r 'x') in Q obj)
32 then unit_set (true, r, h) else empty_set)
34 We can call the `(fun (truth_value, r, h) -> ...)` part \[[Qx]] and then updating `u` with \[[Qx]] will be:
38 or as it's written using Haskell's infix notation for bind:
42 * 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"?
44 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`. Except that we don't have just one `dpm` to compose it with, but a set of them. However, we'll leave that to our predicates to deal with. We'll just make \[[x]] be an operation on a single `dpm`. Let's call the `dpm` we start with `v`. Then what we want to do is:
46 let getx = fun (r, h) ->
47 let obj = List.nth h (r 'x')
49 in bind_dpm v (fun _ -> getx)
51 What's going on here? Our starting `dpm` is a kind of monadic box. We don't care what value is inside that monadic box, which is why we're binding it to a function of the form `fun _ -> ...`. What we return is a new monadic box, which takes `(r, h)` as input and returns the entity they associate with variable `x` (together with unaltered versions of `r` and `h`).
53 * Now what do we do with predicates? We suppose we're given 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:
55 fun entity_dpm -> bind_dpm entity_dpm (fun e -> unit_dpm (Q e))
57 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`:
59 fun entity_dpm -> unit_set (bind_dpm entity_dpm (fun e -> unit_dpm (Q e)))
61 If we let that be \[[Q]], then \[[Q]] \[[x]] would be:
63 let getx = fun (r, h) ->
64 let obj = List.nth h (r 'x')
66 in let entity_dpm = getx
67 in unit_set (bind_dpm entity_dpm (fun e -> unit_dpm (Q e)))
71 let getx = fun (r, h) ->
72 let obj = List.nth h (r 'x')
74 in unit_set (bind_dpm getx (fun e -> unit_dpm (Q e)))
78 let getx = fun (r, h) ->
79 let obj = List.nth h (r 'x')
82 let (a, r', h') = getx (r, h)
83 in let u' = (fun e -> unit_dpm (Q e)) a
84 in unit_set (u' (r', h'))
89 let obj = List.nth h (r 'x')
90 in let (a, r', h') = (obj, r, h)
91 in let u' = (fun e -> unit_dpm (Q e)) a
92 in unit_set (u' (r', h'))
97 let obj = List.nth h (r 'x')
98 in let u' = unit_dpm (Q obj)
99 in unit_set (u' (r, h))
104 let obj = List.nth h (r 'x')
105 in unit_set (unit_dpm (Q obj) (r, h))
110 let obj = List.nth h (r 'x')
111 in unit_set ((Q obj, r, h))
120 , so really \[[x]] will need to be a monadic operation on *a set of* `entity dpm`s. But one thing at a time. First, let's figure out what operation should be performed on each starting `dpm`. Let's call the `dpm` we start with `v`. Then what we want to do is:
123 So that's how \[[x]] should operate on a single `dpm`. How should it operate on a set of them? Well, we just have to take each member of the set and return a `unit_set` of the operation we perform on each of them. The `bind_set` operation takes care of joining all those `unit_set`s together. So, where `u` is the set of `dpm`s we start with, we have:
125 let handle_each = fun v ->
127 let getx = fun (r, h) ->
128 let obj = List.nth h (r 'x')
130 in let result = bind_dpm v (fun _ -> getx)
131 (* we return a unit_set of each result *)
133 in bind_set u handle_each
135 This is a computation that takes a bunch of `_ dpm`s and returns `dpm`s that return their input discourse possibilities unaltered, together with the entity those discouse possibilities associate with variable 'x'. We can take \[[x]] to be the `handle_each` function defined above.
138 * They say the denotation of a variable is the entity which the store `h` assigns to the index that the assignment function `r` assigns to the variable. In other words, if the variable is `'x'`, its denotation wrt `(r, h, w)` is `h[r['x']]`. In our OCaml implementation, that will be `List.nth h (r 'x')`.
142 * Now 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 `s` with \[[∃xPx]] as:
144 <pre><code>s >>= \[[∃x]] >>= \[[Px]]
147 What does \[[∃x]] need to be here? Here's what they say, on the top of p. 13:
149 > Suppose an information state `s` is updated with the sentence ∃xPx. Possibilities in `s` in which no entity has the property P will be eliminated.
151 We can defer that to a later step, where we do `... >>= \[[Px]]`.
153 > The referent system of the remaining possibilities will be extended with a new peg, which is associated with `x`. And for each old possibility `i` in `s`, there will be just as many extensions `i[x/d]` in the new state `s'` and there are entities `d` which in the possible world of `i` have the property P.
155 Deferring the "property P" part, this says:
157 <pre><code>s updated with \[[∃x]] ≡
158 s >>= (fun (r, h) -> List.map (fun d -> newpeg_and_bind 'x' d) domain)
161 That is, for each pair `(r, h)` in `s`, we collect the result of extending `(r, h)` by allocating a new peg for entity `d`, for each `d` in our whole domain of entities (here designated `domain`), and binding the variable `x` to the index of that peg.
163 A later step can then filter out all the possibilities in which the entity `d` we did that with doesn't have property P.
165 So if we just call the function `(fun (r, h) -> ...)` above \[[∃x]], then `s` updated with \[[∃x]] updated with \[[Px]] is just:
167 <pre><code>s >>= \[[∃x]] >>= \[[Px]]
170 or, being explicit about which "bind" operation we're representing here with `>>=`, that is:
172 <pre><code>bind_set (bind_set s \[[∃x]]) \[[Px]]
175 * In def 3.1 on p. 14, GS&V define `s` updated with \[[not φ]] as:
177 > { i &elem; s | i does not subsist in s[φ] }
179 where `i` *subsists* in <code>s[φ]</code> if there are any `i'` that *extend* `i` in <code>s[φ]</code>.
181 Here's how we can represent that:
183 <pre><code>bind_set s (fun (r, h) ->
184 let u = unit_set (r, h)
185 in let descendents = u >>= \[[φ]]
186 in if descendents = empty_set then u else empty_set