.

One Big Ambient Monad

In my last two blogs on The von Neumann Bottleneck and The Problem with Immutability I was flushing out some thoughts on immutability, side effects and the difference between functional and imperative programming.  One thing I continue wrestling with is reconciling "no side effects" with the real world need for side effects.  We know that side effects lead to all sorts of problems but how can we eliminate side effects and still be left with useful programs?  The answer seems to lie in these magic monads that everyone keeps talking about.  So I spent some time skimming some papers on monads.  It seems as though I'm late to the party.  2007-2008 was the big year of the monads, when people were comparing them to burritos, elephants and sexual conquests.  But I'm always late to the party. 

After a day of casual reading I kind of get monads.  There's left unit, right unit, type constructor, a bind function and a couple of other goodies.  Still a bit abstract since when was the last time a Java programmer like myself ran across an explicit monad.  But something still felt off.  Philip Wadler writes in "Monads for functional programming"     

Monads provide a convenient framework for simulating effect found in other languages, such as global state, exception handling, out-put, or non-determinism

So aren't monads just a neat math trick for keeping things pure when things are in fact full of side effects?  That's like me saying my apartment is clean after I shove all my junk in a closet out of sight.  No, it's still dirty, you just can't see it anymore. 

Then I saw this video of Brian Beckman of Microsoft Research explaining the state monad and I think I'm one step closer to my "ah ha" moment.  Sequential programmers (Java, C, etc.) live in a huge ambient monad.  In this ambient monad side effects (updates) are allowed.  FP forces you to live in smaller monads.  Brian Beckman:

In fact there's nothing wrong about side effects at all, it just how disciplined, how precise are you going to be in your use of side effects.  If your programming language allows you to update any variable then you can never tell by looking at a variable whether it has been side effected. All Haskell does is discipline the side effects; so if you're doing side effects you have to do them in an explicitly written monad.  So now you can tell.  The stuff in the monad may have been side effected by whatever function was ahead of you and may be side effected by whatever function is behind you...It's precise in the text of the program. In a programming environment [like c# or vb] you are in am ambient monad so everything is updatable.

OK, this makes a lot more sense now.  Side effect is not this horrible, terrible, bad thing you absolutely cannot have (duh), you just need to be precise with it.  There's no way to be precise with it in Java or the imperative languages (enforce preciseness), but there is a way to be precise with it in functional languages.  Monads make this precision more convenient than passing the world around as was done in the past.

It should be noted that Beckman goes on to say that monads are not a panacea.  While reading up on Haskell one question in the back of my mind was how does Haskell do logging?  In Java I can do something like System.out.println("the value of x is " + x), but does this mean I have to use the IO monad now to do basic logging?  And Beckman points this out as a shortcoming, that to just do a printf you have to rewrite your functions to use monad.  I guess that's why there's some "unsafe" IO stuff you can do in Haskell, but as the name implies it's unsafe and the compiler can't guarantee things, as it can with monads.

The Problem with Immutability

There's been so many articles touting the benefits of functional programming lately.  Read just a few and one theme immediately emerges: no side effects is good.  With immutability there's no side effects, and with no side effects life becomes a lot easier.  Programs are easier to write, compose, debug and you get concurrency for "free".  While all this may be true, I feel there needs to be a little balance on the subject lest some people start to think functional programming is a silver bullet. 

We live in an imperative world where there's state and things are mutable.    This fact alone hints as to why functional programming cannot be the end all solution.  I/O is the classic example of where imperative operations are required.  For example, Haskell, a functional language, has these things called monads to do I/O.  Michael Scott writes in Programming Language Pragmatics,

Monads...acknowledge that the physical world is imperative, and that a language that needs to interact with the physical world in nontrivial ways must include imperative features.

I also recall a recent article with Joe Armstrong on state and mutability in Erlang that came to the same obvious conclusion: state and side effects are necessary, we just need to confine them so the rest of the program is not polluted.

Beyond this inherent issue of modeling the imperative physical world, there are just some things that are more imperative in nature, like counting and updating.  Destructive updating assignments may clog the von Neumann tube, but immutability creates a lot of garbage.  The need for destructive updates leads to the so-called trivial update problem.  How can we efficiently handle updates without creating new copies of the entire data structure.  In imperative languages it's very easy to do map.remove("myKey") but in a functional language you have to call a function passing in the current immutable map and getting back a new immutable map with one entry removed. 

