Using custom functions with NSExpression

There are a bunch of built-in functions in the NSExpression class that allow you to do some pretty neat stuff. They are: average:, sum:, count:, min:, max:, median:, mode:, stddev:, add:to:, from:subtract:, multiply:by:, divide:by:, modulus:by:, sqrt:, log:, ln:, raise:toPower:, exp:, ceiling:, abs:, trunc:, random, random:, now, floor:, uppercase:, lowercase:, bitwiseAnd:with:, bitwiseOr:with:, bitwiseXor:with:, leftshift:by:, rightshift:by:, onesComplement:, and noindex:. That’s a lot of functions! You have your arithmetic functions, some multi-parameter functions, some bitwise functions, and a few miscellaneous ones thrown in for good measure.

But… what if you want to find the factorial of a number? Or use any sort of trigonometric function? Or say you wanted to do something much more complex? Are you out of luck?

Fortunately, no. There is a way to do custom functions in NSExpression, with the downside that the syntax is a little bit more complex than your standard functions.

The built-in functions can be written as if they were actual functions: now(), sqrt(42), 6 * 9, etc. Unfortunately, we cannot do that with our custom functions. Oh well. Let’s get over that and move on.

The Syntax

The syntax for all functions is:

FUNCTION(operand, 'function', arguments, ...)

In a nutshell, the result of the function is the result of invoking the function method on operand, while passing in the arguments as parameters to the method.

If we dive into one of the NSExpressions produced by a standard function, we learn some interesting things. Let’s example the function “6*9”.

NSExpression * e = [(NSComparisonPredicate *)[NSPredicate predicateWithFormat:@"6*9 = 1"] leftExpression];

The -operand of this expression is another NSExpression. In the case of these built-in functions, it turns out that it’s a constant value expression encapsulating a Class object of type _NSPredicateUtilities. Some runtime introspection on this object shows that it has a whole bunch of class methods that correspond to all of the built-in functions, along with one that’s not listed in the documentation: castObject:toType:. We previously discussed using this function with advanced date predicates.

The operand is an NSExpression (as opposed to an id), because the object receiving the method could be the result of another expression.

The function in our multiplication expression is “multiply:by:”, as we would expect.

The arguments to our multiplication is an NSArray of NSExpression objects. They are expressions for the same reason that the operand is an NSExpression. In our example, we have two expressions, both representing NSNumbers as constant values.

Custom Functions

Now that we understand the syntax behind FUNCTION(), it should be fairly obvious how to go about making our own functions. Here’s what we need:

  • An object on which to operate.
  • A method to invoke
  • Parameters to pass in (optional)

So let’s say we want to add a factorial function. We have two options on how to approach this:

  1. Make our factorial method receive the number as a parameter
  2. Make our factorial method operate on a number directly

I personally prefer the latter approach, since the syntax is slightly less complicated. Here’s what we would do:

@interface NSNumber (FactorialExpression)

- (NSNumber *) factorial;

@end

@implementation NSNumber (FactorialExpression)

- (NSNumber *) factorial {
  double baseValue = [self doubleValue];
  double result = tgamma(baseValue+1);
  return [NSNumber numberWithDouble:result];
}

@end

(This method uses the Gamma Function, which allows for computing the factorial of non-integral numbers)

Then in our format string, we would express it like this:

FUNCTION(4.2, 'factorial')

If we evaluate that expression, we get 32.57809605033135, as we were hoping! The key thing here is realizing that 4.2 will be boxed in an NSNumber, which means that the factorial method will be invoked on NSNumber.

Venturing Toward the Absurd

OK, we’ve got basic functions down. What about functions that take arguments? For this next example, we’ll take a look at a custom function being used in StackKit, a framework for accessing the Stack Overflow API.

