A Functional Language

    In this post, I will start describing a hypothetical functional programming language that I've been thinking of. I hope to make this into a series of posts, each describing a different aspect of this language.
    Today, I will explain the type system of this language. I'll start by writing about types and type systems, and then about types in my language, including basic types, and how to combine them to create more complex types. Later, I'll describe type classes and class instances.

Types
    Types are one of the most important parts of a statically typed language. They define constraints on the values a variable may hold, and allow you to reason about what data a value has. For example, if you wanted to state that, say, a variable n may only be an integer, that would be a type constraint. You would say n is of type integer. If you wanted to state that the variable index is always nonnegative, you could say that index is of type natural number, and that would provide a constraint on the possible values that index can have.

Type Systems
    A type system is (how I think of it) a way to ensure that variables follow the type constraints imposed upon them, and, if possible, to ensure this at compile time (as opposed to runtime, in a dynamically typed language). A compile-time type system should be able to tell if you are, say, assigning an integer value to a variable declared to hold only booleans. That would be an obvious problem, and a type system should flag that. Another thing that type systems can do is infer type constraints, that is, figure out what types a variable can have, and then automatically declare the variable to have those constraints.

Types in the Language
    In the hypothetical language I'm thinking of, there would be basically three kinds of types. These types can be constructed recursively (or not) to create more complex types. The following three sections will describe each kind.

Function Types
    These are written a -> b and define a constraint on values so that a value of a function type can be applied to an argument (of type a) and produce a value of type b. An example of a function type could be
  string -> integer
and would describe a function that can parse a string into the corresponding integer value.

Variant/Sum Types
    These types define a value which can be exactly one of a certain number of other types. For example, if you would like to constrain a value to either an integer or a string, its type would be
  integer | string.
A value of this type can be either an integer or a string, but not both at the same time (what would it even mean? Maybe in a quantum language it would make sense...)
    Variant types may be recursive; a branch of the variant may include itself. The standard functional definition of a linked list is:
  type List T = Cons(T, List T) | Nil
That basically says that a List is either Nil (end of a list) or it contains a T value (the data) and the rest of the List. A value that matches this type could be:
  let list : List int = Cons(1, Cons(2, Nil))
The variable list now contains a Cons value, with data of 1, where the rest of the list is another Cons value (data=2), whose rest-of-list value is Nil (end of list). In a more palatable format, the list value above could be written as
  let list : List int = [1, 2]
which is obviously much more readable.

Tuple/Product Types
    These types define a value which contains several values (of arbitrary) types. Tuple types are the kind of type that allow you to create more complex structures. A tuple type will always declare that a value will hold a certain number of other values. An example of a tuple type is
  (string, int)
which might define a type which contains data about parsing; the current string, and the current location in the string. A value of type could be
  let parseState = ("Hello, World!", 0)
which describes the beginning of a parse on the string "Hello, World!".
    A tuple type may not be recursive, because otherwise the type itself would be infinitely large. A variant type, however, may be recursive if (and only if) there is at least one branch of the variant that is not recursive.

Generic Types
    Any type may be declared to take type parameters (in a curried format). These type parameters may be used in the type definition as concrete types. An example of this is the type List T from above. The "T" is the type parameter, in this case, and List is no longer a concrete type; it is now a type constructor. When List is applied to a type argument (for example, int), it produces another type. In other words, List is a higher-kinded type, of kind * -> *. In English, List takes a type (the type argument), and returns another type (the concrete List type, with type argument set).

Type Classes
    A type class basically defines an interface that a certain kind of types must conform to; it defines what operations may be performed on a certain type kind. It really is almost like an OOP interface. They have the same concepts, and both an interface and a type class allow polyphormism.
    I'll give you an example of a type class and then explain what it means:
  class Parseable T =
    tryParse : string -> Option T
  decl parse[T] where Parseable T = string -> T
  let parse[T] input where Parseable T =
    match tryParse input
    | Some result -> result
    | None -> error "Could not parse input."
    In this example, I define a type class Parseable, which takes a single type argument, T. It says that whenever a type T is an instance of the class Parseable, the function tryParse can be given a string, and will return an Option of T. The parse function takes a single type parameter (so that it knows what type to return), and also takes a string (the input), and then calls the tryParse function, which is part of the type class Parseable. This is the part where polyphormism happens (as you will see later). If the tryParse was successful (returned Some value), parse returns that same value. Otherwise, it is an error (the parse was not successful).
    Now I will write some code that creates a class instance (of Parseable) and then uses the parse method to attempt a parse.
  instance Parseable Bool =
    tryParse input = match input
    | "true"  -> Some true
    | "false" -> Some false
    | _       -> None
  let parsedTrue = parse[Bool] "true"
  let parsedFail = parse[Bool] "not a bool..."
This code creates a class instance of Parseable, with the type argument set to Bool. The tryParse method will return an Option Bool value, telling whether or not the input could be parsed, and, if it could, then what the parsed value is. The parsedTrue value will contain the value Some(true), whereas the parsedFail value will contain the value None. The reason for the type constrain in the parse method call is so that the method knows what type to return; otherwise, it would have no idea which class instance to use. In this case, the Parseable Bool instance is used to attempt a parse.

instance End String = let description () = "
    Well, this has taken quite a while to write (over two weeks, because of homework and not working all the time on this). I'll just leave it as is now, and publish it so that you (the general you) may see it and glean all you want from it. Next time on FAIL, I'll describe a new language I'm writing!
"