CSE 526
Spring 2005
Stony Brook
Principles of Programming Languages
Annie Liu
Homework 3
Handout H3
Feb. 8, 2005
Due Feb. 15

Rules and Proving Properties about Programs and Semantics.

This assignment has three problems, each worth 25%, 25%, and 50% of the grade, respectively. There is a bonus problem at the end, worth an additional 20% of the grade (Note: it 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 on Tuesday Feb. 15.

Problem 1. Rules for evaluation of parallel-or.

Winskel's book Exercise 2.4 on page 18.

Problem 2. Well-founded ordering.

Winskel's book Exercise 3.8 on page 32.

Problem 3. Equivalence of big-step and small-step semantics.

Winskel's book Exercise 4.10 on page 51, excluding the "if" direction mentioned.

Bonus Problem. Proof by contradiction.

Winskel's book Exercise 3.9 on page 33, excluding the comparison mentioned.