3 Declarative versus imperative:
5 In a pure declarative language, the order in which expressions are
6 evaluated (reduced, simplified) does not affect the outcome.
8 (3 + 4) * (5 + 11) = 7 * (5 + 11) = 7 * 16 = 112
9 (3 + 4) * (5 + 11) = (3 + 4) * 16 = 7 * 16 = 112
11 In an imperative language, order makes a difference.
24 Declaratives: assertions of statements.
25 No matter what order you assert true facts, they remain true:
27 The value is the product of x and y.
28 x is the sum of 3 and 4.
29 y is the sum of 5 and 11.
32 Imperatives: performative utterances expressing a deontic or bouletic
33 modality ("Be polite", "shut the door")
34 Resource-sensitive, order sensitive:
40 ----------------------------------------------------
42 Untype (monotyped) lambda calculus
46 Variables: x, x', x'', x''', ...
47 (Cheat: x, y, z, x1, x2, ...)
49 Each variable is a term.
50 For all terms M and N and variable a, the following are also terms:
52 (M N) The application of M to N
53 (\a M) The abstraction of a over M
64 ((\x (x x))(\x (x x)))
66 Reduction/conversion/equality:
68 Lambda terms express recipes for combining terms into new terms.
69 The key operation in the lambda calculus is beta-conversion.
71 ((\a M) N) ~~>_beta M{a := N}
73 The term on the left of the arrow is an application whose first
74 element is a lambda abstraction. (Such an application is called a
75 "redex".) The beta reduction rule says that a redex is
76 beta-equivalent to a term that is constructed by replacing every
77 (free) occurrence of a in M by a copy of N. For example,
80 ((\x (x x)) z) ~~>_beta (z z)
81 ((\x x) (\y y)) ~~>_beta (\y y)
83 Beta reduction is only allowed to replace *free* occurrences of a variable.
84 An occurrence of a variable a is BOUND in T if T has the form (\a N).
85 If T has the form (M N), and the occurrence of a is in M, then a is
86 bound in T just in case a is bound in M; if the occurrence of a is in
87 N, than a is bound in T just in case a is bound in N. An occurrence
88 of a variable a is FREE in a term T iff it is not bound in T.
91 T = (x (\x (\y (x (y z)))))
93 The first occurrence of x in T is free. The second occurrence of x
94 immediately follows a lambda, and is bound. The third occurrence of x
95 occurs within a form that begins with "\x", so it is bound as well.
96 Both occurrences of y are bound, and the only occurrence of z is free.
98 Lambda terms represent functions.
99 All (recursively computable) functions can be represented by lambda
100 terms (the untyped lambda calculus is Turning complete).
101 For some lambda terms, it is easy to see what function they represent:
103 (\x x) the identity function: given any argument M, this function
104 simply returns M: ((\x x) M) ~~>_beta M.
106 (\x (x x)) duplicates its argument:
107 ((\x (x x)) M) ~~> (M M)
109 (\x (\y x)) throws away its second argument:
110 (((\x (\y x)) M) N) ~~> M
114 It is easy to see that distinct lambda terms can represent the same
115 function. For instance, (\x x) and (\y y) both express the same
116 function, namely, the identity function.
118 -----------------------------------------
119 Dot notation: dot means "put a left paren here, and put the right
120 paren as far the right as possible without creating unbalanced
121 parentheses". So (\x(\y(xy))) = \x\y.xy, and \x\y.(z y) x =
122 (\x(\y((z y) z))), but (\x\y.(z y)) x = ((\x(\y(z y))) x).
124 -----------------------------------------
126 Church figured out how to encode integers and arithmetic operations
127 using lambda terms. Here are the basics:
135 Adding two integers involves applying a special function + such that
136 (+ 1) 2 = 3. Here is a term that works for +:
138 + = \m\n\f\x.m(f((n f) x))
141 (((\m\n\f\x.m(f((n f) x))) ;+
145 ~~>_beta targeting m for beta conversion
147 ((\n\f\x.[\f\x.fx](f((n f) x)))
150 \f\x.[\f\x.fx](f(([\f\x.fx] f) x))
152 \f\x.[\f\x.fx](f(fx))
160 ----------------------------------------------------
162 A concrete example: "damn" side effects
164 1. Sentences have truth conditions.
165 2. If "John read the book" is true, then
167 Someone read the book,
168 John did something to the book,
170 3. If "John read the damn book",
171 all the same entailments follow.
172 To a first approximation, "damn" does not affect at-issue truth
174 4. "Damn" does contribute information about the attitude of the speaker
175 towards some aspect of the situation described by the sentence.
179 -----------------------------------------
180 Old notes, no longer operative:
182 1. Theoretical computer science is beautiful.
184 Google search for "anagram": Did you mean "nag a ram"?
185 Google search for "recursion": Did you mean "recursion"?
187 Y = \f.(\x.f (x x)) (\x.f (x x))
190 1. Understanding the meaning(use) of programming languages
191 helps understanding the meaning(use) of natural langauges
193 1. Richard Montague. 1970. Universal Grammar. _Theoria_ 34:375--98.
194 "There is in my opinion no important theoretical difference
195 between natural languages and the artificial languages of
196 logicians; indeed, I consider it possible to comprehend the
197 syntax and semantics of both kinds of languages within a
198 single natural and mathematically precise theory."
202 Function/argument structure:
207 John is his own worst enemy
209 foreach x in [1..10] print x
210 Print every number from 1 to 10
212 3. Possible differences:
216 ?It was four plus seven that John computed 3 multiplied by
217 (compare: John computed 3 multiplied by four plus seven)
220 Time flies like and arrow, fruit flies like a banana.
223 A cloud near the mountain
224 Unbounded numbers of distinct pronouns:
225 f(x1) + f(x2) + f(x3) + ...
226 He saw her put it in ...
227 [In ASL, dividing up the signing space...]
230 2. Standard methods in linguistics are limited.
232 1. First-order predicate calculus
234 Invented for reasoning about mathematics (Frege's quantification)
236 Alethic, order insensitive: phi & psi == psi & phi
237 But: John left and Mary left too /= Mary left too and John left
239 2. Simply-typed lambda calculus
241 Can't express the Y combinator
244 3. Meaning is computation.
246 1. Semantics is programming
248 2. Good programming is good semantics
252 1. Programming technique
258 2. Application to linguistics
269 presupposition failure
270 build into meaning of innocent predicates?