\documentclass[12pt]{article}
\textheight 9.75in
\textwidth 6.75in
\parskip=0in
\parindent=0.3in
\oddsidemargin -.1in
\evensidemargin -.1in
\topmargin -.5in
\headsep 0in
\topsep 0ex
\itemsep 0ex


\newcommand{\CSharp}{\mbox{C$\sharp$}}



\begin{document}
\pagestyle{empty}
\sloppy
\noindent
{\large\bf
\begin{tabular*}{\textwidth}
{@{}l@{\extracolsep{\fill}}c@{\extracolsep{\fill}}r@{}}
CSE305, Spring 2007& Final Exam & Wed.\ May 9, 2007
\end{tabular*}
}

\smallskip
\noindent
Open book, open notes, closed neighbors, 170 minutes.  Do
{\em all five\/} questions in the exam booklets provided.
The exam totals 234 pts., subdivided as shown.
{\em Show your work\/}, and explain your reasoning where it is
called for---doing so may help for partial credit.

\bigskip
\bigskip
\noindent
{\bf (1) (3+0+6+9+15+9+6+3+6+6 = 63 pts.)}

Consider the following function written in ML

\medskip
\begin{verbatim}
      fun findDoubles(L) = case L of
          nil => nil
        | x::nil => nil
        | x::y::rest => if x = y then x::findDoubles(rest)
                                 else findDoubles(y::rest)
      ;
\end{verbatim}

\begin{itemize}
\item[(a)]
Calculate {\tt findDoubles [1,3,3,3,5,5,2,2,2,2,6,5,5]}.  
(3 pts.)
\item[(b)]
Suppose your original intent was to make a list {\tt findRepeaters(L)}
of all the repeating elements, so that you'd get {\tt [3,5,2,5]} instead
of your actual answer to (a).  How would you modify the code?
Wait---don't answer this yet.
(0 pts.)
\item[(c)]
Make a tail-recursive ``helper function'' {\tt fdh(L,R)} that does
the same thing as {\tt findDoubles}, except that
the output list is accumulated onto the given list {\tt R}.  
(6 pts.)
\item[(d)]
Now modify your {\tt fdh}
to answer part (b).  Did using your answer to (c) make things
easier than your first thoughts in (b), and if so, how?
(9 pts.)
\item[(e)]
Now write a predicate {\tt findDoubles(L,R)} in Prolog, where
{\tt L} is given and the output is to be stored in {\tt R}.
You may use the built-in equality predicate {\tt =}, but must
use a cut in place of also using the inequality predicate {\tt\verb+\=+}.
(15 pts.)
\item[(f)]
Now write {\tt findDoubles(L)} as a method of the {\tt Array}
class in Ruby.  You may use {\tt self} to refer to the
array/list itself, and/or use the {\tt at(i)} method.  Note
that for an array {\tt arr}, {\tt arr.at(i)} is a synonym for
{\tt arr[i]}.  Note also that {\tt arr.push(m)} and {\tt\verb+ arr << m+}
are also synonyms, with {\tt m} going to the rear in each case.
Return a new array---i.e., don't destroy the invoking array.
(9 pts.)
\item[(g)]
Explain in words why this code would be hard (indeed, annoying
and kludgey) to write using a {\tt foreach} loop on an array in
$\CSharp$, or using the {\tt .each} method in Ruby.
(6 pts.)
\item[(h)]
{\em Now\/} suppose you were coding {\tt E findFirstDouble()}
inside the generic linked-list class {\tt\verb+LL<E>+} from
Assignment~4.  As the name says, you're no longer returning
a {\em list\/} of doubled items, but just the first such {\em item\/}.
In case the invoking list had no doubles, what would you return?
(You don't have to write any $\CSharp$ code, just answer the
question. 3 pts.)
\item[(i)]
Now in ML, you can use the built-in ``option'' datatype:

\begin{verbatim}
datatype 'a option = NONE | SOME of 'a
\end{verbatim}

to make {\tt findFirstDouble(L)} return {\tt NONE} if {\tt L}
has no doubles, or {\tt SOME d} if {\tt d} is the first double.
But why might this be annoying?
Write the ML type signature of {\tt findFirstDouble} as part of your
answer.  (6 pts.)
\item[(j)]
Would coding {\tt findFirstDouble(L)} be similarly annoying in
Ruby?  Explain why or why not.  (6 pts., for 63 total)
\end{itemize}

