[Pitch] Swift Predicates

  1. Yes, you'd construct the tree using the public initializers on the various PredicateExpression types.
  2. As the tree walking section shows, this is typically done by defining a protocol, and then conforming Predicate and all the PredicateExpression types you want to handle to that protocol via extensions. If the protocol is (e.g.) ParseToResult like so:
protocol ParseToResult {
    func parse() -> Result
}

after writing extensions to conform Predicate et. al. to ParseToResult, you'd then do this:

let myResult = aPredicate.parse()

Note that the parse function could have an argument that would act as global state that could be passed down to component PredicateExpression values. While the example works if you have your own Predicate type, to do it for standard Predicate you need to cast:

extension Predicate: ParseToResult
    func parse() -> Result {
        return (expression as! ParseToResult).parse()
    }
}

If you wanted to allow for the case where you don't handle every PredicateExpression type, you could make parse() return an optional and use as? instead.

evaluate() is not involved in tree walking. You only use that if you wish to supply input to the predicate and evaluate it.

3 Likes

Thanks for the clarification @dgoldsmith (we missed parse() somehow, it was the missing piece for us - EDIT: in fact, looking at the pitch, I can't find it, perhaps it can be added to the Tree Walking section as an example? It would be clearer than spotlightQuery at least for us) - we've discussed the pitch with our team internally and overall we think it would be a great addition and definitely would make heavy use of this, looks really promising.

Our only remaining major concern (which obviously is hard to know from a pitch, but please view this as an open question) would as mentioned be performance (of evaluate() - specifically the use of keypaths, as even though SE-061 have the following note on performance:

The performance of interacting with a property/subscript via KeyPaths should be close to the cost of calling the property directly.

There are a few references so far to (quite significant) performance issues with the current keypath implementation, e.g.:

and

I understand the optimization of keypath handling is handled by a different set of priorities, I just wanted to point it out if there is anything that can be done to minimize that possible impact.

I guess it's only tangential to the pitch, but wanted to at least call it out as performance of evaluate() is critical to the usability of Predicates (at least for us) - and the pitch overall really looks great and we'd be super happy to use it (as long as performance is ok).

So, anyway - big +1 for the pitch overall.

2 Likes

Thanks for the explanation! I played around with expression macros and (although I got quite a few errors and couldn’t run anything) I understand why they’re used in the pitch. My only concern of macros in general, which does extend to this pitch, is the risk duplicating common functionality in different projects. For example, even after the advent of macros, property wrappers are still a great way of adding behavior to properties in a way most Swift programmers understand. I think this is the case with the proposal’s macros aa they are mainly used for custom operators. However, this behavior is not unique to predicates, the power assert discussed in the expression-macro threads is another great example and I imagine scoped operators being used for numerical computing too. In other words, you made a great case for why predicates would benefit from scoped operators instead of overloading, but we should generalize this feature to extend beyond Foundation. Otherwise the Swift ecosystem will become fragmented with each library author choosing their own version of scoped operators. The following is a simple, generic design we could use for this feature:

macro Predicate<R>(body: () -> R) = #scopedOperators(
  OperatorDescriptor(
    infix: “+”, 
    implementation: PredicateExpressions.Equal.init
  ),
  body
)
2 Likes

Quite an interesting idea. A similar idea, but for result builders, was recently pitched here:

Maybe a more general feature could solve both problems. I guess namespace and automatic usages of namespaces could be a nice thing but of course a lot of work to design and implement. I imagine this would also make autocomplete work more seamless.

2 Likes

I actually hadn’t considered a unified result-builder and operator namespacing feature; it’s a great idea!

The design would definitely be time consuming. For one, there’s the question of whether operators outside the namespace are just prioritized over global ones, or completely prohibited (e.g. there’s no bitshift operator in SwiftPredicates). However, the implementation, at least for the prototype in my previous post, was actually quite simple. You just parse the operators given to the macro, visit all operator nodes and substitute with the correct implementation.

2 Likes

Hi all, as mentioned in this pitch, we've posted a followup pitch regarding the serialization behavior of predicates at [Pitch] Swift Predicates: Archiving.

3 Likes

I'm glad to see this proposal went into live with Xcode 15 Beta, but I noticed that the variadic generic APIs are not implemented. In fact the variadic generic semantics are not fully described in the proposal, but it did mention an example of the macro and listed an entry in detailed designs.

So my question is: Is the variadic generic version of Predicate and #Predicate still planned? How soon can we use it on Darwin & how soon can we see it in swift-foundation?

1 Like

Yes! We still plan to adopt variadic generics / parameter packs for the new Predicate type. I don't have exact details that I can provide on when it'll appear in Darwin but I've posted a new and updated PR for swift-foundation at Variadic Generics Support for Predicate by jmschonfeld · Pull Request #178 · apple/swift-foundation · GitHub. I'm just working out a few final details before hopefully landing this.

3 Likes

Glad to see the PR being merged! @jmschonfeld

I've got another question: Why there's no Equatable and Hashable conformance to StandardPredicateExpressions? This is really useful when forming a fact list, etc.

If there's no particular reason for not adding the conformance, I wish to see it before the new OS fall releases, or else we may encounter the ABI hell.

2 Likes

Great question! I've thought about this a little bit when I was working on the initial implementation of Predicate. I chose not to add this for a few reasons. First, each conformance requirement on the expressions contained within a Predicate also translate to a conformance requirement on every value captured by a Predicate. We could require that every captured value be Hashable (in addition to the current Codable & Sendable requirement), but that's a choice we'd have to make if Predicate were also Hashable/Equatable.

However, likely more importantly, I didn't feel that the Equatable conformance for Predicate would actually be very useful in practice. Delegating down to an expression's Equatable conformance would check whether the structure of the expression is identical to that of another structure, but not truly equal. For example, consider the following two predicates:

// Predicate A
#Predicate<Bool, Bool, Bool> { ($0 && $1) && $2 }

// Predicate B
#Predicate<Bool, Bool, Bool> { $0 && ($1 && $2) }

These two predicates are semantically equivalent given they will always produce the same results and are equivalent boolean-algebra-wise. However, an Equatable conformance on the expressions would return that these are not equal because the expressions are actually entirely different types. Since Equatable doesn't afford for a way to "normalize" the expression tree before checking equality, in practice I suspect that an Equatable or Hashable conformance wouldn't produce desired results and likely wasn't worth the additional "cost" of requiring all captured values to be Hashable/Equatable as well.

5 Likes

Oh, that’s indeed a downside of it! I suspect this could break a lot of usages.

This is expected from my side. Equatable doesn’t mean to be semantically identical (i.e. behaves exactly the same) — I would like the functionality of matching, let’s say, structurally identical predicates as possible. Semantic equality doesn’t generally make sense because such associative law doesn’t apply to all operators.


Here’s a possible solution: Can we just add default Equatable and Hashable conformance, without modifying StandardPredicateExpression? Default conformance of the protocols can only be added in the same file, so it’s important to make them into Foundation.

Ah interesting. Perhaps an example might help then, are you able to describe a bit more about the use case for when you think this might be pertinent? I'm worried about providing this API in a manner that might suggest a semantic equivalence that behaves as a structural/identity equivalence. But, if there is a great use case for this that I haven't thought of yet, I'd definitely like to hear about it!

I think I have a similar thought here - at a technical level we can, however it might be good to discuss what the use case is for this. If individual expressions are Equatable and Hashable, but StandardPredicateExpression and Predicate itself are not, is that useful? I suppose you could use it if you're storing pieces of expressions separately, but I think that use case might not be very common so I'd love to hear more about it before deciding on adding this conformance. I think my main concern currently is that the potential utility of the conformance doesn't quite seem to outweigh the possibility of confusion around its use and the restrictions it imposes (in my eyes currently).

So we are looking at migrating to #Predicates from our own internal implementation - one question we have is what seems to be the lack of support for dynamically building predicates?

Very specifically, let's say if we (or the SwiftUI team!) would like to build NSPredicateEditor | Apple Developer Documentation for the new #Predicate, how would that be done?

1 Like

Presumably for anything dynamic you'd have to drop down to constructing the underlying predicate types directly instead of relying on the macro. Those appear to be nested in the PredicateExpressions namespace; I think this list would be a good start: PredicateExpression | Apple Developer Documentation

2 Likes

Yep, @allevato's point above is correct. The macro is designed around constructing a predicate based on static swift code. If you'd like to generate a predicate's contents dynamically (based on input from an editor, for example) you'll want to implement that logic to initialize the predicate expression types directly without using the macro. For this, you can directly call the Predicate initializer that takes a closure, and within that closure (which will provide you with the appropriate PredicateExpression.Variables to use for your inputs), you can dynamically return different expressions based on other input from your editor.

3 Likes

Hi!
Thank you for the reply.
We played a bit with #Predicate macro and a builder closure, but it still not clear how we could build predicate with dynamic expressions. For example we have to create a predicate for

    struct Monster {
        let level: Int
        let name: String
    }

to find all monsters with particular level and name, or level, or name, so we could use the #Predicate macro like:

    func makePredicate(level: Int?, name: String?) -> Predicate<Monster> {
        #Predicate<Monster> {
            ((level == nil) || ($0.level == level!))
            && ((name == nil) || ($0.name == name!))
        }
    }

