Monday, December 11, 2006

A General Theory of Programming Language Relativity

I don't usually write responses to other articles because, frankly, I think people spend too much time writing articles and too little time writing open source Erlang code that I can use without paying those do-gooder souls a dime for their efforts :) However, this one -- "No Silver Bullet" and Functional Programming -- piqued my curiosity because it discusses functional programming in a positive light and it mentions Erlang a bunch of times. Clearly, the author has gotten *something* right :)

I actually think the author did a pretty good job at explaining some of the benefits of functional programming. The main issue I have with the article is that, as past in other articles I've seen, it puts too much weight on conciseness as an indicator of expressiveness. Although conciseness often contributes to expressiveness, conciseness isn't the only measure of expressiveness. It it were, the commenter who wrote that Python generally has a similar conciseness multiplier to C++ as Haskell, debunking this shootout's conclusion that functional languages are "better" (i.e. more expressive), would have a strong argument.

Both the author and the commenter are making valid points, but I think they are overlooking an aspect of language expressiveness that's at least as important, if not more important, for code quality as conciseness: readability. The reason is pretty obvious: code communicates a solution to a problem not just to computers, but also to humans. If code written in a given language is unduly hard to understand, its conciseness doesn't hold much value because the pain of debugging and maintaining it outweights the ease of writing it. I think it's safe to say that most programmers would prefer to work with a 1500 line solution that's highly readable than a 1000 line solution that's hard to comprehend.

So how does this relate to the functional vs. imperative programming debate? Although functional languages (I'm talking primarily about Erlang because that's the functional language I know best) don't always trump OO/imperative ones in conciseness, their code does generally wins hands down in readability.

This is especially true when comparing functional languages to dynamically-typed OO languages, whose code for anything beyond short scripts is borderline unreadable IMO. Dynamically typed OO languages trade a large degree of readability for conciseness, and that's why Java code, as bloated as it often is, is often more readable than Python and Ruby code. The reason is in the fundamental design (flaw?) of OO languages: they encourage the programmer to bind functions to data (they name the child of this unhealthy marriage an 'object' to make us think this chimera models something from the "real world" :) ), and then use data objects to indirectly invoke bound (virtual) functions. If the type of an object isn't evident in the source code, it's difficult to figure out what functions are called when you read statements such as "obj.doSomething(param)". Due to the abundance of indirect function calls in OO code, dynamically typed OO languages require extra discipline by the programmer to carefully document the types of all variables in his/her code so that other people have a chance to understand what functions are being called.

In my relatively brief encounter with Python, I ran into a bunch of code containing seemingly innocent idioms such as the following (I apologize in advance for Python syntax errors):

respond(channel, msg):
if channel.isValid() and msg.body().equals("next"):
return channel.send("A2-B3")
return channel.send("bye")

Because I has no idea what the types of 'channel' and 'msg' are (the code was poorly documented), what such snippets did was a veritable mystery. After wallowing for hours at a time in such nebulae, trying arduously to trace back to the instantiation points of mysterious parameters, where I would hope to find the golden nuggets of information indicating what types their variables are holding, my frustration would reach such uncomfortable levels that I wouldn't know anymore whether to feel angry or deeply depressed.

When you read Erlang code -- even with scant documentation -- you don't normally have go through such troubles. Although Erlang is dynamically typed, Erlang code avoids such readability black holes because it doesn't throw so much type information out the window. In Erlang, the above snippet would be written as follows:

respond(Channel, Msg) ->
case Channel#chess_channel.is_valid && Msg#chess_msg.body == next of
true -> chess_channel:send(Channel, {move, a2, b3});
false -> chess_channel:send(Channel, bye)

The Erlang code is less concise, but it's also more readable. (It's also more optimized because it doesn't require the resolution of function pointers in runtime.) In a large code base, this added readability wins over conciseness because it can make difference between providing continuous service and begging your users to come back in a few more hours as you're chasing the mysterious bug that has taken your system offline. It also helps you develop new features faster because you can spend less time debugging and more time coding.

At this point, you may be thinking, "The extra type information in Erlang code has a cost because it sacrifices generality." If you need to write generic code, you can use Erlang's remote function invocation as follows:

