OOP Setters Can be Used to Emulate Partial Application

Recently I was asked an awesome question that went something like

How would you do something like high-order functions and partial application in object-oriented programming?

For high-order function my mind immediately jumped to Guava's Function Interface. I said, "hmmmm, let's see, could have some method (maybe called partiallyApply) that took an argument and returned another Function." In retrospect, this may have been overly complex, and a much simpler implementation of Function may work just as well in this case: fluent setters.

Let's look at a contrived, dead-horse-esque example. A partial function that does addition on two arguments.

In Haskell, if I wanted to build such a function, and partially apply it to, let's say 5, I might do the following

add5 = (+) 5

add5 10 -- is 15

In Clojure, this might look like

(def add-5 (partial + 5))

(add-5 10) ; is 15

So, how would I do this using setters? Simple! Here's some Ruby code

class Adder
  def value(first)
    @first = first
    self
  end

  def to(second)
    @second = second
    self
  end

  def add
    @first + @second
  end
end

adder_of_5 = Adder.new.value(5)

adder_of_5.to(10).add # is 15

This code (obviously) has a lot more ceremony wrapped around it, but it does achieve some of the same benefits as partial application (e.g. laziness, partial parameter fulfillment). The point is, if this were Java code, I could easily implement Function and change add to invoke and have a partial function in an object-oriented system.

Baby Don't Fear the Code Review

Although I'm (at best) a novice in the software engineering industry, I've had the opportunity to provide and receive many code reviews. I don't know of many companies that allow their junior developers to perform code reviews, but I'm not complaining; reading others' code is an invaluable practice, in my opinion.

I wanted to share some of the dos and don'ts that are floating around in the back of my head, so here they are.

• Don't provide feedback without reason. "Because I said so" and "because that's how we do things" may have been acceptable reasons from our parents when we were 7, but they just don't stand up in any half-professional industry.
• Do ask questions as a reviewer. If something you are reviewing doesn't make sense to you, it probably won't make sense to others. You may very well be fumbling to understand some malformed abstraction, or trying to mentally unravel some code that will prove difficult to maintain. You are doing yourself and the coder a discredit by not making a sincere effort to understand what you are reviewing.
• Do ask question as the programmer whose code is being reviewed. The worst thing you can do is sheepishly accept feedback that you don't understand. Always dig deeper, try to find the reasons behind the reviewer's feedback, strive to uncover the Why.
• Do favor verbal, in-person reviews over reviews done in a tool (if possible). Actually walking through the code with a peer has the potential to make the process more of a discussion than a chat-room session. I have found, through my short experience, that in-person reviews also tend to be conductive to question asking, and help alleviate many of the communication and timing errors that are so prone to occur in tools.
• Don't take it personally -- you are not your code. Try to consider code reviews as learning experiences, as opportunities to gain insight from the feedback of your peers.
• Do get an informal review of your code review. I know that sounds strange, let me restate that differently. Ask the programmer whose code you are reviewing if your comments are clear, if you had comments that weren't really valuable, if some element of the process could be improved, etc.... Feedback need not be one-way, and there is generally room for improvement in any process. Seek improvement.

LISP Core in Less Than 100 Lines of Haskell

A couple of months ago, I built a LISP core engine in about 100 lines of Haskell code (of course, just for the fun of it). I thoroughly enjoyed the challenge, and with the help of techniques from the awesome Programming Languages MOOC I was taking, I felt ready to take it on. In conclusion, it was truly a fun project and I thought I'd share some things I learned along the way.

LISP's Core Primitives are Easily Implemented Recursively

In the simplest terms, the LISP core engine I built is simply a function that operates, with a specific environment (variable bindings) in mind, on the LISP syntax tree. Because of this I was able to implement primitives like label (aka define) simply with pattern matching and the cons (: in Haskell) operator!

To show how simple these primitives were to define, here's eq? (checks equality)

aux env (AList (Atom "eq?":a:b:_)) =
  if aux env a == aux env b then aTruthyValue else theFalseyValue

Note that aux is the name of the helper function called by the executor.

Haskell Code Can Be Very Elegant

There aren't many languages in which code as elegant as this can be written:

executeText env = execute env.parseMany.tokenize

In my opinion, it doesn't get much more straight forward than this. The dots may throw C-style programmers, but to a Haskell programmer they're pure gold.

Additionally refactoring in Haskell is extremely powerful. Consider the evolution of my bind function (takes names and values and adds them to an environment). It started as this:

bind [] [] env = env
bind (name:names) (value:values) env = bind names values ((name, value):env)

then was transformed to this:

bind names values = (++) $ zip names values

and ended up as:

bind names = (++) . zip names

