Com S 342 --- Principles of Programming Languages HOMEWORK 2: INDUCTION and RECURSION (File $Date: 2004/02/19 04:22:26 $) Due: problems 1-2, 5-6, on Feb. 17, 2004; problems 7, 9, 11, 13-15 on Feb. 19, 2004. problem 17 on Feb. 24, 2004 In this homework, you will learn (or recall what you know) about induction and recursion; this topic is one foundation of the functional style of programming. It includes the vitally important topic of recursion over grammars, which is fundamental to programming interpreters (since languages are specified using grammars). Remember the motto: "follow the grammar!" You will also learn about types and type checking and write some operations on sets that will be of use later. 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 the directory $PUB/homework/hw2 for test data for each coding problem, as described in problem 7 below. (Recall that $PUB means /home/course/cs342/public/.) This applies even if you aren't using the Com S machines. (If you're not, see the course web page for hints.) *No* credit will be given for Scheme programming problems unless you also hand in a transcript that includes our tests. For this homework, all your code should type check. Each use of define must also be accompanied by a deftype, so that your code has the form: (deftype whatever ...) (define whatever ...) That is, the deftype gives the type of the name (whatever) being defined. See the type notation document available from the course resources web page for details on the type notation you are to use. The type checker and these use of deftypes are to help you learn to think about the types of what you are writing, something that will help you avoid mistakes in the future. Although the type checker you get from using scheme342typed will help you with writing deftypes, it's best if you learn how to do this yourself and just use the type checker to check your work. You are not permitted to use trustme! or has-type-trusted in the typed interpreter problems. Don't use the parse-* helpers in your code either. The section headings below give the readings related to the problems. (Please read them!) ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.1 1. (5 points) [syntactic derivation] Write a syntactic derivation that proves (3 . (4 . (2 . ()))) is a list of numbers, using the first grammar on page 4 in the text (i.e., in Essentials of Programming Languages, second edition). (This can be handwritten) 2. (5 points) [Kleene * and +] Do exercise 1.2 on p. 7 in the text. (This can be handwritten) 3. (suggested practice) [syntactic derivation] Do exercise 1.3 on p. 7 in the text. ESSENTIALS OF PROGRAMMING LANGUAGES: Section 1.2 THE LITTLE SCHEMER, CHAPTERS 2-4 (especially chapter 3) 4. (15 points, extra credit) [error checking] Do exercise 1.5 on p. 14 in the text. 5. (5 points) [change to remove-first] Do exercise 1.8 on p. 18 in the text. (This can be handwritten) 6. (5 points) [change to remove] Do exercise 1.9 on p. 19 in the text. (This can be handwritten) 7. (35 points) [set-ops] In this problem you will write procedures to operate on the ADT of sets. We will implement sets as lists, as noted in the `defrep' declaration below. However, we will use lists *without* duplicate elements. Duplicates are defined by Scheme's `equal?' operation; that is, we consider x to be a duplicate of y if (equal? x y) is true. To get you started, here are some operations on sets with that representation. (Note that `set' uses `set-add', which you are to write; so it won't work, or type check, until you define `set-add'.) (defrep (forall (T) (set-of T)) (forall (T) (list-of T))) (deftype the-empty-set (forall (T) (set-of T))) (define the-empty-set '()) (deftype set-empty? (forall (T) (-> ((set-of T)) boolean))) (define set-empty? (lambda (s) (null? s))) (deftype set-size (forall (T) (-> ((set-of T)) number))) (define set-size (lambda (s) (length s))) (deftype set (forall (T) (-> (T ...) (set-of T)))) (define set (lambda args (if (null? args) the-empty-set (set-add (car args) (apply set (cdr args)))))) (deftype set-member? (forall (T) (-> (T (set-of T)) boolean))) (define set-member? (lambda (e S) (and (not (set-empty? S)) (or (equal? e (car S)) (set-member? e (cdr S)))))) (deftype set-one-elem (forall (T) (-> ((set-of T)) T))) (define set-one-elem (lambda (s) ;; REQUIRES: s is not empty (car s))) (deftype set-rest (forall (T) (-> ((set-of T)) (set-of T)))) (define set-rest (lambda (s) ;; REQUIRES: s is not empty (cdr s))) (deftype set-subset? (forall (T) (-> ((set-of T) (set-of T)) boolean))) (define set-subset? (lambda (S1 S2) (or (set-empty? S1) (and (set-member? (set-one-elem S1) S2) (set-subset? (set-rest S1) S2))))) (deftype set-equal? (forall (T) (-> ((set-of T) (set-of T)) boolean))) (define set-equal? (lambda (S1 S2) (and (set-subset? S1 S2) (set-subset? S2 S1)))) Your task is to write a procedure for each of the following operations on sets (whose deftypes are given below). (deftype set-add (forall (T) (-> (T (set-of T)) (set-of T)))) (deftype set-remove (forall (T) (-> (T (set-of T)) (set-of T)))) (deftype set-union (forall (T) (-> ((set-of T) (set-of T)) (set-of T)))) (deftype set-minus (forall (T) (-> ((set-of T) (set-of T)) (set-of T)))) (deftype set-intersect (forall (T) (-> ((set-of T) (set-of T)) (set-of T)))) (deftype set-union-list (forall (T) (-> ((list-of (set-of T))) (set-of T)))) (deftype set-union* (forall (T) (-> ((set-of T) ...) (set-of T)))) The operation `set-add' inserts an item into a set, `set-remove' takes an item out of a set (or returns its set argument unchanged if the element argument was not in the set argument), `set-union' returns the union of its two arguments as a set (i.e., without duplicates), `set-minus' returns the set of all elements such that every element of the result is an element of the first set argument, but no element of the result is an element of the second set argument, `set-intersect' returns the set of elements that are elements of both sets, `set-union-list' gives the union of all the sets in its argument list, and `set-union*' is the variable argument version of set-union-list. Note that the expression (set 2 3 1) evaluates to the set containing 1, 2 and 3. The code for procedure set is given above. The following are examples illustrating these operations. (set-equal? (set-add 1 (set 2 3)) (set 1 2 3)) ==> #t (set-equal? (set-add 1 (set 2 3 1)) (set 1 2 3)) ==> #t (set-equal? (set-remove 1 (set 2 3 1)) (set 3 2)) ==> #t (set-equal? (set-remove 1 (set 2 3 4 8)) (set 3 2 4 8)) ==> #t (set-equal? (set-union (set 'a 'b) (set 'c 'd)) (set 'a 'b 'c 'd)) ==> #t (set-equal? (set-union (set 'a 'b 'c) (set 'c 'd)) (set 'a 'b 'c 'd)) ==> #t (set-equal? (set-minus (set 'a 'b) (set 'c 'd)) (set 'a 'b)) ==> #t (set-equal? (set-minus (set 'a 'b 'c) (set 'c 'a 'd)) (set 'b)) ==> #t (set-equal? (set-intersect (set 'a 'b) (set 'c 'd)) the-empty-set) ==> #t (set-equal? (set-intersect (set 'a 'b 'c) (set 'c 'a 'd)) (set 'a 'c)) ==> #t (set-equal? (set-union-list (list (set 'a 'b) (set 'c 'd))) (set 'a 'b 'c 'd)) ==> #t (set-equal? (set-union-list (list (set 'a) (set 'b 'c) (set 'c 'a))) (set 'a 'b 'c)) ==> #t (set-equal? (set-union* (set 'a 'b) (set 'c 'd) (set)) (set 'a 'b 'c 'd)) ==> #t (set-equal? (set-union* (set 'a) (set 'b 'c) (set 'c 'a)) (set 'a 'b 'c)) ==> #t (set-equal? (set-union* ) (set )) ==> #t Make a file `set-ops.scm' containing the code we have provided above, and your own procedure definitions. You should start by copying the file $PUB/homework/hw2/set-ops.scm to your directory: cp $PUB/homework/hw2/set-ops.scm . In your solution you may not modify any of the provided procedures. To save yourself time, you should write and test each of your procedures one by one. It really will save time to test your code yourself; just trying to run our test cases will be frusrating, because you won't have much idea of what went wrong. After doing your own testing on the procedures you have written, 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 set-ops.out Then, assuming you have the directory $PUB/bin (/home/course/cs342/public/bin) in your PATH, start the typed interpreter, scheme342typed, by typing at the shell prompt scheme342typed Now load your code: (load "set-ops.scm") Then execute our test by typing: (test-hw2 "set-ops") (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 `set-ops.out' and hand that in with your printout of the code in `set-ops.scm'. Be sure your name appears in a comment in your code (as in homework 0). See homework 0 for other ways to make transcripts. If you aren't on the Com S machines, see the directions in the file $PUB/homework/hw2.tst/README.txt You can also edit and print at home but test on ISU's machines if you want. No credit will be given unless you hand in a transcript that includes our tests. 8. (suggested practice) [flat recursion over lists] Do exercise 1.15 on pp. 24-25 in the text, whichever of parts 1-5 [duple, invert, filter-in, every?, exists?] or 9 [down] seem interesting. Which of these can you do using Scheme's `map' procedure? 9. (10 points) [merge] Do exercise 1.16 on p. 26 in the text, part 5 [merge]. You can assume that the argument lists are sorted in ascending order. The type of merge is given by the following. (deftype merge (-> ((list-of number) (list-of number)) (list-of number))) After doing your own testing on the procedure merge you must test your code as for problem 7 above, using (test-hw2 "merge") Print your transcript, merge.out, and hand that in with your printout of the code. Be sure your name appears in a comment in your code (as in homework 0). ESSENTIALS OF PROGRAMMING LANGUAGES, pp. 19-20 THE LITTLE SCHEMER, CHAPTER 5 10. (suggested practice) [why does subst recursion halt?] Do exercise 1.10 on p. 21 in the text. 11. (5 points) [subst-with-map using map] Do exercise 1.12 on p. 21 in the text. Call your procedure subst-with-map. You should start by copying the code in $PUB/lib/subst.scm, since that version type checks. Use the following deftype in your code: (deftype subst-with-map (-> (symbol symbol (list-of sym-exp)) (list-of sym-exp))) You only have to use map once in your code. Note that map has type following type: (forall (S T) (-> ((-> (S) T) (list-of S)) (list-of T))) After doing your own testing on the procedure subst-with-map you wrote, you must test your code as for problem 7 above, using (test-hw2 "subst-with-map") Print your transcript, subst-with-map.out, and hand that in with your printout of the code. Be sure your name appears in a comment in your code (as in homework 0). 12. (suggested practice) Do exercise 1.16 on p. 26 in the text, part 1 [up]. Either don't use the type checker, or consider `up' to take a s-list and use the helpers in $PUB/lib/sym-exp.scm to get it to type check. 13. (10 points) Do exercise 1.16 on p. 26 in the text, part 2 [swapper]. This is an s-list problem, so use the helpers in $PUB/lib/sym-exp.scm to get your code to type-check. For example, put (load-quietly "sym-exp.scm") in your code. After doing your own testing on the procedures you wrote, you must test your code as for problem 7 above. Use (test-hw2 "swapper") This test case assumes that you have already loaded $PUB/lib/sym-exp.scm. Be sure to include a deftype for each definition in your code. Don't use parse-s-list or parse-sym-exp in your code. 14. (5 points) Write a procedure swap-sym-exp whose deftype is (deftype swap-sym-exp (-> (symbol symbol sym-exp) sym-exp)) The procedure swap-sym-exp takes symbols s1 and s2 and returns a symbol-expression with all occurrences of s1 replaced by s2 and likewise with all occurrences of s2 replaced by s1. See p. 47 for the grammar for symbol-expression. (Hint: this should be *very* easy if you organized swapper as discussed in the text and in class.) For examples, consider the following. (swap-sym-exp 'a 'b (parse-sym-exp 'a)) ==> b (swap-sym-exp 'a 'b (parse-sym-exp 'b)) ==> a (swap-sym-exp 'x 'y (parse-sym-exp '(a b c x y x))) ==> (a b c y x y) (swap-sym-exp 'x 'y (parse-sym-exp '((x) () y (z (x))))) ==> ((y) () x (z (y))) After doing your own testing on the procedures you wrote, you must test your code as for problem 7 above. Use (test-hw2 "swap-sym-exp") Be sure to include a deftype for each definition in your code. Don't use parse-s-list or parse-sym-exp in your code. 15. (20 points (10 points each)) More practice with symbol-expressions. Use two procedures for each problem. Again, use the helpers in $PUB/lib/sym-exp.scm by putting (load-quietly "sym-exp.scm") at the top of your solution. Don't use parse-s-list or parse-sym-exp in your code. a. Write a procedure, occurs?, that takes a symbol, s, and a sym-exp, symexp, and returns #t if s occurs in symexp and #f otherwise. For example: (occurs? 'x (parse-sym-exp 'x)) ==> #t (occurs? 'x (parse-sym-exp 'y)) ==> #f (occurs? 'x (parse-sym-exp '(z () q (() (x))))) ==> #t b. Write a procedure, flatten, that takes a sym-exp, symexp, and returns a list of all the symbols that occur in symexp, in left-to-right order. For example: (flatten (parse-sym-exp 'x)) ==> (x) (flatten (parse-sym-exp '(x (((y)))))) ==> (x y) (flatten (parse-sym-exp '(x () y (x)))) ==> (x y x) After doing your own testing on the procedures you wrote, you must test your code as for problem 7 above. Use (test-hw2 "occurs") (test-hw2 "flatten") For this problem, write a deftype for each recursive procedure definition in your code. ESSENTIALS OF PROGRAMMING LANGUAGES, Section 1.2.3 STRUCTURE AND INTERPRETATION OF COMPUTER PROGRAMS, Section 1.2.1 16. (15 points; extra credit) [prove partial-vector-sum correct] Do exercise 1.14 on p. 24 in the text. 17. (10 points) [vector-index] Write a procedure, vector-index, that takes a predicate, pred, and a vector, v, and returns the zero-based index of the first element of v that satisfies pred, or -1 if no element of v satisfies pred. The type of vector-index is thus as follows: (deftype vector-index (forall (T) (-> ((-> (T) boolean) (vector-of T)) number))) For example, (vector-index zero? '#(9 8 0 1 0 3 0)) ==> 2 (vector-index zero? '#(9 8 7 1 3)) ==> -1 (vector-index odd? '#()) ==> -1 (vector-index odd? '#(2 2 2 2 2 2 2 2 2 2 2 2 3 4 2)) ==> 12 You should use tail recursion, and without using Scheme's procedures vector->list or list->vector. After doing your own testing you must test your code as for problem 7 above. After starting a transcript as above, run the tests by typing to Scheme: (test-hw2 "vector-index") Print the transcript and hand that in with your printout of the code. Be sure your name appears in a comment in your code (as in homework 0). 18. (15 points; extra credit) [vector-append-list] Do exercise 1.15 part 10 on p. 25 in the text, except that your code only has to work for vectors and lists of numbers. That is, the type of vector-append-list will be given by: (deftype vector-append-list (-> ((vector-of number) (list-of number)) (vector-of number))) You should use tail recursion on this problem. Hint: use make-vector with two arguments to make a vector whose length is the first argument, for example: (make-vector 7 0) ==> #(0 0 0 0 0 0 0). You will also need to use vector-set! 19. (suggested practice) Do exercise 1.17 on p. 27 in the text [path, sort]. 20. (15 points; extra credit) [car&cdr2] Do exercise 1.18 on p. 27 in the text, part 3 If type checking this is too hard, use the untyped interpreter, scheme342untyped. 21. (10 points, extra credit) Find a mistake or bug in the type checker that is not recorded in $PUB/lib/type-check-to-do.txt or $PUB/lib/type-check-bugs*.tst, and send mail to leavens@cs.iastate.edu illustrating the problem with a small example.