respond(ChannelType, Channel, MsgType, Msg) ->
case ChannelType:is_valid(Channel) && MsgType:body(Msg) == "ok" of
true -> ChannelType:send(Channel, {move, a2, b3});
false -> ChannelType:send(Channel, bye)

This example is admittedly silly, but as you can see, Erlang lets you parameterize module names (and function names) in generic code. This capability is often very useful. Even with remote invocation, the vast majority of Erlang code I've read contains enough type information to be much more readable than imperative/OO code.

In addition to the general absence of mystery functions (for a counter-example, check out ErlyDB :) ), Erlang, and other functional languages such as Haskell, have two language features that make them more readable than imperative languages: pattern-matching and immutability.

How do these features enhance readability and therefore expressiveness? Pattern-matching is easy -- just compare the following snippets:


foo({bar, [baz, boing], "18"}) -> ok;
foo(_) -> error.

Imperative, dynamic pseudo-language:

foo(arr) {
if (arr instanceof Array &&
arr.length == 3 &&
arr[0] == 'bar' &&
arr[1] instanceof List &&
arr[1].size() == 2 &&
arr[1].element(0) == 'baz' &&
arr[1].element(1) == 'boing') &&
arr[2] instanceof String &&
return 'ok';
return 'error';

Update (12/12/06): If you read Anders' comment, you'll see that code such as above can be written more succinctly in Python. Please take this example as an illustration of how Erlang pattern matching engine works rather than as a suggestion that there's no better way of writing such code in any imperative language.

I hope this example makes the benefits of pattern-matching obvious :) So, let's look single-assignment, which is another functional programming feature that I have learned to appreciate as an essential contributor to code quality. In Erlang, when you bind a value to a variable, this binding holds for the life of the variable. For instance, in Erlang, if you wrote code such as

foo() ->
X = 1,
X = 2.

the second expression would throw an error. If you're used to Erlang, the reason is quite natural: the first line states that X equals 1, and therefore the following line, stating that X equals 2, is wrong. To someone who isn't used to functional programming, the benefits of this behavior may not be obvious -- it may even seem like a burdensome restriction (I used to think so too). However, over time I learned that single-assignment often makes for drastically more readable code. For example, consider this snippet in an imperative/OO/dynamic language:

out(name, paradigm) {
var l = new Language(name, paradigm);

// much code below
l = bar(l);

// much code below
return l.getName() + "/" + l.getParadigm();

Now answer the following question: what does 'out("Ruby", "imperative")' return? Clearly, you have no way of knowing. In fact, even reading the all the code for the 'foo' function won't help you much -- you'd have to read the code for 'bar' (and any other function that take 'l' as a parameter) in order to have a better clue. Sadly, all that reading still wouldn't guarantee anything if the value of 'l' changes during execution based on some IO input. And that's not the end of it: to make things worse, your life would be even much more miserable if the author of the code decided to venture into the dangerous terrain of multi-threaded programming. If 'l' is shared between different threads, your code comprehension efforts would be that much closer to hopeless.

If this code were written in Erlang, the answer would be simple: the function 'foo' returns a string of value "Ruby/imperative". In small code snippets, such as the ones used in most language comparisons, the readability benefits of single-assignment may not be obvious. However, in a large-scale production systems with high availability requirements written by large teams of developers, the ability to answer questions about unfamiliar code segments is essential for both readability and (automated and non-automated) debugging. Erlang was designed to build such systems, so it makes sense that Erlang shuns mutable variables. (I imagine Ericsson would be in a rather uncomfortable position if a portion of England's phone network went offline because some programmer thought to himself, "the variable 'l' holds an object of type 'Language'!" :) )

So where does all this lead us? Is there a precise way of measuring language expressiveness that takes into account both conciseness and readability? Well, after thinking about this stuff for a while, I arrived at an elegant equation for arriving at an objective quantitative measure of a language's expressiveness. Without further ado, here is my equation for the General Theory of Programming Language Expressiveness:

E = C*R^2


E is expressiveness
C is conciseness
R is readability

Now I just need to figure out how to factor in the speed of light. If I succeed, it would undoubtedly pave the way for the Nobel :)

Well, I hope I was able to shed some light on why readability is at least as important as conciseness when evaluating language expressiveness, and also why code written in functional languages (primarily Erlang) enjoys greater readability -- and often, conciseness -- than code written in imperative/OO languages. Now consider this: even if imperative/OO languages were just as concise and readable as Erlang, Erlang code would nonetheless have a higher average quality. Sounds bizzare? Maybe, but it's true :) The reason is that no matter how good a language is, bugs always creep into non-trivial systems, and Erlang is the only language I know that has truly effective mechanisms for dealing with defects that do affect live systems. The idea behind Erlang's approach to fault-tolerance is actually quite simple: a crash in one process doesn't bring down the whole system, and furthermore it's detected by a supervising process that's configured with rules telling it what action to take (e.g. restart the process) when a crash does occur. When you've fixed that pesky bug that has been causing intermittent (yet non-catastrophic!) crashes, you can hot swap the new code into the live system without taking if offline. Due to Erlang's fault tolerant design, 1000 lines of Erlang code with 7 bugs are in a sense "better" than 1000 lines of Java doing exactly the same thing and containing an equal number of bugs. Unfortunately, comparisons that count only line numbers don't show this side of the story.

If none of this convinces you that functional languages are worth using, maybe this tip the paradigm balance in your mind: I've never met a programmer who's versed in both functional programming and OO/imperative programming and who prefers the latter.

But maybe I just need to get more friends :)


