Com S 342 --- Principles of Programming Languages HOMEWORK 4: REDUCTION RULES AND IMPERATIVE PROGRAMMING (File $Date: 1995/10/20 20:46:22 $) Due: problems 1-4 at beginning of your discussion section, October 6; problems 11-13,15, at the beginning of class, October 9; problems 17-18, at the beginning of class, October 11; problems 23-24 and 26 at the beginning of discussion section, October 20, problems 27-28 at the beginning of class, October 23. In this homework, you will review some of the ideas studied in the last chapter about syntactic abstraction and data abstraction. You will also learn about the semantics of the lambda calculus, and study imperative programming features and their semantics, as well as get a glimpse of the semantics of object-oriented languages, and start getting a handle on types. For code hand in *both* your printout of the Scheme code and a transcript of testing. See the directory $PUB/data/hw4/hw4.tst for test data for each coding problem. (You can use the procedure test-hw4 to run our tests, as described in homework 1. Recall that $PUB means /home/cs342/public.) The section headings below give the readings related to the problems. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 3.1-3 For the problems in this section, please give a brief answer: no more than about three (3) sentences. Use examples to illustrate your ideas, so that you aren't just copying ideas from the book or notes. 1. (5 points) Give an example of syntactic abstraction in some programming language other than Scheme or LISP (e.g., Pascal, C, C++, Ada, CLU, BASIC, ...). 2. (5 points) What are the advantages of syntactic abstraction as a means of specifying features of a programming language? (As opposed to giving the semantics direectly.) Give an example. 3. (5 points) In Scheme, "and" and "or" are examples of syntactic abstraction (see section 3.2). Is "not" also an example of syntactic abstraction? Explain why or why not. 4. (10 points) The programming language Haskell has a feature called "where". It allows one to write x * x + y * y where x = 3 and y = 2 which evaluates to 13. Suppose we wanted to add this kind of feature to the lambda calculus (or to Scheme). We might choose a syntax so that the above example would be written as follows. (where (+ (* x x) (* y y)) ((x 3) (y 2))) That is, the syntax would look as follows. ::= (where ({}*)) | (lambda ({}*) ) | ( {}*) | | ::= ( ) ::= ::= ::= Your problem is to give a semantics to the where expression by using the technique of syntactic abstraction. That is, say how to translate an expression of the form (where body ((v1 e1) ... (vn en))) into some other expression in the version of the lambda calculus that allows multiple argument functions and numbers. (This is to be handwritten, not a Scheme program.) 5. (10 points, extra credit) Why do you think Scheme has "let" expressions, but not "where" expressions? 6. (suggested practice) What is the difference between "cond" and "case" in Scheme? What is an example of something like each one in some other language? 7. (suggested practice) Could if expressions be eliminated from Scheme? 8. (10 points, extra credit) Why is the syntactic sugar for "or" in Scheme more complex than that for "and"? 9. (suggested practice) What is more like "and" in Scheme: C++'s "&&" or "&"? Why does C++ have both "&&" and "&"? Which is like the "and" in Pascal? 10. (15 points, extra credit) Is there any way that a syntactic abstraction is different than a macro? ESSENTIALS OF PROGRAMING LANGUAGES: Sections 3.4-7 For the problems in this section, please give a brief answer: no more than about three (3) sentences. Use examples to illustrate your ideas, so that you aren't just copying ideas from the book or notes. 11. (5 points) What are the advantages and disadvantages of transparent representations for ADTs? 12. (10 points) Are union types more convenient to use in Scheme than in C++ (or C or Pascal, whichever you are familiar with)? Explain with an example. 13. (10 points) Give abstract syntax for the "where" expession of problem 4 above. That is, write an appropriate define-record definition. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 3.4-7 $PUB/docs/type-notation.txt 14. (10 points, extra credit) Give an example of a union type in C++ (or C or Pascal), and implement it in Scheme as an ADT. 15. (15 points) Using a procedural representation for data, one can encode infinite data structures, as we did in class for mathematical sequences. In this problem you will do the same for sets. In set theory, a "set comprehension expression" is something like { x | x is an integer and x > 5 }. That is, it has a bound variable (like x) that represents a typical element, and a predicate (like "x is an integer and x > 5") that tells when something is in the set. Note that the set described by the above set comprehension expression is infinite, yet represented in a small space. We can think of this as a way to turning a predicate (the description) into a set. A predicate can be represented as a closure in Scheme. As usual, such a predicate has type (-> (datum) boolean), meaning a one-argument function that returns a boolean. Your problem then, is to implement the following functions, with the given types, using a procedural representation. (See $PUB/docs/type-notation.txt for details on the notation.) set-comprehend: (-> ((-> (datum) boolean)) set) set-member?: (-> (datum set) boolean) set-union: (-> (set set) set) set-intersection: (-> (set set) set) set-complement: (-> (set) set) For examples, consider the following. (define empty-set ; TYPE: set (set-comprehend (lambda (dat) false))) (define universal-set ; TYPE: set (set-comprehend (lambda (dat) true))) (define greater-than-maker ; TYPE: (-> (number) set) (lambda (n) (set-comprehend (lambda (m) (and (number? m) (> m n)))))) (define greater-than-5 ; TYPE: set (greater-than-maker 5)) (set-member? 342 empty-set) ==> #f (set-member? 'x universal-set) ==> #t (set-member? 3 (set-comprehend number?)) ==> #t (set-member? 'b (set-comprehend number?)) ==> #f (set-member? 3 greater-than-5) ==> #f (set-member? 7 greater-than-5) ==> #t (set-member? 'b greater-than-5) ==> #f (set-member? '7 (set-union (greater-than-maker 5) (set-complement (greater-than-maker 342)))) ==> #t (set-member? '7 (set-intersection (greater-than-maker 5) (set-complement (greater-than-maker 342)))) ==> #t Hint: set-comprehend and set-member? should be *really* simple, since you are using a procedural representation. For the others, think of how the set theoretic concepts relate to logic; this is helpful because the predicates are essentially boolean-valued. Remember, for all coding problems, you must hand in a transcript showing testing using our test data (see above). For this problem, you can use (test-hw4 "infinite-set-ADT") on the Com S department machines when running scm342 to test these. 16. (20 points, extra credit) Transform your procedural representation of sets into a record representation. ESSENTIALS OF PROGRAMING LANGUAGES: Sections 4.1-3 17. (20 points, 5 points each) Do exercise 4.2.1 in the text. [beta reductions] (This can be handwritten.) 18. (15 points) Do exercise 4.2.2 in the text, which is to implement the procedure beta-redex? : (-> (parsed-exp) boolean) where parsed-exp is the type for the abstract syntax of the lambda calculus. You will find the parser already loaded by our test case, which you can invoke by typing (to scm342): (test-hw4 "beta-redex?") 19. (extra credit, 15 points each) Do one or more of exercises 4.2.3-7 in the text. [lambda calc impl.] Give type comments for each procedure (see $PUB/docs/type-notation.txt for the notation). 20. (extra credit, 20 points each) Do one or more of exercises 4.3.1-6 in the text. [lambda calc impl.] Give type comments for each procedure. 21. (extra credit, 10 points each) Do one or more of exercises 4.4.1-3 in the text. [Y combinator stuff] Give type comments for each procedure. 22. (extra credit, 15 points) Do exercise 4.5.1 in the text. [lambda calc impl.] Give type comments for each procedure. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 4.5-6 23. (5 points) Do exercise 4.5.2 in the text. [reverse! transcript] (This can be handwritten.) 24. (5 points) Do exercise 4.5.3 in the text. [set-cdr!] (This can be handwritten.) 25. (suggested practice) Do exercise 4.5.5 in the text. [cell ADT transcript] 26. (10 points) Do exercise 4.5.4 in the text. [cell-ADT] You are to implement the following procedures, where "cell" stands for a representation using cons-cells. make-cell: (-> (datum) cell) cell?: (-> (datum) boolean) cell-ref: (-> (cell) datum) cell-set!: (-> (cell datum) void) cell-swap!: (-> (cell cell) void) Use (test-hw4 "cell-ADT") to test your code. We aren't providing expected results for all of the tests, since you should be able to interpret them for yourself. Note that you should expect a result of #[unknown] when the result type is void. Hint: don't use "eq?" to compare strings (as in the cell tag), use "equal?" or "string=?". Two distinct string literals may be different objects, and hence compare as not eq?. Another way to avoid this is to always use a single string object, but to be on the safe side, don't use eq? for comparing strings. 27. (15 points) Do exercise 4.6.1 in the text. [make-stack] We aren't providing expected results for all of the tests, since you should be able to interpret them for yourself. 28. (15 points) Do exercise 4.6.2 in the text. [ff-ADT using messages] However, use "extend!" instead of "extend", because it will have a side effect. Here are some examples. > (define env1 (make-ff)) > (define env2 (make-ff)) > ((env1 'empty?)) #t > ((env1 'extend!) 'a 20) > ((env1 'extend!) 'w 'val-w) > ((env1 'apply) 'a) 20 > ((env1 'extend!) 'a 5) > ((env1 'extend!) 'x 10) > ((env1 'apply) 'a) 5 > ((env1 'apply) 'x) 10 > ((env1 'empty?)) #f > ((env2 'extend!) 'b 42) > ((env2 'apply) 'b) 42 > ((env2 'empty?)) #f > ((env1 'empty?)) #t > ((env1 'extend!) 'b 3) > ((env2 'apply) 'b) 42 > ((env1 'apply) 'b) 3 29. (suggested practice) Do exercise 4.6.3 in the text. [next-symbol transcript] 30. (20 points, extra credit) Design a suitable type notation for things like figures 4.6.1-2 or problems 4.6.2. Show how it works by giving your notation for figure 4.6.2 and problem 4.6.2. Give the syntax of your notation as a grammar. ESSENTIALS OF PROGRAMMING LANGUAGES: Sections 4.7 31. (10 points, extra credit) Do exercise 4.7.1 in the text. [make-input-stream] 32. (35 points, extra credit) Do exercise 4.7.2 in the text. [fully lazy streams]