Programming Languages, Fall 2013

Review Questions for Midterm I
(no need to submit anything)

Midterm I will assume good understanding of HW1-5 plus these questions.

1. Given a list of booleans (assuming the first definition of list)
   define "any" which tests if any of the elements are true:

	any (cons fls (cons tru nil)) 

   should be behaviorally equivalent to "tru".
   
   Does your solution work for the second definition of list?

   Define a "map" function that takes a function f and a list l, 
   which maps f onto each element of l:

   	 map not (cons fls (cons tru nil))
	 
   should be behaviorally equivalent to (cons tru (cons fls nil)).

2. Reimplement these on Haskell using Haskell list.

3. Under one-step call-by-name, prove: if t -> t', then FV(t) \supseteq FV(t').

   Under big-step call-by-value, prove: if t => v, then FV(t) \supseteq FV(v).

4. Show that "and" and "or" are behaviorally inequivalent.

   What about (\x. omega) and (\y. (\x. f (x x)) (\x. f (x x))) ?
 
5. Write the evaluation rules for big-step full-beta reduction.

6. Draw all possible derivation trees for (\x.x) ((\x.x) (\z. (\y.y) z)) using 5.

7. (suggested by Liangyue) Why the call-by-name Y-combinator is useless in a call-by-value setting?

8. (suggested by Dezhong) Can you use the second definition of list (pair) to model Church numerals?