+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
+