A Year of Functional Programming

It's been a year since I first came across the concept of functional programming. To say it's changed my life, is an unjust understatement. This is a reflection on that journey.

Warning: I use the term FP quite loosely throughout this article.

Where I Was

I've been coding since the age of 8, so 26 years now. I started with BASIC & different types of assembly then moved on to C, C++, PHP and Perl (those were different times, maaaan ☮), Java, JavaScript, Ruby. That's the brief gist of it. Basically: a lot of time on the clock and absolutely no exposure to FP concepts or languages. I thought functional programming just meant recursive functions (ooooo big deal right?). I really came in blind.

How It Started: Scala

Last year, I wanted the speed and static checking (note: not “types”) of Java with the conciseness and flexibility of Ruby. I came across Scala, skimmed a little and was impressed. I bought a copy of Scala For The Impatient and just ate it for breakfast. I read the entire thing in 2 or 3 days, jotted down everything useful and then just started coding. It was awesome! At first I was just coding the same way I would Java with less than half the lines of code. It is a very efficient Java.

Exposure: Haskell

Lurking around the Scala community, I came across a joke. Someone said “Scala is a gateway drug to Haskell.” I found that amusing, although not for the reasons that the author intended. Haskell? Isn't that some toy university language? An experiment or something. Is it even still alive? Scala's awesome and so powerful, why would that lead to Haskell? How.... intriguing. Inexplicably it piqued my interest and really stuck with me. Later I decided to look it up and yes, it sure was alive and very active. I was shocked to discover that it compiles to machine code (binary) and is comparable in speed to C/C++. What?! It seems idiotic now but a year ago I thought it was some interpreted equation solver. I'm not alone in that ignorance, sadly; talking about it to some mates over lunch last year and a friend incredulously burst out laughing, “Haskell?” as if I was trying to tell him my dishwasher had an impressive static typing system. It saddens me to realise how in the dark I was, and how many people still are. Haskell is pretty frikken awesome! True to the gateway drug prophecy, I do now look to Haskell as an improvement to using Scala. But let's get back on track.

Exposure: Scalaz

I also started seeing contentious discussion of some library called Scalaz. Curious, I had a look at the code to see what people were on about, and didn't understand it at all. I'd see classes like Blah[F[_], A, B], methods with confusing names that take params like G[_], A → C, F[X → G[Y]], implementations like F.boo_(f(x))(g)(x), and I'd just think “What the hell is this? How is this useful?”. I was used to methods that did something pertaining to a goal in its domain. This Scalaz code was very alien to me and yet, very intriguing. Some obviously-smart person spent time making the alphabet soup permutations, why?

I've since discovered that answer to that question and I never could've imagined the amount of benefit it would yield. Instead of methods with domain-specific meaning, I now see functions for morphisms, in accordance with relevant laws. Simply put: changing the shape or content of types. No mention of any kind of problem-domain; applicable to all problem-domains! It's been surprising over the last year to discover just how applicable this is. This kind of abstraction is prolific, it's in your code right now, disguised, and intertwined with your business logic. Without knowledge of these kind of abstractions (and the awareness that a type-component level of abstraction is indeed possible) you are doomed to reinvent the wheel for all time and not even realise it. Identifying and using these abstractions, your code becomes more reusable, simple, readable, flexible, and testable. When you learn to recognise it, it's breathtaking.

FP: The Basics

Now that I'd been exposed to FP I started actively learning about it. At first I learned about referential transparency, purity and side-effects. I nodded agreement but had major reservations about the feasibility of adhering to such principals, and so at first I wasn't really sold on it. Or rather, I was hesitant. I may have been guilty of mumbling sentences involving the term “real-world”. Next came immutability. Now I'm a guy who used to use final religiously in Java, const on everything in C++ back in the day, and here FP is advocating for data immutability. Not just religiously advocating but providing real, elegant solutions to issues that you encounter using fully immutable data structures. Wow! So with immutability, composability, lenses it had its hooks in me.

Next came advocation for more expressive typing and (G)ADTs. That appealed in theory too and again I was hesitant about its feasibility. Once I experimentally applied it to some parts of my project, I was blown away by how well it worked. That became the gateway into thinking of code/types algebraically, which lead to...

FP: Maths

