CSE 526
Spring 2005
Stony Brook
Principles of Programming Languages
Annie Liu
Homework 8
Handout H8
Mar. 15, 2005
Due Mar. 29

Higher-Order Functions and Polymorphic Type Inference.

This assignment has four problems, each worth 25% of the grade. There is a bonus problem at the end, worth an additional 10% of the grade (Note: it is discussed in class and is not harder than other problems; it is only meant to give you extra points if you do it). The assignment is due before class time on Tuesday Mar. 29; since there will be no class that day, please hand in your assignment to Jin, the TA, before that time.

Problem 1. Higher-order functions.

Winskel's book Exercise 11.3 on page 188.

Problem 2. Type inference by generating and solving constraints.

Schwartzbach's lecture notes Exercise 4.7 on page 10.

Problem 3. Curry-Howard isomorphism.

Schwartzbach's lecture notes Exercise 5.3 on page 11.

Problem 4. Polymorphic type system.

Schwartzbach's lecture notes Exercise 6.2 on page 15, but do the first half only.

Bonus Problem. Lazy evaluation.

Write a program, in our higher-order functional language with lazy semantics, that generates the infinite data structure <0,<2,<4,<6,...>>>>.