1 <!-- λ ◊ ≠ ∃ Λ ∀ ≡ α β γ ρ ω φ ψ Ω ○ μ η δ ζ ξ ⋆ ★ • ∙ ● ⚫ 𝟎 𝟏 𝟐 𝟘 𝟙 𝟚 𝟬 𝟭 𝟮 ⇧ (U+2e17) ¢ -->
5 # Doing things with monads
7 ## Extended application: Groenendijk, Stokhof and Veltman's *Coreference and Modality*
9 GSV are interested in developing and establishing a reasonable theory
10 of discourse update. One way of looking at this paper is like this:
14 GS = Dynamic Predicate Logic L&P 1991: dynamic binding, donkey anaphora
15 Dynamic Montague Grammar 1990: generalized quantifiers, discourse referents
17 V = epistemic modality
19 That is, Groenendijk and Stokhof have a well-known theory of dynamic
20 semantics, and Veltman has a well-known theory of epistemic modality,
21 and this fragment brings both of those strands together into a single
24 We will be interested in this paper both from a theoretical point of
25 view and from a practical engineering point of view. On the
26 theoretical level, these scholars are proposing a strategy for
27 managing the connection between variables and the objects they
28 designate in way that is flexible enough to be useful for describing
29 natural language. The main way they attempt to do this is by
30 inserting an extra level in between the variable and the object:
31 instead of having an assignment function that maps variables directly
32 onto objects, GSV provide *pegs*: variables map onto pegs, and pegs
33 map onto objects. We'll discuss in considerable detail what pegs
34 allow us to do, since it is highly relevant to one of the main
35 applications of the course, namely, reference and coreference.
37 What are pegs? The term harks back to a paper by Landman called `Pegs
38 and Alecs'. There pegs are simply hooks for hanging properties on.
39 Pegs are supposed to be as anonymous as possible. Think of hanging
40 your coat on a physical peg: you don't care which peg it is, only that
41 there are enough pegs for everyone's coat to hang from. Likewise, for
42 the pegs of GSV, all that matters is that there are enough of them.
43 (Incidentally, there is nothing in Gronendijk and Stokhof's original
44 DPL paper that corresponds naturally to pegs; but in their Dynamic
45 Montague Grammar paper, pegs serve a purpose similar to discourse
46 referents there, though the connection is not simple.)
48 On an engineering level, the fact that GSV are combining anaphora and
49 bound quantification with epistemic quantification means that they are
50 gluing together related but distinct subsystems into a single
51 fragment. These subsystems naturally cleave into separate layers in a
52 way that is obscured in the paper. We will argue in detail that
53 re-engineering GSV using monads will lead to a cleaner system that
54 does all of the same theoretical work.
56 Empirical targets: on the anaphoric side, GSV want to
58 On the epistemic side, GSV aim to account for asymmetries such as
60 It might be raining. It's not raining.
61 #It's not raining. It might be raining.
65 There are a lot of formal details in the paper in advance of the
66 empirical discussion. Here are the ones that matter for our purposes:
70 type refsys = var -> peg
71 type ent = Alice | Bob | Carl
72 type assignment = peg -> ent
74 So in order to get from a variable to an object, we have to compose a
75 refsys `r` with an assignment `g`. For instance, we might have
76 r (g ("x")) = Alice. A question to keep in mind as we proceed is why
77 the mapping from variables to objects has been articulated into two
78 functions. Why not map variables directly to objects? (We'll return
79 to this question later.)
82 type world = pred -> ent -> bool
84 type poss = world * pegcount * refsys * assignment
85 type infostate = [poss]
87 Worlds in general settle all matters of fact in the world. In
88 particular, they determine the extensions of predicates and relations.
89 In this discussion, we'll (crudely) approximate worlds by making them
90 a function from predicates such as "man" to a function mapping each
93 As we'll see, indefinites as a side effect increase the number of pegs
94 by one. GSV assume that we can determine what integer the next unused
95 peg corresponds to by examining the range of the refsys function.
96 We'll make things easy on ourselves by simply tracking the total
97 number of used pegs in a counter called `pegcount`.
99 So information states track both facts about the world (e.g., which
100 objects count as a man), and facts about the discourse (e.g., how many
101 pegs have been used).
103 The formal language the fragment interprets is Predicate Calculus with
104 equality, existential and universal quantification, and one unary
105 modality (box and diamond, corresponding to epistemic necessity and
106 epistemic possibility).
108 Terms in this language are either individuals such as Alice or Bob, or
109 else variables. So in general, the referent of a term can depend on a
112 ref(i, t) = t if t is an individual, and
113 g(r(t)) if t is a variable, where i = (w,n,r,g)
115 Here are the main clauses for update (their definition 3.1).
117 Following GSV, we'll write `update(s, φ)` (the update of information
118 state `s` with the information in φ) as `s[φ]`.
120 s[P(t)] = {i in s | w(P)(ref(i,t))}
122 So `man(x)` is the set of live possibilities `i = (w,r,g)` in s such that
123 the set of men in `w` given by `w(man)` maps the object referred to by
124 `x`, namely, `r(g("x"))`, to `true`. That is, update with "man(x)"
125 discards all possibilities in which "x" fails to refer to a man.
127 s[t1 = t2] = {i in s | ref(i,t1) = ref(i,t2)}
131 When updating with a conjunction, first update with the left conjunct,
132 then update with the right conjunct.
134 Existential quantification is somewhat intricate.
136 s[∃xφ] = Union {{(w, n+1, r[x->n], g[n->a]) | (w,n,r,g) in s}[φ] | a in ent}
138 Here's the recipe: given a starting infostate s, choose an object a
139 from the domain of discourse. Construct a modified infostate s' by
140 adding a peg to each possibility in s and adjusting the refsys and the
141 assignment in order to map the variable x to a. Then update s' with
142 φ, and collect the results of doing this for every object a in the
145 Negation is natural enough:
147 s[neg φ] = {i | {i}[φ] = {}}
149 If updating φ with the information state that contains only the
150 possibility i returns the empty information state, then not φ is true
153 In GSV, disjunction, the conditional, and the universals are defined
154 in terms of negation and the other connectives (see fact 3.2).
156 Exercise: assume that there are two entities in the domain of
157 discourse, Alice and Bob. Assume that Alice is a woman, and Bob is a
160 We're using `++` here to mean set union.
162 1. {(w,n,r,g)}[∃x.person(x)]
164 = {(w,n+1,r[x->n],g[n->a])}[person(x)] ++ {(w,n+1,r[x->n],g[n->b])}[person(x)]
165 = {(w,n+1,r[x->n],g[n->a])} ++ {(w,n+1,r[x->n],g[n->b])}
166 = {(w,n+1,r[x->n],g[n->a]),(w,n+1,r[x->n],g[n->b])}
167 -- both a and b are people
169 2. {(w,n,r,g)}[∃x.man(x)]
171 = {(w,n+1,r[x->n],g[n->a])}[man(x)] ++ {(w,n+1,r[x->n],g[n->b])}[man(x)]
172 = {} ++ {(w,n+1,r[x->n],g[n->b])}
173 = {(w,n+1,r[x->n],g[n->b])}
176 3. {(w,n,r,g)}[∃x∃y.person(x) and person(y)]
178 = {(w,n+1,r[x->n],g[n->a])}[∃y.person(x) and person(y)]
179 ++ {(w,n+1,r[x->n],g[n->b])}[∃y.person(x) and person(y)]
181 = ( {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->a])}[person(x)][person(y)]
182 ++ {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->b])}[person(x)][person(y)])
183 ++ ( {(w, n+2, r[x->n][y->n+1], g[n->b][n+1->a])}[person(x)][person(y)]
184 ++ {(w, n+2, r[x->n][y->n+1], g[n->b][n+1->b])}[person(x)][person(y)])
186 = {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->a]),
187 (w, n+2, r[x->n][y->n+1], g[n->a][n+1->b])}
188 ++ {(w, n+2, r[x->n][y->n+1], g[n->b][n+1->a]),
189 (w, n+2, r[x->n][y->n+1], g[n->b][n+1->b])}
191 = {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->a]),
192 (w, n+2, r[x->n][y->n+1], g[n->a][n+1->b]),
193 (w, n+2, r[x->n][y->n+1], g[n->b][n+1->a]),
194 (w, n+2, r[x->n][y->n+1], g[n->b][n+1->b])}
196 -- there are four ways of assigning x and y to people
199 4. {(w,n,r,g)}[∃x∃y.x=y]
201 = ( {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->a])}[x=y]
202 ++ {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->b])}[x=y]
203 ++ ( {(w, n+2, r[x->n][y->n+1], g[n->b][n+1->a])}[x=y]
204 ++ {(w, n+2, r[x->n][y->n+1], g[n->b][n+1->b])}[x=y]
206 = {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->a])}
207 ++ {(w, n+2, r[x->n][y->n+1], g[n->b][n+1->b])}
209 = {(w, n+2, r[x->n][y->n+1], g[n->a][n+1->a]),
210 (w, n+2, r[x->n][y->n+1], g[n->b][n+1->b])}
212 -- two ways to assign x and y to the same value
214 ## Order and modality
216 The final remaining update rule concerns modality:
218 s[◊φ] = {i in s | s[φ] ≠ {}}
220 This is a peculiar rule: a possibility `i` will survive update just in
221 case something is true of the information state `s` as a whole. That
222 means that either every `i` in `s` will survive, or none of them will. The
223 criterion is that updating `s` with the information in φ does not
224 produce the contradictory information state (i.e., `{}`).
226 So let's explore what this means. GSV offer a contrast between two
227 discourses that differ only in the order in which the updates occur.
228 The fact that the predictions of the fragment differ depending on
229 order shows that the system is order-sensitive.
231 1. Alice isn't hungry. #Alice might be hungry.
233 According to GSV, the combination of these sentences in this order is
234 `inconsistent', and they mark the second sentence with the star of
235 ungrammaticality. We'll say instead that the discourse is
236 gramamtical, leave the exact word to use for its intuitive effect up
237 for grabs. What is important for our purposes is to get clear on how
238 the fragment behaves with respect to these sentences.
240 We'll start with an infostate containing two possibilities. In one
241 possibility, Alice is hungry (call this possibility "hungry"); in the
242 other, she is not (call it "full").
244 {hungry, full}[Alice isn't hungry][Alice might be hungry]
245 = {full}[Alice might be hungry]
248 As usual in dynamic theories, a sequence of sentences is treated as if
249 the sentence were conjoined. This is the same thing as updating with
250 the first sentence, then updating with the second sentence.
251 Update with *Alice isn't hungry* eliminates the possibility in which
252 Alice is hungry, leaving only the possibility in which she is full.
253 Subsequent update with *Alice might be hungry* depends on the result
254 of updating with the prejacent, *Alice is hungry*. Let's do that side
257 {full}[Alice is hungry]
260 Because the only possibility in the information state is one in which
261 Alice is not hungry, update with *Alice is hungry* results in an empty
262 information state. That means that update with *Alice might be
263 hungry* will also be empty, as indicated above.
265 In order for update with *Alice might be hungry* to be non-empty,
266 there must be at least one possibility in the input state in which
267 Alice is hungry. That is what epistemic might means in this fragment:
268 the prejacent must be possible. But update with *Alice isn't hungry*
269 eliminates all possibilities in which Alice is hungry. So the
270 prediction of the fragment is that update with the sequence in (1)
271 will always produce an empty information state.
273 In contrast, consider the sentences in the opposite order:
275 2. Alice might be hungry. Alice isn't hungry.
277 We'll start with the same two possibilities.
280 = {hungry, full}[Alice might be hungry][Alice isn't hungry]
281 = {hungry, full}[Alice isn't hungry]
284 Update with *Alice might be hungry* depends on the result of updating
285 with the prejacent, *Alice is hungry*. Here's the side calculation:
287 {hungry, full}[Alice is hungry]
290 Since this update is non-empty, all of the original possibilities
291 survive update with *Alice might be hungry*. By now it should be
292 obvious that update with a *might* sentence either has no effect, or
293 produces an empty information state. The net result is that we can
294 then go on to update with *Alice isn't hungry*, yielding an updated
295 information state that contains only possibilities in which Alice
298 GSV comment that a single speaker couldn't possibly be in a position
299 to utter the discourse in (2). The reason is that in order for the
300 speaker to appropriately assert that Alice isn't hungry, that speaker
301 would have to possess knowledge (or sufficient justification,
302 depending on your theory of the norms for assertion) that Alice isn't
303 hungry. But if they know that Alice isn't hungry, they couldn't
304 appropriately assert *Alice might be hungry*, based on the predictions
307 Another view is that it can be acceptable to assert a sentence if it
308 is supported by the information in the common ground. So if the
309 speaker assumes that as far as the listener knows, Alice might be
310 hungry, they can utter the discourse in (2). Here's a variant that
311 makes this thought more vivid:
313 3. Based on public evidence, Alice might be hungry. But in fact she's not hungry.
315 The main point to appreciate here is that the update behavior of the
316 discourses depends on the order in which the updates due to the
317 individual sentence occur.
319 Note, incidentally, that there is an asymmetry in the fragment
322 4. Alice might be hungry. Alice *is* hungry.
323 5. Alice is hungry. (So of course) Alice might be hungry.
325 Both of these discourses lead to the same update effect: all and only
326 those possibilites in which Alice is hungry survive. If you think
327 that asserting *might* requires that the prejacent be undecided, you
328 will have to consider an update rule for the diamond on which update
329 with the prejacent and its negation must both be non-empty.
333 The GSV fragment differs from the DPL and the DMG dynamic semantics in
334 important details. Nevertheless, it has more or less the same things
335 to say about anaphora, binding, quantificational binding, and donkey
338 In particular, continuing the theme of order-based asymmetries,
340 6. A man^x entered. He_x sat.
341 7. He_x sat. A man^x entered.
343 These discourses differ only in the order of the sentences. Yet the
344 first allows for coreference between the indefinite and the pronoun,
345 where the second discourse does not. In order to demonstrate, we'll
346 need an information state whose refsys is defined for at least one
349 8. {(w,1,r[x->0],g[0->b])}
351 This infostate contains a refsys and an assignment that maps the
352 variable x to Bob. Here are the facts in world w:
362 We can now consider the discourses in (6) and (7) (after magically
363 converting them to the Predicate Calculus):
365 9. Someone^x entered. He_x sat.
367 {(w,1,r[x->0],g[0->b])}[∃x.enter(x)][sit(x)]
369 -- the existential adds a new peg and assigns it to each
372 = ( {(w,2,r[x->0][x->1],g[0->b][1->a])}[enter(x)]
373 ++ {(w,2,r[x->0][x->1],g[0->b][1->b])}[enter(x)]
374 ++ {(w,2,r[x->0][x->1],g[0->b][1->c])}[enter(x)])[sit(x)]
376 -- "enter(x)" filters out the possibility in which x refers
377 -- to Alice, since Alice didn't enter
380 ++ {(w,2,r[x->0][x->1],g[0->b][1->b])}
381 ++ {(w,2,r[x->0][x->1],g[0->b][1->c])})[sit(x)]
383 -- "sit(x)" filters out the possibility in which x refers
384 -- to Carl, since Carl didn't sit
386 = {(w,2,r[x->0][x->1],g[0->b][1->b])}
388 Note that `r[x->0][x->1]` maps `x` to 1---the outermost adjustment is
389 the operative one. In other words, `r[x->0][x->1] == (r[x->0])[x->1]`.
391 One of the key facts here is that even though the existential has
392 scope only over the first sentence, in effect it binds the pronoun in
393 the following clause. This is characteristic of dynamic theories in
394 the style of Groenendijk and Stokhof, including DPL and DMG.
396 The outcome is different if the order of the sentences is reversed.
398 10. He_x sat. Someone^x entered.
400 {(w,1,r[x->0],g[0->b])}[sit(x)][∃x.enter(x)]
402 -- evaluating `sit(x)` rules out nothing, since (coincidentally)
403 -- x refers to Bob, and Bob is a sitter
405 = {(w,1,r[x->0],g[0->b])}[∃x.enter(x)]
407 -- Just as before, the existential adds a new peg and assigns
410 = {(w,2,r[x->0][x->1],g[0->b][1->a])}[enter(x)]
411 ++ {(w,2,r[x->0][x->1],g[0->b][1->b])}[enter(x)]
412 ++ {(w,2,r[x->0][x->1],g[0->b][1->c])}[enter(x)]
414 -- enter(x) eliminates all those possibilities in which x did
417 = {} ++ {(w,2,r[x->0][x->1],g[0->b][1->b])}
418 ++ {(w,2,r[x->0][x->1],g[0->b][1->c])}
420 = {(w,2,r[x->0][x->1],g[0->b][1->b]),
421 (w,2,r[x->0][x->1],g[0->b][1->c])}
423 The result is different than before. Before, there was only one
424 possibility: that x refered to the only person who both entered and
425 sat. Here, there remain two possibilities: that x refers to Bob, or
426 that x refers to Carl. This makes predictions about the
427 interpretation of continuations of the dialogs:
429 11. A man^x entered. He_x sat. He_x spoke.
430 12. He_x sat. A man^x entered. He_x spoke.
432 The construal of (11) as marked entails that the person who spoke also
433 entered and sat. The construal of (12) guarantees only that the
434 person who spoke also entered. There is no guarantee that the person
437 Intuitively, there is a strong impression in (12) that the person who
438 entered and spoke not only should not be identified as the person who
439 sat, he should be different from the person who sat. Some dynamic
440 systems, such as Heim's File Change Semantics, guarantee non-identity.
441 That is not guaranteed by the GSV fragment. The GSV guarantees that
442 the indefinite introduces a novel peg, but there is no requirement
443 that the peg refers to a novel object. If you wanted to add this as a
444 refinement to the fragment, you could require that whenever a new peg
445 gets added, it must be mapped onto an object that is not in the range
446 of the original assignment function.
448 As usual with dynamic semantics, a point of pride is the ability to
449 give a good account of donkey anaphora, as in
451 13. If a woman entered, she sat.
453 See the paper for details.
455 ## Interactions of binding with modality
457 At this point, we have a fragment that handles modality, and that
458 handles indefinites and pronouns. It it only interesting to combine
459 these two elements if they interact in non-trivial ways. This is
460 exactly what GSV argue.
462 The discussion of indefinites in the previous section established the
463 following dynamic equivalence:
465 (∃x.enter(x)) and (sit(x)) ≡ ∃x (enter(x) and sit(x))
467 In words, existentials take effective scope over subsequent clauses.
469 The presence of modal possibility, however, disrupts this
470 generalization. GSV illustrate this with the following story.
473 There are three sons, Bob, Carl, and Dave.
474 One of them broke a vase.
475 Bob is known to be innocent.
476 Someone is hiding in the closet.
478 (∃x.closet(x)) and (◊guilty(x)) ≡/≡ ∃x (closet(x) and ◊guilty(x))
480 To see this, we'll start with the left hand side. We'll need at least
484 --------------- ---------------
493 GSV observe that (∃x.closet(x)) and (◊guilty(x)) is true if there is
494 at least one possibility in which a person in the closet is guilty.
495 In this scenario, world w is the verifying world. It remains possible
496 that there are closet hiders who are not guilty in any world. Carl
497 fits this bill: he's in the closet in world w', but he is not guilty
500 Let's see how this works out in detail.
502 14. Someone^x is in the closet. He_x might be guilty.
504 {(w,0,r,g), (w',0,r,g}[∃x.closet(x)][◊guilty(x)]
506 -- existential introduces new peg
508 = ( {(w,1,r[x->0],g[0->b])}[closet(x)]
509 ++ {(w,1,r[x->0],g[0->c])}[closet(x)]
510 ++ {(w,1,r[x->0],g[0->d])}[closet(x)]
511 ++ {(w',1,r[x->0],g[0->b])}[closet(x)]
512 ++ {(w',1,r[x->0],g[0->c])}[closet(x)]
513 ++ {(w',1,r[x->0],g[0->d])}[closet(x)])[◊guilty(x)]
515 -- only possibilities in which x is in the closet survive
517 = {(w,1,r[x->0],g[0->d]),
518 (w',1,r[x->0],g[0->c])}[◊guilty(x)]
520 -- Is there any possibility in which x is guilty?
521 -- yes: for x = Dave, in world w Dave broke the vase
523 = {(w,1,r[x->0],g[0->d]),
524 (w',1,r[x->0],g[0->c])}
526 Now we consider the second half:
528 14. Someone^x is in the closet who_x might be guilty.
530 {(w,0,r,g), (w',0,r,g)}[∃x(closet(x) & ◊guilty(x))]
532 -- existential introduces new peg
534 = {(w,1,r[x->0],g[0->b])}[closet(x)][◊guilty(x)]
535 ++ {(w,1,r[x->0],g[0->c])}[closet(x)][◊guilty(x)]
536 ++ {(w,1,r[x->0],g[0->d])}[closet(x)][◊guilty(x)]
537 ++ {(w',1,r[x->0],g[0->b])}[closet(x)][◊guilty(x)]
538 ++ {(w',1,r[x->0],g[0->c])}[closet(x)][◊guilty(x)]
539 ++ {(w',1,r[x->0],g[0->d])}[closet(x)][◊guilty(x)]
541 -- filter out possibilities in which x is not in the closet
542 -- and filter out possibilities in which x is not guilty
543 -- the only person who was guilty in the closet was Dave in
546 = {(w,1,r[x->0],g[0->d])}
548 The result is different, and more informative.
550 ## Binding, modality, and identity
552 The fragment correctly predicts the following contrast:
554 15. Someone^x entered. He_x might be Bob. He_x might not be Bob.
555 (∃x.enter(x)) & ◊x=b & ◊not(x=b)
556 -- This discourse requires a possibility in which Bob entered
557 -- and another possibility in which someone who is not Bob entered
559 16. Someone^x entered who might be Bob and who might not be Bob.
560 ∃x (enter(x) & ◊x=b & ◊not(x=b))
561 -- This is a contradition: there is no single person who might be Bob
562 -- and who simultaneously might be someone else
564 These formulas are expressing extensional, de-reish intuitions. If we
565 add individual concepts to the fragment, the ability to express
566 fancier claims would come along.
570 Let α be a term which differs from x. Then α is an identifier if the
571 following formula is supported by every information state:
575 The idea is that α is an identifier just in case there is only one
576 object that it can refer to. Here is what GSV say:
578 A term is an identifier per se if no mattter what the information
579 state is, it cannot fail to decie what the denotation of the term is.
581 ## Why articulate the mapping from variables to objects into two
584 In the current system, variables are associated with values in two
587 Variables Pegs Entities
588 --------- r ---- g --------
593 Here, r is a refsys mapping variables to pegs, and g is an assignment
594 function mapping pegs to entities.
596 Assignment functions are free to map different pegs to the same
599 Variables Pegs Entities
600 --------- r ---- g --------
605 But this is possible with ordinary assignment functions as well.
607 It is possible to imagine a refsys that maps more than one variable to
608 the same peg. But the fragment is designed to prevent that from ever
609 happening: the only way to associate a variable with a peg is by
610 evaluating an existential quantifier, and the existential quantifier
611 always introduces a fresh, unused peg.
613 So what does the bipartite system do that ordinary assignment