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.

June 8, 2009

F#- You can overload operators, but you can’t use them.

Filed under: Uncategorized — Grauenwolf @ 10:58 pm

According to the documentation, F# supports operator overloads. This means you should be able to overload common operators like > and <.

YOU CAN OVERLOAD OPERATORS,

F# actually does does support declaring operator overloads. If you compile the code below it will emit the same IL you would expect from other .NET languages.

type OppTest4(value: int) =
   member this.value = value
   static member (^) (left : OppTest4, right : OppTest4) =
     OppTest4( Int32.Parse( left.value.ToString() ^ right.value.ToString()  ))
   static member (+) (left : OppTest4, right : OppTest4) =
     OppTest4(left.value + right.value )
   static member (>) (left : OppTest4, right : OppTest4) =
     left.value > right.value
   static member (<) (left : OppTest4, right : OppTest4) =
     left.value < right.value

BUT YOU CAN’T USE THEM!

That’s right folks. Even though F# goes out of its way to allow you to overload operators in such a way that other languages can honor them, F# itself doesn’t.

Well, that’s a bit of an exaggeration. Lets look at them each in turn:

  • + (op_Addition): Works just fine.
  • ^ (op_Concatenate): Compiler error in F#. Apparently only strings can be concatenated.
  • > (op_GreaterThan): Runtime Error – Failure during generic comparison: the type Program+OppTest4 does not implement the System.IComparable interface.

WHAT THE HELL JUST HAPPENED?

Ok, so you can’t overload op_Concatenate. Fine, I get that. It’s stupid, but whatever.

But what the hell is going on with op_GreaterThan? I can overload the operator just like op_Addition, but it doesn’t honor it. Moreover, it waits until runtime to tell me that it is going to ignore the overload and use System.IComparable instead.

Seriously, is this what they mean by a “strongly typed language”? You can’t make safe conversions like integer to decimal or string to Option<string>, but you can do something reckless like cast a class to an interface it doesn’t implement?

STATIC TYPING MY ASS

I have never seen another language screw up static typing so badly. Support for operator overloads is hard to design, I get that. But to get them so wrong that they effective break your static type checker is inexcusable.

June 4, 2009

F#: Static Typing Done Horribly Wrong

Filed under: Uncategorized — Grauenwolf @ 7:01 pm

The Some operator in F# almost shouldn’t exist. There is one and only one instance where it makes sense.

let mutable a = Some(5)

That’s it. At no other time you should ever have to use it. Consider this silly little function.

let Foo (arg1 : int option, arg2 : int option) = 
    match arg1, arg2 with
    | None, None -> 0
    | arg1, None -> arg1.Value
    | None, arg2 -> arg2.Value
    | _, _ -> arg1.Value + arg2.Value

Normally I pass values of option<int> to it, but once in awhile I would like to pass a normal int.

let b = Foo(a, 5) // Error: This expression has type  int but is here used with type  int option

So? You don’t have to understand that the set of all option<int> values contains all int values. Or in other words, it is always safe to convert a int into an option<int>. I’ll even go one step further. It is always safe to convert any T into any option<T>.

SO WHY ARE YOU WASTING MY TIME?

Ok, lets try something a little bit easier. Every language high on the chain than assembly knows about implicit numeric conversions, right? Well lets try that with F#.

let c = 10
let d = (decimal)2.5
let e = c + d //Type constraint mismatch. The type int is not compatible with type decimal

What do you mean “the type int is not compatible with the type decimal”? Every possible int can be exactly represented as a decimal, so what the heck are you complaining about?

Maybe I’m using it wrong. Maybe I should try F#’s famous automatic generalization of functions.

let SimplyAdd x y = x + y //Type constraint mismatch. The type int is not compatible with 
type decimal The type 'int' is not compatible with the type 'decimal'
let f = SimplyAdd c d //Type constraint mismatch. The type int is not compatible with type
decimal The type 'int' is not compatible with the type 'decimal'

Cool. Now I got errors on tow separate lines, and they each tell me the same thing twice.  Where else can you get four error messages for the price of one type conversion?

If the F# designers were to put in just a little bit of compiler magic so that the language would do the semantically right thing, F# would be a really pleasant language to work with.  But like the way they introduced option-style nulls without removing CLR nulls, making something technically consistent at the expense of both inconsistent syntax and inconsistent semantics is just wrong.

June 1, 2009

Should 0 equal 0.0?

Filed under: Uncategorized — Grauenwolf @ 8:05 pm

Should the integer 0 be equal to the decimal 0.0?

C# says maybe:

int a = (int)0;
decimal b = (decimal)0.0;
Console.WriteLine(a == b); //true
Console.WriteLine(b == a); //true

object boxA = (int)0;
object boxB = (decimal)0.0;
Console.WriteLine(boxA == boxB); //false
Console.WriteLine(boxB == boxA); //false

By contrast, Visual Basic says yes.

Dim a As Integer = CInt(0)
Dim b As Decimal = CDec(0.0)
Console.WriteLine(a = b) 'true
Console.WriteLine(b = a) 'true

Dim boxA As Object = CInt(0)
Dim boxB As Object = CDec(0.0)
Console.WriteLine(boxA = boxB) 'true
Console.WriteLine(boxB = boxA) 'true

UPDATE

The VB code looks like this in C#

Console.WriteLine(RuntimeHelpers.GetObjectValue(Operators.CompareObjectEqual(boxA, boxB, false)));

C# code looks like this in VB

Console.WriteLine((boxA Is boxB))
As you can see, C# assumes that you want == to mean reference equality when dealing with variables of type Object. Meanwhile, VB is using helper functions because it doesn’t automatically trust the Object.Equals(Object) method to be correct.

Blog at WordPress.com.