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

Scheme Lab Activities: First Set

Keep these two things in mind as you work:
After three minutes, ask someone: Some of these activities ask you to read things, try things, look things up, and experiment. As long as you feel as if you're making progress towards a solution, that's great; many problems will require more than three minutes of work to solve. But if you feel stuck and don't know how to proceed, give it three minutes of solid thought and if you're still stuck, ask someone--either a classmate or one of the staff. Nothing we're doing should require more solid thinking time than that.
Help each other: If a classmate asks you something you can answer, lend a hand. This is a cooperative enterprise, not a competitive one.

1. Locate and launch the DrScheme software. If you're using a personal machine, download it from www.drscheme.org and install it.


1. Each DrScheme window has two panes: The bottom half is the interactions (or transcript) window, where you can type Scheme expressions and see the interpreter evaluate them. To type code you wish to save, use the top pane (the definitions window) and click the green "Execute" arrow to evaluate the code (this makes the code available for use in the interactions window below).


2. DrScheme is actually a collection of different languages. For most of COSMOS, we'll use the language called "Pretty Big". You can see which of the DrScheme languages is installed by looking at the green text at the top of the interactions pane. If it doesn't say "Pretty Big" there, change your language through the Language menu. The TA can show you how.


2. Experiment with DrScheme to get familiar with it.


1. Try evaluating some expressions, like (* 3 4 5) and (expt 4 50) and (gcd 75 225) and (/ pi 2). In Scheme, the value of pi and the computation of greatest common divisors are predefined (built in).


2. Type in some definitions of symbols in the interactions window, like (define number-of-students 31) and (define number-of-staff 8) and then try (+ number-of-students number-of-staff). (You may get a yellow warning message. This is telling you that you've typed in the interactions window instead of the definitions window, so what you've typed won't be saved. That's fine for the experimentation we're doing now, but as you start making your own definitions, you'll want to type them in the top window, save them periodically, and evaluate them by clicking Execute.)


3. The factorial function (written with an exclamation point, so "n factorial" would be n!) is used in calculating how many ways there are to arrange things. The value of n! is n * (n-1) * (n-2) * ... * 1, so 5! = 5 * 4 * 3 * 2 * 1 = 120.


1. Type the following function definition into the definitions window. Actually do the typing so you can get used to the way it works; don't just copy and paste.
   ; Compute n! (n factorial).
   (define fact
      (lambda (n)
        (cond
          ((<= n 0) 1 ) ; 0! is 1 by definition
          (else (* n (fact (- n 1)))))))
   Notice how the environment indents and highlights blocks of code so you don't get the parentheses confused.


2. Don't forget to click Execute.


3. Try evaluating expressions like (fact 5), (fact 50), and (fact 500).


4. Evaluate (fact (fact 5)).


5. What happens when you evaluate (fact (fact 50))?


6. What is the value produced by (/ (fact 5) (expt 7 2))?


1. This result is called "exact representation"--it looks unusual to us, but it's useful in further calculations because nothing is lost by rounding off to a decimal representation.


2. Enter this definition (you can copy and paste it):
    (define decimal-format
     (lambda (num)
     (string->number (number->string (exact->inexact num)))))


3. Evaluate (decimal-format (/ (fact 5) (expt 7 2))).


4. Go ahead and play around more with DrScheme, trying other expressions.


1. Now try some compound expressions, like (gcd (fact 100) (expt 2 1000)) and (fact (fact 5)) and (first (rest (list Huey Dewey Louie))).


2. Write down on paper the standard mathematical notation for each of the expressions listed above (except the "Huey, Dewey, Louie" one; also, you can leave "gcd" unchanged).


3. What's the longest number you can generate in DrScheme, without running out of memory and taking no more than 60 seconds of elapsed time? Generating the big numbers is one part of the question; counting the digits is another.


1. Try to count digits using (string-length (number->string your-big-number)). How do you get your-big-number into that expression without copying and pasting it (or typing it)?


2. Try to do it using some tool(s) other than Scheme (or any programming language).


3. Using your wristwatch (or slow, measured counting), time how long it takes for Scheme to calculate and display your big number. Now, time how long it takes to calculate the big number and then its length (by nesting the expression to generate the big number inside the length-calculating expression from part C1. You'd expect the second to take longer, but on some Scheme systems it doesn't. Does it on your system? Why might the generate-and-calculate-length task take less time?


4. Experiment with the list operators--cons, first, rest, list, append, null?--until you're comfortable with how they work. You can look at the online help (available under the Help menu) for some more information (a lot more than you will need for now). To understand what a function does, be sure you understand what kinds of data it expects as its arguments (atoms? lists? numbers?) and what kind of data it returns. The function cons, for example, takes any expression as its first argument and a list as its second argument, and it returns a list.

COSMOS Cluster 5 Home * COSMOS UCI Home

Tuesday, July 13, 2004 -- 7:10 AM