The Type System

Halcyon is a statically typed language with full type inference. Type inference means that the types of functions and variables do not need to be written, they can be guessed by the compiler. Compare a function which adds two integers written in C versus in Halcyon:

int add_integers(int x, int y) {
  return x + y;
}

<span class='hljs-keyword'>let</span> add_integers = <span class='hljs-keyword'>fn</span> <span class='hljs-params'>x</span> <span class='hljs-params'>y</span> <span class='hljs-keyword'>=&gt;</span> x <span class='hljs-operator'>+</span> y

Type annotations can be added using :, but they are not necessary. It is an error for a type annotation to be different from the actual type.

<span class='hljs-keyword'>let</span> add_integers <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>integer</span> <span class='hljs-operator'>-&gt;</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>integer</span> =
  <span class='hljs-keyword'>fn</span> <span class='hljs-punctuation'>(</span>x <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>integer</span><span class='hljs-punctuation'>)</span> <span class='hljs-punctuation'>(</span>y <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>integer</span><span class='hljs-punctuation'>)</span> <span class='hljs-keyword'>=&gt;</span> x <span class='hljs-operator'>+</span> y

This book will often provide type annotations for clarity's sake, but this is not intended to imply they are best practice or required.

Primitive types

The following is a list of the primitive types, as well as their equivalents in C:

<span class='hljs-keyword'>let</span> nothing <span class='hljs-punctuation'>:</span> <span class='hljs-type'>(</span><span class='hljs-type'>)</span> = <span class='hljs-punctuation'>(</span><span class='hljs-punctuation'>)</span>
<span class='hljs-keyword'>let</span> life <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>integer</span> = <span class='hljs-variable constant_'>42</span>
<span class='hljs-keyword'>let</span> pi <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>real</span> = <span class='hljs-variable constant_'>3.14159</span>
<span class='hljs-keyword'>let</span> yes <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>boolean</span> = <span class='hljs-built_in'>true</span>
<span class='hljs-keyword'>let</span> grade <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>glyph</span> = <span class='hljs-string'>'A'</span>
<span class='hljs-keyword'>let</span> greeting <span class='hljs-punctuation'>:</span> <span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>string</span> = <span class='hljs-string'>"Hello world!"</span>

Arrays

An array is a list of values of the same type, and that has a variable length. To define an array, use square brackets:

<span class='hljs-keyword'>let</span> numbers <span class='hljs-punctuation'>:</span> [<span class='hljs-title class_'>std</span><span class='hljs-punctuation'>::</span><span class='hljs-type'>integer</span>] = [<span class='hljs-variable constant_'>1</span><span class='hljs-punctuation'>,</span> <span class='hljs-variable constant_'>2</span><span class='hljs-punctuation'>,</span> <span class='hljs-variable constant_'>3</span><span class='hljs-punctuation'>,</span> <span class='hljs-variable constant_'>4</span>]

Tuples

A tuple is a list of values that may be different types, and has a fixed length. To define a tuple, use parenthesis:

<span class='hljs-keyword'>let</span> single_tuple = <span class='hljs-punctuation'>(</span><span class='hljs-string'>"alone"</span><span class='hljs-punctuation'>,</span><span class='hljs-punctuation'>)</span>
<span class='hljs-keyword'>let</span> grocery_list = <span class='hljs-punctuation'>(</span><span class='hljs-string'>"eggs"</span><span class='hljs-punctuation'>,</span> <span class='hljs-string'>"bacon"</span><span class='hljs-punctuation'>,</span> <span class='hljs-string'>"milk"</span><span class='hljs-punctuation'>)</span>
<span class='hljs-keyword'>let</span> favorite_numbers = <span class='hljs-punctuation'>(</span><span class='hljs-variable constant_'>42</span><span class='hljs-punctuation'>,</span> <span class='hljs-variable constant_'>2.718</span><span class='hljs-punctuation'>,</span> <span class='hljs-string'>'∞'</span><span class='hljs-punctuation'>)</span>
<span class='hljs-keyword'>let</span> list_of_lists = <span class='hljs-punctuation'>(</span>grocery_list<span class='hljs-punctuation'>,</span> favorite_numbers<span class='hljs-punctuation'>)</span>

