Alan Dipert tweeted an interesting puzzle:

pop quiz: solve http://www.4clojure.com/problem/107 point-free. answer must be a function value! #clojure

The 4clojure version of the problem is simple enough, but the added requirement of a point-free solution makes Alan’s version of the problem harder. And harder to resist. So I took a shot at it.

My plan was simple: solve the problem in the natural way, and then transform the solution into the point-free style. Piece of cake. Not.

Here’s my starting place:

` (fn [x] (fn [y] (reduce * (repeat x y))))`

That solves the 4clojure version of the problem, but I need to get rid of the arguments **x** and **y**, and the lambdas. To make a long story short, I couldn’t do it. The best I could manage was this:

#(comp (partial reduce *) (partial repeat %))

I managed to rid of one lambda and one variable, but could not get rid of the remaining argument, now slightly disguised as **%**, and the remaining lambda, disguised as **#()**.

I wanted to know the answer, so I asked Alan, who directed me to a tweet by Baishampayan Ghose. Now the story starts to get interesting. This was @ghoseb’s answer:

(partial partial (comp (partial reduce *) repeat))

Yow! I would not want to run into that in the wild. No matter how hard I stared at that code, I could not get a clear understanding of how it works. But there are methods other than staring, say abstraction and equational reasoning. Let’s use them to analyze @ghoseb’s code.

I mentioned equational reasoning, so let’s introduce a couple of equations that describe the action of the functions **partial** and **comp**.

**P**: ((partial f g) x) == (f g x)**C**: ((comp f g) x) == (f (g x))

I have labelled the equations **P** and **C**, so that I can refer to them later. The equations combine infix and prefix notation. Don’t let that bother you; it’s ok to be less than rigorous in meta-language. Mathematicians do it all the time. The symbols **f**, **g**, and **x** are just variables.

Each equation states that two expressions are equivalent. Here are concrete examples of **P** and **C**, written in executable Clojure.

```
(= ((partial * 2 3) 4) ;; illustrates P
(* 2 3 4))
(= ((comp #(* % % ) inc) 1) ;; illustrates C
(#(* % %) (inc 1)) )
```

Now let’s put **P** and **C** to work on @ghoseb’s code. We’ll start by writing out what we know from the problem. We know, and can test by execution, that the following expression evaluates to 256.

(((partial partial (comp (partial reduce *) repeat)) 2) 16)

I mentioned that we would use abstraction; by abstraction I mean giving things names. There is one chunk of code in there, enclosed in the innermost parens, that is easy to understand. Let’s give it a name.

(def mult (partial reduce *))

The **mult** function applied to a finite sequence of numbers returns their product:

```
user> (mult [1 2 3 4])
24
```

We can rewrite our expression using mult and get a slightly simpler expression that still evaluates to 256.

` (((partial partial (comp mult repeat)) 2) 16)`

Next we’ll simplify a sub-expression. **P** allows us to infer that

;; ((partial partial (comp mult repeat)) 2) == (partial (comp mult repeat) 2)

Protip: forget the semantics for a moment, and just look at the syntax. **P** allows us to drop one set of parens, and one instance of **partial**.

Now we go back to our expression that evaluates to 256, and substitute the simplified subexpression.

` ((partial (comp mult repeat) 2) 16)`

The **P** rule has been working for us, let’s use it again. Think symbolically, algebraically. Lose a set of parens, and a partial.

` ((comp mult repeat) 2 16)`

We have eliminated all instances of partial. So let’s use **C** to get rid of the comp.

` (mult (repeat 2 16))`

This expression is easy to understand, provided you understand **mult** and **repeat**.

Just one thing. Did you buy that last substitution? I claimed above that the **C** rule works as follows:

` ((comp f g) x) == (f (g x))`

But the rule I actually used was this:

` ((comp f g) x y) == (f (g x y))`

The thing to understand is that because Clojure functions can be variadic, **C** is really a pattern of rules, dependent on the arity of g.

- ((comp f g) x) == (f (g x))
- ((comp f g) x y) == (f (g x y))
- ((comp f g) x y z) == (f (g x y z))
- … etc …

Similarly, **P** is also a family of rules:

- ((partial f g) x) == (f g x)
- ((partial f g) x y) == (f g x y)
- ((partial f g) x y z) == (f g x z)
- … etc …

The situation with **P** is even trickier, because we have to also account for the fact that **partial** is variadic:

- ((partial f g) x) == (f g x)
- ((partial f g h) x) == ((partial f g) h x) == (f g h x)
- … etc …

In general, **P** allows us to transform (f x_{1} x_{2} … x_{n}) into ((partial f x_{1} …. x_{k}) x_{k+1} … x_{n}) for our choice of 1 <= k < n.
Something to note is that the **P** and **C** rules are bidirectional. We can take advantage of that to run the analysis of @ghoseb’s code backwards, and maybe get some insight into how to construct a point free solution in the first place.

