hints/assignment_7_hint_2.mdwn

   1
   2 *       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.
   3
   4         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.
   5
   6         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.
   7
   8         We'll call these "discourse possibility monads," and let them have the following type:
   9
  10                 type entity = Bob | Carol | Ted | Alice;;
  11                 type store = entity list;;
  12                 type assignment = char -> int;; (* variables are bound to indexes into the store *)
  13                 type 'a discourse_possibility =
  14                         (* we ignore worlds *)
  15                         assignment * store -> 'a * assignment * store
  16
  17         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.
  18
  19 *       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:
  20
  21                 type 'a set = 'a list;;
  22                 let empty_set : 'a set = [];;
  23                 let unit_set (x: 'a) : 'a set = [x];;
  24                 let bind_set (u: 'a set) (f: 'a -> 'b set) =
  25                         List.concat (List.map f u);;
  26
  27 *       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.
  28
  29
  30 *       [More hints](/hints/assignment_7_hint_3).
  31