Anyone familiar with Haskell or Io will be familiar with lazy evaluation. For the rest, a summary: it’s a broadly useful technique which allows you to delay the evaluation of a bit of code until its result is actually required. In (Obj-)C terms, it’s the difference between using variables as operands to the boolean && operator and using the expressions which produce the values stored into those variables as the operands:

BOOL
    a = [self a],
    b = [self b];
return a && b;

vs.

return [self a] && [self b];

These examples are (presumably) equivalent in terms of the return value, but may not be equivalent in terms of performance or side-effects; if -b is costly to evaluate or has side-effects (mutating some state), the latter example avoids both of those since -b is never called.

In languages which don’t provide lazy evaluation of arbitrary expressions, a closure or anonymous function (a block, in Objective-C parlance) is often the preferred solution. This allows you to implement an expression which operates like the if control structure without having to have special access to the internals of the language. For example, this call is trivial to support with categories on NSObject and NSNull:

[object
    ifNull:^{ NSLog(@"object is null!"); }
    else:^{ NSLog(@"object is not null!"); }];

Since the code within these blocks is not evaluated until those blocks are called, this message is equivalent to an if statement which checks whether the object is an NSNull instance. This is, in fact, how Smalltalk phrases its control structures: identically to any other message, and taking blocks as arguments.

While defining new domain-specific control structures is a fun and profitable pastime, my interest in lazy evaluation has more to do with avoiding unnecessary computation and, potentially, analyzing and optimizing an abstract syntax tree of expressions into a simpler/faster equivalent representation.

Objective-C’s blocks are objects more or less like any other, and can be sent messages; therefore they can in theory be subjected to the full scope of engineering techniques we have at our disposal. It is, however, a little more complex than that: we can’t state that a block ^{} should be of a given class, and what’s more, we can’t tell without knowledge of the compiler what class it will be a member of. Even if we did, we won’t be able to write a category on that class, even if we were inclined to do something so untidy, since we can’t find a header which declares that class’ existence.

Fortunately, we have the modern runtime here to assist us, and its support for a technique known as isa-swizzling. isa-swizzling means changing the isa pointer on a live object, that is, the pointer to the object’s class, to instead point to some subclass of its original class. Since we’re again stuck without a way to declare a new class in source as inheriting from whichever block class our block happens to be a member of (I have seen reference to at least four, and via strategically-placed NSLogs have confirmed the existence of at least two: __NSGlobalBlock__ and __NSAutoBlock__), we also take advantage of another feature of the runtime: dynamically-created classes.

Finally we’ll need to provide some methods to our newly enhanced blocks, which we can do by copying them in from a dummy class.

We’ll use these techniques to develop a simple lazily-evaluated arithmetic library (we’ll only show addition and subtraction for brevity, but other operations are trivial to add). We begin with a protocol, TESSValue:

@protocol TESSValue

@property (nonatomic, readonly) CGFloat value;

-(id<TESSValue>)add:(id<TESSValue>)other;
-(id<TESSValue>)subtract:(id<TESSValue>)other;

@end

The -value property returns the evaluated result of the receiver. -add: and -subtract: return an object which, when evaluated, will calculate the addition or subtraction required. Note that while it would be equivalent in terms of -value for -add: to simply return a new static scalar number instance with the result of adding the receiver’s value to the operand’s, it would not be equivalent in terms of the intermediate structure: the object returned by -add: does not represent the result of adding the receiver and the operand, but rather represents the addition operation itself. Having this information available is key to performing algebraic transformations like applying the distributive property:

a(b + c) = ab + ac

Applying the runtime techniques we described above yields a function, TESSValueize, which takes a block and swizzles it to be a member of a subclass (dynamically created if it does not already exist), copying in methods from the TESSValue class which conforms to the TESSValue protocol (remember that protocols and classes have different namespaces):

