CSc520 homework 4 6 March 2006DUE: Monday 27 March 2006 in classPROBLEMSSome problems require you to describe syntax or semantics of a language. Your syntactic/semantic descriptionsshould include thorough comments that explain the ideas behind each specification in clear technical English.The existence of a formalism to describe semantics does not relieve you of the responsibility to explain, anymore than it does in writing code. When precise semantics is called for, divide your solution into parts in thefollowing order: (1) syntax changes (2) semantic domain changes (3) semantic function changes. Under (1),describe any contextual constraints (static semantics) informally—there is no need to formalize these. Under(3), give signatures for all semantic functions and auxiliary functions introduced.Normally, it should only be necessary to give the changes in (1), (2) and (3) above. Do not repeat syntax andsemantics that has been given in the lecture or text, and that remains the same in describing your solution.1. Increment and DecrementExtend the imperative language IMP discussed in class (Example 3.6, p. 66 of the Watt text) to allow expres-sions to have side-effects via the following productions. These productions incorporate the post-increment andpost-decrement operators, which should be taken to have the same meaning as they do in C.Expression ::= Numeral| Expression + Expression...| Identifier ++| Identifier --HINT: Since expression evaluation now has side-effects, the signature of evaluate has now changed toevaluate : Expression→(Environ→(Store→(Store × Value ))Extend the denotational semantics of this language to accommodate this change. You may assume some fixedevaluation order on subexpressions if you like, but state what that order is in your solution. (Be sure to studyhow your changes propagate through the rest of the semantics for this example, and include all changes that arenecessary as a consequence.)2. Extending IMP with Multiple AssignmentWatt text, Exercise 3.16, page 95, part (a).Organize your semantic functions for maximum clarity and economy, using let. . .in.HINT: To approach semantics like this, involving a list of syntactic objects, one approach is to construct anabstract syntax that "breaks up" the list of Identifiers, using (a) left recursion or (b) right recursion on a newnonterminal like "MultAssign ::= ... MultAssign ... | Assign" Auxiliary semantic func-tions that are driven by this recursion may become necessary.To take the semantics of Numeral , for example, we would have with this approachNumeral ::= Numeral Digit | Digitval[[ND]] = 10*val[[N]] + val[[D]]val[[0]] = 0. . .Do not use constructs with ellipses in the list, like val[[d1, d2,. . ., dn]] =. . .since they do not indicatehow the list syntax drives the semantics as the parse tree is walked.hw4 - 1 -3. Extending IMP with Multiple Assignment—RepriseWatt text, Exercise 3.16, page 95, part (b).Organize your semantic functions for maximum clarity and economy, using let. . .in.Same comments as previous problem.4. Extending IMP with Sequential DeclarationsWatt text, Exercise 3.17, page 95.5. A Fixpoint Combinator in SchemeThe power function pow = λn . 2nmay be thought of as the fixed point ("fixpoint") pow = τ pow of the func-tionalτ = λ f . λn . if n = 0 then 1 else 2*f(n − 1) .(Recall we often write function application as f n or ( f n) instead of f (n).)The "call-by-value" or "applicative order" fixpoint combinator (fixpoint functional) can be defined byYcbv= λ f . (λx . λy . f(xx)y)(λx . λy . f(xx)y)Ycbvis much more than a theoretical artifact—it is capable of actually producing the fixpoint function of anyfunctional like τ above. To see this, let us evaluate (Ycbvτ) at the value 2. In other words, we perform reduc-tions until an irreducible (normal) form is reached. To save repetition, it is helpful to write Z for the string(λx . λy . τ(xx) y). Also remember that PQR is short for (PQ) R.(Ycbvτ)2→(ZZ)2→( (λx . λy . τ(xx)y) Z )2→(λy . τ(ZZ)y)2→τ(ZZ)2→(λ f . λn . if n = 0 then 1 else 2* f (n − 1)(ZZ))2→(λn . if n = 0 then 1 else 2*(ZZ)(n − 1))2→if 2 = 0 then 1 else 2*(ZZ)(2 − 1)→2*(ZZ)1→...→2*2*(ZZ)0→2*2*( (λx . λy . τ(xx) y) Z )0→2*2*(λy . τ(ZZ) y)0→2*2*τ(ZZ)0→2*2*(λf . λn . if n = 0 then 1 else 2* f (n − 1)(ZZ))0→2*2*(λn . if n = 0 then 1 else 2*(ZZ)(n − 1))0→2*2* if 0 = 0 then 1 else 2*(ZZ)(0 − 1)→2*2*1→4This certainly provides evidence that, in fact, Ycbvτ≡pow, the power function, aka λn . 2n.(a) Since Scheme is not strongly typed, you can define Ycbvin Scheme. Of course, τ can also be defined, e.g.,hw4 - 2 -(define tau(lambda (f)(lambda (n)(if (= n 0)1(* 2 (f (- n 1)))))))Define Ycbvin Scheme and show a test of((Ycbv tau) 5)Trace evaluations of Ycbv and tau to see if they agree with what would be expected by hand computa-tion. HINT: the (trace ... ) facility is useful here.(b) Pick another simple recursive definition besides the power function. Make it define a function on some typeother than the integers. Construct the functional τ for this application from the right-hand-side of the func-tion definition. Test ((Ycbv tau) arg) to verify that the fixpoint function is being correctly com-puted.(c) Does the following fixpoint combinator, often called the "normal order fixpoint combinator", compute thecorrect fixpoint function in Scheme?Ycbn= λ f . (λx . f (xx))(λx . f (xx))Construct it and experiment on the tau of part (a). If it does, demonstrate that it works by thorough test-ing. If it does not, find out why not. Hand computations may be helpful along with flowtracing the inter-preter. State your conclusions clearly.hw4 - 3
View Full Document
Unlocking...