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

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.

My Take on Monads

Monads

    Yes, monads. Don't go running off yet! I haven't even gotten started! Before you go, I'd at least like to give you my explanation about monads, and several uses of them. So bear with me.

Theoretical Explanation (and Option Monad)

    A Monadic Type is basically any type that has two operations that can be performed on it: bind and make. In a Haskell-like syntax, a monad would be defined as:

  class Monad m =

    make : 'a -> m 'a

    bind : m 'a -> ('a -> m 'b) -> m 'b

In this type class, the type m is the monadic type, and make and bind are the monadic operations. Notice how m must be a generic type, and is eventually constructed by both of the operations. make basically creates a "container" value from a regular old value, and bind takes a container value, removes the value, and creates another container value from that removed value. (I say "container value" to make things simpler). An example of a class instance that allows one to describe failure of computation is an Option monad:

  type Option 'T = Some('T) | None

  instance Monad Option =

    let make val = Some(val)

    let bind maybe cont = match maybe

    | Some(val) -> cont(val)

    | None      -> None

Notice how make takes any old value and returns an Option value from it; this is the "container value". bind takes a container value and a continuation function and then checks whether the container value actually has a value in it; if it does, that contained value is passed to the computation continuation; if it does not, then the entire computation simply fails by returning None.

    bind, as an Option monadic operation, acts as a success/failure mechanism; if the previous operation succeeded, then the value is passed on to the continuation, but if the operation failed (returned None), then bind returns None as well, to pass on the failure.

Example of Use

    A way to use this Option monad would be like this:

  let fail = None

  decl failIfBig : int -> Option int

  let failIfBig n = if n > 1000 then fail

                    else make n

  let sumIfBothSmall x y =

    bind (failIfBig x) (func new_x ->

      bind (failIfBig y) (func new_y ->

        make(new_x + new_y)))

This example shows a failIfBig function; it returns None, meaning failure, if the input is too large. Otherwise, it calls the make function to create a container Option value. The sumIfBothSmall function uses the monadic operation bind, which transmits any failure to the rest of the computation. Once there is failure, there will always be failure (None).

   The sumIfBothSmall function might make a little more sense when written in a different way:

  let sumIfBothSmall x y =

    failIfBig x |> bind (func new_x ->

    failIfBig y |> bind (func new_y ->

    make(new_x + new_y)))

Or how about like this:

  let sumIfBothSmall = do

  {
    let! new_x = failIfBig x

    let! new_y = failIfBig y

    return new_x + new_y
  }

The do { ... } syntax there is basically syntax sugar for the previous code. let! var = val in cont transforms into bind val (func var -> cont), and return val transforms into make val. Functional languages that use monads will usually desugar the nice-looking syntax into a series of makes, returns, and continuations.

    So when you look at the nice syntax, think about what is going on in the background, and then it will make more sense (hopefully). 

Another Monad 

    Another monad is the List monad. If you define lists as

  type List 'T = Link('T, List 'T) | End

and define several helper functions as

  decl singleton : 'T -> List 'T

  let singleton x = Link(x, End)

  decl append : List 'T -> List 'T -> List 'T

  let append list appendage = match list

  | End -> appendage

  | Link(head, tail) -> Link(head, append tail appendage)

  decl concat : List (List 'T) -> List 'T

  let concat lists = match lists

  | End -> End

  | Link(list, rest) -> append list (concat rest)

  

  decl map : ('T -> 'U) -> List 'T -> List 'U

  let map transform list = match list

  | End -> End

  | Link(head, rest) -> Link(transform head, rest)

  

... then you can define the List monad as:

  instance Monad List =

    let make x = singleton x

    decl bind : List 'a -> ('a -> List 'b) -> List 'b

    let bind list projection = list |> map projection |> concat

  let none = End
To make things easier, let us assume that there is a list syntax:
  [a, b, c] -->> Link(a, Link(b, Link(c, End)))

The List monad basically allows you to use functions that return lists, and then pass each return value to another function, and then flatten the resulting list, and then pass each of those values to another function and on it goes. It makes it easier to deal with functions that can return multiple results, in list form. An example of this monad's use is:
  let product listX listY = do
  {
    let! x = listX
    let! y = listY
    return (x, y)
  }
  let list1 = ["a", "b", "c"]
  let list2 = ["x", "y", "z"]
  let listProduct = product list1 list2
  # listProduct = ["ax", "ay", "az", "bx", "by", ...]

And Another Monad... 

    Another example is the Log monad. It can be used to keep track of debugging information, for example, or maintain a log string, threaded through a computation. Let's define a Log as:

  type Log 'T = ('T, string) 

Then define the makeLog function as

  decl makeLog : 'T -> string -> ('T, string)

  let makeLog value info = (value, info) 

