Problem Set 5: Wahoo! Auctions
- Bring in to a stapled turn-in containing your written answers to Questions 1, 2, 3, 5, 7, and 11 by 3:30pm Friday March 13th. Each partner must separately submit a writeup. Your writeup must include your UVA ID (e.g., mst3k) in big block letters at the top. If you have a partner, your writeup must also include your partner's ID in big block letters.
- We do not have class on Friday, so you are responsible for getting the written answers to us. The best way to do this would be to turn them in on Wednesday (the original due date). However, if you want to turn it in on Friday, you will have to ensure that your PS ends up on Zak's desk (Olsson 236 Desk 8) by 3:30pm.
- Use our automatic adjudication service to submit a single Scheme file (a modification of ps5.scm) containing your answers to Questions 4, 6, 8, 9, 10, 12 and 13. You must define an author list. If you have a partner, each partner must separately submit a copy of your joint file. Do this by Midnight Friday March 13th.
Collaboration Policy - Read Very Carefully
If you wish to be assigned a partner for this assignment, send me an email by 11:59 pm, Friday, 27 February. Otherwise, you may work on this assignment alone or with one partner of your choice.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.
You may consult any outside resources, including books, papers, web sites and people, you wish except for materials from previous CS150 courses. You may consult an outside person (e.g., another friend who is a CS major but is not in this class, or a CS prof, etc.) 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 tell you what to type. If you use resources other than the class materials, lectures and course staff, define a sources list to indicate what you used and what you learned — as in this example:
(define sources (list "seymour cray, my roommate, explained parallelism"
"I found the shortest-path algorithm on Wikipedia"
"I asked Professor Robins about divide and conquer"))
You are strongly encouraged to take advantage of the Structured Lab Hours, Staffed Lab Hours and Office & Lab Hours for this course.
Purpose
- Learn to program using state and mutation.
- Learn how mutation changes the Scheme evaluation rules.
- Learn about databases and SQL commands.
- Save the University from further cuts to "non-essential" services.
This file contains:
- ps5.scm — A template for your answers. You should do the problem set by editing this file.
- auction.scm — Partial code for setting up an auction.
- database.scm — Partial implementation of a database.
- listprocs.scm — Some useful procedures for manipulating lists (you have seen most of them already in class).
Background
Once upon a time, in a faraway fictional town known as Charlottansville, East Virginia, there was a highly regarded public university where funding cuts led to a budget crisis. The wise and noble University administration tried cutting "non-essential" services such as heat and cleaning for student housing, libraries, printing and professors and have attempted some more creative solutions including hosting rock concerts, building a fancy new basketball arena, increasing student tuition, installing fancy electronic scoreboards on the intramural sports fields, and increasing student housing fees, but somehow the budget is still not balanced and the University is anticipating many millions of dollars in future firing expenses.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 cs150 students to develop an auction service for them.
The auction service will be built using a database. A database is just a way of storing and manipulating a large amount of structured data. For this problem set, you will implement a database and use it to implement an auction service. Our database is controlled using Scheme procedures that are similar to the SQL commands used to control nearly all commercial databases. In the final course project, you will build a dynamic web site that uses SQL commands to interact with a database.
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 will represent a table using a cons pair where the car is a list of the table fields and the cdr is a list of the table entries. These definitions are found in database.scm:
(define (make-new-table fieldlist) (cons fieldlist null))
(define (make-table fieldlist entries) (cons fieldlist entries))
(define (table-fields table) (car table))
(define (table-entries table) (cdr table))
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.scm:
(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)))
Hint: See the lecture slides from Class 13 or Figure 10.1 from the Course Book for examples of drawn global environments.
a. Draw the global environment after the following expressions are evaluated (starting in a clean global environment where make-new-table, table-fields and table-entries are defined as above):
(define t1 (make-new-table (list 'name 'email))) (set-car! (table-fields t1) 'nom) (set-cdr! t1 t1)b. Suppose we then evaluate:
(define (length lst) (if (null? lst) 0 (+ 1 (length (cdr lst))))) (length t1)Explain why the evaluation of (length t1) never terminates.
Try evaluating the expressions in Question 2 in DrScheme. Also evaluate t1 and see if you can figure out what the printed value means.
Inserting Entries
In Question 2, we manipulated our tables using set-car! and set-cdr!. It is awkward and error-prone to manipulate our database that way. Instead, we want to define more abstract procedures for manipulating data tables.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.scm):
(define (table-insert! table entry)
(assert (= (length entry) (length (table-fields table))))
(if (null? (table-entries table))
(set-cdr! table (list entry))
(append! (table-entries table) (list 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. The assert procedure will produce an error
if the passed parameter is false. It is defined:
(define (assert pred) (if (not pred) (error "Assertion failed!")))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.
a. Why does the definition of table-insert! use append! instead of append? (Your answer should clearly explain what would go wrong if we used append.)
b. Why does the definition of table-insert! need to do something different in the case where (table-entries table) is null?
Hint: try evaluating
(define lst null)
(append! lst 3)
lst
Our auction service will need procedures for adding bidders, posting items for sale and bidding on items.
a. We have already provided a definition of add-bidder! in ps5.scm. 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. Define post-item! and insert-bid!.
- post-item! should take two parameters (name, description) and add an entry in the items table
- insert-bid! should take three parameters (bidder, item and amount) and add an entry in the bids table
Question 5: Describe the running time of your insert-bid! procedure. Your answer should use Θ notation, clearly explain what all variables you use mean, and include an explanation of why your answer is correct.
We have provided a table-display procedure in database.scm for printing out a table. (You don't need to understand the details of how table-display works.)
If you define add-bidder!, post-item! and insert-bid! correctly, 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.comDevelop similar tests for your post-item! and insert-bid! procedures, and make sure they also work correctly.
Selecting Entries
Inserting entries in tables is only useful if we can also get the entries we are interested in out of the table. The table-select procedure takes a table, a field and a procedure. It evaluates to a table that has the same fields as the input table, and has entries that are all entries in the table for with the procedure applied to the value of the field for that entry is true. For example, in auction.scm we define:
(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.
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")))
((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"))))
()
Highest Bids
In any auction, it is important to know who currently has the highest bid.Your get-highest-bid procedure should work like this:
> (setup-tables)
> (get-highest-bid "SEAS")
("Tim Koogle" "SEAS" 10000000)
> (get-highest-bid "Rotunda")
()
Placing Bids
To conduct fair auctions, we can't just allow any bid to be inserted into the bids table. Instead, bids will be placed using a place-bid procedure. It should:- Only allow bids by a bidder that occurs exactly once in the bidder table. If a bid is made by someone who occurs some other number of times, you should report an error and not modify the bids table.
- Only allow bids on items that are up for sale. If a bid is made for an item that does not match the name of an item in the items table (or that matches multiple items), the place-bid procedure should report an error and not modify the bids table.
- Only allow a new bid on an item if the amount of the bid exceeds the amount of the highest earlier bid for the item. If a bid is made that is equal to or less than that amount, place-bid should report an error and not modify the bids table.
- Otherwise modify the bids table and return #t to indicate success if the bid can be successfully placed.
To report an error, use the (error "message") function. For example: (error bidder "is not an authorized bidder!"). For the purposes of grading, the exact prose of your error message doesn't matter — only whether or not you indicate an error. 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 "Westley Weimer" "SEAS" 10000000000)
Westley Weimer "is not a legitimate bidder!"
Ending the Auction
When the auction is over, all items are sold to the highest bidders and the University collects the high bid amounts. If there are no bids for an item, it cannot be sold.
Here's an example:
(setup-tables)
(place-bid "Tim Koogle" "SEAS" 18000000)
#t
(place-bid "Katie Couric" "CLAS" 90000000)
#t
(table-display (end-auction))
bidder-name item-name amount ---------------- ------------- --------- Tiki Barber COMM 79000000 Tim Koogle SEAS 18000000 Katie Couric CLAS 90000000
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.
(define book-comments "You, book, are ugly. But in the morning, I shall be sober. A weakness of this book is that knowledge attained by rote memorization is tantamount to a defeat, for it is momentary. A strength of this book is that if you know this textbook and know yourself, you will not be imperiled in a hundred battles. Finally, I note a mistake on page 1937, where you suggest that it is peace in our time -- clearly a typo.")
More seriously, we covet comments on what you thought was well-explained in the book and what was confusing, as well as what you might have done differently. If you notice any errors in the text, please bring them to our attention. Your comments will reach the textbook author directly, and help me to make the course better.
If you are working with a partner, make a longer comment that addresses all of your concerns.
In any event, you will receive full credit for any comment longer than 20 characters.
(define worst-section (cons "1.2.2" "The van Gogh pictures make me dizzy."))
Your comments should be more substantive and helpful than that example. In any event, you will receive full credit for any comment longer than 20 characters. Students who submit exceptionally helpful book-comments and worst-section answers will receive extra credit.
The creators of the fractals that get the most votes will receive extra credit and public acclaim.