# ApplesAndOranges

This page is about comparing apples and oranges, that is, combining binary predicates in a way that lets you compare things that might be only partially comparable. The most obvious application is sorting. In essence, this is about imposing a total order on an existing partial order. There is nothing earth-shattering here, but it might be of interest to some.

## `sort' and Its Predicate

The built-in EmacsLisp function `sort’ takes a list and a binary predicate as args. It compares the list elements pairwise using the predicate. Whenever the predicate returns non-‘nil’, the first of the pair sorts before the second; otherwise, the second sorts before the first.

You can of course combine simpler predicates using ‘and’ (or ‘or’), applying each in order, until one returns non-‘nil’ (for ‘and’, or ‘nil’ for ‘or’):

(defun pred (a b) (and (pred1 a b) (pred2 a b)))

But often the things we want to compare are only partly comparable, that is, comparable wrt only some of their attributes or qualities. We can compare apples and oranges based on what they have in common (sugar content, size, harvest date, etc.). In doing so, we ignore qualities they do not have in common (number of segments, size of core).

This means that a predicate that compares two pieces of fruit, each of which could be an apple or an orange, can act differently depending on which attributes the fruits have in common. We can compare the core sizes of two apples or the number of segments of two oranges, but these particular attributes must be ignored when comparing an apple and an orange.

For sorting, we can define a complex predicate to pass to ‘sort’, which, for example, sorts first by size, then by core size (if both are apples), then by harvest date:

(defun pred1 (a b)
(or (> (size a) (size b))
(if (and (apple a) (apple b))
(> (core a) (core b))
(> (date a) (date b)))))

You can see here that:

1. We test the various qualities in order, to realize the priority we want.

The latter point means that the various component comparisons are not obvious in the definition; that is, we don’t see a clear and simple combination of them to produce the overall ‘pred’. If we want to reorder the priorities, we must rewrite the function definition pretty much from scratch.

## Yes, No, Dunno (Bottom)

We would like to be able to clearly and simply combine simple predicates that might be appropriate only when certain qualities are present (because they test those qualities), easily recombining them in different orders and combinations to produce different composite predicates that we can use to sort things that might have only some things in common.

One way to do this is to let each component predicate do only what it knows how to do, and to be agnostic otherwise. IOW, let each of them return one of three possible truth values: true, false, and dunno, the last one meaning “I can’t tell; maybe someone else can decide”. Another word for “dunno” here is “maybe” – it’s a bottom truth value.

In Lisp, we can use, for example, `(t)’ for true, `(nil)’ for false, and ‘nil’ for dunno. Dunno as ‘nil’ means we can keep trying predicates until one returns non-‘nil’, that is, until one can actually decide true or false.

We can rewrite ‘pred1’ like this, to separate the component predicates a bit better:

(defun pred2 (a b)
(or (and (both-have-size a b)  (> (size a) (size b)))
(and (both-are-apples a b) (> (core a) (core b)))
(and (both-have-dates a b) (> (date a) (date b)))))

However, what happens if, say, the first component predicate here is true but the second is false? We know that both fruits have the attribute ‘size’ and that ‘a’ is larger than ‘b’. And we know that either both are not apples or the core of ‘a’ is not larger than that of ‘b’.

The latter information isn’t very helpful, because it conflates false (‘a’s core is not larger than ‘b’s) with dunno (‘a’ and ‘b’ are not comparable wrt core size – they don’t both have that attribute).

That means that this info isn’t very helpful in terms of combining predicates. The point is to be able to mix and match. If we wanted to change the sorting priorities, we would have difficulty – we would essentially need to rewrite the entire predicate.

What we need is for each component predicate to clearly distinguish true and false from dunno.

So we rewrite it to use three-valued component predicates:

(defun pred4 (a b)
(let ((decision  (or (size-cp a b) (core-cp a b) (date-cp a b))))
(if decision
(car decision)
(fallback a b))))

I use the suffix ‘-cp’ (for “component predicate”) here to indicate a three-valued predicate. Here, function ‘fallback’ could be an ordinary, two-valued predicate, returning ‘nil’ or non-‘nil’ to arbitrarily sort otherwise incomparables in some way, or it could raise an error or do something else.

Each of the component predicates does only what it knows how to do, passing the buck to someone else when it isn’t qualified to give a definitive answer. Each compares in its specific way if both objects tested allow that. If not, each privileges the presence of the attribute it tests: it sorts an object that has the attribute before one that does not.

(defun size-cp (a b)
(cond ((and (has-size a) (has-size b))
(if (> (size a) (size b)) '(t) '(nil)))
((has-size a) '(t))
((has-size b) '(nil))
(t  nil)))
(defun core-cp (a b)
(cond ((and (is-apple a) (is-apple b))
(if (> (core a) (core b)) '(t) '(nil)))
((is-apple a) '(t))
((is-apple b) '(nil))
(t  nil)))
(defun date-cp (a b)
(cond ((and (has-date a) (has-date b))
(if (> (date a) (date b)) '(t) '(nil)))
((has-date a) '(t))
((has-date b) '(nil))
(t  nil)))

Now it is trivial to define composite comparers that use any priorities we want. E.g.:

(defun pred5 (a b)
(or (core-cp a b) (size-cp a b) (date-cp a b)))
(defun pred6 (a b)
(or (core-cp a b) (date-cp a b) (size-cp a b)))

What about ‘fallback’? Typically, that would be some ordinary, two-valued (not three-valued) predicate. One way of specifying a composite predicate would thus be as a pair: a list of component (three-valued) predicates and a fallback (two-valued) predicate.

An example application of this approach is the sorting code of Bookmark+ (also Icicles). Bookmarks come in lots of flavors. In general, they are comparable in some attributes and incomparable in others. You can sort them using any number of component predicates (and you can easily define your own).

A data structure like that just described is used to specify the composite predicate to use: a list of three-valued predicates and possibly a fallback two-valued predicate. This is user option ‘bmkp-sort-comparer’. Its default value is this list:

((bmkp-info-cp bmkp-gnus-cp bmkp-w3m-cp bmkp-local-file-type-cp)
bmkp-alpha-p)

The fallback two-valued predicate ‘bmkp-alpha-p’ just compares bookmarks by their names, alphabetically. The three-valued predicates collectively compare bookmarks, in order, in this way:

1. If bookmarks ‘a’ and ‘b’ are both Info bookmarks, they are compared first by file name, then by node name, then by bookmark position in the node. If ‘a’ is an Info bookmark and ‘b’ is not, then ‘a’ sorts before ‘b’. If ‘b’ is an Info bookmark and ‘a’ is not, then ‘a’ sorts after ‘b’.

2. If neither ‘a’ nor ‘b’ is an Info bookmark, then we try to compare them as Gnus bookmarks. If they are both Gnus bookmarks, then they are compared by group name, then by article number, then by message ID. If only one is a Gnus bookmark, then that one sorts before the other.

3. If neither is a Gnus bookmark, then we try to compare them as W3M bookmarks. If both are W3M bookmarks, then a W3M-specific comparison is made. If only one is, then it sorts before the other.

And so on: each of the component predicates is tried, in order. If it can decide, it does so. If not, it gives up and the next one is tried. If none of the component predicates can decide, then the bookmarks are simply compared by name.

In essence, each component predicate is a hook function, and they are run using ‘run-hook-with-args-until-success’. If none succeeds (in deciding), then the fallback predicate is called to decide (it has no notion of maybe).

## Reusing a Component Predicate as an Ordinary One

We’ve made a case for defining three-valued predicates, to be combined at will for applications such as sorting. But what if you need an ordinary, two-valued predicate that does pretty much the same thing?

You don’t have to define a two-valued predicate from scratch, if you already have a three-valued one that will do the job. You can just convert it to a function that returns the determined truth value or a fallback truth value if indeterminate.

The following function, for example, does that for a component predicate ‘PRED’ that compares bookmarks.

(defun bmkp-make-plain-predicate (pred &optional final-pred)
"Return a plain predicate that corresponds to component-predicate PRED.
PRED and FINAL-PRED correspond to their namesakes in
`bmkp-sort-comparer' (which see).