And define pipeLog

  decl passLog : Log 'T -> ('T -> Log 'U) -> Log 'U

  let passLog (prev_val, prev_info) compute_log =

    match (compute_log prev_val)

    | (next_val, next_info) -> makeLog next_val (prev_info + next_info) 

And then define the Monad instance as

  instance Monad Log =

    let make (value, info) = makeLog value info

    let bind prev_log cont = passLog prev_log cont   

 This Log monad allows you to keep track of a string description of computation. When you bind one log into a computation, the passLog function keeps track of the previous information, and then appends it to the next information, to create a full log.

And Yet Another Monad... 

    This time, it's the point-free monad. Basically, it allows you to define point-free functions (without reference to formal parameters).

   Let's define the point-free monad as:

  type Function 'I 'O = 'I -> 'O

  let const x = func _ -> x

  instance Monad (Function 'I) =

    let make fn = const fn

    let bind prev_func cont_func = func arg -> arg |> cont_func (prev_func arg)

We can then use it in this example:

  let xTimes2PlusXOver3 = do

  {

    let! times2 = func x -> x * 2

    let! over3  = func x -> x / 3

    return times2 + over3

  }

That example basically uses the point-free monad to multiple a number by 2, and then add to that the number over 3.

  xTimes2PlusXOver3 15 # (15*2) + (15/3) = 30 + 5 = 35

Closing Words (No More Monads For You)

    I hope I explained monads well enough. I showed you the theoretical definition of a monad, desribed the Maybe/Option/Success monad, gave you an example, and then also gave you two other monads to think about. So now, I think I've written enough (so I'll stop writing soon). Next time on FAIL, I will be writing about inline blocks versus methods in Ruby (either that, or about the hypothetical functional language used in this post). See you there!

Thoughts on Some Languages

    For my first real post, I'm going to describe what I like/dislike about several different languages I've used (at least a little). I feel that it's a good way to introduce myself, in a way, to show all you readers what I think about different languages/paradigms. At the end, as as special treat, I'm going to give you some example languages that I'm thinking of creating! So, onto the languages:

C#
    C# is a modern .NET class-based language. It has nice features such as reified generics, operator overloading, automatic conversions, lambdas, and a limited form of type inference. C# is my favorite language because it's what I've used the longest; it feels "clean" to me, much more so than any other language I've used, and I love it because its features work very well together.
    The reified generics mean, basically, that there is no type erasure, and that you can figure out what the actual type argument is at runtime. I'll go more into this later, but Java's type erasure is very annoying at times, because you cannot even make a generic array!
    C#'s operator overloading is a very important feature when one is using user-made structures that can have mathematical operations performed on them. For example, would you rather see vector1.add(vector2.mul(vector3)) or vector1 + vector2 * vector3? I, personally would rather see the second version, with the basic math operations we all know and love.
    Oh, but, but, you can make the + operator do anything you want to! And that's dangerous! Don't give users so much power! Response: what's the difference between making the + operator do something wierd, and making an add(int, int) function do something wierd? It's just naming! Anyway, there are also conversions in C#, which can make some code clearer/cleaner, because you do not need written-out casts for very similar objects. 
    Lambdas are one of the best features; they are useful for so many things, including, but not limited to, callbacks and user-supplied functionality (no need for single-method interfaces!). I'm too lazy to think of more examples right now...
    C# has a limited form of local type inference; you can say var dict = new Dictionary<string, int>(); instead of Dictionary<string, int> dict = new Dictionary<string, int>();
    And, last but not least, C# also has Visual Studio! Some of you may be saying, "but I don't like Visual Studio!" But I do, and since this is my blog (thus my opinion), I'm going to shamelessly say that VS is a bonus point for C#. Now, enough about C#, on to Java!

Java
    Java is, unfortunately, my least favorite language. However, I've got an explanation, so don't start the flames yet, Java-lovers! First, I don't particularly like the Java standard libraries. I haven't used them as much as the .NET libraries, but to me, at least, .NET feels more orderly. As an example of the difference, using .NET+C# you can write string[] lines = System.IO.File.ReadAllLines("C:\Users\...\...\text-file.txt");, whereas in Java, I'm still not sure how to do it, and I've already browsed the internet and StackOverflow to try to get the answer. Perhaps .NET simply has more convenience methods? I don't know.
    Another thing I don't like about Java is the lack of operator overloading (see C# above) and lambdas (again, see C#). Java also uses type erasure, so you cannot even make a generic "transform array" function! In C#, I would write this function as:
  U[] transform<T, U>(T[] array, Func<T, U> convert)
  {
      U[] result = new U[array.Length];
      for (int i = 0; i < array.Length; i++)
          result[i] = convert(array[i]);
      return result;
  }
In Java, you would get an error on the first line of that function; something along the lines of "cannot create generic array".
   Last, but not least, the Java mindset is to create getters and setters for everything, so that you "future-proof" your classes. The idea is that getters and setters allow you to later change the code of these functions, without modifying client code. By simply exposing a field, when (if ever) you want to add verification/other changes to the field, you must at that time add the methods, thus breaking client code. C#, however, follows the Uniform Access Principle, at least in regards to properties and fields.

