\documentstyle[11pt,fleqn]{article}
\topmargin 0pt
\advance \topmargin by -\headheight
\advance \topmargin by -\headsep
\textheight 8.9in
\oddsidemargin 0pt
\evensidemargin \oddsidemargin
\marginparwidth 0.5in
\textwidth 6.5in
\thispagestyle{empty}

\newcommand{\answr}[2]{#2}
\newcommand{\instr}[2]{#2}
%\newcommand{\answr}[2]{{\bf Answer:} #1}
%\newcommand{\instr}[2]{#1}
\long\def\comment#1{}
\def\CC{C\raise.22ex\hbox{{\footnotesize +}}\raise.22ex\hbox{\footnotesize +}}
\renewcommand{\i}[1]{{\it #1\/}}
\renewcommand{\b}[1]{{\bf #1}}
\renewcommand{\t}[1]{{\tt #1}}
\newcommand{\Cond}[3]
        {{\bf if\ } #1 {\bf\ then\ } #2 {\bf\ else\ } #3}
\newcommand{\aro}{\rightarrow}

\setlength{\topmargin}{0in}
\voffset=-0.25in

\begin{document}
%---------------------------------------------------------------------
\begin{flushright}
    CS 242. Autumn 1995. Handout 16\\
    November 30, 1995                
\end{flushright}

\vskip .28in
\begin{center}
    {\Large \bf Homework 7} \\       
Due Thursday, December 7             
\end{center}
%\vskip .18in
\noindent
%-------------------------------------------------------------------
\section*{Reading}
\begin{enumerate}

\item Read the first nine sections (4.5 pages) of Snyder, ``Encapsulation and
inheritance in object-oriented programming.'' This is up through
the section called {``Subtyping''} but not the section
called {``Attribute Visibility,''} or anything later in the paper.

\item Fisher and Mitchell, ``What is an object-oriented programming language?''

\item Stroustrop, ``What is object-oriented programming?''
\item Stroustrop, ``An overview of \CC.''

\item Skim Cook, ``Interfaces and specifications for the Smalltalk-80
collection classes.'' The main point of the paper is contained in Figure 5.
Look at Figure 5 first and then work backwards to
see what parts of the paper you need to read to understand the figure.

\end{enumerate}
%-------------------------------------------------------------------
\section*{Problems}
\begin{enumerate}

\item (10 points) 
Suppose that function $\tt f$ has type $\tt A \aro
B$ and function $\tt g$ has type $\tt C \aro D$.  What must be the
relationship between types $\tt A$ and $\tt C$ and between types $\tt
B$ and $\tt D$ to guarantee that type $\tt C \aro D$ is a subtype of
type $\tt A \aro B$?
\answr{}{\vskip 0.5in}

\item  (10 points)
This question asks about the differences between
subtyping in Smalltalk and \CC{}. 

\begin{itemize}
\item[(a)] In Smalltalk, what conditions would allow class
$S$ to be a subtype of class $T$? In other words, what relationship
between $S$ and $T$ would allow every operation on $T$-objects
to be applied to $S$-objects?

\item[(b)] In \CC{}, what conditions would allow class
$S$ to be a subtype of $T$?

\item[(c)] What do you see as the advantages and disadvantages
of each approach? 
\end{itemize}
\answr{}{\newpage}

\item (20 points) 
This problem is concerned with the relationship between two
class interfaces. The first interface is for objects that represent 
integer sets.
The second is for sets with an additional public 
member function that returns the
maximum integer in the set. Since the question asks you to compare
Smalltalk and \CC{}, the interfaces are written in a ``neutral''
ML-like notation.
\begin{verbatim}
class set     (* sets of integers with insert, membership test  *)
public:
  insert    : int -> unit
  is_member : int -> bool
  print     : unit -> unit
end;

class max_set (* sets with additional function to  return max elt  *) 
public:
  insert    : int -> unit
  is_member : int -> bool
  print     : unit -> unit
  max       : unit -> int
end;
\end{verbatim}
In either language, it would be possible to define
$\tt max\_set$ as a subclass (derived class) of $\tt set$, or 
define the two independently. 
Classes implementing both interfaces would be likely to have some
private representation that would not appear in the public interface.
Suppose we write a routine
$\tt count\_ten$ which, given a set as an argument,
counts how many of the numbers $0,1, \ldots, 10$ are in the
set and returns this number. In computing this sum,
we will ``send the message'' $\tt is\_member(i)$ to the
set for each $\tt i \leq 10$.
\begin{enumerate}
\item (7 points)
Assume that $\tt max\_set$ is \i{not} declared to
be a subclass (derived class) of $\tt set$ and that
$\tt count\_ten$  works properly for any instance of $\tt set$.
In Smalltalk, will $\tt count\_ten$  work properly for any 
instance of $\tt max\_set$? Why or why not? If this depends on
how one or both classes is written, explain how.



\item (7 points) 
Again assume that $\tt max\_set$ is \i{not} declared to
be a subclass (derived class) of $\tt set$ and that
$\tt count\_ten$  works properly for any instance of $\tt set$.
In \CC{}, will $\tt count\_ten$  work properly for any 
instance of $\tt max\_set$? Why or why not? If this depends on
how one or both classes is written, explain how. Assume
that  we have used casts in some way to defeat the type checker;
do not answer that this will not compile.

\answr{}{}

\item (6 points)
Suppose instead that $\tt max\_set$ \i{is} declared to
be a subclass (derived class) of $\tt set$ and that
$\tt count\_ten$  works properly for any instance of $\tt set$.
Would your answer to (a) or (b) change? How? Why?

\answr{}{\newpage}
\end{enumerate}



\item  (10 points)
A \CC{} class  may have virtual
members that may be redefined in derived classes. However, there is no way to
``undefine'' a virtual (or non-virtual) member. Suppose we add another
kind of member, called $\tt phantom$ members, that are treated as 
virtual, but are only defined in derived classes if an explicit definition is
given (i.e., a ``phantom'' function is not inherited unless its name
is listed in the derived class). 
For example, if we have two classes
\begin{verbatim}
class A {
...
public:
   phantom void f(){...}
   ...
};
class B : public A {
...
public:
   ...
};
\end{verbatim}
then $\tt f$ would appear in the $\tt vtbl$ for $\tt A$ objects
and, if $\tt x$ is an $\tt A$ object, $\tt x.f()$ would be allowed.
However, if $\tt f$ is not declared in $\tt B$, then $\tt f$ might
not need to appear 
in the $\tt vtbl$ for $\tt B$ objects and, if $\tt x$ is a $\tt B$ object, 
$\tt x.f()$ would not be allowed. 
Is this consistent with the design of \CC{}, or is there some general 
property of the language that would be destroyed? If so, explain what
this property is. 


\end{enumerate}
\end{document}