anders pearson said...

While I generally agree with your argument, I do have to point out that the OO/imperative code you've posted is badly written. For the respond() python function, it's generally considered very bad form in an OO language to take some objects, inspect them, and then perform some actions based on that. A better design would delegate more to the channel object (whatever it is):

def respond(channel,msg): return channel.respond(msg)

Python is also generally very transparent as long as you follow the style guides and don't do "from module import *" all over the place. So it's usually fairly trivial to figure out what type a variable is. I'm not finding this to be as true with Ruby though.

A better python equivalent to your:

foo({bar, [baz, boing], "18"}) -> ok;
foo(_) -> error.

Would be something like:

def foo(arr):
if arr == ['bar',['baz','boing'],"18"]:
return "ok"
return 'error'

No self respecting python programmer would write it like your example. But, yeah, pattern matching rocks.

anders pearson said...

Like I said, I generally agree with your overall point. I also find functional languages more readable on average. But I think it has more to do with the overall focus of the communities around them and how conducive the languages are to the approach of building up a domain specific vocabulary of functions and composing them. I don't think isolating specific syntax issues quite does it. Languages have to be considered as a whole along with their target audiences, target domains, community values, and the intentions of their designers.

Eg, no, Python doesn't have quite as powerful facilities for unpacking lists as Erlang does. At best you can unpack from lists or tuples where you know the length ( A, B, C = lst) or you can use slices ( [A,B] = lst[0:2]), but since Python isn't very list oriented, not having built-in syntax for pulling out the head and tail of a list doesn't feel like much of an omission. It just doesn't come up in everyday Python programming; it's much more common to work with an iterator or a generator or some kind of custom object instead.

(also, Python does have tuples, so the pattern matching example could have been ['bar',('baz','boing'),'18'] just as easily, which would be pretty equivalent to the Erlang data structure. I just wrote it quickly.)

Java's readability, I will not defend. Let someone else attempt that.

Yariv said...

Very good points, thanks. Indeed, different languages have different strengths, and whereas Erlang shines at list handling, Python may have a more concise syntax for working with hash tables or arrays. That's why I intentionally didn't focus very much on syntax issues beyond showing a simple example of how pattern matching works. I meant this example mostly to illustrate how the pattern-matching engine in Erlang works, as I wrote in the update I just made.

Maybe instead of saying that Java is readable, I should have been more specific in saying that in Java code, the types of variables are more evident, which often aids readability, especially when the reader is trying to figure out what functions are being called.

Thanks for the feedback!

Bryant Cutler said...

Pattern matching seems like an interesting approach, but it seems like it could get cumbersome really quickly - i.e. when the action to be performed depends on the values of several of the variables.

Also, regarding the one assignment per variable rule in functional languages: there may be some technical advantages to such an approach, but mutable variables are the most intuitive way I know to capture and describe changes in state, and computer programs at a basic level, are designed to manipulate the state of the computer - things like state and I/O shouldn't break your paradigm, or require workarounds like monads.

Yariv said...

If you need to match based on multiple variables, where some of them change on each rule and some don't, you can break your pattern matching code into nested 'case' statements to avoid repetition. If this doesn't work in the scenario you describe, can you show please me an example?

Regarding mutable variables, I haven't encountered in Erlang a scenario where it was difficult to express change in state. Do do so, you modify the old state variable and bind the result to a new variable. This usually happens in a process's main loop... or am I missing something?

Yariv said...

Also, I should add that Erlang doesn't have Haskell-style monads because the execution sequence of expressions is determined by their order in the code. In this sense, Erlang is less "pure" than Haskell.

Brian Olsen said...

Don't quote me, since I am not highly versed in Haskell. But, in Haskell there is the sequence_ function, which takes a list of operations and returns a monad, I think, based on the the last item in the list. It, in essence, mimicking an order of expressions. This approach is similar to the "do" construct. So, I was thinking, using a proof by vague association, that Erlang is pretty much doing the same thing as in Haskell, just without monads. :D

Anyway, in terms of Python, I think it can be readable. I never had much of a problem with it. However, good documentation does go far. The major problem, I think though, is managing complexity, which is made harder through artificially hard interfaces and concepts. I think in some cases, OOP makes things a little more complicated where it isn't needed.

My first impressions of Erlang are ones where I believe that all the little small things I am noticing add up to a sum total that makes Erlang a comfortable language to work with. There are little things that I have so far come across, that by virtue of its functional roots, makes Erlang a very interesting language. But, I don't think it is by virtue of the language itself, even though the language is able support certain ideas better than others, but in terms of how the language is *expressed*, in terms of the expectations of a programmer of a given language. This is where my interests lie.

For example, if I say we should make a system that is composed of simple functions with a flat structure, spread across separate modules, and use a system's functionality (like, higher-order functions) to perform code reuse and you say that we should use classes and objects and inheritance hierarchies and object interdependencies and the like, our opinion on the system construction is fundamentally different. However, the "opinion" I see in different languages could tend to take one approach over another. Erlang will take the former, and probably Python will take the latter. But that all depends, I guess.

So, I was thinking it becomes a matter of opinion, tuned to what we can handle. So far, I still think a simple procedural language (or functional) is better. Maybe this guy can make a better argument than I can:

For myself, I like small things, because, as a certified idiot, the smaller the concepts are, the better. Will Erlang fit this role? The only way we can find out is by working with it.

Regardless, programming is still hard. :)

Yariv said...

Thanks for the great comments. I agree with you that the sum of Erlang's little things (many of which go beyond its main "selling point" of concurrency and scalability) make it a very nice language to work with. This is something I've discovered after using it for a while, and that I have the feeling that many people who haven't used Erlang aren't aware of. In this article, I've attempted to explain what some of those aspects are, but as difficult as programming is, it's also difficult to explain what make a programming language "good" :) I also agree with your statement that OOP sometimes makes things a bit more complicated than they should be. The problem I encountered is that in large codebases, this complexity tends to grow in a greater than linear rate until it sometimes runs out of control. By my experience, languages that rely on function composition rather than object/class composition are more manageable in large doses because, partly for the reasons I mentioned in the article, my brain has an easier time disentangling the complexity I see in front of me when it's written in a functional style.

Finally, it appears that my perception of Python is worse than that of many people who are smarter than I, so maybe I need to give it a closer look :)

keithb said...

Yariv, You say:

" Due to the abundance of indirect function calls in OO code, dynamically typed OO languages require extra discipline by the programmer to carefully document the types of all variables in his/her code so that other people have a chance to understand what functions are being called."

Actually, not. What's strongly *reccommended* is that programmers state a contract that objects of a certain type (not class) will fulfill, after which this:

"If the type of an object isn’t evident in the source code, it’s difficult to figure out what functions are called when you read statements such as “obj.doSomething(param)”. "

ceases to be an issue, because I (as a dynamic OO programmer) simply *don't care* what exact function will be called at runtime, so long as it fulfils the contract (or some other contract compatible with it). Late binding is the key feature of dynamic OO languages and it allows a remarkable degree of flexibility--but with the caveat that you cannot in general look at a method's text and work out the full ramifications of its execution. Part of the skill of the OO programmer is to be comfortable with that.

Automated unit tests, especially in the "dynamic" school are an excellent way to do this.

In some circumstances I would care exeactly what is going to happen at runtime: a dynamically typed OO language wouldn't be a great choice for hard real-time, for instance. In others, I don't.

It also helps that I *never* have to figure out code like "obj.doSomething(param)", which is utterly opaque. Instead, I have to figure out code like "door.unlockWith(aKey)" and I have the happy advantage of not needing to care that there are many kinds of door and key, and many kinds of object that can in order to understand that the programmers intention in *this* method is to unlock a door with a key. Only in a debugging scenario (the damn door is stuck!) do I need to dig into exactly what methods are being called.

Now, there's a problem with a lot of current OO programming that 1) the code inside the methods is written in something that looks a lot like C and (partly therefore) 2) methods tend to do a lot of set/get style mutation. This is bad and wrong. If you look at good OO code (Smalltalk images are an easy source of this) you won't see a lot of that.

By the way, I am a programmer who's versed in both functional programming and OO/imperative programming and indeed I don't prefer the latter. But then, I write my OO code in a functional style, not an imperative one. And for that matter I write my functional programs (usually in Scheme) in a object-oriented style. I like the two approaches about equally overall but differently for different tasks.

Yariv said...

Thanks for the insightful comment!

Maybe I am generalizing about the OO paradigm too much based on my encounters with pooly-written OO code. I still think that, conceptually, it is cleaner to pass into a function functions that do things rather than objects that obey contracts. The reason is that contract-based programming adds another layer of complexity to programming: how do you formulate your contracts? For example, is a door something you can open and close, or is it also something that you can fix when its broken and also something you can paint when it's dirty? Some functions take a "door" parameter may only need to open and/or close it, yet other functions may need to paint it and open it, but not close it or fix it. For generality, your best choice is to add all these functions to the contract. But this doesn't scale very well, because as your "door" contract grows, it becomes harder for other people to work with it because they need to understand the entire contract even when they only care about opening things. In some cases, inheritance may help you specialize your contracts to avoid too much generality, but then you would have to deal with the other complexities that inheritance introduces.

In a functional programming style, if you had a function that needed to open something, it would take as a parameter a closure that performs the action on the "object," e.g.

do_something(OpenFun) -> OpenFun(), ...

and you would call is as

do_something(fun() -> door:open(MyDoor) end).

I think this style is nicer than contract-based programming because the parameter to 'do_something' doesn't carry any excess contractual baggage.

In dynamic OO languages, you're actually better off than in static OO languages, because your interfaces aren't rigid, so you can write code such as


and it doesn't matter what the full contract is. In this scenario, the extra flexibility of dynamic typing gives Python a solid win over Java :)

keithb said...

I think you're generalizing about the OO paradigm too much based on your encounters with pooly-written OO code written in inadequate languages.

I don't read Erlang well enough to follow your example exactly, but that "door:open" looks suspiciously like you are explicitly, manually, early binding the open function you're passing in, because of a belief about the type of the value that MyDoor will be bound to. If so, it's not clear to me how this is superior to having the value that MyDoor is bound to know about its own open function, automatically, at runtime. So you trade a bit more generailty on place for having to be much more specific in another.

As far as scaling contracts goes, I think again its' experience with inadequeate examples of OO that's misleading you. Contracts are connected with types, and a language that conflates type with class is broken. In your example "openable" would be a contract but there doens't need to be a Openable class that emobodies it.

This approach really sings with prototype-based, dynamically typed (and otherwise dynamic) OO languages with good support for composition. The name for this is Self. I've this feeling that OO works best when fully dynamic and functional programming works best when fully (lazily) static, which would kind-of resonate with the idea that the two models of programming are somehow dual.

Lisp then wins by having the least bad of all worlds.

One last point: I'm interested in the complaint that someone reading the code would have to understand the entire contract even when they only care about opening things. I've found over the years that its a common syndrome amongst computer science graduates that they feel that they can't claim to understand any part of X untill they understand all parts of X. This is an approahc that I find deeply puzzling (not being a CS grad myself)

Yariv said...

I'm not saying that it's impossible to understand a part of X unless you understand all of X, but that grouping together too many concepts into a single contract can be burdensome to the users of your APIs when most of the contract is extraneous to their problems. That's not to say that contracts aren't useful -- in fact, Erlang uses them frequently when calling functions using dynamic module names (these are similar to "objects" with no instance variables) -- but that it's often nicer to use higher-order functions in order to create little "min-contracts" on the fly rather than using dynamic function invocation via objects, which may have much excess baggage that the users of your APIs don't need. (I studied math and economics in addition to CS, so I hope my thinking isn't entirely brainwashed by the latter :) )

I agree that dynamically-typed OO languages -- especially with support for closures -- give you pretty good means for composition, but then they generally still lack some of the other benefits of functional programming such as single-assignment and pattern-matching (I haven't looked at Self so maybe that one is different), both of which also work wonderfully with concurrent programming.

Yariv said...

By the way, there are two additional reasons to separate data and code that I forgot to mention. The first is that it simplifies hot code swapping. If you change the code for a module in Erlang, this doesn't affect the data in memory. In an OO language, changing the code for a class introduces additional complexities with regards to objects that have already been instantiated: you need to change all their class pointers, and probably add some kind of versioning mechanism to your classes to make sure you don't do anything dangerous. I imagine inheritance can cause additional difficulties there. If you change the code for a base class, and possibly add a field or two, this should have strange effects on objects from child classes. Maybe all this is doable, but hot code swapping certainly harder when your data and code are bound so tightly.

The second reason is that it simplifies messaging. It's easier to send pure data between processes or even different machines than data that's inherently bound to code. Take a hypothetical client/server situation, where the server has rich APIs for working with data, and the client doesn't need those APIs. In Erlang, it's easier for the server to just send the data without requiring the client to have the server classes so that it can properly deserialize the data. (In a similar manner, ErlyDB avoids the impedance mismatch that affects OO database abstraction tools.)

keithb said...

Its' true about the ease of hot swapping code. But then, honestly now, how often have you actually done that in production systems? How many people are really running the sort of non-stop environment that this facility is needed for? Some are, and some of them would benefit from using somehting less like Java/.NET and more like Erlang, but it's not a killer feature of a runtime in general.

As far as inter-process communication goes, yes sending structs is peferable to sending objects. No OO language I know of prevents you from serialising an object into a struct on the wire if you're smart enough to realise that this is what you should be doing. On the other hand, from time to time I might want to guarentee that the bits I send get deserialised into an instance of a particular class at the other end, can't do that if I'm restricted to sending bare structs.

I'm generally suspicious of arguments that A is superior to B because A prohibits vice and promotes virtue when (regarding some facet) B is actually more flexible than B. Its down this route that we end up with Java style operator overloading: good for Sun's Java developers, bad for application developers. I thinkn that language designers shoudl ahve more respect for their programmers (users, in fact) than that.

Yariv said...

Regarding hot code swapping, I actually think it's a killer feature that would be quite difficult for me to live without. Even if you don't care about using it to minimize downtime, this feature is great for speeding up development. After you change some files, you just reload them into your application while it's running without having to restart it. I use hot code swapping all the time.

The messaging argument I made is admittedly not very strong :)

Viscayno said...

Your article has waken my curiosity about Functional Programming. I would like to know if you have other valuable links to read more about the philosophy behind it.
I have a question also. If you sustain that OO modeling is a chimera, why does it keep valid with the possibility also to be enhanced using the Aspect oriented approximation?
Thanks for your nice work.