% $Id: 0DOCS.tex,v 1.22 2012/01/17 11:50:53 leavens Exp leavens $
\documentclass{article}
\input{macros}
\renewcommand{\nonterm}[1]{\mbox{$\langle$\textrm{#1}$\rangle$}}
\newcommand{\opt}[1]{\textrm{[} #1 \textrm{]}}
\renewcommand{\arbno}[1]{\opt{#1} $\ldots$}
\renewcommand{\gramquote}[1]{\textrm{`}#1\textrm{'}}
\setlength{\BEFOREGRAMCOMMENTLEN}{10.5cm}

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

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

\begin{center}
{\huge An Oz Subset}
\end{center}

This document describes a subset of Oz \cite{vanRoy-Haridi04}
that is designed to be slightly larger than the declarative kernel
language of chapter 2 (of \cite{vanRoy-Haridi04}). The subset includes
several syntactic sugars, but not so many that manipulation becomes
unwieldy.

The purpose of this subset, and the programs in the following directory:\\
\url{http://www.eecs.ucf.edu/~leavens/COP4020/reducer} \\
is to show how to define various manipulations of Oz programs.
In particular, we provide definitions of Free and Bound Variable
identifiers and desugaring into the declarative kernel language.
Also provided is a definitional interpreter. All of these programs are
written in Oz (although using a larger portion of the language).

In what follows, I provide the lexical (\secref{sec-microsyntax})
and context-free (\secref{sec-cf-grammar}) grammars for
what the tools use in lexical analysis and parsing. I also define the
abstract syntax trees (\secref{sec-ast}) that are used in other tools (\secref{sec-funs}).

\subsection*{Notational Conventions}

Throughout this document we use the following
conventions for describing grammars.
The square brackets `[' and `]' surround optional parts of a
production.
Thus 
\begin{grammar}%
\nonterm{A} \: example \opt{\nonterm{B}} \nonterm{C}%
\end{grammar}
means the same thing as
\begin{grammar}%
\nonterm{A} \: example \nonterm{C} 
\> \| \> example \nonterm{B} \nonterm{C}%
\end{grammar}
Furthermore, the notation ``$\ldots$'' following an optional construct
means zero or more repetitions of the enclosed sentential form. 
Thus
\begin{grammar}%
\nonterm{A} \: example \arbno{\nonterm{B}} \nonterm{C}%
\end{grammar}
means the same thing as
\begin{grammar}%
\nonterm{A} \: example \nonterm{Bs} \nonterm{C}
\nonterm{Bs} \: \nonterm{B} \nonterm{Bs} 
\> \| \> \nonterm{Empty}
\nonterm{Empty} \: %
\end{grammar}

Single quotes (` and ') are used to indicate when notations such as
`\texttt{[}' and `\texttt{|}' are to be taken literally as terminal symbols,
as opposed to their default interpretation as meta-level grammatical symbols. 

\section{Microsyntax for An Oz Subset}
\label{sec-microsyntax}

The lexical analyzer in \texttt{OzLexer.oz}, which uses the code in
\texttt{LexerTools.oz}, does lexical analysis for the Oz subset.
The lexer recognizes all the keywords (really reserved words)
of the entire Oz language, as
well as all the special keyword tokens. 
However, it currently does not handle the Oz \verb|\insert| directive.

The microsyntax recognized by the lexer is given 
in \figref{fig-microsyntax}.  This
grammar which is to be understood lexically, that is, unlike a normal
grammar, no spaces or comments may appear between the characters of a
token. Thus, in particular, in a \nonterm{label}, there can be no
space or comment before the left parenthesis.

\begin{figure}[htp]
\begin{grammar}%
\nonterm{microsyntax} \: \arbno{\nonterm{lexeme}}
\nonterm{lexeme} \: \nonterm{space} \| \nonterm{comment} \| \nonterm{token}
\nonterm{token} \: \nonterm{varId} \| \nonterm{keyword} \| \nonterm{literal} \| \nonterm{label}

\nonterm{space} \: \nonterm{non-nl-space} \| \nonterm{end-of-line}
\nonterm{non-nl-space} \: \textrm{a blank, tab, or formfeed character}
\nonterm{end-of-line} \: \nonterm{newline} \| \nonterm{carriage-return} \| \nonterm{carriage-return} \nonterm{newline}
\nonterm{newline} \: \textrm{a newline character}
\nonterm{carriage-return} \: \textrm{a carriage-return character}

\nonterm{comment} \: ? \| \% \arbno{\nonterm{non-eol}} \nonterm{end-of-line}
\nonterm{non-eol} \: \textrm{any character except a newline or carriage return}

\nonterm{varId} \: \nonterm{CapitalLetter} \arbno{\nonterm{AlphaNumeric}} \| \nonterm{underbar} \arbno{\nonterm{AlphaNumeric}}
\nonterm{CapitalLetter} \: \textrm{An ISO capital letter, including the letters A through Z}
\nonterm{AlphaNumeric} \: \nonterm{CapitalLetter} \| \nonterm{lowercaseletter} \| \nonterm{digit} \| \nonterm{underbar}
\nonterm{lowercaseletter} \: \textrm{An ISO lower case letter, including the letters a through z}
\nonterm{underbar} \: \_

\nonterm{keyword} \: andthen \| at \| attr
\> \| \> case \| catch \| choice \| class \| declare \| define \| div \| do
\> \| \> else \| elseif \| end \| export \| fail \| finally \| for
\> \| \> from \| fun \| functor \| if \| in \| lazy \| local \| lock
\> \| \> meth \| mod \| of \| orelse \| proc \| prop \| raise
\> \| \> self \| skip \| then \| thread \| try
\> \| \> ( \| ) \| [ \| ] \| \{ \| \} 
\> \| \> \gramquote{|} \| \# \| \: \| \gramquote{...} \| = \| . \| := \| \^ \| \gramquote{[]} \| \$ 
\> \| \> ! \| \texttt{\textasciitilde} \| + \| - \| * \| / \| @ \| <- 
\> \| \> , \| !! \| <= \| == \| $\backslash$= \| < \| =< \| > 
\> \| \> >= \| =: \| \=: \| <: \| =<: \| >: \| >=: \| :: \| ::: 

\nonterm{literal} \: \nonterm{Atom} \| \nonterm{Bool} \| \nonterm{Int} \| \nonterm{Float} \| \nonterm{String}
\nonterm{Atom} \: \nonterm{lowercaseletter} \arbno{\nonterm{AlphaNumeric}} 
\> \| \> ' \nonterm{non-quote-eol} \arbno{\nonterm{non-quote-eol}} '
\nonterm{non-quote-eol} \: \textrm{any character that is a } \nonterm{non-eol} \textrm{ character except a} '
\nonterm{Bool} \: true \| false
\nonterm{Int} \: [ \texttt{\textasciitilde} ] \nonterm{digit} \arbno{\nonterm{digit}}
\nonterm{Float} \: \nonterm{Int} . \nonterm{numeric} \nonterm{exponent}
\nonterm{numeric} \: \arbno{\nonterm{digit}}
\nonterm{exponent} \: \nonterm{exponentChar} \nonterm{Int}
\nonterm{exponentChar} \: E \| e
\nonterm{String} \: " \arbno{\nonterm{non-dq-eol}} "
\nonterm{non-dq-eol} \: \textrm{any character that is a } \nonterm{non-eol} \textrm{ character except a} "

\nonterm{label} \: \nonterm{Atom} ( \| \nonterm{Bool} ( \| \nonterm{varId} (%
\end{grammar}
\caption{The lexical grammar recognized by the tools in this
  directory, which is a subset of the Oz lexical grammar. Note that an
  \nonterm{Atom} that has the same sequence of characters as a
  \nonterm{keyword} or a \nonterm{Bool} will be recognized as that
  \nonterm{keyword} or a \nonterm{Bool}, unless it is quoted.} 
\label{fig-microsyntax}
\end{figure}

The microsyntax and the lexer do not not consider \texttt{unit} to be a keyword, 
unlike the Oz documentation, but merely an \nonterm{Atom}.

\section{Context Free Grammar for the Oz Subset}
\label{sec-cf-grammar}

The parser in \texttt{MyOzParser.oz} recognizes the grammar in 
\figref{fig-concrete-grammar}, which builds on the lexical grammar as
usual.

In the figure, the names in the right column are not part of the grammar, 
but instead show what type of abstract syntax tree(s) record(s) is (are) 
made from the production(s) on the left.
Compare these with the abstract syntax definitions in \secref{sec-ast}.

\begin{figure}[htp]
\begin{commented-grammar}%
\nonterm{Program} \: \opt{\nonterm{Sequence}} \nonterm{Queries1}    \>\>\> program
\nonterm{Queries1} \: \arbno{\nonterm{Query}}
\nonterm{Query} \: declare \nonterm{Sequence} in \nonterm{Sequence} \>\>\> declareInQuery
\> \| \> declare \nonterm{Sequence}                                 \> declareQuery
\nonterm{Sequence} \: \nonterm{Statement} \arbno{\nonterm{Statement}} \>\>\> seqStmt
\nonterm{Statement} \: skip                                       \>\>\> skipStmt
\> \| \> local \nonterm{varId} in \nonterm{InStatement} end        \> localStmt
\> \| \> \nonterm{varId} = \nonterm{varId}                         \> unifyStmt
\> \| \> \nonterm{varId} = \nonterm{varId}                         \> unifyStmt
\> \| \> if \nonterm{Expression} then \nonterm{InStatement} 
\>    \>   else \nonterm{InStatement} end                                 \> ifStmt
\> \| \> case \nonterm{Expression} of \nonterm{Pattern} 
\>    \>   then \nonterm{InStatement} else \nonterm{InStatement} end      \> caseStmt
\> \| \> \{ \nonterm{Expression} \arbno{\nonterm{Expression}} \}          \> applyStmt
\> \| \> fun \{ \nonterm{Formals} \} \nonterm{Expression} end             \> namedFunStmt
\> \| \> thread \nonterm{Statement} end                                   \> threadStmt
\nonterm{InStatement} \: \nonterm{Sequence}
\> \| \> \nonterm{Pattern} = \nonterm{Expression} in \nonterm{Sequence}    \> inStmt
\nonterm{Expression} \: \nonterm{RelationalExp}
\nonterm{RelationalExp} \: \nonterm{VBarExp} \opt{\nonterm{RelationalOperator} \nonterm{VBarExp}} \>\>\> applyExp
\nonterm{RelationalOperator} \: == \| $\backslash$= \| < \| =< \| > \| >=
\nonterm{VBarExp} \: \nonterm{PoundExp} \opt{\gramquote{|} \nonterm{VBarExp}} \>\>\>  recordExp
\nonterm{PoundExp} \: \nonterm{AdditiveExp} \arbno{\# \nonterm{AdditiveExp}} \>\>\> recordExp
\nonterm{AdditiveExp} \: \nonterm{MultiplicativeExp} \arbno{\nonterm{AdditiveOp} \nonterm{MultiplicativeExp}} \>\>\> applyExp
\nonterm{AdditiveOp} \: + \| -
\nonterm{MultiplicativeExp} \: \nonterm{NegateExp} \arbno{\nonterm{MultiplicativeOp} \nonterm{NegateExp}} \>\>\> applyExp
\nonterm{MultiplicativeOp} \: * \| / \| div \| mod
\nonterm{NegateExp} \: \arbno{\texttt{\textasciitilde}} \nonterm{DotExp}               \>\>\> applyExp
\nonterm{DotExp} \: \nonterm{TightOpExp} \arbno{. \nonterm{TightOpExp}}       \>\>\> applyExp
\nonterm{TightOpExp} \: \arbno{!!} \nonterm{PrimaryExp}                       \>\>\> applyExp
\nonterm{PrimaryExp} \: ( \nonterm{Expression} )
\> \| \> \nonterm{varId} \| \nonterm{atomExp}                                 \> varId, atomExp
\> \| \> \nonterm{boolExp}                                                    \> boolExp
\> \| \> \nonterm{intLit} \| \nonterm{floatLit}                               \> intLit, floatLit
\> \| \> \nonterm{String}                                                     \> recordExp
\> \| \> \nonterm{label} \arbno{Field} )                                      \> recordExp
\> \| \> proc \{ \$ \nonterm{Formals} \} \nonterm{Sequence} end               \> procExp
\> \| \> if \nonterm{Expression} then \nonterm{Expression} 
\>    \>   else \nonterm{Expression} end                                      \> ifExp
\> \| \> case \nonterm{Expression} of \nonterm{Pattern} 
\>    \>   then \nonterm{Expression} else \nonterm{Expression} end            \> caseExp
\> \| \> \{ \nonterm{Expression} \arbno{\nonterm{Expression}} \}              \> applyExp
\> \| \> thread \nonterm{Expression} end                                     \> threadExp
\nonterm{Field} \: \nonterm{Feature} : \nonterm{Expression}               \>\>\> colonFld
\> \| \> \nonterm{Expression}                                                 \> posFld
\nonterm{Feature} \: \nonterm{atomExp} \| \nonterm{intLit} \| \nonterm{boolExp}
\nonterm{Pattern} \: \nonterm{VBarPat}
\nonterm{VBarPat} \: \nonterm{PoundPat} \opt{\gramquote{|} \nonterm{VBarPat}}  \>\>\> recordPat
\nonterm{PoundPat} \: \nonterm{PrimitivePat} \arbno{\# \nonterm{PrimitivePat}} \>\>\> recordPat
\nonterm{PrimitivePat} \: \nonterm{varId} \| \nonterm{atomExp}                 \>\>\> varIdPat, atomPat
\> \| \> \nonterm{boolExp}                                                     \> boolPat
\> \| \> ( \nonterm{Pattern} )
\> \| \> \nonterm{label} \arbno{\nonterm{PatField}} )                         \> recordPat
\nonterm{PatField} \: \nonterm{Feature} : \nonterm{Pattern}                \>\>\> colonFld
\> \| \> \nonterm{Pattern}                                                     \> posFld
\nonterm{Formals} \: \arbno{\nonterm{Pattern}}%
\end{commented-grammar}
\caption{Concrete syntax recognized by the parser, which is a subset of Oz.}
\label{fig-concrete-grammar}
\end{figure}

\section{Abstract Syntax Trees for the Oz Subset}
\label{sec-ast}

The grammar in \figref{fig-SugaredOz},
describes the abstract syntax trees produced by the parser and used by
other tools. These data structures are all records with distinguishing labels.
Thus the grammar in the figure represents the abstract syntax of our
Oz subset.
For example the following Oz statement:
\begin{lstlisting}
A = B
\end{lstlisting}
is represented by (parsed into) the following abstract syntax tree:
\begin{lstlisting}
unifyStmt(varId('A') varId('B'))
\end{lstlisting}
Note that the grammar uses Oz atoms to represent variable identifiers.

A more complex example of an abstract syntax tree 
is given in \figref{fig-Parsed}.

\begin{figure}[pt]
\begin{grammar}%
\nonterm{Program} \: program(\nonterm{List \nonterm{Query}} \nonterm{Position})
\nonterm{Query} \: seqQuery(\nonterm{Statement} \nonterm{Position})
\> \| \> declareInQuery(\nonterm{Statement} \nonterm{Statement} \nonterm{Position})
\> \| \> declareQuery(\nonterm{Statement} \nonterm{Position})

\nonterm{Statement} \: skipStmt(\nonterm{Position})
\> \| \> seqStmt(\nonterm{List \nonterm{Statement}} \nonterm{Position})
\> \| \> localStmt(\nonterm{VarIdRef} \nonterm{Statement} \nonterm{Position})
\> \| \> unifyStmt(\nonterm{VarIdRef} \nonterm{Expression} \nonterm{Position})
\> \| \> ifStmt(\nonterm{Expression} \nonterm{Statement} \nonterm{Statement} \nonterm{Position})
\> \| \> caseStmt(\nonterm{Expression} \nonterm{Pattern} \nonterm{Statement} \nonterm{Statement} \nonterm{Position})
\> \| \> applyStmt(\nonterm{Expression} \nonterm{List \nonterm{Expression}} \nonterm{Position})
\> \| \> namedFunStmt(\nonterm{Atom} \nonterm{List \nonterm{Pattern}} \nonterm{Expression} \nonterm{Position})
\> \| \> inStmt(\nonterm{Pattern} \nonterm{Expression} \nonterm{Statement} \nonterm{Position})
\> \| \> threadStmt(\nonterm{Statement} \nonterm{Position})

\nonterm{Expression} \: \nonterm{VarIdRef}
\> \| \> atomExp(\nonterm{Atom} \nonterm{Position}) \| boolExp(\nonterm{Bool} \nonterm{Position})
\> \| \> intLit(\nonterm{Int} \nonterm{Position}) \| floatLit(\nonterm{Float} \nonterm{Position})
\> \| \> recordExp(atomExp(\nonterm{Atom} \nonterm{List \nonterm{Field}} \nonterm{Position})
\> \| \> procExp(\nonterm{List \nonterm{Pattern}} \nonterm{Statement} \nonterm{Position})
\> \| \> ifExp(\nonterm{Expression} \nonterm{Expression} \nonterm{Expression} \nonterm{Position})
\> \| \> caseExp(\nonterm{Expression} \nonterm{Pattern} \nonterm{Expression} \nonterm{Expression} \nonterm{Position})
\> \| \> applyExp(\nonterm{Expression} \nonterm{List \nonterm{Expression}} \nonterm{Position})
\> \| \> threadExp(\nonterm{Expression} \nonterm{Position})

\nonterm{VarIdRef} \: varId(\nonterm{Atom} \nonterm{Position})

\nonterm{Pattern} \: varIdPat(\nonterm{Atom} \nonterm{Position})
\> \| \> atomPat(\nonterm{Atom} \nonterm{Position}) \| boolPat(\nonterm{Bool} \nonterm{Position})
\> \| \> recordPat(atomExp(\nonterm{Atom}) \nonterm{List \nonterm{PatField}} \nonterm{Position})

\nonterm{Field} \: colonFld(\nonterm{Feature} \nonterm{Expression} \nonterm{Position})
\> \| \> posFld(\nonterm{Expression} \nonterm{Position})

\nonterm{PatField} \: colonFld(\nonterm{Feature} \nonterm{Pattern} \nonterm{Position})
\> \| \> posFld(\nonterm{Pattern} \nonterm{Position})

\nonterm{Feature} \: atomExp(\nonterm{Atom} \nonterm{Position}) \| intLit(\nonterm{Int} \nonterm{Position})
\> \| \> boolExp(\nonterm{Bool} \nonterm{Position})

\nonterm{Position} \: pos:pos(\nonterm{FileName} \nonterm{Line} \nonterm{Col})
\> \| \> pos:pos(\nonterm{FileName} \nonterm{Line} \nonterm{Col} \nonterm{FileName} \nonterm{Line} \nonterm{Col})
\> \| \> \nonterm{Empty}

\nonterm{Empty} \:
\nonterm{FileName} \: \nonterm{Atom}
\nonterm{Line} \: \nonterm{Int}
\nonterm{Col} \: \nonterm{Int}%
\end{grammar}
\caption{Abstract syntax for an Oz Subset, based on the textbook's section 2.6
  \cite{vanRoy-Haridi04}.  The optional \nonterm{Position} field is used 
  for error messages, but is often omitted in examples made by hand.
  The type \nonterm{String} is the type of character strings in Oz,
  \nonterm{Atom} is the type of atoms in Oz, \nonterm{Int} is the type
  of Integers 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 (with all positions omitted):
\begin{lstlisting}
namedFunStmt('AddToEach'
             [recordPat(atomExp('#')
                        [posFld(varIdPat('A')) posFld(varIdPat('B'))])
              varIdPat('Ls')]
   caseExp(varId('Ls')
           recordPat(atomExp('|')
                     [posFld(recordExp(atomExp('#')
                                      [posFld(varIdPat('X'))
                                       posFld(varIdPat('Y'))]))
                      posFld(varIdPat('T'))])
           recordExp(atomExp('|')
                     [posFld(recordExp(atomExp('#')
                                       [posFld(applyExp(varId('Plus') 
                                                        [varId('A')
                                                         varId('X')]))
                                        posFld(applyExp(varId('Plus')
                                                        [varId('B')
                                                         varId('Y')]))]))
                      posFld(applyExp(varId('AddToEach')
                                      [recordExp(atomExp('#')
                                                 [posFld(varId('A'))
                                                  posFld(varId('B'))])
                                       varId('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 Main Functions}
\label{sec-funs}

The reducer provides the following main functions to users.

\begin{CONTINUEDENUM}
\item
The function
\begin{lstlisting}
FreeVarIdsStmt: <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}
BoundVarIdsStmt: <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}
DesugarStmt: <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.

\item
\label{ex-Reduce}
The function
\begin{lstlisting}
Reduce1: <fun {$ <Config>}: <Pair String Config>>
\end{lstlisting}
% $
takes a non-terminal configuration and returns a new rule name and a
configuration for the next step in the operational semantics of Oz,
starting at the given configuration.

The implementation is in \texttt{Reducer.oz}.
There are tests in the file \texttt{ReducerTest.oz}.

See \texttt{Configuration.oz} for details on configurations.
\end{CONTINUEDENUM}

\bibliographystyle{alpha}
\bibliography{all}

\end{document}