\bigskip
\bigskip
\noindent
{\bf (2) (0+12+9+6+9+12+6 = 54 pts.)}

Consider the following expression, in the syntax of C/C++/Java/$\CSharp$.
Note that it has an internal assignment---recall that assignment is
treated as a binary expression operation in all of these languages.

\medskip
\begin{verbatim}
            z = (x - y + z) / (x = x + 2) * (y - 3*z)
\end{verbatim}

\medskip
\noindent
And recall part of the standard BNF for expressions in these
languages:

\medskip
\begin{verbatim}
            E1 ::=  Var = E1 | E
            E  ::=  E + T | E - T | T
            T  ::=  T*F | T/F | F
            F  ::=  (E1) | Var | any_numeric_literal
            Var::=  x | y | z | etc.
\end{verbatim}


\medskip
\begin{itemize}
\item[(a)]
Evaluate the expression when {\tt x = 4}, {\tt y = 6}, and {\tt z = 2}.
(Since this question is worth 0 pts., please {\bf do not}
raise your hand to ask a question about it!)
\item[(b)]
Write a parse tree for the above expression in this grammar.
You may abbreviate some productions, e.g.\ {\tt F} can be a direct
child of {\tt E1}.
(12 pts.)
\item[(c)]
Now write an expression tree for the expression itself.
(9 pts.)
\item[(d)]
Use your tree in (c) to convert the expression into Postfix form.
(6 pts.)
\item[(e)]
Now compile the Postfix into our ``rudimentary stack language.''
(9 pts.)
\item[(f)]
Show the evaluation of your stack code in (e) when
{\tt x = 4}, {\tt y = 6}, and {\tt z = 2}.
(12 pts.)
\item[(g)]
Suppose {\tt y} and {\tt z} are marked {\tt const} in a C++ program.
Why might a C++ compiler produce code that gives a different 
answer from that in (f)?  ( 6pts., for 54 on the problem)
\end{itemize}

\bigskip
\bigskip
\noindent
{\bf (3) (12+9+6+6+12 = 45 pts.)}

% Consider the following program written in {\em Madcal\/},
% which is a fictional language.  The point of referring to {\em Madcal\/}
% is that you don't know whether it uses static or dynamic
% scoping---indeed, this could be an option flag on the
% {\em Madcal\/} compiler!
% The meaning of the program should be clear even though the
% syntax is a mixture Ada, C, and ML.  {\em (overleaf)\/}

The program overleaf is written in a language called {\bf Bury},
for ``Ruby the wrong way.''  Like Ada it allows unlimited
nesting of functions---the idea is to Bury your code deep inside
lexical scopes ;-).  The serious point of a made-up language here
is that you don't know whether it uses static or dynamic scoping---indeed
this could even be an option flag on the {\bf Bury} compiler.  The
syntax of the program (overleaf) should be clear from your knowledge
of Ruby and $\CSharp$ and Ada.

\newpage
\begin{verbatim}
      def Main()
          int k,x
          def A(int y) return int
              def B(int x) return int
                  return x*(y + 1)
              end B
              def C(int y) return int
                  int k = 2*y
                  return B(k)
              end C
          /* Main body of A begins here */
          begin A
              if y = 1 then return C(3*y)
                       else return A(y - 1)
              end if
          end A
          def D(int x)
              Console.WriteLine("Answer is: " + (x + k))
          end D
      /* Body of Main() begins here. */
      begin Main
          k = 3
          x = A(k)
          D(x)
      end Main
\end{verbatim}

\begin{enumerate}
\item[(a)]
For each of the four sub-programs
{\tt A,B,C,D}, draw up a table showing which
of the three variable names {\tt k}, {\tt x}, and {\tt y} are
visible within that sub-program, and if so, which block it
belongs to (i.e., was declared in).  For example, the table for
{\tt Main} is: {\tt k = Main.k}, {\tt x = Main.x},
but no {\tt y} is visible.
(12 pts.)
\item[(b)]
Trace out the allocation of stack frames during the execution of
this program.
Show the static and dynamic links from each frame.
(Everything except the particular values of variables within
the frames is independent of parts (c) or (d); you should
be able to use this trace to help you solve (c) and (d)
without having to re-draw it each time.  9 pts.)
\item[(c)]
Suppose that Bury uses static scoping.
Using the information in your answers to (a) and (b),
carefully work out the value printed by this program.
Show your work.  (6 pts.)
\item[(d)]
Now suppose that Bury is using dynamic scoping.
Work out the value that would be printed now.
(Showing where a value would change is enough for full credit.  6 pts.)
\item[(e)]
The mantra in Bury is ``Every function is a class, and every variable
is a method.''  Following this mantra,
sketch code in $\CSharp$ (or Java or C++)
that defines a class hierarchy that mimics the structure
of the above program.
Use {\tt M} for the base class and {\tt A,B,C,D} as the names of the
other classes, and give the methods {\tt x()}, {\tt y()}, and {\tt k()}
in the appropriate classes.  You need not provide anything
else---no constructors
are needed, and you definitely should ignore the bodies of the
functions in your class-hierarchy sketch.  All we are interested in is
the analogy between lexical scoping and inheritance.  (12 pts., for 45 total)
\end{enumerate}