I loved maths back in school and always found it easy. Reading FP literature I started coming across lots of math and at first thought “great! I'm awesome at maths!” but then, trying to make sense of some FP math stuff, I'd find myself spending hours clicking link after link, realising that I wasn't getting it and, in many cases, still couldn't even make sense of the notation. It became daunting. Even depressing. Frequently demotivating.

The good news is that everything you need is out there; you just have to be prepared to learn more than you think you need. I persisted, I stopped viewing it as an annoying bridge and starting treating it as a fun subject on its own and, before long things made sense again. It opens new doors when you learn it.

Example: I had a browser tab (about co-Yoneda lemma) open for 3 months because I couldn't make sense of it. It took months (granted not everyday) of trying then confusion then tangents to understand background and whatever it was that threw me off. Once I learned that final piece of background info, I went from understanding only the first 5% to 100%. It was a great feeling.

Feeling Intimidated

Looking back there were times when I felt learning FP quite intimidating. When I'm in/around/reading conversations between experienced FP'ers quite often I've seriously felt like a moron. I started wondering if I gave my head a good slap, would a potato fall out. It can be intimidating when you're not used to it. But really, my advice to you, Reader, is that everyone's nice and happy to help when you're confused. I have a problem asking for help but I've seen everyone else do it and be received kindly... then I swoop in an absorb all the knowledge, hehe.

It's a mindset change. I wish I'd known this earlier as it would've saved me frustration and doubt, but you kind of need to unlearn what you think you know about coding, then go back to the basics. Imagine you've driven trains for decades, and spontaneously decide you want to be a pilot. No, you can't just read a plane manual in the morning and be in Tokyo in the afternoon. No, if you grab a beer with experienced pilots you won't be able to talk about aviation at their level. It's normal, right? Be patient, learn the basics, have fun, you'll get there.

On that note, I highly recommend Fuctional Programming in Scala, it's a phenomenal book. It helped me wade my way from total confusion to comfortable comprehension on a large number of FP topics with which I was struggling trying to learn from blogs.

Realisation: Abstractions

Recently I looked at some code I wrote 8 months ago and was shocked! I looked at one file written in “good OO-style”, lots of inheritance and code reuse, and just thought “this is just a monoid and a bunch of crap because I didn't realise this is a monoid” so I rewrote the entire thing to about a third of the code size and ended up with double the flexibility. Shortly after I saw another file and this time thought “these are all just endofunctors,” and lo and behold, rewrote it to about a third of the code size and the final product being both easier to use and more powerful.

I now see more abstractions than I used to. Amazingly, I'm also starting to see similar abstractions outside of code, like in UI design, in (software) requirements. It's brilliant! If you're not on-board but aspire to write “DRY” code, you will love this.

Realisation: Confidence. Types vs Tests

I require a degree of confidence in my code/system, that varies with the project. I do whatever must be done to achieve that. In Ruby, that often meant testing it from every angle imaginable, which cost me significant effort and negated the benefit of the language itself being concise. In Java too, I felt the need to test rigorously.

At first I was the same in Scala, but since learning more FP, I test way less and have more confidence. Why? The static type system. By combining lower-level abstractions, an expressive type system, efficient and immutable data structures, and the laws of parametricity, in most cases when something compiles, it works. Simple as that. There are hard proofs available to you, I'm not talking about fuzzy feelings here. I didn't have much respect for static types coming from Java because it's hard to get much mileage out of it (even in Java 8 – switch over enum needs a default block? Argh fuck off! Gee maybe maybe all interfaces should have a catch-all method too then. That really boiled my blood the other day. Sorry-), anyway: Java as a static typing system is like an abusive alcoholic as a parent. They may put food on the table and clothes your back, but that's a far cry from a good parent. (And you'll become damaged.) Scala on the other hand teaches you to trust again. Trust. Trust in the compiler. I've come to learn that when you trust the compiler and can express yourself appropriately, entire classes of problems go away, and with it the need for testing. It's joyous.

Sadly though, eventually you get to a point where Scala starts to struggle. It gets stupid, it can't work out what you mean, what you're saying, you have to gently hold its hand and coax it with explicit type declarations or tricks with type variance or rank-n types. Once you get to that level you start to feel like you've outgrown Scala and now need a big boy's compiler which can lead to habitual grumbling and regular reading about Haskell, Idris, Agda, Coq, et al.

However when you do need tests, you can write a single test for a bunch of functions using a single expression. How? Laws. Properties. Don't know what I mean? Pushing an item on to a stack should always increase its size by 1, the popping of which should reduce its size by 1 and return the item pushed, and return a stack equivalent to what you started with. Using libraries like ScalaCheck, turning that into a single expression like pop(push(start, item)) == (start, item) which is essentially all you need to write; ScalaCheck will generates test data for you.

Where Next?

What does the future hold for me? Well, I could never go back to dynamically-typed language again.

I will stick with Scala as I've invested a lot in it and it's still the best language I know well. I'd like to get more hands-on experience with Haskell; I don't know its trade-offs that well but its type system seems angelic. Got my eye on Idris, too.

Academia!

I used to get excited discovering new libraries. I'd always think “Great! I wonder what this will allow me to do.” Well now I feel that way about research & academic papers. They are the same thing except smarter, more lasting, more dependable, and they yield more flexibility. It's awesome and I've got decades of catching up to do! Over the next year I'll definitely spend a lot of time learning more FP and comp-sci theory. I'd also like to be able to understand most Haskell blogs I come across. They promise very intelligent constructs (which aren't specific to Haskell) but the typing usually gets a bit too dense; it'd be nice to be able to read those articles with ease.

