**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.

**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

(ii) define the value of an

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.

**(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.