Bowling Kata

I've been working on a lot of Katas past few days. Some of them have been trivial and some more challenging. Generally, before I start on a kata I will watch a kata cast before trying it. This gives me a good idea of where I need to go before starting. However, it doesn't really simulate a real life situation very well. In real life you are given a problem and you have to solve it without any clue what the solution might be. So, before I started the bowling kata I decided not to watch the kata cast or look at any previous solutions. It took me a lot longer to come up with the solution than I thought it would. It was significantly harder to write the algorithm with out knowing the solution ahead of time. However, I think it was very valuable to approach the problem without any preconceptions. My algorithm was very messy. I took in an array of rolls and looped over them to sum up the score. The algorithm was really long with lots of duplicaiton. So I decided to make the problem smaller. I refactored so that I was taking in an array of rolls and returning an array of frames. This refactoring allowed me to stop looping once I have reached the maximum amount of frames, 10. It is also a lot easier to test. I can test special frames (strikes, spares, and the 10th frame) without passing in an entire game. So, through this kata I learn a valuable lesson of continuing to break the problem into smaller chucks. Here's the final product.

Prime Factors in Clojure

SCNA

Last weekend I attended the Software Craftsmanship of North America Conference. Overall, it was a really sweet experience. Having never attended a software conference before, I was pleasantly surprised by how much fun it was. One of my favorite things was the community there. There is a very close camaraderie, even among competing companies. Everyone was united by the common goal to become better Craftsman. This also means that there was an atmosphere of learning. Everyone wanted to learn more about everything. My favorite talk was by Carl Erickson, which, strangely enough, was not specifically about programming, but about what makes a conducive environment for Craftsmen to work. I was very intrigued by the wisdom he shared about open financial policies, open work spaces, collaboration and so forth. My least favorite talk was by Zed Shaw. He was relentlessly trying to tell us that we had lost our way and forgotten about just programming. I didn't understand his points because the Software Craftsmanship movement is about being a better programmer. Regardless, it was still enjoyable to have my ideas challenged. All in all, my first conference was really fun and really exhausting. By the end of the weekend I didn't even want to think anymore. This can probably be compared to an athlete being tired after a workout. If you're not tired, you probably didn't work to hard. So, I'm glad that I learned a lot at the conference, but I was glad to rest afterwards as well.

The Clean Coder (3)

I finished reading The Clean Coder last night. Here's the last few nuggets I gained from it.

Apprentices, Journeymen, and Masters

In the last chapter of the book, Uncle Bob explains what it means to be each of these. To be an apprentice is to be, essentially, a learner. As an apprentice you have little autonomy. You are learning from the Journeymen. The Journeymen have already been vetted. They are competent and skilled. They are working to become a master of their craft and are learning from the Masters. The Masters are the leaders, the captain of the ship. They are experienced and skilled, and have the scars to prove it. They know software, but are still learning.


It has been cool to see how this ideology works itself out at 8th Light. As an apprentice I am being mentored by a Craftsmen and being vetted. I have little autonomy and I am trying to learn as much as possible. There is no official between "Journeyman" and "Master" at 8th Light, but among the Craftsman there is a culture of continual learning, from the outside and from each other. And of course, we are all still learning from our Master Craftsman, Uncle Bob. Nonetheless, I am extremely grateful to be a part of this culture of learning. It is the only way to become a master of your craft. 

The Clean Coder (2)

Today I read some more of the The Clean Coder by Robert Martin. Here's a few more of the things I've been learning about being a professional developer.

Stay out of "the Zone"

The hyper-productive state of mind, known as "the Zone", is highly sought after by much of the development world. Many developers will put on headphones as large as the side of their head, isolate themselves, or take whatever other measures necessary in order to get in "the Zone". However, Uncle Bob argues that this state of mind is not as productive as claimed. He claims, "It's really just a mild meditative state in which certain rational faculties are diminished in favor of a sense of speed." The main argument is that the code written while in "the Zone", will suffer in quality and have to be written again. This is because the decisions made while in this mind set will not be mind with quality in mind, but decisions will be made that favor completion and maintaining velocity. It is similar to highway driving. Most drivers lean back, flip on the cruise control and let their minds wander. While in this mindset, most drivers aren't focused on driving defensively or being cautious, they are focused on not slowing down or breaking their cruise control, therefore they are more dangerous to themselves and those around them. The same applies to coding in "the Zone". Everyone's code is in danger.

