Search code examples
design-patternsexpression-trees

Boolean expression tree with predicates?

I am trying to design an expression tree builder that can be used to build an expression tree that can be evaluated lazily with provided context (hash map). Required set of operators is AND/OR/NOT, <,<=,>,>=,=,!=, in_range(inclusive or not). Expression tree must support a short circuiting (not computing more than needed for the final result). Evaluation result is either true or false. Which nodes in my case must be intermediate and which are the leafs? I suppose AND/OR/NOT are intermediate ones and predicates (<,<=,>,>=,=,!=, in_range) will be leaf nodes? Or each predicate will be represented as a subtree?

Solution

  • I recently did this for my employer. I haven't talked to them about open-sourcing it yet, though, so I can't show you any code. I can give you some advice, though.

    • If you have magnitude comparisons, then some subexpressions must not have Boolean results: If you write a <= b, then a and b are numbers or strings. You will probably also want math so you can write a <= b+1, etc. My solution was that:
      • only the atoms are leaves (a, b, 1, etc.)
      • parsing an expression or subexpression produces a typed compiled expression object. It is either known to produce a Boolean, string, or numeric result, or it may produce anything. a < b, for example, is known to produce a Boolean result.
      • An expression that is used as a predicate is invalid unless it is known to produce a Boolean result.
    • Since you will be taking arbitrary hashmaps as input, you need to think about how to handle nulls. I suggest you do it the way SQL does it (the hard thinking has already been done), and add IS NULL and IS NOT NULL to your language.