There are two ways to deal with this.  One is to hope your compiler can optimize.  If the compiler can verify that the old map is never used after the function returns instead of creating a new copy of the map the compiler can just do the update imperatively, in-place.  Apparently there's this Sisal compiler that was shown to eliminate 99-100% of all copy operations.  And that was back in 1992.  Then again, that was very geared toward numerical calculations, so I'm not sure how things would translate to your run of the mill web app.

Another approach is to make your data structures smarter.  Smarter is probably the wrong word.  The key is to recognize the difference between imperative and functional data structures.  In imperative languages data structures are ephemeral, existing as-is, without a history.  Think of all the data structures we use everyday in Java: HashSet, HashMap, ArrayList.  They're all ephemeral.  Functional languages, because of immutability, have automatically persistent data structures.  Adding two elements to an initially empty list means you have three versions of the list: (), (e1), (e1 e2).  In the imperative world you just have a single list of three elements.

The problem is how to achieve persistence with O(1) additional space and O(1) slowdown.  Good news is really smart guys like Sleator, Tarjan and Okasaki have laid the foundation for efficient persistent data structures.  I know Rich Hickey's Clojure has persistent data structures base on Okasaki's work with some modifications to get around just the amortized guarantees.  A lot of the work around persistent data structures is around amortized running times, but Clojure has these "persistent vectors" so the time is guaranteed for certain data structures.  While much progress has been made in this area ephemeral data structures still have quite a head start.

As someone who's basically programmed in Java all his career I find all this very functional stuff very fascinating.  No doubt about functional programming's many pros, but it's also good to be aware of the cons.  I remember when Java faced much criticism because creating objects was expensive, but those criticism have largely subsided.  The Java language hasn't really changed, the bad programs we (I) write definitely haven't changed--it's just that the JVM has gotten a lot better at resource management.  So is functional programming at a similar stage, where all that's needed is improvements in compiler optimization and better functional data structures?  Or are we already there and I'm not just aware of it? 

The von Neumann Bottleneck

In high school English literature was my favourite class because it was the one class where I could be creative and develop new ideas, not just memorize equations.  But then it dawned on me that all my novel ideas and perspectives were just hackneyed, recycled ideas some guy from 1625 already wrote at length on.  This made me depress.  Today, more than a decade after high school, I find myself in the same predicament.  All these "new" things that seem so fascinating and exciting--well, they're just the same old ideas with a few refinements here and there.  It's pretty damn depressing.  Is there nothing truly original left in this world?

Take functional programming, for example.  It's all the rage these days.  I first wrote about it in January of 2007 in an entry titled "The Rise of Functional Programming".  Two and half years later FP is still going strong.  Just search DZone, Artima, InfoQ.  Countless articles and presentation of how imperative programming no longer meets the challenges of today's complex, concurrent world--and how functional programming can.  This gets me excited.  Have we reached a new stage of enlightenment, ready to move beyond for loops?  Are we at a tipping point?

Then I read this paper entitled "Can Programming Be Liberated from the von Neumann Style?  A Functional Style and Its Algebra of Programs" by John Backus, dated August 1978.  WTF, 1978.  In 1978 Backus was already telling us what so many experts are just telling us today, that mainstream programming languages suck.  It really is true, everything interesting in computer science was done between 1950-1980.

When I first saw the paper I asked myself, "who's this John Backus guy anyway?"  Well, he's the B in BNF and lead the invention of FORTRAN.  Hmm, OK, maybe I better read his paper, even if it's so old that all the PDFs on the web are bad scans from an ACM reprint.  Here's the elevator summary of the paper.

All the computers we work with are von Neumann computers, named after the Hungarian bad-ass mathematician John von Neumann.  There's a CPU, a store that holds both data and instruction (memory), and a connecting tube that can transmits a single word (think 16, 32, 64-bit) between the CPU and store.  As the great Senator Ted Stevens from Alaska astutely observed, tubes get clogged.  Backus called this tube the von Neumann bottleneck.  The adverse effect of the von Neumann model is "we have grown up with a style of programming that concerns itself with this word-at-a-time traffic through the bottleneck rather than with the larger conceptual units of our problems."