Working Under Pressure

Uncle Bob opens this section with a quick comparison of how surgeons and developers act under pressure. Surgeons act calm and collected, stick to their disciplines and training, and act professionally. Developers usually act like a two year old who just got his toy taken away from him. This is obviously not professional. If you want to be taken seriously as a professional, we must throw out the attitude, stick to our disciplines and act professionally. This does not mean that we put in 80 weeks, coding until 2AM. This will not get more done, but create a mess. This mean that we manage our time better, write more tests, and pair programming to avoid wasting time on debugging.

The Clean Coder (1)

Yesterday I read about half of The Clean Coder by Robert Martin. So far, this book is great. It is very interesting and easy to read. The book is essentially about how developers are to act in the workplace, as professionals. While this may not be the first book on the market about how to be a professional, it offers the unique perspective a software developer. Even though my career is only 6 months old, I wish that I had read this book 6 months ago. Here's a few of the things I have learned so far.

Work Ethic

Within the software world, the most common attitude I have seen about work ethic has been to work hard while at work and then leave. With this attitude, there is no room for training outside of work, practicing outside of work, or reading software books outside of work. If those things are to happen, they have to happen on work time, on the boss' dime. However, Uncle Bob presents a very different idea. He simply states that these things your responsibility. You need to be learning, reading, and practicing on your own time. He draws a great analogy that musicians don't get great by performing, but by practicing. The same applies to software developers. We need to continuously learn and practice our craft, on our own time. Here is Uncle Bob's suggestion,

I'm not talking about all your free time here. I'm talking about 20 extra hours per week. That's roughly three hours per day. If you use your lunch hour to read, listen to podcasts on you commute, and spend 90 minutes per day learning a new language, you'll have it covered. Do the math. In a week there are 168 hours. Give your employer 40, and your career another 20. That leaves 108. Another 56 for sleep leaves 52 for everything else.¹

Do; or do not. There is no trying.

There is a huge temptation in the software world to say, "Sure, I'll try." Your boss asks you to get something done by Monday, but you know that there is now way that it can be done until Wednesday, so you say, "I'll try." Uncle Bob states that this is simply unprofessional. As professionals, we should never say that we'll try to do something. We give accurate estimates and we stick to them. By saying, "I'll try", we are giving our employers a false sense of security and lying to them. We have to act as professionals and stick to our estimates.

1. Martin, Robert C. "Chapter 1: Professionalism." The Clean Coder: a Code of Conduct for Professional Programmers. Upper Saddle River, NJ: Prentice Hall, 2011. 17. Print.

The Pragmatic Programmer

I just finished reading The Pragmatic Programmer by Andrew Hunt and David Thomas. Here's a few things that I learned while reading this book.

Design by Contract

A code contract specifies how a function should work by clearly stating the preconditions and postconditions of that function. This is an important concept for a few reasons. 1) It is testable. If I know exactly what the pre and post conditions of a function are, it is very easy to test if the function is working as stated. 2) Other people know exactly how your function should work. 3) If the contract is stated clearly enough, it will be very easy to tell who is at fault when the function fails. 

When to use Exceptions

This section explains that Exceptions should only be used in the case of, well, something exceptional (i.e. something that doesn't normally happen). They should not be a part of the normal flow of our software. With each exception, control is transferred from your function to somewhere else. The context switching involved in this is expensive and hard to maintain. Eventually, this style of code will turn into spaghetti code.

Decoupling and the Law of Demeter

This section explains how to decouple classes and methods from each other via the Law of Demeter, which says that a function should only call 1) itself, 2) parameters, 3) objects it creates, 4) functions of the same class. If we write code following these rules, we will avoid coupling classes together. Of course this method has exceptions, such as static functions. It is extremely difficult to take in a static object as a parameter. One options is to create a wrapper class that can be instantiated. This will be useful for testing and decoupling.

Pride and Prejudice

