HigherOrder Fun
 Due: 11:00pm Thursday, 24 September
 Files:
 fork wellesleycs251 / cs251hof, share with bpw
 Programming answers in
functions.rkt
 Text answers in
answers.txt
oranswers.pdf
 Time estimates in
time.txt
 Submission: commit and push your completed work to your Bitbucket fork as in previous assignments.
 Reading:
 Racket
 McCarthy, Recursive Functions of Symbolic Expressions and Their Computation by Machine, 1960. Section 4 (pages 2230).
 Wilson, Uniprocessor Garbage Collection Techniques. As needed: sections 12, 33.2, 4.
 Tools:
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 listlength
function we wrote should be more detailed than, e.g., “listlength returns the length of the given list”, but less detailed than the RackettoEnglish translation, “if the argument is null then return zero otherwise return 1 plus the result of a recursive call to listlength on the cdr of the argument.” A good level of detail would be: “listlength returns the length of the given list. An empty list has length zero. A nonempty 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.

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 thecdr
. For example, the association list:(list (cons 2 3) (cons 5 1) (cons "mountain" #t))
maps the key
2
to the value3
, the key5
to the value1
, and the key"mountain"
to the value#t
.Write a function
lookup
that takes a keyk
and an association listas
and returns:#f
if no mapping with keyk
was not found in the list; and a cons cell whose
car
isk
and whosecdr
is the corresponding value for the shallowest mapping ofk
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 two functions
decimaltail
anddecimalfoldl
that both take a listbs
of bits (0
or1
) and return the nonnegative integer value of the binary number given bybs
.decimaltail
should use tail recursion and no higherorder functions.decimalfoldl
should usefoldl
and no other higherorder 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

Implement the
rev
function from the previous assignment, but do not useappend
or explicit recursion. Do usefoldl
(Racket’s builtin fold left function.) Racket’s builtinfoldl
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 listxs
and reverses its order. You may not use the builtinreverse
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

Implement
all?
andall?foldl
. Each of these functions takes a oneargument predicate functionf
and a listxs
and: returns a non
#f
value if(f x)
returns a non#f
value for allx
inxs
;  returns
#f
if(f x)
returns#f
for anyx
inxs
wheref
is defined on all elements precedingx
inxs
; and  is otherwise undefined.
Think of these functions as generalizations of
containsmultiple
orallcontainsmultiple
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 higherorder functions (other thanf
, which, for all we know, might be higher order).all?foldl
does not use recursion and does use the builtinfoldl
(fold left) function, but no calls to higherorder functions other thanfoldl
andf
.
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
 returns a non

Implement a similar function
all?filter
using Racket’s builtinfilter
function, without using explicit recursion or calls to higherorder functions other thanfilter
(andf
, if it happens to be higherorder).A
filter
based solution will give a result on strictly fewer inputs than correctall?
andall?foldl
solutions. Show a functionf
and a list expressionxs
such that(all?filter f xs)
behaves differently than(all? f xs)
. Explain whyall?filter
violates the specification given forall?
on these inputs and what part of the specification is violated. 
Write a function
any?
that takes a predicate functionf
and a listxs
and: returns a non
#f
value if(f x)
returns a non#f
value for anyx
inxs
wheref
is defined on all elements precedingx
inxs
;  returns
#f
if(f x)
returns#f
for all elementsx
inxs
; 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
 returns a non

Implement
containsmultiple
andallcontainsmultiple
as specified in the previous assignment using no explicit recursion and no higherorder functions other thanall?
andany?
.containsmultiple
takes an integerm
and a list of integersns
that returns#t
ifm
evenly divides at least one element of the integer listns
; otherwise it returns#f
. Usemodulo
to determine divisibility.> (containsmultiple 5 (list 8 10 14)) #t > (containsmultiple 3 (list 8 10 14)) #f > (containsmultiple 5 null) #f
allcontainmultiple
takes an integern
and a list of lists of integersnss
(pronounced “enziz”) and returns#t
if each list of integers innss
contains at least one integer that is a multiple ofn
; otherwise it returns#f
.> (allcontainmultiple 5 (list (list 17 10 2) (list 25) (list 3 7 5))) #t > (allcontainmultiple 3 (list (list 17 10 2) (list 25) (list 3 7 5))) #f > (allcontainmultiple 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 paperreading 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 2230).
 Wilson, Uniprocessor Garbage Collection Techniques, 1992. As needed: sections 12, 33.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
andcdr
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
.  Sexpressions are the parentheticallyinclined notation you know from Racket. McCarthy adds commas where Racket uses only spaces.
 Mexpressions 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 Mexpressioncons[8; NIL]
.  The public pushdown 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 referencecounting, marksweep, and copying garbage collection?
 What is a problem in both referencecounting and marksweep garbage collection that is addressed by copying collection?
 What is one limitation of referencecounting that is not a problem for marksweep 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.