The solution will have to implement exponentiation. Whatever the implementation, it will have to be true that ((solution 2) 16) evaluates to 256. We don’t know the details, but we see the shape of it. We can start with a fairly natural solution with the wrong shape, below, and use the **P** and **C** rules to mold the solution into the right shape.

```
(mult (repeat 2 16)) ;; now use C
((comp mult repeat) 2 16) ;; use P
((partial (comp mult repeat) 2) 16) ;; use P
(((partial partial (comp mult repeat)) 2) 16) :; use def of mult
(((partial partial (comp (partial *) repeat)) 2) 16)
```

And done. The trick, as in algebra, is to know which rule to apply when. Practice helps, as does a clear understanding of what rules apply, and why. I hope anyone who got this far finds some value in this analysis.

My thanks to @alandipert and @ghoseb for the lovely puzzle. It was instructive, in more than one way.

Years ago I made a promise to my wife that I would not allow my daughter to “check out from math”. I have kept that promise, and in so doing have tried to bear in mind that it is hard to learn to think with symbols. This fall my daughter came home first day of school with a math assignment, a variety of simple algebra problems. It was a diagnostic, the problems were nothing she hadn’t seen before, but she was out of practice after a summer off. I walked her through the assignment, but I too was out of practice. Not with the math, that I could do without thinking. And I did, without thinking. And without the patience and understanding that I should have shown. My daughter thought I was disappointed with her. My fault. This problem reminded me of what it’s like to struggle with symbolic thinking. I hacked without plan or self-awareness, and I floundered.

After I saw @ghoseb’s solution I took the time to think systematically, and was rewarded with insight. I learned a bit about programming, and a bit about humility and patience. It was a good day.

Thanks a lot for the blog post David.

+5 Insightful.

September 3, 2012 @ 12:29 am

Coming from the author of the code under discussion, that means a lot. Thank you.

September 3, 2012 @ 8:23 am

I don’t know where I messed up, but I found a much more complex solution to the problem : (comp (partial comp (partial reduce *)) (partial partial repeat))

I guess somewhere I added inappropriate intermediate comps/partials.

But thanks to your reminder of systematic application of equational reasoning, I was able to “reduce” the above to the original (reduce * (repeat x y)) form :)

September 3, 2012 @ 6:55 pm

Very, very nice write-up David!

My favorite part of your post is your exploration of the unique compositional properties of point-free code, and your extraction of ‘mult’. The “dynamic vs. lexical” scopes issue is nowhere in sight, because variables have been removed completely from the story! There is only one, very simple substitution rule – definitions expand to functions.

In most peoples’ minds, and in mine until I was exposed to John Backus’s ideas, “point-free” is synonymous with “pointless”. I think you prove here that this is not the case, deriving both reusable code and abstractions from the exercise.

Your mathematical destructuring of the problem reminds me a lot of the algebra that Backus derives as the basis for his Function Level paradigm, and this is the same paradigm that inspired my initial tweet.

I highly recommend checking out http://archive.org/details/JohnBack1987 and http://dl.acm.org/citation.cfm?id=21855.21859&coll=DL&dl=GUIDE&CFID=90748351&CFTOKEN=52866005. I think you’ll be amazed by how far Backus goes with some of the ideas you stumbled on in your own exploration!

September 3, 2012 @ 7:29 pm

Alan, being mentioned in the same sentence with Backus is lavish praise indeed. I have bookmarked both those links for study.

If you like this approach to thinking about programming, check out R.S. Bird’s Algebraic Identities for Program Calculation.

September 3, 2012 @ 9:04 pm

Hi David!

Very good exploration of the algebra of the code. It’s a good exercise.

I think this goes to show that Clojure is not so great for expressing point-free style. It is very hard to read your example and know what it does. It is expecially clear when compared to the simple fn based version you presented, which is extremely clear.

I use Haskell at work, and it is much better for point-free style since every application is partial application (so you don’t have to be explicit about it) and composition is a single infix character. Though Haskell has its own issues, for instance composition is limited to functions of one argument, and in this case repeat takes two!

Well, all languages have their tradeoffs. I think Haskell wins out on this one because the solution to this problem is just to use the exponentiation function itself. However, it is not too often where it gets in the way in Clojure.

Thanks again!

Eric

September 6, 2012 @ 3:03 pm

Eric,

I have to agree. Haskell is an elegant and expressive language, and I too believe it is better suited to the point-free style than is Clojure, or any lisp. The way Haskell auto-curries functions is very conducive to point-free.

Thanks for you dropping by.

drc

September 6, 2012 @ 4:57 pm