author Chris Barker Sun, 17 Oct 2010 16:09:58 +0000 (12:09 -0400) committer Chris Barker Sun, 17 Oct 2010 16:09:58 +0000 (12:09 -0400)
 assignment2.mdwn patch | blob | history assignment3.mdwn patch | blob | history code/lambda.js patch | blob | history code/tokens.js patch | blob | history index.mdwn patch | blob | history lists_and_numbers.mdwn patch | blob | history offsite_reading.mdwn patch | blob | history week3.mdwn patch | blob | history

index 5d75a85..3e93256 100644 (file)
@@ -107,7 +107,7 @@ For these exercises, assume that LIST is the result of evaluating:

<OL start=16>
-<LI>What would be the result of evaluating (see [[hints/Assignment 2 hint]] for a hint):
+<LI>What would be the result of evaluating (see [[Assignment 2 hint 1]] for a hint):

LIST make-list empty

index e240b73..f93afd6 100644 (file)
Assignment 3
------------

-Erratum corrected 11PM Sun 3 Oct: the following line
-
-       let tb = (make_list t12 (make_list t3 empty)) in
-
-
-       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
+##Writing recursive functions on version 1 style lists##
+
+Recall that version 1 style lists are constructed like this:
+
+<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>

Then length mylist evaluates to 3.

-1. What does head (tail (tail mylist)) evaluate to?
+1. Warm-up: 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: it takes a long time for my browser to compute factorials larger than 4!
+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).

-3. (Easy) Write a function equal_length that returns true just in case
-two lists have the same length.  That is,

-               equal_length mylist (make_list junk (make_list junk (make_list junk empty))) ~~> true
+3. Write a function listLenEq that returns true just in case two lists have the
+same length.  That is,

-               equal_length mylist (make_list junk (make_list junk empty))) ~~> false
+     listLenEq mylist (makeList meh (makeList meh (makeList meh nil))) ~~> true

+     listLenEq mylist (makeList meh (makeList meh nil))) ~~> false

-4. (Still easy) Now write the same function, but don't use the length
-function.
+4. Now write the same function, but don't use the length function (hint: use leq as a model).

-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.
+##Trees##

-#Computing with trees#
+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.

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

-Then we have the following representations:

-<pre>
-   (a)           (b)             (c)
-    .
-   /|\            /\              /\
-  / | \          /\ 3            1 /\
-  1 2  3        1  2               2 3
+[The following should be correct, but won't run in my browser:

-[;;]  [[;];]   [;[;]]
-</pre>
-
-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 factorial = Y (\fac n. isZero n 1 (mult n (fac (predecessor n)))) in

-       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.
+<pre>
+let reverse =
+  Y (\rev l. isNil l nil
+                   (isNil (tail l) l
+                          (makeList (head (rev (tail l)))
+                                                   (rev (tail (rev (tail l))))))))) in
+
+reverse (makeList 1 (makeList 2 (makeList 3 nil)))
+</pre>

-</OL>
+It may require more resources than my browser is willing to devote to
+JavaScript.]

