--- /dev/null
+Here are the definitions pre-loaded for working on assignment 3:
+
+<textarea id="INPUT" style="border: 2px solid black; color: black; font-family: monospace; height: 3in; overflow: auto; padding: 0.5em; width: 100%;">
+let true = \x y. x in
+let false = \x y. y in
+let and = \l r. l (r true false) false in
+let makePair = \f s g. g f s in
+let fst = true in
+let snd = false in
+let nil = makePair true meh in
+let isNil = \x. x fst in
+let makeList = \h t. makePair false (makePair h t) in
+let head = \l. isNil l err (l snd fst) in
+let tail = \l. isNil l err (l snd snd) in
+let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in
+let Y = \f. (\h. f (h h)) (\h. f (h h)) in
+let isZero = \n. n (\x. false) true in
+let succ = \n s z. s (n s z) in
+let mult = \m n s. m (n s) in
+let length = Y (\length l. isNil l 0 (succ (length (tail l)))) in
+let pred = \n. isZero n 0 (length (tail (n (\p. makeList meh p) nil))) in
+let leq = \m n. isZero(n pred m) in
+let eq = \m n. and (leq m n)(leq n m) in
+;
+length (tail mylist)
+</textarea>
+<input id="PARSE" value="Normalize" type="button">
+<input id="ETA" type="checkbox">do eta-reductions too
+<noscript><p>You may not see it because you have JavaScript turned off. Uffff!</p></noscript>
+<script src="/code/lambda.js"></script>
+<script src="/code/tokens.js"></script>
+<script src="/code/parse.js"></script>
+<script src="/code/json2.js"></script>
+<pre id="OUTPUT">
+</pre>
+<script>
+/*jslint evil: true */
+
+/*members create, error, message, name, prototype, stringify, toSource,
+ toString, write
+*/
+
+/*global JSON, make_parse, parse, source, tree */
+
+// Make a new object that inherits members from an existing object.
+
+if (typeof Object.create !== 'function') {
+ Object.create = function (o) {
+ function F() {}
+ F.prototype = o;
+ return new F();
+ };
+}
+
+// Transform a token object into an exception object and throw it.
+
+Object.prototype.error = function (message, t) {
+ t = t || this;
+ t.name = "SyntaxError";
+ t.message = message;
+ throw t;
+};
+
+
+(function () {
+ var parse = make_parse();
+
+ function go(source) {
+ var string, tree, expr, eta;
+ try {
+ tree = parse(source);
+ // string = JSON.stringify(tree, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
+ expr = tree.handler();
+ // string = JSON.stringify(expr, ['key', 'name', 'message', 'value', 'arity', 'first', 'second', 'tag', 'variable', 'left', 'right', 'bound', 'body' ], 4);
+// string = expr.to_string() + "\n\n~~>\n\n";
+ string = '';
+ eta = document.getElementById('ETA').checked;
+ string = string + reduce(expr, eta, false).to_string();
+ } catch (e) {
+ string = JSON.stringify(e, ['name', 'message', 'from', 'to', 'key',
+ 'value', 'arity', 'first', 'second', 'third', 'fourth'], 4);
+ }
+ document.getElementById('OUTPUT').innerHTML = string
+ .replace(/&/g, '&')
+ .replace(/[<]/g, '<');
+ }
+
+ document.getElementById('PARSE').onclick = function (e) {
+ go(document.getElementById('INPUT').value);
+ };
+}());
+
+</script>
+++ /dev/null
-
-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
-
* The seminar meets on Mondays from 4-6, in
the Linguistics building at 10 Washington Place, in room 104 (back of the first floor).
+<font color=red>
+
* One student session will be held every Wednesday from 3-4. The other will
be arranged to fit the schedule of those who'd like to attend but can't
make the Wednesday time. (We first proposed Tuesdays from 11-12, but this
* There is now a [[lambda evaluator]] you can use in your browser (no need to
install any software). It can help you check whether your answer to some of the
-homework questions works correctly.
+homework questions works correctly.
There is also now a [library](/lambda_library) of lambda-calculus
arithmetical and list operations, some relatively advanced.
+ An evaluator with the definitions used for homework 3
+preloaded is available at [[assignment 3 evaluator]].
+
* Henceforth, unless we say otherwise, every homework will be "due" by
Sunday morning after the Monday seminar in which we refer to it.
(Usually we'll post the assignment shortly before the seminar, but don't
what is difficult, what you tried, why what you tried didn't work, and
what you think you need in order to solve the problem.
+</font>
<!--
To play around with a **typed lambda calculus**, which we'll look at later
Topics: Reduction and Convertibility; Combinators; Evaluation Strategies and Normalization; Decidability; Lists and Numbers
-(27 Sept) Lecture notes for [[Week3]]; [[Assignment3]].
+(27 Sept) Lecture notes for [[Week3]]; [[Assignment3]];
+an evaluator with the definitions used for homework 3
+preloaded is available at [[assignment 3 evaluator]].
Topics: Recursion with Fixed Point Combinators