Com S 342 --- Principles of Programming Languages HOMEWORK 1: SCHEME BASICS (File $Date: 2006/08/29 13:35:17 $) Due: problem 1, 3-5 at beginning of class on Tuesday, September 5, 2006. In this homework, you will learn some of the basics of Scheme and functional programming (in particular, a bit about flat recursion over lists). All code is to be written in Scheme, using the exact procedure names specified in the problem descriptions. For code hand in *both* your printout of the code and a transcript of testing. This applies even if you aren't using the department machines. *No* credit will be given for Scheme programming problems unless you also hand in a printout of your code and a transcript of its testing. You may not email us to turn in your homework -- we only accept it in printed form. This is to allow the staff to comment on your coding style. You will need to use the course's teachpack for DrScheme, for these problems, in order to do testing. The section headings below give the readings related to the problems. Doing the readings listed now will save you time in the long run. STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS (Sections 1.1.1-1.1.6, 2.2.1-2.2.2, and 2.3.1) THE LITTLE SCHEMER (p. xiii, chapter 1) REVISED^5 REPORT ON THE ALGORITHMIC LANGUAGE SCHEME (Sections 1 [Overview], and 6.1-6.3 [Standard Procedures]) 1. (105 points total) The following is to help you learn Scheme. a. (5 points) Translate the following algebraic formulas into Scheme's notation. Type the translation into Scheme's interaction window for checking. (8 * 7) - (10 + 5) (5 * (4 + (-5 - -3))) (3 / (5 - (1 / 7))) For example, translating (7 - (4 - 5)) into Scheme's notation yields (- 7 (- 4 5)). b. (5 points) Describe in words how to translate an algebraic formula into Scheme's notation. Be sure to handle the general case. IMPORTANT: Make a transcript for parts c, d, e, f, g, i, k, l. *No credit* will be given without a printed transcript. These may be combined into one transcript, but each problem should be clearly labeled and they should be in order. The TA will deduct points (up to 30%) if there is any difficulty in finding and reading your solutions. (Some of these problems also require you to give English answers; you can do this by writing a comment -- text from a semicolon (;) to the next newline is a comment -- in your transcript.) c. (5 points) Using Scheme's define special form, write definitions of the variables e and pi, with approximations to the usual values (2.73... and 3.14...). d. (5 points) Write and evaluate an if (or cond) expression in Scheme that uses both variables e and pi, and that has as its value the larger of the two variables. (That is, if you are using DrScheme, type the expression into the interactions window.) e. (5 points) Evaluate a similar if (or cond) expression that has as its value the smaller of e and pi. f. (5 points) Without using an if (or cond) expression, write an expression that uses both variables e and pi, and that has as its value #t if the values of e and pi are equal, and #f otherwise. g. (5 points) Experiment with ' (quote) in the Scheme interpreter. Try, for example 'e, '+, '(+ 3 4), 'flooglehorn, and unquoted versions of expressions. In English, give a precise answer the following question: what does ' do? h. (5 points) What can you do with a string in Scheme that you can't do with a symbol? Why is there a distinction between strings and symbols in Scheme? (Hint: look at the Revised^5 Report on Scheme, available from the Help in DrScheme and from the course resources web page, to see the operations that Scheme defines for these types.) i. (5 points) Using *only* the Scheme procedure 'list' and numbers and quoted symbols (such as '+, 'sentence, and 'np), write Scheme expressions to make the following lists. Check them with the Scheme interpreter. (Note that the line breaks and indentation in the last of these lists do not matter; the interpreter will print out the value of your answer without this indentation, which is OK. We are asking for you to create the values displayed below, not the printing displayed below. So don't use #\newline or #\space in your answer.) (3 4 2) (+ 1 (- 2 3)) (sentence (np (noun fred)) (vp (verb sells) (object it))) For example, to make the list (3 (5)), one can use the expression (list 3 (list 5)). j. (5 points) Draw box and pointer diagrams, as shown in class or in Figure 2.3 of Abelson and Sussman's book (Structure and Interpretation of Computer Programs), for the above lists. k. (10 points) Using *only* the Scheme procedure cons, numbers, quoted symbols (such as '+, 'sentence, and 'np), and the empty list ('()), write Scheme expressions to make the lists in part i above. For example, to make the list (3 (5)), one can use the expression (cons 3 (cons (cons 5 '()) '())) l. (5 points) Suppose we are writing code for a procedure in which the variable "lst" is bound to a list of numbers. Suppose further that lst has the value (3 4 2). For each of the following, write an expression that uses lst and makes the given list: (5 3 4 2) (6 5 3 4 2) (4 2) (2) You can check your answer on the computer by first evaluating (define lst (list 3 4 2)) m. (5 points) Make a transcript showing that Scheme's car and cdr procedures do not change their arguments. Be sure to show before and after views of lists that you apply car and cdr to. (Hint: you will need to use define.) n. (5 points) What are the differences between a vector and a list in Scheme? How is a Scheme vector different than arrays in C or C++? o. (10 points) [car, cdr, cons transcript] What do each of the following return in Scheme? (I.e., fill in the blanks in the following transcript. Use the computer to check your work, but don't do this on the computer at first. That is, we aren't looking for a transcript for this problem, but for your answers. So, for this part, you can give us a handwritten answer. > (define capitals '((iowa (des moines)) (michigan (lansing)) (florida (talahassee)) (wisconsin (madison)))) > (car (cdr capitals)) > (cadr capitals) > (cdar capitals) > (cadar capitals) > (caadar capitals) > (cdadar capitals) > (car (cdadar capitals)) > (cons 'st (cons 'paul '())) > (cons (cons 'st (cons 'paul '())) '()) > (cons 'minnesota (cons (cons 'st (cons 'paul '())) '())) > (cons (cons 'minnesota (cons (cons 'st (cons 'paul '())) '())) capitals) p. (10 points) [eq? and sharing transcript] Fill in the blank lines of the following transcript. Use the computer to check your work, but don't do this on the computer at first. That is, we aren't looking for a transcript for this problem, but for your answers. So, for this problem, you can give us a handwritten answer. > (define x '(a b)) > (define y '(a)) > (define z (cons x y)) > z > (eq? z (cons x y)) > (equal? z (cons x y)) > (eq? (car z) x) > (equal? (car z) x) > (set-car! x 'q) > x > z > (eq? (cdr z) y) > (set-car! y 'hmm) > y > (cdr z) > (eq? (cdr z) y) q. (10 points) [vector transcript] Fill in the blank lines of the following transcript. Use the computer to check your work, but don't do this on the computer at first. That is, we aren't looking for a transcript for this problem, but for your answers. So, for this problem, you can give us a handwritten answer. > (define vec1 (vector 3 4 2)) > (define vec2 (vector 3 4 2)) > vec1 > (equal? vec1 vec2) > (eq? vec1 vec2) > (vector-set! vec1 0 5) > vec1 > vec2 > (equal? vec1 vec2) > (eq? vec1 vec2) > (define vec3 vec2) > (equal? vec3 vec2) > (eq? vec3 vec2) > (vector-set! vec2 0 6) > vec2 > vec3 > (equal? vec3 vec2) 2. (10 points; extra credit) Considering problems 1(p) and (q) above, summarize the differences between the Scheme procedures eq? and equal? THE LITTLE SCHEMER (Chapter 2) 3. (10 points) [all-numbers] Write a procedure, all-numbers?, which takes a list, lst, and returns #t just when each element in lst is a number, and #f otherwise. For example: (all-numbers? '()) ==> #t (all-numbers? '(3)) ==> #t (all-numbers? '(2 3)) ==> #t (all-numbers? '(1 2 3)) ==> #t (all-numbers? '(not this either?)) ==> #f (all-numbers? '(94 27 hrumphf 42)) ==> #f Note that, because we stated that the argument is a list, your code may assume, without checking, that the argument is a list. (Problem 4 below, however, does not make this assumption.) Save your code in a file `all-numbers.scm' (we omit the question marks in file names because they cause problems on some operating systems). At the top of your code put a version of the following lines, as in homework 0: (displayln "Name: ") To save yourself time, we recommend that you get in the habit of first testing your procedures yourself. This is better than just running our automatic test cases first (see below), because you can control what parts of your code get executed first. It won't make much of a difference for this problem, but later you'll be happy to have this habit. After doing your own testing, you must provide us with a printout of your code and a transcript of our test cases for your code. You can do this in DrScheme, by opening all-numbers.scm in the definitions window, pressing the "Run" button, and then evaluating: (test-hw1 "all-numbers") (If you get errors that appear to be in our files, they are actually problems in your code... Really!) You can also add your own test cases to the output by running them before (or after) our tests. If you want to see more output from our tests, evaluate: (show-test-output!) before running our tests. By default this information is not printed, but it may be helpful if you have errors. When you are satisfied, print the interactions window and your definitions file (all-numbers.scm). Hand a printout of your code and the transcript of your testing. Be sure your name appears at the top of your code and transcript. (See homework 0 for other ways to make transcripts.) If you aren't on the Com S machines, see the directions in the course "running scheme" web page. You can also edit and print at home but test on ISU's machines (or vice versa) if you want. IMPORTANT: No credit will be given unless you hand in a printout of both your code and a transcript that includes our tests. 4. (15 points) [list-of-number] Generalize all-numbers? to a procedure list-of-number? that takes any kind of non-circular data in Scheme and returns #t just when the argument is a list of numbers. For example: (list-of-number? '()) ==> #t (list-of-number? '(3)) ==> #t (list-of-number? '(2 3)) ==> #t (list-of-number? '(1 2 3)) ==> #t (list-of-number? '(not this either?)) ==> #f (list-of-number? '(94 27 hrumphf 42)) ==> #f (list-of-number? 342) ==> #f (list-of-number? 'all-numbers) ==> #f (list-of-number? '(3 . 4)) ==> #f (list-of-number? (cons 3 (cons 4 '()))) ==> #t As always, put your code in a file `list-of-number.scm', and include your identification at the top of your code. (See problem 3.) Hand in a printout of your code and a transcript of testing that includes our test cases, which you can execute using: (test-hw1 "list-of-number") 5. (20 points) [occurs-twice] Write a procedure, occurs-twice?, which takes a symbol, sym, and a list of symbols, los, and returns #t just when sym appears (at least) twice in los, and #f otherwise. For example: (occurs-twice? 'hmm '()) ==> #f (occurs-twice? 'hmm '(hmm)) ==> #f (occurs-twice? 'hmm '(hmm hmm)) ==> #t (occurs-twice? 'other '(hmm hmm)) ==> #f (occurs-twice? 'ah '(ah ha oh but ah)) ==> #t (occurs-twice? 'ah '(uh ah ha oh but ah)) ==> #t (occurs-twice? 'ah '(ah ah ah)) ==> #t (occurs-twice? 'ah '(ha oh but ah oh)) ==> #f (occurs-twice? 'not '(not this either?)) ==> #f Hint: this is easy if you use an appropriate helping procedure. If you write the helping procedure yourself, you should test it separately. As always, put your code in a file `occurs-twice.scm', and include your identification at the top of your code. (See problem 3.) Hand in a printout of your code and a transcript of testing that includes our test cases, which you can execute using: (test-hw1 "occurs-twice") 6. (30 points; extra credit) [downward-triangle] This problem is about creating images using DrScheme. You should go through DrScheme tour especially chapter 4 (this is available in the Help Desk of DrScheme, under the Software bullet, the "Tour" item, or on the web at http://www.drscheme.org/tour/tour-Z-H-5.html). To work with images, you will need to use the teachpack htdp/image.ss, which is found under PLT/teachpack/htdp, where PLT is the directory in which DrScheme is installed. This teachpack is documented under the "Program Design" bullet, the "Teachpacks" item, and then the second item in the list that selects (and also on the web in http://download.plt-scheme.org/doc/352/html/teachpack/image.html.) This teachpack has a built-in procedure for creating an upward-pointing equilateral triangle using the given edge size and color, named triangle. For example: to create upward pointing equilateral triangle of edge size 50 with solid black color, one can execute: (triangle 50 'solid 'black) If this doesn't work, you have to add the teachpack described above. Your task is to write a procedure, downward-triangle, such that (downward-triangle siz clr) draws a downward-pointing equilateral triangle, of edge size, siz, with color given by the symbol, clr. For example: (downward-triangle 30 'black) should create a downward-pointing triangle with edge size 30 that is solid black. (Hint: use overlay procedure to cover up unnecessary areas with white color.) You'll have to test this code yourself. Hand in a printout of your code and your testing.