At the heart of StackKit is a URL generation system that will turn a combination of an NSPredicate, an NSSortDescriptor, and a Class into an HTTP GET request that can be used to retrieve data from one of the Stack Exchange sites (like http://stackoverflow.com). Due to the limited nature of the API, only certain predicates and sort descriptors are allowed, and only in very specific combinations.

One of the parts of “validating” an NSPredicate is to verify that it is only using allowed keyPaths, and that these keyPaths are being compared with specific operators. Each of the “RequestBuilder” classes vends an NSDictionary called the recognizedPredicateKeyPaths. This dictionary is a map of keyPaths (as the key) to an NSArray of NSNumber objects. The NSNumbers box an NSPredicateOperatorType.

Since each builder recognizes different keyPaths and different operators, I had to get a little creative. Here’s what the code looks like:

p = [NSPredicate predicateWithFormat:@"FUNCTION(%@, 'sk_matchesRecognizedKeyPathsAndOperators:', SELF.recognizedPredicateKeyPaths) == YES", predicateToValidate];
[builders filterUsingPredicate:p];

In this case, predicateToValidate is the user-supplied NSPredicate. I’m going to be passing this predicate in as the operand to my FUNCTION. The method that will be invoked on it is @selector(sk_matchesRecognizedKeyPathsAndOperators:), which is conveniently provided via an NSPredicate category. Finally, the argument to this function is the dictionary of the current request builder. If the sk_matchesRecognizedKeyPathsAndOperators: method returns YES, then we’ve passed this particular step of the validation.

The code for the NSPredicate method is fairly simple; it simply iterates through all of the keys in the NSDictionary, then extracts the subpredicates of the “predicateToValidate" for each key. Of these subpredicates, if there’s one that’s using an operator that’s not recognized, then we abort and return NO. Otherwise we’ll get to the end, find that all of our subpredicates are using allowed operators, and return YES.

The result of those two lines of code is that the builders array will be filtered to only contain the builders that allow the left keyPaths and operators that are specified in the user-provided predicate.

(For more fun, exciting, and absurd uses of NSPredicate, check out SKRequestBuilder.m.)

A Caution

One of the things to be wary of when using custom functions is that all of the parameters to the method must be objects, and the return value of the method must also be an object! This means that you cannot do:

[NSPredicate predicateWithFormat:@"FUNCTION('a', 'isEqual:', 'a') == YES"];

If you try to evaluate that predicate, it will crash. NSExpression is attempting to cast the result of the isEqual: method as an object. However, (id)1 is not an object recognizable by Objective-C, no matter how you cast it.

Instead, if you needed to do this, you’d add a method that simply boxed the result in the appropriate NSValue object and use that method:

@implementation NSString (CustomFunction)

- (NSNumber *) dd_isEqual:(id)other {
  return [NSNumber numberWithBool:[self isEqual:other]];
}

@end

...

FUNCTION('a', 'dd_isEqual:', 'a')

This will work just fine.

Wrap Up

Custom functions in NSExpression are pretty neat. You don’t find yourself using them very often, but when you need them, they can be extremely handy!

Abusing NSPredicate

NSPredicate is a nifty class. It’s intended use is to be an objected-oriented way of expressing a truth statement. We see this being used with things like -[NSArray filteredArrayUsingPredicate:], -[NSFetchRequest setPredicate:], and more. NSPredicate, however, can offer us a lot more.

There are 2 things that make NSPredicate so insanely awesome:

  1. Its string parser
  2. The evaluation power of NSExpression (one of NSPredicate's support classes)

NSPredicate Parsing

One of the best things about NSPredicate is its parsing engine. Given a well-formatted NSString, NSPredicate will turn it into a tree of NSCompoundPredicate and NSComparisonPredicate objects. This can be used to our advantage. If we have a string that represent some boolean expression, we can tap NSPredicate to parse it for us and give us back an organized syntax tree.

For this example, let’s consider the following:

(a | b) & c | (b | d)

If we just try to run this through the predicate parser, we’ll get an exception, for 2 reasons:

  1. A predicate is a truth statement. This expression is simply a value. It is not being compared to anything, and as such does not represent a true or false statement, but simply a value.
  2. Each sub-expression of a predicate must itself be a predicate. Since “c" (for example) is not being compared to anything, it is not a valid statement.

Fixing the first problem is easy. We can just tack “= 0" onto the end of the statement:

(a | b) & c | (b | d) = 0

As for fixing the second, we can do that with a little bit of find-and-replace by regular expression. For simplicity, we’ll say that each one of these identifiers (a, b, c, and d) must be alphanumeric. We can then use something like NSRegularExpression (on iOS) or RegexKit (on Mac) to replace “([a-z0-9]+)" with "\1 = 0”, thereby giving us:

(a = 0 | b = 0) & c = 0 | (b = 0 | d = 0) = 0

We can now run this through +[NSPredicate predicateWithFormat:] to get our parsed tree. From there you can recursively walk the tree and manipulate things as much as you like.

NSExpression Solving

Let’s say you have a string that contains some sort of mathematical statement. Perhaps it’s user-entered, or perhaps it’s dynamically generated. For our purposes, we’re going to use:

22/7.0 + (13*42) - 1024

Our calculator shows us that we should be getting -474.857142857142857 as the result.

But how can we evaluate this dynamically? Well, you could use something like Graham Cox’s excellent GCMathParser to parse and evaluate it, but this has a limitation: it’s a bit difficult (read: nearly impossible) to extend to use functions not supported by the parser.

Fortunately, we can abuse NSPredicate to do the work for us.

NSPredicate has a wonderful parsing engine (which we’ve already abused), and it builds a tree built out of NSExpression objects, which have this wonderful method called -expressionValueWithObject:context: which will evaluate everything for us. Unfortunately, there’s no way to build an NSExpression tree out of an arbitrary NSString. However, NSPredicate can.

So we just need to make out statement into a predicate, run it through the parser, and extract the appropriate value! This is really simple. To make something into a predicate, we simply need to add an operator and a comparison value:

22/7.0 + (13*42) - 1024 = 0

Now, we can pump it through NSPredicate:

NSPredicate * parsed = [NSPredicate predicateWithFormat:@"22/7.0 + (13*42) - 1024 = 0"];

We know that this is an NSComparisonPredicate (since it’s of the form <expression> <operator> <expression>), so we can simply extract the leftExpression:

NSExpression * left = [(NSComparisonPredicate *)parsed leftExpression];

And finally, we can now evaluate it:

NSNumber * result = [left expressionValueWithObject:nil context:nil];
NSLog(@"result: %@", result);

Wonderfully, this logs -474.8571428571429, which is exactly what we were hoping for.