Com S 342 --- Principles of Programming Languages HOMEWORK 1: INDUCTION and RECURSION (File $Date: 1998/09/21 21:37:59 $) Due: problems 1-2, 5-6 at beginning of class on September 14; problems 7,9,13-16 at beginning of class, September 18; problem 21 at beginning of class, September 23. 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 (since languages are specified using grammars). 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. Although the type checker you get from using scm342 will help you with these, it's best if you learn how to do this yourself and just use the type checker 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) [syntactic derivation] Write a syntactic derivation that proves (3 . (4 . (2 . ()))) is a list of numbers, using the grammar from the top of page 34 in the text. (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. It's important 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 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 interpreter, scm342untyped, by typing at the shell prompt scm342untyped This gets you the untyped interpreter, which will make for smaller transcripts, and will cause fewer complications. However, you can instead use the typed interpreter if you wish. Now load your procedures and insert a comment telling who you are: (load "set-ops.scm") ; 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 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). Be sure to include a type comment for each definition in your code. See homework 0 for other ways to make transcripts. 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. (suggested practice) Do exercise 2.2.7 in the text, parts 7 [product] and 9 [rotate]. 12. (suggested practice) Do exercise 2.2.8 in the text, parts 1 [down], 2 [up], and 5 [merge]. 13. (10 points) Do exercise 2.2.7 in the text, part 8 [swapper]. Hint: you can use map for this. Note that the type checker can't handle this kind of procedure; so don't worry if it's no help. 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. 14. (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))) Note that the type checker can't handle this kind of procedure; so don't worry if it's no help. 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. 15. (20 points (10 points each)) More practice with symbol-expressions. Use two procedures for each problem. Again, the type checker can't handle this kind of procedure; so don't worry if it's no help. a. Write a procedure, occurrs?, that takes a symbol, s, and a symbol-expression, sym-exp, and returns #t if s occurs in sym-exp and #f otherwise. For example: (occurs? 'x 'x) ==> #t (occurs? 'x 'y) ==> #f (occurs? 'x '(z () q (() (x)))) ==> #t 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 "occurs?") (test-hw1 "flatten") Be sure to include a type comment for each definition in your code. 16. (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. 17. (15 points; extra credit) Do exercise 2.2.9 in the text, part 3 [car&cdr2] 18. (15 points; extra credit) Do exercise 2.2.9 in the text, part 4 [compose] Test your code as described above for problem 7. 19. (suggested practice) Do exercise 2.2.9 in the text, parts 1 [path], 2 [car&cdr], 5 [sort], and 6 [sort]. 20. (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 {}+) 21. (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. After starting a transcript as above, run the tests by typing to Scheme: (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 exit Scheme and the transcript as above. 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). 22. (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 and send mail to leavens@cs.iastate.edu illustrating the problem with a minimal (small) example (if possible).