<OL start=16>
-<LI>What would be the result of evaluating (see [[Assignment 2 hint 1]] for a hint):
+<LI>What would be the result of evaluating (see [[hints/Assignment 2 hint]] for a hint):
LIST make-list empty
Assignment 3
------------
-Once again, the lambda evaluator will make working through this
-assignment much faster and more secure.
+Erratum corrected 11PM Sun 3 Oct: the following line
-##Writing recursive functions on version 1 style lists##
+ let tb = (make_list t12 (make_list t3 empty)) in
-Recall that version 1 style lists are constructed like this:
+originally read
-<pre>
-; booleans
-let true = \x y. x in
-let false = \x y. y in
-let and = \l r. l (r true false) false in
-
-; version 1 lists
-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
-
-; a list of numbers to experiment on
-let mylist = makeList 1 (makeList 2 (makeList 3 nil)) in
-
-; a fixed-point combinator for defining recursive functions
-let Y = \f. (\h. f (h h)) (\h. f (h h)) in
-
-; church numerals
-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 predecessor = \n. length (tail (n (\p. makeList meh p) nil)) in
-let leq = ; (leq m n) will be true iff m is less than or equal to n
- Y (\leq m n. isZero m true (isZero n false (leq (predecessor m)(predecessor n)))) in
-let eq = \m n. and (leq m n)(leq n m) in
-
-eq 3 3
-</pre>
+ let tb = (make_list t12 t3) in
+
+This has been corrected below, and in the preloaded evaluator for
+working on assignment 3, available here: [[assignment 3 evaluator]].
+
+<hr>
+
+Once again, the lambda evaluator will make working through this
+assignment much faster and more secure.
+
+#Writing recursive functions on version 1 style lists#
+
+Recall that version 1 style lists are constructed like this (see
+[[lists and numbers]]):
+
+ ; booleans
+ let true = \x y. x in
+ let false = \x y. y in
+ let and = \l r. l (r true false) false in
+
+ let make_pair = \f s g. g f s in
+ let get_fst = true in
+ let get_snd = false in
+ let empty = make_pair true junk in
+ let isempty = \x. x get_fst in
+ let make_list = \h t. make_pair false (make_pair h t) in
+ let head = \l. isempty l err (l get_snd get_fst) in
+ let tail = \l. isempty l err (l get_snd get_snd) in
+
+ ; a list of numbers to experiment on
+ let mylist = make_list 1 (make_list 2 (make_list 3 empty)) in
+
+ ; church numerals
+ let iszero = \n. n (\x. false) true in
+ let succ = \n s z. s (n s z) in
+ let add = \l r. l succ r in
+ let mul = \m n s. m (n s) in
+ let pred = (\shift n. n shift (make\_pair 0 0) get\_snd) (\p. p (\x y. make\_pair (succ x) x)) in
+ let leq = \m n. iszero(n pred m) in
+ let eq = \m n. and (leq m n)(leq n m) in
+
+ ; a fixed-point combinator for defining recursive functions
+ let Y = \f. (\h. f (h h)) (\h. f (h h)) in
+ let length = Y (\length l. isempty l 0 (succ (length (tail l)))) in
+ let fold = Y (\f l g z. isempty l z (g (head l)(f (tail l) g z))) in
+
+ eq 2 2 yes no
Then `length mylist` evaluates to 3.
-1. Warm-up: What does `head (tail (tail mylist))` evaluate to?
+1. What does `head (tail (tail mylist))` evaluate to?
2. Using the `length` function as a model, and using the predecessor
function, write a function that computes factorials. (Recall that n!,
the factorial of n, is n times the factorial of n-1.)
-Warning: my browser isn't able to compute factorials of numbers
-greater than 2 (it does't provide enough resources for the JavaScript
-interpreter; web pages are not supposed to be that computationally
-intensive).
-
+ Warning: it takes a long time for my browser to compute factorials larger than 4!
-3. Write a function `listLenEq` that returns true just in case two lists have the
-same length. That is,
+3. (Easy) Write a function `equal_length` that returns true just in case
+two lists have the same length. That is,
- listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true
+ equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true
- listLenEq mylist (makeList meh (makeList meh nil))) ~~> false
+ equal_length mylist (make_list junk (make_list junk empty))) ~~> false
-4. Now write the same function, but don't use the length function (hint: use `leq` as a model).
-##Trees##
+4. (Still easy) Now write the same function, but don't use the length
+function.
-Since we'll be working with linguistic objects, let's approximate
-trees as follows: a tree is a version 1 list
-a Church number is a tree, and
-if A and B are trees, then (make-pair A B) is a tree.
+5. In assignment 2, we discovered that version 3-type lists (the ones
+that
+work like Church numerals) made it much easier to define operations
+like `map` and `filter`. But now that we have recursion in our
+toolbox,
+reasonable map and filter functions for version 1 lists are within our
+reach. Give definitions for `map` and a `filter` for verson 1 type
+lists.
+#Computing with trees#
+Linguists analyze natural language expressions into trees.
+We'll need trees in future weeks, and tree structures provide good
+opportunities for learning how to write recursive functions.
+Making use of the resources we have at the moment, we can approximate
+trees as follows: instead of words, we'll use Church numerals.
+Then a tree will be a (version 1 type) list in which each element is
+itself a tree. For simplicity, we'll adopt the convention that
+a tree of length 1 must contain a number as its only element.
-[The following should be correct, but won't run in my browser:
-
-let factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in
+Then we have the following representations:
<pre>
-let reverse =
- Y (\rev l. isNil l nil
- (isNil (tail l) l
- (makeList (head (rev (tail l)))
- (rev (makeList (head l)
- (rev (tail (rev (tail l))))))))) in
-
-reverse (makeList 1 (makeList 2 (makeList 3 nil)))
+ (a) (b) (c)
+ .
+ /|\ /\ /\
+ / | \ /\ 3 1 /\
+ 1 2 3 1 2 2 3
+
+[[1];[2];[3]] [[[1];[2]];[3]] [[1];[[2];[3]]]
</pre>
-It may require more resources than my browser is willing to devote to
-JavaScript.]
+Limitations of this scheme include the following: there is no easy way
+to label a constituent with a syntactic category (S or NP or VP,
+etc.), and there is no way to represent a tree in which a mother has a
+single daughter.
+
+When processing a tree, you can test for whether the tree contains
+only a numeral (in which case the tree is leaf node) by testing for
+whether the length of the list is less than or equal to 1. This will
+be your base case for your recursive functions that operate on these
+trees.
+
+<OL start=6>
+<LI>Write a function that sums the values at the leaves in a tree.
+
+Expected behavior:
+
+ let t1 = (make_list 1 empty) in
+ let t2 = (make_list 2 empty) in
+ let t3 = (make_list 3 empty) in
+ let t12 = (make_list t1 (make_list t2 empty)) in
+ let t23 = (make_list t2 (make_list t3 empty)) in
+ let ta = (make_list t1 t23) in
+ let tb = (make_list t12 (make_list t3 empty)) in
+ let tc = (make_list t1 (make_list t23 empty)) in
+
+ sum-leaves t1 ~~> 1
+ sum-leaves t2 ~~> 2
+ sum-leaves t3 ~~> 3
+ sum-leaves t12 ~~> 3
+ sum-leaves t23 ~~> 5
+ sum-leaves ta ~~> 6
+ sum-leaves tb ~~> 6
+ sum-leaves tc ~~> 6
+
+
+<LI>Write a function that counts the number of leaves.
+
+</OL>
var res = left, x;
while (stack.length) {
x = stack.shift();
- res = new Lambda_app(res, x.eval_loop([], eta));
+ // res = new Lambda_app(res, x.eval_loop([], eta));
+ res = new Lambda_app(res, reduce(x, eta, false));
}
return res;
}
- return unwind(this, stack);
+ // return unwind(this, stack);
+ // trampoline to, args
+ return [null, unwind(this, stack)];
};
this.eval_cbv = function (aggressive) {
return this;
this.eval_loop = function (stack, eta) {
var new_stack = stack.slice(0);
new_stack.unshift(this.right);
- return this.left.eval_loop(new_stack, eta);
+ // return this.left.eval_loop(new_stack, eta);
+ // trampoline to, args
+ return [this.left, new_stack, eta];
};
this.eval_cbv = function (aggressive) {
var left = this.left.eval_cbv(aggressive);
};
this.eval_loop = function (stack, eta) {
if (stack.length === 0) {
- var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
- if (eta) {
- return term.check_eta();
- } else {
- return term;
- }
+ // var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
+ var term = new Lambda_lam(this.bound, reduce(this.body, eta, false));
+ if (eta) {
+ return [null, term.check_eta()];
+ } else {
+ return [null, term];
+ }
} else {
var x = stack[0];
var xs = stack.slice(1);
- return subst(this.bound, x, this.body).eval_loop(xs, eta);
+ // return subst(this.bound, x, this.body).eval_loop(xs, eta);
+ // trampoline to, args
+ return [subst(this.bound, x, this.body), xs, eta];
}
};
this.eval_cbv = function (aggressive) {
if (cbv) {
return expr.eval_cbv(cbv > 1);
} else {
- return expr.eval_loop([], eta);
+ // return expr.eval_loop([], eta);
+ var to_eval = expr, res = [[], eta];
+ while (to_eval !== null) {
+ res = to_eval.eval_loop.apply(to_eval, res);
+ to_eval = res.shift();
+ }
+ return res[0];
}
}
}
} catch (e) {}
-/*
-let true = K in
-let false = \x y. y in
-let and = \l r. l r false in
-let or = \l r. l true r in
-let pair = \u v f. f u v in
-let triple = \u v w f. f u v w in
-let succ = \n s z. s (n s z) in
-let pred = \n s z. n (\u v. v (u s)) (K z) I in
-let ifzero = \n. n (\u v. v (u succ)) (K 0) (\n withp whenz. withp n) in
-let add = \m n. n succ m in
-let mul = \m n. n (\z. add m z) 0 in
-let mul = \m n s. m (n s) in
-let sub = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
-let min = \m n. sub m (sub m n) in
-let max = \m n. add n (sub m n) in
-let lt = (\mzero msucc mtail. \n m. n mtail (m msucc mzero) true (\x. true) false) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
-let leq = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true (\x. false) true) (pair 0 I) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
-let eq = (\mzero msucc mtail. \m n. n mtail (m msucc mzero) true (\x. false) true) (pair 0 (K (pair 1 I))) (\d. d (\a b. pair (succ a) (K d))) (\d. d false d) in
-let divmod = (\mzero msucc mtail. \n divisor.
- (\dhead. n (mtail dhead) (\sel. dhead (sel 0 0)))
- (divisor msucc mzero (\a b c. c x))
- (\d m a b c. pair d m) )
- (triple succ (K 0) I)
- (\d. triple I succ (K d))
- (\dhead d. d (\dz mz df mf drest sel. drest dhead (sel (df dz) (mf mz)))) in
-let div = \n d. divmod n d true in
-let mod = \n d. divmod n d false in
-let Y = \f. (\y. f(y y)) (\y. f(y y)) in
-let Z = (\u f. f(u u f)) (\u f. f(u u f)) in
-let fact = \y. y (\f n. ifzero n (\p. mul n (f p)) 1) in
-fact Z 3
-*/
+// Chris's original
+
// // Basic data structure, essentially a LISP/Scheme-like cons
// // pre-terminal nodes are expected to be of the form new cons(null, "string")
// function cons(car, cdr) {
for (;;) {
c = this.charAt(i);
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
- (c >= '0' && c <= '9') || c === '_' || c === '-') {
+ (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '/') {
str += c;
i += 1;
} else if (c === '?' || c === '!') {
// should only be terminal
str += c;
i += 1;
+ c = this.charAt(i);
// make sure next character is not an identifier
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
- (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '?' || c === '!') {
+ (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '/' || c === '?' || c === '!') {
str += c;
i += 1;
make('name', str).error("Bad identifier");
## Announcements ##
-The seminar meets on Mondays from 4-6, in
+* The seminar meets on Mondays from 4-6, in
the Linguistics building at 10 Washington Place, in room 104 (back of the first floor).
-Student sessions will be held on Tuesdays from 11-12 and Wednesdays from 3-4. (You only need attend one session.) You should see these sessions as opportunities to clear up lingering issues from material we've discussed, and help get a better footing for what we'll be doing the next week. It would be smart to make a serious start on that week's homework, for instance, before the session.
-
-We've sent around an email to those who left their email addresses on the roster we passed around. But it's clear that the roster didn't make its way to everyone. So if you're not receiving our seminar emails, please email <mailto:jim.pryor@nyu.edu> with your email address, and if you're a student, say whether you expect to audit or take the class for credit.
-
-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.
+<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
+time turns out not to be so helpful.) If you're one of the students who
+wants to meet for Q&A at some other time in the week, let us know.
+
+ You should see the student sessions as opportunities to clear up lingering
+issues from material we've discussed, and help get a better footing for what
+we'll be doing the next week. It would be smart to make a serious start on that
+week's homework, for instance, before the session.
+
+* 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.
+
+ 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
+rely on this.) However, for every assignment there will be a "grace
+period" of one further week for you to continue working on it if you
+have trouble and aren't able to complete the assignment to your
+satisfaction by the due date. You shouldn't hesitate to talk to us---or
+each other!---about the assignments when you do have trouble. We don't
+mind so much if you come across answers to the assignment when browsing
+the web, or the Little Schemer book, or anywhere. So long as you can
+reason yourself through the solutions and experience for yourself the
+insights they embody.
+
+ We reserve the privilege to ruthlessly require you to
+explain your solutions in conversations at any point, in section or in
+class.
+
+ You should always *aim* to complete the assignments by the "due" date,
+as this will fit best with the progress of the seminar. Let's take
+assignment 3 to be "due" on Sunday Oct 3 (the date of this
+announcement), but as we announced last week in seminar, you can take up
+until this coming Sunday to complete it. If you need to. Try to complete
+it, and get assistance completing it if you need it, sooner.
+
+* We'll shortly be posting another assignment, assignment 4, which will be
+"due" on the Sunday before our next seminar. That is, on Sunday Oct 17.
+(There's no seminar on Monday Oct 11.)
+
+ The assignments will tend to be quite challenging. Again, you should by
+all means talk amongst yourselves, and to us, about strategies and
+questions that come up when working through them.
+
+ We will not always be able to predict accurately which problems are
+easy and which are hard. If we misjudge, and choose a problem that is
+too hard for you to complete to your own satisfaction, it is still
+very much worthwhile (and very much appreciated) if you would explain
+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
(13 Sept) Lecture notes for [[Week1]]; [[Assignment1]].
-Topics: Applications; Basics of Lambda Calculus; Comparing Different Languages
+> Topics: [[Applications]], including [[Damn]]; Basics of Lambda Calculus; Comparing Different Languages
(20 Sept) Lecture notes for [[Week2]]; [[Assignment2]].
-Topics: Reduction and Convertibility; Combinators; Evaluation Strategies and Normalization; Decidability; Lists and Numbers
+> Topics: Reduction and Convertibility; Combinators; Evaluation Strategies and Normalization; Decidability; [[Lists and Numbers]]
-(27 Sept) ...(Notes to come)
-Topics: Recursion with Fixed Point Combinators
+(27 Sept) Lecture notes for [[Week3]]; [[Assignment3]];
+an evaluator with the definitions used for homework 3
+preloaded is available at [[assignment 3 evaluator]].
-<!-- Introducing the notion of a "continuation", which technique we'll now already have used a few times
--->
+> Topics: [[Evaluation Order]]; Recursion with Fixed Point Combinators
+
+(4 Oct) Lecture notes for [[Week4]]; [[Assignment4]].
+
+> Topics: More on Fixed Points; Sets; Aborting List Traversals; [[Implementing Trees]]
+
+
+(18 Oct) Lecture notes for Week 5
+
+> Topics: Types, Polymorphism
[[Upcoming topics]]
+[Advanced Lambda Calculus Topics](/advanced_lambda)
+
##[[Offsite Reading]]##
This wiki is powered by [[ikiwiki]].
-[[Test]]
+[[!toc]]
+
Building Lists
==============
* [Penn lambda calculator](http://www.ling.upenn.edu/lambda/) Pedagogical software developed by Lucas Champollion, Josh Tauberer and Maribel Romero.<p>
<!-- Haskell Curry had ideas that he felt were validated upon reading a 1924 paper by M. Schönfinkel "Uber die Bausteine der mathematischen Logik" which used combinators in a similar way to his own ideas. Haskell then wrote "An analysis of logical substitution" which appeared in the American Journal of Mathematics in 1929. -->
+
* [[!wikipedia Moses Schönfinkel]]
* [[!wikipedia Haskell Curry]]
* [[!wikipedia Alonzo Church]]<p>
* [To Dissect a Mockingbird](http://dkeenan.com/Lambda/index.htm)
* [Combinator Birds](http://www.angelfire.com/tx4/cus/combinator/birds.html)
-* [Les deux combinateurs et la totalite](http://www.paulbraffort.net/j_et_i/j_et_i.html) by Paul Braffort.
-
+* [Les deux combinateurs et la totalite](http://www.paulbraffort.net/j_et_i/j_et_i.html) by Paul Braffort.
## Evaluation Order ##
* [Y Combinator for Dysfunctional Non-Schemers](http://rayfd.wordpress.com/2007/05/06/y-combinator-for-dysfunctional-non-schemers/)
* [The Y Combinator](http://www.ece.uc.edu/~franco/C511/html/Scheme/ycomb.html)
* [The Y Combinator](http://dangermouse.brynmawr.edu/cs245/ycomb_jim.html) derives the applicative-order Y-combinator from scratch, in Scheme. This derivation is similar in flavor to the derivation found in The Little Schemer, but uses a slightly different starting approach...
-
+* [The church of the least fixed point, by Sans Pareil](http://www.springerlink.com/content/n4t2v573m58g2755/)
## Types ##
+[[!toc]]
+
+##More on evaluation strategies##
+
+Here are notes on [[evaluation order]] that make the choice of which
+lambda to reduce next the selection of a route through a network of
+links.
+
+
##Computing the length of a list##
How could we compute the length of a list? Without worrying yet about what lambda-calculus implementation we're using for the list, the basic idea would be to define this recursively:
##Fixed-point Combinators Are a Bit Intoxicating##
-
+
There's a tendency for people to say "Y-combinator" to refer to fixed-point combinators generally. We'll probably fall into that usage ourselves. Speaking correctly, though, the Y-combinator is only one of many fixed-point combinators.
that is similar, but expressed in terms of non-well-founded sets
rather than recursive functions.
-HOWEVER, you should be cautious about feeling too comfortable with
+##However...##
+
+You should be cautious about feeling too comfortable with
these results. Thinking again of the truth-teller paradox, yes,
<code>Ω</code> is *a* fixed point for `I`, and perhaps it has
some a privileged status among all the fixed points for `I`, being the