Don't fall for the industry dogma that academia isn't applicable to the real-world. What a load of horseshit that lie is. It does apply to the real-world, it's here to help you achieve your goals, it will save you significant time and effort, even with the initial learning overhead considered. Don't say you don't have time to do things in half the time. If you're always busy and your business are super fast-paced agile scrum need-it-yesterday kinda people, well I know you don't have time, but what I'm offering is this: say you just need to get something out the door and can do it quickly and messily in 1000 lines in 6 hours with 10 bugs and 10 “abilities”, well if you spend a bit of your own time learning you could perform the same task in 400 lines in 4 hours with maybe 1 bug and 20 “abilities”. You've just saved 2 hours up-front, not to mention days of savings when adding new features, fixing bugs, etc. That's applicable to you, the “real-world” and the industry. I've spent years in the industry and not just as a coder and I wish I'd known about this stuff back then because it would've saved me so much time, effort and stress. There seems to be this odd disdain for academia throughout the industry. Reject it. It's an ignorant justification of laziness and short-sightedness. It's false. I encourage you to take the leap.

Problems with at_exit{}, exit(), and RSpec

I had an interesting problem the other day, working on a Ruby project of mine. I ran my tests: (note: I have "rak" aliased to "bundle exec rake")

rak test

which internally expands to the equivelent of:

rak test:spec test:int

which runs my specs and integration tests in that order.

Then an odd thing happened. My specs failed but then the integration tests ran anyway and scrolled the spec failure off the screen to report happy success. After some digging around I discovered the following:

• I'd had this test failure for a few commits without noticing.
• My CI builds on Travis CI were all reporting success (although the failure message was there in the build logs should one manually check.)
• Rake itself and RSpec's rake task were both fine.
• Running my tests directly with the rspec CLI, I was getting an exit code of 0 on both success and failure.

The Problem

RSpec was returning an error/exit/status code of 0 despite test failure. It should be non-zero so that external processes like Travis CI and Rake can determine that something's gone wrong and react accordingly.

I'm going to cut a tedious story down to the result here. After investigation I learned that rspec worked as expected again when I avoided this piece of code in my tests: What this piece of code does is:

1. create a temporary directory the first time it's called
2. reuse that temporary directory on subsequent calls
3. remove the directory at the end of the process's lifecycle

Why does that affect RSpec returning non-zero on failure? Because RSpec itself doesn't run immediately; it wants to wait until all of your specs have been loaded first. The way it accomplishes that is it registers itself to run via an at_exit block and then calls exit when it's finished with your specs. Still sounds like there's no problem right? Well this is what happens from that point on...

1. RSpec finishes running tests and calls exit with 0 for success or 1 for failure.
2. Accordingly, Ruby creates an instance of SystemExit and plonks it into the $! global variable.
3. Now that the process is shutting down, my at_exit in the snippet above starts running.
4. My cleanup code (correctly, validly and legally) runs Ruby's FileUtils.remove_entry_secure to remove the temporary directly created during tests. This isn't a problem in itself.
5. Here's the gotcha: FileUtils.remove_entry_secure removes the directory and sets $! to nil to indicate that no exception occurred.
6. Ruby ends the process and sets the exit code to the result of $!.status which was lost in the previous step.

