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:
(*var* noun-phrase)
?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.
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)) ==> -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.
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) ==> 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) ==> ()
(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