Types and type declarations

Types and type constructors

Values in Timber are classified into types. The integer value 7 has type Int, a fact that is expressed in Timber as 7 :: Int, so :: is read "has type". One seldom adds such explicit type information to expressions in Timber code, but it is allowed to do so. More common is to supply type signatures as documentation to top-level definitions, but also these can be omitted, leaving to the Timber compiler to infer types.

Timber also has type constructors, which can be thought of as functions that take types as arguments and give a type as result. An example is the primitive type constructor Request, which takes a type a as an argument and constructs the type Request a of methods (in the object-oriented sense) returning a value of type a.

Kinds and kind declarations

Timber types and type constructors are classified by their kind. All types have kind *, while type constructors that expect one type argument (such as e.g. Request) have kind * -> *. In general, a kind is either * or k1 -> k2 where k1 and k2 are kinds. A type constructor of kind k1 -> k2 expects an argument of kind k1; the result is then a type (constructor) of kind k2.

The programmer may declare the kind of a type constructor in a top-level kind declaration:

con :: kind

This is particularly useful when defining abstract data types; in the public part of a module one declares the kind of an abstract type and the signatures of the operators; the actual type definition and equations are given in the private part.

Examples Comments
Stack :: * -> *Stacks with elements of arbitrary type
Dictionary :: * -> * -> *Dictionaries storing info about keys

Primitive types

We first describe the primitive types of Timber. In Timber code it is always clear from the context whether an expression denotes a type or a value, so some types use the same syntax for type expressions as for values, without confusion. (A beginner might disagree about the last two words.)

Primitive simple types

As part of the language, the following primitive types are provided:

Literals of types Int and Float are as in most programming languages; integer constants can be given in octal or hexadecimal formed if prefixed by 0o and 0x, respectively.

Time values are expressed using the primitive functions sec, millisec, microsec and nanosec, which all take an integer argument and return a Time value. Of course, millisec 1000 and sec 1 denote the same value.

Character literals are written within single quoutes as in 'a' or '3'; common escaped characters are '\n' and '\t' for newline and tab, respectively. (Many other forms of character literals omitted.)

Primitive type constructors

The following type constructors are also primitive in the language.

Polymorphic types

We can now form complex types such as

Int -> Int -> Bool
[Int] -> Int
(a -> Bool) -> [a] -> [a]

The two first examples are monomorphic; they involve only known types and type constructors. The third is polymorphic; it involves the type variable a (a type variable since it starts with a lower-case letter), that stands for an arbitrary type. A function possessing this type can be used at any type obtained by substituting a type for a.

The type variable a is implicitly bound in such a type expression; one should think of an implicit "for all a" quantification prepended to the type expression.

Data types

The programmer may introduce new ways of constructing data by defining data types. The simplest case is enumeration types like

data Day = Mon | Tue | Wed | Thu | Fri | Sat | Sun
The type Day contains the seven constructor values that are enumerated in the right hand side.

The constructors may have arguments, as in

data Temp = Fahrenheit Int | Celsius Int

Values in type Temp are e.g., Fahrenheit 451 and Celsius 100. There may be one, two or more alternatives and a constructor may have more than one argument. A data type for a web log entry might be

data Entry = Entry IPAddress Date URL Method Int

where a value of type Entry might be

Entry "123.456.789.000" (May 29 2007) "http://www.abc.def"  GET 321

given suitable type definitions for the other types involved. Note that the type and the constructor have the same name; this is OK since types and constructors live in different namespaces.

We may also define parameterised data types:

data Tree a b = Nil | Branch (Tree a b) a b (Tree a b)

Tree thus has kind * -> * -> * and a value of type Tree String Int is a binary tree with a String and an Int stored in each internal node.

Two different data types may not use the same constructor name; with the above definition, no other data type in the same module can use constructor Nil. For data types in imported modules there is no problem if they use Nil; only that the qualified name must be used for the imported constructor.

Struct types

Struct, or record, types collect values bound to named selectors. Declarations have the syntax

struct con var* where

struct Point where
  x, y :: Int
struct Dictionary a b where
  insert :: a -> b -> Action
  lookup :: a -> Request (Maybe b)

An example value of type Point is Point {x=3, y=7}. The order between the fields is not significant, so Point {y=7, x=3} is the same value. Similarly as for constructors, two different struct types in the same module may not use the same selector name. Thus a struct value is uniquely defined by the collection of selectors and the type name can be omitted from the value; {x=3, y=7} is again the same value.

If p :: Point, the selectors are accessed using dot notation, so the two integer coordinates are p.x and p.y, respectively.

A struct type may have any number of selectors and the types of selectors are arbitrary. A struct type may also be parameterised as shown by Dictionary, a type suitable as an interface to an object that acts as a dictionary, storing information of type b about keys of type a. (The result type Maybe b for lookup is intended to capture the possibility that the given key is not stored in the dictionary; the prelude defines data Maybe a = Nothing | Just a.)

Type synonyms

The user may introduce new names for existing types:

type Age = Int
type IPAddress = String
type List a = [a]
type Pair a b = (a,b)

Such definitions do not introduce new types; they can only be helpful to improve program readability. They may not be recursive and can not be partially applied (i.e., Pair Int is not a legal type constructor). The prelude introduces one type synonym:

type String = [Char]


Subtyping for struct types

Struct types and data types may be defined in subtype hierarchies. As an example, we can extend Point:

struct Point3 < Point where
  z :: Int

We define Point3 to be a subtype of Point; for struct types this means that Point3 has all the selectors of Point and possibly some more (in the example, one more: z). So we have {x=0, y=3, z=5} :: Point3. A function that expects a Point as argument can be given a Point3 without problem, since all the function can do with its argument is use the selectors x and y, which are present also in a Point3.

As another example we might split the dictionary type into two:

struct LookupDict a b where
  lookup :: a -> Request (Maybe b)

struct Dictionary a b < LookupDict a b where
  insert :: a -> b -> Action

In a program we may build a dictionary dict :: Dictionary a b and then send it to an unprivileged client typed as a LookupDict; the client can then only lookup information, not insert new key/info pairs.

A struct type may have several supertypes; given a struct type

struct Object where
  self :: OID
where OID is a type that allows test for equality between objects, we could have defined
struct Dictionary a b < LookupDict a b, Object where
  insert :: a -> b -> Action

to get the same effect as before and, in addition, the possibility to test whether two dictionaries are the same (meaning same object, not equivalent content).

Subtyping for data types

We can also define hierarchies of data types, but these are completely separate from any hierarchy of struct types; a data type can never be a sub- or supertype of a struct type. For data types we may add new constructors to get a supertype:

data CEntry > Entry = Corrupt

Type CEntry adds another constructor to the type Entry defined above; a CEntry is either a proper entry as above or Corrupt. A function that is defined to take a Entry as argument cannot accept a CEntry; it may stumble on a Corrupt entry. The converse is OK; newly defined functions on CEntry values can happily take an Entry; they will not have to use their Corrupt case.

Subtyping among primitive types

The following subtyping relations hold between primitive types:

Request a < Cmd s a
Action < Cmd s Msg
Ref a < OID