

\section{ Introduction }
\mynote{updated language spec}
In the following, we define the tiny language used to define how
mclasses propagate through builtins. This is used in the builtin specification
to specify mclass propagation, using the {\tt Class} attribute. To specify the
mclass propagation for a builtin, or an abstract builtin, it is
specified as an attribute in the builtin specification, using the syntax
\begin{equation*}
  Class(<expr>)
\end{equation*}
or
\begin{equation*}
  Class(<expr_1>,<expr_2>,<expr_3>,\ldots,<expr_n>)
\end{equation*}
where the expressions follow the syntax of the mclass propagation
language. 
\rednote{It is also possible to separate the cases using the $||$
operator:
\begin{equation*}
  Class(<expr_1> || <expr_2> || <expr_3> || \ldots ||<expr_n>)
\end{equation*}}
The language itself is somewhat similar to regular
expressions in that it matches incoming mclasses. But rather than
having a match as a result, the language allows to
explicitly state what the result is.



\section{ Class Specification }

\subsection{Basics}
Every expression is interpreted either in LHS (left-hand side) or in RHS
(right-hand side) mode. In LHS mode it matches the mclasses of
arguments to the expression, in RHS it emits the mclasses as
output. For example
\mynote{Not every operator change is marked}
\begin{equation*}
double \text{{\tt ->}} char
\end{equation*}
will attempt to match a $double$ argument, and if one is found, it
will emit a $char$ result. For any expression \emph{iff} all input arguments
have been consumed by matching, it will result in an overall match,
and the emitted results will be returned.

At any point there will be a partial match, which consists of the next
input argument index to be read, and the result mclasses emitted so far. For
example, after the above expression, if one attempts to match the input
arguments $[double, double]$, the partial result will refer to the 2nd
argument, and will have $char$ as an output.



\subsection{Language Features}
In the following, we present the syntax and semantics of the language,
showing the LHS (matching) and RHS (emitting) semantics for every feature. Note that
for some expressions, the LHS and RHS semantics are the same, i.e.
some expressions may ignore the current mode.

\subsubsection{Operators}
\begin{description}
\mynote{all > changed to -> }
\item[$expr_1 \text{{\tt ->}} expr_2$] \hfill \\
  LHS, RHS: will attempt to match $expr_1$ as a LHS, and if it is a match,
  will execute $expr_2$ as a RHS expression and emit the results.

\mynote{all \&  removed}
\item[$expr_1 \phantom{.} expr_2$] \hfill \\
  LHS: will attempt to match $expr_1$ as a LHS, and if it is a match,
  will attempt to match $expr_2$.
  \\RHS: will emit the results of $expr_1$ in RHS mode, then will emit the results of $expr_2$ in RHS mode.

\item[$expr_1 | expr_2$] \hfill \\
  LHS: will attempt to match both $expr_1$ and $expr_2$ independently, then will
  return whichever successful match consumed the most arguments.
  \\RHS: will emit the union of the emitted results of $expr_1$ and $expr_2$,
  run as RHS expressions. Both $expr_1$ and $expr_2$ must have the same
  number of emitted result. If not, it will throw a runtime error.

\mynote{function ``opt'' changed to operator ``?'', ``star'' changed to ``*''}
\item[$expr?$] \hfill \\
  $expr?$ is equivalent to $none|expr$\\
  LHS: will attempt to match the expression. If does not match, $?$ will still
  return a match successfully, but it does so by matching $none$.\\
  RHS: This will likely cause an error, because the union of two match
  results must both result in the same number of emitted outputs.

\item[$expr*$] \hfill \\
  $expr*$ is equivalent to $expr? \phantom{.} expr? \phantom{.}  expr?  \dots$
\end{description}

\rednote{
  The operators $*$ and $?$ have the same, highest precedence, $|$ has a lower precedence, putting no symbol
(i.e. $expr_1 \phantom{.} expr_2$) has a lower precedence than that. $\text{{\tt ->}}$ has the lowest
precedence. }

\newpage
\subsubsection{Non-parametric Expressions}
\begin{description}
\item[ Builtin MClasses] \hfill \\
The mclass propagation language supports the following builtin \rednote{mclasses and groups of mclasses}:
%\begin{center}
\vspace{.1cm} \\
\begin{tabular}{ p{.3in} p{1in} p{1in} }
&$double$ & $logical$\\                   
&$float$  & $function\_handle$\\
&$char$   & $int8$   \\ 
&$uint8$  & $int16$  \\
&$uint16$ & $int32$  \\
&$uint32$ & $int64$  \\
&$uint64$ & \\
\end{tabular} \vspace{.1cm} 
\\
%\end{center}
  LHS: will attempt to match the builtin mclass \\
  RHS: will emit the builtin mclass

\item[ Groups of Builtin Mclasses] \hfill \\
  Certain mclasses are grouped together using union:\\
