Com S 227 --- Introduction to Computer Programming HOMEWORK 1: SCHEME DATA AND OPERATORS (File $Date: 1993/09/04 19:42:40 $) Due: problems 0-6, Sept. 1; 7-10 and 12-14, Sept. 3; 15-16, Sept. 8. In this homework you will explore the fundamental building blocks of Scheme programs, data and operators. You will learn what the different kinds of scheme data there are, and some primitive ways of constructing and picking apart lists. These will be used in later chapters to write more interesting programs. There is another more immediate motivation, however. Part of writing a program is designing its data: data modeling. Data modeling is the art of designing forms of data that capture the information needed to do interesting things in a progarm. In Scheme, the fundamentals of data modeling are symbols, numbers, and lists. The section headings below give the sections of Scheme and the Art of Programming that you should read to help yourself with the problems. Whenever possible you should type your answers into a file, and print the result. This will give you more practice typing. (Feel free to draw pictures by hand.) At the top left of your homework, put your name, and at the top right, your TA's name. Clearly identify each problem. ERRATA FOR SCHEME AND THE ART OF PROGRAMMING 0. (0 points; basic) In the file /home/cs227/doc/errata.txt is the errata for our textbook. Look in this file to see what corrections you should make in the text. If you bought a new book you only have one correction to make. If you have a used book check it carefully to see what printing you have, as described in the file, and make the corrections at least up to chapter 13. We will assume that you have done this so that we don't have to warn you about potential problems in the first printing. SECTIONS 1.1-1.3 This may be a good time to read in ``The Little LISPer'': pages xiii and 1-5 or so. 1. (10 points; basic) When you enter the numbers 1 and 5 at the Scheme interpreter's prompt, it prints them for you. Does the Scheme interpreter print everything you enter? What happens when you enter (+ 1 5) to the interpreter? Why doesn't it print 1 and 5? What happens when you enter the following? (+ 7 (+ 1 5)) Why doesn't it print the 6? Write down a description of what the Scheme interpreter does with your input. Distinguish between computing the value of an expression and printing it. Hand in this description. 2. (5 points; basic) Do execrcise 1.2 in the text on paper, then check your answers on the computer. To check your answers for problem 1.2, enter the definitions first, then the various parts. Write a description of how ``define'' and quote (') affect the Scheme interpreter. Refer to parts of exercise 1.2 for examples. Hand in this description. 3. (0 points; suggested practice) Do as many parts of exercises 1.3 and 1.4 as you need to be completely confident and quick. For these problems, it is important to think first, and check your work on the computer. Use the computer for feedback, not to think for you. 4. (10 points) How could the ``who's on first'' program (in the file "/home/cs227/lib/whos-on-first.ss") have used quotation when communicating with you to avoid confusion? What similar kinds of confusion are avoided in Scheme by using quotation? Give an example. 5. (6 points; basic) Suppose alpha, beta, and gamma are three numbers. Translate the following Scheme expressions into the usual arithmetical notation. For example: (- alpha (- gamma beta)) translates into (alpha - (gamma - beta)). a. (/ alpha (/ (+ beta gamma) beta)) b. (- (* alpha beta) (/ beta gamma)) c. (- (* alpha alpha) (* beta beta)) 6. (10 points; basic) On Project Vincent, get into Scheme and type the following lines, substituting your name and your TA's name where indicated. (Lines starting with a semicolon (;) are comments, and ignored by the Scheme interpreter.) (transcript-on "hw1-prob6.out") ;; NAME: TA: ;; homework 1, problem 6 (load "/home/cs227/homework/data/hw1-prob6.so") The last line loads a compiled scheme file, which makes it hard for you to read the variables defined in it, unlike a Scheme source file. (Scheme source file names end in .ss instead of .so.) You are now in the same position as a computer progarm, in that you have access to variables named a-num, b-num, c-num, d-num, and e-num but do not (yet) know what their values are. Using just these variables (not using numbers such as ``9''), write Scheme expressions that return the following values. For example, the expression (- b-num a-num) returns 1. a. 10 b. 38 c. 18 Hand in your transcript. Note the form used in this transcript. SECTION 1.4, CONSTRUCTING LISTS This may be a good time to read in ``The Little LISPer'': pages 8-9. 7. (5 points; basic) Draw pictures like those we have drawn in class for the lists in exercise 1.6. 8. (0 points; suggested practice) Do problem 1.6 and check your answers on the computer. (Don't leave out parts d and e, as they are different from parts a-c.) 9. (6 points; basic) The nesting of lists can be thought of as a tree structure. This is often used in artificial intelligence to do things like representing sentences in English. For example, the sentence ``apple sells it'' could be represented by the list (sentence (np (noun apple)) (vp (verb sells) (object it))) If you format it to show the tree structure more clearly, it looks like the following. (sentence (np (noun apple)) (vp (verb sells) (object it))) (Looked at from the side, this looks vaguely like a tree.) As in the book's problem 1.6, without using quoted lists (that is, using only cons, quoted symbols, and the empty list '()), define the the lists: a. (object it), b. (vp (verb sells) (object it)), and c. (sentence (np (noun apple)) (vp (verb sells) (object it))). Turn in a printout of a file that contains the code to build these and a transcript (of a Scheme session) that loads that file, or a transcript where you built them interactively. You will find it easiest to use define to reuse the answer of part (a) in part (b), and of part (b) in part (c). Thus what you type to the Scheme interpreter for your solution can look like the following. ;; NAME: TA: ;; homework 1, problem 6 (define part-a (cons 'object ...)) part-a (define part-b (cons ... part-a ...)) part-b (define part-c (cons ... part-b ...)) part-c Note that after you define part-a, to check to see if your definition is correct, you have to enter the variable name, part-a, at the Scheme prompt. That is why part-a, by itself, follows the definition of part-a. 10. (8 points) Ben Bittwiddle wonders what lists in Scheme are good for. John McCarthy says ``nearly anything,'' but Ben wants examples. One example is English sentences; we have seen that a sentence can be represented as a list as in the problem above. As another example, we can represent relations (tables) by lists of two-element lists, where the first element of each list is the key and the second is the value. For example, the relation of the colors of a traffic light to their meanings would be represented as follows ((green go) (yellow caution) (red stop)) There is usually more than one way to represent information. For example, one could also represent relations by a list of 2 lists of the same length, one of the keys, and the other of the associated values; with the nth element of the keys list related to the nth element of the values list. For example, with this representation the traffic light meaning relation would be represented as the following list. ((green yellow red) (go caution stop)) Show Ben at least one way to represent the following kinds of information as lists. For each one, give the general pattern in English, and how our example would be represented. (Don't use cons, just show us how the example values would look, as in our examples above.) a. Numbers with units. For example, 3 minutes. b. The time of day. For example, 3:10 PM. c. Information about countries of the world, whether they belong to the United Nations, and the year they were admitted. For example, USA is a charter member, France is a charter member Vatican City is not a member, Switzerland is not a member, Poland has been a member since 1945. d. A catalog of a collection of records or compact disks, organized by type of music. For example, rock music: Abbey Road by The Beetles, 25 or 6 to 4 by Chicago jazz: Newport in New York by various artists, Take the A Train by Ellington, classical: Symphony number 9 in D by Beethoven, Piano concerto in a-minor by Grieg, Fanfare for Stadt Wein by R. Strauss To see if your answer is good, ask yourself if you can tell someone (or Scheme) how to extract all the relevant information. In parts (c) and (d), make sure you can do this for examples of different sizes. 11. (6 points; extra credit only) A fascinating feature of Scheme (and LISP) is that Scheme programs are also represented as lists in Scheme. Show how to construct Program 2.1 as a list in Scheme. SECTION 1.5, TAKING LISTS APART This may be a good time to read in ``The Little LISPer'': pages 5-8 and 10-13. 12. (0 points; suggested practice) Do problems 1.9 (page 22), 1.10 and 1.11 (page 25). Check your answers on the computer. 13. (0 points; suggested practice) Do as many parts of problem 1.12 as you need to feel comfortable and confident with car and cdr. Check your answers on the computer. 14. (8 points; basic) The ability to extract parts of a list using car and cdr is important in writing procedures that manipulate interesting list structures. In this problem, you are to write an expression around a given list, so that the entire expression returns the symbol it. We say that the expression ``extracts the symbol it from the list.'' For example, we can extract the symbol it from the list (walk (slowly towards) it) using the expression (car (cdr (cdr '(walk (slowly towards) it)))). (See also exercise 1.13.) Write expressions using car and cdr to extract the symbol ``it'' from the following lists. a. (I he she it we they) b. ((english it) (german das)) c. ((verb go) (pronoun it)) d. ((whatever) ((I am) (against it))) Hand in a printout of a transcript (of a Scheme session) with your answers clearly labeled by comments, showing that your expression works. For example, our example of extracting ``it'' from (walk (slowly towards) it) would be typed as ;; homework 1, problem 14 example (define example-for-14 '(walk (slowly towards) it)) (car (cdr (cdr example-for-14))) 15. (0 points; suggested practice) Do problems 1.14 and 1.15. 16. (10 points) In this problem you will do the same thing as in the previous problem, but with hidden data. Start Scheme, and start a transcript. Then load the file /home/cs227/homework/data/hw1-prob15.so by entering (load "/home/cs227/homework/data/hw1-prob16.so") Follow the program's prompts to extract the symbol ``it'' from the lists as directed. Hand in your transcript. We won't mark you down for getting a less than perfect score in this game, but we will take off if you don't play it through to the end. It may be frustrating at first, but it should help you put yourself in the computer's place. 17. (0 points; suggested practice) For more practice in the car-cdr game of problem 16, load the file (load "/home/cs227/homework/data/hw1-prob17.so") 18. (10 points; extra credit only) Show how to encode something from one of your other classes as a list. For example, if Chemistry, you might show how to encode the atomic formula for a compound. In mathematics, you might show how to encode the kind of facts you are learning (like the derivative of x squared is 2x). For a foreign language class, you might show how to encode a vocabularly list, or some grammatical rules (such as how to spell plurals).