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