Weight: 300 points. Please hand in via online
dropbox.
- IMPORTANT: Use full recipe (contract, purpose, relevant type-based template, examples) and good style where applicable.
- Remember: Save your work in DrScheme as text, and hand it in as text.
This avoids possible problems with the beta versions of DrScheme
that some of you have downloaded.
- Be careful to do all subparts of a problem, unless otherwise
indicated. Exercises end typographically with a dark square in
the printed version and with a "hand" in the online version.
- The following problem numbers refer to the online version.
The numbering of chapter 18 is
different in at least some printed versions.
-
Book problems:
-
21.2.1 All parts,
21.2.2 Part 3,
21.2.3 Part 3, and Follow recipe for relevant types carefully!
-
22.2.2,
-
23.3.4,
23.3.9,
-
24.0.8,
24.0.9.
- Clarifications:
On 24.0.8, there is no need for drawing boxes. Add a subscript
to each variable name as done in the lecture (to do this in
text, simply add "_n" to each variable name, where n is a number).
Use the same subscript for variables if they all refer to the
same entity. Use the same subscript both for binding and
use occurrences.
-
Challenge question (30 Extra points):
For this question, consider only programs made of
lambda, application, and variables. How many programs
have the following
most general types:
-
X -> X
-
Y -> Y
-
X -> (X -> Y) -> Y
-
(X -> Y) -> (X -> Y)
-
(X -> X) -> (X -> X)
-
X -> (Y -> X)
-
(X -> Y) -> ((X -> Y) -> (X -> (X -> Y)))
-
(X -> Y) -> Y
-
(X -> X) -> X
When you count programs, if two programs do the same thing, count them as one.
If the number of programs is small, list those programs. If it's large, indicate how
large.