The Solution

That was the problem. Now what's the solution?
Simple. Just take care to preserve the exit status in your at_exit so that it ends with what it started with. Here is a helper method that I created: (You can also view this file directly on Github in a utility library of mine.)

Then the solution becomes simply use at_exit_preserving_exit_status instead of at_exit in first snippet, and everything works again! Happy days!

TL;DR: Conclusion

Be careful that you don't corrupt the value of $! when using at_exit. If you're not careful (or don't use a handy, safe function like presented above), then you can corrupt the exit status of RSpec in particular, and other libraries that work in a similar fashion.

Ruby Mutex Reentrancy

This morning I was making some Ruby code of mine thread-safe which is always fun. (I'm serious btw. I frikking love multithreaded programming!) In doing so I came across something that I found a bit surprising.

Consider the following snippet: Think it will work? Let's try...

<internal:prelude>:8:in `lock': deadlock; recursive locking (ThreadError)
 from :8:in `synchronize'
 from reentrancy.rb:5:in `block in 
'
 from :10:in `synchronize'
 from reentrancy.rb:4:in `
'

Shocking!
Mutex is not reentrant. Wow. Ok. Let's try something else...

Let's change that Mutux into a Monitor and try again. Alrighty, let's put on fresh underwear and give it a whirl...

Monitor is reentrant.

Ah, the world makes sense again. If I had to code my own reentrancy I would've cried and hated Ruby a little bit. My love and faith in Ruby remains, yay!

Is There A Cost?

Nothing is free. Is there a performance penalty? Time for some benchmarks.

Here is a little benchmarking script that acquires and releases both a mutex and monitor 1 million times each: Benchmarking results:

                 user     system      total        real
Mutex        0.400000   0.000000   0.400000 (  0.406259)
Monitor      0.870000   0.010000   0.880000 (  0.864888)

Ouch, monitor takes over the double the time that mutex does. That's the trade-off.

What About JRuby

I'm curious, let's try JRuby too. We'll change bm to bmbm and fire it up.

Rehearsal ---------------------------------------------
Mutex       0.571000   0.000000   0.571000 (  0.539000)
Monitor     2.012000   0.000000   2.012000 (  2.012000)
------------------------------------ total: 2.583000sec

                user     system      total        real
Mutex       0.321000   0.000000   0.321000 (  0.321000)
Monitor     1.696000   0.000000   1.696000 (  1.696000)

Wow, Monitor is 5.3x slower when using JRuby!!! Hmmm, I suspect JIT just need more time to warmup. Here's a new benchmarking script with a big warmup: And the results:

> jruby --1.9 --fast reentrancy-benchmark-jruby.rb
Warmup #1/20
...
Warmup #20/20
                user     system      total        real
Mutex       0.357000   0.000000   0.357000 (  0.357000)
Monitor     0.768000   0.000000   0.768000 (  0.768000)

Ok, that's on-par with the MRI results. Mutex is fast off-the-bat with JRuby where as Monitor will be a lot slower at first then decrease to a little over double the speed of mutex.

Conclusion

Mutex: No reentrancy. Fast, less than half the speed of Monitor.
Monitor: Reentrancy. Slow, little over twice as slow as Mutex.

Ruby JSON Libraries

Over the last 5 years or so I'd been away from the world of Ruby. I still used Ruby at work and home for various little things [cos it's awesome!] but that's quite different to living in it, especially seeing its community is one of the most fast-paced I've seen. So when I came back recently and I needed a JSON library, I went searching and found (what felt like) 100 different JSON libraries...

Long story short, I benchmarked them. Feel free to skip to the end of this post to just get the conclusion and be on your way.

What Was Used

NAME	VERSION	BUILD
MRI Ruby	1.9.3p125	ruby 1.9.3p125 (2012-02-16 revision 34643) [x86_64-linux]
JRuby	1.6.7	jruby 1.6.7 (ruby-1.9.2-p312) (2012-02-22 3e82bc8) (OpenJDK 64-Bit Server VM 1.7.0_03-icedtea) [linux-amd64-java]
"	1.7.0.dev	jruby 1.7.0.dev (ruby-1.9.3-p139) (2012-04-15 b4b38d4) (Java HotSpot(TM) 64-Bit Server VM 1.7.0_03) [linux-amd64-java]
OpenJDK	1.7.0_03	OpenJDK Runtime Environment (IcedTea7 2.1) (ArchLinux build 7.b147_2.1-3-x86_64) OpenJDK 64-Bit Server VM (build 22.0-b10, mixed mode)
Oracle Java	1.7.0_03	java version "1.7.0_03" Java(TM) SE Runtime Environment (build 1.7.0_03-b04) Java HotSpot(TM) 64-Bit Server VM (build 22.1-b02, mixed mode)
MultiJson	1.3.2	c73bc389fa1b0b1c0b8225ea77ff3e2dee312304

The following JSON libraries were tested:

NAME	GEM NAME	VERSION
Optimized JSON (Oj)	oj	1.2.4
YAJL	yajl-ruby	1.1.0
JSON JRuby	json-jruby	1.5.0
JSON Pure	json_pure	1.6.6
JSON gem	json	1.6.6
OkJson	okjson	Version packaged with MultiJson 1.3.2

I created a little app to benchmark each library that performs two functions 100,000 times and records the time taken. Said two functions are:

1. [Writing] Generates JSON for Ruby data structure:

   {
     a: 2,
     b: (1..50).to_a, # i.e. an array of 1,2,3,4,5,6, ... ,49,50
     c: %w[asf xcvb sdfg sdf gfsd],
     d: {
       omg: 'hedfasgdsfg',
       wewr: 34,
       sfgjbsdf: %w[sdfg sdfgsdfgnj klj kj hkuih ui hu kjb bkj b sdfg],
     },
   }

2. [Reading] Parses this JSON:

   {"a":2, "b":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50], "c":["asf","xcvb","sdfg","sdf","gfsd"], "d":{"omg":"hedfasgdsfg", "wewr":34, "sfgjbsdf":["sdfg","sdfgsdfgnj","klj","kj","hkuih","ui","hu","kjb","bkj","b","sdfg"]}}

If you're interested you can grab the code here: https://github.com/japgolly/WebServerBenchmark/tree/json_libraries
You're free to read it, play with it, hack it, print it and eat it, make love to it; It's all good.

Finally, these tests were performed on a Q9550 with 8GB RAM running Arch Linux 64-bit.

➤ uname -a
Linux golly-desktop 3.3.2-1-ARCH #1 SMP PREEMPT Sat Apr 14 09:48:37 CEST 2012 x86_64 Intel(R) Core(TM)2 Quad CPU Q9550 @ 2.83GHz GenuineIntel GNU/Linux

Results: First Cut

The numeric axis represents number of seconds taken to perform 100,000 operations.
Less is better.

	Linear Graph	Logarithmic Graph
MRI
JRuby (on Oracle Java)

Wow. Two things are immediately obvious:

1. OkJson is extremely slow on both Ruby implementations. Whatever its design goals, performance isn't one of them.
2. JRuby runs YAJL like my grandmother runs marathons.

I really thought JRuby would perform better. Maybe 1.7 will be better. I know the JRuby team expect significant performance gains; I wonder if they've implemented them yet... Let's try using the latest dev version of JRuby 1.7.0!

Also I think I'll try using JRuby 1.6.7 with the OpenJDK implementation of Java and see if that gives better results.

Results: Lots of JRuby Love

[Update 2012-04-23: New JRuby library discovered, see conclusion.]

Alrighty, done. Here are the results: (note: using a logarithmic scale here again) And the same thing expressed differently:

Jeez, it's not getting much better for JRuby...

Ok, enough of this. Let's get rid of the council-working options [hey, Aussies get that!] and just look at the feasible ones.

Results: The Finalists

The numeric axis represents number of seconds taken to perform 100,000 operations.
Less is better.

Conclusion

If you use MRI, use Oj unless you generate more JSON than you parse, in which case use YAJL.

If you use JRuby, you've only really got one choice: json-jruby. You can expect roughly the same performance with OpenJDK, Oracle Java and the latest dev build of JRuby.

Update 2012-04-23: jrjackson for JRuby is approx 4x faster than json-jruby and faster than MRI. If you use JRuby, you want this!!