API's that Suck

June 19, 2009

On LINQ, Monads, and the Blindness of Power

Filed under: Uncategorized — Grauenwolf @ 8:04 pm

Some languages are built on one or two very powerful concepts. So powerful in fact that the most of the language in constructed in terms of these concepts.

In Haskell, monads are incredibly powerful. Everything from nullable types to collections to state management is constructed using monads. So in a way it is understandable that Haskell developers see monads everywhere and believe you can’t do any real programming without them.

Then there is Common Lisp. In CL the fundamental building block is the macro. Macros are used so extensively that they even form the foundation of CLOS, their OOP-style type system. So of course Lisp programmers have a hard time seeing how anyone can do real work in a language that doesn’t support them. (From what I hear, in Scheme closures are just as important as macros. I don’t know it they actually do it in real code, but you can build all your object fields in terms of closures.)

Finally there is “dynamic languages” such as Ruby, Python, and JavaScript. In these languages the dictionary is key. The fact that you can slot in anything function or field into any object gives these languages their flexibility. Like the other’s, dynamic programmers think it is impossible to be productive without objects based on dictionaries.

Now lets take a look at LINQ.

The Haskell guys think LINQ is monad-based and their logic is pretty easy to follow.

  1. Monads are the way you compose functions and separate them from their execution in Haskell.
  2. LINQ is about composing queries and separating the creation of queries from the execution of the queries.
  3. Therefore, LINQ must be built on top of monads.

The flaw in that reasoning is also easy to see. Consider the same argument using Lisp.

  1. Macros are the way you manipulate and rewrite expressions in Lisp.
  2. LINQ providers like LINQ to SQL are based on manipulating and rewrite expressions.
  3. Therefore, LINQ must be built on top of macros.

Or look at the same thing from the perspective of a Ruby programmer

  1. Dynamic types are what allows you to build types based on map operations in Ruby.
  2. LINQ requires building types based on map operations.
  3. Therefore LINQ is based on dynamic types.

Working backwards, we know that LINQ actually uses anonymous types to handle the result of map operations. Likewise it is pretty clear that object-based expression trees are used instead of macros for expression rewriting.

As for functional composition, LINQ also has it’s own way of doing things. Instead of using monads, LINQ uses continuations. Specifically, continuations based on operations that accepts and return an IEnumerator object. This of course leads them to think IEnumerator is a monad.

But IEnumerable doesn’t actually meet the criteria of a monad.

First of all, IEnumerable isn’t even a type construction, or what we call in .NET a generic type. IEnumerable has no idea what type it contains, nor does it care. Sure you can build an IEnumerable<T> on top of it, but that’s just there to avoid explicit casting. All the actual power is in IEnumerable itself.

Secondly, IEnumerable doesn’t necessarily have a unit function. In C# a unit function is basically a constructor that accepts a parameter of type T where T is the generic type of the class. Classes that implement IEnumerable don’t necessarily have such a function. In fact, many enumerators don’t accept any parameters at all.

Finally, it didn’t always have a true binding operation. A true binding operation has this signature:

