%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\appendix


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{The TL Grammar}
\label{Sec. The Tycoon Grammar}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Syntax Notations}
\label{Sec. Syntax Notations}

The following notation is used for the definition of syntactical and
lexical elements. \s{Id} denotes a non-terminal symbol (a meta variable)
and \s{A} and \s{B} denote syntactic expressions.

\begin{center}
\begin{tabular}{ll}
  \s{Id$_1$, \ldots, Id$_n$::= A;} & the non-terminal symbols \s{Id$_i$} \\
                    &  are defined as \s{A} ($n\geq1$) \\
  \s{Id}            & a non-terminal symbol \\
  \k{if}            & a terminal symbol \\
  \synquot{x}       & the character \s{x} (\synquot{} is the empty string \\
                    & \synquot{\dq} is a double quote) \\
  \synbrack{A}      & means \s{A} \\
  \s{A B}           & means \s{A} followed by \s{B} (binds strongest) \\
  \s{A $|$ B}       & means \s{A} or \s{B} \\
  \synopt{A}        & means \synbrack{\synquot{} $|$ A} \\
  \synrep{A}        & means \synbrack{\synquot{} $|$ A \synrep{A}} \\
\end{tabular}
\end{center}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Symbols}
\label{Sec. Symbols}

The source text of a \Tl\ program consists of a sequence of characters
that is converted into a sequence of symbols of the categories \s{int,
real, longreal, char, string, identifier, infix, colonInfix} and \s{delimiter}.

The set of formatting characters is an implementation-dependent subset
of the non-printable characters and includes at least the characters
space, tab, carriage return, line feed and vertical tab.

Comments are sequences of arbitrary printable or formatting characters
that are enclosed by \mbox{\s{(* *)}}. Comments can be nested.

To read a symbol, all formatting characters are skipped and then the
longest sequence of characters that forms a symbol is read. Therefore, a
space in the source text is only required between two identifiers or two
(colon-) infix symbols that appear in direct succession.

\begin{xple}
int::=
        \verb$["~"]$ digit \synrep{digit};
real::=
        int \synquot{.} digit \synrep{digit} $|$
        int \synopt{\synquot{.} digit \synrep{digit}} \synquot{E} int;
longreal::=
        int \synopt{\synquot{.} digit \synrep{digit}} \synquot{D} int;
char::=
        \synquot{'} \synbrack{digit $|$ alpha $|$ special $|$ escape $|$ delimiter $|$ reserved} \synquot{'};
string::=
        \synquot{\dq} \synrep{digit $|$ alpha $|$ special $|$ escape $|$ delimiter $|$ reserved} \synquot{\dq};
infix::=
        special \synrep{special};
colonInfix::=
        \synquot{:} \synrep{special};
identifier::=
        alpha \synrep{digit $|$ alpha};
delimiter::=
        \synquot{(} $|$ \synquot{)} $|$ \synquot{\{} $|$ \synquot{\}} $|$ \synquot{[} $|$ \synquot{]} $|$ \synquot{.} $|$ \synquot{,} $|$ \synquot{;};
digit::=
        \synquot{0} $|$ \synquot{1} $|$ \synquot{2} $|$ \synquot{3} $|$ \synquot{4} $|$ \synquot{5} $|$ \synquot{6} $|$ \synquot{7} $|$ \synquot{8} $|$ \synquot{9};
alpha::=
        \synquot{A} $|$ \synquot{B} $|$ ... $|$ \synquot{Z} $|$ \synquot{a} $|$ \synquot{b} $|$ ... $|$ \synquot{z};
reserved::=
        \verb$"~"$ $|$ \synquot{ };
