Welcome to the CSE526 (Principles of Programming Languages)
home page for Spring 2008.
This page will be the main source of course information throughout
the semester.
Please check this page regularly for new messages.
The newest messages will always appear first.
- Final Exam Scores
- The statistics for the final exam were as follows:
The maximum possible grade on the exam was 75 points.
The maximum score actually achieved was 52 points.
The minimum score actually achieved was 7 points.
The statistics are as follows:
FINAL (whole class ) Valid 8; Mean 28.00; Std. Dev. 15.46
In the above, "Valid" means the number of nonzero scores in the
applicable category.
- Final Exam Time
- Please note: I had conflicting times for the final exam posted
here on the web site. The time for the final exam is set by
the registrar. It is my belief that this time is
Thursday, May 15, 8:00AM. The exam will be held in the regular
classroom.
See here
for what I am using as the authoritative
information regarding the time of the final exam. This seems to be
the only documentation I can locate at this time.
-
OBJECTS Interpreter
- See here if you want
to see the rest of the slides on the
OBJECTS
interpreter that we didn't cover in class.
- Denotational Semantics References:
-
- Optional Exercise: Continuations
- If you want to do an exercise with continuations, I have
placed here an
exercise that I gave last year.
- Midterm Exam Grades
- Grades for the midterm exam are now available. The statistics
were as follows:
The maximum possible grade on the exam was 64 points.
The maximum score actually achieved was 45 points.
The minimum score actually achieved was 19.5 points.
The statistics are as follows:
MIDTERM (whole class ) Valid 9; Mean 26.44; Std. Dev. 8.20
In the above, "Valid" means the number of nonzero scores in the
applicable category.
For what it's worth, statistics on the homework grades I have so
far are as follows:
HW1 (whole class ) Valid 9; Mean 9.67; Std. Dev. 3.46
- Midterm Problem 3
-
The problem asked you to exhibit a lambda-calculus term F
that satisfies:
FN cnv \z.z N(F(\f.\x.f(N f x)))
If you understood the use of the fixed-point combinator Y,
this is just plugging and chugging:
F = Y(\F.\N.\z.z N(F(\f.\x.f(N f x))))
The problem then asked you to determine the normal form of
F Z K* K* K* K* K* K, where Z = \f.\x.x,
K = \x.\y.x, and K* = \x.\y.y.
Well, here is the full term written out, and you can plug it
into the lambda-calculus reducer below:
(\f.(\x.f(x x))(\x.f(x x)))(\F.\N.\z.z N (F (\f.\x.f(N f x))))(\f.\x.x)(\x.\y.y)(\x.\y.y)(\x.\y.y)(\x.\y.y)(\x.\y.y)(\x.\y.x)
But, you were not supposed to have to do that.
HINT: Z is the Church numeral for zero, K and K* are the
two projections for the pairing function
\M.\N.\z.zMN, and \N.\f.\x.f(N f x)
is the successor function for Church numerals.
Now can you figure it out?
- Source to my lambda-calculus reducer
-
Here is my source,
in case there are any tricks to be learned from it.
- Another lambda-calculus reference
-
This paper by
Henk Barendregt (author of the lambda calculus bible)
and coauthor may be useful as a source of additional insight
and details.
- Another lambda-calculus reducer
-
This one looks interesting.
- Lambda-calculus reducer
- I was asked in class today if there was a tool that would allow
you to check your lambda-calculus reductions. In answer to the
question, I whipped something up in Java. To use it, download
these class files.
Run this with
java Term and at the prompt type
your lambda-calculus term to be reduced.
The first line output will be the parsed version of the term.
Subsequent lines will be obtained from the first by contracting
beta redexes, according to a "leftmost-outermost" reduction
strategy.
Here is an example:
%java Term
? (\d.d d)(\f.\x.f(f x))
((\d.(d d)) (\f.(\x.(f (f x)))))
((\f.(\x.(f (f x)))) (\f.(\x.(f (f x)))))
(\x.((\f.(\x.(f (f x)))) ((\f.(\x.(f (f x)))) x)))
(\x.(\a.(((\f.(\x.(f (f x)))) x) (((\f.(\x.(f (f x)))) x) a))))
(\x.(\a.((\a.(x (x a))) (((\f.(\x.(f (f x)))) x) a))))
(\x.(\a.(x (x (((\f.(\x.(f (f x)))) x) a)))))
(\x.(\a.(x (x ((\a.(x (x a))) a)))))
(\x.(\a.(x (x (x (x a))))))
Note that the input syntax uses backslash for lambda.
Hopefully I got the bugs out of the parser.
You should be able to omit parentheses and it should
parse the expression properly.
If you see any problem with it, send me a test case.
I did not spend that long testing it, so be forewarned.