Foundations of Computer Science
Fall 2007

For today you should have:

1) finished the symbolic differentiator

2) done the "Scheme challenges" in notes04

3) brought hardcopies of your solutions to (1) and (2)

4) read from Sipser and answered the questions in notes04


For next time you should:

1) read from Sipser and answer the questions below

2) read the Wikipedia page on the lambda calculus

3) work on the lambda calculus exercises below

4) prepare for a quiz Thursday

Solutions
---------

Here are my solutions to the Scheme challenges from notes04.
Understanding them will be helpful for our journey to the
next level of heck.


(define incr
   (lambda (x) (+ 1 x))) 

(define (repeatedly f n)
  (if (= n 1) f
      (lambda (x) (f ((repeatedly f (- n 1)) x)))))

(repeatedly incr 3)

((repeatedly incr 3) 6)

((repeatedly (lambda (x) (* x x)) 3) 2)
   
((repeatedly (repeatedly incr 4) 5) 200)

(define (repeatedly-until f g)
  (define (iter f g x)
    (if (g x) x
        (iter f g (f x))))
  (lambda (x) (iter f g x)))

(define divisible-by-10
  (lambda (x) (= (remainder x 10) 0)))

(repeatedly-until incr divisible-by-10)

((repeatedly-until incr divisible-by-10) 346)



Currying
--------

Functions of more than one argument are syntactic sugar;
you can express any function as a nested sequence of functions
with one argument each.

This way of writing functions is called currying ("Wikipedia
currying" for more details; disambiguation may be required).

For example, here is a version of 'add that takes x and returns
a function that takes y and returns the sum.

(define add
  (lambda (x)
    (lambda (y)
      (+ x y))))

To invoke it, you need an extra pair of parentheses:

((add 3) 4)

The advantage of this style is that you can evaluate a function
with fewer arguments:

(add 3)

The result is a function that is waiting for the remaining arguments.

This process is called "partial application".


The lambda calculus
-------------------

First, some lambda calisthenics.  What is the value of the
following expressions:

a) L x. x

b) L y. y

c) (L x. x x) L y. y

d) L x. f x

e) (L x y. x) (L x. x x) L y. y

f) (L x y. y x) (L y. y) L y. y

g) (L x. x x) (L x. x x) 

h) (L x. x x x) (L x. x x x) 



Next, we'll write functions in Scheme that evaluate
lambda calculus expressions:

1) Read the section of the Wikipedia page on Logic and Predicates.
Then translate the expressions for TRUE, FALSE and NOT into Scheme.

To get you started, here's TRUE written in the style I recommend:

(define TRUE
  (lambda (x)
    (lambda (y)
      x)))

Notice two things

a) I am using the lambda form of function definition, not the fancy
   syntactic sugary form.

b) I am writing a function of two parameters as a function of one
   parameter that returns a function of one parameter.
   (See currying, above).


Now you write FALSE and NOT.  If you get it right, then

(NOT TRUE)     should yield FALSE, and
(NOT FALSE)    should yield TRUE.


2) Now write AND, and try

((AND TRUE) FALSE)
((AND TRUE) TRUE)

Chances are, you'll get procedures as return values, but Scheme
might not recognize them as FALSE and TRUE.

The following function might help:

; boolean: take a boolean and return the
; canonical true or false value
(define boolean
  (lambda (p) ((p TRUE) FALSE)))


But don't go on until you understand what it is doing.

Really.


3) Ok, now write OR and test it with

(boolean ((OR TRUE) FALSE))
(boolean ((OR FALSE) FALSE))


4) And then write IFTHENELSE and test it with


(((IFTHENELSE TRUE) TRUE) FALSE)
(((IFTHENELSE FALSE) TRUE) FALSE)


But be forewarned that the natural Scheme implementation of
IFTHENELSE is a "greedy" version that evaluates both branches.

This will turn out to be a problem later.


5) Write definitions for ZERO and SUCC, and then compute

(define ONE (SUCC ZERO))


6) Translate ISZERO and confirm that (ISZERO ZERO) is TRUE
   and (ISZERO ONE) is FALSE.


7) Now compute

(define TWO (SUCC ONE))

The result is a procedure, but we have the same
problem we had with booleans: it is not easy to see which
number is represented by a given Church numeral.

Write a function called 'integer that takes a Church numeral
and returns the corresponding Scheme number.

Then run

(integer ZERO)
(integer ONE)
(integer TWO)

And see if you get the right thing.

Hint: if you think about how ISZERO works, that might give 
you an idea.



8) Translate PLUS and compute

(define THREE ((PLUS ONE) TWO))
(integer THREE)


9) Translate MULT and compute

(define SIX ((MULT TWO) THREE))
(integer SIX)


9a) If you are having fun, translate the other form of MULT.


10) Translate PRED and compute

(define FIVE (PRED SIX))
(integer FIVE)


10a) If you are having fun, translate the other form of PRED.


11) Translate CONS, CAR and CDR, then test

(define PAIR ((CONS ONE) TWO))
(integer (CAR PAIR))
(integer (CDR PAIR))

Note: take some time to think about how these work.  It might
help to know that the parameters of CONS stand for first, second
and boolean.  Also, think about what the boolean values are; that
is, what do they do?

Question: when you build a pair, where (ultimately) are the
elements of the pair stored?


12) Translate NIL (which represents an empty pair) and NULL?
(which is a boolean that returns TRUE for NIL and FALSE for
any other PAIR).

(NULL? NIL)     should return TRUE
(NULL? PAIR)    should return FALSE


13) Read the section about recursion and then stop translating
and read this page:

http://www.ececs.uc.edu/~franco/C511/html/Scheme/ycomb.html


We'll try to implement this next time, but first we have to
solve the greedy IFTHENELSE problem.


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

Sipser, pages 31 - 47

1) Can you think of a simple, familiar system that can be modeled
with a finite state machine?  Draw a state transition diagram for
the system.




2) What is the meaning of \delta: Q \cross \Sigma -> Q




3) In what state does M1 end with input string 00110?




4) In what state does M2 end with input string 00110?




5) What is the definition of a regular language?




6) What steps and techniques does Sipser recommend for designing 
   a finite automata?




7) Why can't you "rewind the input tape" to simulate two FSMs?




8) What does it mean to say that the set of regular languages
is closed under union?




9) What kind of proof is used to prove that regular languages
are closed under union?




You can stop reading on page 47 before Section 1.2.


9) Do exercise 1.4 on page 83, parts (a) and (b), and read
the rest to convince yourself that you could do them if
they showed up on a quiz or something.