1. This assignment will take longer than the last. Start early!
2. The problems are not sorted by difficulty. Feel free to jump around.
3. Inspiration: ‘(1 2 3 4

## 1. Racket Programming1 (70 points)

Complete the following programming problems. If at all possible, avoid the use of the built-in list `append` function (and the equivalent `list-append` we wrote in lecture today). One or two functions below may seem to require `append` or something equivalent—feel free to use `append` there, but note its running time is O(n) given an n-element first argument. Soon we will see a new style of recursion for an efficient, elegant alternative.

1. Write a function `merge` that merges two lists into one as in merge-sort. Assuming the two argument lists are each sorted lists of numbers, this function will return a sorted list containing all elements from the two lists. Your function does not need to work for inputs that are not sorted.

``````> (merge (list 1 3 6 7 9 10) (list 2 4 5 8))
'(1 2 3 4 5 6 7 8 9 10)
> (merge (list 4 5 6) (list 1 2 3))
'(1 2 3 4 5 6)
> (merge null null)
'() ; this means null``````
2. Write a function `rev` that 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)
'()``````
3. Write a function `deep-rev` that takes any argument `x` and deeply reverses it. If `x` is an atom, `deep-rev` returns it as is. If `x` is a `cons` cell, `deep-rev` assumes it is 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.2

``````> (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)
'()``````
4. Write a function `contains-multiple` that 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``````
5. Write a function `all-contain-multiple` that 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``````
6. Write a function `bits` that takes a natural number `n` and returns a list of the bits (`0`s and `1`s) in the binary representation of `n`.

``````> (bits 5)
'(1 0 1)
> (bits 10)
'(1 0 1 0)
> (bits 11)
'(1 0 1 1)
> (bits 22)
'(1 0 1 1 0)
> (bits 23)
'(1 0 1 1 1)
> (bits 46)
'(1 0 1 1 1 0)
> (bits 1)
'(1)
> (bits 0)
'()``````

Hint: The above sequence of examples has been chosen carefully to illustrate the divide/conquer/glue nature of the solution.

Optional 240-tinted challenge: Write a separate function `bits-2s` that takes a natural number `b` and an integer `n` and a returns a list of `0`s and `1`s representing all digits of the `b`-bit two’s-complement representation of integer `n`.

``````> (bits-2s 4 6)
'(0 1 1 0)
> (bits-2s 4 -6)
'(1 0 1 0)``````
7. Write a function `censor-word` that takes a string `w` and returns `w` if `w` is not is a word in the bad words list `'(algorithms midterm extension databases systems grade)` and returns `'XXXX` if `w` is a bad word. The built-in `member` function takes a value `x` and a list `xs` and returns `#f` if `x` is not an element in `xs` or non-`#f` otherwise. We have been avoiding writing the quote notation in Racket programs so far. Make an exception here to use symbols. We will discuss these more later.

