blog.lukhnos.org

"Currying" Objective-C Methods

In this blog post, I'll show you a way to "curry" Objective-C methods. I'll first talk about the problem I'm trying to solve, what currying is, and how currying can help solve the problem. Then I'll discuss how you can use blocks to achieve currying and the issue with that approach. Next, I'll present a library that can easily "curry" Objective-C methods of your choice. You have probably noticed I put the term in quotes, and I'll briefly talk about why the approach I present here is not the real currying in a strict sense. I'll also discuss some other issues in introducing the notion of currying in an imperative, object-oriented programming language like Objective-C.

Please note that the library is written for study purposes, and I didn't consider its practicality or performance. Nor is it intended for production use.

If you want to dive right into the code, here's the source, along with some sample showing you how to use it.

Introduction

Let's say we have a method in SomeClass:

    - (void)doThis:(id)a withThat:(id)b andThat:(id)c;

If we refer only to the method and want to emphasize its class membership, we can also write it as -[SomeClass doThis:withThat:andThat:], although that does not reveal the type information for the parameters and return value.

Then one day you find that, in your project, you have quite a few places that look like this:

    SomeClass *foo = [[SomeClass alloc] init];
    [foo doThis:a withThat:b andThat:c];
    [foo doThis:a withThat:b andThat:d];
    [foo doThis:a withThat:b andThat:e];
    [foo doThis:a withThat:b andThat:f];

The method takes three arguments, but we are always passing the same a and b here. Would it be nice if there's some way to remember those, so that we only need to pass the argument that actually changes, namely, c, d, e, and f, like this:

    [someMagicFoo blahAndThat:c];
    [someMagicFoo blahAndThat:d];
    [someMagicFoo blahAndThat:e];
    [someMagicFoo blahAndThat:f];

It turns out that there are quite a few possible solutions to this problem. Before I discuss them, let me first introduce a concept called currying.

Currying

Let's take the C function for example:

    int f(int x, int y)
    {
        return x + y;
    }

Then say you want to do these computations:

    int z;
    z = f(5, 10);
    z = f(5, 20);
    z = f(5, 30);

Again, we see that we're always passing 5 for x. One way to save that effort is to write another function:

    int g(int y)
    {
        return f(5, y);
    }

    int z;
    z = g(10);
    z = g(20);
    z = g(30);

In other words, we want to "fix" the first argument of f and we only want to pass the second argument to get the function value. This is called "partial application", as we only want to apply the function to a smaller set of arguments.

Wouldn't it be nice if, instead of writing g ourselves, the compiler can help us write that, using the hypothetical construction below:

    int (*g)(int) = fix(f, 5);  // hypothetical construction
    int z;
    z = g(10);
    // ...

The construction above is actually not hypothetical, although it's not available in the C language. The transformation that allows such construction is called currying.

In C, we declare the prototype of function f as int f(int, int), meaning it's a function that has two integer parameters and returns an integer value. It can also be written formally as:

    f: int × int -> int

We can also write it as:

    f: (int, int) -> int

Which reads "f is a function that maps a pair of integers to an integer". The two forms are equivalent, as n-tuples (a pair is a 2-tuple) can be used to represent set cross products.

Now let's talk about currying with a concrete example. We can "curry a function", in the sense that we pass a function to a machinery called curry, and it will give us a new function (think of it as someone who writes a new function for us).

So, if we curry f (i.e. passing f to curry), then we get a new function with the following type:

    curry f: int -> (int -> int)

That looks bizarre, so let me explain. The above line reads "curry f (the returned function of calling curry with f) is a function that, when passed an integer, returns a function that takes an integer and returns an integer".

Sounds familiar?

It should! Remember the C example we just mentioned. Let's suppose if the C language supports currying, and we can actually obtain a function from that:

    // we need this bizarre type to declare h
    typedef ...SomeBizarreType...;

    SomeBizarreType h = curry(f);

Then, if we call h(5), it will give us the function g that we want!

    int (*g)(int) = h(5);
    int z;
    z = g(10);
    z = g(20);
    z = g(30);

curry is actually a function that takes a form like this:

    curry: ((a, b) -> c) -> (a -> (b -> c))

