code GC, tail recursion, and higher-order functions

Contents

Time Info

In Fall 2019, students self-reported spending a median of 6.0 hours on this assignment.

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 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 fundamental limitation that applies to reference-counting, mark-sweep, and copying garbage collection? Focus on effectiveness rather than performance.
  3. What is a problem in both reference-counting and mark-sweep garbage collection that is addressed by copying collection?
  4. What is a key limitation of the effectiveness 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.

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

Write your answers to this part in hof.rkt. Follow the same style guidelines as in the previous assignment, with the exception that use of append (or any equivalent function) is prohibited in this assignment.

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.

  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 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)

  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)
'()

  3. 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

  4. In class, we introduced both append-based and tail-recursive versions of rev.

    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

  5. Write two new versions of the deep-rev function from the previous assignment. These functions take any argument x and deeply reverse it. If x is an atom (any non cons cell value), deep-rev returns it as is. If x is a cons cell, deep-rev assumes it represents a list, reverses the list, and deeply reverse any lists that are elements in x. Assume that cons cells are used only to represent lists. The cons? function returns #t if its argument is a cons cell and #f otherwise.

    The new deep-rev-map function should use rev-foldl (or any other reverse function, such as Racket’s built-in reverse) and map, without any explicit recursive calls of deep-rev-map appearing in the body of deep-rev-map. (Read that restriction carefully.)

    The new deep-rev-tail function should use tail recursion but no external helper functions and no higher-order functions. Internal helper functions are fine. Note that you will need both tail recursion and natural recursion.

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

  6. Implement all? and all?-foldl. Each of these functions takes a one-argument predicate function p 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 p 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.

    In logical/mathematical terms, the all? functions determines whether the following property holds for a given predicate $P$ and lists of elements $\mathit{xs}$:

    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 p, 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 p.

    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 special note of the last two examples, which demonstrate that all? and all?-foldl should take a short-circuited approach when applying the predicate function p to individual elements.

  7. 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 p, if it happens to be higher-order).

  8. A correct all?-filter function will return a result on strictly fewer argument cases than correct all? and all?-foldl solutions.

    Define:

    1. a one-argument function, distinguish-all?-filter-pred; and
    2. a binding for a list expression, 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.

  9. Write a function any? that takes a predicate function p 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.

    In logical/mathematical terms, the any? functions determines whether the following property holds for a given predicate $P$ and lists of elements $\mathit{xs}$:

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

    > (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

  10. 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 m 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 m; 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

  11. 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:

  1. Test your source code files one last time. Make sure that, at a minimum, submitted source code is free of syntax errors and any other static errors (such as static type errors or name/scope errors). In other words: the code does not need to complete the correct computation when invoked, but it must be a valid program. We will not grade files that do not pass this bar.

  2. Make sure you have committed your latest changes.

    $ git add ...
$ git commit ...

  3. Run the command cs251 sign to sign your work and respond to any assignment survey questions.

    $ cs251 sign

  4. 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.