F#
    F# is undoubtedly my favorite functional language. First, it is built on the .NET framework, which means libraries and idioms that I'm used to. Second, it has full Hindley-Milner type inference, which means that you, in some cases, don't have to provide even a single type declaration; the compiler will figure it out for you. F# also allows arbitrary operators to be defined, with prefix-based operator precedence, so it allows you to stay on the well-beaten path of operator overloading, but you are not stuck with the default operators that the language designer built in.
    F# is an impure functional language, which, I think, is the best of both worlds: functional and imperative. Granted, F# does sometimes make it harder to use imperative styles, but that's because it's a functional language!
    One thing I really loved about F# was the workflow idea. F# workflows are basically Haskell monads, but the description of workflows in the book Expert F# explained the idea much better than anything on the internet taught me about monads.
    One last thing (that I will write about) that I love about F# is the pattern matching. It allows for very concise value destructuring and is very clear to the code reader about what is going on.

Ruby
    Ruby is an extremely dynamic, completely object-oriented language with a beautiful syntax. It follows the idea of "everything is an object" as much as it can; all values are objects, including primitive values such as integers and floating-point numbers. The lack of static safety (including type-safety) brings ease of use, but also causes me to fear silly mistakes, like typing array.lengt instead of array.length. In most languages, an error such as this would be caught at compile time, but in Ruby, there is no compile time. So do most people get their fears assauged through unit tests? I've never used one, believe it or not (but I've also not used Ruby very much at all...)

Last, But Not Least: Tcl
    TCL stands for Tool Command Language. It is a word-based language; every command is of the form word arg1 arg2 arg3 ... Every word is a string, and every command can interpret their string arguments in different ways. In one command, a string might be interpreted as a number; in another, a list. I think Tcl is a cool language, but the idea of "everything is a string" is, I think, wrong (to put in plainly). Not everything is a string; for example, C#'s Object.

(Almost) The End of the Journey
    ... in regards to languages I've used/learned. I like something about all of these languages (except Java -- I'm sorry, Javalovers!), and I hope I've explained why I like certain features. Now I would like to show you some languages that I've thought about.

A Functional Language
    This functional language is kinda-sorta minimal. I suppose it would (initially) have a type system that supports only variants (sum types), tuples (product types) and functions. It would have a fully generic type system, and some form of type inference. It would also have type classes and type class instances, Haskell-style. I think an example is in order:
  type Int = Zero | Succ Int
  let add Zero b = b
  let add Succ(a) b = Succ(add a b)
  class Addable T =
    (+) : T -> T -> T
    dec : T -> T
    zero? : T -> Bool # Bool defined as: type Bool = True | False
  instance Addable Int =
    (+) a b = add a b
    dec Succ(n) = n
    dec Zero = Zero
    zero? Zero = True
    zero? _    = False
  decl mul : 'a -> 'a -> 'a where Addable 'a
  let mul a b when zero? a = b
  let mul a b = b + (mul (dec a) b)
This example shows a definition of the Peano integers, an addition function, an Addable class, a class instance, and a function that requires a type classification.

A Word-Based Language
    This word-based language would be like Tcl, except that not everything is a string; in other words, it would be like typed Tcl. An example:
  proc fact n {if [= $n 0] 1 {* $n [fact [- $n 1]]}}
  set n [to-int [ask 'Enter an integer: ']]
  puts [fact $n]
The variable n would be typed as an integer, not as a string. Unlike Tcl, curly brackets { } would signify a code block, instead of an unparsed string. Or something like that. As an aside, I think that a word-based language would be a good OS shell language, because such languages often make it easy to use plaintext in the code (as in [ask Integer:]), and have a simple, command-based syntax. In this model, if a command could not be found, then an executable with the command's name would be searched up and then executed with the arguments.

Actually The End
    Wow, that was a long post. Probably the longest one you'll ever see from me. Unless I feel like writing more... eh. Maybe. I've gotta work on my calc homework now!

I Lied In The Previous Heading
    ... because I have one more thing to say, before I go: next time is monads! I'll try to describe how I think about them, and hopefully have a better (or at least different) description than the many guides there already are.

First Post/Introduction

Welcome!
    I'm Grant Posner, and this is my first blog post! So exciting! This will be a short post, because, well, I don't really have anything to say yet. So I'll just say what this blog is about:

Fun Adventures in Languages (FAIL)
This blog will be about my thoughts on different languages, ideas, frameworks, code, etc.; basically, anything to do with programming languages. Because that's what I love. Whenever I make a programming language, I will try to blog about it, describing my thought process, ideas I have, considerations I've made, and much more, so that I can show others how fun it is to think about languages.

Have Fun!
... and enjoy the posts!