**2D1455 Foundations of Object Orientation**

**OOTeori 07**

**2007-05-25**

**Take Home Exam (tentamen)**

**NOTES: (Please read these carefully!)**

**(i)** Clearly mark at the top of __ each__ sheet you use: (a)
your

**(ii)** On the __ front page__ indicate (a) how many pages are
contained in your work in

**(iii)** There are two ways to submit your work. (**a**) Your work may
be handed in to NADA's studentexpedition no later than **Monday 28th May 2007
at 11.00 am**. After this time it will be marked as late, and marks will be
subtracted. (**b**) If for any reason your are unable to reach the studentexpedition
yourself (for example if you are at work) then you may __post__ your manuscript
to: *Studentexpeditionen, NADA, KTH, 100 44 Stockholm*. The date and time
on the postmark will be taken as the date and time of your submission. The __same
deadline__ applies to manuscripts submitted by post.

**(iv)** If manuscripts are submitted in any other place or by any other
means than those described in Part (iii) then the examiner and NADA cannot be
held responsible in the case that manuscripts are lost.

**(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 10.00 am or after 6.00pm!

**(vi)** You may use your kursbunt, and any course books. You are allowed
to use the internet including search engines. However, any work which you download
and use must be **credited to its source**. You are **not** allowed to
discuss or develop your answer with anyone else before 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 abided by these rules. In
the case that cheating is suspected, actions will be taken against any students
involved.

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

__ Answer all questions__. Maximum marks are 50 points. A grade 3
will be awarded for 25 points or more, grade 4 is awarded for 30 points or more,
grade 5 is awarded for 35 points or more.

** Question 1 **.

Let *C* = { *c1, c2*, ... } be a set of class names for a seqool
program. A * subtype declaration* < is a binary relation on class
names, formally, < is a subset of the Cartesian product

Let << denote the

**(i) (3 points)** Redefine the set *SExp*( *c_d* ) for *c*
in *C* and *d* in *C*+ of all expressions with possible side
effects so as to allow a method *m^c0_d0,...,dn* to take any actual parameters
which are of **subtypes** to *d1 , ..., dn* according to the relation
<<. You must also allow an object to invoke methods belonging to all its
supertypes.

**(ii) (3 points)** Redefine the set *Stat*(*c*) for *c*
in *C* of all statements for a class *c*, so that for any assignment
statement, if the right hand side expression has a type that is a subtype of
the left hand side variable (or class attribute) then the assignment is legal.

**(iii) (3 points)** Redefine the set *MethDef*(*c*)_*d0,...,dn*
of all method definitions for a class *c* in *C* so that if the return
expression of a method definition is a subtype of *d0* according to <<
then the method definition is legal.

**(iv) (3 points)** Extend the definition of the set *State* of all
semantic states for an abstract machine that executes this extended seqool language
so that at run time:

**(a)** a *c* class attribute *x^c_d1* in *Ivar*(*c*)_*d1*
of type *d1* (for* c* in *C*) can be bound to any value of type
*d2* << *d1*, and

**(b)** a temporary variable *u_d1* in *Tvar*(*d1*) of type
*d1* can be bound to any value of type *d2* << *d1*.

**(v) (2 points)** Carefully explain, using your answer to part (i), how
this subtype mechanism supports code reuse in seqool programs.

** Question 2. (total 12 points)** Recall that the natural numbers
can be represented as objects in the

zero = [ iszero = true, pred = sigma(x) x, succ = sigma(x) ( x.iszero := false ).pred := x ]

**(i) (4 points)** Extend this zero object to a new object zero' which also
has a unary method add(x) to perform addition. Your method must implement the
usual recursive addition rules for add, which can be expressed as

add( 0, x ) = x, and if y>0 then add ( y, x ) = add( y-1, x ) + 1

That is to say, you may not assume that addition is a built in operation of
the language that you can call. On the other hand, you can make use of any boolean
operations that you wish. **Hints:** Recall how unary operators can be added
to the object calculus by using the lambda calculus notation for functions.
If in doubt consult your course notes! You may find it easiest to introduce
some sort of boolean if_then_else_ operator to express your method.

**(ii) (4 points)** Prove that the term zero'.succ.add(zero'.succ) reduces
to the term zero'.succ.succ by using the reduction rules of the object calculus
and the beta reduction rule of the lambda calculus. Be as mathematically precise
as you can in your use of the reduction rules. **Hints**: try showing that
zero'.succ.add(zero'.succ) reduces to (zero'.add(zero'.succ)).succ which in
turn reduces to zero'.succ.succ. Also it may be easier to use *weak reduction*
as a strategy (c.f. course notes) , in which the calling object is reduced first.

**(iii) (4 points)** Extend your object zero', given as answer to part (i),
to an object zero'' which also has a unary method mult(x) to perform multiplication.
Your method must implement the usual recursive rules for mult, which can be
expressed as:

mult( 0, x ) = 0, and if y>0 then mult( y, x ) = add( x, mult( y-1 , x ) ).

** Question 3. (total 12 points)** Consider the following simple object
model of an automatic teller machine (ATM).

An ATM system consists of cash dispenser clients and a security code server that authorises transactions based on submitted personal identification number (pin) codes. A pin code is a 4-digit decimal integer. The cash dispenser provides the following five methods that can be called directly from the user interface: (1) void enterCard(Card c), which enters a card c into the cash dispenser, (2) void enterDigit(int d), which enters a single decimal digit d corresponding to pushing the interface digit button d, (3) void delete() which deletes the last decimal digit entered (if it exists), and (4) void enter() which signals that a complete pin code has been submitted. (5) The cash dispenser also provides a methode void message(String s) which will display the string s on the video screen for the user. The security code server provides a single method: (1) int getCode(Card c) which returns the correct pin code of the card c.

Write a universal **Live Sequence Chart** (LSC) that describes the use case
for entering a card into the cash dispenser and entering some digits followed
by the enter() command. If the
entered pin code matches the card's correct pin code stored on the security
code server then the cash dispenser should display the message "enter
cash amount" otherwise it should display the message "wrong
pin code: try again".

**Notes:** You may add any local variables of int
or boolean type to the chart
and/or attributes to the cash dispenser or security code server. You can assume
the existence of all the basic arithmetic operations and tests on the int
type, as well as the usual boolean
operations.

** Question 4**.

**(i) (3 points)** A method double
squareRoot(double x) must produce the square root of its non-negative
argument x. How robust is your
specification to different floating point models of double?

**(ii) (2 points)** A method int
searchArray(int[] A, int key) must search a non-null, unordered array
A of integers without repetitions
for key. It must return the index
of the first element in A that
matches key if such an element
exists, otherwise it must return the value A.length().

**(iii)** **(2 points)** A method int
searchOrderedArray(int[] A, int key) must do the same as searchArray()
in part (ii) above, but in addition, it also requires the array A
to be ordered.

**(iv)** **(2 point)** Comment on what you think ESC/Java might do if
calls to searchOrderedArray()
were replaced by calls to searchArray()
in a Java program. Conversely, what if we replace calls to searchArray()
by calls to searchOrderedArray()?

**(v)** **(3 points)** A method boolean
pathExists(boolean[][] A, int i, int j) must take an adjacency matrix
representation of an n-node directed graph (digraph) G as an n*n boolean matrix
A. If i
and j represent the ith and jth
nodes in G then this method returns true if there is a directed path from the
ith node to the jth node in G and false otherwise. **Note**: a *directed
path* in a digraph G is a finite sequence of edges of G where each edge in
the path (except the last) points to the start of the next edge in the path.
Look up any book on graph theory or discrete mathematics if you are not sure.