That macro expands to

Foundation.Predicate<Monster>({
    PredicateExpressions.build_Conjunction(
        lhs: PredicateExpressions.build_Disjunction(
            lhs: PredicateExpressions.build_Equal(
                lhs: PredicateExpressions.build_Arg(level),
                rhs: PredicateExpressions.build_NilLiteral()
            ),
            rhs: PredicateExpressions.build_Equal(
                lhs: PredicateExpressions.build_KeyPath(
                    root: PredicateExpressions.build_Arg($0),
                    keyPath: \.level
                ),
                rhs: PredicateExpressions.build_ForcedUnwrap(
                    PredicateExpressions.build_Arg(level)
                )
            )
        ),
        rhs: PredicateExpressions.build_Disjunction(
            lhs: PredicateExpressions.build_Equal(
                lhs: PredicateExpressions.build_Arg(name),
                rhs: PredicateExpressions.build_NilLiteral()
            ),
            rhs: PredicateExpressions.build_Equal(
                lhs: PredicateExpressions.build_KeyPath(
                    root: PredicateExpressions.build_Arg($0),
                    keyPath: \.name
                ),
                rhs: PredicateExpressions.build_ForcedUnwrap(
                    PredicateExpressions.build_Arg(name)
                )
            )
        )
    )
    })

So we check level and name for nil each time we evaluate predicate, which is probably not good if we have millions of monsters. In that particular case for the very synthetic example we could write it like:

    func makePredicate(level: Int?, name: String?) -> Predicate<Monster> {
        if let level, let name {
            return #Predicate<Monster> {
                ($0.level == level) && ($0.name == name)
            }
        } else if let level {
            return #Predicate<Monster> {
                ($0.level == level)
            }
        } else if let name {
            return #Predicate<Monster> {
                ($0.name == name)
            }
        }
    }

But what if we have more than 2 conditions and we want to have different logical operation?
The idea was to add the code checking level and name for nil inside the predicate building closure and create different expressions. I tried many different things but not one compiled :confused:
Could you please help us and show how we can dynamically build a predicate expressions inside the predicate building closure for the example above?

1 Like

Hey @ser-0xff, thanks for the additional explanation! The last approach you have there would work as you mentioned, but as you add more properties it would become much more complex. If you need to dynamically create a predicate while analyzing what should go into the predicate, you can do so by manually constructing the expression tree. Unfortunately, since this is a more advanced use case you wouldn't be able to use the macro to help here, but you could write something along the lines of the following:

func makePredicate(level: Int?, name: String?) -> Predicate<Monster> {
    func buildConjunction(lhs: some StandardPredicateExpression<Bool>, rhs: some StandardPredicateExpression<Bool>) -> any StandardPredicateExpression<Bool> {
        PredicateExpressions.Conjunction(lhs: lhs, rhs: rhs)
    }
    
    return Predicate<Monster>({ input in
        var conditions: [any StandardPredicateExpression<Bool>] = []
        if let level {
            conditions.append(
                PredicateExpressions.Equal(
                    lhs: PredicateExpressions.KeyPath(root: input, keyPath: \Monster.level),
                    rhs: PredicateExpressions.Value(level)
                )
            )
        }
        if let name {
            conditions.append(
                PredicateExpressions.Equal(
                    lhs: PredicateExpressions.KeyPath(root: input, keyPath: \Monster.name),
                    rhs: PredicateExpressions.Value(name)
                )
            )
        }
        guard let first = conditions.first else {
            return PredicateExpressions.Value(true)
        }
        
        let closure: (any StandardPredicateExpression<Bool>, any StandardPredicateExpression<Bool>) -> any StandardPredicateExpression<Bool> = {
            buildConjunction(lhs: $0, rhs: $1)
        }
        return conditions.dropFirst().reduce(first, closure)
    })
}

In short, we create a list of the conditions that need to be met and build up the list based on which parameters are specified to the makePredicate function. We can then reduce this array into a single tree of conjunctions to ensure that all of the conditions are met. There are a few small hoops to jump through here in order to satisfy the type-checker with the use of generics such as the closure and separate buildConjunction function, but this allows you to just append to conditions for each new property rather than needing to work with a combinatorial explosion of conditions using the macro.

3 Likes

Thank you very much for the reply!
Using an intermediate generic buildConjunction() function looks like some magic, never would try that.
Not clear to me why it does not compile if I construct PredicateExpressions.Conjunction in the closure directly, while it is a generic as well...

Yes it does:

Equality implies substitutability—any two instances that compare equally can be used interchangeably in any code that depends on their values.

Also, the literal dictionary definition of 'equal' is "uniform in application or effect".

But:

To maintain substitutability, the == operator should take into account all visible aspects of an Equatable type.

Of course that hinges on what you consider "visible". It isn't as simple as technically visible - Array and Set have a capacity, for example, not just their actual contents, and that capacity does have a visible effect on their behaviour yet is not factored into their hashing or equality. It's considered not essential to their function, because it doesn't technically change the outcome of any operations, just its speed.

Now, some people might care about the speed (for good and valid reasons), but it's uncommon, so they're the ones that get lumped with extra work to account for it (if a == b && a.capacity == b.capacity etc).

I think what you're asserting is that for your purposes the structure of the predicate is what you care about, not the predicate's effect. i.e. you consider the structure meaningfully visible. Which is fine, but I think not what most people want. As @jmschonfeld suggested, I expect that most people care only whether predicate a and predicate b will produce the same result for every given input.

I know that in some domains performance is really important, e.g. relational databases where there are many ways of writing the same effective query but they can differ in performance massively. Still, I don't think domain-specific concerns should dominate the broad definition of equality, because:

  • There's no realistic way to determine abstractly whether two predicates are of universally equivalent performance (and determining that even just empirically can be non-trivial).
  • Practically-speaking if you really care about performance that much, you're most likely to address it procedurally, e.g. by running a predicate optimiser, and/or educationally, by teaching your users which forms are superior.
  • You'd likely want a way to compare predicates for behavioural equality anyway, e.g. as a validation check to ensure any transformations don't mistakenly alter the predicate's behaviour.

Now, the problem is that determining whether two predicates are behaviourally equivalent might also be hard. So that might make it impractical to provide that equality comparison at all. Even so, I think having no Equatable support is better than falling back to exact tree comparison, because it's going to be noisy with false negatives.

It does indeed seem a little unintuitive, but the behavior comes from the combination of unwrapping existentials and calling generic functions. PredicateExpressions.Conjunction is a generic type where the generic type parameters are inferred from the parameters to the initializer. This means that in order to form the return type of the initializer (i.e. PredicateExpressions.Conjunction<SomeLHSType, SomeRHSType>) the parameter types need to be statically known. However, in the closure, the parameter types are existentials, so their concrete types are not statically known. Instead we create a helper function which uses the some keyword so that the concrete types of these parameter inputs are statically known. This means that we can construct the concrete PredicateExpressions.Conjunction type with its known type parameters, and then box it in an existential and return the value. We are able to call buildConjunction from closure because the compiler understands how to implicitly unwrap existentials and call generic functions with their values thanks to the features added in SE-0352.

2 Likes