Showing posts tagged clojure

Functional Thinking in Clojure: Part 2

Welcome to part 2 of my Functional Thinking in Clojure series. Today we’ll discuss how to optimize the Number Classifier we implemented last time like the original Java implementation was, and how to do closures in Clojure.

The Number Classifier (Optimized and Optimizable)

If you remember, the requirements for the Number Classifier are as follows:

… given any positive integer greater than 1, you must classify it as either perfect, abundant, or deficient. A perfect number is a number whose factors (excluding the number itself as a factor) add up to the number. Similarly, an abundant number’s sum of factors is greater than the number, and a deficient number’s sum of factors is less.

Our original implementation looked like this:

For a full discussion of my reasoning behind that implementation, see part 1 of this series. For now, all I’ll point out is that it’s a naive and terribly slow implementation for one very good reason.

The implementation of aliquot-sum relies on finding the proper factors of a given number. The implementation of that function in turn relies on finding all of the factors of a number and then filtering them. That means that I have to check every number from 1 to number and see if it’s a factor.

It’s correct, but man alive is it slow.

So let’s correct that.

Neal points out in part 2 of his series (and mentions in part 1) that there is a very simple optimization that involves realizing that if you have the factors of the square root of a number, you can quickly find the rest of the factors by dividing the number by each of those factors in turn.

So what we’ll do is open up our implementation to our users and give them the ability to provide their own implementation of our logic.

What have we done?

  1. I added a comment form at the bottom of core.clj that contains calls to time that can be executed from Emacs using C-x C-e if you’re using clojure-jack-in. They’re a quick and easy way to time how long a given call to classify takes to execute. This gives us the ability to see if our optimizations are actually making a difference.

  2. As you can see, if you have a particular part of your algorithm that you think might be useful to swap a different implementation in for, you just provide an argument for that part. Functions are first class citizens in Clojure so we just pass the name of the algorithm part in to our function and it get’s used.

  3. I use the idiom of arity overloading to provide defaults for arguments all the time in my own code. This allows us to call aliquot-sum naked and get the un-optimized version but at the same time provide a different function if we so choose. Obviously, by default you would want the optimized version but I left it this way for clarity.

  4. aliquot-sum-optimized utilizes a very common idiom in Clojure code of naming steps in a programming using let binding. Remember, the core optimization is to only explicitly check the numbers from 1 to the square root and then utilize the results of that to get the other factors. This is easy to do by naming each step and then combining them later.

  5. I also demonstrate here just how easy it is to use Java functions (read ‘static methods’) from Clojure. The Java Math class implements all sorts of goodness for mathematical operations and they implement it all as static methods. We love static methods because static methods are (or should be!) functional and thus we can call them directly by pretending that the class is a namespace.

  6. Notice that because the base abstraction for our system is a function, I can easily reuse the same function for finding factors that I used with the proper-factors implementation. I didn’t wrap that up in a class that I would then have to reference elsewhere, so I just get that logic for free.

That’s enough for that.

Now we move on to the ugliness of state…

make-counter With A Closure

I’ll admit outright that I don’t get closures. I think I understand them technically: You have a block of code that has implicit local bindings to the variables in it’s containing scope so that it can change it’s reference to them without changing other blocks with their own references to them.

I also have used them to great effect in Gradle et al and so I get their usefulness in terms of library and framework construction. But maybe I just don’t get the big deal of them. What’s the big deal that’s a bigger deal than first-class functions? I don’t know.

But that won’t stop me from showing how I’d implement it in Clojure!

  1. Yuk! Look at that state! I have no tests written for this guy because it’s hard to test functions that rely on state.

  2. make-counter relies on a let-bound atom named incremented which is set to 0 at the start. Every anonymous function returned from make-counter gets their own locally-bound reference to incremented.

  3. The defn form is actually a macro that does nothing but create a different form (def function-name (fn [args])). That’s why I can (def c1 (make-counter)) and then call c1 as if it’s a function. It is a function because make-counter returns a function and then gets assigned to the name c1.

  4. atom is one of the concurrency primitives provided by Clojure. One of Clojure on the JVM’s killer features is their STM and explicit state management logic. Everything is a value in Clojure by default. If you need state, you need to use one of the concurrency primitives which then force you to utilizes transactions to update their value. It’s overall quite a brilliant system but is well beyond the scope of this post to document. For now, if you use atoms, you just need to be aware that the way to update their state is with swap!. Read up if you’re interested!

