Saturday, February 16, 2013

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!
"

Sunday, February 3, 2013

The Magic is Gone

    Last time, I mentioned that I would be writing about Ruby or about a hypothetical new language. Well, I'll do that next time, because I thought of a more interesting (to me, at least) thing to write about right now.

    Have you ever felt that you aren't as excited about an activity as you used to be? Does it ever feel like the wonder and the magic are missing? That there is just something absent?
    Over the past year or so, programming has started to lose its magic. When I started programming, everything was a new experience. I would learn a new language, and then feel like suddenly the entire computer was at my fingertips. I would feel powerful, amazing, and smart, because I knew more about programming.
    I remember, when I started learning C#, I saw the "namespace" keyword and thought "that looks so cool! It's so exciting to be able to learn what it is! I wonder if it's something to do with objects, or files, or classes, or something else." I would happily learn about anything there was to learn, because it those early stages (and still now, though not quite as much), all I wanted to do was learn. Learn how to do more things and become more proficient at programming, and read a lot of material.
    But now, when I see a new language feature, it doesn't make me excited. Now I think about it in a distant manner. I think of new ideas, now, as simply another thing to use. The magic of learning new things is now gone.
    I've been thinking about this a lot, and I'm trying to figure out why I feel this way. I think I understand now, so I'll try to write my explanation as best I can:
    During the first couple of years of programming, everything was new, exciting, and novel. Because I saw how cool languages were, I decided to learn about how they worked. Because I didn't now how operating systems worked, I decided to try to implement one. Because I didn't now how x, or y, or z worked, I tried to create it.
    The problem is, now I know how languages, and operating systems, and x, and y, and z, and more, work. It no longer holds any wonder for me.
    I've created my own emulated assembly language, and wrote an interpreter for it (although it was buggy, and never quite worked). I started a project to write a mini operating system for my hypothetical assembly language. I never finished it, but after writing parts of the OS, and after reading the Minix Book of Operating Systems, it is no longer magical. I can no longer think of the computer as this fuzzy idea, just something that allows me to type in some text, and then make it run. Now I understand what an operating system does, how it works (in excruciating detail, for many parts), and now it is not magical.
    I've created my own programming language, named Prototype. I built my own lexer, parser, bytecode compiler, and bytecode interpreter for it. Now I know how all of these work, and what they do, to create a working language implementation. I no longer see C# as a magical thing, that somehow knows what I mean when I write some text on my computer screen, and then does what I say. Amazing! But now I know.
    Now I know how all of these work. They are no longer magical; I cannot any more think about them as black boxes, taking in some input and emitting some output. I know how they work, how they are implemented, the mechanisms at work, and the magic is gone.
    Once upon a time, everything was new and exciting. I couldn't wait to understand how something worked. Now I can no longer wonder, because I know how they work, and I almost wish I could go back to that time, when everything was still wonderful. But I can't.
    The magic is gone.