2D1455 OO-Teori

2006-05-17

Take Home Exam

NOTES: (Please read these carefully!)

(i) Clearly mark at the top of each sheet you use: (a) your name (b) your e-mail address (in case I need to contact you) (c) the page number.

(ii) On the front page indicate how many pages are contained in your work in total.

(iii) Before handing in your work, tie the pages together with a paperclip, staple, or put them in a folder.

(iv) Your work must be handed in to NADAs studentexpedition no later than Thursday 18th May 2006 at 11.00 am. After this time it will be marked as late, and marks will be subtracted.

(v) If you have any questions about the exam (for example, if you do not understand a question) you may call my mobile number 076 223 86 79. Please do not call before 9.00 am or after 9.00pm! During the work day you may also e-mail me.

(vi) You may use your kursbunt, and any course books. You are allowed to use the internet, including search engines. However, you may not download any material from the internet and present it as your own without giving credit to your source. You are not allowed to discuss or develop your answer with anyone else until after all manuscripts have been handed in. You are not allowed to copy anyone else's work. By handing in your manuscript you are declaring that you have read, understood and abided by these rules. In the case that cheating is suspected, strong disciplinary action will be taken against all students involved.

(vii) Write clearly. No marks will be awarded for work that I cannot read. You can write your answers in swedish or english.

(viii) Be mathematically precise. You will loose marks for careless or imprecise mathematical work.

(ix) Please take time to fill in the course evaluation and remember to hand it in with your manuscript!


Answer all questions. Maximum marks are 33 points. A grade 3 will be awarded for 16 points or more, grades 4 and 5 are returned for better performances.

An exam paper which is handed in late will not be able to score the maximum grade of 5 under any circumstances.

Question 1. Recall the sequential object-oriented language Seqool and its operational semantics. You are going to add arrays as a new object type.

This exercise is rather lengthy and detailed, so the following questions will take you through step by step. There may be more than one way to answer each section, so think carefully about the consequences of each step you take, and read the entire question carefully before you write anything down.

(i). (1 point) Let C = { c1, c2, ... } be an infinite collection of class names, and let C^+ = { int, bool, c1, c2, ... }. Begin by extending C^+ to a larger set C^Array which includes names for all array types, so that if d is an array type then so is array(d). In particular you should allow arrays of arrays, arrays of arrays of arrays, ... etc. Give an inductive definition of the set C^Array.

(ii). (2 points) Consider whether or not you need to extend the sets of IVar(c) of instance variables (attributes), TVar of temporary variables and MName of method names. Extend the definition of the set of Exp(c) of side effect free expressions to include:
(a) a length function on expressions of array type (usually written something like length(A)), and
(b) array element access (usually written something like A[i])

(iii). (2 points) Extend the definition of the set SExp(c) of expressions for a class c with side effects to allow an array object constructor that takes an integer parameter that should set the length of the constructed array.

(iv). (2 points) Extend the definition of the set Stat(c) of all statements for a class c to allow an array assignment , A[i] := e, at an integer indexed location.

(v). (2 points) All the definitions so far concern only the syntax of this extended language. Now we will turn our attention to the operational semantics. In the following questions I will use the letter T to denote the upside down letter T as in your notes (standing for an undefined value) which I cannot access in html!

Mathematically extend the definition of the set State of all states from 3-tuples to 5-tuples of the form

sigma = ( sigma_1, sigma_2, sigma_3, sigma_4, sigma_5 ),

where:
sigma_1 is a set of currently active object names,
sigma_2 binds non-array attributes to values, (integers, booleans or object names including an undefined value of each type)
sigma_3 binds array attributes to finite sequences of values (including an undefined value, T, for an undefined value of the array type),
sigma_4 binds temporary variables which do not have array type to values, and
sigma_5 binds temporary variables which do have array type to finite sequences of values.
Hint: follow the mathematical style of your lecture notes.

Discuss the semantic difference between the undefined value T of type array(d) and the finite sequence (T', T', .... T') (n-times T') also of type array(d), where T' is the undefined value of type d. Why might both these values be useful for modeling? (Hint: look at your later answers!)

(vi). (2 points) Extend the definition of the semantic mapping

[[ . ]] : Exp(c)_d * State * O^c -> O^d_T

( * is the Cartesian product of sets) to:
(i) define the value of an expression using the length operator on an array, and
(ii) define the value of an array access expression A[i].
Be careful here to deal with the case of an array access out of bounds. You can return an undefined value of appropriate type in such cases. Note: You do not need to redefine the meaning of all the other existing expressions in the Seqool language.

(vii). (2 points) We wish to give an exception based operational semantics to our extended programming language which will raise an exception when we try to assign to an array variable outside the array bounds. Define an appropriate abstract machine model, in terms of possible machine states as in the notes, explaining each component of the model.

(viii). (2 points) Using the machine model you introduced above, define the semantics of an array assignment statement

x_array(d)^c [ e_int^c ] := s_d^c

where d denotes a type, c is a class name, x_array(d)^c is a class c instance variable (attribute) of type array(d), e_int^c is an expression (without side effects) of integer type for class c, and s_d^c is a class c expression of type d (possibly with side effects). Be careful to deal with any exceptions that may arise.

(ix). (2 points) Using the same machine model, define the semantics of an array construction statement of the form

x_array(d)^c := new( e_int^c )

where d is a type, c is a class name, x_array(d)^c is a class c instance variable (attribute) of type array(d), and e_int^c is an expression (without side effects) of integer type for class c. Again be careful to deal with any exceptions which might arise.

(x) (3 points) Starting from an initial state where all instance variables (attributes) and temporary variables of a class c object beta^c have undefined values T, and beta^c has the thread of control, and no exceptions have been raised, explain how the following simple Seqool code (belonging to some method in class c) executes:

x_array(int)^c := new(3);
x_array(int)^c [2] := 0;
x_array(int)^c [4] := 0;

You should mathematically define each of the three intermediary abstract machine states reached during execution, and explain in words what is happening.

Question 2. Consider the problem of evaluating a polynomial

P(x) = a[n] + a[n-1] x + a[n-2] x^2 + ... + a[0] x^n

The coefficients a[i] can be stored in a floating point array. Consider the following naive implementation of evaluation as a while program.

PolyEval(float[] a, float x, int n)

{ y[0] := 1;

i := 1;

while ( i <= n ) do

y[i] := y[i-1] * x;

i := i + 1 od;

P := 0;

i := 0;

while ( i <= n ) do

P := P + a[n-i] * y[i];

i := i + 1 od;

}

(i) (1 point) Draw a flowchart for this while program.

(ii) (12 points) Using Floyd's method of invariant assertions prove the correctness assertion

{ n >=0 } PolyEval { P = Sum from {i=0} to {n} a[i] x^(n-i) }

(where Sum represents the usual Sigma sum operator that I can't express in html!) under its partial correctness interpretation. Take care to show how you derive each labelling invariant formula using the branching and assignment rules.