some-fn and
every-pred started life as single-line combinators
proposed by Fogus,
Christophe Grand and others:
(defn every-pred [& preds]
(fn [& args] (every? #(every? % args) preds)))
(defn some-fn [& preds]
(fn [& args] (some #(some % args) preds)))
Rich Hickey accepted them into Clojure with an important condition: they must be “unrolled”. This increases the performance for small numbers of arguments.
It turns out this is very hard. Here’s what those
unrollings look like—very long, nested, and hard to reason about.
To even write them, you need to run a nested loop in your head for all combinations of small numbers of preds and args.
On March 20th, 2011, they were merged
in time for Clojure 1.3, and remain two of the most stylish functions in Clojure.
Is there a correspondence between the one-line versions of some-fn and every-pred and the
30x longer unrollings that landed in Clojure?
The answer is no, but for a trivial reason.
Neither unrolling supports zero arguments: (some-fn) or (every-pred).
This is a subset of the original behavior, so let’s refine the correspondence:
(defn every-pred [p & preds]
(fn [& args] (every? #(every? % args) (cons p preds))))
(defn some-fn [p & preds]
(fn [& args] (some #(some % args) (cons p preds))))
Is there a correspondence now? Well, not if you count CLJ-2649, a bug in both implementations, fixed ten years later. Check out the commit resolving the issue—it’s amazing this was found at all. Clearly, we need more human compilers in the Clojure community.
As of 2022 (Clojure 1.11) that leaves us in a great spot for one of our candidates.
The current implementation of every-pred is operationally equivalent to its revised one-liner!
Update 2022-09-12: This claim is actually false.
some-fn is not so lucky. With 3 predicates or less, the return value can be inconsistent
with different numbers of arguments.
The proposal to fix this was rejected,
so we’re left without a neat end to this story.
However, if you’re a fan of the original functions at the top of this post, I have good news.
I have released two new functions somef
and everyp
that are operationally equivalent to the original one-liners.
Somepff and evreep would make good Pokémon names and are fun to say, but if you don’t buy that
or are just nostalgic,
see
some-fn
and
every-pred
for the original names mapped to their simplest operational equivalences.
I’ll leave you with these questions that kept me awake for years:
- How would you verify that each unrolled implementation is operationally equivalent to its original specification?
- How might we have prevented CLJ-2649, where the predicates were inadvertently tested in the wrong order?
- How can we verify that each function’s short-circuiting behavior is correct?
- Can we generalize solutions to the above so they are as easy to use as clojure.spec’s automatic generative testing features, where we specify these properties in the form of function specs?
- Update (via Ben Sless): How can we automatically unroll a function via a macro? (asked by Rich Hickey in 2011).