More than 30 years ago Backus was bitching about the things we're bitching about today.  And many of us are only bitching about it because of the "multi-core revolution" and our desire for immutablity.  It really is depressing, to think about it.  We're still writing a bunch of statements to manipulate memory via this clogged tube.  Half the time we're not even dealing with the data, we're just assigning variables that point to the data.  Tomorrow, when I come into work bright and early, I know I'll be excited to spend the day thinking of ways to best clog this von Neumann tube.

Scala's Dirty Little Scalability Secret

The other week, while shooting the shit about programming languages, a colleague mentioned the Twitter Ruby v. Scala debate, how Twitter had switched to Scala to meet their scaling needs. I wasn't following the ruckus that closely (no dog in the fight), but that sounded really odd, to say that one language is more scalable than the another.

For one, different people give different meanings to scalability so any discussion on scalability is bound to be problematic unless the participants all agree on a single definition. I personally like to use Amazon CTO Werner Vogel's description.  Haven't given much more thought to the debate since then; until yesterday, when an article on Twitter's evolving architecture appeared on InfoQ.   Most of the commotion stems from Twitters messaging queue problem:

The first implementation of the MQ was using Starling, written in Ruby, and did not scale well especially because Ruby’s GC which is not generational. That lead to MQ crashes because at some point the entire queue processing stopped for the GC to finish its job. A decision was made to port the MQ to Scala which is using the more mature JVM GC. The current MQ is only 1,200 lines and it runs on 3 servers.

Now I see the problem. We're muddling the language with the platform.  The sentence "a decision was made to port the MQ to Scala which is using the more mature JVM GC" should have read "a decision was made to move to the more mature JVM GC and Scala was chosen as the language".  The move to Scala was dictated by the performance and reliability of the Java VM and its garbage collector, not Scala the programming language.  Twitter is giving Scala the programming language too much credit.  I don't think they are doing this intentionally and they do always note the JVM aspect, but with slides like this

 

and focusing more on Scala the programming language than the VM platform it's not entirely surprising that some folks took issue and were confused by Scala's magical scaling abilities.  And the bit about only 1,200 lines of code omits their dependency on Apache Mina (plain old Java).  In essence Twitter moved to Java and the Java platform--it just so happens that Scala is a cool language that can co-exist on the platform.

And that's Scala's dirty little secret. Scala is only scalable in the sense that it runs on the reliable, high-performing JVM platform. This is why people say that Java the programming language is dead, but long live the virtual machine. Rich Hickey has a good, succinct take on languages and platforms in his rationale for Clojure.  In this sense Ruby is doing it the "old way" whereas languages like Clojure and Scala are doing it the "new way" by leveraging the platform.  If Scala only ran on the 1.4 JVM no one probably would even be talking about Scala, because while some of the language constructs are neat, lets face it, they are not revolutionary or entirely novel.  What's the saying, everything interesting in computer science was between 1950-1980. 

So, in addition to

• languages don't scale, architecture scale
• frameworks don't scale, solutions scale

I will add the following

• languages don't scale, platforms scale  

Incidentally, it should be noted that the creator of Scala refers to Scala's scalability not with respect to the platform but because Scala can be applied to a "wide range of programming tasks, from writing small scripts to building large systems." But since scalability means different things to different people we're bound for disconnect.

Universal Law of Software Usefulness

Read an interesting little paper by Neil J. Gunther the other day on benchmarking blunders.  It was interesting enough that I ended up buying his Guerrilla Capacity Planning book.  He's really into queuing theory (my favourite theory because Little's Law sounds funny) and has formulated a universal scalability model base on just two parameters, contention and coherency. 

Anyway, in the paper Gunther points out that maximum throughput X_max is bounded by the longest service time S_max.

 X_max  =  1 / S_max

Suddenly it hit me that something else I've been thinking about in recent days follows this similar inverse relationship: software component usefulness.  By component I simply mean some piece of software you write.  A logging component to log stuff; an authentication component to login users; etc.  A component can be a framework, a library, a module or just some related code. 

Each component in your application has a usefulness quantity that is inversely proportional to the time required to explain the component.

 U_max  =  1 / E_max