This is a simple concept that a Developer is to be proud of his work. The pride that we have in our work should express itself with our signature at the top of every file which we own. This is an intimidating concept for those that like to remain anonymous. However, if your code is tested, comment, and decoupled, your signature will stand as a symbol of quality.

Domain Languages

This section explains that when we need a specific way to describe some data or problem, we should create a Domain Specific Language. On example is makefiles. There is a domain specific language used for writing makefiles and there is a parser that interprets them. The authors simply state that if we need a language that is closer to our problem, just create it. However, I don't agree with this for a few reasons. 1) DSL's are an investment. The parser for makefiles didn't come together overnight. It took a lot of time. 2) It's hard to disseminate and maintain them. If you start using some language you just made up for a project, you are the only person that knows about it. If you leave the project or worse, get hit by a bus, your team is in trouble. 3) There are already a lot of great languages for describing data, XML, YAML, JSON, to name a few. These are standards that are very well known and have very developed toolsets to accompany them. For these reasons, I don't agree with developing a DSL whenever needed.

Minimax Depth

In my last post I mentioned that my Minimax algorithm would overflow whenever I tried to calculate moves on a 4x4 board. I attempted to solve this problem by converting the Minimax algorithm to a tail recursive algorithm. This worked fine, however, it was really slow. So, I needed to search for another way. Another apprentice here suggested that I pass in a depth limit to my algorithm. So, I refactored my original forward recursive algorithm and have it working. Through some trial and error I have found that in order to maintain unbeatably, the max depth must be at least 5 on a 3x3 board and 7 on a 4x4 board. So, here is my fast and scalable Minimax in Clojure, 

(defn- forward [player board alpha beta game-state-fn max-depth depth]

  (let [state (game-state-fn board)]

    (if (not= state (game-states :playing))

      (* -1 (+ (get-state-score player state) depth))

      (if (>= depth max-depth)
        (scores :draw)

        (loop [alpha alpha open-spaces (board/open-indecies board)]

          (if (or (empty? open-spaces) (>= alpha beta))

            (* -1 alpha)

            (let [score (forward (players/get-other-player player)

                (assoc-in board (first open-spaces) player)

                (* -1 beta) (* -1 alpha) game-state-fn max-depth (inc depth))]
        (recur (max score alpha) (rest open-spaces)))))))))

Tree Traversal with Tail Recursion

Anyone who has ever tried to build an AI for a Tic Tac Toe game has come across the Minimax algorithm. This algorithm simply iterates through the children of a node and returns the maximum value. This is perfect for Tic Tac Toe because it will iterate through every possible board and return the highest scoring option. This allows you to build a AI that is unbeatable. By design this algorithm uses forward recursion to traverse the tree of boards. This allows you to see all the options available to you and then choose the best one. On a normal 3x3 Tic Tac Toe board, this will work fine. However, when I tried to run the forward recursing Minimax on a 4x4, I quickly received a wonderful stack overflow error. So, lets take a look at it.

(defn- forward [player board game-state-fn]

  (let [state (game-state-fn board)]

    (if (not= state (game-states :playing))

      (* -1 (get-state-score player state))

        (loop [best-score (scores :lose) open-spaces (open-indecies board)]

          (if (empty? open-spaces)

            (* -1 best-score)

            (let [score (forward (get-other-player player)

              (assoc-in board (first open-spaces) player) game-state-fn)]

              (recur (max score best-score) (rest open-spaces))))))))

Note: this is a very naive implementation. It does not apply a heuristic score or perform any sort of branch trimming. Nonetheless, it runs quickly on a 3x3 board. However, with a 4x4 board, it will overflow. My first idea was to try memoizing the recursive call. This did improve the speed of the calls significantly, but it still crashed on a 4x4 board. So, it looks like the best option is to convert this into a tail recursive algorithm. Essentially, we are attempting to perform a in order traversal of an unbalanced tree. Unfortunately, with the current implementation, we have no way to return to our parent once we reach a leaf node. So, I believe we are going to need a basic data structure to hold our tree. Something, like this should suffice.

Tree
  :parent
  :current-node

  :children
  :best-score

This simple object will maintain our tree structure and allow us to traverse the tree without losing our parent. In Clojure this looks like,

