factorials.core

Exploring Clojure with Factorial Computation

"Fork me on on GitHub!"

This project demonstrates a variety of of Clojure language features and library functions using factorial computation as an example.

Many Clojure tutorials (and CS textbooks, for that matter) use factorial computation to teach recursion. I implemented such a function in Clojure and thought: "why stop there?"

Basics

The classic (and verbose) loop + recur example.

reduce * on a range

apply * to a range

apply * but take-ing from an iterate

"Code is data, data is code"

Higher-order functions FTW.

This returns a function that you can later call to compute a factorial value when needed.

Usage:

(def fac5 (make-fac-function 5))
(fac5)
=> 120

Here we illustrate Clojure homoiconicity using eval cons and ' (quote).

Our function is building a valid Clojure expression that we then eval. Here's how you would do it manually at the REPL:

(def fac5 (cons '* (range 1 6)))
(println fac5)
=> (* 1 2 3 4 5)
(eval fac5)
=> 120

defmacro generates Clojure code for a function that will calculate a fixed factorial value on-demand.

Similar to the previous function, but note the macro output.

 (macroexpand `(factorial-function-macro 5))
 => (fn* ([] (clojure.core/* 1 2 3 4 5)))

(More information on the mysterious fn* here)

Parallel Computation

Using future dosync and alter

partition-all is just fantastic, by the way.

Reminder: map is lazy, so force execution with dorun (effectively discarding the results).

Using agent send and await

I found that (send result * p) doesn't work here, because of how * and send are overloaded. Perhaps this is obvious, but I puzzled over it for a while.

Also: per Joy of Clojure (§11.3.5) this is not the best use case for Agents (particularly the await call at the end).

pmap to the Rescue

If the previous code looked arduous, never fear. Enter: pmap

Yes, it is map executed in parallel (lazily!) .

There is also pvalues, which evaluates a list of expressions in parallel.

Even though this works, it feels wrong having to jump through hoops with defmacro like this.

pmap is more natural for this use-case.

pvalues calls a collection of zero-arg functions in parallel to create a lazy sequence. Again, I had to use defmacro to accomplish my goal.

More Advanced Stuff

Rolling Your Own Lazy Sequences

In simpler times, we used functions like take range and iterate to compute factorials. Under the covers, these functions create "lazy" sequences.

In fact, we can cut out the middleman and compute a lazy sequence of factorials using cons and lazy-seq

I find "top-down" style to be more readable, so I forward-declare my function that generates the lazy seq.

We use nth to grab the target factorial value from the sequence.

Finally, the function to generate the lazy factorial sequence. In this case, I've made it private to the namespace with defn-.

Trampoline

Here, I've created a factorial function for use with trampoline.

If you're not familiar with trampoline, it basically works like this:

1. trampoline calls the function you pass in.
2. If your function returns a value, trampoline returns that value.
3. However, if your function returns a function instance, trampoline calls that function.
4. Repeat steps 2 and 3 until we finally get a non-function value.

Example usage:

(trampoline (factorial-for-trampoline 5))
=> 120

A benefit of trampoline is that it allows mutual recursion between functions without overflow.

Multimethods

I also thought of a way to compute a factorial using multimethods (and some recursion).

First define a "struct" that has the fields n and value

(Yes, a tuple in the form of {:n 1 :value 1} would also have worked here, but (to be honest) I wanted to use defrecord in at least one of these examples)

By the way, we actually just defined the Java class factorials.core.Factorial

To define a multimethod, first you define the dispatch function with defmulti. Here our function dispatches on just two possible values: true or false, where "false" means we reached the end of our factorial computation.

The function argument {:keys [n]} is actually an example of one of Clojures mini-languages, "destructuring." For more on that, see Jay Fields' terrific blog entry.

Our multimethod repeatedly dispatches to this function while n < limit (true)

Note how I had to overload this method to initialize our Factorial struct on the first invocation.

We hit the multimethod function for false when our Factorial struct has the desired :n value. It returns the final factorial value after one last computation.

Using Arrays

Clojure also supports operating on arrays, for when you absolutely, positively need performance (at the sacrifice of immutability).

long-array creates a Java long primitive array, and the functions aset-long aget and areduce operate upon it.

(Of course, this approach requires allocating and initializing an array of size n. The real point is to illustrate Clojure array functions, not performance).

Java Interop

Elsewhere we wrote a plain old Java class with a static method that computes factorials. We can still re-use that legacy code via Clojure's Java interop.

Taming Java Complexity

But what if our Java team read Effective Java, 2nd Ed. and decided to use the Builder pattern?

We can use the -> operator (aka the "pipeline operator") to get this under control.

And if you're working with java.util.Map instances or "JavaBeans" with copious "setters," there's the doto macro.

More on the Pipeline Macro

I found clojure.walk/macroexpand-all really useful for understanding and debugging the -> macro:

Executing the following at the REPL

outputs

which is equivalent to

Implementing Java Interfaces

Perhaps our Java team, which doesn't use Clojure, needs us to implement one of their API interfaces.

Here we use reify to generate a Java class that implements the example.ValueComputer interface while re-using one of our functions for the implementation.

Finally...

Why not just use Incanter? (Duh!)

Epilogue: HALL OF SHAME

Here are some functions I wrote that "work" but have hidden defects or are just plain wrong.

defs Aren't Variables

After calling (factorial-using-do-dotimes 5) you will have a var named a pointing to a value of 120. Unless another thread called the function concurrently, in which case who knows what happened?

This is because def binds to the namespace, not the scope of the function.

This approach using do and while has the same correctness problem as above. Now you have two vars in your namespace: a and res.

Abusing Atoms

An example using Atoms. I suspect one would never (ab)use atoms locally-scoped like this (although they work well for implementing closures).

However, perhaps you could contrive an example using the Factorial struct from earlier and compare-and-set!

Recursive Agent Race Condition

Finally, an attempt to compute a factorial using an agent that recursively submits computation tasks to itself.

This approach sometimes fails due to a race condition between the recursive (and asychronous) send-off and the await call.

(for [x (range 10)] (factorial-using-agent-recursive 5))
=> (2 4 3 120 2 120 120 120 120 2)
(for [x (range 10)] (factorial-using-agent-recursive 5))
=> (2 2 2 3 2 2 3 2 120 2)