## 0. Time Estimates

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

## 1. Racket Programming (70 points)

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.

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.