% $Id: 0DOCS.tex,v 1.3 2009/08/20 14:42:48 leavens Exp leavens $
\documentclass{article}
\input{macros}
\renewcommand{\nonterm}[1]{\mbox{$\langle$\textrm{#1}$\rangle$}}
\renewcommand{\arbno}[1]{\{#1\}}
\renewcommand{\gramquote}[1]{\textrm{`}#1\textrm{'}}

\renewcommand{\KW}[1]{\textbf{\texttt{#1}}}

\begin{document}
\noindent
~
\hfill COP 4020 --- Programming Languages 1
\hfill \today \\

\begin{center}
{\huge Free and Bound Variable Identifiers, Desugaring, in Oz}
\end{center}

\section*{A Grammar for Oz with Sugars}

Consider the grammar in \figref{fig-SugaredOz},
which describe data structures (records) called abstract syntax trees.
These are to be thought of as representing in Oz data the statements
and expressions of Oz itself.
Thus the grammar in the figure represents the abstract syntax of a
sugared version of Oz. 
For example the following Oz statement:
\begin{lstlisting}
A = B
\end{lstlisting}
is represented by the record structure:
\begin{lstlisting}
assignStmt("A" varIdExp("B"))
\end{lstlisting}
Note that the grammar uses Oz strings to represent variable identifiers.
A more complex example that illustrates more features of the representation
is given in \figref{fig-Parsed}.

\begin{figure}[h]
\begin{grammar}%
\nonterm{Statement} \: skipStmt
\> \| \> seqStmt(\nonterm{List \nonterm{Statement}})
\> \| \> localStmt(\nonterm{String} \nonterm{Statement})
\> \| \> assignStmt(\nonterm{String} \nonterm{Expression})
\> \| \> ifStmt(\nonterm{Expression} \nonterm{Statement} \nonterm{Statement})
\> \| \> caseStmt(\nonterm{Expression} \nonterm{Pattern} \nonterm{Statement} \nonterm{Statement})
\> \| \> applyStmt(\nonterm{Expression} \nonterm{List \nonterm{Expression}})
\> \| \> namedFunStmt(\nonterm{String} \nonterm{List \nonterm{Pattern}} \nonterm{Expression})
\> \| \> inStmt(\nonterm{Pattern} \nonterm{Expression} \nonterm{Statement})

\nonterm{Expression} \: varIdExp(\nonterm{String})
\> \| \> atomExp(\nonterm{Atom}) \| boolExp(\nonterm{Bool})
\> \| \> numExp(\nonterm{Number})
\> \| \> recordExp(\nonterm{Expression} \nonterm{List \nonterm{Field}})
\> \| \> procExp(\nonterm{List \nonterm{Pattern}} \nonterm{Statement})
\> \| \> ifExp(\nonterm{Expression} \nonterm{Expression} \nonterm{Expression})
\> \| \> caseExp(\nonterm{Expression} \nonterm{Pattern} \nonterm{Expression} \nonterm{Expression})
\> \| \> applyExp(\nonterm{Expression} \nonterm{List \nonterm{Expression}})

\nonterm{Pattern} \: varIdPat(\nonterm{String})
\> \| \> atomPat(\nonterm{Atom}) \| boolPat(\nonterm{Bool})
\> \| \> recordPat(\nonterm{Atom} \nonterm{List \nonterm{Field}})

\nonterm{Field} \: colonFld(\nonterm{Atom} \nonterm{Expression})
\> \| \> posFld(\nonterm{Exp})%
\end{grammar}
\caption{Grammar for a simplified subset of the practical version of the
  declarative language of chapter 3, based on the textbook's section 2.6
  \cite{vanRoy-Haridi04}.  
  The type \nonterm{String} is the type of character strings in Oz,
  \nonterm{Atom} is the type of atoms in Oz, etc.
}
\label{fig-SugaredOz}
\end{figure}

\begin{figure}[p]
The following Oz statement:
\begin{lstlisting}
fun {AddToEach A#B Ls}
   case Ls of
     (X#Y)|T then ({Plus A X}#{Plus B Y})|{AddToEach A#B T}
   else nil
   end
end
\end{lstlisting}
is represented by the following record structure:
\begin{lstlisting}
namedFunStmt("AddToEach"
             [recordPat('#'
                        [posFld(varIdExp("A")) posFld(varIdExp("B"))])
              varIdPat("Ls")]
   caseExp(varIdExp("Ls")
           recordPat('|'
                     [posFld(recordExp(atomExp('#')
                                      [posFld(varIdExp("X"))
                                       posFld(varIdExp("Y"))]))
                      posFld(varIdExp("T"))])
           recordExp(atomExp('|')
                     [posFld(recordExp(atomExp('#')
                                       [posFld(applyExp(varIdExp("Plus") 
                                                        [varIdExp("A")
                                                         varIdExp("X")]))
                                        posFld(applyExp(varIdExp("Plus")
                                                        [varIdExp("B")
                                                         varIdExp("Y")]))]))
                      posFld(applyExp(varIdExp("AddToEach")
                                      [recordExp(atomExp('#')
                                                 [posFld(varIdExp("A"))
                                                  posFld(varIdExp("B"))])
                                       varIdExp("T")]))])
           atomExp(nil)))
\end{lstlisting}
\caption{Example showing how Oz is parsed into the record structures
  (abstract syntax trees) from \figref{fig-SugaredOz}.
}
\label{fig-Parsed}
\end{figure}

\clearpage

\section*{The Functions (or Problems to be Solved)}

\begin{CONTINUEDENUM}
\item
The function
\begin{lstlisting}
FreeVarIds: <fun {$ <Statement>}: <Set <String>>
\end{lstlisting}
% $
takes a \nonterm{Statement} in the grammar of \figref{fig-SugaredOz}
and returns a set of all the variable identifiers that occur free in
its argument. 
Its implementation is in \texttt{FreeVarIds.oz}.
There are tests in the file \texttt{FreeVarIdsTest.oz}.

See the file \texttt{TestOutput.txt} for results of testing.

\item
\label{ex-BoundVarIds}
The function
\begin{lstlisting}
BoundVarIds: <fun {$ <Statement>}: <Set <String>>
\end{lstlisting}
% $
takes a \nonterm{Statement} in the grammar of \figref{fig-SugaredOz}
and returns a set of all the variable identifiers that occur bound in
its argument. 
Its implementation is in \texttt{BoundVarIds.oz}.
There are tests in the file \texttt{BoundVarIdsTest.oz}.

See the file \texttt{TestOutput.txt} for results of testing.

\item
\label{ex-Desugar}
The function
\begin{lstlisting}
Desugar: <fun {$ <Statement>}: <Statement>
\end{lstlisting}
% $
takes a \nonterm{Statement} in the grammar of \figref{fig-SugaredOz}
and returns a \nonterm{Statement} in the subset of that grammar that
represents Oz statements in the kernel language of the textbook
\cite[Section 2.3]{vanRoy-Haridi04}.

An implementation is in \texttt{Desugar.oz}.
There are tests in the file \texttt{DesugarTest.oz}.

See the file \texttt{TestOutput.txt} for results of testing.
\end{CONTINUEDENUM}

\bibliographystyle{alpha}
\bibliography{all}

\end{document}
