week1.mdwn

   1 Here's what we did in seminar on Monday 9/13, (Sometimes these notes will expand on things mentioned only briefly in class, or discuss useful tangents that didn't even make it into class.)
   2
   3 Applications
   4 ============
   5
   6 We mentioned a number of linguistic and philosophical applications of the tools that we'd be helping you learn in the seminar. (We really do mean "helping you learn," not "teaching you." You'll need to aggressively browse and experiment with the material yourself, or nothing we do in a few two-hour sessions will succeed in inducing mastery of it.)
   7
   8 From linguistics
   9 ----------------
  10
  11 *       generalized quantifiers are a special case of operating on continuations
  12
  13 *       (Chris: fill in other applications...)
  14
  15 *       expressives -- at the end of the seminar we gave a demonstration of modeling [[damn]] using continuations...see the linked summary for more explanation and elaboration
  16
  17 From philosophy
  18 ---------------
  19
  20 *       the natural semantics for positive free logic is thought by some to have objectionable ontological commitments; Jim says that thought turns on not understanding the notion of a "union type", and conflating the folk notion of "naming" with the technical notion of semantic value. We'll discuss this in due course.
  21
  22 *       those issues may bear on Russell's Gray's Elegy argument in "On Denoting"
  23
  24 *       and on discussion of the difference between the meaning of "is beautiful" and "beauty," and the difference between the meaning of "that snow is white" and "the proposition that snow is white."
  25
  26 *       the apparatus of monads, and techniques for statically representing the semantics of an imperatival language quite generally, are explicitly or implicitly invoked in dynamic semantics
  27
  28 *       the semantics for mutation will enable us to make sense of a difference between numerical and qualitative identity---for purely mathematical objects!
  29
  30 *       issues in that same neighborhood will help us better understand proposals like Kit Fine's that semantics is essentially coordinated, and that `R a a` and `R a b` can differ in interpretation even when `a` and `b` don't
  31
  32
  33
  34
  35
  36 1.      Declarative vs imperatival models of computation.
  37 2.      Variety of ways in which "order can matter."
  38 3.      Variety of meanings for "dynamic."
  39 4.      Schoenfinkel, Curry, Church: a brief history
  40 5.      Functions as "first-class values"
  41 6.      "Curried" functions
  42
  43 1.      Beta reduction
  44 1.      Encoding pairs (and triples and ...)
  45 1.      Encoding booleans
  46
  47
  48
  49
  50
  51
  52         Order matters
  53
  54 Declarative versus imperative:
  55
  56 In a pure declarative language, the order in which expressions are
  57 evaluated (reduced, simplified) does not affect the outcome.
  58
  59 (3 + 4) * (5 + 11) = 7 * (5 + 11) = 7 * 16 = 112
  60 (3 + 4) * (5 + 11) = (3 + 4) * 16 = 7 * 16 = 112
  61
  62 In an imperative language, order makes a difference.
  63
  64 x := 2
  65 x := x + 1
  66 x == 3
  67 [true]
  68
  69 x := x + 1
  70 x := 2
  71 x == 3
  72 [false]
  73
  74
  75 Declaratives: assertions of statements.
  76 No matter what order you assert true facts, they remain true:
  77
  78 The value is the product of x and y.
  79 x is the sum of 3 and 4.
  80 y is the sum of 5 and 11.
  81 The value is 112.
  82
  83 Imperatives: performative utterances expressing a deontic or bouletic
  84 modality  ("Be polite", "shut the door")
  85 Resource-sensitive, order sensitive:
  86
  87 Make x == 2.
  88 Add one to x.
  89 See if x == 3.
  90
  91 ----------------------------------------------------
  92
  93 Untype (monotyped) lambda calculus
  94
  95 Syntax:
  96
  97 Variables: x, x', x'', x''', ...
  98 (Cheat:    x, y, z, x1, x2, ...)
  99
 100 Each variable is a term.
 101 For all terms M and N and variable a, the following are also terms:
 102
 103 (M N)   The application of M to N
 104 (\a M)  The abstraction of a over M
 105
 106 Examples of terms:
 107
 108 x
 109 (y x)
 110 (x x)
 111 (\x y)
 112 (\x x)
 113 (\x (\y x))
 114 (x (\x x))
 115 ((\x (x x))(\x (x x)))
 116
 117 Reduction/conversion/equality:
 118
 119 Lambda terms express recipes for combining terms into new terms.
 120 The key operation in the lambda calculus is beta-conversion.
 121
 122 ((\a M) N) ~~>_beta M{a := N}
 123
 124 The term on the left of the arrow is an application whose first
 125 element is a lambda abstraction.  (Such an application is called a
 126 "redex".)  The beta reduction rule says that a redex is
 127 beta-equivalent to a term that is constructed by replacing every
 128 (free) occurrence of a in M by a copy of N.  For example,
 129
 130 ((\x x) z) ~~>_beta z
 131 ((\x (x x)) z) ~~>_beta (z z)
 132 ((\x x) (\y y)) ~~>_beta (\y y)
 133
 134 Beta reduction is only allowed to replace *free* occurrences of a variable.
 135 An occurrence of a variable a is BOUND in T if T has the form (\a N).
 136 If T has the form (M N), and the occurrence of a is in M, then a is
 137 bound in T just in case a is bound in M; if the occurrence of a is in
 138 N, than a is bound in T just in case a is bound in N.  An occurrence
 139 of a variable a is FREE in a term T iff it is not bound in T.
 140 For instance:
 141
 142 T = (x (\x (\y (x (y z)))))
 143
 144 The first occurrence of x in T is free.  The second occurrence of x
 145 immediately follows a lambda, and is bound.  The third occurrence of x
 146 occurs within a form that begins with "\x", so it is bound as well.
 147 Both occurrences of y are bound, and the only occurrence of z is free.
 148
 149 Lambda terms represent functions.
 150 All (recursively computable) functions can be represented by lambda
 151 terms (the untyped lambda calculus is Turning complete).
 152 For some lambda terms, it is easy to see what function they represent:
 153
 154 (\x x) the identity function: given any argument M, this function
 155 simply returns M: ((\x x) M) ~~>_beta M.
 156
 157 (\x (x x)) duplicates its argument:
 158 ((\x (x x)) M) ~~> (M M)
 159
 160 (\x (\y x)) throws away its second argument:
 161 (((\x (\y x)) M) N) ~~> M
 162
 163 and so on.
 164
 165 It is easy to see that distinct lambda terms can represent the same
 166 function.  For instance, (\x x) and (\y y) both express the same
 167 function, namely, the identity function.
 168
 169 -----------------------------------------
 170 Dot notation: dot means "put a left paren here, and put the right
 171 paren as far the right as possible without creating unbalanced
 172 parentheses".  So (\x(\y(xy))) = \x\y.xy, and \x\y.(z y) x =
 173 (\x(\y((z y) z))), but (\x\y.(z y)) x = ((\x(\y(z y))) x).
 174
 175 -----------------------------------------
 176
 177 Church figured out how to encode integers and arithmetic operations
 178 using lambda terms.  Here are the basics:
 179
 180 0 = \f\x.fx
 181 1 = \f\x.f(fx)
 182 2 = \f\x.f(f(fx))
 183 3 = \f\x.f(f(f(fx)))
 184 ...
 185
 186 Adding two integers involves applying a special function + such that
 187 (+ 1) 2 = 3.  Here is a term that works for +:
 188
 189 + = \m\n\f\x.m(f((n f) x))
 190
 191 So (+ 0) 0 =
 192 (((\m\n\f\x.m(f((n f) x))) ;+
 193   \f\x.fx)                 ;0
 194   \f\x.fx)                 ;0
 195
 196 ~~>_beta targeting m for beta conversion
 197
 198 ((\n\f\x.[\f\x.fx](f((n f) x)))
 199  \f\x.fx)
 200
 201 \f\x.[\f\x.fx](f(([\f\x.fx] f) x))
 202
 203 \f\x.[\f\x.fx](f(fx))
 204
 205 \f\x.\x.[f(fx)]x
 206
 207 \f\x.f(fx)
 208
 209
 210
 211 ----------------------------------------------------
 212
 213 A concrete example: "damn" side effects
 214
 215 1. Sentences have truth conditions.
 216 2. If "John read the book" is true, then
 217    John read something,
 218    Someone read the book,
 219    John did something to the book,
 220    etc.
 221 3. If "John read the damn book",
 222    all the same entailments follow.
 223    To a first approximation, "damn" does not affect at-issue truth
 224    conditions.
 225 4. "Damn" does contribute information about the attitude of the speaker
 226    towards some aspect of the situation described by the sentence.
 227
 228
 229
 230 -----------------------------------------
 231 Old notes, no longer operative:
 232
 233 1. Theoretical computer science is beautiful.
 234
 235    Google search for "anagram": Did you mean "nag a ram"?
 236    Google search for "recursion": Did you mean "recursion"?
 237
 238    Y = \f.(\x.f (x x)) (\x.f (x x))
 239
 240
 241 1. Understanding the meaning(use) of programming languages
 242    helps understanding the meaning(use) of natural langauges
 243
 244       1. Richard Montague. 1970. Universal Grammar. _Theoria_ 34:375--98.
 245          "There is in my opinion no important theoretical difference
 246          between natural languages and the artificial languages of
 247          logicians; indeed, I consider it possible to comprehend the
 248          syntax and semantics of both kinds of languages within a
 249          single natural and mathematically precise theory."
 250
 251       2. Similarities:
 252
 253          Function/argument structure:
 254              f(x)
 255              kill(it)
 256          pronominal binding:
 257              x := x + 1
 258              John is his own worst enemy
 259          Quantification:
 260              foreach x in [1..10] print x
 261              Print every number from 1 to 10
 262
 263       3. Possible differences:
 264
 265          Parentheses:
 266              3 * (4 + 7)
 267              ?It was four plus seven that John computed 3 multiplied by
 268              (compare: John computed 3 multiplied by four plus seven)
 269          Ambiguity:
 270              3 * 4 + 7
 271              Time flies like and arrow, fruit flies like a banana.
 272          Vagueness:
 273              3 * 4
 274              A cloud near the mountain
 275          Unbounded numbers of distinct pronouns:
 276              f(x1) + f(x2) + f(x3) + ...
 277              He saw her put it in ...
 278              [In ASL, dividing up the signing space...]
 279
 280
 281 2. Standard methods in linguistics are limited.
 282
 283    1. First-order predicate calculus
 284
 285         Invented for reasoning about mathematics (Frege's quantification)
 286
 287         Alethic, order insensitive: phi & psi == psi & phi
 288         But: John left and Mary left too /= Mary left too and John left
 289
 290    2. Simply-typed lambda calculus
 291
 292         Can't express the Y combinator
 293
 294
 295 3. Meaning is computation.
 296
 297    1. Semantics is programming
 298
 299    2. Good programming is good semantics
 300
 301       1. Example
 302
 303          1. Programming technique
 304
 305             Exceptions
 306               throw (raise)
 307               catch (handle)
 308
 309          2. Application to linguistics
 310               presupposition
 311               expressives
 312
 313               Develop application:
 314                 fn application
 315                 divide by zero
 316                 test and repair
 317                 raise and handle
 318
 319                 fn application
 320                 presupposition failure
 321                 build into meaning of innocent predicates?
 322                 expressives
 323                 throw
 324                 handle
 325                 resume computation
 326