PRED should return `(t)', `(nil)', or nil.

Optional arg FINAL-PRED is the final predicate to use if PRED cannot
decide (returns nil).  If FINAL-PRED is nil, then `bmkp-alpha-p',
the plain-predicate equivalent of `bmkp-alpha-cp' is used as the
final predicate."
`(lambda (b1 b2)
(let ((res  (funcall ',pred b1 b2)))
(if res
(car res)
(funcall ',(or final-pred 'bmkp-alpha-p) b1 b2)))))

## Discussion

Nice entry Drew . I constantly find myself reinventing the wheel with this sort of thing. That said, a case can/should be made for not building overly extensive sets of one’s own dedicated predicates in deference to the CL sequence keyword args (e.g. :test, :test-not, :key) and for using CL’s defun* with &key.

I always seem to eventually encounter situations where having built a suite of ‘utility’ functions only to I can no longer realistically recall what that suite was first intended for. This is an indication of time to reify the ‘suite’ into a wrapper function that takes keyword args:

(defun* reify-cp (a b cond-pred &key size-kcp core-kcp date-kcp)
(let* ((conds '(if cond when unless and or))
(c-prd (car (member cond-pred conds))))
(cond ((eq c-prd 'cond)       ( {...cond-logic-here...} ))
((eq c-prd 'if)         ( {...if-logic-here...} ))
((eq c-prd 'when)       ( {...when-logic-here...} ))
((eq c-prd 'unless)     ( {...unless-logic-here...} ))
((eq c-prd 'and)        ( {...and-logic-here...} ))
((eq c-prd 'or)         ( {...or-logic-here...} ))
(destructoring-macro/function-here
,@body))

This is also about the time that I give up tyring to build cathedrals and start wishing that Elisp had a more comprehensive CL foundation. These types of things are fairly routine and to the extend they are is indicative of why CLTL[2]/ANSI-CL were created in the first place. It can become tiresome living in the Bazaar where we are continually reinventing standard idioms. – mon key

Maybe I’m missing something, but I don’t see the relation to what I discuss here. How does that help with “don’t know” decisions? The point here is that a predicate can be partial, able to answer some true-or-false questions but not others, or partly able answer a complex true-or-false question, and to be able to combine such partial deciders in arbitrary ways (e.g. by changing their order). – DrewAdams

The relation is w/re the vacuous unknown. I’m simply presenting a side note/caveat w/re to building large sets of “don’t know” predicates in elisp b/c:

a) There are a lot of things we don't know we don't know;
b) It is difficult to decide when one should stop enumerating procedures to
test unknown;
c) Any reasonable well developed set of predicate helpers will eventually
become unwieldy;
d) It is difficult in Elisp to reify sub-components of a the predicate
helper superset;

To the degree that ‘a’ is a fact, what does one do when one’s existing (and inherently inexhaustible set) of unknowns does in fact eventually lead to situation ‘c’? Apropos ‘a’,‘b’, ‘c’ this is not an unreasonable question to take into consideration when examining the idiom you’re presenting. Lisp history provides indicators of what happens when large sets of predicate utilities are developed w/out robust mechanisms for encapsulation/reification. ‘d’ appears to have been taken into consideration with CLTL2 esp. w/re `&key’, ‘values’, ‘multiple-value-bind’, ‘destructuring-bind’ esp. when considered in conjunction w/ sequence predicates `:test’ `:test-not’ `:key’ etc. These features simply aren’t present in the same way for Emacs lisp.

So, the relation is this:

The very useful idioms you’ve eloquently identified and outlined are not a panacea for interrogating unknowns if/when/should one expect them to scale with emacs lisp as they too quickly become unmanageable and b/c it can be difficult/inelegant to reify these sorts of predicates into larger wrapper functions/macros/methods in the absences of ANSI-CL style features.

IME for non-trivial applications the idioms you’ve outlined fall over easily in vanilla Emacs lisp and one may be better off mastering elisp’s existing CL compatibility features instead of trying to extend elisp into a realm that it is not well capable of supporting.

When it comes to implementing applications which leverage predicate testing may be better off focusing Emacs lisp development efforts elsewhere and where predicate frobbing is concerned instead pursue a mastery of those CL predicate idioms that elisp does support. Certainly this is the case where implementation of elisps existing CL predicates afford one the opportunity to scale/port and extend code to a bona fide CL. If such is a transition that one anticipates making with ones existing/future elisp code then time/energy/effort may be better spent elsewhere instead of accumulating a too extensive set of elisp specific “user-level predicate utilities” esp. where these procedures might be far more easily/rapidly/readily embodied in a fully functional CL. --mon key

I’m glad that my writing on this topic has interested you, but AFAICT you have misunderstood what this is about.

1. It’s not about “building large sets of “don’t know” predicates” (or any kind of predicates). It’s not about “building overly extensive sets of one’s own dedicated predicates” or a “suite of ‘utility’ functions” or defining “large sets of predicate utilities”, with or without “robust mechanisms for encapsulating/reification”.

It’s not about providing a “panacea” for anything or “interrogating unknowns” or reifying predicates or “focusing Emacs lisp development efforts” in any way or accumulating “user-level predicate utilities”.

No one is suggesting to build a library of predicates. I assume as given that you have apples and oranges (and…) to sort, and that you already have (or will anyway need) predicates that compare apples to apples, oranges to oranges, etc. The point is that if those are ordinary two-valued predicates, then there is no easy, manageable way to combine them, but that three-valued predicates do the job nicely.

The reason that ordinary predicates don’t help is that their mission is to decide definitively, rather than to decide or delegate. Combining implies cooperating, which in turn implies relinquishing some control.

2. AFAIK there is nothing in Common Lisp that is particularly relevant here or that provides a ready-made way to do what I suggested or something equivalent. Certainly “CL sequence keyword args (e.g. :test, :test-not, :key)” and “CL’s defun* with &key” do not help in any direct way that I am aware of.

Perhaps you are focusing on the predicates examining particular attributes (e.g. apple core size), and that’s what made you think of :key etc? Or perhaps you are focusing on the combining of predicates by sequencing them, and you thought of CL’s ‘some’ etc. sequence functions? If so, then none of that is particularly relevant here. It is not the fact that the objects to be compared are rich, and comparison must examine their attributes, that is interesting. It is not the how of sequencing (e.g. ‘some’ vs iteration) that is interesting.

The point is instead about letting a predicate report “dunno” and by that means letting another predicate take over deciding. The idea is that this lets you shuffle and combine simple predicates, to provide a gamut of combinations that would be otherwise difficult to realize or unmanageable. This same idea is just as relevant for Common Lisp. (Is this an important idea or a new idea? Nah – please reread the 3rd sentence on the page.)

I hesitate to say again what this is about, since I don’t seem to be getting through. Let us not waste more words on it. I’m sorry my writing here was not clear enough. If you look at the actual code where this is used (bookmark+.el), perhaps you will see. See ‘bmkp-sort-comparer’ and how it is used. Thinking in terms of sorting should help. If you want to discuss issues that are specifically related to the code, fine, but I’m not interested in a wide-ranging, abstract discussion in unclear terms. If this page stimulated you to think about something else that is interesting, that’s good, whether or not I understand what that is. DrewAdams

Re: 1 There is simply no easy way to implement this idiom in Emac lisp without accumulating a suite of predicates. Each predicate begets the next.

Re: 2 Real CL’s ‘values’ (and the requisite language foundations which support it) are quite relevant vis a vis this idiom. Your missing the nuance. Obv. this is not a CL wiki but w/re this particular idiom emacs lisp is woefully shorthanded and it should bear mentioning that most of what your advocating doesn’t scale well in Emacs lisp. This isn’t to say it isn’t doable or that your examination isn’t cogent because it is.

That this idiom is relevant to CL needn’t imply that it take the same form there. It can, but typically doesn’t. Which is essentially what I’m getting at. That there is a difference (measured by degrees of elegance) in how a CL coder would approach this idiom as contrasted with an elisper (esp. in the aggregate) is indicative that elisp is short handed here. Because these are both lisps the distinction is cloudy. Consider an implementation of this idiom in ‘C’ as compared to elisp. Or in assembly as compared to ‘C’. Certainly the idiom can be translated across environments - this doesn’t mean it should be.

Consider how this idiom might be accomodated more readily with the assistance of multiple values.

Consider how multiplicative return values could be immediatlely extended with mvb/destructuring-bind.

Consider how such bound forms could be immediately interogated with CL’s sequencing predicates.

Consider that all of this could happen inside a very small set of functions/macros.

Consider that if the limtations of binary return are lifted the utility ternary-valued predicates aren’t nearly as utilitarian.

Your discussion of this idiom is clear, and it is a fascinating read because it provides an opportunity for insight into a struggle many seem to share in shoe-horning Emacs lisp functionality. To the extent that this struggle does exist it is enlightening to compare and contrast how other lisps accomodate the idiom if only as an exercise in “Comparitive Lispology”.

FWIW I did take time to review the code in bookmark+. Your macro solution w/ bmkp-sort-comparer belabors what I am pointing out here. Hint, the tip of this iceberg began with my consideration of eql vs. equal in lieu of a review of bmkp-sort-comparer; which by the way occured prior to my initial response here. --mon key

I said “I’m not interested in a wide-ranging, abstract discussion in unclear terms”. Sorry.

Suffice it to say that I disagree that anything in CL, including ‘values’, ‘multiple-value-bind’, and the higher-order sequence functions, adds anything to the party or changes anything wrt the ideas presented here.

Whether you use explicit lists or ‘values’ to return multiple values is irrelevant. One way or another, you still have to let the component predicates indicate whether they have decided definitively or not (and two-valued predicates always decide definitively). In CL, you might choose to use ‘values’ to do that (or you might choose to use a list or a structure or…). In EmacsLisp, ‘values’ is not an option, but that changes nothing essential. If all you are saying is that if one were implementing these ideas in CL then one might choose a different implementation, then sure, that’s obvious.

But show me how you would use existing two-valued predicates to accomplish this (in CL or any other language). Employ ‘values’, ‘m-v-b’, and anything else you want. Show me how to combine two-valued predicates ‘size’, ‘core’, and ‘date’ to compare apples and oranges. Show me something that moves beyond `pred1’ and `pred2’ above, so that one can easily change the order of predicate application (hence sorting) etc.

Again, if you want to present specific, alternative code snippets (e.g. CL code) to the code in bookmark+.el, we can discuss that – in specific terms. I am not interested in a hand-waving, abstract discussion.

To be clear about CL – I have nothing against it; quite the contrary. And I prefer it to Emacs Lisp in many ways. I used CL from the moment it existed (the first implementations available in Europe, in the early 80s – in particular Kyoto CL, even before it was fully baked). I like CL and appreciate many of the features it has that Emacs Lisp lacks.

The macro you refer to wrt sorting is, I assume, ‘bmkp-define-sort-command’. That is irrelevant to this discussion. It simply facilitates interactive choice of sort orders – it is purely a UI thing, unrelated to how predicates are combined or how sorting works. It takes as input a comparer (list of predicates) and simply makes that particular comparer available interactively in various ways (e.g. cycling). The code for sorting using a comparer is in ‘bmkp-multi-sort’ – it is essentially ‘run-hook-with-args-until-success’. – DrewAdams

CategoryCode