Assignment 3

---

Due Date: 4/5/2004.

Questions to amiha@cs.bgu.ac.il

---

Objectives

In this assignments you are requested to define tools for a simple phonebook implementation. We will define an interface for tuples, and you will have to implement it in two ways. Both implementations will reside together side-by-side, using the techniques we studied in class. The phonebook will be a list of entries that are implemented as tuples. There is a basic interface for phonebooks, which you will also implement. Finally, you will implement several operations that manipulate data in phonebooks.

Notice that, in general, your functions should return appropriate error messages, and handle all special cases.

Code you need

New tagging method

In this assignment you need to pass untyped data to a function inside a package. To be able to do so you have to use the following definitions, instead of the one shown in the class. We will explain it in the next class.

(define (attach-tag type-tag contents)
 (cons 'typed-data (cons type-tag contents)))
 
(define (type-tag datum)
 (if (and (pair? datum) (eq? (car datum) 'typed-data))
 (car (cdr datum))
 'untyped))
 
(define (contents datum)
 (if (and (pair? datum) (eq? (car datum) 'typed-data))
 (cdr (cdr datum))
 datum))

Lookup Tables

Implementation of lookup tables, i.e., put and get, can be found here. It is also available in the text book (Section 3.3.3, page 266)

Part I: Tuples

A tuple is a data type that provides a way to assign values to different fields. For example: ((name ronen) (group friends) (number 5285555)), represents a tuple with three fields: name, group, and number, whose values are ronen, friends, and 5285555 , respectively. There are various ways to implement a tuple, and the above choice of a list of pairs is one possibility.

The following is an interface for the tuples abstract data type that you should follow use in assignment:

1. The constructor:

To create a new tuple we use: (make-tuple [field-name-1] [value-1] ... [field-name-n] [value-n]). Notie that the number of parameters is not fixed.

Example:

> (define Tuple1 (make-tuple 'name 'ronen 'group 'friends 'number 5285555))
 

2. value-of:

(value-of [field-name] [tuple]) returns the value that [field-name] is assigned to in the tuple. If [field-name] is not a valid field it returns #f.

Example:

> (value-of 'group Tuple1)
friends
 

3. set-value!:

(set-value! [name] [value] [tuple]) sets the value of field [name] to the value [value] in the tuple [tuple]. The returned value is not important, so assume it is always #t.

Example:

> (value-of 'group Tuple1)
friends
> (set-value! 'group 'colleagues Tuple1)
> (value-of 'group Tuple1)
colleagues
 

4. add-field!:

(add-field! [name] [value] [tuple]) adds a new field [name] with the value [value] to the tuple [tuple]. The returned value is not important, so assume it is always #t.

Example:

> (add-field! '2nd-number 9012525 Tuple1)
#t
> (value-of '2nd-number Tuple1)
9012525
 

5. We will also have a function (print-tuple tuple) for printing a tuple.

Example:

 > (print-tuple Tuple1)
 
 name: ronen
 group: friends
 number: 5285555
 2nd number: 9012525
 

Implementation

You will implement the above abstract data type in two ways:

1. The first implementation will represent a tuple as a list. A list of pairs, as used earlier is fine, but any implementation in which make-tuple returns some list is fine.

2. The second implementation will be based on message-passing, i.e., make-tuple will return a function which can receive message, etc.

For Example: Suppose that make-tuple is implemented using message passing. Then:

 > (define Tuple1 (make-tuple 'name 'ronen 'group 'friends 'number 5285555))
 > ((Tuple1 'value-of) 'group)
 friends
 > ((Tuple1 'set-value!) 'group 'colleagues) 
 > ((Tuple1 'print))
 name: ronen
 group: colleagues
 number: 5285555
 

You should provide two packages:

• install-list-package: This package implements the tuples using lists. It should export the following:
1. The constructor: Register the constructor in the entry 'make-list-tuple 'list
2. value-of: Register the function value-of in the entry 'value-of '(untyped list)
3. set-value!: Register the function set-value! in the entry 'set-value! '(untyped untyped list)
4. add-field! Register the function add-field! in the entry 'add-field! '(untyped untyped list)
5. print-tuple: Register the function print-tuple in the entry 'print-tuple '(list)

• install-mp-package: This package implements the tuples using message passing. It should export the following:
1. The constructor: Register the constructor in the entry 'make-mp-tuple 'mp
2. value-of: Register the function value-of in the entry 'value-of '(untyped mp)
3. set-value!: Register the function set-value! in the entry 'set-value! '(untyped untyped mp)
4. add-field! Register the function add-field! in the entry 'add-field! '(untyped untyped mp)
5. print-tuple: Register the function print-tuple in the entry 'print-tuple '(mp)

When these functions are executed, the table is updated with functions that implement the interface. In addition, you have to implement the actual interface (i.e., define each of the following in the top level) for:

• value-of
• set-value!
• add-field!
• print-tuple
• make-list-tuple
• make-mp-tuple

using the techniques we saw in class (i.e., by calling apply-generic for the selectors, and using get for the constructors).

Also define the function make-tuple to be make-list-tuple or make-mp-tuple, i.e.: (define make-tuple make-list-tuple) or (define make-tuple make-mp-tuple).

Part II: Phonebook Entries

Now we proceed to implementing entries in a phonebook. Phonebook entries are basically a list of tuples with the same fields. We will refer to the tuples in a single entry as its elements.

The interface for a phonebook that you will implement is defined as follows:

1. Create a new (empty) phonebook:

Each phonebook is specified using the constructor (make-phonebook [field-1-name] ... [field-n-name]). Assume all the fields have different names, but check that there is at least one field.

Example:

(define std-phonebook (make-phonebook 'name 'group 'number)) would create a new phonebook with three fields per entry: name, group and number.

2. Get table fields names:

(entry-fields [phonebook]) should return a list of the field names in the same order as when the phonebook was created.

Example:

> (entry-fields std-phonebook)
(name group number)
 

3. Adding entries:

Entry addition to the phonebook (the table) is done by the function: (add-entries [phonebook] [entry-list]), which adds the entries from [entry-list] to the phonebook (at the end of the book). You must check for data integrity (i.e., that all entries have the right number of fields).

Example:

> (add-entries std-phonebook
 '((ronen friends 5258888)
 (danny friends 9621111)
 (dana colleagues 6382020)))
 

changes the std-phonebook phonebook to contain the three entries '(ronen friends 5285555), '(danny friends 9621111) and '(dana colleagues 6382020).

4. Deleting entries:

Entry deletion is performed by the function (delete-entries phonebook entry-list), which deletes the entries in entry-list from the book if they exist. The entry-list is given in a way similar to the one in add-entries. If an entry appears more than once in the book you should delete all occurrences.

Example:

(delete-entries std-phonebook '((danny friends 9621111))) would change the phonebook std-phonebook to contain only the entries '(ronen friends 9621111) and '(dana colleagues 6382020).

5. Is the book empty:

The function empty-book? returns True iff the phonebook contains no entries, otherwise return #f.

6. Getting the first entry: Getting the first entry from a phonebook is performed by: (first-entry phonebook), which returns the first entry of the book. If the function is called with the empty phonebook, it should return false (#f). Note that the returned value is an entry.
7. Getting the rest of the entries: (rest-entries phonebook), which returns a new phonebook that contains all the entries of the book except the first. If the function is called with the empty phonebook, it should return false (#f)
8. Adding a field to all entries: (add-field <phonebook> <field-name> <field-values>) returns a new phonebook, in which to all entries was added a new field: <field-name>. Note that <field-values> is a list, containing values needed for the field in the book’s entries. These values should be inserted accordingly. Note that if the list is too long, you should truncate it. If it is too short, you should return an error.

Example:

(add-field std-phonebook ‘entry-number ‘(1 22 3 4.4)) would return a new phonebook, containing the following entries: '(ronen friends 5285555 1), (danny friends 9621111 22) and '(dana colleagues 6382020 3).

9. Printing all entries: To print all entries of a given book we apply (print-entries <phonebook>).

Implementation

You can implement this in any way you wish, as long as your implementation does not make any assumptions about how tuples are represented, i.e., you are allowed to use the constructor make-tuple only and the setters and selectors from the tuple interface.

Part III

Given the interface from Part II, implement the following operations. The implementation should rely on the functions map, filter, and\or accumulate defined in class.

1. Projection:

Suppose we wish to create a new phonebook that will contain only part of the data in a given book. Define the function (project [field-name-list] [phonebook]), which returns a new phonebook whose fields appear in [field-name-list] and whose entries are the projections of the given fields in the book. Check that [field-name-list] contains only fields that are part of phonebook. You have to print appropriate error messages.

Example:

(define simple-phonebook (project '(name number) std-phonebook))
 

will return the phonebook that contains the entries: '(ronen 5285555), '(danny 9621111) and '(dana 6382020).

2. Selecting elements:

Define the function (select [phonebook] [predicate]) where [predicate] is a Boolean function defined on entries of the given [phonebook], which returns a new phonebook that contains the entries from [phonebook] that satisfy the predicate. The argument of the predicate is of type tuple.

Example:

(select std-phonebook (lambda (tup) (eq? (value-of 'group tup) ‘colleagues)))
 

will return a new book that contains: '(dana colleagues 6382020).

3. Conditional Merge

Define the function (cond-merge [pred] [phonebook-1] [phonebook-2] … [phonebook-n])

This function will be used to combine several phonebooks (an unknown number) to a new, single book. This book will only contain entries in the given n books that satisfy [pred]. The argument of the predicate is of type tuple.

You may assume that all books have the same entry structure, but not the same number of entries.

Example:

(define 2nd-phonebook (make-phonebook 'name 'group 'number))

(add-entries 2nd-phonebook 
 '((yosi roommates 6482444)
 (olga colleagues 6481111)))
 
(cond-merge (lambda (tup) (eq? (value-of 'group tup) ‘colleagues)) std-phonebook 2nd-phonebook)
 

will return a new book that contains: '((dana colleagues 6382020) (olga colleagues 6481111))