CSE 526
Spring 2005
Stony Brook
Principles of Programming Languages
Annie Liu
Homework 4
Handout H4
Feb. 15, 2005
Due Feb. 22

Denotational Semantics and Least Fixed Points.

This assignment has two problems, each worth 50% of the grade, respectively. There is a bonus problem at the end, worth an additional 30% 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. 22.

Problem 1. Complete partial orders.

Which ones below are partial orders? and which ones are not? For those that are not, say why.

a. (Pow(S),subset), where Pow(S) is the power set of S, and subset is the subset relation.

b. (int,<=), where int is the set of integers, and <= is the standard comparison relation.

c. (int,<), where int is the set of integers, and < is the standard comparison relation.

d. (nat,|), where nat is the set of natural numbers, and a|b iff a divides b iff b=ka for some natural number k.

e. (S,=), where S is any set, and = is the identity relation.

f. (S,]), where S is any set, and ] is such that a ] b iff b [ a, and if (S,[) is a partial order.

Which ones below are complete partial orders? and which ones are not? For those that are not, say why.

a, b, e above.

g. (int U {infinity}, <=)

h. ([0,1], <=), where [0,1] is the closed continuum between 0 and 1.

i. ([0,1), <=).

Problem 2. Continuous functions.

Winskel's book Exercise 5.12 (ii) on page 73.


Bonus Problem. Least-fixed points.

Winskel's book Exercise 4.13 on page 54. In particular, its last sentence is clarified as follows.

  • "given any set A, there is a least fixed point of Rbar that includes A"
    i.e., given any set A, there is a fixed point, say called X, of Rbar such that (1) X includes A, and (2) X is included in any fixed point of Rhar that includes A.

  • "this property can fail for monotonic operations"
    i.e., if an operator is monotone (only, but not increasing), then given any set A, there might not be a least fixed point of the operator that includes A.