.

WTF is F-Bounded Polymorphism

Here's an example of where I read random articles just because the title is very catchy: F-Bounded Polymorphism for Object-Oriented Programming by Peter Canning, William Cook, Walter Hill, Walter Olthoff and John Mitchell.  Polymorphism is already confusing enough.  Just look at the Wikipedia entry on type polymorphism: "this article may be confusing or unclear to readers".

There's parametric polymorphism, let-polymorphism, impredicative polymorphism, ad-hoc polymorphism, intensional polymorphism and subtype polymorphism.  So WTF is F-bounded polymorphism then.  If there's no Wikipedia entry does it really exist?  Despite no mention in Wikipedia F-bounded polymorphism is pretty important and I'm using it everyday without knowing it.

Lets start with "bounded quantification".  With bounded quantification you can do something like this

Moveable {
 Moveable move(int x, int y)
}

Moveable moveMeOneInch(Moveable m) {...}

The method moveMeOneInch takes in some a Moveable, moves it one inch, and returns a Moveable.  It is polymorphic and will work on Cars, Trains, Points--anything that's Moveable.  All good, except we'll have to do some unsafe type casting.

Car c = ...
Car movedCar = (Car) moveMeOneInch(c);

But with Java 5 we can do something like this

<T extends Moveable> T moveMeOneInch(T m) {...}

Car c = ...
Airplane p = ...

Car movedCar = moveMeOneInch(c);
Airplane movedAirplane = moveMeOneInch(p);

and get the type safety we want, because "run time is a little late to find out whether you have a landing gear".  What we've done is created an "F-bound".

F-Moveable[t] = { move : int, int -> t }
F-Moveable[Car] = { move : int, int -> Car }
F-Moveable[Airplane] = { move : int, int -> Airplane }

Note the type appears on both sides. 

Here's a real world example.  The Collections utility class has a max method that takes in a Collection of Comparables and return the max of the collection.

public static <T extends Object & Comparable<? super T>> 
 T max(Collection<? extends T> coll) {...}

//Integer implements Comparable<Integer>
Collection<Integer> ints = ...
Integer i = Collections.max(ints);

Here we bound the type of the collection and the type is part of the bound for Comparable.  A collection of integers, and integers are comparable to integers.

That's F-bounded polymorphism in a nutshell.  Now you can say, "yea, I like Java, it supports F-bounded polymorphism."

Scala, FUD and the PCP Drug

When something new comes along the established players often spread fear, uncertainty and doubt (FUD) in an attempt to remain dominant.  But what's the opposite of FUD?  I propose praise, certainty and perfection: PCP.  Every now and then something new comes along that so enamors early adopters they uncontrollably praise its merits, the certainty of its value and its utter perfection.  Like a drug, PCP is dangerous unless carefully supervised.

Take Scala, for example. There's so much PCP surround Scala I'm about to overdose.  DZone's top link for the last two days has been a blog titled Scala is my next choice.  It's a nice entry highlighting some of Scala's strengths but the author is too generous with some of the claims.  A quick read might well lead a programmer to conclude Scala will solve all of our programming problems.  Lets look at two claims.

Efficient

Scala is an efficient language, actually due to the latest benchmarks Scala is almost as fast as Java. The JVM implementation of Scala compiles down to bytecode, but during so, the code passes through optimization phaze. An optimization example is the tail recursion optimization, to help you stick to the functional paradigm without sacrificing the performance.

While the Scala compiler (which I praised here) does do tail recursion optimization it's very limited, a performance hack if you will.  The tail call has to be within a final method or local function (and has to be to itself, hence the recursive qualifier).  Rich Dougherty has a nice post on tail calls in Scala that goes into this further.  The fundamental issue is that unlike Scheme or Haskell there's no guarantee of tail calls in Scala because the JVM doesn't support tail calls. See John Rose's post here for further information on tail call support in the JVM and the difference between soft tail calls (the Scala hack) and hard tail calls. Bottom line: recursion in Scala will affect your performance.

Concurrency

Thus Scala suggests another concurrency model called Actors, where an actor sends and receives asynchronous messages in it’s inbox instead of sharing data. This is called: shared nothing model. Once you stop thinking about shared data, you relief yourself from the headache of thinking of code synchronization and deadlocks problems.

I'm not going to argue which concurrency model is better, but it's incorrect to say that you won't get deadlocks using Actors. See James Iry's post on deadlocks in Erlang, or see Charles Leiserson's discussion of deadlocks with MPI, another message based model used by the super computer guys.  Anytime there's a cycle in the dependencies you can get deadlocks, including when you're just passing messages around. Bottom line: Scala won't stop your deadlock problems.

I don't have anything against Scala but lets not make Scala out to be this magically language that will solve all our performance, scalability and concurrency problems.

Everything is a Function

I picked up Real World Haskell last week when Gilad Bracha warned me that I might become unemployable if I don't brush up on my functional programming skills.  I found his comment amusing because I have Lisp on my resume and have always wondered if anybody cared that I know Lisp.  Know is an exaggeration;  all I remember is cons, car, cdr and thinking why the f*** are there so many parentheses.  Yet here I am, a decade older, reading up on lambda-calculus and folding to remain marketable.

One thing that might confuse the imperative programmer when reading Haskell code for the first time is the unfamiliar function definitions.  In Java if you have an "add" method that adds two ints and returns an int you might write it as

add (int, int) : int

or

int add (int a, int b)

or

(int, int) -> int

In any case it's clear that add takes two ints and returns an int.  But in Haskell your add function will be

add :: Int -> Int -> Int

You might guess that the first int is the first argument, the second int is the second argument, and the final int the return type.  But not really.  In Haskell all functions are single argument functions.  Add is a function that takes an int, returns a function that takes an int, returns a function that evaluates to an int.  Here's an example with the map function. 

map abs [-1,-3,4,-12] 
[1,3,4,12]

:type map
map :: (a -> b) -> [a] -> [b]

It appears that the map function takes two arguments, a mapping function (in this case the abs function that returns the absolute value of a number) and a list, and applies the mapping function to each element of the list.  But as you can see in the type definition map is a function that takes a mapping function (a->b), returns a function that takes a list [a], returns a function that evaluates to a list [b]. 

This is because the lambda-calculus which Haskell is based upon doesn't have built-in support for multi-argument functions.  It'd be pretty easy to support multi-argument functions according to Benjamin Pierce, but to confuse us imperative programmers they decided it would be easier and better to use higher-order functions (functions that accept and/or return functions). Instead of f = λ(x,y).s we have f = λx.λy.s.  Then we would just write f v w and do two "reductions" instead of writing something like f(v,w). 

Converting multi-argument functions into higher-order functions is called "currying" after Haskell Curry, for whom the Haskell language is named.  Haskell was a contemporary of Alonzo Church, who developed the lambda-calculus during the 1920s.  While at Princeton Church supervised the doctoral thesis of Alan Turing, the tape machine guy, who committed suicide in 1954 after being prosecuted for his homosexuality.   (That was for all the history buffs out there.)

Once you see it a few times the notation becomes "normal".  It's actually very elegant (among other things).  Everything is a single argument function.  I mean everything.  You know how Smalltalk guys are always saying everything is an object, well the lambda ultimate guys say everything is a function, including numbers like 23 and 17.  Maybe that's what Java's missing, a pithy tag line.  Java, where everything is a....

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.

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.

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.