Programming Languages, Fall 2013
HW4 - Lambda Calculus I
Due electronically on Blackboard on Monday Sep 30, 11:59pm.

Expected Amount of Work for an average student: 4-6 hours.

Textbooks for References:
[1] TAPL, Chap. 5

1. Finish and extend part 2 of the Quiz:

data Ast = TRUE
         | FALSE
         | IFTHENELSE Ast Ast Ast
           deriving (Show)

implement three functions: 
a) eval (for one-step evaluation)
b) eval2 (for multi-step evaluation)
c) eval3 (for big-step evaluation)

Note that all three functions have type Ast -> Ast.

Show a few testcases (by continuing calling eval on some term you'll eventually get the same answer 
as eval2 and eval3).

2. The "and" and "or" functions seem to lazy, i.e., for 
      or tru t 
   it looks like we don't need to evaluate expression t.
   Is that true? Work out the following in the call-by-value evaluation:
      
      or (not fls) (fst (pair fls fls))
   =  ...
   =  ...
   ...

3. Redefine the one-step evaluation to be call-by-name (i.e., lazy) to
   simulate Haskell. Then redo the above example.

4. Define the big-step evaluation for lambda calculus. 
   Draw the derivation tree for the above example.

5. What does \x -> \x -> x + 1 do? (is it a valid lambda calculus expression?)

6. For the two successor functions (slide 27-a). Work out (scc c3) annd (scc2 c3).
   Explain the intuition behind scc and scc2.

7. Work out (plus c3 c2). Explain the intuition behind plus.

8. Work out (times c3 c2). Explain the intuition behind times.

9. Redefine times without using plus. Explain the new intuition.

10. Define two versions of the power function, one with and one without times.
    Work out (power c3 c2). Explain the intuitions behind each definition.

Debriefing (required!): --------------------------

1. Approximately how many hours did you spend on this assignment?
2. Would you rate it as easy, moderate, or difficult?
3. Did you work on it mostly alone, or mostly with other people?
4. How deeply do you feel you understand the material it covers (0%–100%)? 
5. Any other comments?

This section is intended to help us calibrate the homework assignments. 
Your answers to this section will *not* affect your grade; however, skipping it
will certainly do.