These exercises are meant for self-evaluation and practice. You need not turn in code for any of them and you are also not expected to code them all up. (Though you may find some of the functions useful in future coding.) It is sufficient if you are familiar with how to approach each of the problems. Each question is tagged with the aspect of Scheme programming that it emphasizes. More challenging questions have been marked with * (hard) or ** (darn hard).

The background materials listed on the course home page should be useful. You're almost certain to need to refer to Dybvig for some of the more esoteric Scheme features, even if you're already familiar with the basics of the language.

*The history of this document:* Raja Sooriamurthi wrote this
problem set for C463 in the Fall of 1991. In the Fall of 1995, John Nienart updated the
macro problem to reflect the changes in the Chez Scheme syntactic
extensions facility, and converted the problems to HTML.

Scheme provides a primitive function `assoc`

that takes an
object and an *alist* (list of pairs) and returns the first
pair in alist whose car field is obj. If no pair in alist has obj as
its car `#f`

is returned. `assoc`

uses
`equal?`

to compare obj with the car fields of the alist.
Write a function `multi-assoc`

that behaves like
`assoc`

except that it returns all the pairs in the alist
whose car field is obj.

(multi-assoc 'gee '((gee golly) (golly solly) (gee glee))) ==> ((gee golly) (gee glee)) (multi-assoc 'wed '((mon tough) (tue slog) (sat party!))) ==> #f

Write a function `filter`

that takes a predicate and a list
as argument and returns a list of only those elements that satisfy the
predicate.