Hopefully you’ve gleaned some useful tips from this post. Stay tuned till next time when I cover the code samples provided in the third article of Neal Ford’s Functional Thinking series.

Functional Thinking in Clojure: Part 1

I admit it. I’m one of the poor sods who had no idea who Neal Ford was until I watched his plan for world domination at the 2011 Clojure Conj. It’s a good presentation and discussion related to how to get your technology (even if it’s not Clojure) adopted by the circles you travel in. One of the things he mentioned in passing in that talk was his Functional Thinking Series at IBM Developer Works. That got me intrigued and then I found that he had an entire presentation that he’d delivered at Strange Loop which solidified my will to go through the series.

Then I figured: “Hey! Why not turn this into a little blog series?”. So here we are. I’ll be trying to go through the Functional Thinking Series one post at a time, converting the code examples into idiomatic Clojure, as I know it. Hopefully along the way we’ll have some nice epiphanies about programming in general and Clojure in particular.

I’m doing this for a few reasons.

  1. Even though I’ve been developing a system for a good number of months now in Clojure using almost no state, I still don’t feel like I grasp Functional Programming the same way I grasped Object-Oriented Programming. This doesn’t surprise me, but it does drive me to want to continue to wrap my brain around this extremely useful paradigm.

  2. While I applaud Neal’s efforts to make his series extremely accessible to great mass of developers who are still programming every day in Java, I thought it would be fun to be able to see his examples in Clojure.

  3. I’m still exploring Clojure and so I thought it would be useful to get feedback on my implementations, since I can’t release the source of the system that I’ve been developing.

I’ll be developing my conversions in a public GitHub Repo so you’re more than welcome to follow along and/or submit patches to my awful code.

Number Classifier

For our first trick, we’re going to take the Number Classifier example from the article and convert it to Clojure and see what we come up with.

From the article:

The requirements state that, given any positive integer greater than 1, you must classify it as either perfect, abundant, or deficient. A perfect number is a number whose factors (excluding the number itself as a factor) add up to the number. Similarly, an abundant number’s sum of factors is greater than the number, and a deficient number’s sum of factors is less.

Fairly simple. If you’re interested, you can read about Abundant, Deficient, and Perfect Numbers over at Wikipedia. I know I did!

Here’s the final implementation I came up with.

I developed the solution as much as possible using TDD and you can follow along with that process at the GitHub repo.

Some notes about the implementation:

First, I noticed late in the game that perfect, abundant, and deficient numbers are related to something called an aliquot sum. I failed pre-calc in high school so I’m not the best person to consult about math, but I can read specs. An aliquot sum is just the sum of the proper factors of a number. My implementation ended up being written in terms of that function, rather than Neal’s implementation which chose to focus more on how to gather factors. Neal’s focus leads to the collection of is* functions at the bottom all repeating sum(factors(number)) - number … number;. For me, the fundamental part of this problem was comparing the aliquot sum to the number, so that’s what my implementation ends up focusing on.

I ended up (and end up in real life) yielding many of the implementation details that Neal talks about to my run time, as he said I would. I’m not sure exactly if this is a product of thinking functionally or not. After all, Java 5 introduced for (type var : arr) and while that abstracts away the very common idiom of looping over the entirety of a collection, I’m not convinced it helps you be functional. But maybe it does. I take the use of my functional language’s constructs a step further because I’m not as concerned with being accessible to people new to functional thinking through the use of filter, range, partial, and reduce.

I also make no effort to duplicate the efficiency optimization that the original Java implementation utilizes. That’s for the next part in the series.

I make no new use of higher-order functions but I do use comp and partial. I like this use especially as it it shows how awesome it is for everything to be a function. The / operator isn’t a language level operator, but a function with a funny name. Same for >. That makes them instantly composable and thus subject to use in functions that return functions like partial and comp. I’m beginning to understand the benefits of composability much more in systems that I develop.

I’d be quite interested in hearing your thoughts on my implementation, how I could make it better, and other constructs in Clojure that I could be using to make this code even cleaner.