In Haskell, it seems, there is a function for everything. Honestly, there's probably even one out there that can replace my bind function, I just haven't found it yet!

The Macro System is Pretty Cool

At the moment, the macro system in this LISP is pretty tight. Macros are written in Haskell code (I would like to eventually add support in the language) and are provided with (1) and "eval" which encapsulates the current environment and can run code and (2) a list of the arguments passed to the macro.

All registered macros are simply added to a list, and are thus loosely coupled to the actual core engine (but tightly coupled to the AST since they are essentially generating new portions of it).

Here's an example of how I defined if, in terms of the cond primitive:

structuralMacros = [(
  "if", \_ (p:a:b:_) -> AList [Atom "cond", p, a, Atom "1", b]),
  ...]

Parting Words

If you're interested in the full code, it's on github. Also the project has a REPL whose build step is at the bottom of "README.md."

Hash Table (Map) Built In Python

Lately, I've been studying up on my data structures and algorithms. I decided it would be fun to implement a HashMap (the map abstract data type). I decided to rely on Python's idiomatic __hash__ function, and use linear probing as the collision resolution mechanism. In the process of building this, I learned a few things and I would like to share them.

Deletion is the Hardest Part

Overall the data structure was not very difficult to build. Well, except for deletion. It's not as simple as shifting all elements back (overwriting the deleted). Instead, I had to flag the item as being "deleted". This wasn't that difficult, however, maintaining quick-access sizing on the data structure was complected by it.

In the end, I had to maintain two states: one that programmers who called __len__ would see and the actual count of stored elements (being actual plus deleted).

Linear Probing is Not as Hard

My "find index" method, boiled down to just

    def __locate_index(self, key):
        i = hash(key) % self.capacity()

        while self.__values[i] and self.__values[i][0] != key:
            i = (i + 1) % self.capacity()

        return i

Where each value is just a tuple where elements 0 and 1 are the key and its value, respectively.

Everything Else is Just Bookkeeping

In the end, the code wasn't too difficult. In the end, the class had a lot more state than I would've liked, however, "getting it right" wasn't that difficult. As always, I hope I'm not missing any edge cases with my tests.

As usual, the code is on github and I'm open to any suggestions or thoughts.

Just-For-Fun Clojure Spec DSL

TL; DR Clojure is hip for DSLs

Just for the fun of it, I've been playing around with Clojure, building a for-fun spec testing DSL (kind of like RSpec). So far, I must say, Clojure is working awesomely!

Since functions are the first-class citizen (and arguably the highest-class), it seemed natural to start off by defining ways to test them and simple values because, technically, if you can test a value, you can test the application of a function. However, testing return-value-only is not the spec testing way. Things should be descriptive.

So, here are a few examples of my spec testing DSL in action:

(describe 42
  (it > 31))

(describe +
  (when-applied-to 1 2 3 4
    (it = 10)))

The DSL is truly _that_ simple! Sure, these are simple tests, and yes, there's no nice documentation-esque output (yet). But, I just wanted to show how dead simple this DSL is at the moment.

To do the same operation in RSpec, I believe I would have to do something like:

describe 42 do
  subject { 42 }

  it { is_expected.to be > 42 }
end

describe '#sum' do
  subject { sum(*args) }

  context 'when applied to 1, 2, 3 and 4' do
    let(:args) { [1, 2, 3, 4] }

    it { is_expected.to be 10 }
  end
end

This isn't terrible, and I in absolutely no way claim this little DSL is as powerful as RSpec, but it is pretty neat, eh? Also, not to mention, the DSL is about 21 lines at this moment (whoot whoot for macros!)

Pure TDD: A JavaScript Example

The other day I took some time to practice TDD, in JavaScript. I chose a problem at random from cyber-dojo and worked my way through, as by-the-book (following Red->Green->Refactor) as I could.

Not only did I finish this exercise, but I committed each step of the process to github.

So, if you're interested in reading through an example as-pure-as-I-can-at-the-moment-TDD-session, start with this commit (I'd recommend a tool like `gitg` so that you can step through the commits easily).

Some Notes

• The problem took me 12 Red->Green->Refactor cycles where I kept divided up a lot of the refactors into smaller steps (to keep the commits sensible).
• At some points the algorithm got kind of bloated, but overall patterns did emerge and were easy to generalize.

Quicksort in Ruby

Just wanted to open up some code for examination and/or (hopefully) ridicule. Here's a recent quicksort implementation in Ruby that I threw together:

class Array
  def quick_sort
    return self if count < 2

    pivot = pop
    parts = partition { |x| x < pivot }

    [*parts.first.quick_sort, pivot, *parts.last.quick_sort]
  end
end

It's pretty straight-forward and Ruby's expressiveness really does cause the code to closely resemble the algorithm.