(filter odd? '(1 2 3 4 5 6 7 8 9)) ==> (1 3 5 7 9)Write

`multi-assoc`

in terms of `filter`

.
In areas of AI like Natural Language Processing, Logic there is a need for variables which are used to represent entities (which are different from Scheme variables but similar to the algebraic notion of variables). Some of the possible notations for variables are:

- a list whose car is a special tag:
`(*var* noun-phrase)`

- a symbol whose first letter is special:
`?noun-phrase`

or`*noun-phrase`

.

The second notation is preferable for its conciseness. Write a
predicate (boolean valued function) that takes an object as input and
returns `#t`

if its a variable and `#f`

otherwise. You can use either the `*`

or `?`

prefix notation.

(variable? '*np) ==> #t (variable? "*np") ==> #f (variable? '(*np jack)) ==> #f

Write a function `explode`

that takes a symbol as input and
returns a list of symbols corresponding to its individual characters.

(explode 'apple) ==> (a p p l e) (explode 'a) ==> (a)

Also write a function implode that is the inverse of explode. It takes a list of one character symbols and combines them to form a single symbol.

(implode '(a p p l e)) ==> apple (implode '(a)) ==> a (implode (explode 'geewhiz)) ==> geewhiz

For simplicity you may assume that the symbols on which explode and implode operate on consist only of alphabets.

* Extend explode and implode to deal with symbols that have numerals in them.

(explode 'r2d2) ==> (r 2 d 2)

** Chez uses the notation of bracketing a symbol between two
vertical bars when the symbol contains special characters like a space
or parenthesis. For example, `|apple 2|`

represents an
identifier with a space between the e and 2; `|(a)|`

represents a symbol which is flanked by a pair parenthesis.

(symbol? '|(a)|) ==> #t (symbol? '(a)) ==> #f (pair? '|(a)|) ==> #f (pair? '(a)) ==> #tGeneralize

`explode`

and `implode`

to work for
lists.
(explode '(r2d2))) ==> (|(| r 2 d 2 |)|) (explode '(r2d2 c3po)) ==> (|(| r 2 d 2 | | c 3 p o |)|) (implode (explode '(r2d2 c3po))) ==> (r2d2 c3po)This is a hard problem. One solution would be to use string-ports.

Write a function `cxr`

that is a generalization of the
`car/cdr`

operators provided in Scheme. `cxr`

should take a string of "a"s and "d"s representing the sequence of
`car`

and `cdr`

operations to be performed and
return a function capable of performing that sequence.

Thus `(cxr "ad")`

is equivalent to the function
`cadr`

.

((cxr "ad") '(i ii iii iv v vi vii)) ==> ii (define sixth (cxr "addddd")) (sixth '(i ii iii iv v vi vii)) ==> vi

Write a function `split`

that takes a flat list of symbols
and numbers and returns a pair of lists, one consisting only of
symbols and the other only of numbers.

(split '(a 2 s 4 5 f)) ==> ((a s f) (2 4 5)) (split '()) ==> (() ())A two pass algorithm is simple. Try writing a one pass algorithm using accumulators. Re-write your solution using functional continuations.

The primitive `map`

function available in scheme can take a
function of one argument and one list and apply that function to all
the top-level items of the list. Write a generalization of this
`mu-map`

that can take a function of any arity and a
corresponding number of lists. It then returns a list by applying the
function to the corresponding elements of all the lists. You may
assume that all the lists are of the same length.

(mu-map (lambda (x y) (+ x y)) '(1 2 3) '(10 11 12)) ==> (11 13 15)Modify

`mu-map`

so that it even when the lists are not of
the same length it will work. It applies the function to as many
elements as there are in the shortest list.
(mu-map (lambda (x y) (+ x y)) '(1 2 3 4 5) '(10 11)) ==> (11 13)

`call/cc`

as an escaper
Write a function `list-index`

that takes an object and a
list as argument and returns the zero-based index of the first
occurrence of the object in the list. You signal the absence of the
object in the list by returning -1.

(list-index 'a '(a s d a)) ==> 0 (list-index 'b '(a s d b s)) ==> 3 (list-index 'z '(a b c)) ==> -1There are several ways you can do this. You could first test to see if the object you are looking for is in the list with a function like

`member`

and if not you return -1 or else you proceed to
determine the index. Instead of testing for membership you could use
an accumulator. Finally you could use `call/cc`

to set up
an escaping function which you then invoke when you have determined
that the object is not in the list. Write the function using
`call/cc`

.
Write the function `reverse`

that reverses the top level
elements of a list.

(reverse '(a b c d)) ==> (d c b a) (reverse '()) ==> ()Sounds easy? Well, heres the catch. You are allowed to use only

```
car
```

, `cdr`

, `cons`

, `cond`

and, of course, recursive applications of `reverse`

. This
means no other help functions are allowed and so the general way of
writing reverse with snoc as below doesn't count:
(define reverse (lambda (ls) (cond [(null? ls) '()] [else (snoc (reverse (cdr ls)) (car ls))])))

Write a program to solve the following puzzle:

Dr. Z the ruler of the ancient kingdom of Joejb has her political foes locked up in individual cells in her dungeon. There are a total of 100 cells. On their Independence day as all the Joejbians were celebrating Dr. Z decided to release some of her political prisoners. But being the maverick she was she does the following: She goes to the first cell and opens it, she goes to 2nd and opens and she continues to open the 3rd, 4th ... all the way to the 100th cell. She then comes back to the 2nd cell and closes it. Shes closes the 4th and in steps of 2 she closes the 6th, 8th ... 98th and 100th cells. She then comes to the 3rd cell and this times in steps of 3 she visits each cell (3rd, 6th, 9th ...) and if the cell is open she closes it and if its closed she opens it. She repeats this process of opening closed cells and closing open cells in steps of 4, 5 ... all the up to a step of 100. In the end she decrees that all the prisoners in the cells that remain open are free to go.

Who are those lucky prisoners (ie what are their cell numbers)?

Scheme gives you the functions `getprop`

and
`putprop`

. They enable you to associate values with a key.

(putprop 'john 'category 'noun) (getprop 'john 'category) ==> nounWhen associating a new value with an existing key the old value is replaced. Write a function

`addprop`

which doesn't replace
the value associated with a key but keeps the values in a list which
is added on to.
(getprop 'run 'category) ==> () (addprop 'run 'category 'verb) (getprop 'run 'category) ==> (verb) (addprop 'run 'category 'noun) (getprop 'run 'category) ==> (noun verb)

If you were to write the set operation `intersection`

(on
sets of symbols) using
membership testing routines, your program would cost on the order of `m
* n` where `m`, `n` are the sizes of the
individual sets (represented as lists).

Use property lists to write a more efficient version of
`intersection`

that is of order `O(m+n)` [`O(2m+n)` to be precise].

Using the `syntax-rules`

facility of Chez scheme, write a macro
`begin0`

, which is similar to `begin`

. Each of
them takes a sequence of one or more expressions, and evaluates
them in order of occurrence (from left to right). However,
`begin`

returns the value of the last expression, whereas
`begin0`

should return the value of the first.

(begin 1 2 3 4 5) ==> 5 (begin0 1 2 3 4 5) ==> 1

The function `gensym`

in Chez provides a mechanism for
creating fresh symbols. But the notation for gensym symbols generally
isn't pleasing, so you might want to write your own symbol
generator. Write a function `newsym`

which behaves similar
to `gensym`

which, when invoked as a thunk returns a new
symbol each time.

(newsym) ==> g0 (newsym) ==> g1 ...But unlike

`gensym`

write `newsym`

so that it
can also take an optional number as argument and use that as base for
the counter to generate new symbols.
(newsym) ==> g2 (newsym 10) ==> g10 (newsym) ==> g11