## Scheme Practice Problems

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.

### Flat recursion

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

### Recursion

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

### Strings

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))            ==> #t
```
Generalize `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.

### Higher order functions

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
(sixth '(i ii iii iv v vi vii))         ==> vi
```

### Accumulators and continuations

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.

### Map

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)

```

### Using `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))        ==> -1
```
There 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`.

### **Recursion

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

### *Vectors

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

### Property lists

Scheme gives you the functions `getprop` and `putprop`. They enable you to associate values with a key.

```        (putprop 'john 'category 'noun)
(getprop 'john 'category)       ==> noun
```
When 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)        ==> ()
(getprop 'run 'category)        ==> (verb)
(getprop 'run 'category)        ==> (noun verb)
```

### Property lists

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

### Macros

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

### Local state

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