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.) Applications ============ 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.) From linguistics ---------------- * generalized quantifiers are a special case of operating on continuations * (Chris: fill in other applications...) * 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 From philosophy --------------- * 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. * those issues may bear on Russell's Gray's Elegy argument in "On Denoting" * 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." * 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 * the semantics for mutation will enable us to make sense of a difference between numerical and qualitative identity---for purely mathematical objects! * 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 1. Declarative vs imperatival models of computation. 2. Variety of ways in which "order can matter." 3. Variety of meanings for "dynamic." 4. Schoenfinkel, Curry, Church: a brief history 5. Functions as "first-class values" 6. "Curried" functions 1. Beta reduction 1. Encoding pairs (and triples and ...) 1. Encoding booleans Order matters Declarative versus imperative: In a pure declarative language, the order in which expressions are evaluated (reduced, simplified) does not affect the outcome. (3 + 4) * (5 + 11) = 7 * (5 + 11) = 7 * 16 = 112 (3 + 4) * (5 + 11) = (3 + 4) * 16 = 7 * 16 = 112 In an imperative language, order makes a difference. x := 2 x := x + 1 x == 3 [true] x := x + 1 x := 2 x == 3 [false] Declaratives: assertions of statements. No matter what order you assert true facts, they remain true: The value is the product of x and y. x is the sum of 3 and 4. y is the sum of 5 and 11. The value is 112. Imperatives: performative utterances expressing a deontic or bouletic modality ("Be polite", "shut the door") Resource-sensitive, order sensitive: Make x == 2. Add one to x. See if x == 3. ---------------------------------------------------- Untype (monotyped) lambda calculus Syntax: Variables: x, x', x'', x''', ... (Cheat: x, y, z, x1, x2, ...) Each variable is a term. For all terms M and N and variable a, the following are also terms: (M N) The application of M to N (\a M) The abstraction of a over M Examples of terms: x (y x) (x x) (\x y) (\x x) (\x (\y x)) (x (\x x)) ((\x (x x))(\x (x x))) Reduction/conversion/equality: Lambda terms express recipes for combining terms into new terms. The key operation in the lambda calculus is beta-conversion. ((\a M) N) ~~>_beta M{a := N} The term on the left of the arrow is an application whose first element is a lambda abstraction. (Such an application is called a "redex".) The beta reduction rule says that a redex is beta-equivalent to a term that is constructed by replacing every (free) occurrence of a in M by a copy of N. For example, ((\x x) z) ~~>_beta z ((\x (x x)) z) ~~>_beta (z z) ((\x x) (\y y)) ~~>_beta (\y y) Beta reduction is only allowed to replace *free* occurrences of a variable. An occurrence of a variable a is BOUND in T if T has the form (\a N). If T has the form (M N), and the occurrence of a is in M, then a is bound in T just in case a is bound in M; if the occurrence of a is in N, than a is bound in T just in case a is bound in N. An occurrence of a variable a is FREE in a term T iff it is not bound in T. For instance: T = (x (\x (\y (x (y z))))) The first occurrence of x in T is free. The second occurrence of x immediately follows a lambda, and is bound. The third occurrence of x occurs within a form that begins with "\x", so it is bound as well. Both occurrences of y are bound, and the only occurrence of z is free. Lambda terms represent functions. All (recursively computable) functions can be represented by lambda terms (the untyped lambda calculus is Turning complete). For some lambda terms, it is easy to see what function they represent: (\x x) the identity function: given any argument M, this function simply returns M: ((\x x) M) ~~>_beta M. (\x (x x)) duplicates its argument: ((\x (x x)) M) ~~> (M M) (\x (\y x)) throws away its second argument: (((\x (\y x)) M) N) ~~> M and so on. It is easy to see that distinct lambda terms can represent the same function. For instance, (\x x) and (\y y) both express the same function, namely, the identity function. ----------------------------------------- Dot notation: dot means "put a left paren here, and put the right paren as far the right as possible without creating unbalanced parentheses". So (\x(\y(xy))) = \x\y.xy, and \x\y.(z y) x = (\x(\y((z y) z))), but (\x\y.(z y)) x = ((\x(\y(z y))) x). ----------------------------------------- Church figured out how to encode integers and arithmetic operations using lambda terms. Here are the basics: 0 = \f\x.fx 1 = \f\x.f(fx) 2 = \f\x.f(f(fx)) 3 = \f\x.f(f(f(fx))) ... Adding two integers involves applying a special function + such that (+ 1) 2 = 3. Here is a term that works for +: + = \m\n\f\x.m(f((n f) x)) So (+ 0) 0 = (((\m\n\f\x.m(f((n f) x))) ;+ \f\x.fx) ;0 \f\x.fx) ;0 ~~>_beta targeting m for beta conversion ((\n\f\x.[\f\x.fx](f((n f) x))) \f\x.fx) \f\x.[\f\x.fx](f(([\f\x.fx] f) x)) \f\x.[\f\x.fx](f(fx)) \f\x.\x.[f(fx)]x \f\x.f(fx) ---------------------------------------------------- A concrete example: "damn" side effects 1. Sentences have truth conditions. 2. If "John read the book" is true, then John read something, Someone read the book, John did something to the book, etc. 3. If "John read the damn book", all the same entailments follow. To a first approximation, "damn" does not affect at-issue truth conditions. 4. "Damn" does contribute information about the attitude of the speaker towards some aspect of the situation described by the sentence. ----------------------------------------- Old notes, no longer operative: 1. Theoretical computer science is beautiful. Google search for "anagram": Did you mean "nag a ram"? Google search for "recursion": Did you mean "recursion"? Y = \f.(\x.f (x x)) (\x.f (x x)) 1. Understanding the meaning(use) of programming languages helps understanding the meaning(use) of natural langauges 1. Richard Montague. 1970. Universal Grammar. _Theoria_ 34:375--98. "There is in my opinion no important theoretical difference between natural languages and the artificial languages of logicians; indeed, I consider it possible to comprehend the syntax and semantics of both kinds of languages within a single natural and mathematically precise theory." 2. Similarities: Function/argument structure: f(x) kill(it) pronominal binding: x := x + 1 John is his own worst enemy Quantification: foreach x in [1..10] print x Print every number from 1 to 10 3. Possible differences: Parentheses: 3 * (4 + 7) ?It was four plus seven that John computed 3 multiplied by (compare: John computed 3 multiplied by four plus seven) Ambiguity: 3 * 4 + 7 Time flies like and arrow, fruit flies like a banana. Vagueness: 3 * 4 A cloud near the mountain Unbounded numbers of distinct pronouns: f(x1) + f(x2) + f(x3) + ... He saw her put it in ... [In ASL, dividing up the signing space...] 2. Standard methods in linguistics are limited. 1. First-order predicate calculus Invented for reasoning about mathematics (Frege's quantification) Alethic, order insensitive: phi & psi == psi & phi But: John left and Mary left too /= Mary left too and John left 2. Simply-typed lambda calculus Can't express the Y combinator 3. Meaning is computation. 1. Semantics is programming 2. Good programming is good semantics 1. Example 1. Programming technique Exceptions throw (raise) catch (handle) 2. Application to linguistics presupposition expressives Develop application: fn application divide by zero test and repair raise and handle fn application presupposition failure build into meaning of innocent predicates? expressives throw handle resume computation