Stay tuned for the next part of this series at some point in the near future.

Clojure is a sequence processing language – sequences are the core abstraction between data and function. I have come to the notion that code that handles 1 or N of something is far more likely to be correct than code that handles 2 (or any fixed number > 1). In general, any time you use the second function, your warning sensors should go off.

2 is a smell : Pure Danger Tech

Solid advice. I’m happy to report that I don’t have any occurrences of second in my own code base, but it wasn’t because I knew or thought of it as a smell. I have structure specific code all over, though, because I deal with a particular map data structure that’s core to my system.

I wonder if I can get rid of that…

Uncle Bob’s Bowling Game Kata, Clojure Style

Introductions

Lately, I’ve been getting into a new(ish) language for the JVM called Clojure. It’s wicked cool, fulfills my rabid desire to learn a Lisp, and is backed by some people I’ve come to respect a lot.

The bullet points of Clojure are fairly simple:

  • Build on the inherent power of Lisps in general, but in such a way that you’re not encumbered by decisions that were good 50 years ago but make no sense now.
  • Embrace the host platform, the JVM (and even the CLR).
  • Provide language level support for concurrency-oriented programming so that people can avoid the hell of concurrent programming in any of the imperative, lock based, OO languages on the plate today.
  • Be (practically) functional.
It’s a Lisp

Lisp is this ultra-cool language designed by a guy named John McCarthy over 50 years ago which itself was based on the Lambda Calculus. Amazingly, he proved that you can create a language where every computable problem can be expressed in terms of just 7 primitives (quote, atom, eq, car, cdr, cons, and cond). As such, Lisp has been described as beautiful, elegant, concise, syntaxless, etc. and all of the negative corollaries you can imagine: obtuse, obscure, opaque. Doubtless, though, no one interested in Computer Science can not get goose bumps reading about all of computation being described in just 7 terms.

Lisp has this funny habit of continually coughing politely and reminding people that it was doing every cool new innovation in computer science since it’s invention. XML has been described as Lisp redone. Metaprogramming is just Lisp multimethods and ad-hoc hierarchies. Functional programming like Haskell? It’s just Lisp. Of course whenever that comes up there’s a large bevy of extremely smart people who calmly attempt to remind everyone that it’s not exactly true. Lisp didn’t invent every good idea known in computer science. What is true is that as programming languages become more powerful, they do begin to adopt features of Lisp and many other functional languages that Lisp has had for decades. They do so with different syntaxes and larger libraries, but many of the greatest ideas of computer science were expressed quite elegantly in functional languages like Lisp.

As such, Rich Hickey, who was a Lisp fan to begin with while not being able to afford to be a Lisp professional, thought it wise to attempt to reintroduce the language, especially since it has such potential power for use in todays concurrency-oriented world.

Embrace the platform

Where many Lisps have failed in the past has been in the area of libraries and platforms. I’ve never coded in Common Lisp, and the old saying is that "Every C program includes a poorly written and buggy implementation of half of Common Lisp", but at the same time, since Lisp never really caught the imagination of the professional development community, new libraries are hard to come by. Compared to the explosion of Libraries for a poor language like Java, Lisp has always been somewhat left in the dust.

So M. Hickey decided that he’d solve the library problem, and the GC problem, and the System Call problem, and the etc. problem, by using the stunning piece of technology called the JVM as his platform. This means that at the expense of adding a couple of new primitives to McCarthy’s 7, he was able to provide amazingly good interoperability with Java, and thus open up the entire ecosystem of Java libraries to Clojure developers.

Many Clojure programmers like to say that Clojure does Java better than Java. And I’m inclined to agree.

A canonical example:

(doto (JFrame.) (add (JLabel. "Hello World")) pack show)

It’s important to note that the only special, Clojure, part of that line is doto. Everything is purely Java Swing. (JFrame.) constructs a new JFrame, doto is a macro that is a little like the with operator of languages like Ruby that allow you to avoid typing the thing you’re operating on over and over and over again, the rest, if you’ve done any Swing programming, should be familiar to you because it’s just native Java calls.

The interesting thing here, for people who think that Lisp stands for Lots of Irritating Superfluous Parentheses, is that that code snippet beats Java, handily, for paren count.