IEnumerable<TResult> Bind<TSource, TResult> (IEnumerable<TSource> source, Func<TSource, IEnumerable<TResult>> selector)
Function Bind(Of TSource, TResult) Bind (source As IEnumerable(Of TSource), selector as Func(Of TSource, IEnumerable(Of TResult))

Classes based IEnumerator doesn’t normally compose this way. Prior to LINQ, if you want to wrap a sorting enumerator you would write something like “new SortedEnumerator(source)”.

With LINQ, we have the “SelectMany” function which has that signature. But it is only one of many function signatures needed to make LINQ work. For even basic LINQ functionality you also need Select, Where, Join, and OrderBy, none of which have a direct mapping to the monad’s binding operation.

IEnumerable and IEnumerator

Classes that implement IEnumerable do so for one reason and one reason only, to expose an IEnumerator. In these discussions about whether or not IEnumerable is a monad, that never seems to be mentioned. This is a problem because enumerators have some very important considerations.

First of all, there is the dichotomy between IEnumerable and IEnumerator. IEnumerable is usually used to decide what’s going to happen, but IEnumerator actually performs the operations. These separate concepts in .NET for a reason.

  • IEnumerator is a state machine. The very first operation that anyone does to an enumerator is call the function MoveNext. And they do so specifically for the side effects.
  • IEnumerator can’t be shared. Because enumerators have a state that must be mutated, only one logical operation can be performed on it at a time.
  • IEnumerator is fragile. Any changes to the data structure an enumerator references will break most enumerators.

Real monads don’t have any of these limitations. You won’t find a Reset or MoveNext function on a List Monad. It just wouldn’t make any sense in the mostly immutable world of Haskell.

On the Blindness of Power

Monads are powerful, there is no disputing that. But that power can blind you to the capabilities of other languages. Consider this problem.

Goal: You want to wrap a LINQ query in a future so you can process it asynchronously while doing other things.

Solution using an Async monad from Elder George:

public static class Async
{
    public static Future<T> Do<T>(Func<T> creator)
    {
        return new Future<T>(creator);
    }
    public static void Do(Action action)
    {
        new Future<object>(() => { action(); return null; });
    }

    public static Future<TR> Select<TS, TR>(this Future<TS> f, Func<TS, TR> selector)
    {
        try
        {
            return Do(() => selector(f.Value));
        }
        catch (Exception ex)
        {
            return Future<TR>.Failure(ex);
        }
    }

    public static Future<T> Where<T>(this Future<T> f, Func<T, bool> predicate)
    {
        return Async.Do(() => predicate(f.Value) ? f.Value : default(T));
    }

    public static Future<TR> Join<TS1, TS2, TR>(this Future<TS1> f1, Future<TS2> f2,
                                                Func<Future<TS1>, bool> keySel1, Func<Future<TS2>, bool> keySel2,
                                                Func<TS1, TS2, TR> selector)
    {
        return Async.Do(() => selector(f1.Value, f2.Value));
    }
    private static Future<TR> SelectMany<TS, TR>(this Future<TS> f, Func<TS, Future<TR>> selector)
    {
        try
        {
            if (f.Completed)
            {
                return selector(f.Value);
            }
            return f.Select(selector).Value;
        }
        catch (Exception ex)
        {
            return Future<TR>.Failure(ex);
        }
    }

    public static Future<TR> SelectMany<TS, TR, TI>(this Future<TS> f, Func<TS, Future<TI>> selector1, Func<TS, TI, TR> selector2)
    {
        Future<TI> intermediate = f.SelectMany(selector1);
        return intermediate.SelectMany<TI, TR>(i => new Future<TR>(selector2(f.Value, i)));
    }

}

Solution based on IEnumerable.

public static Task<IList<T>> ToFuture<T>(this IEnumerable<T> source)
{
    var result = new Task<IList<T>>(() => source.ToList());
    result.Start();
    return result;
}

Clearly the non-monadic version is far more elegant than the monadic version in C#. But I don’t want you leaving with the idea that monads are somehow inferior. My point is that what’s powerful in one language isn’t necessarily powerful in all languages. You would be in just as much trouble if you tried using C# concepts in Haskell.

About these ads

16 Comments »

  1. You might want to take a look at this video with Erik Meijer, the creator of LINQ talking about designing it specifically to circumvent the lack of type-constructor abstraction in the CLR languages.

    http://www.infoq.com/interviews/LINQ-Erik-Meijer

    IEnumerable most certainly is a monad. A bind function can be written for it, as can fmap, and those will obey the monad laws, hence it’s a monad.

    Comment by apocalisp — June 19, 2009 @ 9:41 pm

    • In .NET 1.0, IEnumerable didn’t have a binding function.
      In .NET 2.0, IEnumerable was created, also without a binding function.
      In .NET 3.5, a binding function was finally introduced.

      Is it really your argument that IEnumerable suddenly became a monad in 3.5 even though it didn’t actually change in any way?

      Or was it always a monad merely because it was possible to create a binding function?

      If the latter is true, why call it a “monad”? Clearly you can write a binding function for any generic type, which makes the term monad redundant.

      Comment by grauenwolf — June 20, 2009 @ 10:05 am

      • Hello grauenwolf. I’d like to point out your error since you are *so* close. The answer to your question is “yes it was always a monad”. However, you say “Clearly you can write a binding function for any generic type”. If this were true, then you would have a case. No wonder you have been so confused!

        This is incorrect — you cannot satisfy the monad laws for any type constructor. I’ll give you a simple one to start off with. Remember that if you can write a SelectMany/Unit then you can also write a Select. In other words, all monads are (covariant) functors. So in order to drive the point home, I’ll give you something that is not even a covariant functor, let alone a monad! You won’t even be able to write a satisfactory Select method for this type:

        using System;

        public abstract class IntContraFunctor {
        public abstract int apply(A a);

        public IntContraFunctor Select(Func f) {
        throw new Exception(“todo, but you won’t be able to”);
        }
        }

        Comment by dibblego — June 20, 2009 @ 10:20 pm

  2. The authors of LINQ have spoken at conferences about how they borrowed
    monad comprehensions from Haskell when designing LINQ….

    Comment by Don Stewart — June 19, 2009 @ 9:48 pm

    • Only for “select from” and “where”. And Haskell in turn is looking to take “order by” and “group by” from LINQ.

      http://www.infoq.com/interviews/LINQ-Erik-Meijer

      But you are missing the forest for the trees. There is a lot more you can do with IEnumerable that just monadic transformations. In the example I gave I wrapped the LINQ query in a future without using an additional monad. I could have used a monad like our Russian friend, but the code would have been far more complex and, in his own words, buggy.

      Closures, continuations, expression tree rewriting, these are all just as important to LINQ as monadic transformations.

      Comment by grauenwolf — June 20, 2009 @ 9:56 am

      • You are arguing that IEnumerable is not a monad because you can do things with it that are not part of the definition of a monad. That is like arguing that an automobile is not an automobile because it can also play audio programs.

        Comment by phoog — May 21, 2014 @ 1:30 pm

      • You’ve got it backwards. Saying IEnumerable is a monad is like saying a car is a radio.

        Comment by Grauenwolf — May 21, 2014 @ 10:12 pm

  3. Um, no. People think that LINQ has to do with monads because, you know, it sort of does. And so say the people that designed LINQ, for one…
    http://weblogs.asp.net/podwysocki/archive/2009/03/25/talking-functional-programming-with-erik-meijer.aspx

    And continuations do form a monad. In fact, they pretty much form *every* monad. http://blog.sigfpe.com/2008/12/mother-of-all-monads.html

    Comment by sclv — June 19, 2009 @ 11:09 pm

    • > Um, no. People think that LINQ has to do with monads because, you know, it sort of does. And so say the people that designed LINQ, for one…

      Yes, of course it does. That is why I explicitly said that SelectMany was the monadic binding function.

      But in LINQ you don’t always use the monadic binding function. It is just one of many transformations and compositions that are available to you.

      > And continuations do form a monad. In fact, they pretty much form *every* monad.

      Then why call it a “monad”. If all monads are based on continuations, then why not just call it a continuation?

      Comment by grauenwolf — June 20, 2009 @ 10:09 am

      • Aah, it seems you did learn something. I’m glad for you grauenwolf, even if you like to hide it :)

        However, there is much more to learn — I hope you’re not so resistant next time!

        Comment by dibblego — June 21, 2009 @ 11:30 am

      • > Then why call it a “monad”. If all monads are based on continuations, then why not just call it a continuation?

        Continuations are part of the monadic infrastructure, but that doesn’t mean that monads are continuations.

        The bind operator takes a monadic value and a continuation, unwraps the monadic value, and passes the unwrapped value to the continuation. Monadic actions are chained together in this way.

        One thing you missed when you wrote “it is understandable that Haskell developers see monads everywhere” is that monads aren’t just about Haskell. Monads are a construct which were originally adapted from category theory in order to simplify the formal semantics of programming languages.

        There are very standard ways to map the semantics of arbitrary programming languages onto a monadic representation. An environment monad (aka ReaderT) captures the notion of lexical variable binding. A state monad captures imperative mutable state. Similarly, monads can capture exception handling as well as non-determinism, both because of their intimate relationship with continuations. All these monads can be combined together, using monad transformers, to form arbitrary languages in a very composable, modular, and formally tractable way.

        As such, monads are indeed very general, and it’s easy to see them all over the place if you understand this. You can also exploit this in various ways, as LINQ apparently does.

        Comment by Anton — October 23, 2009 @ 11:13 pm

  4. Jonathan,
    There is a project dedicated to explaining monads in essay form (WIP). Part of this essay explains the relationship to LINQ. This should hopefully correct all your misunderstandings. Please ask questions if you have any. http://code.google.com/p/monad-tutorial/

    Comment by dibblego — September 11, 2009 @ 11:39 pm

  5. Hello,
    For what it’s worth, I support Jonathan. I simply don’t see a case for an argument here. It’s quite obvious that Linq, monads and IEnumerable are all related. But I can’t care less whether something is a monad or a catamorphism, and about all those quotients by kernel and universal semigroups. See, I studied categories ones upon a time. But I never did any functional programming.
    There is no doubt: If I were doing functional programming, I would certainly benefit from understanding the power of monads.
    But to efficiently utilize Linq and functional features of C#, all I need to know that the chord and the muscle of this mechanics is IEnumerable and the ability of functions to return enumerators.

    Comment by BB — November 12, 2009 @ 9:26 am

  6. Hmm, the way I think of it is that the advantage of monads is that they are actually not that powerful — in the sense of the “Principle of Least Power” (http://www.w3.org/DesignIssues/Principles.html) while LINQ is actually too powerful, making it more difficult to create a LINQ provider (as we see even in some of the ones from Microsoft, e.g. LINQ to Entities on SQL Server Compact). I need to think through this some more.

    Comment by contextfree — November 22, 2009 @ 9:19 pm

  7. “Macros are used so extensively that they even form the foundation of CLOS”

    No, they don’t. The CLOS macros (defclass, defgeneric and defmethod) are but simple wrappers of a functional protocol. The foundation of CLOS is the Meta Object Protocol, which is itself written in CLOS. If there is one defining trait of lisp, it’s this type of metacircularity. Macros are just one of many tools in the CL developers chest, but not at all the foundation, nor the end-all-be-all, of common lisp.

    Comment by drewc — June 4, 2010 @ 11:35 am


RSS feed for comments on this post. TrackBack URI

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

The WordPress Classic Theme. Create a free website or blog at WordPress.com.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: