Hi, I'm Aditya Athalye. I make, learn, teach here.

Someone working through the "Brave Clojure" book asked #beginners in the Clojurians Zulip chat, for help about implementing comp "in their own words". Useful help followed in the Zulip thread, of course. I was late to the party. Of course. But when has that ever stopped anyone on the Internet from generating a wall of text?

Having done so, I realised a bunch of ideas have to coalesce in the Clojure learner's mind to truly See the picture, and I certainly did not See it for a long time:

• Functions are first-class values at run-time, just like "normal" constants.
  • So we can pass them around, and in Clojure, we can also put functions inside normal Clojure data structures (maps, lists, vectors, sets etc.).
• Pure functions, and the substitution principle of reducing functional expressions down to the smallest form.
• Recursive thinking / inductive reasoning (same thing)
  • Constructing base ("empty") case, unit case, two case, three-case, and using that to generalise to the n-case (of n arguments to a function).
• Familiarity with writing functions having variable arguments
• Familiarity with the stdlib (reduce and reductions, for example).
• How to use "code as data", for self-education, if nothing else.

So… comp…

The REPL says…

user=> (clojure.repl/doc comp)
-------------------------
clojure.core/comp
([] [f] [f g] [f g & fs])
Takes a set of functions and returns a fn that is the composition
of those fns.  The returned fn takes a variable number of args,
applies the rightmost of fns to the args, the next
fn (right-to-left) to the result, etc.

This means:

• comp's type signature is List[Function] -> Function.
• It accepts functions as arguments, ergo functions must be "normal" values.
• It must always return a function.
• By definition, the returned function must be of exactly one argument.

We consult Clojure Docs for examples illustrating what comp does.

(filter (comp not zero?)
        [0 1 0 2 0 3 0 4])
;;=> (1 2 3 4)


(def negative-quotient
  (comp - /))

(negative-quotient 8 3)
;;=> -8/3


(def concat-and-reverse
  (comp (partial apply str)
        reverse
        str))

(concat-and-reverse "hello" "clojuredocs")
;;=> "scoderujolcolleh"


;; etc...

Now, to rewrite it in one's on words.

What might comp be doing?

comp's argument list indicates it must handle several "arities" of arguments:

• zero argument case: comp of nothing should "do nothing". But comp must return a function. So what is the function of one argument that does "nothing"? identity, as you identified it.
• unit argument case: comp of f must return a function that "does f" to a single argument. Thus the return value must be (fn [x] (f x)).
• two argument case: comp of f and g must return a function that first "does g to a single argument", then "does f" to the return value of (g x). This is (fn [x] (f (g x))).
• three case: comp of f, g, h must return (fn [x] (f (g (h x)))). BUT this reduces to the two-case… (fn [x] (f (g x'))), where (h x) returns some new value x' (pronounced "x prime").
• n case: and so on… the 'n' case will follow the same (inductive) reasoning and collapse down to the two-case.

So, we essentially need to handle zero, one, and two argument cases, and figure out how to use that solution to handle the fully general n argument case.

And with this thought, if we know reduce, we can draw the rest of the Owl…

(defn my-comp
  [& funcs]
  (reduce (fn [f g]
            (fn [x]
              (f (g x))))
          identity
          funcs))

user=> ((my-comp reverse str inc) 41)
(\2 \4)
user=> ((my-comp str inc) 41)
"42"
user=> ((my-comp inc) 41)
42
user=> ((my-comp) 41)
41

If this looks freaky, fear not… It took me a long time to figure out how to think like that "natually". And it still freaks me out that this kind of thing "just works". Give it time, it will come to you.

In general, the technique used above is called the "substitution principle"… how we turned the three-case into the two-case.

We can do it because there is no difference between a pure function f called on some x, and the return value arrived at… i.e. If (f x) returns x', then you could just as well say x', and the consumer of the return value can be none the wiser.

Incidentally, constant folding in compilers is the same thing. If the compiler has all the information about what is calling what, then it can just say…

"Weeeeell… Obviously the program does not need to keep doing the work again and again because it will always end up at the same value. So, here you go, the final return value as it is supposed to be, hard-coded into the compiled binary…"

So I guess I'm saying that understanding comp, can help understand compiler. I'll show myself out… (:

But that was typed well past midnight.

This morning my brain realised that it's possible to directly show how the reduction process itself unfolds…

First, let's rewrite the reduce body so that it only generates the fully-formed expression without evaluating anything. This is one of the little joys of being able to write our programs in terms of the data structures of the language ("homoiconicity").

(defn my-comp-no-eval
  [& funcs]
  (reduce (fn [f g]
            `(fn [x]
               (~f (~g x))))
          identity
              funcs))

user=> (my-comp-no-eval reverse str inc)
(clojure.core/fn [user/x]
  ((clojure.core/fn [user/x]
     ((clojure.core/fn [user/x]
        (#object[clojure.core$identity 0x42c2f48c "clojure.core$identity@42c2f48c"]
         (#object[clojure.core$reverse 0x41aaedaa "clojure.core$reverse@41aaedaa"] user/x)))
      (#object[clojure.core$str 0x303a5119 "clojure.core$str@303a5119"] user/x)))
   (#object[clojure.core$inc 0x75b3673 "clojure.core$inc@75b3673"] user/x)))

We can do one better, and directly visualise every step of the reduction process, using reductions instead of reduce.

Read this doozy "bottom to top".

(defn my-comp-no-eval-show-steps
  [& funcs]
  (reductions (fn [f g]
                `(fn [x]
                   (~f (~g x))))
              identity
              funcs))

user=> (my-comp-no-eval-show-steps reverse str inc)

;; FINAL REDUCTION...
;; Retuns identity of whatever value is computed.
(#object[clojure.core$identity 0x42c2f48c "clojure.core$identity@42c2f48c"]

 ;; BEFORE THAT:
 ;; The 'two arguments case' is reduced to the 'one argument case'.
 (clojure.core/fn [user/x]
   (#object[clojure.core$identity 0x42c2f48c "clojure.core$identity@42c2f48c"]
    (#object[clojure.core$reverse 0x41aaedaa "clojure.core$reverse@41aaedaa"] user/x)))

 ;; BEFORE THAT:
 ;; The 'three arguments case' is reduced to the 'two argument case'
 (clojure.core/fn [user/x]
   ((clojure.core/fn [user/x]
      (#object[clojure.core$identity 0x42c2f48c "clojure.core$identity@42c2f48c"]
       (#object[clojure.core$reverse 0x41aaedaa "clojure.core$reverse@41aaedaa"] user/x)))
    (#object[clojure.core$str 0x303a5119 "clojure.core$str@303a5119"] user/x)))

 ;; THE VERY BEGINNING:
 ;; Starting form of the computation, before the reduction process kicks off.
 (clojure.core/fn [user/x]
   ((clojure.core/fn [user/x]
      ((clojure.core/fn [user/x]
         (#object[clojure.core$identity 0x42c2f48c "clojure.core$identity@42c2f48c"]
          (#object[clojure.core$reverse 0x41aaedaa "clojure.core$reverse@41aaedaa"] user/x)))
       (#object[clojure.core$str 0x303a5119 "clojure.core$str@303a5119"] user/x)))
    (#object[clojure.core$inc 0x75b3673 "clojure.core$inc@75b3673"] user/x))))

That's it for now.

If you like this, you may like to learn of the n ways to fizzbuzz in Clojure.