EECS 762

Programming Language Foundation I


Homework 2

The original Y-Combinator developed by Haskell Curry has a different form that the call-by-value form we learned in class. Specifically, his Y-Combinator has this form:

This is often called a fixed point because for any function \(F\):

  1. Using pure beta reduction (not call-by-value) show that this true. Specifically, do a derivation that shows \(Y\; F = F(Y\; F)\)
  2. Explain or show why this new Y will not work with call-by-value semantics for beta reduction.
  3. Use this new Y combinator to calculate 3!. Use pure beta reduction and not call-by-value semantics.
  4. Exercise 5.2.1
  5. Exercise 5.2.4
  6. Exercise 5.2.7