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 name, (b) the page number.

(ii) On the front page indicate (a) how many pages are contained in your work in total. Clearly mark: (b) your name (c) your personnummer, (d) your e-mail address (in case I need to contact you)

(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 . (total 14 points) In this question you are going to add a simple static and compile time checkable subtype mechanism to the seqool language. Since this requires several changes to the language, the questions below will lead you through the required changes step by step.

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 C*C. Intuitively, if ci < cj then ci is a subtype of cj or cj is a supertype of ci. We will take ci < cj to mean that both:
(a) an object of type ci can be used everywhere that an object of type cj is used, and
(b) an object of type ci can invoke any method of an object of type cj .
Let << denote the reflexive transitive closure of <, thus: (i) ci < cj implies ci << cj, (ii) ci << ci and, (iii) ci << cj and cj << ck implies ci << ck.

(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 object calculus in the following way

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. (total 12 points) Write Java Modeling Language (JML) specifications consisting of pre- and post-conditions to formally model the following requirements on the following Java methods:

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