[SOLVED] CS450 Homework Assignment 7 Memory management

Homework Assignment 7
Any automatically graded answer may be manually graded by the instructor. Submissions
are expected to only use functions taught in the course. If a submission uses a disallowed function, that
exercise can get zero points. Excluding promises, all functions that mutate values are disallowed (mutable
functions usually have a ! in their name).
Memory management
1. Implement function frame-refs that returns the set of all handles contained in the given frame, according
to the notion of contains introduced in class.
• Hint: Consider using function frame-values.
• Hint: Suppose you have a list l of d:values. You can keep just the elements of a given type,
say you want to only keep the d:numbers of l, with filter and a type predicate. That is
(filter d:number? l) returns all of the numbers in l and has type (Listof d:number).
2. Implement function (mem-mark contained mem ref) that returns the set of all reachable handles from
handle ref, and takes: contained a function that takes an element of the heap and returns a set of
handles contained in that element, mem is a heap, and ref is the initial handle, according to the memory
sweep algorithm discussed in class. This is effectively a graph traversal algorithm. An example
of a contained function is function frames-refs for a heap of frames. Notice that function mem-mark
expects a heap of any data.
3. Implement function (mem-sweep mem to-keep) that given a heap mem and a set of handles to keep
(parameter to-keep) returns a new heap of frames that only contains the handles in the given set. Hint:
Peruse hw7-util.rkt for heap-related functions. The solution should be a single function call.
Monads
Recall the list operations we have implemented in class.
4. Implement map for lists of effectful operations.
5. Implement exists? for lists of effectful operations.
Manually graded questions
6. Manually graded. Consider memory management via reference counting and the increment count operation. Suppose that the reference count algorithm is faulty and the reference count overflows resetting
back to zero. Discuss if overflowing the reference count affects soundness or completeness of memory
management.
Page 2