-* GS&V's semantics involves elements from several different monads we've been looking at. First, they're working with (epistemic) modalities, so there are worlds playing a role like they did in [[Reader Monad for Intensionality]]. But we're going to ignore the modal element for this exercise. There's also variable binding, which is [another reader monad](/reader_monad_for_variable_binding). Next, there is a notion of a store, which some operations add new reference cells to. We implement this with a state monad (and so too do they, in effect, though they don't conceive of what they're doing in those terms). So we'll be working with a combination of both a reader monad for the variable binding and a state monad to keep track of the new "pegs" or reference cells.
+* GS&V's semantics involves elements from several different monads we've been looking at. First, they're working with (epistemic) modalities, so there are worlds playing a role like they did in [[Reader Monad for Intensionality]]. But we're going to ignore the modal element for this exercise. There's also variable binding, which calls for [another reader monad](/reader_monad_for_variable_binding). Next, there is a notion of a store, which some operations add new reference cells to. We implement this with a state monad (and so too, in effect, do they---though they don't conceive of what they're doing in those terms). So we'll be working with a combination of both a reader monad for the variable binding and a state monad to keep track of the new "pegs" or reference cells.
There are systematic ways to layer different monads together. If you want to read about these, a keyword is "monad transformers." Ken Shan discusses them in [his paper](http://arxiv.org/abs/cs/0205026v1) that we recommended earlier.
However, since we haven't studied these, we will just combine the reader monad and the state monad in an ad hoc way. The easiest way to do this is to think of the assignment function and the store of reference cells as a combined state, which gets threaded through the computations in the same way that simple states did in your earlier homeworks.
- We'll call these "discourse possibility monads," and let them have the following type:
+ We'll call these "discourse possibility monads," or `dpm`s, and type them as follows:
type entity = Bob | Carol | Ted | Alice;;
- type store = entity list;;
+ let domain = [Bob; Carol; Ted; Alice];;
type assignment = char -> int;; (* variables are bound to indexes into the store *)
- type 'a discourse_possibility =
+ type store = entity list;;
+
+ type 'a dpm =
(* we ignore worlds *)
assignment * store -> 'a * assignment * store
- Although we're leaving worlds out of the picture, each of these monadic objects still represents a different discourse possibility: which entities might be being talked about, using which variables.
+ Although we're leaving worlds out of the picture, each of these monadic values still represents a different *discourse* possibility: which entities might be being talked about, using which variables.
-* We notice though that GS&V don't just work with discourse possibilities (or more broadly, epistemic possibilities), they work with what they call "information states," which are *sets* of possibilities. OK, a set is just another monadic layer. For simplicity, we'll represent sets using lists:
+ 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:
- 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) =
- List.concat (List.map f u);;
+ let unit_dpm (value : 'a) : 'a dpm = fun (r, h) -> (value, r, h);;
-* So GS&V's information states, which they notate using `s`, are set-monads, whose elements in turn are discourse possibilities, which they notate using `i`, which are state monads that keep track of which entities have been introduced as objects of discourse, and which variables are bound to them, in a given discourse possibility. In GS&V's system, possibilities are triples of an assignment function, `r`, a store `g`, and a world `w`. We're leaving the worlds out. Also, instead of just working with pairs `(r, g)`, we're working with state monads for which those pairs constitute the states we update.
+ 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
+ in u' (r', h')
+* A *possibility* for GS&V is a triple of an assignment function `r`, a store `h`, and a world `w`. We're dropping worlds so we'll call pairs `(r, h)` *discourse possibilities*. *dpm*s are monads that represent computations that may mutate---or in GS&V's terminology "extend"---discourse possibilities. An `'a dpm` is a function that takes a starting `(r, h)` and returns an `'a` and a possibly mutated `r'` and `h'`.
-* [More hints](/hints/assignment_7_hint_3).
+* Is that enough? If not, here are some [more hints](/hints/assignment_7_hint_3). But try to get as far as you can on your own.