Beyond being able to call Java from Clojure, all of Clojure’s core abstractions are defined in terms of Java Interfaces which mostly implement things like Collection. All data is the Object version of that data (i.e. ints are Integers), but can be coerced into primitive types for performance. That means that Java code written against the core Java abstractions (like all good code should be) can seamlessly interoperate with the Clojure data structures.

Java interop in Clojure rocks. Really.

Language level support for concurrency

I’ve never had the joy it sounds like programming concurrently in lock based languages personally, but reading through JCIP and listening to people who’ve done it extensively scares me enough that I never want to.

Clojure provides amazing support for concurrency directly in the language through reference types, persistent, immutable data structures, and a remarkable STM implementation based on the MVCC.

Functional

While Haskell may be the only possible truly functional language, Clojure strikes a better balance between the real world that does actually change and the functionally pure world that’s easy to reason about and model. Rich Hickey is not an academic by profession and he knows that when you’re programming most systems, you need side effects and you need state. Suffice it to say that where purity conflicted with practicality, M. Hickey sided with practicality most of the time. The persistent data structures and how they interoperate with change and transaction semantics is truly remarkable and easy to grok. At the end of this post I’ll link to some videos that are worth your time which do a much better job describing why Clojure’s concurrency primitives are the best concurrency story on the market today.

Kata

Because of pragmatic Dave’s efforts, software kata seem to be all the rage these days. I was actually introduced to them via Uncle Bob’s excellent Bowling Game Kata, which indeed is the subject of this post. Uncle Bob, in this case though, is the one who hit the nail on the head as far as the point of kata and how they should be thought about, over against Pragmatic Dave.

A kata is meant to be memorized. Students of a kata study it as a form, not as a conclusion. It is not the conclusion of the kata that matters, it’s the steps that lead to the conclusion. If you want to lean to think the way I think, to design the way I design, then you must learn to react to minutia the way I react. Following this form will help you to do that. As you learn the form, and repeat it, and repeat it, you will condition your mind and body to respond the way I respond to the minute factors that lead to design decisions.

So, what’s his basis?

From Wikipedia:

Kata is a Japanese word describing detailed choreographed patterns of movements practiced either solo or in pairs.

Again

One explanation of the use of kata is as a reference guide for a set of moves. Not to be used following that “set” pattern but to keep the movements “filed”.

A nice moving example (for however long it stays up) can be found in this clip from Fist of Legend round about 9 minutes 11 seconds.

A software kata takes the traditional notion of a short but thorough series of movements designed to tune your body to react in certain ways to a preconceived set of situations as well as to become used to moving in certain ways and translates it into a series of actions leading to the solution of a software problem.

It’s very important to realize that the ‘point’ is not the solution. If that were the point then ‘practicing’ a kata would make no sense. Once the problem’s been solved, why solve it again? Even more important is that no problem can be truly interesting and solvable in a short enough amount of time that you can practice it every day. Katas are short enough that you can spend 15 minutes in the morning ‘loosening up’ with one and actually get some benefit from it.

A kata a day keeps the debugger away

Uncle Bob and Stuart Halloway

Uncle Bob is an all around great dude who cares intensely about software, developers, and customers. His video from OREDEV about clean functions changed the way I thought about writing code. I read pretty much anything I can get my hands on from him. The reason I bother mentioning him at all is because he’s the one who designed this particular kata in Java.

Stuart Halloway is another of these luminaries who I’ve begun to come in contact with mainly because of my interest in Clojure. He’s one of the big name Clojure users and is a regular contributor not only on the Google Group but on the actual code base as well. His solution is what I ultimately based this kata on, with some minor tweaks..

Prior Art

The bowling game Kata is quite simple.

The problem is that we want to score a game of American 10 pin bowling.

The steps to memorize are these.

  1. A brief design session
  2. Set up your project
  3. Test 1: Score a gutter game
  4. Test 2: Score a game of 1 pin frames
  5. Test 3: Score a game of 1 spare frame, a 3 pin frame, and gutters
  6. Test 4: Score a game of 1 strike frame, an 8 pin frame, and gutters
  7. Test 5: Score a perfect game

Test 5 should actually require no extra coding. The way it was originally published was as a Java kata.