Where U_max  is the maximum usefulness of the component and E_max  is longest it will conceivably take to explain exactly what your component does to the dumbest person in your company.  If it takes 3 hours to explain what component C does, component C is not that useful.  U_max  is an upper bound, so a component requiring very little explanation time may turn out to be not that useful; but a component requiring lengthy explanations can never be that useful. 

That's my law, Tinou's Law.  I can't prove it mathematically, but from years of experience I am confident it true.  How often do you come across a piece of software and have no idea what the F*** it does.   So you ask the resident expert for an explanation, but after an hour or so you're still left unclear.  This is a clear indicator that the software component is pretty useless.

It should be noted that succint explanation times do not imply simplistic designs and ease of implementation.  Quite the contrary.  Often, very useful components that can be explained in 5-10 minutes takes months and years to develop.

Scala Gets Operator Overloading Wrong

If you like programming languages here's an interesting interview and discussion on language design and evolution featuring Erik Meijer, Gilad Bracha and Mads Torgersen.  I came across the video while googling for Mads Torgersen and his paper "The Expression Problem Revisited."  Gilad Bracha I recognized from the Java world and his thoughts on dependency injection with respect to his Newspeak language when I proclaimed that dependency injection is broken.  Not sure who Erik Meijer, but he looks really familiar.  Basically three really smart guys shooting the shit on languages.

One thing that stuck with me was language purity.  Erik mentioned that he really likes languages that are base on one fundamental concept, idea, notion.  A language where everything is a function (Haskell).  A language were everything is virtual (Newspeak).  A language where everything is a message send (Self). 

