Com S 342 --- Principles of Programming Languages EXERCISE 08: RECURSION OVER SYMBOL EXPRESSIONS AND ATOMIC EXPRESSIONS (File $Date: 2004/02/24 17:49:07 $) The purpose of this exercise is for you to learn about recursion over symbol expressions and atomic expressions. As with all exercises, this is to be done individually. And it is due the day this topic is planned to be discussed in class, unless specified otherwise (see the syllabus at: http://www.cs.iastate.edu/~cs342/syllabus.shtml). As with all exercises, you have two choices for doing the work. You can either: - complete it as specified or - write down questions or problems that you had in trying to complete it. If you write down questions or problems you have, these should be detailed enough so that we can tell that you have read the materials and thought about them. (Don't just write: "I didn't understand how to do it". Instead, say what you tried and what you didn't understand.) During the class where this exercise is discussed, you should ask about these difficulties, and clear them up. Don't be shy; there will be other people with the same problem, and everyone can learn by discussing these issues. And you'll most likely see similar things on the homework, so it's best to understand them now. 1. [sym-exp-map] Write a Scheme procedure, sym-exp-map, with type declaration: (deftype sym-exp-map (-> ((-> (symbol) symbol) sym-exp) sym-exp)) that takes a procedure, p, of type (-> (symbol) symbol), and a sym-exp, se, and returns a sym-exp that is formed by applying p recursively to each symbol in se. You should do this by using the helping procedures in $PUB/lib/sym-exp-cooked.scm. These have the same names as the procedures in the familiar $PUB/lib/sym-exp.scm, but they use a different representation for symbol expressions. Your code should type check. The examples below on the following rely on the following additional definitions: (deftype y-to-z (-> (symbol) symbol)) (define y-to-z (lambda (s) (if (eq? s 'y) 'z s))) (deftype make-swapper (-> (symbol symbol) (-> (symbol) symbol))) (define make-swapper (lambda (a b) (lambda (s) (cond ((eq? s a) b) ((eq? s b) a) (else s))))) Note that the following examples show the output using $PUB/lib/sym-exp-cooked.scm. (sym-exp-map y-to-z (parse-sym-exp '())) = (parse-sym-exp '()) (sym-exp-map y-to-z (parse-sym-exp 'y)) = (parse-sym-exp 'z) (sym-exp-map y-to-z (parse-sym-exp 'x)) = (parse-sym-exp 'x) (sym-exp-map y-to-z (parse-sym-exp '(v w x y))) = (parse-sym-exp '(v w x z)) (sym-exp-map y-to-z (parse-sym-exp '(w () (((x))) (() y) () x (() (y) ((() v)))))) = (parse-sym-exp '(w () (((x))) (() z) () x (() (z) ((() v))))) (sym-exp-map (make-swapper 'x 'y) (parse-sym-exp '())) = (parse-sym-exp '()) (sym-exp-map (make-swapper 'x 'y) (parse-sym-exp 'y)) = (parse-sym-exp 'x) (sym-exp-map (make-swapper 'x 'y) (parse-sym-exp 'x)) = (parse-sym-exp 'y) (sym-exp-map (make-swapper 'x 'y) (parse-sym-exp '(v () ((w x (y ())))))) = (parse-sym-exp '(v () ((w y (x ()))))) (sym-exp-map (make-swapper 'x 'y) (parse-sym-exp '(w () x (((y (()))) x ((y) v))))) = (parse-sym-exp '(w () y (((x (()))) y ((x) v)))) (sym-exp-map (make-swapper 'x 'y) (parse-sym-exp '((((x (((((y)) () x))))))))) = (parse-sym-exp '((((y (((((x)) () y)))))))) 2. [atomic-exp-map] The type "atomic-exp", is a generalization of the type sym-exp to deal with elements that are not necessarily symbols, but which are atomic. The grammar is as follows: <(atomic-exp-of T)> ::= | ( {<(atomic-exp-of T)>}* ) where the T's are required to be atomic and not null. Here we define a type to be atomic if it is not a pair. Helping procedures for this type are defined in the file in $PUB/lib/atomic-exp.scm, which you should load at the beginning of your file. Use these to get your code to type-check. Write a Scheme procedure, atomic-exp-map, with type declaration: (deftype atomic-exp-map (forall (S T) (-> ((-> (S) T) (atomic-exp-of S)) (atomic-exp-of T)))) that takes a procedure, p, of type (-> (S) T), and an (atomic-exp-of S), ae, and returns an (atomic-exp-of T) that is formed by applying p recursively to each S object in ae. You should do this by using the helping procedures in $PUB/lib/atomic-exp.scm. These have the same names as the procedures in the familiar $PUB/lib/sym-exp, but they use a different representation for symbol expressions. Your code should type check. The examples below on the following rely on the following additional definitions: (deftype make-replacer (forall (S T) (-> (S T) (-> (S) T)))) (define make-replacer (lambda (old new) (lambda (x) (if (eqv? x old) new x)))) (deftype make-swapper (forall (T) (-> (T T) (-> (T) T)))) (define make-swapper (lambda (a b) (lambda (x) (cond ((eqv? x a) b) ((eqv? x b) a) (else x))))) (atomic-exp-map (make-replacer 'y 'z) (parse-atomic-exp symbol? '())) = (parse-atomic-exp symbol? '()) (atomic-exp-map (make-replacer 'y 'z) (parse-atomic-exp symbol? 'y)) = (parse-atomic-exp symbol? 'z) (atomic-exp-map (make-replacer 333333333333333 4) (parse-atomic-exp number? 333333333333333)) = (parse-atomic-exp number? 4) (atomic-exp-map (make-replacer 333333333333333 4) (parse-atomic-exp number? 342)) = (parse-atomic-exp number? 342) (atomic-exp-map (make-replacer #t #f) (parse-atomic-exp boolean? '(#t #f #t #t))) = (parse-atomic-exp boolean? '(#f #f #f #f)) (atomic-exp-map (make-replacer 3 4) (parse-atomic-exp number? '(72 () (((3))) (() 5) () 3 (() (3) ((() 541)))))) = (parse-atomic-exp number? '(72 () (((4))) (() 5) () 4 (() (4) ((() 541))))) (atomic-exp-map (make-swapper 'x 'y) (parse-atomic-exp symbol? '())) = (parse-atomic-exp symbol? '()) (atomic-exp-map (make-swapper 'x 'y) (parse-atomic-exp symbol? 'y)) = (parse-atomic-exp symbol? 'x) (atomic-exp-map (make-swapper 'x 'y) (parse-atomic-exp symbol? 'x)) = (parse-atomic-exp symbol? 'y) (atomic-exp-map (make-swapper 3 4) (parse-atomic-exp number? '(72 () ((43 3 (4 ())))))) = (parse-atomic-exp number? '(72 () ((43 4 (3 ()))))) (atomic-exp-map (make-swapper 311 321) (parse-atomic-exp number? '(217 () 311 ((321 (())) 311 ((321) 430))))) = (parse-atomic-exp number? '(217 () 321 ((311 (())) 321 ((311) 430)))) (atomic-exp-map (make-swapper #f #t) (parse-atomic-exp boolean? '((((#t (((((#f)) () #t))))))))) = (parse-atomic-exp boolean? '((((#f (((((#t)) () #f)))))))) WHAT TO HAND IN You should have at the beginning of class, written answers to the above questions (or written out questions and problems you encountered for each part). Make sure your name is on these. Attach the printouts, if any, requested above.