Regardless of whether you work alone or with a partner, you are encouraged to discuss this assignment with other students in the class and ask and provide help in useful ways.
Remember to follow the pledge you read and signed at the beginning of the semester. For this assignment, you may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous cs1120, cs150, and cs200 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class) who is not a member of the course staff, but that person cannot type anything in for you and all work must remain your own. That is, you can ask general questions such as "can you explain recursion to me?" or "how do lists work in Scheme?", but outside sources should never give you specific answers to problem set questions. If you use resources other than the class materials, lectures and course staff, explain what you used in your turn-in.
You are strongly encouraged to take advantage of the scheduled help hours and office hours for this course.
This file contains:
Fortunately, the University was able to get "Chapter 11" status from the Commonwealth, which gives it more power to control its own destiny by raising tuition and selling off assets. The Board of Transients has decided the time for drastic measures has arrived, and they will conduct an auction to raise money. To avoid paying fees to a commercial auction service, they have decided to exploit free labor from cs1120 students to develop an auction service for them.
Data in a database is stored in tables. The fields of a table describe the data and are not mutable. The entries of a table are the data, and can be changed.
We represent a table using a mutable mcons pair where the mcar is a list of the table fields and the mcdr is a list of the table entries. Note that we use a mutable pair to represent the table so can mutate the fields and entries associated with a table.
These definitions are found in database.ss:
(define (make-table fieldlist entries) (make-tlist 'table (mcons fieldlist entries))) (define (make-new-table fieldlist) (make-table fieldlist null)) (define (table-fields t) (mcar (tlist-get-data 'table t))) (define (table-entries t) (mcdr (tlist-get-data 'table t)))They use a tagged list to make an abstract datatype (as in Section 5.6).
For the Wahoo! Auctions service, we will need several different tables to keep track of the bidders, the items for sale, and the bids on those items. We use quoted symbols to describe the fields in a table. Those tables are defined in auction.ss:
(define bidders (make-new-table (list 'name 'email)))
(define items (make-new-table (list 'item-name 'description)))
(define bids (make-new-table (list 'bidder-name 'item-name 'amount)))
a. Draw the global environment after the following expressions are evaluated:
(define t1 (mcons 'name 'email)) (set-mcar! t1 'nom) (set-mcdr! t1 'courriel) (set-mcdr! t1 t1)b. Suppose we then evaluate (mlist-length t1) where mlist-length is defined as in Section 9.3. Explain why the evaluation of (mlist-length t1) never terminates.
Try evaluating the expressions in Question 1 in DrScheme. Also evaluate t1 and see if you can figure out what the printed value means.
The table-insert! procedure inserts an entry into a table. We follow the Scheme (and Yahoo!?) convention of using an ! at the end of the names of procedures that mutate state. You should follow this convention also.
You shouldn't need to change the definition of table-insert!, but you should be able to understand it (defined in database.ss):
(define (table-insert! table entry)
;;; The entry must have the right number of values --- one for each
field in the table
(assert (= (length entry) (length (table-fields table))))
(if (null? (table-entries table))
(set-mcdr! (tlist-get-data 'table table) (mlist entry))
(mlist-append! (table-entries table) (mlist entry)))
(void)) ;;; don't evaluate to a value
The expression (assert (= (length entry) (length (table-fields table))))
checks that the entry we are adding to the table has the right number of elements
— there must be one element in the entry corresponding to each
field in the table. Note that we use length here insetad of
mlength because we are making the entries themselves
immutable. This means we can change the entries in the table (since the
entries is a mutable list), but we cannot change the value of an entry itself.
The assert procedure will produce an error if the passed parameter is false. It is defined (in book-code.ss):
(define (assert pred) (if (not pred) (error "Assertion failed!")))Next, it uses an if expression that tests if (table-entries table) is null. The consequent expression uses set-mcdr! to replace the cdr part of the table data with a new mutable list containing a single element, the inserted entry. The alternate expression uses mlist-append! (from Example 9.4) to mutate the table entries by adding the input entry to the list. Note that mlist-append! does not work when the input list is null since there is no way to mutate null (it is not a mutable cons pair, but it is a mutable list). This is why we needed the if expression with the consequent expression for handling the case where the entries are empty.
We use (void) at the end of the procedure body to prevent an application of table-insert! from evaluating to a value. The procedure void takes no parameters, and produces no value.
Our auction service will need procedures for adding bidders, posting items for sale and bidding on items. We have provided a definition of add-bidder! in ps5.ss:
(define (add-bidder! name email) (table-insert! bidders (list name email)))It takes two parameters (name and email) and adds an entry in the bidders table. Understanding it should give you a good idea how to define some additional procedures. We have defined a table-display procedure in database.ss for printing out a table. (You don't need to understand the details of how table-display works.)
You should obtain the following interactions:
> (table-display bidders)
name email ------------------------- -------------------------
> (add-bidder! "Tim Koogle" "tk@yahoo.com")
> (add-bidder! "Katie Couric" "katie@cbs.com")
> (add-bidder! "Dave Matthews" "dave@dmb.com")
> (table-display bidders)
name email ------------------------- ------------------------- Tim Koogle tk@yahoo.com Katie Couric katie@cbs.com Dave Matthews dave@dmb.com
a. Define post-item! as a procedure that takes two parameters (name, description) and adds an entry with the given name and description to the items table.
b. Define insert-bid! as a procedure that takes three parameters (bidder, item and amount) and adds a corresponding entry to the bids table.
Develop tests for your post-item! and insert-bid! procedures similar to the add-bidder! examples above, and make sure they also work correctly. For the problem set, we are not providing any automatic adjudicator service. This means you need to think carefully yourself about how to test your code.
For example,
(table-select bids 'item-name (lambda (pitem) (string=? pitem "CLAS")))should produce a table with the same fields as the bids table, (bidder-name item-name amount), but only containing those entries whose item-name matches the string "CLAS".
So, to define table-select, you will first need to find the index of the selected field (e.g., 'item-name in the example). We have provided (in book-code.ss) the list-find-element procedure that may be helpful for this. It takes as input a list and a value, and outputs a number that indicates what is the first element of the input list that matches the input value. Elements are numbered starting from 1. If none of the elements match, the output is 0.
(define (list-find-element p el) ; evaluates to the index of element el
(define (list-find-element-helper p el n)
(if (null? p)
0 ; element not found
(if (eq? (car p) el)
n
(list-find-element-helper (cdr p) el (+ n 1)))))
(list-find-element-helper p el 1))
Using list-find-element, we have defined
table-field-number, a procedure that takes a table and a field
and outputs the index of that field in the table's field list:
(define (table-field-number table field) (list-find-element (table-fields table) field))The fields are indexed starting from 1; if the field is not in the table, table-field-number outputs 0.
Hence, you could start to define table-select as:
(define (table-select table field predicate)
(let ((fieldno (table-field-number table field)))
(if (= fieldno 0) (error "No matching field: ~a" field))
...
Another procedure you may find helpful in finishing the definition of
table-select is the mlist-filter procedure (defined in
book-code.ss:
(define (mlist-filter test p)
(if (null? p) null
(if (test (mcar p))
(mcons (mcar p) (mlist-filter test (mcdr p)))
(mlist-filter test (mcdr p)))))
Note that this procedure is very different from mlist-filter!
from Example 9.3. It does not mutate the input list, but instead
creates a new mutable list that contains only those elements in the
input list for which the test function evaluates to true.
If your table-select is working correctly, you should see interactions similar to these:
> (insert-bid! "Tim Koogle" "SEAS" 10000000)
> (insert-bid! "Dave Matthews" "CLAS" 2000000)
> (insert-bid! "Tiki Barber" "COMM" 79000000)
> (insert-bid! "Katie Couric" "CLAS" 37000000)
> (table-select bids 'item-name (lambda (pitem) (string=? pitem "CLAS")))
(table . {(bidder-name item-name amount) ("Dave Matthews" "CLAS" 2000000) ("Katie Couric" "CLAS" 37000000)})
> (table-display (table-select bids 'item-name (lambda (pitem) (string=? pitem "CLAS"))))
bidder-name item-name amount ------------------------- ------------------------- ------------------------- Dave Matthews CLAS 2000000 Katie Couric CLAS 37000000
> (table-entries (table-select bids 'item-name (lambda (pitem) (string=? pitem "SEAS"))))
{("Tim Koogle" "SEAS" 10000000)}
> (table-entries (table-select bids 'item-name (lambda (pitem) (string=? pitem "Rotunda"))))
()
> (table-entries (table-select bids 'amount (lambda (pamount) (> pamount 10000000))))
{("Tiki Barber" "COMM" 79000000) ("Katie Couric" "CLAS" 37000000)}
> (table-entries
(table-select
(table-select bids 'amount (lambda (pamount) (<= pamount 10000000)))
'bidder-name
(lambda (pbidder) (string=? pbidder "Katie Couric"))))
()
In auction.ss we define define some procedures for making it easier to do table selects:
(define (make-string-selector match) (lambda (fval) (string=? fval match)))
(define (get-bids item)
(table-entries (table-select bids 'item-name (make-string-selector item))))
The get-bids procedure evaluates to a list of bid entries
that are the entries in the bids table whose
item-name field matches the parameter item. If
you're not sure how this works, try evaluating some expressions using
make-string-selector by themselves.
Your get-highest-bid procedure should work like this:
> (setup-tables)
> (get-highest-bid "SEAS")
("Tim Koogle" "SEAS" 10000000)
> (get-highest-bid "Rotunda")
()
To report an error, you can use the error function. It take a list of values and prints them as an error message, terminating the execution. For example: (error bidder "is not an authorized bidder!"). The exact prose of your error message doesn't matter — only that it clearly indicates what the problem is. So be as creative as you like with your error messages.
Hint: place-bid! may be a relatively long procedure: 25 to 30 lines is reasonable. Don't worry if yours is longer or shorter, as long as you understand what is going on and you are getting the right answers.
You should get interactions similar to these:
> (setup-tables)
> (place-bid! "Tim Koogle" "SEAS" 20000000)
#t
> (place-bid! "Katie Couric" "SEAS" 18000000)
Bid amount does not exceed previous highest bid: {"Tim Koogle" "SEAS" 20000000}
> (place-bid! "Katie Couric" "SEAS" 22000000)
#t
> (place-bid! "Dave Matthews" "The Rotunda" 1000000)
The Rotunda is not for sale!
> (place-bid! "David Evans" "SEAS" 10000000000)
David Evans is not a legitimate bidder!
(A truly stellar end-auction! should evaluate to a number representing the total amount of money the University makes from the auction. It is acceptable to produce no output.)
Here's an example:
> (setup-tables)
> (end-auction!)
Congratulations Tim Koogle! You have won SEAS for $10000000. Congratulations Katie Couric! You have won CLAS for $37000000. Congratulations Tiki Barber! You have won COMM for $79000000. No bids on CS1120. Congratulations Bono! You have won SIS for $1.
126000001
Try some sample auctions to demonstrate your program. See if you can make enough money to save the University, but be careful not to sell off too many important assets — we will revisit the University in Charlottansville in Problem Set 6.