Tasks

1. Garbage Collection (25 points)

Write your responses in gc.txt.

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, Recursive Functions of Symbolic Expressions and Their Computation by Machine, 1960. Section 4 (pages 22-30).
Wilson, Uniprocessor Garbage Collection Techniques, 1992. As needed: sections 1-2, 3-3.2, 4.

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.

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.
What is a limitation that applies to reference-counting, mark-sweep, and copying garbage collection?
What is a problem in both reference-counting and mark-sweep garbage collection that is addressed by copying collection?
What is one limitation of reference-counting that is not a problem for mark-sweep garbage collection?
What is the point of incremental garbage collection?
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.

2. Racket Programming with Tail Recursion and Higher-Order Functions (75 points)

Write your answers to this part in hof.rkt.

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.

Feel free to introduce helper functions where they would be useful in solving the problems (or simplifying the solutions).

append prohibited

On the previous assignment you were asked to use append only where needed. On this assignment, now that you know more techniques for recursion and iteration, use of append is prohibited in all of the following programming tasks.

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 associations and returns:
- #f if no mapping with key k was 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)
```
Write a function bits-tail using tail recursion without higher-order functions that takes a non-negative integer n and return a list of the bits (0s and 1s) in the binary representation of n. This function should produce the same results (via different implementation) as your bits function from the previous assignment.
```
> (bits-tail 5)
'(1 0 1)
> (bits-tail 10)
'(1 0 1 0)
> (bits-tail 11)
'(1 0 1 1)
> (bits-tail 22)
'(1 0 1 1 0)
> (bits-tail 23)
'(1 0 1 1 1)
> (bits-tail 46)
'(1 0 1 1 1 0)
> (bits-tail 1)
'(1)
> (bits-tail 0)
'()
```

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

In class, we introduce a tail-recursive version of rev, from the previous assignment.

Implement the rev-foldl function without using append or explicit recursion. Use foldl (Racket’s built-in fold left function).

rev-foldl takes a list xs and reverses its order. You may not use the built-in reverse function.
```
> (rev-foldl (list 1 (list 2 3) (list 4 5 (list 6 7 8))))
'((4 5 (6 7 8)) (2 3) 1)
> (rev-foldl (list 1 2 3 4 5))
'(5 4 3 2 1)
> (rev-foldl (list 1))
'(1)
> (rev-foldl null)
'() ; null
```
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-contain-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
```
Take note especially of the last two examples, which demonstrate that all? and all?-foldl should take a short-circuited approach when applying the predicate function f to individual elements.
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 correct all?-filter function will give a result on strictly fewer argument cases than correct all? and all?-foldl solutions.

Define:
1. a function (define (distinguish-all?-filter-pred x) ____); and
2. a list expression (define distinguish-all?-filter-list ____);
such that (all?-filter distinguish-all?-filter-pred distinguish-all?-filter-list) behaves differently than (all? distinguish-all?-filter-pred distinguish-all?-filter-list).

Explain in a comment why all?-filter violates the specification given for all? on these arguments and what part of the specification is violated.
Write a function any? that takes a predicate function f and a list xs and:
- returns a non-#f value if there exists some element x in xs such that (f x) returns a non-#f value and, for all elements y preceding x in xs, (f y) is defined;
- returns #f if (f x) returns #f for all elements x in xs; and
- is otherwise undefined.
The entire 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
```
Implement contains-multiple and all-contain-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
```
Write a function nondecreasing? that takes any list of numbers and returns #t if its elements, from first to last, are nondecreasing (i.e., monotonically increasing): each element is at least as large as the last. Do not use any form of recursion in your solution. Do use a higher-order function.
```
> (nondecreasing? null)
#t
> (nondecreasing? (list 2))
#t
> (nondecreasing? (list 2 5))
#t
> (nondecreasing? (list 2 5 1))
#f
> (nondecreasing? (list 0 3 7))
#t
> (nondecreasing? (list 1 1 1))
#t
```

Submission

Submit: The course staff will collect your work directly from your hosted repository. To submit your work:

Make sure you have committed your latest changes.
```
$ git add ...
$ git commit ...
```
Run the command cs251 sign to sign your work and respond to any assignment survey questions.
```
$ cs251 sign
```
Push your signature and your latest local commits to the hosted repository.
```
$ git push
```

Confirm: All local changes have been submitted if the output of git status shows both:

Your branch is up to date with 'origin/master', meaning all local commits have been pushed
nothing to commit, meaning all local changes have been committed

Resubmit: If you realize you need to change something later, just repeat this process.