Com S 342 --- Principles of Programming Languages HOMEWORK 1: INDUCTION and RECURSION (File $Date: 1997/09/18 17:22:38 $) Due: problems 1-2, 5-6 at beginning of your discussion section, September 11; problems 7, 9 at beginning of class on September 15; problems 14-17 at beginning of your discussion section, September 18. problem 11 at beginning of class, September 19. In this homework, you will learn (or recall what you know) about induction and recursion; this topic is the foundation of the functional style of programming. It includes the vitally important topic of recursion over grammars, which is fundamental to programming interpreters. You will also write some operations on sets that will be of use later, and will learn about types. 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/hw1.tst 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 directions in $PUB/homework/hw1.tst/README. *No* credit will be given for Scheme programming problems unless you hand in a transcript that includes our tests. Each definition must have a comment of the form (define whatever ; TYPE: ... ...) that gives the type of the name (whatever) being defined. See the file $PUB/docs/type-notation.txt for details on the type notation you are to use. These comments 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. If you like, you can use the type-checker in $PUB/lib/type-check.scm or the type-checked read-eval-print loop in $PUB/lib/type-check-and-eval.scm to help you with these, but it's best if you learn how to do this yourself and just use these to check your work. The section headings below give the readings related to the problems. (Please read them!) ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.1 1. (5 points) Do exercise 2.1.1 in the text. [syntactic derivation] (This can be handwritten) 2. (5 points) Do exercise 2.1.2 in the text. [Kleene * and +] (This can be handwritten) 3. (suggested practice) Do exercise 2.1.3 in the text. [syntactic derivation] 4. (15 points, extra credit) Do exercise 2.2.1 in the text. [error checking] ESSENTIALS OF PROGRAMMING LANGUAGES: Section 2.2 5. (5 points) Do exercise 2.2.2 in the text. [change to remove-first] (This can be handwritten) 6. (5 points) Do exercise 2.2.3 in the text. [change to remove] (This can be handwritten) 7. (25 points) [set-ops] In this problem you will write procedures to operate on the ADT of sets. Let us implement sets as lists WITHOUT duplicate elements. To get you started, here are some operations on sets with that representation. (Note that `set-of' uses `set-add', which you are to write; so it won't work until you define `set-add'.) (define the-empty-set ; TYPE: (set T) '()) (define set-empty? ; TYPE: (-> ((set T)) boolean) (lambda (s) (null? s))) (define set-size ; TYPE: (-> ((set T)) number) (lambda (s) (length s))) (define set-of ; TYPE: (-> (T ...) (set T)) (lambda args (if (null? args) the-empty-set (set-add (car args) (apply set-of (cdr args)))))) (define set-member? ; TYPE: (-> (T (set T)) boolean) (lambda (e S) (and (not (set-empty? S)) (or (equal? e (car S)) (set-member? e (cdr S)))))) (define set-one-elem ; TYPE: (-> ((set T)) T) (lambda (s) ; REQUIRES: s is not empty (car s))) (define set-rest ; TYPE: (-> ((set T)) (set T)) (lambda (s) ; REQUIRES: s is not empty (cdr s))) (define set-subset? ; TYPE: (-> ((set T) (set T)) boolean) (lambda (S1 S2) (or (set-empty? S1) (and (set-member? (set-one-elem S1) S2) (set-subset? (set-rest S1) S2))))) (define set-equal? ; TYPE: (-> ((set T) (set T)) boolean) (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 types follow after the colon on each line). set-add: (-> (T (set T)) (set T)) set-remove: (-> (T (set T)) (set T)) set-union: (-> ((set T) (set T)) (set T)) set-minus: (-> ((set T) (set T)) (set T)) set-intersect: (-> ((set T) (set T)) (set T)) The operation `set-add' inserts an item into a set, `set-remove' takes an item out of a set (or returns its argument if the element was not in the set to begin with), `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, and `set-intersect' returns the set of elements that are elements of both sets. Note that the expression (set-of 2 3 1) evaluates to the set containing 1, 2 and 3. The procedure set-of is given above. The following are examples illustrating these operations. (set-equal? (set-add 1 (set-of 2 3)) (set-of 1 2 3)) ==> #t (set-equal? (set-add 1 (set-of 2 3 1)) (set-of 1 2 3)) ==> #t (set-equal? (set-remove 1 (set-of 2 3 1)) (set-of 3 2)) ==> #t (set-equal? (set-remove 1 (set-of 2 3 4 8)) (set-of 3 2 4 8)) ==> #t (set-equal? (set-union (set-of 'a 'b) (set-of 'c 'd)) (set-of 'a 'b 'c 'd)) ==> #t (set-equal? (set-union (set-of 'a 'b 'c) (set-of 'c 'd)) (set-of 'a 'b 'c 'd)) ==> #t (set-equal? (set-minus (set-of 'a 'b) (set-of 'c 'd)) (set-of 'a 'b)) ==> #t (set-equal? (set-minus (set-of 'a 'b 'c) (set-of 'c 'a 'd)) (set-of 'b)) ==> #t (set-equal? (set-intersect (set-of 'a 'b) (set-of 'c 'd)) the-empty-set) ==> #t (set-equal? (set-intersect (set-of 'a 'b 'c) (set-of 'c 'a 'd)) (set-of 'a 'c)) ==> #t Make a file `set-ops.scm' containing your procedures and the ones provided above. In your solution you may not modify any of the provided procedures. If you are new to Scheme (or want to save time) you should write and test each of your procedures one by one. After doing your own testing on the procedures you have written, you must test your code as follows: (you have to be in your own directory for this) If you are using the Com S machines, and have the directory $PUB/bin (/home/course/cs342/public/bin) in your PATH, start the interpreter, scm342, by typing at the shell prompt scm342 Load your procedures: (load "set-ops.scm") Then start a transcript (This creates a file `set-ops.out'.): (transcript-on "set-ops.out") ; Name: ; Section: Then execute our test by typing: (test-hw1 "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 sending the following lines to Scheme: (transcript-off) (exit) 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). Be sure to include a type comment for each definition in your code. If you aren't on the Com S machines, see the directions in $PUB/homework/hw1.tst/README. No credit will be given unless you hand in a transcript that includes our tests. 8. (suggested practice) Do exercise 2.2.4 in the text. [why does subst recursion halt?] 9. (5 points) Do exercise 2.2.5 in the text. [subst-with-map using map] Call your procedure subst-with-map. The type of subst-with-map is the following, which should appear as a comment in your code. (-> (symbol symbol s-list) s-list) You only have to use map once in your code. (Note that map has type (-> ((-> (S) T) (list S)) (list 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-hw1 "subst-with-map") Print the file 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). 10. (15 points; extra credit) Do exercise 2.2.6 in the text. [prove partial-vector-sum correct] 11. (15 points (5 points each)) Do exercise 2.2.7 in the text, parts 3 [list-index], 4 [vector-index], and 5 [ribassoc]. When you write vector-index, don't convert the vector to a list and then back to a vector. That's too inefficient and doesn't give you practice with the tail recursion pattern. Also, you are encouraged to use any previously defined procedures as helping procedures. Many times throughout the course (although not always) the homework problems are specifically selected so you will have helping procedures for future homework problems. Be sure to include type comments in each procedure. For example the comment for list-index should read as follows. ; TYPE: (-> (symbol (list symbol)) number) As another example, the comment for ribassoc should read as follows. ; TYPE: (-> (symbol (list symbol) (vector datum) datum) datum) After doing your own testing on the procedures you wrote, you must test your code as for problem 7 above. That is, start the interpreter, scm342, by typing at the shell prompt (you have to be in your own directory for this): scm342 Then start a transcript and run the tests by typing to Scheme: (transcript-on "hw1-11.out") (test-hw1 "list-index") (test-hw1 "vector-index") (test-hw1 "ribassoc") (If you get errors that appear to be in our files, they are probably problems in your code...) You can also add your own test cases to the output by running them now if you want. Now if you are satisfied, you can stop by typing to Scheme: (transcript-off) (exit) Print the file hw1-11.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 2.2.7 in the text, parts 7 [product] and 9 [rotate]. 13. (suggested practice) Do exercise 2.2.8 in the text, parts 1 [down], 2 [up], and 5 [merge]. 14. (10 points) Do exercise 2.2.7 in the text, part 8 [swapper]. Hint: you can use map for this. After doing your own testing on the procedures you wrote, you must test your code as for problem 7 above. Use (test-hw1 "swapper") Be sure to include a type comment for each definition in your code. 15. (5 points) Write a procedure swap-symbol-expression with type (-> (symbol symbol symbol-expression) symbol-expression) that 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 easy if you organized swapper as discussed in the text and in class.) For examples, consider the following. (swap-symbol-expression 'a 'b 'a) ==> b (swap-symbol-expression 'a 'b 'b) ==> a (swap-symbol-expression 'x 'y '(a b c x y x)) ==> (a b c y x y) (swap-symbol-expression 'x 'y '((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-hw1 "swap-symbol-expression") Be sure to include a type comment for each definition in your code. 16. (20 points (10 points each)) More practice with symbol-expressions. Use two procedures for each problem. a. Write a procedure, count-occurrences, that takes a symbol, s, and a symbol-expression, sym-exp, and returns the number of occurrences of s in sym-exp. For example: (count-occurrences 'x 'x) ==> 1 (count-occurrences 'x 'y) ==> 0 (count-occurrences 'x '(x () y (x))) ==> 2 b. Write a procedure, flatten, that takes a symbol-expression, sym-exp, and returns a list of all the symbols that occur in sym-exp. For example: (flatten 'x) ==> (x) (flatten '(x (((y))))) ==> (x y) (flatten '(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-hw1 "count-occurrences") (test-hw1 "flatten") Be sure to include a type comment for each definition in your code. 17. (40 points (20 each)) Our type notation uses a subset of the following grammar (where the {...}* below is the Kleene star, not a terminal symbol). ::= | | ::= number | boolean | string | character | symbol ::= S | T | U | V | W | X | Y | Z ::= (-> ({}*) ) In this problem you will program the following operations on lists that represent s according to the above grammar. (Hint: make your program follow the grammar!) a. Write a procedure polymorphic?: (-> (type) boolean) that returns #t if and only if the type passed contains a . For example, (polymorphic? 'number) ==> #f (polymorphic? 'boolean) ==> #f (polymorphic? 'character) ==> #f (polymorphic? 'T) ==> #t (polymorphic? 'S) ==> #t (polymorphic? '(-> (U) boolean)) ==> #t (polymorphic? '(-> (number) T)) ==> #t (polymorphic? '(-> ((-> (V) W)) V)) ==> #t (polymorphic? '(-> (number T) character)) ==> #t (polymorphic? '(-> (symbol boolean) string)) ==> #f b. Write a procedure instantiate: (-> (type-variable type type) type) that takes a symbol representing a , tv, and two s val and typ, and returns typ with all occurrences of tv replaced by val. For example (instantiate 'T 'number 'boolean) ==> boolean (instantiate 'T 'number 'number) ==> number (instantiate 'T 'number 'string) ==> string (instantiate 'T 'boolean 'T) ==> boolean (instantiate 'T 'string 'S) ==> S (instantiate 'T 'number '(-> (S T S) S)) ==> (-> (S number S) S) (instantiate 'T '(-> (T) T) '(-> (S T S) S)) ==> (-> (S (-> (T) T) S) S) After doing your own testing on the procedures you wrote, you must test your code as for problem 7 above. Use (test-hw1 "polymorphic?") (test-hw1 "instantiate") Be sure to include a type comment for each definition in your code. 18. (15 points; extra credit) Do exercise 2.2.9 in the text, part 3 [car&cdr2] 19. (15 points; extra credit) Do exercise 2.2.9 in the text, part 4 [compose] Test your code as described above for problem 10. 20. (suggested practice) Do exercise 2.2.9 in the text, parts 1 [path], 2 [car&cdr], 5 [sort], and 6 [sort]. 21. (50 points, extra credit) Extend your code for the procedures polymorphic? and instantiate, from homework 1 problem 17, to deal with the entire grammar for our type notation, as given below. ::= | | | | ::= number | boolean | string | character | symbol | void | datum | poof | ::= any symbol except one of the s ::= S | T | U | V | W | X | Y | Z ::= (-> ({}*) ) ::= (list ) | (pair ) | (vector ) ::= (and {}+)