special::=
        \verb$"@"$ $|$ \verb$"#"$ $|$ \verb^"$"^ $|$ \verb$"%"$ $|$ \verb$"&"$ $|$ \verb$"*"$ $|$ \verb$"_"$ $|$ \verb$"+"$ $|$ \verb$"="$ $|$ \verb$"-"$ $|$
        \verb$"|"$ $|$ \verb$"\"$ $|$ \verb$"`"$ $|$ \verb$":"$ $|$ \verb$"<"$ $|$ \verb$">"$ $|$ \verb$"/"$ $|$ \verb$"^"$ $|$ \verb$"?"$ $|$ \verb$"!"$;
escape::=
        \verb$"\"$ $($\synquot{n} $|$ \synquot{t} $|$ \synquot{r} $|$ \synquot{f} $|$ \verb$"\"$ $|$  \verb$"'"$ $|$ \synquot{\dq} $|$ digit digit digit$)$;
\end{xple}

Escape characters in character and string literals are interpreted as follows:

\begin{center}
\begin{tabular}{|l|l|}
\hline
  \verb$\n$   &  new line \\
  \verb$\t$   &  tab\\
  \verb$\r$   &  carriage return \\
  \verb$\f$   &  form feed \\
  \verb$\'$   &  \verb$'$ \\
  \verb$\"$   &  \verb$"$ \\
  \verb$\\$   &  \verb$\$ \\
  \verb$\nnn$ &  A single character with the code \s{nnn} \\
              & (three decimal digits that denote an integer in the interval [0,255])\\
  \verb$\$f \ldots f\verb$\$ & The sequence of formatting characters \s{f} is ignored\\
\hline
\end{tabular}
\end{center}


The last rule allows the programmer to define string literals that exceed the
length of a single source line.

The above definitions make a scanner implementation possible that requires just
a single character lookahead.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Reserved Keywords}
\label{Sec. Reserved Keywords}

The \index{reserved keyword} following identifiers and (colon-) infix symbols are reserved keywords
and cannot be used as user-defined identifiers in \Tl\ programs.

\begin{xple}
    \k{and} \k{andif} \k{assert} \k{begin} \k{case} \k{do} \k{downto} \k{else} \k{elsif} \k{end} \k{exception} 
    \k{exit} \k{export} \k{extend} \k{for} \k{fun} \k{hide} \k{if} \k{import} \k{in} \k{interface} \k{let} \k{library}
    \k{loop} \k{module} \k{of} \k{ok} \k{open} \k{orif} \k{raise} \k{rec} \k{record} \k{reraise} \k{then} \k{try} 
    \k{tuple} \k{typecase} \k{upto} \k{var} \k{when} \k{while} \k{with}

    \k{Dyn} \k{Exception} \k{Fun} \k{Let} \k{Nok} \k{Ok} \k{Oper} \k{Rec} \k{Record} \k{Repeat} \k{Tuple}

    = $<$: : ? !
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Productions}
\label{Sec. Productions}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Compilation Units}
\label{Sec. Compilation Units}

Based\index{compilation unit}\index{interface}\index{module}\index{library} on the symbols and keywords defined in the previous sections, the
grammar of \Tl\ is described by the following productions that define a
non-ambiguous LL(1) grammar. \s{Unit} is the root production for the
language.

\begin{xple}
Unit::=
        \synbrack{Library $|$ Interface $|$ Module $|$ Import $|$ Bindings} \synquot{;};
Library::=
        \k{library} identifier Import \k{with} \synrep{ComponentSignatures}
        \synopt{\k{hide} \synrep{identifier}} \k{end};
ComponentSignatures::=
        \k{library} \synrep{identifier} $|$
        \k{interface} \synrep{identifier} $|$
        \k{module} \synrep{identifier \synquot{:} identifier};
Interface::=
        \k{interface} identifier Import \k{export} Signatures \k{end};
Module::=
        \k{module} identifier Import \k{export} Bindings \k{end};
Import::=
        \synopt{\k{import} \synrep{\synopt{\synquot{:}} identifier}};
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Bindings}
\label{Sec. Bindings}

\index{binding}
\begin{xple}
Bindings::=
        \synrep{TypeBindings $|$ ValueBindings $|$ \k{open} ValueIde \synopt{\synquot{:} Type}
            \synquot{:} \synopt{\k{Dyn}} Type $|$ \synopt{\k{var}} Value};
TypeBindings::=
        \synrep{\k{Let} \synopt{\k{Rec}} TypeBinding \synrep{\k{and} TypeBinding}};
TypeBinding::=
        \synopt{\k{Dyn}} TypeIde Parameters \synopt{\synquot{$<:$} Type} \synquot{=} Type;
ValueBindings::=
        \synrep{\k{let} \synopt{\k{rec}} ValueBinding \synrep{\k{and} ValueBinding}};
ValueBinding::=
        \synopt{\k{var}} ValueIde Parameters \synopt{\synquot{:} Type} \synquot{=} Value;
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Values}
\label{Sec. Values}

\index{value}
\begin{xple}
Value::=
        Value$_1$ \synrep{\synbrack{\k{orif} $|$ \k{andif} $|$ colonInfix} Value$_1$};
Value$_1$::=
        Value$_2$ \synrep{infix Value$_2$};
Value$_2$::=
        Value$_3$ \synrep{\synquot{(} Bindings \synquot{)} $|$ \synquot{?} CaseIde $|$ \synquot{!} CaseIde $|$
                    \synquot{.} FieldIde $|$ \synquot{[} Value \synquot{]} $|$
                    \k{of} Bindings Location \k{end}};
\end{xple}
\begin{xple}
Value$_3$::=
        \verb$"{"$ Value \verb$"}"$ $|$
        ValueIde $|$
        \k{ok} $|$
        int $|$ char $|$ string $|$ real $|$ longreal $|$
        \k{fun} \synquot{(} Signatures \synquot{)} \synopt{\synquot{:} Type} Location Value $|$
        \k{tuple} Location \synopt{\k{case} CaseIde \k{of} Type \synopt{\k{with}}} Bindings \k{end} $|$
        \k{record} Location Bindings \k{end} $|$
        \k{extend} Value \k{with} Bindings \k{end} $|$
        \k{array} Location Bindings \k{end} $|$
        \k{exception} Value \synopt{\k{with} Signatures \k{end}} $|$
        \k{begin} Location Bindings \k{end} $|$
        \k{if} Value \k{then} Bindings \synrep{\k{elsif} Value \k{then} Bindings}
                \synopt{\k{else} Bindings} \k{end} $|$
        \k{case} \synopt{\k{of}} Value \synrep{\k{when} CaseIdeList \synopt{\k{with} ValueIde} \k{then} Bindings}
                \synopt{\k{else} Bindings} \k{end} $|$
        \k{typecase} \synrep{ValueIde \synquot{.}} TypeIde \synrep{\k{when} Type \k{then} Bindings}
                \synopt{\k{else} Bindings} \k{end} $|$
        \k{loop} Bindings \k{end} $|$
        \k{exit} $|$
        \k{while} Value \k{do} Bindings \k{end} $|$
        \k{for} ValueIde \synquot{=} Value \synbrack{\k{upto} $|$ \k{downto}} Value \k{do} Bindings \k{end} $|$
        \k{try} Bindings \synrep{\k{when} Value \synopt{\k{with} ValueIde} \k{then} Bindings}
                \synopt{\k{else} Bindings} \k{end} $|$
        \k{raise} Value \synopt{\k{with} Bindings \k{end}} $|$
        \k{reraise} $|$
        \k{assert} Value;
Location::=
        \synopt{\k{in} Value};
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Signatures}
\label{Sec. Signatures}

\index{signature}
\begin{xple}
Signatures::=
        \synrep{TypeSignatures $|$ ValueSignatures $|$ TypeBindings $|$ \k{Repeat} Type};
TypeSignatures::=
       \synopt{\k{Dyn}} \synopt{TypeIdeList Parameters} \synquot{$<:$} Type;
ValueSignatures::=
       \synopt{\k{var}} \synopt{ValueIdeList Parameters} \synquot{:} Type;
Parameters::=
        \synrep{\synquot{(} Signatures \synquot{)}};
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Types}
\label{Sec. Types}

\index{type}
\begin{xple}
Type::=
        Type$_1$ \synrep{colonInfix Type$_1$};
Type$_1$::=
        Type$_2$ \synrep{infix Type$_2$};
\end{xple}
\begin{xple}
Type$_2$::=
        Type$_3$ \synrep{\synquot{(} \synrep{Type} \synquot{)}};
Type$_3$::=
        \verb$"{"$ Type \verb$"}"$ $|$
        \synrep{ValueIde \synquot{.}} TypeIde $|$
        \k{Ok} $|$ \k{Nok} $|$
        \k{Fun} \synquot{(} Signatures \synquot{)} \synquot{:} Type $|$
        \k{Tuple} Signatures \synrep{\k{case} CaseIdeList \synopt{\k{with} Signatures}} \k{end} $|$
        \k{Record} Signatures \k{end} $|$
        \k{Exception} \synopt{\k{with} Signatures \k{end}} $|$
        \k{Oper} \synquot{(} Signatures \synquot{)} \synopt{\synquot{$<:$} Type} Type;
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsubsection{Identifier}
\label{Sec. Identifier}

\index{identifier}
\begin{xple}
ValueIdeList, TypeIdeList, CaseIdeList::=
        Ide \synrep{\synquot{,} Ide};
Ide, ValueIde, TypeIde, FieldIde, CaseIde::=
        identifier $|$ infix $|$ colonInfix $|$ \verb$"{"$ Ide \verb$"}"$;
\end{xple}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\section{Predefined Identifiers}
\label{Sec. Predefined Identifiers}

The\index{predefined, ~ identifier} following tables lists all identifiers of \Tl\ that are accessible
without explicit import. These identifiers are not reserved keywords and
can be rebound (locally) in \Tl\ programs. They are introduced and
explained in more detail in the \Tl\ bootfiles \s{boot.tyc} and
\s{tycoon.tyc}.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Type Identifiers}
\label{Sec. Type Identifiers}

\index{predefined, ~ type}
\begin{tabular}{|l|l|l|}
  \hline
  \bold{Type}   & \bold{Supertype} & \bold{Description} \\
  \hline
  \s{Bool}     & \k{Ok}     & type of boolean literals \\
  \s{Char}     & \k{Ok}     & type of character literals \\
  \s{Int}      & \k{Ok}     & type of integer number literals \\
  \s{Real}     & \k{Ok}     & type of floating point number literals \\
  \s{String}   & \k{Ok}     & type string literals \\
  \s{Locality} & \k{Ok}     & type of locality values \\
  \s{Array}    & \s{\k{Oper}(E $<$:\k{Ok}) \k{Ok}} & arrays with mutable elements of type E \\
  \hline
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Value Identifiers}
\label{Sec. Value Identifiers}

\index{predefined, ~ constant}
\begin{tabular}{|l|l|l|}
  \hline
  \bold{Value}  & \bold{Type} & \bold{Description} \\
  \hline
  \s{false}, \s{true} & \s{Bool}     & boolean values \\
  \s{somewhere}       & \s{Locality} & locality value \\
  \hline
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Infix Functions}
\label{Sec. Infix Functions}

\index{infix operator}
\begin{tabular}{|l|l|l|}
  \hline
  \bold{Symbol} & \bold{Type} & \bold{Description} \\
  \hline
  \s{:=}       & \s{\k{Fun}(A $<$:\k{Ok} \k{var} :A :A) :\k{Ok}} & destructive assignment\\
  \s{==}       & \s{\k{Fun}(A $<$:\k{Ok} :A :A) :Bool}       & identity test \\
  \s{!=}       & \s{\k{Fun}(A $<$:\k{Ok} :A :A) :Bool}       & negation of \s{==} \\
  \hline
  \s{$<$}      & \s{\k{Fun}(:Int :Int) :Bool}    & less than \\
  \s{$>$}      & \s{\k{Fun}(:Int :Int) :Bool}    & greater than \\
  \s{$<$=}     & \s{\k{Fun}(:Int :Int) :Bool}    & less equal than \\
  \s{$>$=}     & \s{\k{Fun}(:Int :Int) :Bool}    & greater equal than \\
  \hline
  \s{+}        & \s{\k{Fun}(:Int :Int) :Int}     & addition \\
  \s{--}       & \s{\k{Fun}(:Int :Int) :Int}     & subtraction \\
  \s{*}        & \s{\k{Fun}(:Int :Int) :Int}     & multiplication \\
  \s{/}        & \s{\k{Fun}(:Int :Int) :Int}     & division \\
  \s{\%}       & \s{\k{Fun}(:Int :Int) :Int}     & modulo \\
  \hline
  \s{$<<$}     & \s{\k{Fun}(:Real :Real) :Bool}  & less than \\
  \s{$>>$}     & \s{\k{Fun}(:Real :Real) :Bool}  & greater than \\
  \s{$<<$=}    & \s{\k{Fun}(:Real :Real) :Bool}  & less equal than \\
  \s{$>>$=}    & \s{\k{Fun}(:Real :Real) :Bool}  & greater equal than \\
  \hline
  \s{++}       & \s{\k{Fun}(:Real :Real) :Real}  & addition \\
  \s{-- --}    & \s{\k{Fun}(:Real :Real) :Real}  & subtraction \\
  \s{**}       & \s{\k{Fun}(:Real :Real) :Real}  & multiplication \\
  \s{//}       & \s{\k{Fun}(:Real :Real) :Real}  & division \\
  \hline
  \s{$\backslash$/} & \s{\k{Fun}(:Bool :Bool) :Bool} & or \\
  \s{/$\backslash$} & \s{\k{Fun}(:Bool :Bool) :Bool} & and \\
  \s{not}           & \s{\k{Fun}(:Bool) :Bool}       & not \\
  \hline
  \s{$<>$} & \s{\k{Fun}(:String :String) :String}    & concatenation \\
  \hline
  \s{extent} & \s{:\k{Fun}(E $<$:\k{Ok} :Array(E)) :Int} & size \\
  \hline
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Functions}
\label{Sec. Functions}

\index{predefined, ~ function}
\begin{tabular}{|l|l|l|}
  \hline
  \bold{Function}  & \bold{Type} & \bold{Description} \\
  \hline
  \s{builtin} & \s{:\k{Fun}(\k{Dyn} FctType $<$:\k{Ok}}                   & builtin function of the \\
              & \hspace{.5cm} \s{name :String  ifFail :FctType) :FctType} & code generator \\
  \s{bind}    & \s{:\k{Fun}(\k{Dyn} FctType $<$:\k{Ok}}                   & external binding to a \\
              & \hspace{.5cm} \s{lib, label, type :String) :FctType}      & C language function \\
  \hline
\end{tabular}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\subsection{Exceptions}
\label{Sec. Exceptions}

\index{exception}
\begin{tabular}{|l|l|l|}
  \hline
  \bold{Exception}  & \bold{Type} & \bold{Description} \\
  \hline
  \s{intOverflow}           & \k{Exception} \k{end} & integer overflow \\
  \s{intError}              & \k{Exception} \k{end} & integer error \\
  \hline
  \s{realError}             & \k{Exception} \k{end} & real error \\
  \hline
  \s{ccallError}            & \k{Exception} \k{with}                    & cannot find library or \\
                            & \hspace{.5cm}\s{lib, entry, type :String} & entry point, or bad \\
                            & \k{end}                                   & arguments \\
  \s{assertError}           & \k{Exception} \k{with}                    & condition in assert \\
                            & \hspace{.5cm}\s{line, column :Int}        & statement violated \\
                            & \hspace{.5cm}\s{where :String}            & \\
                            & \k{end}                                   & \\
  \s{typecaseError}         & \k{Exception} \k{with}                    & non-handled type in \\
                            & \hspace{.5cm}\s{line, column :Int}        & typecase statement \\
                            & \hspace{.5cm}\s{where :String}            & \\
                            & \k{end}                                   & \\
  \s{caseError}             & \k{Exception} \k{with}                    & non-handled case label \\
                            & \hspace{.5cm}\s{line, column :Int}        & in case statement \\
                            & \hspace{.5cm}\s{where :String}            & \\
                            & \hspace{.5cm}\s{variant :Int}             & \\
                            & \k{end}                                   & \\
  \s{tupleProjectError}     & \k{Exception} \k{with}                    & variant projection error \\
                            & \hspace{.5cm}\s{line, column :Int}        & in \s{!} expression \\
                            & \hspace{.5cm}\s{where :String}            & \\
                            & \hspace{.5cm}\s{variant :Int}             & \\
                            & \k{end}                                   & \\
  \s{extendError}           & \k{Exception} \k{with}                    & duplicate label in \\
                            & \hspace{.5cm}\s{line, column :Int}        & record \k{extent} \\
                            & \hspace{.5cm}\s{where :String}            & expression \\
                            & \hspace{.5cm}\s{rcd :\k{Record} \k{end}}  & \\
                            & \hspace{.5cm}\s{label :String}            & \\
                            & \k{end}                                   & \\
  \s{indexOutOfBoundsError} & \k{Exception} \k{with}                    & array index out of \\
                            & \hspace{.5cm}\s{line, column :Int}        & bounds \\
                            & \hspace{.5cm}\s{where :String}            & \\
                            & \hspace{.5cm}\s{arr :Array(\k{Ok})}       & \\
                            & \hspace{.5cm}\s{index :Int}               & \\
                            & \k{end}                                   & \\
  \hline
\end{tabular}