\begin{tabular}{p{.2in} c c c c}
&$float  $ &  is the same as &$single|double$ \\
&$uint   $ &  is the same as &$uint8|uint16|uint32|uint64$ \\
&$sint   $ &  is the same as &$int8|int16|int32|int64$ \\
&$int    $ &  is the same as &$uint|sint$ \\
&$numeric$ &  is the same as &$float|int$ \\
&$matrix $ &  is the same as &$numeric|char|logical$ \\
\end{tabular}

\item[Non-parametric Language Features] \hfill % \\
\begin{description}
\item[$none$] \hfill \\
  LHS, RHS: matches without consuming inputs or emitting results
\item[$begin$] \hfill \\
  LHS, RHS: will match if the next argument is the first argument (no
  arguments have been matched)
\item[$end$] \hfill \\
  LHS, RHS: will match if all arguments have been matched
\item[$any$] \hfill \\
  LHS: will match the next argument, no matter what it is, if there
  is an argument left to match \\
  RHS: error
\item[$parent$] \hfill \\
  LHS, RHS: will substitute the expression that is defined for the abstract
  parent builtin. If the parent builtin does not define mclass
  propagation information, will substitute $none$.
\item[$error$] \hfill \\
  LHS, RHS: same as none, except that the result is flagged as
  erroneous. During matching $error$ is ignored (partial matching will
  continue), but if a result is erroneous overall, it will result in
  not a match overall.
\item[$natlab$] \hfill \\
  LHS, RHS: Besides the {\tt Class} attribute for builtins, one can define an
  alternative attribute {\tt MatlabClass} which more closely resembles \matlab
  semantics, including some of the irregularities of the language. When
  defining such a {\tt MatlabClass} attribute, the keyword $natlab$ will refer to
  the expression defined by the {\tt Class} attribute. Note that one cannot
  define a {\tt MatlabClass} without defining a {\tt Class} attribute, so $natlab$
  should always be defined.
\item[$matlab$] \hfill \\ equivalent to $natlab$, but this can be used
  inside {\tt Class} attribute to refer to whatever is defined for the
  {\tt MatlabClass} attribute.\\ This does not verify whether the {\tt
    MatlabClass} attribute has been defined; therefore, undefined
  behavior may result if the attribute is not defined.
\item[$scalar$] \hfill
  \\ LHS: If there is another argument to consume, matches if it is
  scalar, or if its shape is unknown, without consuming the argument.
  This can be used to check if the next argument is scalar. This
  should only be used if the scalar requirement is directly related to
  mclass behavior. If shapes and types are independent, they should be
  specified independently.
  \\ RHS: runtime error
\end{description}
\end{description}

\subsubsection{Functions}
\begin{description}
\item[$coerce(replaceExpr, expr)$] \hfill \\
  will take every single argument, and execute $replaceExpr$ on it
  individually and independently. The replace expression must either
  not match, or a match and emit a single result. If it does, this
  result gets replaced as a the new argument. 
  $coerce$ will then take the new set of arguments, and execute 
  $expr$ with it, either as LHS or RHS depending on whether
  the $coerce$ itself was executed in LHS or RHS mode, and return the result
  of that.\\
  This allows operand coercion. For example, a function may convert all
  incoming $char$ or $logical$ arguments to $double$, which would be done using
\vspace{-.3cm} \begin{equation*}
    coerce(char|logical\text{{\tt ->}}double, expr)
\end{equation*}


\item[$typeString(expr)$] \hfill \\ LHS, RHS: if the next element is a
  $char$, $typeString$ will consume it. If its actual runtime value is
  known, it will check whether the value of the string is the name of
  a mclass which is emitted by $expr$ (running $expr$ in RHS mode).
  If it is, $typeString$ will emit that mclass.\\
  If the $char$ has another known value, $typeString$
  will return an error.\\
  If the value is not known, will emit all results
  produced by $expr$. $expr$ should produce one (union) result.\\
  This can be used to match a last optional argument denoting a
  desired mclass for the return value. This used, for example, by the
  functions {\tt ones} and {\tt zeros}, which allow a last 
  optional argument specifying that the result should have a
  numerical mclass other than the default $double$.
\end{description}

\subsubsection{Number}
\begin{description}
\item[$<number>$] \hfill \\
  LHS, RHS: Equivalent to the input argument with the same index as
  the given number. For example, $0$ will match (LHS) or emit (RHS)
  the mclass of the first argument.  Negative numbers will match from
  the back, so -$1$ is the mclass of the last argument.
\end{description}

\section{Extra Notes on Semantics }

\subsection{RHS Can Have LHS Sub-expressions, and Vice Versa}
An expression may emit results even if it is run as a LHS
expression, and an expression run as RHS may match more elements. For
example for
\begin{equation*}
  double \text{{\tt ->}} (char \text{{\tt ->}} logical  \phantom{.}  int16)
