Com S 342 --- Principles of Programming Languages HOMEWORK 2b: RECURSION OVER GRAMMARS Supplementary Work for the Exam 2 Makeup (File $Date: 2004/03/12 21:55:23 $) The reason for having this makeup homework, and a makeup exam, is that problems of recursion over grammars are important. This kind of recursion is both a fundamental technique in functional programming and is crucially important in programming interpreters. Thus these skills are are critically important for the course objectives, and for your successful performance in the rest of the course. The problems in this homework are all suggested practice problems. That is, unlike most homeworks, you do not have to print out and hand in your work. It will be discussed at the discussion section before the next exam, however, so you may want to bring your work to that discussion section. But aside from that opportunity for feedback, the only way we will judge whether you understand the contents of this supplementary homework are by your performance on the makeup exam. That exam will focus exclusively on problems of recursion over grammars. Such problems may be like those in problems 6, 7, and 8 of exam 2, but will most likely also involve different grammars. If you, like most people, had trouble with problems 6, 7, and 8 on exam 2, then you should do enough of the work below to ensure that you can do such problems quickly and surely. Don't be put off by the number of problems below, some of them are quite easy and just conceptual things. You need to learn this material now, because the rest of the course depends on it. (If you did perfectly well on problems 6, 7, and 8 in exam 2, then you should feel free to ignore most of the work below. However you will run the risk of doing poorly on the makeup exam, which you must take like everyone else. You probably should look over the work below, and find problems that look interesting to you and do some of them as a preparation for the makeup exam. Look especially at the "Follow the Grammar" section below for such problems.) The work below is organized into various categories, corresponding to different ideas and perspectives for learning the skill of being able to understand and write recursive programs over a new grammar describing some abstract data type. Some topics, like "Scheme Syntax" may not apply to you; if that is the case, then you can skip these topics. But everyone should look at the first topic below, which is an orientation. WHAT YOU DID WRONG ON EXAM 2 1. Look at your graded exam 2 very carefully, especially at problems 6, 7, and 8. Make a list of the comments you received on your work. Categorize (group) these comments to get some idea of the general difficulties you had on the test. If you received comments of the form "syntax error", then look at the section on "Scheme Syntax" below. If you have problems understanding our problem descriptions and examples, or if you only read the examples, or only the problem descriptions because the other does not make sense to you, then look at the section on "Problem Descriptions and Examples" below. You should also look at this section if you did not write any code at all for some problem, especially if you have trouble getting started on such problems. If you received comments of the form "this may fail" or "this will fail" or "fails", then look at the section on "Dynamic Checks". If you received comments of the form "type error", "missing cast", or "missing type declaration", or if you had errors in types and type checking, then look at the section on "Types and Type Checking" below. If you received comments of the form "improper division of work between these procedures", "wrong division of work", "not following the grammar", "not recursing on ...", or "missing recursive call", then look at the section on "Following the Grammar" below. You should also look at this section if you did not write any code at all for some problem, or if it takes you too long to do homework and exam problems in this class. (Also look at that section if you received comments of the form "repeated code".) If you have comments which don't seem to fit into these categories, please see or email us (the course staff) to get an explanation. If there are comments that you cannot read, or that do not understand after doing the work below that corresponds to them, please also see or write us for more help. 2. Type in all the code you wrote on the test, and get it to run and type check. Make sure you understand the effect of each mistake you made. If you don't understand some mistake we pointed out, take the corrected version of the program and change the corrected version slightly, introducing just that one mistake only, and see the effect that has on the program. SCHEME SYNTAX This section is for people have difficulty with Scheme's syntax. 3. Have you seen the file $PUB/docs/c++-translation.txt? If not, look at that. 4. (a) Write out a list of the kind of mistakes you make in syntax. (b) Copy, by hand, 5 procedures from chapter 1 of the textbook. check these over for your mistakes. (c) Write down, by hand, 5 different (correct) examples of the syntax you made the most mistakes with. Don't just make a difference in names. 5. For the other problems below, write out solutions by hand first. Then check your work by typing in the code. And you get things working, go back and very carefully compare the corrected version to your initial handwritten code. Note any syntax errors, especially places where you have extra or missing parentheses. PROBLEM DESCRIPTIONS AND EXAMPLES 6. If you had trouble with the vocabulary used in stating the problems, make a list of the phrases or words that you had difficulty understanding. Write out definitions of these (perhaps in another language if necessary). 7. If you understand the examples and the individual words, but don't understand the English descriptions of problems, then try the following. (a) If you understand the examples, try writing out, in your own (English) words, a description of one or more of problems 6-8 on exam 2. Then trying to see a correspondence between the words that are used on the test and the ones you wrote. (b) Write down 4 problem descriptions for problems you think might be on a makeup exam, in the same style as the exam problem. Two problems should be about s-lists or symbol-expressions, and two about a new grammar. 8. If you understand the problem descriptions, but don't understand the examples, then try the following. (a) Take several examples from each of problems 6-8 on exam 2, and use that example to compare against the English description of the problem. That is, mentally assigning each of the arguments in the example to the appropriate name given in the problem description, and then see if the answer given fists with your understanding of the description of the result in the problem. (b) Takes several of the problem descriptions in the work below, and makeup your own examples for them, before you look at the examples given by us. DYNAMIC CHECKS 9. In the sym-exp helping procedures, in $PUB/lib/sym-exp.scm, which of the procedures (that you can use in problems) do checking of their arguments? What checks do they make? 10. Suppose you have loaded $PUB/lib/sym-exp.scm in Scheme, and then suppose that you make the following definitions. (define empty (parse-sym-exp '())) (define a-empty-b (parse-sym-exp '(a () b))) (define a-sym (parse-sym-exp 'a)) With this context, what do each of the following expressions do? (sym-exp->s-list empty) (sym-exp->symbol empty) (sym-exp->s-list a-empty-b) (sym-exp->symbol a-empty-b) (sym-exp->s-list a-sym) (sym-exp->symbol a-sym) (car '()) (cdr '()) 11. Suppose that the variable lst is a list. What test should a program make in Scheme, before doing (car lst) or (cdr lst), to ensure that these expressions can never fail? 12. Suppose that symexp is of type sym-exp. What test should a program make in Scheme, before doing (sym-exp->symbol symexp) or (sym-exp->s-list symexp), to ensure that these expressions can never fail? 13. Suppose that exp is of type lambda-1-exp (from $PUB/lib/lambda-1-exp.scm). What test should a program make in Scheme, before doing expressions like: (lambda-exp->id exp) (lambda-exp->body exp) to ensure that these expressions can never fail? TYPES AND TYPE CHECKING 14. Read the type notation document in $PUB/docs/typedscm.pdf or on the web from the course resources page. In English, what do the following types mean? Give an example expression that has the given type, and check your answer using the type checker. symbol (list-of symbol) sym-exp (list-of sym-exp) (-> (sym-exp) symbol) (-> (sym-exp) boolean) (-> ((list-of sym-exp)) boolean) (forall (T) (list-of T)) (forall (S T) (-> ((-> (S) T) (list-of S)) (list-of T))) 15. What are the types of the following Scheme expressions? Check your answers using the type checker. (You will have to load $PUB/lib/sym-exp.scm first). 'a (parse-sym-exp 'a) (symbol->sym-exp 'a) '() (parse-s-list '()) '(a b c) (parse-s-list '(a b c)) (parse-sym-exp '(a b c)) (s-list->sym-exp (parse-s-list '(a b c))) (s-list->sym-exp (list (symbol->sym-exp 'a) (s-list->sym-exp '()))) (sym-exp->s-list (s-list->sym-exp (list (symbol->sym-exp 'a) (s-list->sym-exp '())))) 15. In each of the following, what does the type checker think that the type of the argument (named x0, x1, etc.) is? (Assume that we have to loaded $PUB/lib/sym-exp.scm first). (symbol? x0) (list? x1) (sym-exp-symbol? x2) (sym-exp-s-list? x3) (sym-exp->symbol x4) (sym-exp->s-list x5) (s-list->sym-exp x6) (symbol->sym-exp x7) 15. Is there a type named s-list that the type checker understands? If so, give an example expression that has that type. 16. Does the type checker think that every value of type (list-of sym-exp) also has type sym-exp? 17. Does the type checker think that every value of type symbol also has type sym-exp? 18. Which of the following are type errors, and which of then leads to a failure at runtime? (All of them do one or the other, assuming you have loaded $PUB/lib/sym-exp.scm first.) (symbol->sym-exp '()) (s-list->sym-exp 'a) (sym-exp->symbol (s-list->sym-exp '())) (sym-exp->s-list (symbol->sym-exp 'a)) 19. Consider the helpers in $PUB/lib/lambda-1-exp.scm. What are the types of the following expressions? 'a (var-exp 'a) (parse-lambda-1-exp 'a) (lambda-exp 'x (var-exp x)) (list (list 'x) 'x) (app-exp (lambda-exp 'x (var-exp x)) (var-exp 'a)) (list (list (list 'x) 'x) 'x) (lambda-exp? (var-exp 'a)) (var-exp->id (var-exp 'a)) (lambda-exp->id (lambda-exp 'x (var-exp x))) (lambda-exp->body (lambda-exp 'x (var-exp x))) 20. In each of the following, what does the type checker think that the type of the arguments (named x0, x1, etc.) is? (Assume that we have to loaded $PUB/lib/lambda-1-exp.scm first). (lambda-exp? x0) (lambda-exp->id x1) (lambda-exp->body x3) (var-exp->id x4) (app-exp->rator x5) (lambda-exp x6 x7) (app-exp x8 x9) (var-exp x10) 21. What are the types of the following expressions involving map? Check your answers using the type checker. (You will have to load $PUB/lib/sym-exp.scm first). (map (lambda (x) (+ 1 x)) (list 1 2 3 4)) (map (lambda (s) (symbol->sym-exp s)) '(a b c)) (map symbol->sym-exp '(a b c)) (map sym-exp->symbol (map symbol->sym-exp '(a b c))) (map sym-exp-symbol? (map symbol->sym-exp '(a b c))) (map (lambda(s) (sym-exp-symbol? (symbol->sym-exp s))) '(a b c)) FOLLOWING THE GRAMMAR A. What "Following the Grammar" Means What does "following the grammar" mean? Essentially, for every nonterminal there is a procedure that decides between the alternatives offered in its grammatical production(s), and that in every place in the productions where a nonterminal appears, there is a call to the corresponding procedure. Let's consider several different examples of grammars and procedures that follow them. A.1. Only Alternatives, No Recursion The simplest kind of grammar has no recursion, but just has alternatives. For example, consider the following grammar for temperatures. ::= hot | warm | cold then a procedure that takes a temperature as an argument will have the outline typified by the following example: (deftype select-outerwear (-> (temperature) symbol)) (define select-outerwear (lambda (temp) (cond ((hot? temp) 'none) ((warm? temp) 'wind-breaker) (else 'down-jacket)))) where hot? : (-> (temperature) boolean) warm? : (-> (temperature) boolean) cold? : (-> (temperature) boolean) are helping procedures defined elsewhere. Notice that there are three cases in the procedure, each of which corresponds to a condition tested in the body of the procedure. 22. Which of the following is a correct outline that follows the grammar for temperature? ;; (a) (define possibly-freezing? (lambda (temp) (cond ((null? temp) #f) ((cold? (car temp)) #t) (else (possibly-freezing? (cdr temp)))))) ;; (b) (define possibly-freezing? (lambda (temp) (cond ((sym-exp-symbol? temp) (eq? 'cold (sym-exp->symbol temp))) (else (possibly-freezing-s-list? (sym-exp->s-list temp)))))) (define possibly-freezing-s-list? (lambda (slist) (if (null? slist) #f (or (possibly-freezing? (car slist)) (possibly-freezing-s-list? (cdr slist)))))) ;; (c) (define possibly-freezing? (lambda (temp) (cond ((cold? temp) #t) ((hot? temp) #f) (else #f)))) ;; (d) (define possibly-freezing? (lambda (temp) (cond ((cold? temp) (possibly-freezing? temp))))) 23. Consider another example with simple alternatives: ::= red | yellow | green | blue Assuming you have procedures red?, yellow?, green?, and blue? write the procedure: equal-color? : (-> (color color) boolean) that takes two colors and returns #t if they are the same, and #f otherwise. A.2. Only Recursion, No Alternatives Another kind of grammar is one that just has recursion, but no alternatives. ::= The outline that corresponds to such a procedure is typified by the following example: (deftype infinite-sequence-map (-> ((-> (number) number) infinite-sequence) infinite-sequence)) (define infinite-sequence-map (lambda (f iseq) (infinite-sequence-cons (f (head iseq)) (infinite-sequence-map f (tail iseq))))) where infinite-sequence-cons : (-> (number infinite-sequence) infinite-sequence) head : (-> (infinite-sequence) number) tail : (-> (infinite-sequence) infinite-sequence) are helping procedures defined elsewhere. Following the grammar in this example means that the procedure does something with the head of the infinite-sequence and recurses on the tail of the infinite-sequence, just like the grammar has a head, which is a number, and a tail, which is a infinite-sequence where it recurses. In this example, there's no stopping condition, because the grammar has no alternatives to allow one to stop. 23. Which of the following is a correct outline that follows the grammar for infinite-sequence? ;; (a) (define any-negative? (lambda (iseq) (cond ((null? iseq) #f) ((negative? (car iseq)) #t) (else (any-negative? (cdr iseq)))))) ;; (b) (define any-negative? (lambda (iseq) (cond ((negative? (head iseq)) #t) (else (any-negative? (tail iseq)))))) ;; (c) (define any-negative? (lambda (iseq) (cond ((sym-exp-symbol? iseq) (eq? 'negative (sym-exp->symbol iseq))) (else (any-negative-s-list? (sym-exp->s-list iseq)))))) (define any-negative-s-list? (lambda (slist) (and (not (null? slist)) (or (any-negative? (car slist)) (any-negative-s-list? (cdr slist)))))) ;; (d) (define any-negative? (lambda (iseq) (cond ((cold? iseq) #f) ((warm? iseq) #f) (else #t)))) 24. Write a procedure, nth-element : (-> (infinite-sequence number) number) that takes an infinite sequence, iseq, and a positive number, n, and returns the nth of iseq. A.3. Multiple Nonterminals When the grammar has multiple nonterminals, the outline should have two features. First it should one procedure for each nonterminal. Second, when the grammar production for a nonterminal, X, uses another nonterminal, Y, there should be a call from the procedure for X to the procedure for Y. Consider the following example. ::= - ::= ::= To write a procedure like valid-number? : (-> (phone-number) boolean) one would structure the code as follows: (define valid-number? (lambda (num) (let ((ex-num (phone-number->exchange num))) (and (valid-exchange? ex-num) (valid-subscriber? (lookup-exchange ex-num) (phone-number->subscriber num)))))) (define valid-exchange? (lambda (ex-num) (contains? *known-exchanges* ex-num))) (define valid-subscriber? (lambda (exchange sub-num) (contains? exchange sub-num))) Notice that in the example above there are 3 procedures, corresponding to the three nonterminals. Also notice that, just as the grammatical production for uses the nonterminals and , the procedure valid-number? calls the procedures valid-exchange? and valid-subscriber?. 25. Which of the following is a correct outline that follows the grammar for phone-number? ;; (a) (define lookup-name (lambda (num) (cond ((null? num) "none") (else (lookup-name (lookup-exchange (car num)) (cdr num)))))) ;; (b) (define lookup-name (lambda (num) (if (zero? num) num (lookup-name (- num 1))))) ;; (c) (define lookup-name (lambda (num) (cond ((sym-exp-symbol? num) (eq? 'negative (sym-exp->symbol num))) (else (lookup-name-s-list? (sym-exp->s-list num)))))) (define lookup-name-s-list? (lambda (slist) (and (not (null? slist)) (or (lookup-name (car slist)) (lookup-name-s-list? (cdr slist)))))) ;; (d) (define lookup-name (lambda (num) (lookup-subscriber (lookup-exchange (phone-number->exchange num)) (phone-number->subscriber num)))) (define lookup-exchange (lambda (ex-num) (table-lookup *known-exchanges* ex-num))) (define lookup-subscriber (lambda (exchange sub-num) (table-lookup exchange sub-num))) 24. Write a procedure, phone-number->string : (-> (phone-number) string) that takes a phone number, num, and returns a string with the conventional formatting for the phone number (e.g., "555-1212"). 25. Suppose you have a grammar with 10 nonterminals, how many procedures would be contained in an outline that followed the grammar? B.1. Combinations Most interesting examples of grammars in programming languages involve all three types discussed above. 26. Consider the sym-exp grammar: ::= | ::= ( {}* ) (a) If you follow this grammar, how many procedures would you use to do a problem? (b) If you follow this grammar, which procedures would call which other procedures? (c) If you follow this grammar, what decisions are made in the procedure that corresponds to the nonterminal? (d) If you follow this grammar, what decisions are made in the procedure that corresponds to the nonterminal? 27. Consider the s-list grammar: ::= ( {}* ) ::= | (a) If you follow this grammar, how many procedures would you use to do a problem? (b) What is the difference between this grammar and grammar for sym-exp? (c) What is an example of something that is a sym-exp but not a s-list? (d) What type does the type checker associate with an s-list? 27. The depth of a sym-exp is the largest number of paretheses that surround any place in the sym-exp. For example, a has depth 0 () has depth 1 (a () (b)) has depth 2 Give 5 more examples of sym-exp, one at depth 0, one at depth 1, one at depth 2, one at depth 3, and another at depth 4. 28. Is the symbol x in the grammar for ? If so, give a derivation. If not, say why not. 29. Trace, on paper, the execution of your original solution to problems 6 and 7 on exam 2. Use an input that has a depth of at least 2. 30. There are only 3 kinds of (interesting) problems on sym-exp and s-lists. Make up one of each of the following kinds of problems for yourself, write out a description, and solve it. (a) Extracting some information from a sym-exp or s-list (e.g., a procedure that returns a boolean or a number). Occurs?, num-of? and the exam's has-times? or has-plus? are examples. (b) Transforming the sym-exp or s-list into some other type (e.g., a list). Flatten is an example. (c) Copying a sym-exp or s-list, and making some local changes along the way. Remove, and the exam's duplicate are examples. When testing your problems, use examples that pass the parse methods, and that have various depths. Be sure to include various empty lists scattered around. For example, try inputs like: 'a, '(), '(a () b), '(((b ())) () (x) (())) 31. Write a procedure map-sym-exp : (-> ((-> (symbol) sym-exp) sym-exp) sym-exp) that takes a procedure, f, and a sym-exp, se, and returns a sym-exp that has the same shape as se, but with each symbol, X, in se replaced by the result of (f X). For example: (map-sym-exp (lambda (x) (symbol->sym-exp 'y)) (symbol->sym-exp 'x)) ==> y (map-sym-exp (lambda (x) (if (eq? x 'a) (symbol->sym-exp 'y) x)) (symbol->sym-exp 'a)) ==> y (map-sym-exp (lambda (x) (if (eq? x 'a) (symbol->sym-exp 'y) x)) (symbol->sym-exp 'b)) ==> b (map-sym-exp (lambda (x) (if (eq? x 'a) (symbol->sym-exp 'y) x)) (s-list->sym-exp '())) ==> () (map-sym-exp (lambda (x) (if (eq? x 'a) (symbol->sym-exp 'y) x)) (parse-sym-exp '(a b () c))) ==> (y b () c) (map-sym-exp (lambda (x) (if (eq? x 'coms) 'cpre 'mis)) (parse-sym-exp '((a dept) ((of)) (coms (() or math)) ()))) ==> ((mis mis) ((mis)) (cpre (() mis mis)) ()) B.2 Something, Anything, Other than Sym-Exp and S-list, Please! Okay, okay. In fact, I'm glad you asked for this. It's better to understand how to follow the grammar by using a new grammar you haven't seen before anyway. 32. Consider the following grammar, with comments on the right side enclosed in quotations (" and "). The comments are an aid to remembering the helping procedures found in $PUB/lib/window-layout.scm. ::= (window ) "window (name width height)" | (horizontal {}*) "horizontal (subwindows)" | (vertical {}*) "vertical (subwindows)" In this grammar, the nonterminals and have the same syntax as in Scheme. Write a procedure, total-width : (-> (window-layout) number) that takes a window-layout, wl, and returns the total width of the layout. The width of a of the form (window S N1 N2) is N1. The width of a of the form (horizontal W1 W2 ... Wm)} is the sum of the widths of W1 through Wm (inclusive). The width of a of the form (vertical W1 W2 ... Wm) is the maximum of the widths of W1 through Wm (inclusive). If the list is empty, the width should be taken as 0. The following are examples. (total-width (parse-window-layout '(window olympics 50 33))) ==> 50 (total-width (parse-window-layout '(horizontal ))) ==> 0 (total-width (parse-window-layout '(vertical ))) ==> 0 (total-width (parse-window-layout '(horizontal (window olympics 80 33) (window local-news 20 10)))) ==> 100 (total-width (parse-window-layout '(vertical (window olympics 80 33) (window local-news 20 10)))) ==> 80 (total-width (parse-window-layout '(vertical (window star-trek 40 100) (window olympics 80 33) (window local-news 20 10)))) ==> 80 (total-width (parse-window-layout '(horizontal (vertical (window tempest 200 100) (window othello 200 77) (window hamlet 1000 600)) (horizontal (window baseball 50 40) (window track 100 60) (window equesterian 70 30)) (vertical (window star-trek 40 100) (window olympics 80 33) (window local-news 20 10))))) ==> 1300 Helpers for this grammar can be loaded using (load-from-lib "window-layout.scm"). Your code should type check with them. Feel free to use Scheme's map and max procedures. But beware that max requires at least one argument. You can test your solution using: (test-hw2b "total-width") 33. Design another problem over window-layouts. Give an English explanation, the deftype, and some examples. Then solve your problem, first on paper, then on the computer. For example, you might do something like computing the total area of the window layout, or a list of all the names of the windows... 34. Consider the following grammar with comments on the right side enclosed in quotations (" and "). The comments are an aid to remembering the helping procedures found in $PUB/lib/bexp.scm. ::= "var-exp (symbol)" | (and ) "and-exp (left right)" | (or ) "or-exp (left right)" | (not ) "not-exp (arg)" ::= P | Q Write a procedure beval : (-> (bexp boolean boolean) boolean) that takes 3 arguments: bexp, which is a , p-val, which is the value for P, and q-val, which is the value for Q. It evaluates the expression for those values. (Do this without using Scheme's eval function.) For example, (beval (parse-bexp 'P) #t #f) ==> #t (beval (parse-bexp 'Q) #t #f) ==> #f (beval (parse-bexp '(not P)) #t #f) ==> #f (beval (parse-bexp '(or (not P) Q)) #t #f) ==> #f (beval (parse-bexp '(and P (or Q (not Q)))) #t #f) ==> #t (beval (parse-bexp '(and (or P P) (or (or P P) (or Q Q)))) #f #t) ==> #f (beval (parse-bexp '(and (or P P) (or (or P P) (or Q Q)))) #t #f) ==> #t (beval (parse-bexp '(or (not (and P P)) (and (not (not (and P P))) (not (and P Q))))) #t #f) ==> #t Helpers for this grammar can be loaded using (load-from-lib "bexp.scm"). Your code should type check with them. You can test your solution using: (test-hw2b "beval") 35. Using the bexp grammar and helpers as in the previous problem, write a procedure bswap : (-> (bexp) bexp) that takes a and returns a with the same shape, but with every P changed to Q and every Q changed to P. For example, the following equations hold (not these aren't evaluations, but equations between Scheme terms): (bswap (parse-bexp 'P)) = (var-exp 'Q) (bswap (parse-bexp 'Q)) = (var-exp 'P) (bswap (parse-bexp '(not P))) = (parse-bexp '(not Q)) (bswap (parse-bexp '(or (not P) Q))) = (parse-bexp '(or (not Q) P)) (bswap (parse-bexp '(and P (or Q (not Q))))) = (parse-bexp '(and Q (or P (not P)))) Helpers for this grammar can be loaded using (load-from-lib "bexp.scm"). Your code should type check with them. You can test your solution using: (test-hw2b "bswap") 36. Consider the following grammar with comments on the right side enclosed in quotations (" and "). The comments are an aid to remembering the helping procedures found in $PUB/lib/statement-expression.scm. ::= "exp-stmt (exp)" | (set! ) "set-stmt (id exp)" ::= "var-exp (id)" | "num-exp (num)" | (begin {}* ) "begin-exp (stmts exp)" where an has the same syntax as a Scheme . Write a procedure subst-identifier : (-> (symbol symbol statement) statement) that takes two symbols, new and old, and a statement, stmt, and returns a statement that is just like stmt, except that all occurrences of old in stmt are replace by new. The following are examples. (subst-identifier 'new 'old (exp-stmt (var-exp 'old))) = (exp-stmt (var-exp 'new)) (subst-identifier 'new 'old (exp-stmt (var-exp 'x))) = (exp-stmt (var-exp 'x)) (subst-identifier 'x 'a (exp-stmt (var-exp 'a))) = (exp-stmt (var-exp 'x)) (subst-identifier 'x 'a (set-stmt 'a (num-exp 3))) = (set-stmt 'x (num-exp 3)) (subst-identifier 'x 'a (set-stmt 'a (begin (list (set-stmt 'a (num-exp 3))) (var-exp 'b)))) = (set-stmt 'x (begin (list (set-stmt 'x (num-exp 3))) (var-exp 'b))) (subst-identifier 'x 'a (parse-statement '(set! a (begin (set! a 3) (set! b a) b)))) = (parse-statement '(set! x (begin (set! x 3) (set! b x) b))) (subst-identifier 'x 'a (parse-statement '(begin a))) = (parse-statement '(begin x)) (subst-identifier 'x 'a (parse-statement '(set! a (begin (begin a))))) = (parse-statement '(set! x (begin (begin x)))) (subst-identifier 'x 'a (parse-statement '(begin (set! a (begin 3)) (set! a (begin (set! a (begin 4)) a)) 5 6 a (begin a) 5 (begin (begin (begin b) a)) (begin (set! b (begin a)) b)))) = (parse-statement '(begin (set! x (begin 3)) (set! x (begin (set! x (begin 4)) x)) 5 6 x (begin x) 5 (begin (begin (begin b) x)) (begin (set! b (begin x)) b))) Helpers for this grammar can be loaded using (load-from-lib "statement-expression.scm"). Your code should type check with them. You can test your solution using: (test-hw2b "subst-identifier") 37. In solving the previous problem, did you write a procedure subst-identifier-exp : (-> (symbol symbol expression) expression) as a helper? If not, follow the grammar by doing that. If so, test that also. You can test your solution using: (test-hw2b "subst-identifier-exp") 38. Invent one or more other problem on the statement and expresion grammar above. For example, try incrementing all the numbers found in a statement, or reversing the list of statements in every begin expression whose expression contains a num-exp with a number less than 3. 39. Work some problems like those on the homework for the lambda+if-exp grammar. For example, substitute for all bound occurrences of an identifier in an expression. 40. Invent your own grammar, and some problems on it.