It can be a bit cumbersome to read out the definition above. Here's a way to see this: if you call curry(f), it returns function h to you. Then if you call h(5), it returns our good friend g. Here, f is the function of type (a, b) -> c, and h is (a -> (b -> c)), and g is (b -> c). Those parentheses are added to disambiguate, but rest assured that there are many people who can do without them.

This transformation technique is named after Haskell Curry (1900-1982), a mathematician (yes, the language is named after him), who, among other things, discovered a fixed-point combinator called Y combinator (yes, that firm is named after it), a construct which can express recursive functions.

Also note that curry is not confined to functions that have two parameters (i.e. have a pair of parameters):

    curry: ((t_0_, t_1, ..., t_{n-1}) -> t_n) ->
            (t_0 -> (t_1 -> ( ... -> (t_{n-1} -> t_n))))

And there's uncurry that is the inverse of curry:

    uncurry: (t_0 -> (t_1 -> ( ... -> (t_{n-1} -> t_n)))) ->
            ((t_0_, t_1, ..., t_{n-1}) -> t_n)

Now that we know what currying is, let's see how it can help us find a solution to the problem we have in the beginning.

Using Objective-C Blocks for Currying

It turns out that there isn't really a way to write a curry function in C. The problem is that in C, functions are not first-class objects, meaning you can't manipulate functions like you do data structures. Unlike, say, in Haskell, where curry is a function you can actually use.

Then, there's a practical issue. Recall the example of f and g above. If we always want to fix the x parameter with a constant, then for each constant we need to write a new g. What if we don't want to be confined to a constant?

    int g(int y)
    {
        // a is an argument we want to fix
        return f(a, y);
    }

Now the problem is that g has to "remember" what a is. You don't want to use global variable for that:

    // suppose a is a global variable and a = 5 initially
    z = g(10);  // 15
    z = g(20);  // 20
    foo();      // a gets changed to 0
    z = g(10);  // ugh! it's 10 now

In the example above, we want to have a g that "remembers" to pass 5 for x to f. Using a global variable ruins that.

A construct to "remember" something happening in your program is called closure. A closure "remembers" the local states when it's created.

In Objective-C, blocks are closures. We can actually use blocks to write the h function (compilable code here):

    typedef int (^int_to_int_t)(int);
    typedef int_to_int_t (^int_to_int_to_int_t)(int);

    int_to_int_to_int_t h = ^(int x) {
        int_to_int_t fx = ^(int y) {
            return f(x, y);  
        };

        return fx;
    };

    int_to_int_t g = h(5);

    int z;
    z = g(10);

So, when the block fx is created, it will "remember" the x argument that's passed to h. You also noticed that we need to use some typedefs here.

I'm declaring h as a local block because I don't want to dive into the block copying issue here, which is another complex matter that requires an entire blog post. Just remember that you should return an autoreleased copy of the block if you want to pass it around (yes, I'm essentially telling you that I'm doing it wrong here for the sake of brevity).

In fact, we can go one step further, then we'll have something that's very close to the curry function, by passing the function we want to curry using a function pointer (compilable code here):

    // typedefs for int->int, int->(int->int), etc.
    typedef int (^int_to_int_t)(int);
    typedef int_to_int_t (^int_to_int_to_int_t)(int);
    typedef int (*int_x_int_to_int_t)(int, int);
    typedef int_to_int_to_int_t (^curry_t)(int_x_int_to_int_t);

    curry_t curry = ^(int_x_int_to_int_t f) {
        int_to_int_to_int_t h = ^(int x) {
            int_to_int_t g = ^(int y) {
                return f(x, y);  
            };
            return g;        
        };
        return h;
    };

    int_to_int_to_int_t h = curry(f);
    int_to_int_t g = h(5);

    int z;
    z = g(10);

That's a lot of declarations, not pretty, but it's something very close to the real thing.

What about Objective-C Methods?

Now that we know what currying is, and how Objective-C blocks can give us some kind of "curried" functions, let's see how they can help when it comes to Objective-C methods. Recall our first example:

    SomeClass *foo = [[SomeClass alloc] init];
    [foo doThis:a withThat:b andThat:c];
    [foo doThis:a withThat:b andThat:d];
    [foo doThis:a withThat:b andThat:e];
    [foo doThis:a withThat:b andThat:f];

