assignment 10 tweaks
[lambda.git] / hints / assignment_7_hint_4.mdwn
index 253ee96..046a45b 100644 (file)
@@ -1,59 +1,61 @@
 
 
-*      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.
+*      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 ascribed 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:
 
 
 *      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 set_bind u (fun one_dpm -> set_unit (dpm_bind 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.
+       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 `set_bind` operation. This works by taking each `dpm` in the set and returning a `set_unit` of a filtered `dpm`. The definition of `set_bind` takes care of collecting together all of the `set_unit`s that result for each different set element we started with.
 
        We can call the `(fun one_dpm -> ...)` part \[[Qx]] and then updating `u` with \[[Qx]] will be:
 
 
        We can call the `(fun one_dpm -> ...)` part \[[Qx]] and then updating `u` with \[[Qx]] will be:
 
-               bind_set u \[[Qx]]
+               set_bind u \[[Qx]]
 
        or as it's written using Haskell's infix notation for bind:
 
                u >>= \[[Qx]]
 
 
        or as it's written using Haskell's infix notation for bind:
 
                u >>= \[[Qx]]
 
-*      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"?
+*      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 = fun (r, h) ->
+               let getx : entity dpm = fun (r, h) ->
                        let obj = List.nth h (r 'x')
                        in (obj, r, h);;
 
 *      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:
 
                        let obj = List.nth h (r 'x')
                        in (obj, r, h);;
 
 *      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:
 
-               fun entity_dpm -> bind_dpm entity_dpm (fun e -> unit_dpm (q e))
+               fun entity_dpm -> dpm_bind entity_dpm (fun e -> dpm_unit (q e))
 
 
-       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`:
+       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 `set_unit`:
 
 
-               fun entity_dpm -> unit_set (bind_dpm entity_dpm (fun e -> unit_dpm (q e)))
+               fun entity_dpm -> set_unit (dpm_bind entity_dpm (fun e -> dpm_unit (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 ->
 
        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 dpm_unit false
+                                       else dpm_bind entity_dpm (fun e -> dpm_unit (q e))
+                       in fun one_dpm -> set_unit (dpm_bind 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`.
 
 
        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`.
 
                        let obj = List.nth h (r 'x')
                        in (obj, r, h)
                in let entity_dpm = getx
                        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
                        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)
+                       then dpm_unit false
+                       else dpm_bind entity_dpm (fun e -> dpm_unit (q e))
+               in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator)
 
 
+       <!--
        or, simplifying:
 
                let getx = fun (r, h) ->
                        let obj = List.nth h (r 'x')
                        in (obj, r, h)
        or, simplifying:
 
                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
                        if truth_value
-                       then bind_dpm getx (fun e -> unit_dpm (q e))
-                       else unit_dpm false
-               in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs)
+                       then dpm_bind getx (fun e -> dpm_unit (q e))
+                       else dpm_unit false
+               in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator)
+       -->
 
 
-       unpacking the definition of `bind_dpm`, that is:
+       If we simplify and unpack the definition of `dpm_bind`, that's equivalent to:
 
                let getx = fun (r, h) ->
                        let obj = List.nth h (r 'x')
                        in (obj, r, h)
 
                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)
                        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 let u' = (fun e -> dpm_unit (q e)) a
                                        in u' (r', h')
                                        in u' (r', h')
-                       ) else unit_dpm false
-               in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs)
+                       ) else dpm_unit false
+               in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator)
 
 
-       continuing to simplify:
+       which can be further simplified to:
 
 
-               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')
                                        let (a, r', h') = (obj, r, h)
                        if truth_value
                        then (fun (r, h) ->
                                        let obj = List.nth h (r 'x')
                                        let (a, r', h') = (obj, r, h)
-                                       in let u' = (fun e -> unit_dpm (q e)) a
+                                       in let u' = (fun e -> dpm_unit (q e)) a
                                        in u' (r', h')
                                        in u' (r', h')
-                       ) else unit_dpm false
-               in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs)
+                       ) else dpm_unit false
+               in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator)
 
 
-               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')
                        if truth_value
                        then (fun (r, h) ->
                                        let obj = List.nth h (r 'x')
-                                       in let u' = unit_dpm (q obj)
+                                       in let u' = dpm_unit (q obj)
                                        in u' (r, h)
                                        in u' (r, h)
-                       ) else unit_dpm false
-               in fun one_dpm -> unit_set (bind_dpm one_dpm eliminate_non_Qxs)
+                       ) else dpm_unit false
+               in fun one_dpm -> set_unit (dpm_bind one_dpm eliminator)
+       -->
 
 
-               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)
                        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)
+                       ) else dpm_unit false
+               in fun one_dpm -> set_unit (dpm_bind 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:
 
 
        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))
                        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 -> set_unit (dpm_bind one_dpm eliminator)
 
        Can you persuade yourself that these are equivalent?)   
 
 
        Can you persuade yourself that these are equivalent?)   
 
-*      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:
+*      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 monadically bind this operaration to whatever `bool dpm set` we already have on hand:
 
 
-               bind_set u \[[Qx]]
+               set_bind u \[[Qx]]
 
        or:
 
 
        or:
 
-       <pre><code>u >>=<sub>set</sub> \[[Qx]]
+       <pre><code>u >>= \[[Qx]]
        </code></pre>
 
 *      Can you figure out how to handle \[[&exist;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.
        </code></pre>
 
 *      Can you figure out how to handle \[[&exist;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.