CSc520 OPTIONAL homework 6 17 April 2006DUE: Monday 1 May 20061. AliasingBroadly defined, aliasing occurs whenever there are 2 or more reference paths to the same location or object.(a) Distinguish between pointer aliasing and name aliasing. Illustrate your explanations with examples fromsome programming language. Could there be other kinds of aliasing? Illustrate with examples.(b) The following procedure divides the parameters a, b by their greatest common divisor, leaving them as a"simplest ratio" without common factors. It is used to reduce a ratio a : b to lowest terms. All argumentsare assumed positive integers. Assume that at call time variable references are passed (CBR).procedure simpleratio(var a, b : integer) ; { a, b > 0 and integer }var c, d : integer;beginc: = a; d: = b;while c < > d doif c > d then c: = c − delse d: = d − c ;b: = b div c;a: = a div c;end { simpleratio };Describe what happens with calls like simpleratio(x, x)? How can this bug be fixed?(c) The Pascal User Manual states: "the actual parameter [corresponding to a var formal parameter] must be avariable . . . Furthermore, if x1,. . ., xn are the actual variables that correspond to the formal var param-eters v1,. . ., vn, then x1,. . ., xn should be distinct variables."The phrase following the "Furthermore" has become known as the actualization taboo (since the Manualsays "should" but not "must", it seems to be taken as a moral but not a legal injunction).If the taboo is violated, what kind of aliasing can occur, in the terminology of part (a)?(d) Another source of aliasing can occur when there are variables free in a procedure body. Describe what canhappen by an example from a specific language. Can the parameter-passing mechanism adopted by thelanguage affect this kind of aliasing, by perhaps preventing it or by preventing certain kinds of aliasing?2. Boolean OperatorsWe want to add the Boolean operators ‘&&’ (‘‘and’’) and ‘||’ (‘‘or’’) to the language IMP (Example 3.6, p. 66 oftext). To this end, we extend the syntax of expressions by adding the following productions:Expression ::=. . .| Expression && Expression| Expression || Expression(a) Which of the semantic domains Value, Storable, and Bindable need to change as a result of this exten-sion to the language?(b) Complete the following semantic equation, under the assumptions listed below:evaluate[[E1&&E2]]env sto =(i) Assuming that short-circuit evaluation is not being used.(ii) Assuming that short-circuit evaluation is being used.hw6 - 1 -3. Multiple ArgumentsExtend the IMP language of Watt, Example 3.9 to allow multiple parameters. See the discussion at (3.104,3.105). HINT: Remarkably little of the syntax and semantics has to change, but you will have to deal with argu-ment lists in Argument *.4. Continuation Semantics of breakUsing as a basis the model language IMPgdeveloped in the text and in class, describe a denotational continua-tion semantics for the language IMPgextended to allow break statements within while loops. Assume thefollowing simiplifications:that the only looping structure in IMPgis the while syntactic structure.that expressions have no side-effects or jumps (so that only command continuations are needed and expres-sion continuations do not have to be discussed).Extend the language syntax to have a new Command called break. If a break occurs in the body of awhile, execution is to continue with the continuation of the entire while construct. If a break occurswith no surrounding loop, the resulting program is invalid syntactically. The break is always made to thecontinuation of the closest surrounding loop construct.HINT: If while E do C executes in environment e, what environment must C execute in, if breaks out of Care to be allowed?(a) Provide grammar rule(s) for the new syntax. Only show changes.(b) Describe any new contextual constraints (static semantics). Only describe new constraints. If there are none,say so.(c) Give the new semantic rule forexecute : Command→Environ→Cont→Contexecute [[while E do C]] env cont(d) Give the semantic rule forexecute [[break ]]hw6 - 2
View Full Document
Unlocking...