If we want to fix foo, a, and b, we can actually write a simple block like this:

    void (^fooABAndThat)(id) = ^(id x) {
        [foo doThis:a withThat:b andThat:x];
    };

    fooABAndThat(c);
    fooABAndThat(d);
    // ...

If you want to have to flexibility to just fix a then fix b or some other arguments later, however, then you'll end up with something as messy as the previous "curry" function we have. Namely, if you want to do something like this (provided we always fix foo, to make things simpler):

    ((fooDoThis(a))(b))(c);

Then you have to write something like:

    typedef void (^id_to_void)(id);
    typedef id_to_void (^id_to_id_to_void)(id);
    typedef id_to_id_to_void (^id_to_id_to_id_to_void)(id);
    id_to_id_to_id_to_void fooDoThis = ^(id x) {
        id_to_id_to_void withThat = ^(id y) {
            id_to_void andThat = ^(id z) {
                [foo doThis:x withThat:y andThat:z];
            };
            return andThat;
        };
        return withThat;
    };

    ((fooDoThis(a))(b))(c);

Apparently, that's not very fun to write.

As I mentioned before, in C, functions are not first class objects. That you have to declare a type for everything doesn't help, either (hence the messy typedefs above). Unless we have a fancy compiler or language extension that writes those declarations implicitly and automatically for us, this seems to be as good as it can get with blocks.

But wait. Objective-C is a dynamic language. Its runtime API allows us to create classes and methods on the fly. Before the introduction of blocks, a lot of language have actually been built by making use of that property. Is there an easier way to "curry" an Objective-C method, so that we can do something like this?

    [someMagicFoo blahAndThat:c];
    [someMagicFoo blahAndThat:d];
    [someMagicFoo blahAndThat:e];
    [someMagicFoo blahAndThat:f];

With ObjCurry, we can do that.

Using Objective-C Runtime API to "Curry" Methods

ObjCurry is an Objective-C library that allows you to "curry" a wide range of Objective-C methods. Once included in a project, you can do this:

    [SomeClass curry:@selector(doThis:withThat:andThat:)];

Then, you can do things like:

    id fooDoWithA = [foo doThis:a];
    id thenB1 = [foo withThat:b1];
    id thenB2 = [foo withThat:b2];

    // equivalent to [foo doThis:a withThat:b1 andThat:c]
    [thenB1 andThat:c];

    // equivalent to [foo doThis:a withThat:b1 andThat:c]
    [thenB2 andThat:c];

    id someMagicFoo = [[foo doThis:a] withThat:b];
    [someMagicFoo blahAndThat:c];
    [someMagicFoo blahAndThat:d];
    [someMagicFoo blahAndThat:e];
    [someMagicFoo blahAndThat:f];

And, of course, we can curry methods in a Foundation class. For example:

    [[NSMutableDictionary class] curry:@selector(setObject:forKey:)];

Then, say, we have a dictionary, and we want to be able to set the same value to different keys:

    NSMutableDictionary *dict = ...;    
    id dictSetBarWithKey = [dict setObject:@"bar"];
    [dictSetBarWithKey forKey:@"a"];
    [dictSetBarWithKey forKey:@"b"];
    [dictSetBarWithKey forKey:@"c"];

    // dict is now {"a":"bar", "b":"bar", "c":"bar"}

Under the Hood

ObjCurry uses Objective-C runtime API to dynamically create new classes and methods. In the previous example, after you call:

    [SomeClass curry:@selector(doThis:withThat:andThat:)];

A new instance method doThis: will be added to SomeClass. Then, when you call:

    id fooDoWithA = [foo doThis:a];

