Com S 342 --- Principles of Programming Languages HOMEWORK 1: SCHEME BASICS (File $Date: 2004/01/22 23:10:48 $) Due: problem 1 at beginning of class on Tuesday January 27, 2004; problems 3 and 5 at beginning of class on Thursday January 29, 2004. In this homework, you will learn some of the basics of Scheme and functional programming (in particular, a bit about flat recursion). 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 (see homework 0 for instructions on how to make transcripts). This applies even if you aren't using the department machines. (If you're not, see the directions in course "running Scheme" web page.) *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 TAs to comment on your coding style. You should use the course interpreter, scheme342, for these problems. A few of the problems required to use the interpreter, scheme342typed, which provides type checking. 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. Note: don't use the typed interpreters for this problem, as several parts will cause type errors. Instead use the untyped interpreters (which are the current defaults for scheme342 and scm342). a. (5 points) Translate the following algebraic formulas into Scheme's notation. Your answer may be handwritten, however you may want to check it with the Scheme interpreter. (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. (This can be handwritten.) IMPORTANT: Make a transcript for parts c, 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 -- a semicolon (;) up to a newline is a Scheme comment -- in your transcript, or by giving some handwriting on your printout.) c. (5 points) Give definitions of the variables e and pi in Scheme, so that they approximate to the usual values (2.73... and 3.14...). d. (5 points) Write an if-expression in Scheme that uses both variables e and pi, and that has as its value the larger of the two variables. e. (5 points) Write a similar if-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), and unquoted versions of expressions. In English, 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? (You may want to look at the Revised^5 Report on Scheme, see the course resource web page, for some hints on this.) 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. (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)). Note: don't use the typed interpreters for this problem. 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 '()) '())) Note: don't use the typed interpreters for this problem. 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 typing (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. (Hint: you may want to use define.) n. (5 points) What are the differences between a vector and a list in Scheme? What is a vector like in C or C++? How is a Scheme vector different than the corresponding feature 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. Note: assume that you are using the untyped interpreters for this problem. > (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) Use the computer to check your work, but don't do this on the computer at first. Be sure not to use the typed interpreter, instead use the untyped interpreter. What you hand in should be handwritten for this problem. p. (10 points) [eq? and sharing transcript] Fill in the blank lines of the following transcript. > (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) Use the computer to check your work, but don't do this on the computer at first. What you hand in should be handwritten for this problem. q. (10 points) [vector transcript] Fill in the blank lines of the following transcript. > (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) Use the computer to check your work, but don't do this on the computer at first. What you hand in should be handwritten for this problem. 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, l, and returns #t just when each element in the l is a number, and #f otherwise. That is, all-numbers? has the following type: (forall (T) (-> ((list-of T)) boolean)) (See $PUB/docs/typedscm_toc.html, which is also available from the course resources web page for a discussion of the above notation for types.) 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 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.) Put 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: ") (displayln "Section: , ") 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 latter you'll be happy to have this habit. After doing your own testing, you must provide us a transcript of our test cases for your code. You can do this as follows. First, make sure you cd to a directory you own (not $PUB, for example). If you are using the Com S machines, start a transcript by typing at the Unix shell's prompt script all-numbers.out Then, assuming you have the directory $PUB/bin in your PATH, start the typed interpreter, scheme342, by typing at the shell prompt scheme342 (You can, however, use the typed interpreter, scheme342typed, if you wish.) Now load your code (load "all-numbers.scm") Then execute our test by typing: (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 now if you want. When you are satisfied, you can stop by typing the following lines (exit) exit The first stops the Scheme interpreter, the second stops the Unix script. Print the file `all-numbers.out' and hand that in with your printout of the code in `all-numbers.scm'. Be sure your name appears at the top of your code (as described above). (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 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. (10 points; extra credit) [list-of-number] Generalize all-numbers? to a procedure list-of-number? that takes any kind of 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? 342) ==> #f (list-of-number? 'all-numbers) ==> #f (list-of-number? '(3 . 4)) ==> #f (list-of-number? (cons 3 (cons 4 '()))) ==> #t Hint: I needed to use has-type-trusted to get my version of this to type check with the desired type: (-> (datum) boolean). So don't use the type checker on this problem. Normally we won't provide test cases for extra credit problems, but there is one available for this. So hand in a printout of your code and testing with our test cases, as described in the previous problem. 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. That is, occurs-twice? has the following type: (-> (symbol (list-of symbol)) boolean) 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")