Foundations of Computer Science
Fall 2007

For today you should have:

1) read from Sipser and answered the questions in notes05

2) read the Wikipedia page on the lambda calculus

2a) read the web page on the Y combinator

3) worked on the lambda calculus exercises in notes05

4) prepare for a quiz


For next time you should:

1) read from Sipser and answer the questions below.

2) finish your translation of the lambda calculus and
   bring a hardcopy of your solution to class on Monday.


Ackermann
---------

Read the Wikipedia page on the Ackermann function.

Type in your solution to quiz02 and compute A(n, n) for n = 1, 2, 3, 4.

See ya!


Lambda calculus
---------------

By the end of notes05, you should have translated the lambda
calculus into Scheme, up to but not including the dreaded

	 Y combinator!

For today you should have read the web page I recommended
about the Y combinator.  You should understand what it is
for and (at least roughly) how it works.


1) Translate the factorial function from the lambda-calculus
   Wikipedia page into Scheme.



2) Notice that in the IFTHENELSE clause, it is necessary
   that we don't evaluate both branches before choosing one.

   One way to implement a non-greedy (also known as "lazy",
   which just goes to show that you can't win) IFTHENELSE
   is to change the interface so that it takes a boolean
   and two functions of no parameters.

   Then it chooses one of the two functions and evaluates it.

   Modify IFTHENELSE in this way and then test it with some
   simple examples.

   Then modify your implementation of factorial to work with
   the new version of IFTHENELSE.



3) Translate the applicative-order Y combinator (from the web 
   page) into Scheme.

   Use the Y combinator to construct the recursive version of
   factorial and then apply it to a Church numeral like SIX.

   Translate the result into an integer, and see what you get!



4) Notice that the applicative order Y combinator from the
   web page is one eta-conversion more abstract than the version
   from the Wikipedia page.

   Convert the simpler version into Scheme and test it with
   your implementation of factorial.  What happens?  Why?




Reading questions
-----------------

Sipser, pages 47-67

Before you read this section, you should skim it to see
what results are developed in this section and why.

1) Why do we have to introduce non-determinism at this point?




2) What is the relationship between the set of languages recognized
   by a DFA and the set of languages recognized by an NFA?




3) What does Theorem 1.39 state, and what technique is used to
   prove it?




4) What is the definition of a regular language?  What effect
   does Corollary 1.40 have on this definition?




5) How is Theorem 1.45 related to Theorem 1.25?  How are their
   proofs related?




6) What is a regular expression?  What is the difference between
   R and L(R)?




7) What does Theorem 1.54 state and what technique is used to
   prove it?




You can stop reading at the top of page 67.  We'll pick up here
next time.