The returned object, fooDoWithA, is actually a proxy object whose class implements withThat:. That method, in turn, will return another proxy object, whose class (currently the same as the previous proxy object's) implements andThat:. The last method in the chain, andThat:, will actually send the message doThis:withThat:andThat: to foo, along with the captured three arguments.

The implementation uses NSInvocation, which is the working horse for many Objective-C techniques often collectively called "higher-order messaging", to capture the arguments along the way. Proxy objects are also often used in tandem with NSInvocation. One of the best example is NSUndoManager, which can give you a proxy object for undoing. Any message you send (i.e. and method invocation) to that proxy object is recorded but not executed. The real invocation is deferred until the user chooses to undo, then the recorded invocation is "played back" (i.e. the real method on the target object is called).

Because methods have to be typed, ObjCurry only supports a limited number of common types, such as id, char, (un)signed short/int/long/long long, and generic pointer (void *). For return types, there is one more supported: void.

It's possible to add more types — see NSObject+Curry.m to see how to expand the type support. For example, you can add CGRect/NSRect support. The problem is that, unless deeper runtime API hack is found (perhaps some assembly required), for n argument types and m return types, we have to write nm* definitions. Even with the current macro usage it still won't scale well. If you have better solution, I'd be very happy to hear from you.

Issues and Extensions

You probably noticed that when I say we want a way to "curry" Objective-C methods, I always put the term in quotes.

The reason is that ObjCurry is not the real thing. To understand why, we have to first know how is message sending done in Objective-C.

Let's say we have an Objective-C instance method of class Foo that adds two NSNumber objects:

    - (NSNumber *)add:(NSNumber *)x to:(NSNumber *)y;

When we call:

    NSNumber *z = [foo add:x to:y];

The compiler actually turns that into a function call:

    z = objc_msgSend(foo, @selector(add:to:), x, y);

(The real code is of course optimized, but this is what the compiler would do from a high-level point of view.)

And the method -[Foo add:to:] is compiled as something like the following (again this is just a sketch). Remember that in Objective-C there is actually only one object type, hence the use of type id all over:

    id Foo_add_to(id obj, SEL selector, id x, id y)
    {
        // ...
    }

Let's ignore the selector parameter to simplify the matter. Obviously, a method is like a function, but it needs to take an object parameter so that it knows which object to act on. In other words, our Foo_add_to function actually has the type:

    Foo_add_to: id × id × id -> id

Ideally, a curry function should give us something like:

    curry Foo_add_to: id -> (id -> (id -> id))

But because ObjCurry introduces proxy objects in the picture, what we actually have is more like this:

    "curried" Foo_add_to: (id × id) -> (id × id -> id)

That's why ours is not a real thing in the strict sense.

Another issue that comes with using ObjCurry is that Objective-C compilers give you warnings on previously undeclared methods. This is a nuisance, although there is a workaround. In the main.m that demonstrates how the use ObjCurry, I put a few Objective-C categories that declares the methods as a result of currying. This silences the compiler warnings, but it can be a debugging hazard when you invoke a method that's not actually created, since the compiler now trusts you that you have an implementation somewhere, even if not statically available at compile or link time.

In addition, there's the issue of mutability. Although proxies behave like immutable objects (as each time a curried method is called, a new proxy object is created), the target object (i.e. the original object on which the original method is invoked) is not. So while the proxies create an illusion of closures, you are still dealing with an imperative language. So if you intend to try ObjCurry in a multithreaded system, you have been warned.

With the basics in place, it's possible to extend the fun. For example, each proxy object can actually remember the parameters that are ever passed to them and the returned objects. So if the parameter doesn't change, the proxy can always returned the "memorized" return value. This is known as "memoization" (some people say it's just a fancy term for "caching"). Again, in an imperative language like Objective-C, there are all kinds of issues that come with this.

The use of proxy object also brings some overhead and will have some impact on performance in places such as a tight loop. NSInvocation is slow compared to the straightforward message sending, considering the overhead in creating invocation objects and all the house keeping efforts.

Finally, because this is not a feature supported by the compiler, debugging can be tricky if something happened inside the proxy object (especially in the last step that actually invokes the original method).

Related Works

Conclusion

The idea of currying is actually very straightforward, but implementing it with a non-functional programming language incurs many issues, some of which I have discussed above. We have seen how Objective-C blocks can be used to curry functions, and I've also introduced the library ObjCurry to "curry" Objective-C methods using the Objective-C runtime API. As I said in the beginning, the project is more of a study and does not consider performance issues. Still, we have in effect created a small language extension of our own. There are still other issues with the implementation, which I've also briefly addressed. As Curry is an open source project, you can try it out yourself. And you know a way to generate automatically IMPs for non-id, non-primitive data types such as NSRect/CGRect, I'd be more happy to hear from you.