Computer Science & Engineering 505
Concepts of Programming Languages
Assignment 4 - Combinators

Due: Nov 3

    1. Using the basic algorithm described by Turner in his paper "A New Implementation Technique for Applicative Languages" (i.e. using only the S, K and I combinators), give the variable-free form of the function:
      square x = x * x
    2. Show the result of applying this expression to 5.
    3. Give the optimized form for square using the additional rules (those for the B and C combinators and the simplification rules)
    4. Show the result of applying the optimized expression to 5.
  1. Write a haiku reflecting on the Haskell programming experience.(See for inspiration.)