\end{equation*}
the $char$ expression will get matched, due to the second $\text{{\tt ->}}$
operation. Similarly,
\begin{equation*}
  (double  \phantom{.}  char \text{{\tt ->}} logical) \text{{\tt ->}} int16
\end{equation*}
being an equivalent expression, will emit the $logical$ because of the second $\text{{\tt ->}}$.



\subsection{Overall Evaluation of Class Attribute Expressions}
Overall, expressions are evaluated as LHS expressions, so the builtin attribute
\begin{center}
{\tt   Class(double) }
\end{center}
will attempt to match a incoming $double$ argument, and have no returns.
Multiple arguments to the {\tt Class} attribute  get transformed internally to
their union, so
\begin{equation*}
  Class(expr_1,expr_2,..,expr_n)
\end{equation*}
is equivalent to
\begin{equation*}
  Class(expr_1 | expr_2 | .. | expr_n)
\end{equation*}
This only applies for arguments to the {\tt class} attribute , comma is not an
operator equivalent to $|$ in general.



\subsection{Greedy Matching}
While the language looks similar to regular expressions, it is in fact
different: all matching is done greedily.
So the expression
\begin{equation*}
  (double | none)  \phantom{.}  (double)
\end{equation*}
When run on a single $double$ input, will not match. This is because the
union will greedily match the longest expression, which will consume
the input argument.


\section{ Examples }
\begin{description}
\item[$Class(double|single \phantom{.} double|single\text{{\tt ->}}double)$] \hfill \\
  will match two floats, and result in a $double$.


\item[$Class(coerce(char|logical\text{{\tt ->}}double, numeric\text{{\tt ->}}0))$] \hfill\\
  will convert any $char$ and $logical$ arguments to $double$, then will
  match any single $numeric$ argument, and emit the type of that argument.

\item[$Class(char \phantom{.} char\text{{\tt ->}}char, numeric \phantom{.} 0|double\text{{\tt ->}}0,  double|1 \phantom{.} numeric\text{{\tt ->}}1)$] \hfill\\
  Either two $chars$ will result in a $char$, or, if two arguments are
  $numeric$, they should either have the same mclass or at least one
  argument has to be a $double$, in which case it will return the mclass
  of the other argument.

\item[$Class(none\text{{\tt ->}}double)$] \hfill\\
  If there are no inputs, will result in a $double$ (i.e. this models a
  double constant).

\item[$Class(parent \phantom{.} any?)$] \hfill\\
  Matches whatever the parent builtin matches, but will allow for one
  extra argument with any mclass.

\item[$MatlabClass(char|logical 1\text{{\tt ->}}error, natlab)$] \hfill\\
  This will define separate semantics for \matlab, compared to natlab.
  The example specifies that \matlab will reject any input that is either two
  $chars$ or two $logicals$, but use the original natlab definition other
  than that.

\item[$Class(numeric* \phantom{.} (typeString(numeric)|(none\text{{\tt ->}}double)))$] \hfill\\
  Will match any number of $numeric$ arguments. If the last argument
  is a $char$, will attempt to interpret it as a string denoting a
  numeric type. if it is, return that numeric type. if it is a string
  of unknown value, return all $numeric$. if it's another string, return
  an error. if the last argument is not a string, return a $double$.
  This can be used for function calls like
       {\tt ones(3,3)} or 
       {\tt ones(2,2,4,4,\textquotesingle int8\textquotesingle)}
\end{description}

%\section{ Source Code }
%Where to find the definition:
%- processTags.py (did it move?) shows the python definition
%- ClassPropTools.java has the Java implementation of the expr nodes



\newpage
\subsection{Grammar}
\vspace{-.2cm}
Below is the complete grammar of the class propagation language. The overall
goal is to produce a node 'cases'.
\begin{footnotesize}
\vspace{-.2cm}
\mynote{added grammar section}
\begin{verbatim}
%terminals NUMBER, LPAREN, RPAREN, OROR, OR, COMMA, MULT, QUESTION, ARROW, ID;
%terminals COERCE, TYPESTRING;

%left  RPAREN;
%left  MULT, QUESTION;
%left  OR;
%left  CHAIN;
%left  ARROW;
%left  COMMA;
%left  OROR;

cases
    = list
    ;
list
    = expr                    
    | expr COMMA list
    ;
expr 
    = clause ARROW clause
    | expr   OROR  expr   
    | clause
    ;
clause
    = clause QUESTION
    | clause MULT
    | clause clause @ CHAIN
    | clause OR clause
    | NUMBER
    | ID
    | LPAREN expr RPAREN
    | COERCE LPAREN expr COMMA expr RPAREN
    | TYPESTRING LPAREN expr RPAREN
    ;
\end{verbatim}
\end{footnotesize}
