0. Time Estimates

Please record estimates of the time you spent on each problem in time.txt.

1. Racket Programming (70 points)

Please do not use DrRacket’s “box comments” in your code. They interact poorly with our grading infrastructure.

Grading is based on correctness, efficiency, conciseness, elegance, and comments that show you understand how or why your solution works. For example, comments for the list-length function we wrote should be more detailed than, e.g., “list-length returns the length of the given list”, but less detailed than the Racket-to-English translation, “if the argument is null then return zero otherwise return 1 plus the result of a recursive call to list-length on the cdr of the argument.” A good level of detail would be: “list-length returns the length of the given list. An empty list has length zero. A non-empty list has length one greater than the length of the tail (rest) of the list.” There are of course many valid styles of conveying this information, but this should give you an idea of the level of detail to target.

  1. An association list is a list of pairs that represents a mapping from key to value. Each pair of key and value is represented by a cons cell, with the key in the car and the value in the cdr. For example, the association list:

    (list (cons 2 3) (cons 5 1) (cons "mountain" #t))

    maps the key 2 to the value 3, the key 5 to the value 1, and the key "mountain" to the value #t.

    Write a function lookup that takes a key k and an association list as and returns:

    • #f if no mapping with key k was not found in the list; and
    • a cons cell whose car is k and whose cdr is the corresponding value for the shallowest mapping of k in the association list.

    Use the function (equal? x y) to test for equality of keys. This will support keys more interesting than just simple values.

    For example:

    > (lookup 1 (list (cons 2 3) (cons 5 1) (cons "mountain" #t)))
#f
> (lookup 5 (list (cons 2 3) (cons 5 1) (cons "mountain" #t)))
'(5 . 1)
> (lookup 5 (list (cons 2 3) (cons 5 1) (cons 5 "river")))
'(5 . 1)
> (lookup (list 3 5) (list (cons (list 3 5) 2) (cons 5 1)))
'((3 5) . 2)

  2. Write two functions decimal-tail and decimal-foldl that both take a list bs of bits (0 or 1) and return the non-negative integer value of the binary number given by bs. decimal-tail should use tail recursion and no higher-order functions. decimal-foldl should use foldl and no other higher-order functions and no explicit recursion. For example:

    > (decimal null)
0
> (decimal (list 0))
0
> (decimal (list 1))
1
> (decimal (list 1 0))
2
> (decimal (list 1 0 0))
4
> (decimal (list 1 0 1))
5
> (decimal (list 1 0 1 0))
10
> (decimal (list 1 0 1 1))
11
> (decimal (list 1 0 1 1 0))
22
> (decimal (list 1 0 1 1 1))
23
> (decimal (list 1 0 1 1 1 0))
46

  3. Implement the rev function from the previous assignment, but do not use append or explicit recursion. Do use foldl (Racket’s built-in fold left function.) Racket’s built-in foldl expects its function argument to be of the form (lambda (x acc) ...), where the list element is the first argument and the accumulator is the second argument.

    rev takes a list xs and reverses its order. You may not use the built-in reverse function.

    > (rev (list 1 (list 2 3) (list 4 5 (list 6 7 8))))
'((4 5 (6 7 8)) (2 3) 1)
> (rev (list 1 2 3 4 5))
'(5 4 3 2 1)
> (rev (list 1))
'(1)
> (rev null)
null

  4. Implement all? and all?-foldl. Each of these functions takes a one-argument predicate function f and a list xs and:

    • returns a non-#f value if (f x) returns a non-#f value for all x in xs;
    • returns #f if (f x) returns #f for any x in xs where f is defined on all elements preceding x in xs; and
    • is otherwise undefined.

    Think of these functions as generalizations of contains-multiple or all-contains-multiple from the previous assignment.

    The functions are to be implemented as follows. Also consider the examples below carefully.

    • all? uses recursion, but no calls to higher-order functions (other than f, which, for all we know, might be higher order).
    • all?-foldl does not use recursion and does use the built-in foldl (fold left) function, but no calls to higher-order functions other than foldl and f.

    In the following examples, both functions should have identical results:

    > (all? (lambda (x) (> x 7)) (list 34 42 12 8 73))
#t ; or any non-#f value
> (all? (lambda (x) (= x 9)) null)
#t ; or any non-#f value
> (all? not (list #f #f #t #f))
#f
> (all? (lambda (x) (> (/ 8 x) 3)) (list 2 0))
; error
> (all? (lambda (x) (= 2 (/ 8 x))) (list 8 4 2 0))
#f

  5. Implement a similar function all?-filter using Racket’s built-in filter function, without using explicit recursion or calls to higher-order functions other than filter (and f, if it happens to be higher-order).

    A filter-based solution will give a result on strictly fewer inputs than correct all? and all?-foldl solutions. Show a function f and a list expression xs such that (all?-filter f xs) behaves differently than (all? f xs). Explain why all?-filter violates the specification given for all? on these inputs and what part of the specification is violated.

  6. Write a function any? that takes a predicate function f and a list xs and:

    • returns a non-#f value if (f x) returns a non-#f value for any x in xs where f is defined on all elements preceding x in xs;
    • returns #f if (f x) returns #f for all elements x in xs; and
    • is otherwise undefined.

    The function definition should fit comfortably on one or two lines. Hint: consider the relationship between “for any” (a.k.a. “exists”) and “for all”.

    > (any? (lambda (x) (> x 7)) (list 34 42 12 8 73))
#t ; or any non-#f value
> (any? (lambda (x) (= x 9)) null)
#f
> (any? not (list #f #f #t #f))
#t
> (any? (lambda (x) (> (/ 8 x) 3)) (list 2 0))
#t
> (any? (lambda (x) (= 2 (/ 8 x))) (list 0 2 4 8))
; error

  7. Implement contains-multiple and all-contains-multiple as specified in the previous assignment using no explicit recursion and no higher-order functions other than all? and any?.

    contains-multiple takes an integer m and a list of integers ns that returns #t if m evenly divides at least one element of the integer list ns; otherwise it returns #f. Use modulo to determine divisibility.

    > (contains-multiple 5 (list 8 10 14))
#t
> (contains-multiple 3 (list 8 10 14))
#f
> (contains-multiple 5 null)
#f

    all-contain-multiple takes an integer n and a list of lists of integers nss (pronounced “enziz”) and returns #t if each list of integers in nss contains at least one integer that is a multiple of n; otherwise it returns #f.

    > (all-contain-multiple 5 (list (list 17 10 2) (list 25) (list 3 7 5)))
#t
> (all-contain-multiple 3 (list (list 17 10 2) (list 25) (list 3 7 5)))
#f
> (all-contain-multiple 3 null)
#t

2. Garbage Collection (30 points)

Read the sections of papers listed below and answer the questions following. You may find it helpful to read the questions first to make your paper-reading more efficient. There is much interesting detail in the assigned paper sections, but also more than you need to answer the questions below.

Reading

McCarthy Terminology:

  • Register refers to a memory location (a unit of storage: either a register or a memory location in 240 terms). Each register is holds one word worth of data. One word of data is equivalent to the representation of a cons cell. Thus a register is the unit of storage required to store a cons cell. On the IBM 704 computer used to build the first Lisp system, the largest single accessible unit of data (a.k.a. word size) was 36 bits. Each cons cell or symbol was represented by one word, stored in some available register.
  • The car and cdr names are derived from the contents of the address and decrement parts of a register (features of the IBM 704) used to represent a cons cell.
  • NIL is null.
  • S-expressions are the parenthetically-inclined notation you know from Racket. McCarthy adds commas where Racket uses only spaces.
  • M-expressions are an alternative notation of Lisp programs where parentheses are replaced by brackets, the operator/function occurs outside the brackets, and arguments are separated by semicolons. For example, Racket (cons 8 null) would be written as the M-expression cons[8; NIL].
  • The public push-down list is the call stack, as footnote 8 indicates. SAVE is push, UNSAVE is pop.

Questions

Answer these questions briefly. For each question, write a few sentences at most.

  1. McCarthy claims that cyclic structures of cons cells are impossible to construct using the expressions he describes earlier in the paper. Is this also true of the subset of the Racket language we have explored? If so, describe why and consider your experience with other languages to suggest a feature that could be used to create cyclic structures. If not, write a Racket expression that results in a cyclic structure of cons cells.
  2. What is a limitation that applies to reference-counting, mark-sweep, and copying garbage collection?
  3. What is a problem in both reference-counting and mark-sweep garbage collection that is addressed by copying collection?
  4. What is one limitation of reference-counting that is not a problem for mark-sweep garbage collection?
  5. What is the point of incremental garbage collection?
  6. What is the key expected behavior of programs for which generational collection is optimized? (This is also called the generational hypothesis.) Briefly describe how generational collection optimizes for this behavior.