Function types

A fundamental rule in Halcyon is that every function has a single parameter. This is achieved using a process called currying. Understanding this concept is extremely important, so lets work through an example. Consider this function:

<span class='hljs-keyword'>let</span> add_integers = <span class='hljs-keyword'>fn</span> <span class='hljs-params'>x</span> <span class='hljs-params'>y</span> <span class='hljs-params'>z</span> <span class='hljs-keyword'>=&gt;</span> x <span class='hljs-operator'>+</span> y <span class='hljs-operator'>+</span> z

The compiler will automatically transform add_integers into the following:

<span class='hljs-keyword'>let</span> add_integers =
  <span class='hljs-keyword'>fn</span> <span class='hljs-params'>x</span> <span class='hljs-keyword'>=&gt;</span>
    <span class='hljs-keyword'>fn</span> <span class='hljs-params'>y</span> <span class='hljs-keyword'>=&gt;</span>
      <span class='hljs-keyword'>fn</span> <span class='hljs-params'>z</span> <span class='hljs-keyword'>=&gt;</span> x <span class='hljs-operator'>+</span> y <span class='hljs-operator'>+</span> z

Let us see how the expression add_integer 1 2 3 is evaluated. First, substitute the variable name for its definition:

<span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> x <span class='hljs-keyword'>=&gt;</span> <span class='hljs-keyword'>fn</span> y <span class='hljs-keyword'>=&gt;</span> <span class='hljs-keyword'>fn</span> z <span class='hljs-keyword'>=&gt;</span> x <span class='hljs-operator'>+</span> y <span class='hljs-operator'>+</span> z<span class='hljs-punctuation'>)</span> <span class='hljs-variable constant_'>1</span> <span class='hljs-variable constant_'>2</span> <span class='hljs-variable constant_'>3</span>

Next, call the outermost function with the first argument 1:

<span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> y <span class='hljs-keyword'>=&gt;</span> <span class='hljs-keyword'>fn</span> z <span class='hljs-keyword'>=&gt;</span> <span class='hljs-variable constant_'>1</span> <span class='hljs-operator'>+</span> y <span class='hljs-operator'>+</span> z<span class='hljs-punctuation'>)</span> <span class='hljs-variable constant_'>2</span> <span class='hljs-variable constant_'>3</span>

Repeat with the next two arguments 2 and 3:

<span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> y <span class='hljs-keyword'>=&gt;</span> <span class='hljs-keyword'>fn</span> z <span class='hljs-keyword'>=&gt;</span> <span class='hljs-variable constant_'>1</span> <span class='hljs-operator'>+</span> y <span class='hljs-operator'>+</span> z<span class='hljs-punctuation'>)</span> <span class='hljs-variable constant_'>2</span> <span class='hljs-variable constant_'>3</span>
<span class='hljs-punctuation'>(</span><span class='hljs-keyword'>fn</span> z <span class='hljs-keyword'>=&gt;</span> <span class='hljs-variable constant_'>1</span> <span class='hljs-operator'>+</span> <span class='hljs-variable constant_'>2</span> <span class='hljs-operator'>+</span> z<span class='hljs-punctuation'>)</span> <span class='hljs-variable constant_'>3</span>
<span class='hljs-variable constant_'>1</span> <span class='hljs-operator'>+</span> <span class='hljs-variable constant_'>2</span> <span class='hljs-operator'>+</span> <span class='hljs-variable constant_'>3</span>
<span class='hljs-variable constant_'>6</span>

The type of a function is written as a -> b, where a is the parameter type, and b is the return type. The -> operator, like =>, is right associative. This means that a -> b -> c is interpreted as a -> (b -> c). The type of add_integers in the example above is:

integer -> integer -> integer -> integer