Cluster 5 * Summer 2004
Computer Science Through Games and Scheme Programming
David G. Kay, Dan Frost, Kevin Papke

Scheme Lab Activities: Fifth Set

1. In today's lab, you will continue doing pair programming. We noticed from Tuesday's labs that some pairs were practicing pair programming better than others. We also noticed that the groups actually doing pair programming (two people, one computer, one person at a time using the mouse and keyboard, discussing possible approaches) got a lot further with the labs, even those groups whose members had very little programming experience.
   So, if you haven't gotten going with pair programming, try again today. Talk to each other; good programming is not an individual, isolated activity.


2. If you still need to work on Lab 3 or Lab 4, finish those up. You may change partners, but if one partner hasn't gotten as far as the other, the group needs to work on the activities that one partner has completed already, so everyone gets the full experience. Remember, getting the answer isn't the important thing; understanding the process is. This would be a good opportunity for the student who hasn't yet done an activity to be the driver while the one who has already been through it acts as navigator.


3. Here is some more explanation about let. Sometimes when you write a function, it's convenient to calculate a few values and give them names so you can use them in the body of your function. The way to do this within a function in Scheme is not to use define (which we use only at the top level of the interpreter) but instead to use let. Here's an example from one version the battleship code; this uses let* instead of let because the order of the definitions is important (we'll talk later about why this makes a difference):
   (define add-ship-of-length
     (lambda (board ship-length)
     (let* ((width (length (car board)))
     (height (length board))
     (x (random width))
     (y (random height))
     (dir (random 4)))
     (write-line "trying x=" x " y=" y " dir=" dir)
     (cond
     [(open-water? board x y dir ship-length)
     (add-ship-at board x y dir ship-length)]
     [else
     (write-line " trying again . . .")
     (add-ship-of-length board ship-length)]))))
   Whenever we learn a new feature of a programming language, we describe its syntax (its grammar, or how you write it) and its semantics (its meaning, or what it does).
   The syntax of let is as follows:
      (let
        (
          (name1 value1--any Scheme expression)
          (name2 value2--any Scheme expression)
          . . .
        )
        body of let--any Scheme expression
      )
   The difference between a description of a feature's syntax and an example of its use is that the syntax description provides the general rule for writing that feature. Syntax descriptions usually include meta-symbols or place-holders that indicate the kind of thing to be included at a given point. Each underlined phrase above is a meta-symbol. You'd never type the words "value 1--any Scheme expression" into your program; instead, you'd put an actual Scheme expression there. There are two things to watch out for in the syntax of let: The first is that there's a set of parentheses around each name-value pair and a separate set around all the name-value pairs. When you have just one name-value pair, it will have two sets of parentheses around it, which people sometimes forget. The second thing to notice is that the body of the let, where all the work gets done using the names you defined, is included within the parentheses enclosing the let. Scheme will remember the name-value pairs you define, but only while you're inside the let (we call that the scope of the definitions--the limits of where those definitions are usable). Why is it useful to have definitions with limited scope? Why not just make everything visible everywhere? Because in real-life-size programs, the programmer working on one part might choose the same name as another programmer working on a different part. To keep everyone on the project from wasting time coordinating their choice of names, we limit the visibility of names just to the places where we know they're needed.


4. There's plenty to do in this lab assignment. Work on it for the morning session; if you don't finish (and probably you won't), put it aside and work on Dan's games lab in the afternoon. You'll get a chance to come back to these activities later.


5. Here are some classic list-processing functions. Trying to write them will really help you learn to think recursively. Write each of these functions in Scheme. It will help to pay attention to the type of value that each function returns: Is it a list, a single item, a number, a boolean? That tells you what type of expression you need as the right-hand side of each cond clause. Be sure to test your answers in DrScheme, using at least all of the examples we show below.


1.  
   (member? A B) returns #t (true) if A occurs in the list B, and #f (false) if it doesn't.
   (member? 'a '()) returns #f;
   (member? 'a '(b a t t y)) returns #t;
   (member? '(b (c)) '(a b (b (c)) d (b (c)))) returns #t;
   (member? '(b (c)) '(a b (c))) returns #f.


2.  
   (find-all-evens A) takes a list of numbers and returns a list containing all the numbers from the original list that are even. The predefined predicate even? is useful here.
   (find-all-evens '()) returns ();
   (find-all-evens '(3 9 7)) returns ();
   (find-all-evens '(1 2 3 4 5)) returns (2 4);
   (find-all-evens '(3 2 7 2 6)) returns (2 2 6).


3.  
   (all-even? A) takes a list of numbers and returns #t if they're all even, and #f otherwise.
   (all-even? '()) returns #t;
   (all-even? '(3 5 7 2 6)) returns #f;
   (all-even? '(2 8 0 4 88)) returns #t.


4.  
   (count-all-matches A B) returns the number of times A occurs in the list B.
   (count-all-matches 'a '()) returns 0;
   (count-all-matches 'a '(a b a c a d)) returns 3;
   (count-all-matches 'a '(a b (a) c (a d))) returns 1;
   (count-all-matches '(a (b)) '(a b (a (b)) a (b) (a (b)) ((a (b))))) returns 2.


5.  
   (subst A B C) returns C with all occurrences of A changed to B.
   (subst 'x 'y '()) returns ();
   (subst 'a 'b '(a c e)) returns (b c e);
   (subst 'a 'b '(b c d)) returns (b c d);
   (subst 'a '(a b) '(a b r a)) returns ((a b) b r (a b));


6.  
   (subst '(a b c) 'abc '(w x (a b c) y (a b c) z)) returns (w x abc y abc z).
   (first-atom A) returns the first atom in the list A, no matter how deeply nested. Use the predefined predicates pair? and null? to test whether something is an atom or not.
   (first-atom '()) returns ();
   (first-atom '(a b c)) returns a;
   (first-atom '(((a b) c))) returns a;
   (first-atom '( () a b c)) returns (), which is easy because (atom? '()) is #t.


7.  
   (atomize A) returns a list of all the atoms in A, no matter how deeply nested. (Hint: Use the predefined function (append L1 L2) to join the atoms in (first A) with the atoms in (rest A).)
   (atomize '()) returns ();
   (atomize '(a b c)) returns (a b c);
   (atomize '((a b) c)) returns (a b c);
   (atomize '(((a) () (b c)) (d e))) returns (a () b c d e).


6. Let's go back to thinking about restaurants. Suppose we change the way we represent restaurants. Instead of one best dish and the price of that dish, let's give each restaurant a menu:
      (define-struct new-Rrant (name cuisine phone menu))
   The menu will be a list of dishes; each dish will have a name and a price:
      (define-struct dish (name price))
   Thus, we could define a restaurant with a two-dish menu as follows:
      (define R1 (make-new-Rrant "Thai Touch" 'Thai "949-640-0123"
        (list (make-dish "Mee Krob" 8.50) (make-dish "Larb Gai" 10.25))))


1. Write a new definition of R1 that includes a third dish, Paht Woon Sen at $7.95.


2. Define R2 as a new-Rrant structure for the French restaurant Pascal, whose phone number is 940-752-0107; they serve escargots for $12.95, poached salmon for $18.50, rack of lamb for $24.00, and marjolaine cake for $8.50.
   Of course it is possible in Scheme to build a user interface to allow users to enter data without the user having to type lengthy Scheme expressions. It takes a bit of time and effort to do, and since our focus right now is on the actual internal processing rather than the user interface, we're not making GUI-building a part of this activity.


3. As you go through the remainder of these activities, take the time to define other restaurant structures to use in your testing. A fundamental principle of programming is to design your testing before you write your code. This is why we always come up with examples in advance. The examples help us clarify what our functions should be doing, and they become our test cases.


4. Write the function new-Rrant-first-dish that takes a restaurant as its argument and returns the name of the first dish on the restaurant's menu. Remember to write the test cases and examples before you write the function. You should include code to check whether the menu has zero dishes and return the empty list if so.


5. Write the function dish-cheap? that takes a single dish structure and a number and returns true if (and only if) the price of the dish is less than the specified number.


6. Write the function menu-all-cheap? that takes a menu (i.e., a list of dish structures) and a number and returns true if (and only if) all the dishes on the menu have a price less than the specified number. If the menu is empty, menu-all-cheap? should return true. Of course you should use dish-cheap? in your definition.


7. Write the function new-Rrant-all-cheap? that takes a restaurant and a number and returns true if all the dishes the restaurant serves cost less than the specified number. Of course you should use menu-all-cheap? in your definition.


8. Write the function menu-prices that takes a menu and returns a list of numbers where each number is the price of a dish on the menu. That is, your function will collect all the prices of the dishes into a list and return that list.


9. Write the function menu-average that takes a menu and returns the average price of the dishes on that menu. The predefined function length will be helpful; it will also be helpful to write a function sum that returns the sum of a list of numbers. Note also that you'll need to check for an empty menu and return zero in that case, so you don't divide by zero. Finally, note that the straightforward way to do this involves calling menu-prices twice; to avoid this duplication of effort, use let.


10. Write the function new-Rrant-cheap? that takes a restaurant and a number and returns true if the average price of the restaurant's menu is less than the specified number.


11. Write the function new-Rrant-keep-cheap that takes a restaurant and a number and returns (a newly constructed copy of) that restaurant with all the menu items that aren't cheap removed. The right way to go about this is to follow the pattern of the functions above: Start by writing a function to operate on a menu, and then call that function from your new-Rrant-keep-cheap function. The actual removal task follows the pattern of one of the functions we discussed in class.


12. Write the function keep-cheap-restaurants that takes a list of restaurant objects and a number (representing a price threshold) and returns a new list of restaurant objects with the non-cheap restaurants removed. A cheap restaurant is one whose average menu price is less than a given price threshold.


13. Those of you with experience programming in other programming languages might take a minute to ask yourselves how much code it would take in the other language to perform these tasks.
    Now, what if we told you that in Scheme, there's a way to do many of these tasks that's a lot shorter even that what you've written in this lab activity? It's true; stay tuned for next week.

COSMOS Cluster 5 Home * COSMOS UCI Home

Thursday, July 15, 2004 -- 8:30 AM