(defrecord BoardTree [board parent children best-score])

Using this data structure, we can implement the tail recursive version of Minimax.

(defn- tail [player current-node game-state-fn]

  (if (and (= nil (:parent current-node))

    (= 0 (count (:children current-node))))
      ;base case
      (* -1 (:alpha current-node))
      (let [state (game-state-fn (:board current-node))]
        ;determine if this is a leaf node
 (if (not= state (game-states :playing))
   ;leaf node
   (if (= nil (:parent current-node)) ;it's a leaf and a root
     (* -1 (get-state-score player state))
     (recur (get-other-player player)

              (get-parent-with-max current-node

              (* -1 (get-state-score player state))) game-state-fn))

           ;return from child to the parent
    (if (empty? (:children current-node))
      (recur (get-other-player player)

               (get-parent-with-max current-node

               (* -1 (:alpha current-node))) game-state-fn)
      ;create a new child board and take the child out of the parent's list of children (a.k.a. marking it as visited)
      (let [new-board (assoc-in (:board current-node)

               (first (:children current-node)) player)

                 old-board (update-in current-node [:children] rest)]
        (recur (get-other-player player)

                 (BoardTree. new-board old-board

                 (open-indecies new-board) 

                 Float/NEGATIVE_INFINITY Float/POSITIVE_INFINITY) game-state-fn)                 ))))))

As you can see, this method is slightly more verbose. If this is a little overwhelming, here's the pseudocode version,

tail (current_node) ->
  if current_node.parent is null and all current_node.children are visited:
 return best value of my children
  
  if current_node is leaf:
    if current_node.parent is null:
      return -1 * score
    else:
      current_node.parent.best_score = max(-1 * current_node.best_score, current_node.parent.best_score)
      tail(current_node.parent)
  else:
    if all current_node.children are visited:
      current_node.parent.best_score = max(-1 * current_node.best_score, current_node.parent.best_score)
      tail(current_node.parent)
    else:
      tail(current_node.children.first)

Unfortunately, during my testing I discovered that the tail recursive version is significantly slower. However, it will run on a 4x4 board with out crashing.

Snippets

While writing my first project in Clojure, Tic Tac Toe, I noticed that there were a few lines of code that I was using over and over again. One of these lines was,

(apply (partial conj coll) x)

This line of code simply appends the items in vector x to vector coll. So if vector coll is [1 1] and x is [2 2], the result would be [1 1 2 2]. This was especially useful to me while writing Tic Tac Toe because I used vectors to implement the board. So, my natural inclination was to abstract this line of code into a utility function. Great, now I have a utility function that combines two vectors. However, now that I am finished with the Tic Tac Toe project, I have a problem. Let's say I start a new project in Clojure and I need to use that utility function. I have to open up my Tic Tac Toe project and search for that utility function. This isn't so bad, but if I hadn't put the line into a utility function, it would probably be lost in a sea of parentheses. I believe this is a problem a lot of developers run into. You write some brilliant one-liner that is extremely useful, but it gets buried as a private function in an obscure class. If you ever need to use it again, you have to dig for a while. One has to wonder if there a better way. Here's my suggestion: a personal repository of snippets. I'll define a snippet as a small function that preferably can function on it's own (no outside dependencies). If you keep your snippets repository small, modular and organized, you can simply copy and paste the snippets whenever you need them. No more searching through private functions in obscure classes. But wait, I've left out the best part, testing!! If you abstract these small snippets into their own project, they can also have their own suit of tests. So, not only do you have a central place to store all of your genius one-liners, but they are tested as well, so now you can be confident in your copy and pasting. To put this to practice, I've created a project of Clojure snippets. I added the vector combine function above and added three tests to cover it. Great! Now I know that I have a function to combine two vectors whenever I need it. And what's better, I know exactly where to find it! Beware, I am not suggesting that you create a utility library for you or your company to reference in all your projects. A lot of the usefulness of the snippet repository is that you know exactly what is there and exactly where to find it. If you create a massive library across your entire company, no one will know what is in there and all usefulness is lost. I do not believe the snippet library is very scalable, it should probably be kept personal.