Java is far from pure and singular.  Most things are objects, but a few aren't.  You can do reflection, but not really.  Etc.  It then hit me why I've never really liked Java:  Java doesn't have a raison d'être.  Some people bash Java for its verbosity, or because it lack this feature or that feature, but those things don't really bother me as much as Java's conceptual elegance--lack thereof.  It is, by designed, a mix bag, meant for the hoi polloi.  And It's quite successful at what it does.  Don't get me wrong, I'm not a language zealot.  Java is great, with its VM, the available IDEs, the libraries, etc.  But it'll always be a Porsche, not a Ferrari (Porsche has always been designed with driveability in mind--the every man's sport car).

So I started thinking about Scala versus Newspeak/Smalltalk.  I think part of the reason Scala has been successful is it adopts a less than pure approach--a pragmatic approach.  Here's a trivial example (like all trivial examples it could just prove a trivial point).  Joey Gibson writes that Scala gets operator overloading right because 2 + 3 * 5  = 17 in Scala but 2 + 3 * 5 = 25 in Smalltalk (and likewise Newspeak).  But it's not that Scala gets it right, it's that Scala has chosen a pragmatic approach to operator precedence.  If Scala was pure then 2 + 3 * 5 would equal 25, because + and * are just ordinary methods on objects;  it'd be like saying method foo has higher precedence than method bar.  Smalltalk treats + and * equally because there's nothing special about them and the expression precedence is well-defined at a higher level: unary messages, then binary messages, then keywords.

Pragmatism "wins" in the "real" world.  That's why I don't expect Newspeak to gain wide adoption.  Worse is better?

The Expression Problem and Other Mysteries of Life

The "expression problem" or the "extensibility problem" is closely related to the Open-Closed Principle (OCP).  OCP states that software should be open for extension but closed to modification.  The expression problem observes that for the two fundamental dimensions found in programs, data types and operations, OCP is only achieved for one but not both.

Take, for example, an application involving vehicles.  There two kinds of vehicles, automobiles and trucks.  All vehicles can accelerate.  It is easy to extend our application to include space ships. 

The problem arises when we realize that vehicles should also be able to brake.  To add a brake operation we will need to modify vehicle, automobile and truck; violating OCP.

We can attempt to approach things from a more operational point of view.  Using something like the visitor pattern we can build our application to handle new operations without the need to modify existing source code.  Here we simply add a new brake operation visitor.

But now the problem becomes how do we add a new vehicle to our application without violating OCP.  It is not hard to add a truck vehicle but all of our existing operations must be aware of truck.

Mind you, we want to achieve everything discussed so far with type safety, and static type safety at that, because, as Bertrand Meyer would argue, run time is a little late to find out whether you have a landing gear.  Incidentally, if you're wondering what the mysteries of life title is all about, it from this Meyer's article.  I find his style amusing.

So how can we solve this expression problem and the goals of Open-Closed?  Don't ask me, I'm just a guy with a blog who likes to use OmniGraffle.  But from what I've been able to gather there's no easy, straightforward solution.  We can use generics and "F-bounds" but the code then looks like

interface FooBar<C extends FooBar<C>> extends Bar<C> {...}

Quick, anybody knows what this means, because I sure have a hard time keeping track of recursive types.  The Scala guys say you can solve the problem with abstract types, self types and mixins.  But there seems to be a lot of scaffolding involved--lots of redefinition.  Maybe it's not so bad if I really knew Scala beyond a cursory level.  Some people argue these techniques only work if you have the foresight--you have to parameterized your design from the beginning; you have to declare types as abstract types from the start; etc.  Multi-dispath/multi-methods can help, but I don't think any mainstream languages support those constructs. 

In conclusion, I have no idea what I'm talking about.  But I do find it interesting--and a bit sad--that such a seemingly fundamental problem, the expression problem, is pretty involved to solve.  You would think by now some brilliant language designer would have figured things out in a simple, elegant way.

Build Solutions, Not Frameworks (tm)

I've created a new category for my postings, "Rants and Raves," although it'll probably be more ranting than raving.  If you're looking for a little nugget of new knowledge, today's not the day, just pure ranting.  Nugget of new knowledge--wow, that's really bad writing.

There are two ways you can approach a software problem.

Approach No. 1

• Provide a solution to the problem.  If a similar problem arises in the future and a similar solution is required you then build out a general solution, through some common library, service or tool kit.  Some rework will be necessary.

Approach No. 2

• Build a framework because all solutions to all problems require a framework.  Let me be more precise: all solutions to all problems require at least one framework, possibly many.
• Now that there's a framework available, build the solution around the framework.
• Realize the solution doesn't exactly align with the framework, put in a bunch of workarounds.

Can you guess which approach I advocate?  I have a visceral reaction to mere mention of the word framework.  Even when a framework has proven itself to be good and useful I still prefer to not call it a framework because the word framework has so many bad connotations for me.  This is what Dave Thomas (not the Wendy's Dave Thomas, not the Pragmatic Programmer Dave Thomas, but the Smalltalk Dave Thomas) had to say about frameworks,

The best way to get software components is to stop people build software frameworks, where they let the raw material leak out with all the encapsulation violations and complexities of frameworks. One of the big mistakes we made, I believe, is encouraging people in building frameworks and shipping them. Frameworks are the best way to ship something that is unfinished and is not professionally polished.

  Before further ranting, lets define exactly what is a framework.  Frameworks are like Hollywood agents: "don't call us, we'll call you."  Frameworks are like girls you meet at bars: "give me your number, I'll call you sometimes."  They may or may not call you.  And if they do call you, they often call at the most inconvenient times, like when you're playing golf or watching SportsCenter.  Frameworks are like bad friends with tiny Smart cars.  They'll only give you a ride to the airport if it's convient for them and if your luggage fits in their non-existent trunk.  Contrast this with libraries.  Libraries are your dependable friends who'll pick you up on your schedule--just call them up, you have their number.

So lets get back to why approach no. 2 annoys the shit out of me.  Unless you are really smart or really lucky or the problem is just really trivial, trying to build a framework independent of a complete solution is like trying to predict the future--you will get it wrong more often than not (the will is bolded in case you missed it).  Solutions to problems evolve because requirements change or are not fully known.  Solutions to problems evolve because "little" details creep up and "little" constraints pop up.  Lets be honest now, how often do you scrap your code because you realize it just doesn't work as originally thought for whatever reason.  The evolution of solutions necessitates the evolution of frameworks, if the framework is to be useful. 

Unfortunately, frameworks don't like to evolve.  When a framework is "completed" the framework developers move on.  Evolution of a framework means a new framework--one without all the shortcomings of the first framework.  There might be minor updates to a framework, some new feature here and there, bug fixes, etc.; but they don't evolve in the same manner as solutions (and problems). 

How often do you see this.  There's a vague problem P1 with requirements r1, r2, r3.  A framework seems like it might come in handy because some other team also needs all of r2 and a little bit of r3 for a vague problem P2.  So you go out and build framework Q.  Meanwhile, the vague problem P1 becomes a little clearer and the requirements are now r1, r3 and r4--surprise, r2 was dropped.  So now what do you do?  Write a new framework W?  Can't do that, too much time and energy already invested in framework Q.  Try to evolve framework Q to meet r1, r3 and r4?  Can't really do that, r2 led you to a design that's largely incompatible with r4.  Well, the only option is to use framework Q as-is and hack together something for r4.  In the meantime, that other team, the one who also needed framework Q, well, they decided to do something else.

At this point you might think, wait a second, but don't we need a framework in place if we want to grow and scale and do all those things?  A particular solution to a particular problem seems awfully myopic.  A framework will allow us to meet the challenges of tomorrow without re-write/re-work/re-do.  Well, maybe, if you're an oracle.  But this is really a false dichotomy.  You can provide a robust, scalable, high-performing, extensible solution without frameworks.  It's really absurd to think a fancy, unproven framework is a prerequisite for a robust, scalable, high-performing, extensible solution.  Reminds me of Cal Henderson's proclamation: languages don't scale, architecture scales.  Let me add: frameworks don't scale, properly architected solutions scale.   

There's really only one way to develop good, useful frameworks--and that's not to develop them at all.  Provide a solution S1 to problem P1.  Make sure it works.  Provide a solution S2 to problem P2.  Make sure it works.  Refactor out common functionality into a library/service/tool kit.  Provide a solution S3 to problem P3 using the common library. Make sure it works.  Provide a solution S4 to problem P4 using the common service.  Make sure it works.  Try to further refactor out common functionality into version 2 of your library/service/tool kit.  After several successful solutions you might reach a point where you can't refactor anymore--you really do need a framework.  Then, and only then, do you even attempt to build out a framework.  By then, building out the framework should be fairly straightforward.  And lastly, call your framework something besides framework.

Feels great to get that off my chest.

Scalable Component Abstractions

If I was to summarize the evolution of my thoughts regarding dependency injection (DI)...

What is this dependency injection thing everybody is so excited about?

Oh, you mean decoupling interface and implementation--I like that. 

So what do these DI frameworks bring to the table?

Less boilerplate code--that's good.

But now I have a dependency on a framework--that kind of sucks.

Now I have all this hairy configuration in some XML file--that really sucks.

Annotations are pretty cool.  Still seems like be can do better.

Well, it's 2009 and maybe we have done better.  Consider how the Scala compiler is composed

While it's not called dependency injection per se the net result is the same: we're able to abstract the required services.  Tomorrow, if we wanted to log symbols we'd just implement a new LogSymbols and use mixin composition to get our new behavior.  Or we can stub/mock out Symbols during testing.  All without boilerplate code, messy configuration or clumsy bindings.  And everything is type-safe.  Pretty cool initial impression.  

You can read more about how Scala does it in "Scalable Component Abstractions."  Some of stuff is a bit foreign unless you have a strong functional background or really into type systems, but the compiler case study helps.

Tony Hoare on Broken Software Engineering

Apparently not too many people cared for my "Software Engineering is Broken" blog entry (maybe because I called everybody incompetent), but I don't think I'm totally off.  "Binging" around, I discovered the Association for Computing Machinery (ACM) looked into treating software engineering as a licensed engineering profession during the late 1990s, but concluded the field was too immature and that licensing would not give the same level of assurance as it did in other engineering fields.  ACM did qualify their position with the "at this time" clause, so hopefully they will address this issue again.

And I think they will, because it's not just me, some random guy with a blog, who thinks software engineering is broken.  Tony Hoare, legendary computer scientist who developed Quicksort, also thinks software engineering is broken.  He didn't exactly say it was broken and I don't want to put words into his mouth, but in a recent presentation on the "Science of Computing and the Engineering of Software" he dreams that one day,

• software will be the most reliable component of every product which contains it
• software engineering will be the most dependable of all engineering professions
  

I read that as: software engineering is broken, hopefully we can fix it one day.  Think about it for a second.  Today, when I buy an iPhone and it doesn't work my first inclination is crappy software, not defective hardware or manufacturing.  This both annoys and embarasses me as a person and software engineer professional.  When there's a problem with the iPhone I want consumers to think, "must be the bad manufacturing process Apple's Chinese partners are using"--not "buggy software."

I have 42 years on Hoare, so lets hope I get to see his dreams come true.