Spent an hour and implemented predicates. Expressions like that above now execute - it's now sufficiently complete to do useful work. Only took about 10 lines, so feeling slightly smug.
Things remaining to do include functions, some axes, variable binding, some types of expression (unions, relational expressions), and one or two other things. Not long now though :)