Now, Uncle Bob is getting into Clojure and he wants to translate his kata into it. This leads to some difficulties and some not too pretty code as it’s really his first foray into Clojure any way. He publishes it nonetheless and asks for feedback.

Stuart Halloway comes along and does a nice implementation of the kata solution and even publishes a wonderful little post about his thoughts while refactoring.

So why am I bothering writing this? Well, because I can’t find anywhere where this kata was published as a kata on the web and I figured I’d rectify that. Remember, the kata isn’t the solution, the kata is the process leading to the solution. For a kata to be a kata, you should be working in the same IDE and use the same file names, and literally do every single thing exactly the same as the kata you’re following. Do it a hundred times before you start looking for ways to improve it!

Here’s the kata, then.

The Kata

I’ll give the high level steps. The easiest way to learn the kata the way I do it is to watch the video I’ll embed at the end.

  1. A Design Session

    • Bowling can be thought of as a sequence of rolls, some number of which constitute the score of a certain frame. Example: (repeat 0) or (repeat 10)
    • The total score, then, is the score of 10 frames, plus a certain number of rolls if the last frames require them, because they are a spare or a strike.
    • We’ll need a score-game function which takes a sequence of rolls. We’ll throw in the rolls as an infinite sequence just for fun, even though that goes beyond our requirements.
    • We’ll need a score-frame function to score each frame. Example: (reduce + (map score-frame (to-frames game-rolls)))
    • We’ll need functions to determine if a particular sequence of rolls is a strike or a spare. Example: (strike? game-rolls)
    • We’ll need a function to transform a series of rolls into a series of frames that can be totaled up. Examples: game-rolls => (10 5 3 0 0 0 0 ...) (to-frames game-rolls) => ((10 5 3) (5 3) (0 0) (0 0) ...)
  2. Set Up

    • Create a directory called bowling-game. I always do it on my Desktop because you’re going to delete it as soon as you’re done.
    • Create main and test directories under their.
    • Create bowling-game.clj in both of those directories.
    • Create a bowling-game namespace in test/bowling-game.clj and use deftest, is, and run-tests from clojure.test.
  3. Test 1

    You’re first test!

    Score a gutter game. At the end you have

    test/bowling-game.clj:

    (is (= 0 (score-game (repeat 0))))
    

    main/bowling-game.clj:

    (defn score-game [game-rolls]
      0)
    
  4. Test 2

    Score a game of 2 pin frames. At the end you’ve added

    test/bowling-game.clj:

    (is (= 20 (score-game (repeat 1))))
    

    main/bowling-game.clj:

    (defn score-game [game-rolls]
        (reduce + (take 20 game-rolls))
    
  5. Test 3

    Score a game of 1 spare and a 3 pin frame. At the end you’ve added

    test/bowling-game.clj:

    (is (= 16 (score-game (concat [5 5 3] (repeat 0)))))
    

    main/bowling-game.clj:

    (defn score-game [game-rolls]
      (reduce + (map score-frame (take 10 (to-frames game-rolls)))))
    
  6. Test 4

    Score a game of 1 strike, an 8 pin frame, and gutters. At the end you’ve added

    test/bowling-game.clj:

    (is (= 26 (score-game (concat [10 5 3] (repeat 0)))))
    

    `main/bowling-game.clj:

    nothing
    
  7. Test 5

    Score a perfect game. This simply runs.

  8. Test 6

    Score a game of spares specifically of the configuration 0 10 repeating. My favorite.

    test/bowling-game.clj:

    (is (= 100 (score-game (cycle [0 10]))))
    

    main/bowling-game.clj:

    nothing
    
  9. Formatting

    Format to your tastes. I find that because of how compressed Clojure code tends to be it benefits more than most languages that I’ve seen from good formatting practices.

  10. Done

    Have a beer.

The Video

For the nitty gritty details of myself performing this kata, I present the following:

Bowling Game Kata in Clojure from Tim Visher on Vimeo.

Further Reading

So there you have it. The Bowling Game Kata published as a Clojure Kata (not just a solution!).

If the common wisdom that I hear from almost every software luminary is true, I would absolutely recommend you learn new languages and for the best bang for your buck, make it a language as different from what you’re used to as Clojure almost certainly is.

Here’s some great clojure resources: