Institut for Matematik og Datalogi Odense Universitet April 27, 1995

JFB

DM15 – F95 – Week 27

Lecture, April 24

We covered up through page 77 in the second chapter of Mitchell’s monograph.

Lecture, May 1

We will continue on the second chapter of Mitchell’s monograph.

Lecture, May 8

We will continue on the second chapter of Mitchell’s monograph.

Problems to be discussed in week 19

• Look at the examples on page 66 and 67. What do the different expressions do?

• Do exercises 2.3.1 and 2.3.2 on page 71 of Mitchell.

• Do exercises 2.4.7 and 2.4.8 on page 80 of Mitchell.

• Do exercise 2.4.9 on page 81 of Mitchell.

• Do exercise 2.4.10 on page 82 of Mitchell.

Clarifications of statements in the textbook

• The “brute force” reduction strategy discussed at the bottom of page 81 is not a reduction strategy by the definition given on that page. That definition restricts F to being a one-step reduction strategy. The brute force reduction strategy is a multi-step reduction strategy, in that F (M) = N implies that M → → N, rather than that M → N.

• In the proof of Proposition 2.4.15, it says that the proof of the converse is by induction on the proof. Actually, it doesn’t appear that induction is necessary. This is just a case analysis in which one considers all the possible reductions which could have been applied. However, the proof of Corollary 2.4.16 would be a proof by induction, and one needs to show that the expression being reduced is never a λ-abstraction or a pair.