rename topics/_week5_system_F.mdwn to topics/week5_system_F.mdwn
[lambda.git] / topics / week1_order.mdwn
1 ## Major theme: order ##
2
3 Notes from part of the first lecture on one of the larger themes of
4 the course, namely, order.
5
6 ### Order in programming languages, order in natural languages ###
7
8 In programming languages, order matters.  Consider the following
9 program fragment:
10
11     x := 2
12     x := 1
13     print x
14
15 We're using ":=" to mean "takes on the value of" (not "is equal to").
16 This is a fragment written in an imperative style.  When this program
17 is executed, three things should happen: the value of the variable `x`
18 should be set to 1, the value of `x` should be set to 2, and the value
19 of `x` should be printed.  But in addition, these things should happen
20 in a specific order, namely, the order in which the commands are
21 written.  Compare:
22
23     x := 1
24     x := 2
25     print x
26
27 In this fragment, the same things happen, but they happen in a
28 different order.  One way to see this is to note that the expected
29 behavior is different.  The first program will print the number 1,
30 and the second program will print the number 2.
31
32 A similar point is familiar from discussions in the lingusitics
33 literature concerning discourse anaphora.
34
35     1. a. A woman arrived.
36        b. She spoke.
37        c. "a woman" == "she": OK
38
39     2. a. She spoke.
40        b. A woman arrived.
41        c. "a woman" == "she": nearly impossible
42
43 In the discourse fragment in (1), two events are described: an arrival
44 event and a speaking event.  It is easy to interpret the discourse as
45 describing a situation in which the same woman who entered spoke.  In
46 contrast, in discourse (2), it is much more difficult---in fact,
47 barring time travel, nearly impossible---to interpret the situation as
48 describing two events involving a single person.
49
50 The standard explanation is that the use of an indefinite such as "a
51 woman" creates a new discourse referent, which a pronoun such as "she"
52 can refer back to under appropriate circumstances.  In the discourse
53 in (1), the indefinite occurs first, and the pronoun in the second
54 sentence is able to access the discourse referent created by the
55 indefinite.  In the discourse in (2), the pronoun occurs first.  Since
56 the definite has not yet had a chance to create its discourse
57 referent, the pronoun has nothing local to latch onto, and must take
58 its value independently of the resources provided by the discourse.
59
60 We'll discuss a number of specific analyses that will seek to capture
61 the contrast between (1) and (2) later in the course.
62
63 Note that the analogy we are making between the program fragments and
64 the discourse fragments suggests that it makes sense to think of
65 natural language meaning as if it were a computer program.  We are
66 going to take this analogy very seriously indeed: we will suggest that
67 natural language meanings are isomorphic to computer programs.  A
68 closely related version of this claim is the Curry-Howard isomorphism,
69 which establishes a parallel correspondence between logical
70 derivations and programs.
71
72 One consequence of this correspondence is that it makes sense to think
73 of interpreting an expression in natural language in the same terms as
74 we think of interpreting a program: they are "evaluated" or "run".
75
76 ### Dynamic versus static ###
77
78 There is a major long-standing debate in the fields of linguistics and
79 the philoosphy of language about whether it is right to think of
80 natural language meanings as being dynamic in this way.  The
81 alternative, to oversimplify, is to think of natural language (well,
82 the fragment of natural language consisting of declarative sentences)
83 as expressing propositions, which we can treat for the moment as
84 denoting truth values.  The the denotation of a sentence like (1a)
85 will be `true` just in case a woman arrived, and `false` just in case
86 no woman arrived.  On this kind of view, the obvious asymmetry between
87 the discourse in (1) versus the discourse in (2) is supposed to be the
88 result of the ways in which people tend to react to sentences as they
89 exchange information.  That is, it's a fact about the psychology of
90 belief revision, and not part of the meaning of the sentences.  In the
91 terminology of the debate, we can call our view, that sentences
92 express programs, a *dynamic* view, and the notion that sentence
93 meaning is truth conditions and nothing else a *static* view.  (See
94 recent work of Yalcin and Rothschild for a recent version of the
95 static view, with pointers into the literature.)
96
97 One of the things that makes the dynamic/static debate so interesting
98 is that it is not always easy to tell whether a system ought to be
99 classified as dynamic or as static just by looking at its formal
100 properties.  On the one hand, it is well-known (see work of Yalcin and
101 Rothschild, or Groenendijk and Stokhof) that grammars taking the form
102 of a dynamic update system can be reformulated as static grammars if
103 certain conditions are met.  (We'll explore this point in more detail once
104 we have more experience with dynamic grammars.)  So being expressed in
105 the form of a dynamic recipe is no guarantee that the grammar is
106 essentially dynamic.
107
108 On the other hand, it is much less appreciated that supposedly static
109 grammars can nevertheless express analyses that have dynamic
110 intuitions embedded deeply within them.  To see this, consider
111 Classical Logic, the paradigm example of a static system.  Classical
112 theorems are timeless, in the sense that conclusions are independent
113 of the order of the premises.  Here is the meaning of one of the
114 logical connectives of classical logic, expressed in the form of a
115 standard truth table:
116
117     A   B  A and B
118     --------------
119     T   T    T
120     T   F    F
121     F   T    F
122     F   F    F
123
124 This table says that if either of the conjuncts is false, the
125 conjunction as a whole will be false.
126
127 But now consider a small but crucial extension of classical logic.
128 Instead of limiting values to `true` and `false`, we'll allow one
129 additional value: `undefined`, which we'll write as `#`.  To motivate
130 this extension, think of sentences whose presuppositions are not
131 satisfied.
132
133     3. The earth is round.          (true)
134     4. The sun is green.            (false)
135     5. The King of France is bald.  (undefined)
136
137 The usual attitude towards sentences like (5), which presupposes the
138 existence of a specific object that does not in fact exist, is that
139 they are neither true nor false.  Certainly (5) is not true, and
140 saying that it is false appears to commit you to believing that its
141 negation is true, which is not a commitment that everyone is willing
142 to make.
143
144 Given that a partial-function approach to presupposition failure is
145 coherent, let's consider one way to extend classical conjunction:
146
147        p   q  p and q
148     -----------------
149     a. T   T    T
150     b. T   F    F
151     c. F   T    F
152     d. F   F    F
153     -------------
154     e. #   #    #    The King of France is bald and the King of France is bald.
155     f. T   #    #    The earth is round and the King of France is bald.
156     g. #   T    #    The King of France is bald and the earth is round.
157     -------------
158     h. F   #    F
159     i. #   F    #
160
161 The truth table begins just as before (lines (a) through (d)): when
162 both conjuncts are defined, the value of the conjunction as a whole
163 conincides with classical conjunction.  In lines (e) and (f), we
164 imagine conjoining a true proposition with an undefined one.  In order
165 for a conjoined sentence to be true, both conjuncts must be true; and
166 if one of the conjuncts is undefined, there is no way that requirement
167 can be met.  If both conjuncts are undefined, as in (g), then of
168 course the conjunction as a whole will be undefined.
169
170 So far, so good.  Nothing so far undermines the static view.  But now
171 consider the two remaining possibilities, one by one, starting with
172 line (h).  Here is a concrete sentence fitting the pattern addressed
173 by line (h), `F and #`:
174
175     6. The sun is green and the King of France is bald.
176
177 Since a conjoined sentence is true only if both conjuncts are true,
178 (6) cannot possibly evaulate to true: the left conjunct is false, and
179 that settles the matter.  It doesn't matter whether the second
180 conjunct is undefined---any rational and alert listener should be
181 prepared to commit to the falsity of the conjunction as soon as she
182 realizes that the first conjunct is false.  In fact, she can simply
183 stop listening as soon as she hears "The sun is green and...".  No
184 matter whether the second conjunct is well defined, the conjunction as
185 a whole must be false.
186
187     7. The King of France is bald and the sun is green.
188
189 Concerning line (i), in a similar spirit, if the first conjunct is not
190 defined, by the time the first conjunct has been heard, a rational and
191 alert listener should be prepared to commit to the judgment that the
192 presuppositions of the sentence are impossible to satisfy.  No matter
193 how the rest of the conjoined sentence continues, it will presuppose
194 that France has a King.  Therefore is rational to judge the conjoined
195 sentence as a whole to be undefined.
196
197 Comparing lines (h) and (i) in the truth table, there is an asymmetry:
198 the outcome depends on the order of the conjuncts.  The truth table
199 embodies the following processing strategy: if the status of the first
200 conjunct reliably determines some aspect of the status of the
201 conjunction as a whole, let the value of the left conjunct control the
202 outcome.
203
204 To be sure, it would also be coherent to choose a fully symmetric
205 truth table by replacing line (h) with one that maps `F and #` to `#`, or
206 by replacing line (i) with one that maps `# and F` to `F`.  With respect
207 to natural language, of course, which truth table is a better match
208 for a given natural language is an empirical question, and not one
209 that can be settled by logical argument.  If native speakers behave as
210 if sentences with the form in (i) are false, then that is the way a
211 truth table describing that language ought to look.
212
213 But it is sufficient for our point here for the truth table as given
214 to merely be coherent.  Consider a language with a conjunction as
215 defined in the table.  Are the semantics for this language dynamic or
216 static?  Well, there is no explicit notion of *before* or *after* in the
217 processing of a complex sentence.  But the truth table has sensitivity
218 to order baked into its truth conditions.  In that sense, it is
219 dynamic in spirit.
220
221 We should mention that in a series of papers, Schlenker defends a
222 static view of presupposition, given detailed consideration to
223 situations very much like the ones we discuss here involving possible
224 continuations of a sentence, reasoning about the conclusions that a
225 rational listener would come to based on partial knowledge of the
226 sentence.
227
228 An open-ended question:
229
230 The asymmetry in the table arises from the asymmetry in the status
231 of true versus false with respect to conjunction, not from any
232 asymmetry between being undefined and true versus false.  That is,
233 knowing that one conjunct is false is enough to constrain the value of
234 the conjunction as a whole, whereas knowing that one conjunct is true
235 leaves the final outcome completely open.  This asymmetry is evident
236 from the orginal classical truth table.  To what extent can the same
237 point be made using only the classical truth table?  That is, is it
238 possible to argue that classical logic has some order sensitivity
239 baked into it?  It may be worthwhile thinking about material
240 implication: afer all, in the material implication `T --> X`,
241 the value of the implication as a whole depends on the value of `X`,
242 but in the material implication `F --> ?`, the outcome is `T` no
243 matter what the value of `X` turns out to be.
244
245 (To be added: citation details; reasoning about order sensitivity in
246 an order-independent way.)
247
248 The preceding discussion has endeavored to bring out some *similarities*
249 between the kind of order-dependence in our three-valued truth-table, and the
250 kinds of order-dependence exhibited by "dynamic semantics." But there are also
251 of course substantial *differences* between them, and these are also, perhaps
252 even more interesting. Over the course of this semester we hope to clarify and
253 help you to think more carefully about both the similarities and the
254 differences.
255