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