1 <!-- λ ◊ ≠ ∃ Λ ∀ ≡ α β γ ρ ω φ ψ Ω ○ μ η δ ζ ξ ⋆ ★ • ∙ ● ⚫ 𝟎 𝟏 𝟐 𝟘 𝟙 𝟚 𝟬 𝟭 𝟮 ⇧ (U+2e17) ¢ -->
5 ## Doing things with monads (an extended application): Groenendijk, Stokhof and Veltman's *Coreference and Modality*
7 GSV are interested in developing and establishing a reasonable theory
8 of discourse update. One way of looking at this paper is like this:
12 > GS = Dynamic theories of binding of Groenendijk and Stokhof, e.g.,
13 > Dynamic Predicate Logic L&P 1991: dynamic binding, donkey anaphora
14 > Dynamic Montague Grammar 1990: generalized quantifiers and
17 > V = a dynamic theory of epistemic modality, e.g.,
18 > Veltman, Frank. "Data semantics."
19 > In Truth, Interpretation and Information, Foris, Dordrecht
21 > Veltman, Frank. "Defaults in update semantics." Journal of
22 > philosophical logic 25.3 (1996): 221-261.
24 That is, Groenendijk and Stokhof have a well-known theory of dynamic
25 semantics, and Veltman has a well-known theory of epistemic modality,
26 and this fragment brings both of those strands together into a single
27 system. The key result, as we'll discuss, is that adding modality to
28 dynamic semantics creates some unexpected and fascinating
31 ## Basics of GSV's fragment
33 The fragment in this paper is unusually elegant. We'll present it on
34 its own terms, with the exception that we will not use GSV's "pegs".
35 See the discussion below below concerning pegs for an explanation.
36 After presenting the paper, we'll re-engineer the fragment using
39 In this fragment, points of evaluation are not just worlds, but pairs
40 consisting of a world and an assginment function. This conception of
41 an evaluation point is familiar from Heim's 1983 File Change
42 Semantics. Following GSV, we'll call a world-assignment pair a
43 "possibility", and so a context (an "information state") will be set
44 of possiblities. As GSV emphasize, infostates simultaneously track
45 information about the world (which possible worlds are live
46 possibilities?) as well as information about the discourse (which
47 objects to the variables refer to?).
49 The formal language the fragment interprets is the Predicate Calculus
50 with equality, existential and universal quantification, and one unary
51 modality, interpreted as epistemic possibility.
53 An implementation in OCaml is available [[here|/code/gsv.ml]]; consult
54 that code for details of syntax, types, and values. [[An implementation
55 in Haskell|/code/gsv.hs]] is available as well, if you prefer.
57 (We've also written [[a fuller and separate implementation|/code/gsv2.ml]] using the OCaml Juli8 Monad libraries. This fuller implementation
58 demonstrates a graduated collection of semantics, so that you can see how we start from a monadic implementation
59 of classic variable binding, and step by step approach the system presented by GSV. In the fullness of time, these
60 two bodies of code will be merged. But for the time being, we just present them both for your edification.)
62 Terms in this language are either individuals such as Alice or Bob, or
63 else variables. So in general, the referent of a term can depend on a
66 ref (i,t) = t if t is an individual, and
67 g(t) if t is a variable, where i = (w,g)
69 Immediately following are the recipes for context update (GSV's
70 definition 3.1). Following GSV, we'll write `update(s, φ)` (the
71 update of information state `s` with the information in φ) as `s[φ]`.
73 s[P(t)] = {(w,g) in s | extension w P (ref((w,g),t))}
75 So `man(x)` is the set of live possibilities `(w,g)` in s such that
76 the set of men in `w` given by `extension w "man"` maps the object
77 referred to by `x`, namely, `g("x")`, to `true`. That is, update with
78 "man(x)" discards all possibilities in which "x" fails to refer to a
81 s[t1 = t2] = {i in s | ref(i,t1) == ref(i,t2)}
85 When updating with a conjunction, first update with the left conjunct,
86 then update with the right conjunct.
88 Existential quantification is somewhat intricate.
90 s[∃xφ] = Union {{(w, g[x->a]) | (w,g) in s}[φ] | a in ent}
92 Here's the recipe: given a starting infostate s, choose an object a
93 from the domain of discourse. Construct a modified infostate s' by
94 adjusting the assignment function of each possibility so as to map the
95 variable x to a. Then update s' with φ. Finally, take the union over
96 the results of doing this for every object a in the domain of
97 discourse. If you're unsure about exactly what this recipe does,
98 examine the implementations linked above.
100 Negation is natural enough:
102 s[neg φ] = {i | {i}[φ] = {}}
104 If updating φ with the information state that contains only the
105 possibility i returns the empty information state, then not φ is true
108 In GSV, disjunction, the conditional, and the universals are defined
109 in terms of negation and the other connectives (see fact 3.2).
111 Exercise: assume that there are three entities in the domain of
112 discourse, Alice, Bob, and Carl. Assume that Alice is a woman, and
113 Bob and Carl are men.
115 Compute the following:
117 1. {(w,g)}[∃x.man(x)]
119 = {(w,g[x->a])}[man(x)] ++ {(w,g[x->b])}[man(x)]
120 ++ {(w,g[x->c])}[man(x)]
121 = {} ++ {(w,g[x->b])} ++ {(w,g[x->c])}
122 = {(w,g[x->a]),(w,g[x->b]),(w,g[x->c])}
123 -- Bob and Carl are men
125 2. {(w,g)}[∃x.woman(x)]
126 3. {(w,g)}[∃x∃y.man(x) and man(y)]
129 Running the [[code|code/gsv.ml]] gives the answers.
132 ## Order and modality
134 The final remaining update rule concerns modality:
136 s[◊φ] = {i in s | s[φ] ≠ {}}
138 This is a peculiar rule: a possibility `i` will survive update just in
139 case something is true of the information state `s` as a whole. That
140 means that either every `i` in `s` will survive, or none of them will.
141 The criterion is that updating `s` with the information in the
142 prejacent φ does not produce the contradictory information state
145 So let's explore what this means. GSV offer a contrast between two
146 discourses that differ only in the order in which the updates occur.
147 The fact that the predictions of the fragment differ depending on
148 order shows that the system is order-sensitive.
150 1. Alice isn't hungry. #Alice might be hungry.
152 According to GSV, the combination of these sentences in this order is
153 `inconsistent', and they mark the second sentence with the star of
154 ungrammaticality. We'll say instead that the discourse is
155 gramamtical, leave the exact way to think about its intuitive status
156 up for grabs. What is important for our purposes is to get clear on
157 how the fragment behaves with respect to these sentences.
159 We'll start with an infostate containing two possibilities. In one
160 possibility, Alice is hungry (call this possibility "hungry"); in the
161 other, she is not (call it "full").
163 {hungry, full}[Alice isn't hungry][Alice might be hungry]
164 = {full}[Alice might be hungry]
167 As usual in dynamic theories, a sequence of sentences is treated as if
168 the sentence were conjoined. This is the same thing as updating with
169 the first sentence, then updating with the second sentence.
170 Update with *Alice isn't hungry* eliminates the possibility in which
171 Alice is hungry, leaving only the possibility in which she is full.
172 Subsequent update with *Alice might be hungry* depends on the result
173 of updating with the prejacent, *Alice is hungry*. Let's do that side
176 {full}[Alice is hungry]
179 Because the only possibility in the information state is one in which
180 Alice is not hungry, update with *Alice is hungry* results in an empty
181 information state. That means that update with *Alice might be
182 hungry* will also be empty, as indicated above.
184 In order for update with *Alice might be hungry* to be non-empty,
185 there must be at least one possibility in the input state in which
186 Alice is hungry. That is what epistemic might means in this fragment:
187 there must be a possibility in the starting infostate that is
188 consistent with the prejacent. But update with *Alice isn't hungry*
189 eliminates all possibilities in which Alice is hungry. So the
190 prediction of the fragment is that update with the sequence in (1)
191 will always produce an empty information state.
193 In contrast, consider the sentences in the opposite order:
195 2. Alice might be hungry. Alice isn't hungry.
197 We'll start with the same two possibilities.
199 = {hungry, full}[Alice might be hungry][Alice isn't hungry]
200 = {hungry, full}[Alice isn't hungry]
203 This is a very different result: the two sentences are consistent, and
204 do not guarantee an empty output infostate.
206 GSV comment that a single speaker couldn't possibly be in a position
207 to utter the discourse in (2). The reason is that in order for the
208 speaker to appropriately assert that Alice isn't hungry, that speaker
209 would have to possess knowledge (or sufficient justification,
210 depending on your theory of the norms for assertion) that Alice isn't
211 hungry. But if they know that Alice isn't hungry, they couldn't
212 appropriately assert *Alice might be hungry*, based on the predictions
215 Another view is that it can be acceptable to assert a sentence if it
216 is supported by the information in the common ground. So if the
217 speaker assumes that as far as the listener knows, Alice might be
218 hungry, they can utter the discourse in (2). Here's a variant that
219 makes this thought more vivid:
221 3. (Based on public evidence,) Alice might be hungry.
222 (But in fact I have private knowledge that) she's not hungry.
224 The main point to appreciate here is that the update behavior of the
225 discourses depends on the order in which the sentences are processed.
227 Note, incidentally, that the treatment of modality contains an
228 asymmetry related to negation.
230 4. Alice might be hungry. Alice *is* hungry.
231 5. Alice is hungry. (So of course) Alice might be hungry.
233 Both of these discourses lead to the same update effect: all and only
234 those possibilites in which Alice is hungry survive. So negating an
235 assertion rules out the possibility, but asserting the non-negated
238 You might think that asserting *might* requires that the prejacent be
239 not merely possible, but undecided. If you like this idea, you can
240 easily write an update rule for the diamond on which update with the
241 prejacent and its negation must both be non-empty.
245 The GSV fragment differs from the DPL and the DMG dynamic semantics in
246 important details. Nevertheless, it is highly similar to DPL with
247 respect to anaphora, binding, quantificational binding, and donkey
248 anaphora (at least, until we add modality into the mix, as we will
251 In particular, continuing the theme of order-based asymmetries,
253 6. A man^x entered. He_x sat.
254 7. He_x sat. A man^x entered.
256 These discourses differ only in the order of the sentences. Yet the
257 first allows for coreference between the indefinite and the pronoun,
258 where the second discourse does not.
260 In order to demonstrate how the fragment treats these discourses, we'll
261 need an information state whose refsys is defined for at least one
266 This infostate contains a refsys and an assignment that maps the
267 variable x to Bob. Here are the facts in world w:
269 extension w "enter" a = false
270 extension w "enter" b = true
271 extension w "enter" c = true
273 extension w "sit" a = true
274 extension w "sit" b = true
275 extension w "sit" c = false
277 We can now consider the discourses in (6) and (7) (after magically
278 converting them to the Predicate Calculus):
280 9. Someone^x entered. He_x sat.
282 {(w,g[x->b])}[∃x.enter(x)][sit(x)]
284 = ( {(w,g[x->b][x->a])}[enter(x)]
285 ++ {(w,g[x->b][x->b])}[enter(x)]
286 ++ {(w,g[x->b][x->c])}[enter(x)])[sit(x)]
288 -- "enter(x)" filters out the possibility in which x refers
289 -- to Alice, since Alice didn't enter
292 ++ {(w,g[x->b][x->b])}
293 ++ {(w,g[x->b][x->c])})[sit(x)]
295 -- "sit(x)" filters out the possibility in which x refers
296 -- to Carl, since Carl didn't sit
298 = {(w,g[x->b][x->b])}
300 One of the key facts here is that even though the existential has
301 scope only over the first sentence, in effect it binds the pronoun in
302 the following clause. This is characteristic of dynamic theories in
303 the style of Groenendijk and Stokhof, including DPL and DMG.
305 The outcome is different if the order of the sentences is reversed.
307 10. He_x sat. Someone^x entered.
309 {(w,g[x->b])}[sit(x)][∃x.enter(x)]
311 -- evaluating `sit(x)` rules out nothing, since (coincidentally)
312 -- x refers to Bob, and Bob is a sitter
314 = {(w,g[x->b])}[∃x.enter(x)]
316 -- Just as before, the existential adds a new peg and assigns
319 = {(w,g[x->b][x->a])}[enter(x)]
320 ++ {(w,g[x->b][x->b])}[enter(x)]
321 ++ {(w,g[x->b][x->c])}[enter(x)]
323 -- enter(x) eliminates all those possibilities in which x did
326 = {} ++ {(w,g[x->b][x->b])}
327 ++ {(w,g[x->b][x->c])}
329 = {(w,g[x->b][x->b]), (w,g[x->b][x->c])}
331 Before, there was only one possibility: that x refered to the only
332 person who both entered and sat. Here, there remain two
333 possibilities: that x refers to Bob, or that x refers to Carl. This
334 makes predictions about the interpretation of continuations of the
337 11. A man^x entered. He_x sat. He_x spoke.
338 12. He_x sat. A man^x entered. He_x spoke.
340 The construal of (11) as marked entails that the person who spoke also
341 entered and sat. The construal of (12) guarantees only that the
342 person who spoke also entered. There is no guarantee that the person
345 Intuitively, there is a strong impression in (12) that the person who
346 entered and spoke not only should not be identified as the person who
347 sat, he should be different from the person who sat. Some dynamic
348 systems, such as Heim's File Change Semantics, guarantee non-identity.
349 That is not guaranteed by the GSV fragment. If you wanted to add this
350 as a refinement to the fragment, you could require that the
351 existential only considers object in the domain that are not in the
352 range of the starting assignment function.
354 As usual with dynamic semantics, a point of pride is the ability to
355 give a good account of donkey anaphora, as in
357 13. If a woman entered, she sat.
359 See the paper for details.
361 ## Interactions of binding with modality
363 At this point, we have a fragment that handles modality, and that
364 handles indefinites and pronouns. It it only interesting to combine
365 these two elements if they interact in non-trivial ways. This is
366 exactly what GSV argue.
368 The discussion of indefinites in the previous section established the
369 following dynamic equivalence:
371 (∃x.enter(x)) and (sit(x)) ≡ ∃x (enter(x) and sit(x))
373 In words, existentials can bind pronouns in subsequent clauses even if
374 they don't take syntactic scope over those clauses.
376 The presence of modal possibility, however, disrupts this
377 generalization. GSV illustrate this with the following story.
380 There are three children: Alice, Bob, and Carl.
381 One of them broke a vase.
382 Alice is known to be innocent.
383 Someone is hiding in the closet.
385 (∃x.closet(x)) and (◊guilty(x)) ≡/≡ ∃x (closet(x) and ◊guilty(x))
387 To see this, we'll start with the left hand side. We'll need at least
391 --------------- ---------------
400 GSV say that (∃x.closet(x)) and (◊guilty(x)) is true if there is at
401 least one possibility in which a person in the closet is guilty. In
402 this scenario, world w' is the verifying world: Carl is in the closet,
403 and he's guilty. It remains possible that there are closet hiders who
404 are not guilty in any world. Alice fits this bill: she's in the
405 closet in world w, but she is not guilty in any world.
407 Let's see how this works out in detail.
409 14. Someone^x is in the closet. They_x might be guilty.
411 {(w,g), (w',g}[∃x.closet(x)][◊guilty(x)]
413 -- existential introduces new peg
415 = ( {(w,g[x->a])}[closet(x)]
416 ++ {(w,g[x->b])}[closet(x)]
417 ++ {(w,g[x->c])}[closet(x)]
418 ++ {(w',g[x->a])}[closet(x)]
419 ++ {(w',g[x->b])}[closet(x)]
420 ++ {(w',g[x->c])}[closet(x)])[◊guilty(x)]
422 -- only possibilities in which x is in the closet survive
425 = {(w,g[x->a]), (w',g[x->c])}[◊guilty(x)]
427 -- Is there any possibility in which x is guilty?
428 -- yes: for x = Carl, in world w' Carl broke the vase
429 -- that's enough for the possiblity modal to allow the entire
430 -- infostate to pass through unmodified.
432 = {(w,g[x->a]),(w',g[x->c])}
434 Now we consider the second half:
436 15. Someone^x is in the closet who_x might be guilty.
438 {(w,g), (w',g)}[∃x(closet(x) & ◊guilty(x))]
440 = {(w,g[x->a])}[closet(x)][◊guilty(x)]
441 ++ {(w,g[x->b])}[closet(x)][◊guilty(x)]
442 ++ {(w,g[x->c])}[closet(x)][◊guilty(x)]
443 ++ {(w',g[x->a])}[closet(x)][◊guilty(x)]
444 ++ {(w',g[x->b])}[closet(x)][◊guilty(x)]
445 ++ {(w',g[x->c])}[closet(x)][◊guilty(x)]
447 -- filter out possibilities in which x is not in the closet
448 -- and filter out possibilities in which x is not guilty
449 -- the only person who was guilty in the closet was Carl in
454 The result is different. Fewer possibilities remain. We have one of
455 the possible worlds (w is ruled out), and we have ruled out possible
456 discourses (x cannot refer to Alice). So the second formula is more
459 One of main conclusions of GSV is that in the presence of modality,
460 the hallmark of dynamic treatments--that existentials bind outside of
461 their syntactic scope--needs to refined into a more nuanced understanding.
462 Binding still occurs, but the extent of the syntactic scope of an existential
463 has a detectable effect on truth conditions.
465 As we discovered in class, there is considerable work to be done to
466 decide which expressions in natural language (if any) are capable of
467 expressing which of the two translations into the GSV fragment. We
468 can certainly grasp the two distinct sets of truth conditions, but
469 that is not the same thing as discovering that there are natural
470 language sentences that conventionally express one or the other or
474 ## Binding, modality, and identity
476 The fragment correctly predicts the following contrast:
478 16. Someone^x entered. He_x might be Bob. He_x might not be Bob.
479 (∃x.enter(x)) & ◊x=b & ◊not(x=b)
480 -- This discourse requires a possibility in which Bob entered
481 -- and another possibility in which someone who is not Bob entered
483 17. Someone^x entered who might be Bob and who might not be Bob.
484 ∃x (enter(x) & ◊x=b & ◊not(x=b))
485 -- This is a contradition: there is no single person who might be Bob
486 -- and who simultaneously might be someone else
488 These formulas are expressing extensional, de-re-ish intuitions. If we
489 add individual concepts to the fragment, the ability to express
490 fancier claims would come along.
492 ## GSV's "Identifiers"
494 Let α be a term which differs from x. Then α is an identifier if the
495 following formula is supported by every information state:
499 The idea is that α is an identifier just in case there is only one
500 object that it can refer to. Here is what GSV say:
502 A term is an identifier per se if no mattter what the information
503 state is, it cannot fail to decie what the denotation of the term is.
507 One of the more salient aspects of the technical part of the paper is
508 that GSV insert an extra level in between the variable and the object:
509 instead of having an assignment function that maps variables directly
510 onto objects, GSV provide *pegs*: variables map onto pegs, and pegs
511 map onto objects. It happens that pegs play no role in the paper
512 whatsoever. We've demonstrated this by providing a faithful
513 implementation of the paper that does not use pegs at all.
515 Nevertheless, it makes sense to pause here to discuss pegs briefly,
516 since this technique is highly relevant to one of the main
517 applications of the course, namely, reference and coreference.
519 What are pegs? The term harks back to a 1986 paper by Fred Landman
520 called `Pegs and Alecs'. Pegs are simply hooks for hanging properties
521 on. Pegs are supposed to be as anonymous as possible. Think of
522 hanging your coat on a physical peg: you don't care which peg it is,
523 only that there are enough pegs for everyone's coat to hang from.
524 Likewise, for the pegs of GSV, all that matters is that there are
525 enough of them. (Incidentally, there is nothing in Gronendijk and
526 Stokhof's original DPL paper that corresponds naturally to pegs; but
527 in their Dynamic Montague Grammar paper, pegs serve a purpose similar
528 to discourse referents there, though the connection is not simple.)
530 Pegs can be highly useful for exploring puzzles of reference and
533 Standard assignment function System with Pegs (drefs)
534 ---------------------------- ------------------------
535 Variable Object Var Peg Object
536 --------- ------- --- --- ------
537 x --> a x --> 0 --> a
539 z --> b z --> 1 --> a
541 A standard assignment function can map two different variables onto
542 the same object. In the diagram, x and y are both mapped onto the
543 object a. With discourse referents in view, we can have two different
544 flavors of coreference. Just as with ordinary assignment functions,
545 variables can be mapped onto pegs (discourse referents) that are in
546 turn mapped onto the same object. In the diagram, x is mapped onto
547 the peg 0, which in turn is mapped onto the object a, and z is mapped
548 onto a discourse referent that is mapped onto a. On a deeper level,
549 we can suppose that y is mapped onto the same discourse referent as
550 x. With a system like this, we are free to reassign the discourse
551 referent associated with z to a different object, in which case x and
552 z will no longer refer to the same object. But there is no way to
553 change the object associated with x without necessarily changing the
554 object associated with y. They are coreferent in a deeper, less
557 GSV could make use of this expressive power. But they don't. In
558 fact, their system is careful designed to guarantee that every
559 variable is assigned a discourse referent distinct from all previous
562 The addition of pegs tracks an active discussion in the dynamic
563 literature around the time of publication of the paper. Groenendijk
564 and Stokhof (Two theories of dynamic semantics, 1989) noted that it
565 was possible in DPL for information to be "lost".
567 18. (∃x.P(x)) & (∃x.Q(x)) & R(x)
569 If the two existentials happen to bind the same variable (here, "x"),
570 then the second existential occludes the first. That is, at the point
571 at which we evalute R(x), all of the assignment functions will be
572 mapping the variable "x" to objects that have property Q. The
573 information that there exist objects with property P has been lost.
574 If you want your dynamic system to be eliminative---or in more general
575 terms, if you want the amount of information embodied by an updated
576 information state to be monotonically increasing---then this is a
579 A syntactic solution is to require that the variable bound
580 by an existential to be chosen fresh.
582 Vermeulen, Cees FM. "Merging without mystery or: Variables in dynamics
583 semantics." Journal of Philosophical Logic 24.4 (1995): 405-450 offers
584 a different approach, one based on *referent systems*. GSV's pegs are
585 a referent system. In the pegs system, when (18) is processed, the
586 information that there is an object that has property P is maintained
587 in the information state. Curiously, however, there is still no way
588 to refer to that object, at least, not with a variable, since there is
589 no variable that is associated with the peg that points to the
590 relevant object. So the information is present, but not accessible.
592 That does not mean that there aren't other expression types besides
593 pronouns or variables that might be able to latch onto pegs. An
594 intriguing suggestion based on an example in Vermeulen is that
595 "former" might be able to provide access to a hidden peg:
597 19. Someone entered. Someone spoke. The former was a woman.
599 Presumably we want *the former* to be able to pick out the person who
600 entered, whether or not the two existentials bind the same variable or
601 not. If we allow "former" to latch onto the second most recently
602 established peg, no matter whether there is a variable still pointing
603 to that peg, the desired effect is achieved.
605 But none of this is relevant for any of the explanations or analyses
606 provided by the GSV fragment, and it is considerably simpler to see
607 what their fragment is about if we leave referent systems out of it.