\bigskip
\bigskip
\noindent
{\bf (4) (8 $\times$ 3 = 24 pts.)}

{\em True/False\/} {\bf without} {\em justifications\/}.
Please write out the words {\tt true} and {\tt false} in full.
No justifications are asked for---and be sure to leave at least
a half-hour for the essay question next.

\begin{itemize}
\item[(a)]
Since the syntax of Ruby is based on the syntax of C, Ruby
suffers from the ``dangling-else'' ambiguity.
\item[(b)]
Upon execution of a pointer assignment {\tt p = q},
the value of {\tt p} is the address of the storage
object {\tt q}, so that
{\tt p} now points at {\tt q}.
\item[(c)]
In Ada, the loop variable {\tt i} in the for-loop
{\tt for i in 1..15 loop ... end loop;} has value {\tt i = 16} after
the loop exits.
\item[(d)]
In Java, the loop variable {\tt i} in the for-loop
{\tt\verb^for (int i = 1; i <= 15; i++) {...}^} has value {\tt i = 16} after
the loop exits.
\item[(e)]
On executing a $\CSharp$ statement
{\tt Foo x = new Foo();}, where {\tt Foo} is a class,
a storage object is created on the stack
as well as on the heap.
\item[(f)]
One of the reasons ML is not object-oriented is that if you
could do {\tt\verb+class D < B+} as with subclassing in Ruby, and
you coded a function {\tt f(L)} to which the ML compiler gave the
type {\tt\verb+B list -> B list+}, then you would be unable to
pass a {\tt D list} object {\tt L} to it.
\item[(g)]
In Ruby, if you declare {\tt\verb+class Swan < Animal+} and
{\tt\verb+class Duck < Animal+}, then it is not a
compile-time error to add a {\tt Duck} to a list of {\tt Swan} objects.
(You can give a two-word reason here.:-)
\item[(h)]
In Standard ML, in a function call of the form {\tt f(X,Y)} where
{\tt X} and {\tt Y} stand for arbitrary expressions, both {\tt X}
and {\tt Y} are evaluated before the body of {\tt f} is executed.
\end{itemize}




\bigskip
\bigskip
\noindent
{\bf (5) (4 $\times$ (3+3+3+3) = 48 pts.)}

In the decade before Java came out in 1994, C++ was the 
pre-eminent OOP language.  For each of the following four
language features, state how Java~5 and/or $\CSharp$ on one
hand, and Ruby on the other hand, have different features that work
{\em in opposite directions\/} from C++.  For each of (a,b,c,d), you must
give one concrete related feature of Ruby and one of Java-or-$\CSharp$,
one positive and one negative aspect of the Java/$\CSharp$
way of doing things, and one positive and one negative aspect of the
Ruby way of doing things.  
The grading is based on concrete example features and your evaluations
of them.

\begin{itemize}
\item[(a)]
C++ allows global functions, which in particular gives you
freedom to add functions that handle any data type (though
you can't edit source code within existing classes or {\tt struct}s.)
\item[(b)]
C++ is moderately strongly typed.  In particular, you can
freely mix ints and floats and doubles with each other, though
you might lose some precision.
\item[(c)]
Templates in C++ guarantee compile-time type safety (as opposed
to casting from {\tt void*}, or from {\tt Object} in Java/$\CSharp$),
but produce separate blocks of
executable code for each client of the template class.
\item[(d)]
C++ allows you to code classes with by-value semantics, and
pointers to classes which use by-reference semantics.
\end{itemize}









\centerline{\sc End of Exam}

\end{document}

