\section{Types}

\subsection{Rationale}

\Kaya{} is a polymorphic statically typed language; i.e., types are
checked at compile time and values retain the same type throughout
their lifetime. There are two major advantages to this over more
dynamically typed languages. Firstly, several classes of programming
error are caught before the program is run, rather than at some
possibly obscure and difficult to reproduce point during
execution. Secondly, static typing allows the programmer to describe
data structures more precisely, which is a valuable aid both for the
programmer and the compiler. Besides, there are already lots of
dynamically typed scripting languages!

Unlike more traditional statically typed languages such as C++ and
Java it is not usually necessary to declare the types of local
variables, since these can (in almost all cases) be inferred from
context. \Kaya{}'s type system also allows you to create and use
variables freely without declaring them in advance, and without
explicit casting.

Programming is about manipulating data, and if data structures are
well designed, manipulating them should be easy. This was a point made
by Fred Brooks many years ago \cite{manmonth} and repeated by Eric
Raymond \cite{esr}. Therefore, \Kaya{} provides a notation for
accurately describing and manipulating data structures as algebraic
data types (a feature more commonly seen in functional languages such
as Haskell \cite{haskell-report} and ML \cite{ml}). Before looking at
program structure, and how to manipulate data, let us consider the
datatypes available in \Kaya{}.

\subsection{Primitive Types}

\fragment{
\BNF{
\Rule{\MC{type}}{\CD{Int}}
\Or{\CD{Char}}
\Or{\CD{Bool}}
\Or{\CD{Float}}
\Or{\CD{String}}
\Or{\CD{File}}
\Or{\CD{Ptr}}
\Or{\CD{Exception}}
\Or{\CD{Void}}
\Or{\ldots}
}
}

There are a number of primitive types, which can be combined into
various forms of compund types. Compound types can be built as
arrays (discussed in section \ref{arrays}), user defined types (in section
\ref{usertypes}), or function types (discussed
in section \ref{funtypes}). 

The primitive types in \Kaya{} are described in Table \ref{primtable}.

\begin{table}[h]
\begin{tabular}{|l|l|l|}
\hline
Type name & Meaning & Example values\\
\hline
\CD{Int} & 32 bit Integers & \CD{42}, \CD{6}, \ldots \\
\CD{Char} & Characters & \CD{'a'}, \CD{'Z'},
\CD{'\SL{}n'}, 
\ldots \\
\CD{Bool} & Boolean & \CD{true}, \CD{false} \\
\CD{Float} & Floating point values & \CD{42.0}, \CD{3.1415},
\CD{2.718}, \ldots \\
\CD{String} & Strings of characters &
\CD{"Fish"},\CD{"Hello world\SL{}n"}, \ldots \\
\CD{File} & File handles & N/A \\
\CD{Exception} & Exceptions  &
\CD{Exception("Out Of Cheese Error",1)} \\
\CD{Ptr} & Foreign language pointers &
N/A \\
\CD{Void} & Empty type & none \\
\hline
\end{tabular}
\caption{Primitive Types}
\label{primtable}
\end{table}


There are no pointer types, other than pointers to foreign objects. In
\Kaya{} everything is a reference (and therefore, internally, a
pointer). The programmer never needs to worry about any
memory management details; it is all handled by the run-time system
and the garbage collector\footnote{The current implementation
usesthe Boehm garbage collector~\cite{boehm-gc}}.

C and Java programmers should note that all concrete types begin with
a capital letter. This is to allow a distinction with polymorphic type
variables (see section \ref{polymorphic}).

\subsection{Arrays}

\label{arrays}

\fragment{
\BNF{
\Rule{\MC{type}}{\ldots}
\Or{\CD{[} \MC{type} \CD{]}}
}
}

Given a type \CD{t}, an array containing values of type \CD{t} is
denoted by \CD{[t]}. An array value can be constructed by listing the
values between square brackets, \CD{[]}, e.g.:

\begin{verbatim}
empty = [];
count = [1,2,3,4,5,6,7,8,9,10]; // Type is [Int]
people = ["Fred","Jim","Sheila"]; // Type is [String]
\end{verbatim}

Integer arrays can also be constructed with \demph{ranges}, e.g.:

\begin{verbatim}
count = [1..100];
evens = [2,4..100];
downards = [10,9..0];
\end{verbatim}

\subsection{Function Types}
\label{funtypes}

\fragment{
\BNF{
\Rule{\MC{type}}{\ldots}
\Or{\MC{type} \CD{(} \oneplus{\MC{type},} \CD{)}}
}
}

Functions are first class values, and so have types like any other
value. A function type expresses the return type and type argument
types, e.g. \CD{Int(Float,String)} is the type of a function which
takes
a \CD{Float} and a \CD{String} and returns an \CD{Int}.

\subsection{Polymorphic Types}
\label{polymorphic}

\fragment{
\BNF{
\Rule{\MC{type}}{\ldots}
\Or{\MC{lc\_identifier}}
}
}

A polymorphic type (i.e. a generic type which can be instantiating by
another concrete type) is denoted by an identifier beginning with a
lower case identifier. The case of the initial letter distinguishes
polymorphic type variables from concrete types.

\subsection{User Defined Types}
\label{usertypes}

\fragment{
\BNF{
\Rule{\MC{type}}{\ldots}
\Or{\CD{uc\_identifier}}
\Or{\CD{uc\_identifier} \CD{<} \oneplus{\MC{type},} \CD{>}}
}
}

User defined types can describe enumerations, records or discriminated
unions. The grammar for declaring a data type is as follows:

\fragment{
\BNF{
\Rule{\MC{data\_decl}}{\zeroplus{\MC{data\_opt}} \CD{data} \MC{uc\_identifier} \MC{params}
  \MC{data\_def}}
\Rule{\MC{params}}{}
\Or{\CD{<}\zeroplus{\MC{lc\_identifier},}\CD{>}}
\Rule{\MC{data\_def}}{
\CD{(} \zeroplus{$\langle$\MC{type} \maybe{\MC{identifier}}$\rangle$,} \CD{)}
}
\Or{\oneplus{$\langle$\MC{constructor}\CD{|}$\rangle$}}

\Rule{\MC{constructor}}{\MC{identifier}}
\Or{\MC{identifier}
\CD{(} \zeroplus{$\langle$\MC{type} \maybe{\MC{identifier}}$\rangle$,} \CD{)}

}
\Rule{\MC{data\_opt}}{\CD{public}}
\Or{\CD{private}}
\Or{\CD{abstract}}
}
}

Any type variable used in the data definition must have been listed in
\MC{params}, otherwise there is a compile time error. Identifier names
are optional, and a name can occur at most once within a data
declaration.

The options \CD{public}, \CD{private} and \CD{abstract} define the
type's visibility outside the current module or compilation unit (see
section \ref{sect:modules}). \CD{public} means the type is completely
visible, \CD{private} means the type is invisible. \CD{abstract} means
that the type is visible, but the constructors are invisibile.

Some brief examples follow.

\subsubsection{Enumerations}

An enumeration consists of a number of constructor declarations with
no arguments, e.g.:

\begin{verbatim}
data Colour = Red | Green | Blue;
data Weather = Sunny | Cloudy | Rainy | Snowy;
\end{verbatim}

\subsubsection{Records}

A record is a data type with only one constructor, e.g.:

\begin{verbatim}
data Person(String name, Int age);
data Location(Int x, Int y, Int z);
\end{verbatim}

Values of these types are constructed as follows:

\begin{verbatim}
bob = Person("Bob",30);
wheresbob = Location(1900,762,800);
\end{verbatim}

Field values can be projected out of such values by referring to the
field name:

\begin{verbatim}
bobsname = bob.name;
bobsheight = wheresbob.z;
\end{verbatim}

\subsubsection{Discriminated Unions}

Discriminated unions combine enumerations and records, e.g.:

\begin{verbatim}
data IntOrString = mkInt(Int num)
                 | mkString(String str);
data List<a> = nil
             | cons(a head, List<a> tail);
\end{verbatim}

\CD{IntOrString} represents either an integer or string, depending on
whether it is constructed with \CD{mkInt} or \CD{mkString}. \CD{List}
is a polymorphic type representing a linked list.

Projection of a value from a discriminated union checks whether the
correct constructor was used; e.g. the following are ok:

\begin{verbatim}
x = mkInt(5);
list = cons("Fred",cons("Jim",cons("Sheila",nil)));
number = x.num;
first = list.head;
\end{verbatim}

The following would generate an error at run-time:

\begin{verbatim}
x = mkString("Sossidges");
number = x.num; // Oops, didn't use mkInt.
\end{verbatim}

See section \ref{caseexp} (\CD{case} statements) for more on how to
work with discriminated unions.

\subsection{Exceptions}
\label{exceptions}

An exception is a value describing what went wrong. It is simply a
pair of a string (the error message) and an integer (the error code).

\fragment{
\BNF{
\Rule{\MC{exception}}
{\CD{Exception} \CD{(} \MC{typed\_expr} \CD{,} \MC{typed\_expr} \CD{)}}
}
}

See section \ref{sect:expressions} for the definition of \MC{typed\_expr}.