Thursday, January 31, 2013

My Take on 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!

Tuesday, January 29, 2013

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# 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 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# 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 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.

Monday, January 28, 2013

First Post/Introduction

    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!