index 0eea4c9..609cce0 100644 (file)
@@ -207,14 +207,11 @@ function Lambda_var(variable) {
var res = left, x;
while (stack.length) {
x = stack.shift();
-                               // res = new Lambda_app(res, x.eval_loop([], eta));
-                               res = new Lambda_app(res, reduce(x, eta, false));
+                               res = new Lambda_app(res, x.eval_loop([], eta));
}
return res;
}
-        // return unwind(this, stack);
-               // trampoline to, args
-               return [null, unwind(this, stack)];
+        return unwind(this, stack);
};
this.eval_cbv = function (aggressive) {
return this;
@@ -264,9 +261,7 @@ function Lambda_app(left, right) {
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);
-               // trampoline to, args
-               return [this.left, new_stack, eta];
+        return this.left.eval_loop(new_stack, eta);
};
this.eval_cbv = function (aggressive) {
var left = this.left.eval_cbv(aggressive);
@@ -360,19 +355,16 @@ function Lambda_lam(variable, body) {
};
this.eval_loop = function (stack, eta) {
if (stack.length === 0) {
-                       // 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];
-                       }
+            var term = new Lambda_lam(this.bound, this.body.eval_loop([], eta));
+            if (eta) {
+                return term.check_eta();
+            } else {
+                return term;
+            }
} else {
var x = stack;
var xs = stack.slice(1);
-            // return subst(this.bound, x, this.body).eval_loop(xs, eta);
-                       // trampoline to, args
-                       return [subst(this.bound, x, this.body), xs, eta];
+            return subst(this.bound, x, this.body).eval_loop(xs, eta);
}
};
this.eval_cbv = function (aggressive) {
@@ -422,13 +414,7 @@ function reduce(expr, eta, cbv) {
if (cbv) {
return expr.eval_cbv(cbv > 1);
} else {
-        // 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;
+        return expr.eval_loop([], eta);
}
}

@@ -450,11 +436,42 @@ try {
}
} 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.
+              (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) {
index 921040d..53639a8 100644 (file)
@@ -81,17 +81,16 @@ String.prototype.tokens = function (prefix, suffix) {
for (;;) {
c = this.charAt(i);
if ((c >= 'a' && c <= 'z') || (c >= 'A' && c <= 'Z') ||
-                        (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '/') {
+                        (c >= '0' && c <= '9') || 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 === '!') {
+                                               (c >= '0' && c <= '9') || c === '_' || c === '-' || c === '?' || c === '!') {
str += c;
i += 1;
index 66f40b6..28fc8c4 100644 (file)
@@ -7,72 +7,15 @@ This course will be co-taught by [Chris Barker](http://homepages.nyu.edu/~cb125/

## 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).

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

<!--
To play around with a **typed lambda calculus**, which we'll look at later
@@ -87,31 +30,20 @@ what you think you need in order to solve the problem.

(13 Sept) Lecture notes for [[Week1]]; [[Assignment1]].

->      Topics: [[Applications]], including [[Damn]]; Basics of Lambda Calculus; Comparing Different Languages
+Topics: Applications; 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]]
-
-(27 Sept) Lecture notes for [[Week3]];  [[Assignment3]];
-an evaluator with the definitions used for homework 3
-preloaded is available at [[assignment 3 evaluator]].
-
->      Topics: [[Evaluation Order]]; Recursion with Fixed Point Combinators
-
-(4 Oct) Lecture notes for [[Week4]]; [[Assignment4]].
+Topics: Reduction and Convertibility; Combinators; Evaluation Strategies and Normalization; Decidability; Lists and Numbers

->      Topics: More on Fixed Points; Sets; Aborting List Traversals; [[Implementing Trees]]
+(27 Sept) ...(Notes to come)
+Topics: Recursion with Fixed Point Combinators

-
-(18 Oct) Lecture notes for Week 5
-
->      Topics: Types, Polymorphism
+<!-- Introducing the notion of a "continuation", which technique we'll now already have used a few times
+-->

[[Upcoming topics]]

-

@@ -294,4 +226,5 @@ All wikis are supposed to have a [[SandBox]], so this one does too.

This wiki is powered by [[ikiwiki]].

+[[Test]]

index 571ed7b..e047312 100644 (file)
@@ -1,5 +1,3 @@
-[[!toc]]
-
Building Lists
==============

index c9f1d7e..d9c7f82 100644 (file)
@@ -52,7 +52,6 @@ get more out of. (Rinse and repeat.)
*      [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 Alonzo Church]]<p>
@@ -67,9 +66,6 @@ get more out of. (Rinse and repeat.)
<http://people.cs.uu.nl/jeroen/article/combinat/combinat.ps>
*      [Chris Barker's Iota and Jot](http://semarch.linguistics.fas.nyu.edu/barker/Iota/)<p>

-*      [To Dissect a Mockingbird](http://dkeenan.com/Lambda/index.htm)
-*      [Combinator Birds](http://www.angelfire.com/tx4/cus/combinator/birds.html)
-
## Evaluation Order ##

*      [[!wikipedia Evaluation strategy]]
@@ -96,7 +92,7 @@ get more out of. (Rinse and repeat.)
*      [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 ##

index 39e472b..f749921 100644 (file)
@@ -1,12 +1,3 @@
-[[!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
-
-
##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:
@@ -424,7 +415,7 @@ to *the tail* of the list we were evaluating its application to at the previous

##Fixed-point Combinators Are a Bit Intoxicating##

-![tatoo](/y-combinator-fixed.jpg)
+![tatoo](/y-combinator.jpg)

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.

@@ -592,9 +583,7 @@ truth and circularity](http://tinyurl.com/2db62bk) for an approach
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>&Omega;</code> is *a* fixed point for I, and perhaps it has
some a privileged status among all the fixed points for I, being the