\documentclass{article}
\usepackage{../style}
\usepackage{../graphics}
\usepackage{../langs}

\begin{document}

\section*{Homework 9}

\HEADER

\begin{enumerate}
\item Describe what is meant by \emph{eliminating tail
      recursion}? When can this optimization be applied and
      why is it of benefit?

\item A programming language has arithmetic expression. For an
  arithmetic expression the compiler of this language produces the
  following snippet of JVM code.

\begin{lstlisting}[language=JVMIS,numbers=none]
ldc 1 
ldc 2 
ldc 3 
imul 
ldc 4 
ldc 3 
isub 
iadd 
iadd
\end{lstlisting}

  Give the arithmetic expression that produced this code.  Make sure
  you give all necessary parentheses.

\item Describe what the following three JVM instructions do!

\begin{lstlisting}[language=JVMIS,numbers=none]
iload 3
istore 1
ifeq label
\end{lstlisting}


\item Early in the module, we saw that the regular expression matchers
  in Java, Python and Ruby are very slow with some (basic) regular
  expressions. What is the main reason for this ineffcient computation?

\item \POSTSCRIPT  

%  \item It is true (I confirmed it) that
%  
%  \begin{center} if $\varnothing$ does not occur in $r$
%  \;\;then\;\;$L(r) \not= \{\}$ 
%  \end{center}
%  
%  \noindent
%  holds, or equivalently
%  
%  \begin{center}
%  $L(r) = \{\}$ \;\;implies\;\; $\varnothing$ occurs in $r$.
%  \end{center}
%  
%  \noindent
%  You can prove either version by induction on $r$. The best way to
%  make more formal what is meant by `$\varnothing$ occurs in $r$', you can define
%  the following function:
%  
%  \begin{center}
%  \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
%  $occurs(\varnothing)$      & $\dn$ & $true$\\
%  $occurs(\epsilon)$           & $\dn$ &  $f\!alse$\\
%  $occurs (c)$                    & $\dn$ &  $f\!alse$\\
%  $occurs (r_1 + r_2)$       & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\ 
%  $occurs (r_1 \cdot r_2)$ & $\dn$ &  $occurs(r_1) \vee occurs(r_2)$\\
%  $occurs (r^*)$                & $\dn$ & $occurs(r)$ \\
%  \end{tabular}
%  \end{center}
%  
%  \noindent
%  Now you can prove 
%  
%  \begin{center}
%  $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
%  \end{center}
%  
%  \noindent
%  The interesting cases are $r_1 + r_2$ and $r^*$.
%  The other direction is not true, that is if $occurs(r)$ then $L(r) = \{\}$. A counter example
%  is $\varnothing + a$: although $\varnothing$ occurs in this regular expression, the corresponding
%  language is not empty. The obvious extension to include the not-regular expression, $\sim r$,
%  also leads to an incorrect statement. Suppose we add the clause
%    
%  \begin{center}
%  \begin{tabular}{@ {}l@ {\hspace{2mm}}c@ {\hspace{2mm}}l@ {}}
%  $occurs(\sim r)$      & $\dn$ & $occurs(r)$
%  \end{tabular}
%  \end{center}  
%  
%  \noindent
%  to the definition above, then it will not be true that
%  
%  \begin{center}
%  $L(r) = \{\}$ \;\;implies\;\; $occurs(r)$.
%  \end{center}
%  
%  \noindent
%  Assume the alphabet contains just $a$ and $b$, find a counter example to this
%  property.
  
\end{enumerate}

\end{document}

%%% Local Variables: 
%%% mode: latex
%%% TeX-master: t
%%% End: