Answer 4 of the following 5 questions.
Problem 1: C implements call-by-value (pass-by-value) by
copying the bits of an argument's representation into the local
storage holding the corresponding formal parameter. This
implementation works well for atomic values like numbers, booleans,
and characters, but produces anomalous behavior for objects such as
structures and arrays.
Explain how this implementation of call-by-value interferes with
a semantic interpretation of an object as a value; include an example.
(Hint: Consider how both Scheme and Java treat objects and
call-by-value.)
Problem 2: Some experts claim that all garbage collection
algorithms are "conservative". More specifically, they
assert that no automatic memory manager can reclaim
all the memory that a program will
not access in the remainder of an evaluation.
Question 1: Explain what portion of allocated memory is
difficult to reclaim. Give an example showing reclaimable memory that
"precise" (non-conservative) garbage collectors miss.
Question 2: Can a C programmer, who has far more control over
memory allocation than, say, a Java or a Scheme programmer, overcome
this problem?
Problem 3: A former 311 student recalls Milner's famous
theorem, which says that "typed programs can't go wrong." Explain
what the theorem really asserts and what it does not
assert. Address the following questions:
Question 1: Consider the Scheme subset consisting of the simply
typed lambda-calculus where the only ground type is
integer and the only functions are (curried) addition,
if0 (a conditional expression operator where the test
expression is compared against 0), and Ys
(fixed-point) operators of every type s. Is it true that any
typable program in this language (using the standard type checking
rules taken from the simply typed lambda-calculus) cannot
generate a run-time error.
Question 2: Extend the preceding Scheme subset to include array
operations (allocation, access, and update) and the corresponding type
system to include an array type constructor. Is it true that a
typable program in this expanded language cannot raise a run-time
error?
Question 3: Is it true that an untypable program in the array
language must raise a run-time error?
Problem 4: Convert the following Scheme function into CPS:
(define (quick-sort comp alon) (if (null? alon) null (append (quick-sort (lesser comp (cdr alon) (car alon))) (equals comp (cdr alon) (car alon)) (quick-sort (greater comp (cdr alon) (car alon))))))
Assume append
, lesser
, equals
,
and greater
are atomic functions.
Problem 5: An object-oriented language supporting inheritance
such as Java, C++, or SmallTalk, does not lexically close the object
(instance) methods in a class over the other methods defined in the
class. (In contrast, Scheme letrec
performs precisely this form
of closure for the procedures introduced in the letrec
.) Why do
OO languages fail to perform this closure? Give an example showing
why performing the closure would have undesirable consequences.
![]() |
![]() |
---|