id<TESSValue> TESSValueize(CGFloat(^object)()) {
    if(!class_conformsToProtocol(
        [object class],
        @protocol(TESSValue))
    ) {
        NSString *name = [NSString stringWithFormat:
            @"%@_TESSScalar",
            NSStringFromClass([object class])
        ];
        Class scalarClass = NSClassFromString(name);
        if(scalarClass == Nil) {
            scalarClass = objc_allocateClassPair(
                [object class],
                [name UTF8String],
            0);
            unsigned int methodCount = 0, i = 0;
            Method *methods = class_copyMethodList(
                [TESSValue class],
                &methodCount
            );
            for(; i < methodCount; i++) {
                class_replaceMethod(
                    scalarClass,
                    method_getName(methods[i]),
                    method_getImplementation(methods[i]),
                    method_getTypeEncoding(methods[i])
                );
            }
            free(methods);
            objc_registerClassPair(scalarClass);
        }
        object_setClass(object, scalarClass);
    }
    return object;
}

To summarize:

1. First, check if the passed-in object already implements the TESSValue protocol. If so, we’re done.
2. Next, find out if the object’s class already has a dynamically-created subclass. If so, swizzle it to that class, and we’re done.
3. Otherwise, create a new subclass of the object’s class, and copy in the methods implemented by the TESSValue class. Finally, swizzle the object to this new class, and we’re done.

(At this point I’d like to thank Kevin Ballard for pointing out that you should use object_setClass instead of setting an object’s isa pointer directly with the -> operator. While the latter functions in clang, it does not in GCC 4.2, and is exceedingly bad form.)

To bring it all together, the TESSValue class provides the methods that we will call on the block:

@implementation TESSValue

-(CGFloat)value {
    return (
        (CGFloat(^)())
        (void *)self
    )();
}


-(id<TESSValue>)add:(id<TESSValue>)other {
    return TESSValueize([^{
        return self.value + other.value;
    } copy]);
}

-(id<TESSValue>)subtract:(id<TESSValue>)other {
    return TESSValueize([^{
        return self.value - other.value;
    } copy]);
}

@end

Top to bottom, -value is implemented by simply calling the block (which returns a CGFloat), and -add: and -subtract: return a new TESSValueized block implementing the operation in question.

As yet, the protocol has no way to introspect the operation represented by any particular TESSValue-conforming instance, and as you might be aware, you can’t swizzle an instance to a class with more instance variables than the instance’s class, so adding data is tricky. Adding support for these and other interesting techniques (for example, auto-memoization on evaluation in -value) is left as an exercise to the reader, but as Steve Weller points out, associated objects can be used to provide relevant state to the block’s methods.

Lazy evaluation implemented by swizzling blocks isn’t the only possible implementation; you could do it with a class wrapping a block (at the cost of an extra allocation) or with a plethora of subclasses implementing every desired operation (at the cost of writing a plethora of subclasses implementing every desired operation). And, indeed, this arithmetical experiment is only scratching the surface of what can be accomplished with lazy evaluation; list comprehensions and Python-style generators spring readily to mind. However, I’m satisfied with my approach: it avoids an extra allocation (nothing to sneeze at if you’re looking at using this mechanism as a stage in a vector algebra implementation) and provides a pleasing balance between technical complexity and semantic simplicity; I feel that it’s the sweetest hack I’ve managed yet, and not just a hack: isa-swizzling is used by Apple to implement key-value observing in Cocoa.

In closing, there is a koan which I feel closely relates to this subject:

The venerable master Qc Na was walking with his student, Anton. Hoping to prompt the master into a discussion, Anton said “Master, I have heard that objects are a very good thing - is this true?” Qc Na looked pityingly at his student and replied, “Foolish pupil - objects are merely a poor man’s closures.”

Chastised, Anton took his leave from his master and returned to his cell, intent on studying closures. He carefully read the entire “Lambda: The Ultimate…” series of papers and its cousins, and implemented a small Scheme interpreter with a closure-based object system. He learned much, and looked forward to informing his master of his progress.

On his next walk with Qc Na, Anton attempted to impress his master by saying “Master, I have diligently studied the matter, and now understand that objects are truly a poor man’s closures.” Qc Na responded by hitting Anton with his stick, saying “When will you learn? Closures are a poor man’s object.” At that moment, Anton became enlightened.

Anton was not the only one to learn from this encounter.