`````` > (censor-word 'apple)
'apple
> (censor-word 'midterm)
'XXXX``````

Write a second function `censor` that uses `censor-word` and the built-in `map` function to censor sentences by replacing all bad words: `censor` takes a list of strings and returns a list of strings with bad words replaced by `'XXXX`. Do not use recursion in `censor`.2

`````` > (censor '(I need an extension because I have an algorithms midterm))
'(I need an XXXX because I have an XXXX XXXX)
> (censor '(Programming languages is more fun than systems))
'(Programming languages is more fun than XXXX)``````

## 2. Error Detection Constructs2 (10 points)

Evaluation of a Racket expression can either terminate normally (and return a value), terminate abnormally with an error, or run forever. Some examples of expressions that terminate with an error are `(/ 3 0)`, division by 0; `(car 2)`, taking the `car` of an atom; and `(+ 3 #f)`, adding a boolean to a number. As we have seen in evaluation rules for Racket expressions, dynamic type-checking detects these errors. In DrRacket, this terminates evaluation and prints a message to the screen. Suppose that you work at a software company that builds text editors in Racket-with-Side-Effects. (It’s been done in a very similar language: Emacs is built in a dialect of Lisp!) Side effects are observable changes that are not just values returned by evaluation. They include: changing the value stored in a mutable variable (like variables work in Java), sending data across the network, displaying text or images on a screen, and countless other operations. The subset of Racket we have studied so far lacks side effects, but the full language includes operations with side effects.

Your boss, who is notoriously skittish about side effects, wants to handle errors in Racket programs without terminating the computation, but doesn’t know how. Thus, the job has fallen to you (the programming language expert).

1. Your boss asks you to implement a Racket construct `(error? e)` that detects whether an expression `e` will cause an error when evaluated. More specifically, your boss wants evaluation of `(error? e)` to return the value `#t` if evaluating `e` terminates with an error and return the value `#f` if evaluating `e` behave in any way except terminating in error. Explain why it is not possible to add the `error?` construct to Racket.

2. Your boss asks you to implement a Racket construct `(guarded e)` that either evaluates `e` and returns its value, or if `e` would halt with an error, returns `0` without performing any side effects. This could be used to try to evaluate `e` and if an error would occur, just use `0` instead. For example,

`````` (+ (guarded e1) e2) ; just (+ 0 e2) if e1 halts with an error
; (+ e1 e2) otherwise``````

will have the value of `e2` if evaluation of `e1` would halt in error, and the value of `(+ e1 e2)` otherwise. Describe how you might implement the `guarded` construct. What difficulties might you encounter? Notice that unlike `(error? e)`, evaluation of `(guarded e)` does not need to finish and produce a result in all cases.

## 3. Conditional Expressions (20 points)

We introduced the `if` expression in Racket. The original definition of Lisp focused instead on a related `cond` expression, presented by McCarthy in his 1960 paper, Recursive Functions of Symbolic Expressions and Their Computation by Machine, which discussed foundations and implementation details of Lisp. The name `cond` stands for conditional. Read sections 1-2 (pages 1-8) of McCarthy’s paper to answer the questions below.

McCarthy uses mathematical notation that differs somewhat from Racket syntax. Here is a conversion from McCarthy’s notation to a syntax that would fit Racket.

• (p1 → e1, …, pn → en) would be written `(cond [p1 e1] ... [pn en])`, where all `pi` and `ei` are expressions.
• T is `#t` and F is `#f`.
• is boolean and (logical conjunction), is boolean or (logical disjunction), and ¬ is boolean not (logical negation). (The text defines these standard notations.)
• λ((x1,…,xn), e) would be `(lambda (x1 ... xn) e)`, where `x1` through `xn` are variable names and `e` is an expression.

Section 2 gets denser on pages 6-8. The most important material is earlier, but try to pick up what you can from the later parts as well.

The remainder of McCarthy’s paper is an interesting read as well if you are curious. It describes more features of the Lisp language (still present in Racket) that we will consider briefly later. We will soon return to at least the section describing implementation.

Questions

1. McCarthy describes undefined results for some conditional expressions.

What does it mean for an expression’s result to be undefined? (McCarthy gives an indirect definition of this notion early in Section 2.)

2. Write two Racket expressions (using only the Racket features we have examined in this course) whose results are undefined, one using recursion and one without.

3. Write an evaluation rule for `cond` (using the Racket-style syntax listed above and the style of evaluation rules we have defined in class) to describe the semantics of McCarthy’s conditional expression.

4. Given the `cond` syntax shown above and your evaluation rule, we can implement `cond` as syntactic sugar. Describe in English how to construct an equivalent Racket expression to replace a `cond` expression. Feel free to show concrete examples of replacement by an equivalent expression, but please describe the general transformation or “desugaring” you would perform given any valid `cond` expression.

For inspiration, recall how we desugared the short-circuit and operation, `(and e1 e2)`, to the semantically equivalent expression `(if e1 e2 #f))` or how we desugared the `or` expresion in class. If you need to produce an undefined result explicitly, call the zero argument function `void`; it produces “no value.”

1. Several problems in this section are adapted from courses by Randy Shull and Lyn Turbak here at Wellesley College.

2. This problem is adapted from a problem by Stephen Freund at Williams College, by permission. 2 3