CS 319 - The Lambda Calculus
Assignment 4, Winter 2000
Due Monday, 14 February

1. Define a natural version of sharing in the lambda calculus, where residuals are initially shared, and portions of a term are copied only when it appears to be necessary. Show that there is no effective optimal strategy for beta reduction in this version of the lambda calculus with sharing.
2. Give an example where optimal shared reduction in the combinator calculus does not correspond to optimal shared reduction in the lambda calculus.