Does Object-Oriented Programming really suck?

I recently read Armstrong essay on how much OOP sucks. While such opinions would probably have considered pure blasphemy a few years ago, nowadays they are becoming more popular. So, what’s the matter with OOP?

The first thing that comes to mind is that OOP promised too much. As already occurred to other paradigms and ideas (e.g., Logic Programming and Artificial Intelligence) sometimes researchers promise too much and then they (or the industry) cannot stay true to their promises.

OOP promised better modularity, better code-reuse [0], better “whatever”. Problem is, bad developers write crap with every single programming paradigm out there. With crap I really mean “utter crap”. A good programmer using structured programming and a bad programmer using OOP, is that the good programmer’s structured program would probably look “more object oriented” than the other one.

Another problem occurred in the OOP community: OOP “done right” was about message-passing. Information Hiding, Encapsulation and the other buzz-words are a consequence of the approach (because object communicate with messages, their internal state is opaque) not a goal of OOP. Objects are naturally “dynamic” and the way we reason about code is separating concerns in objects having related concerns and having the objects communicate in order to achieve the task at hand. And I’m a bit afraid of talking about “OOP done right”: I really just have my vision. OOP is very under-specified, so that it becomes very hard to criticize (or defend) the approach.

However, OOP becomes “data + functions”. To me data is simply *not* part of OOP. It’s an implementation detail of how objects maintain state. As a consequence, I do not really see data-driven applications as good candidates to OOP. Once again, OOP was sold as universal. It is not. Consider the successes that functional programming is achieving (performance and concept-wise) in this area.

This “data + functions” comes from C++ being the first commercially successful OOP platform. The great advantage was that the transition from structured programming to OOP was quite more easier, that programs could be far more efficient (read “less runtime”) than message passing dynamic OOP systems, at least back in the day. However, there was so much missing from the original idea!

Since back then classes were considered good (and C++ had — and has — no separate concept of interface) + static typing and a relatively verbose language with no introspection, it became rather natural to focus on inheritance. Which later was proved to be a bad strategy. Consequently, there is less experience in building OO software than one would think, considering that for a large part of its history OOP was dominated by sub-optimal practices.

So, what is really bad with OOP? Following Armstrong:

Data structure and functions should not be bound together

Agreed! But I believe that Data Structures are not *truly* part of OOP. Let me explain.

Data is laid out in some way. There is a “physical layout”, for example. You can express that very precisely in C with extensions, to the point of exactly specifying the offsets of the various datas. A phyisical layout also exists in high level languages such as Python. However, it is not part of the Python model. Of course with the struct module or ctypes you can fiddle with it (but they are libraries), however, for the most part, it is just outside the conceptual language used to describe the problem.

Data is also laid out in logical ways. Computer Science defined many data structures and algorithms over them. You can use OOP to express such structures and such algorithms. Still they are not “part” of OOP, they are just expressed in an object oriented way (or maybe not, and remain at structured programming level).

One very good practice in OOP is not using together in the same body of code objects reasoning at different levels. So, for example, you have your low level business logic code that is expressed in terms of data structures, high level business logic expressed in terms of low level business code… and that’s it. Functions is not really together with data. You don’t have “data”. You have some layers of objects.

The point is that OOP is about creating languages at semantic level (you usually do not get to change the syntax). That’s it. If the language is good, well… good. If the language is bad, ok, we’ve got a problem.

Is this suboptimal? In a way, yes. All the indirection may be very expensive. And since abstractions, well… abstract, you may find yourself with a language that is not expressive enough (at least not at the expenses of additional performance costs). Still functions and data structure is not bound together. You just have objects and messages. No “functions” and no “data”. Please notice: this may not be the right thing to do. Still, the problem is not with data + functions, is just related to applying OOP to a specific domain that is ill suited for the approach. OOP is not for every task in the world. But the same objections applies to every system that is built as a stack of layered abstractions.

Please also consider the Qc Na story! Objects are not necessarily opposed to functional programming (you can see them as closures that make different actions available). Objects are just about state + behavior + identity.

Everything has to be an object

And this is something that I don’t think is a problem. It is like saying that Scheme is bad because “everything is a list” (which, strictly speaking, is not true, there are atoms and lambdas etc). If you do not want to program OO, then don’t. If you want, you probably want that everything is an object.

The only issue with everything is an object is, sometimes, performance. From a variety of points of view, such strategy may kill performance. Objects usually have indirections (read pointer). 64 bit pointer for every integer is bad. So we have hybrid stuff like Java and then we have to deal with boxing (either manually in the past or automatically right now). Performance issues can be somewhat “fixed” using proper JIT systems or other optimization techniques. Or providing libraries that do the right thing (see Numpy, for example).

Other than that, I prefer objections in the line of “this thing that should be an object is something else” than those requesting that something that is an object really is. So, I can favorably consider an objection that says that, in Python, “if” is not an object (true). Even though I’m convinced that having if as a statement is not bad either.

And the whole objections with “time”… well, time (and dates) are a bitch to handle. But I find that Python datetime module gets as close to perfection as humanely possible. I really can’t see describing time with a bunch of enums + some structures as an improvement. On the other hand, it looks to me as one of the cases where it is *easy* to see that the OO approach works better.

Consider the related problem of representing a date in a locale. If you introduce a new representation of time, you need either to modify the original function or create a new function (maybe one that works with both things). Creating an interface, on the other hand makes it very easy to introduce new representations of time.

Objection 3 - In an OOPL data type definitions are spread out all over the place

And once again, in OOPL languages data type definitions are not spread out all over the place. They are in C++ and perhaps in Java. And even in Java, if things are done properly, you reason in terms of interface, i.e., in terms of typed messages, not in terms of data structure.
“”“In an OOPL I have to choose some base object in which I will define the ubiquitous data structure, all other objects that want to use this data structure must inherit this object. Suppose now I want to create some “time” object, where does this belong and in which object…
””“
Here it is pretty clear what he has in mind. I think that it is clear that, conceptually, time is an interface and that there is really no need for it to define “data structure”. And if your language is duck typed, the interface is implicit and you have finished before you started.

Objection 4 - Objects have private state

And here I have to agree: state is the root of all evil. Problem is that entirely stateless systems are simply unpractical. We reason in terms of state. We can describe lots of things as stateless, but somewhat we have state. We have files. We have documents. We want them saved and retrieved.
So, we have to deal with state. Agreed. But: 1. imperative programming is about state2. object oriented programming is not, strictly speaking
You can use a “functional” style in OOP, for example. Most of the times, you don’t do it because the code becomes harder to write. But in many situations, on the contrary, you do it because it makes it easier. Often I write immutable objects that cannot be modified: they are not more stateful than a parameter in a function.
Sometimes this is not practical. Ok. And surely using a very stateful style of programming is bad. State in OOP is expressed as behavior. That’s it. Sometimes is done properly, sometimes it is not. Some strategy to deal with state are extremely nice (STM, as an example). Others are not. Also consider how “modern” functional languages really merge concepts from OOP (without being OOP) and how “modern” OOP languages merge concepts from FP (without being functional).
Examples: Python from the OOP side, using generators, lazy evaluation, list comprehensions, closures, etc etc etc.Clojure from the FP side… and all the features it has to express what resembles interfaces, STM and so on…

——

[0] someone once told me they feel lucky when they can actually use the code effectively once, let alone reusing it.

Handle this! (views, const, state in Clojure, Java, C++ and Python)

Introduction

The original vision Alan Key had on object oriented programming was about separate entities communicating through message passing. A logical consequence is that the global programming state is the sum of the individual states of these entities (called objects). State of such objects is naturally hidden from the outside and state modifications occur only as a consequence of the exchanged messages.

I would like to mention that in this model the "privacy" of internal variables is not exactly simply a matter of a keyword, but a consequence of a programming philosophy. This is not the kind of limitation you get in Java classes or C++, where the field is there, you just cannot access it. It somewhat more similar to calling a black-box with a state that is its own business; there are no fieldsand if there are, they are just an implementation detail. Or even more so, private variables are not accessed in the same sense that the physical address of an object in Java is not part of the programming model.

Such objects do not necessarily have their own thread of execution (in the sense that they are concurrently in control). However, if they had, the logical model would not be overly different. But back to the objects…

I somewhat believe that objects are an overloaded metaphor. In fact, there are at least two types of objects. And while the object oriented message only metaphor well applies for domain specific objects, I somewhat feel that it is not appropriate for some data structures. Sometimes, it is a nice property that "similar structures" have a common interface so that, for example, switching from an array to a linked-list is a painless transition, because it eases experimentation with different trade-offs regarding computational efficiency (although such problems are better solved with pen and paper).

However, in other situations, accessing the internals of some complex structure is plainly the "right thing to do". It is a walking-horror from the object oriented point of view, but it plainly makes sense for computational reasons. I often have to deal with graphs with billions of nodes, and more often than not I feel that usual OO laws are too restrictive.

Graph example

A clear example here is the design of networkx.Graph: I have nothing against the design, by the way. I believe they do the right thing. Here the idea is that they have implemented their Graph internals in some way (does not matter how, right now). However, you may want to get a list of all the nodes in the graph. Now, how to do this? The first issue, is that the nodes may not be memorized in a way which is easier to return. This is actually the case: nodes are a dictionary keys, under the hood. So essentially there is no easy way to return them without calling some dict member which returns a newstructure holding the nodes.

State and "Static" OOP

OOP is all about state change. Perhaps just local state change, if done correctly. And hopefully the state's effect do not propagate too far from where the state is hidden. About C++, I found no other very mainstream OO language that makes it clear what you shall change and what you shall not.

The C++ pragmatics is really precise on consting whatever you can const. And to solve issues where it is not practical to have a logically const object which actually mutates something inside, you can use the mutable modifier to support the idea that the object realstate did not change while some irrelevant parts of it indeed changed. Examples are forms of caching, counting stuff, logging to a logger we hold a reference to.

Another important aspect of C++ is that it quite distinguishes between a const pointer (a pointer that cannot change) and a pointer to a const object (the pointed object cannot change). As always all this leads to additional complexity. However, declaring stuff const is good: first it is a rather strong safety guarantee, second it really leads to optimizations otherwise impossible. Still, it is tragically inadequate wrt. plainly immutable objects.

Moreover, although many other languages do not have pointer arithmetics, they do have references. In Java it is possible, for example, to mark such a reference final, which essentially means it will always refer to a given object. However, there is no way to state that the actual object could not be mutated by accesses through that specific reference.

In Java, the only way to achieve that goal is not providing methods that mutate the state. In fact this approach makes sense. Somewhat you make the language simpler without really losing much. And C++ newbies really do not get the whole constness thing very well.

Essentially, in Java you do not have the possibility to have a mutable object that some clients cannot mutate. There are options, however. For example, in Figure 1) we have two interfaces, one mutable and one immutable. We have the mutable interface extend the immutable one and the appropriate base classes.

Immutability at class level can be obtained both (a) with a true immutable implementation implementing the immutable interface and a mutable implementation implementing the mutable one; or (b) with just a mutable implementation: clients that should not mutate the object will use the immutable interface. This is quite similar to the const in C++ in the sense that a const_cast is usually possible (and in this case we could just cast to the mutable interface). Such things somewhat break the whole immutability thing, but sometimes have their uses.

And what is the big deal with immutability? Basically, in this context immutable stuff can be shared with no fear. And copying huge datasets is too inefficient to be considered.

Dynamic OOP

The essential problem here is that the OO language we have discussed so far are built around the idea that your co-workers will screw the project if they can do stuff. So the objective is not letting them do it. Constness shall be enforcedby the language (you had the opinion that I was happy about C++ const, did you?) because otherwise someone will foobar the project.

On the other hand in languages such as Python you may well do everything to every object and consequently the const-enforcement does not fare very well. A bit more could be done (formally) in Ruby. Still, even then you could always hack the objects to let you do whatever you want. And believe me, you could do that also in C++ and Java, provided you have sufficient control of the environment where the program is going to be run. It is just way harder.

In fact, I believe approaches where good policies about code isolation can be also (easily) implemented in Python. Good API design is of paramount importance. A C++ wise advise (from Meyers) was "Avoid returning Handles to object internals" (Item 28, Effective C++, 3rd ed, Scott Meyers, Addison-Wesley).

Essentially the idea is never to let your object guts exposed and never ever let someone mess with it. This is not about trust. This is about such handles are just a sure way to break your object constraints (why I'm talking like a static programmer anyway?). The point is that such handles change state independently by the core object and this is probably going to be bad, because the corruption of the state will be revealed in a place and time extremely distant from when and where it actually happen.

So, we have to carefully design our APIs, even (shall I say, especially?) if we are dynamic programmers. For example, we can return views on our object internals. Since our languages are very dynamic, such views can be easily constructed: they just have to quack like the original objects. When it makes sense, it is probably just better place the functionality in the "large" object and to delegate to the attribute (delegation is so trivial to implement in dynamic languages!). Notice that strongly interface based languages such as Java could make this approach even more natural, provided that formally specified interfaces make sense for the specific case.

Sometimes it makes also sense to return object which can mutate and where their mutation influences the state of the object from which they come from. However, in this situations such objects shall be built in a way that they do not break the behavior of the object from which they were gotten. Essentially here we are just obeying principle like SRP (single responsibility principle) and design things to work together. In fact, they are not handles to the object internals at all. We are not exposing the implementation of the object: we are just exposing an interface to a part of the object state (perhaps even state that cannot be changed through the main object interface).

What are the problems with this approach? As long as things are not modified, copying is fine. A view is a good thing, because it may be as efficient as possible for reading, while being completely safe. The problem essentially arises when we want to mutate the objects state: internals handles are bad, so we have to:

1. carefully craft the object interface to allow modifications efficiently and that make sense to the problem at hand, without making it excessively general (because it clashes with efficiency) or excessively big (because it clashes with almost every good property OOP tries to give to programs)

2. Perhaps create special objects that are able to perform controlled modifications on the original object. This may give lot of generality, in a sense, but also complicates the class hierarchy significantly.

Graph example

Back to our example… we may have many solutions. Suppose that this "get the list of nodes" operation is frequent enough. It may make sense to memorize such list separately from the dictionary. If node removal and addition is not too frequent, the additional memory may well be worth it (well, perhaps not, if we really have lots of nodes). Even if such operations are frequent, we double the cost of the addition and make deletion O(N)… but if instead of a list we use a set, we have both operation O(1) simply with an increased multiplicative constant. Of course a language could offer a dict implementation which essentially offers an efficient view over the set of keys, so that separate memorization is not needed.

We could use a mutable datatype to hold the list, but then we should make a copy before returning it (this what actually happens with networkx). Not making a copy has the same problems of returning an internal handle. If we make a copy, then we could return something immutable or mutable. Essentially returning something immutable has not a lot of sense, as modifications would not affect the graph andmodifications to the graph are not reflected in the node-list. The simplest thing to do is plainly return a list of nodes.

The true solution would be that dictionary supported a "true" view object which is able to modify the original dictionary. And actually Python 2.7 and Python 3 have it. At this point we could just return such thing and have both efficiency and functionality… were it not for a simple issue: a networkx graph has more than one internal structure holding the nodes. Thus a higher level view would need to be created which could work across the different point were the same information is memorized inside a Graph. And we are back to the "complicating the class hierarchy thing".

Immutable by default

The thing is that actually having to specify things to be const, is a bit a pain. And perhaps it is just me... but consider the Java solutions (this apply to things which roughly work like Java): we are talking about having two class and two interfaces (or just one class and two interfaces) for lots of objects. In my opinion, this is not practical. And if we want to create "well-behaved handles" things become even more complex.

In fact, this is probably why it is not done (most of the times). Probably it should be sufficient to limit such strategies for things where it really matters. Think about the collections framework.

On the other hand... think about a world where most things are just immutable. I think it is just a safer mind model of programming. It is not about limiting your colleagues (or yourself) on not doing things which are licit in the model and that we want to restrict.

If we thinkimmutable, things are just easier. But then we are definitely moving towards the functional side of things. I'm not claiming that functional languages have onlyimmutable stuff. Even though many functional languages (Clojure, Haskell) have mostly immutable stuff. However, reasoning in terms of flows of functions and immutable objects is just easier than thinking about immutable immutable objects. At least, it should be, if we were trained to think functionally from the beginning.

Here we are used to deal with const objects. Sometimes we needto change the state. Two typical scenarios spring to mind. We aren't doing "Object Oriented Programming": we are just writing an algorithm and the algorithm was conceived for imperative languages. Sometimes there is no clear conversion into the functional world. Not an efficient one, at least. In this case we may want to use some special mutable object (arrays?) to perform our computation efficiently. And this may even generally work.

In the second case, it is simply not practical to structure the state of the world as some function parameters. In fact most of the times the global state is to big to be wisely represented as a huge set of parameters. In this case we probably want to express the computation as a set of transformations (functions, basically) that shall be executed one after the other on the world. Here I am mostly thinking about Haskell's monads. Though, even different from a syntactical and semantical point of view, we are not far from the realm of refs/agents.

The issue of efficiency, however, remains. We should still keep in mind that well buried under layers of object orientations there may be lots of hidden costs. Interfaces often get in the way of really efficient implementations, because costs are not part of the interface. The collections framework is beautiful… but sort is still implemented copying everything to an array and sorting the array.

Welcome under the sign of the Lambda

Not only it is better to have const object by default, that is to say object mutability shall be an opt-in rather than an opt-out. In fact, a part from the famous koanabout objects and closures, we have to avoid returning handles to our objects guts… but I do not see often closures that open up the enclosed state to the world.

The point is that avoiding all the copy costs may be simply thething to do when we have to deal with huge datasets. Restrict mutability where needed (e.g., implementing the algorithms) but mostly use mutable input and outputs from functions. Moreover, functional code is generally flatter, which can also, in the long run, improve efficiency.

Eventually, with languages such as clojure, even the perceived drawbacks of lists can be avoided using vectors, which support efficiently a different sets of primitives. Lazyness is also extremely helpful: actions that are not performed do not cost.

Erlang and OTP in Action (review)

First time I got into Erlang, it was with "Programming Erlang: Software for a Concurrent World" (Joe Armstrong). It is a very nice book, in my opinion, and I enjoyed immensely reading it. That was like 4 years ago or something. Back then, the functional revolution was just at the beginning: no widespread Scala, no Clojure at all, essentially no F#. Back then it looked like OO was going to rule the industry for years and years, with no contender of sort. Rails was fresh, Django was fresher (back then the APress book was just being released).

I bought the book because I wanted to see this "brand new" technology (20 year old, but just going to make it through in the circles I did frequent). And really, the language looked like 20 years old. Full of Prolog legacy, Unicode who's that guy? and so on. However, it no other piece of software I knew could as easily. Massive concurrency, hot swapping code. Wow.

The language, I did not especially like. The runtime… WOW! As a language, I love Python or Clojure because the way apparently distant functionalities work together and create something even more beautiful. Erlang does not have that at language level. It has at a framework level.

Think about hot swapping code in an object oriented software. First, I somewhat believe that object oriented modules are somewhat more tangled that functional equivalents. Partly because of the object reuse OO promotes (that can really be against you if you want to swap code). Then, there is the whole problem of references vs. addresses. Addresses have an additional level of indirection that makes it far easier to swap a process than it is to swap an object.

But the very idea that state is in the function parameters and that process linking and easy restarting thing are at the very root of how easy it is to swap code in Erlang. But then… back to the books.

The essential problem was that after seeing a bit of Erlang, I thought OTP was not a big deal. Yes, it is easier to use. But also plain Erlang is. And I convinced myself that should I need Erlang, I could just use plain Erlang. Than things changed: I read some OTP using code and I understood not so much of it. That was this year. What I understood, was that it could be helpful. I had to write a concurrent prototype and I welcomed the idea not to write as much code as possible.

In the meantime, I forgot many things about Erlang. In this situations, instead of reading the same book twice, I buy another book to gain perspective. So I decided to buy another book. One of the candidates was "ERLANG Programming" (Francesco Cesarini, Simon Thompson). It also had excellent reviews. Essentially I believe it contains more material than Armstrong's book and is also a bit more recent. However, as far as I understand, is still a bit terse on OTP.

As a consequence, I bought "Erlang and OTP in Action" (Martin Logan, Eric Merritt, Richard Carlsson) instead. And I'm very happy of this choice. It complements Armstrong's book well and extensively covers OTP. In fact, I also believe that the approach is very interesting. Introduce OTP first and learn to use it, then when you know what it can do, you are going just to use that. Then, learn plain Erlang in order to extend OTP when your use case is not covered. And a nice plus was a detailed description of JInterface, which I could need as well.

In fact, I do think that as it may make sense to introduce objects as early as possible in a book on an object oriented language, starting with OTP is a very big plus from a learning perspective. Then perhaps the point is that I did not need to get into a functional mindset (which I think Armstrong book does with more attention.

If the question is however just "learn to think functionally" I believe that "The Joy of Clojure: Thinking the Clojure Way" (Michael Fogus, Chris Houser), LYHFGG or Land of Lisp are probably better alternatives. Another interesting one is "Functional Programming for Java Developers: Tools for Better Concurrency, Abstraction, and Agility" (Dean Wampler), even if it has a whole different perspective.

Excellent Learn You a Haskell for Greater Good

This is the third book explicitly about Haskell I directly buy (a part from things such as Functional Data Structers or Pearls of Functional Algorithm Design), the others being Haskell School of Expression and Real World Haskell, plus some online tutorials and freely available books. I believe they are all excellent books, although with slightly different focus. They come from different ages as well (with HSOE being quite holder).

Back then I enjoyed a lot HSOE, but I think I missed something. Large part of the book used libraries not easily available on the Mac, for example. Moreover, the book did not use large parts of the Haskell standard library which are very useful. For that and other reasons, I did not go on working with Haskell. Real World Haskell has a very practical focus and I quite enjyoed that. Unfortunately, I still remembered too much Haskell not to "jump" the initial parts of the book (and that is usually a bad thing, because you don't get comfortable with the author style before jumping to more elaborate subjects). Moreover, the book is quite massive and I had other stuff to do back then (like graduating).

I did not even want to buy LYHFGG. Afterall, I am a bit skeptical over using Haskell for real world stuff (I prefer more pragmatic languages like Python or Clojure) and so I tried to resist the urge to buy another Haskell book (I could finish RWH, afterall). For a combination of events I did not even remember, I put the book in an amazon order. Understanding a couple of Haskell idioms could improve my clojure, I thought, and I started reading the book in no time.

The first part of the book is very well done but somewhat uninteresting. By the time I started reading it, I had forgotten most Haskell I knew and consequently I read that carefully: however, I made the mistake not to start a small project just to toy with the language. That is the reason I say "somewhat uninteresting": it is very basic, very easy and very clear. Still, I did only remind me of things I knew, without really improving my way of thinking much. Still, the writing was fun and light and I read through it quickly. I consider it a very good introduction to functional programming in Haskell and to functional programming in general and as such the tag line "a beginner guide" is well deserved.

Later in chapter 11 comes the real meat. Functors, Applicative Functors, Monoids and then Monads are presented. The order is excellent: after having learned Applicative Functors, Monads require only a small further understanding steps. Moreover, repeating all the reasoning on Maybe and lists really clarifies the thing. The examples were also in HSOE, but connecting the dots was somewhat left to the reader. This time I did not make the mistake to see monads as just a tool to implement state monad and reached a deeper insight on the subject.

About the book itself, I just love no starch press...

"Learn You a Haskell for Great Good!: A Beginner's Guide" (Miran Lipovaca)

"The Haskell School of Expression: Learning Functional Programming through Multimedia" (Paul Hudak)

"Real World Haskell" (Bryan O'Sullivan, John Goerzen, Don Stewart)

"Pearls of Functional Algorithm Design" (Richard Bird)

"Purely Functional Data Structures" (Chris Okasaki)

Technorati Tags: Haskell, Functional Programming

Is removing parentheses worth it?

Introduction

The first objection to lisp is "too many parentheses". It is roughly the same objection that programmers do to Python (well, not "too many parentheses" but the fact that you have to follow minimum decency rules for indentation). And Clojure claims to have reduced parentheses... let's go into this.

Back to the indentation vs. parentheses thing, the objections are similar because they share a single pattern: people who do not use the language feel that it is a major drawback, people using it usually like it and people who have to use it without particular enthusiasm usually are agnostic about it. That is to say, the language feature under examination looks "worse" from the inside than from the inside.

In fact Python programmers usually justify saying "you would indent it that way in any case"; which is true to some degree (programmers may use a slightly different style, but essentially it would not be that different to make anybody uncomfortable). Beside, as someone having to read and fix code from complete novices (being an assistant for a basic programming undergrad course), most of the times the first thing I have to do is running the programs through a beautifier (and most of the times even the novices spot the error as the program is properly indented -- but that is another story, and I keep telling them about indenting properly).

Lisp programmers usually answer objecting that in fact they do not even see the parentheses when typing (in fact I do see them) and that they are automatically inserted by Emacs (which is true). As a consequence, they do not have to type more. I add that Emacs is very good at using parentheses to understand the program structure and gets the indentation right. I have to say that the major drawback of Python approach is just that automatic indenters cannot do their job properly (not that I ever felt that it was a real issue).

Use all the parentheses!

Common Lisp basically uses only () because language implementors feel that the other kind of parentheses are free for the language user to abuse in defining custom languages. I understand that this may an advantage in some situations. On the other hand I also feel like having the parentheses in the language also allows interesting possibilities.

For example, I quite like that in scheme R6RS the possibility of liberally using [] can improve readability, at least to my eyes. For example I often use them in case expressions and to hold let bindings. In general when I have multiple S-expressions in the form ((LHS1 RHS1 ...) ... (LHSN RHSN ...)) I often write them as ([LHS1 RHS1 ...] ... [LHSN RHSN ...]), especially in cond/let forms, which is, as far as I can tell, an usage explicitly sanctioned in the C appendix of [1].

The good part is that you are free to use square brackets or not to use them. The bad part is that you can choose to use square brackets or not to use them. That is to say: there is a non normative suggestion, but you are not forced to follow it. As a consequence code can legitimately use or not use square brackets. Moreover, their usage is not standard in R5RS; consequently if the code is meant to work on both implementations, using square brackets is not an option.

In this, I praise Clojure choice. Using square brackets and braces is a good idea for a new lisp dialect, especially for one that is not meant to win Common Lisp programmers, but to be used in Java environments and to bring object oriented people into a more functional world.

I really like the idea that vectors are just [foo bar ...]. Even thought it was not particularly hard to write #(foo bar) instead. However, the syntax for hash maps is really a plus, in my opinion. And so it is the one for sets. It is not something you leave Common Lisp for, but it is a legitimate choice and a rather wise one: once you decide that you are definitely not going to let user customize the language with reader macros, then you better use the symbols you have! Moreover, considering that the JVM is more optimized for array like stuff, I believe that wider usage of vectors [] also justifies their new syntax. Where a scheme programmer uses a list of atoms, a clojure programmers uses a vector of symbols.

I am quite agnostic on using [] to delimit binding forms. I don't think that more than two lines should be written on the subject (even though depending on the width of your screen, these may be far more than two lines). I don't feel it is less lisp because we write (let [...] ...) instead of (let (...) ...).

Readability counts

On the other hand, I feel the removal of parentheses a drawback rather than an advantage. But I may be biased: for example in languages with infix syntax, I tend to use additional parentheses when precedence issues are slightly more complicated than trivial (which basically happens as soon as we use more than the elementary arithmetic operations).

The question is that using less parentheses decreases the redundancy of code (which would be a good thing, if it wasn't for the fact that redundancy means better error correction). For example, consider this code:

(let [x 1 y 2] (+ x y))

First, I do believe that having the paramethers all together makes code less clear. Syntax can be used to visually aid the programmer. In this case while it is obvious for a machine to match arguments pairwise, the eye is not helped at all. Besides, if I do indent it properly, I also feel some sense of irresoluteness because of the way the parameters are divided [notice that parameters should be lined up; however it seems that something between blogger and scribefire randomly destroys proper indentation, sometimes, if it happens it was not what I meant]:

(let [x 1 
           y 2] 
  (+ x y))

I believe that this is far more readable (but it may be my bias, as I said):

(let ([x 1]
           [y 2])
  (+ x y))

because parentheses logically group arguments. Notice that in C if I could write int foo 8;. I would still prefer int foo = 8. Ok that syntax would be ambiguous (consider int foo (8); would be a valid function declaration and a valid variable definition, as I can place () around expressions... in a way which resembles me of the classic error mytype foo(); which most beginners do -- that is a function definition, not a variable declaration).

Anyway... back to clojure. Consider the following code:

(let [x 1 y] (+ x y))

It is an obvious mistake (well, not so obvious, IMHO). And the compiler says:

java.lang.IllegalArgumentException: 
  let requires an even number of forms in binding vector 
  (NO_SOURCE_FILE:0)

Good. But what if we are type hinting freaks and write:

(let [^Integer x 1 y] (+ x y))

I know that in this case it would be better to use (int 1) but, that's just an example. Ok... the compiler still complains (rightly):

java.lang.IllegalArgumentException: 
  let requires an even number of forms in binding vector 
  (NO_SOURCE_FILE:0)

Now I should check what is a "form in a binding vector". Perhaps the definition explicitly excludes type hints, so the compiler is not lying. But the heck... the message is extremely unclear. I believe that lack of parentheses is rather annoying in this case. But I've seen worse.

The cond statement is not very good either...

(cond
  (instance? Integer x) :int 
  (instance? String x) :string
  :default :dontknow)

Once again, a few more parentheses could group things more tightly. But this is just a matter of taste.
A discussion about the condp form is here.

References

1. M. Sperber, R. K. Dybvig, M. Flatt and A. van Straaten, "Revised⁶ Report on the Algorithmic Language Scheme - Non-Normative Appendices -.
   

Clojure, Programming, Lisp, Common Lisp, Scheme

The Game of Life

When Conway introduced "the Game of Life" in the mathematical column of Scientific American it immediately had an enormous success. The game itself is simple: there is an infinite grid of cells and cells live or die according to a bunch of simple rules.

The game roots are far less than trivial, as in those times Conway was interested in a problem which is still actual today (introduced by von Neuman, according to Wikipedia). The idea was building a machine able to copy itself (in which von Neuman succeeded, but Life is just simpler). Later, the game was proved to have the same computational power of a Turing machine. Anyway, the rules are:

• if a living cell has just two living neighbours, it dies.
• if a living cell has two or three living neighbours, it remains alive
• if a living cell has four or more living neighbours, it dies.
• if a dead cell has exactly three living neighbours, it becomes alive

Every self-respecting computer geek has tried to implement the game at least once. Indeed, the variant usually implemented is placed on a thorus (that is to say, finite width, finite height, wraparound). This greatly simplifies the implementation (which becomes trivial) and holds much of the nice properties "game-wise".

I have no idea how many times I implemented the thing in different languages. Indeed, it is a very nice problem to implement idiomatically. I have to admit that I still have the idea of proposing this as an exercise for the programming lab of a course here at the University. Still, I'm not sure students would find it as amusing as I do and perhaps it would be just a hard exercise for them (depending on how much exercise they did on holiday). So I decided not to give it. Moreover, they would have to do it in C++, which is far less amusing than doing it in Lisp (the last language in which I did it).

I somewhat feel lot of freedom in Lisp. I don't feel I'm forced to a careful and formal object oriented design: things usually feel better if they are simpler. And usually code remains decently organized nonetheless. For example, in an OOL the "board topology" would probably be a class. From another point of view, there is nothing suggesting that a very simple GOL implementation needs such generality. Probably, it we would like to have different boards (especially considering questions about very large boards and efficiently storing and manipulating data) different visiting strategies (cell for cell) should be used. In fact just iterating over the alive cells, does not account for the 4th rule. Detecting a cluster of three alive cells (starting from an alive cell) around the dead one may not be efficient. In fact, I have not thought about the algorithms that should be used in those cases, not I wanted to. I did not want to develop an industrial strong GOL implementation: I just wanted to toy with Lisp. Over-engineering is just around the corner. Beware!

By the way, here the toy implementation.

Seven Languages in Seven Weeks

Today I eventually received my own copy of "Seven Languages in Seven Weeks". To be sincere, I started reading the electronic version some time ago (Pragmatic Programmers had a huge discount some time ago, just after the "Programming Ruby" at 10$).

Seven Languages in Seven Weeks

I'm not going to criticize the language choice. In fact, I think that the languages are a wise selection (Ruby, Io, Scala, Clojure, Prolog, Haskell, Erlang). They are all interesting languages and have something other languages do not have. Although I'm quite into Python, I'm not going to complain for its exclusion: the author is far more confident with Ruby (as far as he tells) and that means that his explanations are surely more accurate.

I love the idea of the seven languages in seven weeks: beware, this is not a "Teach yourself C++ in 21 bloody hours". The author is well aware that you could not possibly learn seven languages in seven weeks, but you can understand what those languages are about in seven weeks. I'm thinking about the potential this book has when read by people grown up in closed Microsoft or Java contexts (or perhaps even C and C++). If after reading this book he is still convinced that all the languages are the same he is either a compiler or a very distract reader (and probably hasn't understood a thing about the book).

Just seeing the languages is a wonderful enlightening experience. Realizing how much useless boilerplate compiler-friendly code some languages force developers to read is the first step towards better ways of programming.

And what about me? Well... I already knew 5 of the 7 languages quite well. I have known Ruby and Haskell for 5 years or so, a couple of years later I learned Erlang as well. Besides, I also wrote some thousand of lines in Prolog for my BSc and my MSc dissertation was on logic programming (specifically on building an efficient "interpreter" for a given logic programming language not too dissimilar from Prolog itself). I started studying Clojure basically when the word of mouth started spreading, which makes it about 2 good years. So what's it for me? For example, I am sorry to say that I found the part on Prolog rather unsatisfactory, but hey... I don't think that the goal of the book is to teach me Prolog. However, it gave me a pleasant introduction to Io (which I would have probably never learned) and convinced my that my first impressions on Scala were wrong and perhaps I have to give it a second chance.

So definitively worth reading. And here a free chapter!

Programming, Programming Languages, Seven Languages in Seven Weeks, Ruby, Haskell, Io, Prolog, Clojure, Scala, Erlang

Romans in scheme

I described (here and here) three different ways to write the code to represent an integer in "roman" format.
Essentially, I think the best is the one using closures. In fact, while writing the python version, I also wrote a scheme version.

Although scheme is mostly a functional language, I will use the very same example to move towards a more imperative style. In Python I made my code "more functional"; the experiment is now making the code "more imperative" in scheme.

I show here the python code as an immediate reference:

@apply
def int2roman():
    weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}
    sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
    def int2roman(n):
        thousands, n = divmod(n, 1000)
        roman_digits = ['M', ] * thousands

        for m, s in sorted_weights_tuples:
            while n >= m:
                roman_digits.append(s)
                n -= m

        return ''.join(roman_digits)
    return int2roman

I wrote two helper functions: the first one essentially is equivalent to the inner while loop in Python, the other one to the for loop.

(define simplify-by-weight
  (lambda (weight ch n digits)
    (letrec ([sbw 
              (lambda (n digits)
                (cond ((< n weight) (cons n digits))
                      (else 
                       (sbw (- n weight) (cons ch digits)))))])
      (sbw n digits))))

(define simplify-all
  (lambda (weights n digits)
    (cond 
      ((null? weights) digits)
      (else
       (let* ([ret (simplify-by-weight (caar weights) (cadar weights) n digits)]
              [n (car ret)]
              [digits (cdr ret)])
         (simplify-all (cdr weights) n digits))))))

The idea to make the code more imperative looking or more imperative tout court comes from the idea that 4 lines in Python became 18 lines in scheme. This is not a "python vs. scheme". The solution I proposed in Python is, in my opinion, far more easier to read and undertand because it's so much shorter and the scheme version is cluttered with iteration details/function calls where it should have been much easier. New versions will be proposed. In the meantime, here it is the main function:

(define integer->roman-a
  (let ([weights (sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
                                 (40 "XL") (50 "L") (90 "XC") (100 "C")
                                 (400 "CD") (500 "D") (900 "CM"))
                       >
                       #:key car)])
    (lambda (n)
      (let-values ([(thousands n) (quotient/remainder n 1000)])
        (foldl string-append ""
               (simplify-all weights n(build-list thousands (lambda (_) "M")))))))
  )

Apparently this is not a closure. However, remember that in scheme let is essentially syntactical sugar over a lambda form. In fact, we could have been made the closure more apparent writing the function this way:

(define integer->roman-b
  ((lambda (weights)
     (lambda (n)
       (let-values ([(thousands n) (quotient/remainder n 1000)])
         (foldl string-append ""
           (simplify-all weights n(build-list thousands (lambda (_) "M")))))))
   (sort '((1 "I") (4 "IV") (5 "V") (9 "IX") (10 "X")
                   (40 "XL") (50 "L") (90 "XC") (100 "C")
                   (400 "CD") (500 "D") (900 "CM"))
         >
         #:key car))) 

I have to confess that I like the foldl/string-append thing more than the python append/join.
This is, of course, just a matter of taste. I could have made the code simpler pushing the while logic in an iterator and then simply using list comprehensions. However, I believe the design would have been far more complicated.

In order to simplify the code of the first two functions, I will:

1. use more special forms (or different variants of special forms)
2. try to eliminate the functions as independent units
3. if necessary, use more forms provided by racket (most of them can be added to any scheme with macros)

Here is the first function; I often use a "sub-lambda" to iterate only on the parameters which change. Here I use a let form (remember... let is sugar over lambda). I believe code is simpler, here.

(define simplify-by-weight
  (lambda (weight ch n digits)
    (let loop ([n n] [digits digits])
      (cond ((< n weight) (cons n digits))
            (else 
             (loop (- n weight) (cons ch digits)))))))

It is simple enough to be removed:

(define simplify-all
  (lambda (weights n digits)
    (cond 
      ((null? weights) digits)
      (else
       (let* ([weight (caar weights)]
              [ch (cadar weights)]
              [ret (let loop ([n n] [digits digits])
                     (cond ((< n weight) (cons n digits))
                           (else 
                            (loop (- n weight) (cons ch digits)))))]
              [n (car ret)]
              [digits (cdr ret)])
         (simplify-all (cdr weights) n digits))))))

In fact, with let-values and values code could be simplified a lot.
Essentially here the problem is that we have two nested loops
and they loop on two different things and the value of n is logically modified.

Here we are simply using named lets to express loops:

(define simplify-all
  (lambda (weights n digits)
    (let next-weight ([n n]
                      [digits digits]
                      [weight-pair (car weights)]
                      [weights (cdr weights)])
      (let  ([weight (car weight-pair)]
             [ch (cadr weight-pair)])
        (let simplify-again ([n n] [digits digits])
          (cond
            ((< n weight)
             (cond 
               ((null? weights) digits)
               (else (next-weight n digits (car weights) (cdr weights)))))
            (else
             (simplify-again (- n weight) (cons ch digits)))))))))                   

Now the tentative is using the destructive state change:

(define simplify-all-e
  (lambda (weights n digits)
    (for-each 
     (lambda (weight-pair)
       (let  ([weight (car weight-pair)]
              [ch (cadr weight-pair)])
         (let simplify-again ()
           (cond
             ((< n weight) null)
             (else
              (set! n (- n weight))
              (set! digits (cons ch digits))
              (simplify-again))))))
     weights)
    digits))

The above code can be improved using the for special form and unless (which we should already have used):

(define simplify-all
  (lambda (weights n digits)
    (for ([weight-pair weights])
      (let  ([weight (car weight-pair)]
             [ch (cadr weight-pair)])
        (let simplify-again ()
          (unless (< n weight)
            (set! n (- n weight))
            (set! digits (cons ch digits))
            (simplify-again)))))
    digits))

We are still longer than the four python lines, but we are no longer more complicated. In fact, considering scheme macros, we can define a while/until pair of special forms which simplify the code greatly:

(define simplify-all-g
  (lambda (weights n digits)
    (for ([weight-pair weights])
      (let  ([weight (car weight-pair)]
             [ch (cadr weight-pair)])
        (until  (< n weight)
            (set! n (- n weight))
            (set! digits (cons ch digits)))))
    digits)) 

Some performance measures here.

Classes and closures

Let us write some python code to transform an integer into "roman" format.
Here we use a class:

class Int2RomanConverter(object):
    weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}
    sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)

    def __call__(self, n):
        thousands, n = divmod(n, 1000)
        roman_digits = ['M', ] * thousands

        for m, s in self.sorted_weights_tuples:
            while n >= m:
                roman_digits.append(s)
                n -= m

        return ''.join(roman_digits)

int2roman = Int2RomanConverter()

This class is a callable and works as a function. We probably should have made
the class non public (_Int2RomanConverter) and made only the int2roman function
available to clients.

The more straightforward way to write the code, would have been a simple function.
In fact, I consider this an example of premature optimization. The point was
to show how functions which rely on some sort of static data (the sorted weight)
could be constructed as classes.

In this case, I think there is no perceivable difference without the "optimization".
But an example is an example.

The very first thing coming to my mind would have been creating a function
with the sorted tuples as a default argument. Something like:

def int2roman(n, weights=sorted(
              { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}.iteritems(), reverse=True)):
...

But I find this rather ugly since the weights are not a true argument,
the intention (having some data not evaluated every time) is rather masked
and users could think they can provide their own sets of weights. Well,
actually this code blatantly sucks.

Another idea was using decorators. I love decorators...
This decorator essentially adds the sorted weights to the function
as an attribute (in Python functions are objects).

def with_weights(weights):
    def _aux(f):
        f.weights = weights
        f.sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
        return f
    return _aux

The rest of the code becomes:

@with_weights({ 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'})
def int2roman(n):
    thousands, n = divmod(n, 1000)
    roman_digits = ['M', ] * thousands

    for m, s in int2roman.sorted_weights_tuples:
        while n >= m:
            roman_digits.append(s)
            n -= m

    return ''.join(roman_digits)

This code has its merits. It's rather easy to understand, provided
that you know decorators (and these are decorators with arguments,
which is slightly more complicated). You have a function, with the
right number of arguments and you are not tempted to modify
the weights.

Then a voice in the back of my head suggested "Use the closure, Riko!"
The voice sounded a lot like the one of Alec Guinness, but that's enterely
another story.

Ideally I was already using closures, only it was not obvious.
In the decorator solution, I have a function modifying the original
function. This is not very different from having a function returning
a function. It's only less general and (in other circumstances easier
to grasp).

The class based solution is rather similar (only more verbose) to
a solution using closures. In fact I have a "function" which returns
a "function". Only the first function is a constructor and the second
function is a callable object (whose only capability is being called).

Frankly I'm ashamed. The first solution is terribly javish. The second
looks a lot like... well, python has decorators, let's use them. So,
a better code is, in my opinion:

@apply
def int2roman():
    weights = { 900 : 'CM', 500 : 'D', 400 : 'CD', 100 : 'C',
                90  : 'XC', 50  : 'L', 40  : 'XL', 10  : 'X',
                9   : 'IX', 5   : 'V', 4   : 'IV', 1   : 'I'}
    sorted_weights_tuples = sorted(weights.iteritems(), reverse=True)
    def int2roman(n):
        thousands, n = divmod(n, 1000)
        roman_digits = ['M', ] * thousands

        for m, s in sorted_weights_tuples:
            while n >= m:
                roman_digits.append(s)
                n -= m

        return ''.join(roman_digits)
    return int2roman

Notice the apply trick.

The apply decorator trick

From wikipedia:

In computer science, a closure is a first-class function with free variables that are bound in the lexical environment. Such a function is said to be "closed over" its free variables. A closure is defined within the scope of its free variables, and the extent of those variables is at least as long as the lifetime of the closure itself. The explicit use of closures is associated with functional programming and with languages such as ML and Lisp. Closures are used to implement continuation passing style, and in this manner, hide state. Constructs such as objects and control structures can thus be implemented with closures.

In terms of python you have a closure when a function returns another function. This is something you often do when you use decorators, for example.

However, this is not about decorators. The classical example is the "adder":

>>> def add_creator(n):
...   def adder(m):
...     return m + n
...   return adder
... 
>>> add5 = add_creator(5)
>>> add5(6)
11

This is fun and nice. However, I often use closures in a more functional way to hide state instead of using classes. In this cases you often are not interested in the higher order function.
You use it to hide state in local variables/parameters, but you plan to use the returned function.

E.g.,

def do_something_builder():
    val = very_long_computation(...)
    def do_something(z):
        x = use(val)
        y = do_other_things(z)
        return g(x, y)
do_something = do_something_builder()

In this cases, I use the "apply trick". Apply "calls" the callable argument and
returns the result. apply can be used as a decorator as well.

@apply
def do_something():
    val = very_long_computation(...)
    def do_something(z):
        x = use(val)
        y = do_other_things(z)
        return g(x, y)

This is very similar to schemish things like, which I have seen often:

(define do-something
  (let ([val (very-long-computation)])
     (lambda (z)
       (let ([x (use val)]
             [y (do-other-things z)])
        (g x y)))))

Mastermind/Bulls and Cows Breaker

Introduction

Mastermind is a classical code breaking game. And I bet almost everyone has played it at least one time (at least, any geek[0]). I won't explain the rules here. If you really don't know the rules, here there is an explanation. Besides, we are playing Bulls and Cows, which is very similar, but has no copyright.

I sincerely find the game rather boring, though I find writing programs solving boring games quite entertaining. This is a very old prolog program I wrote to break the code. The algorithm is extremely trivial, and is more an example in how easy to solve are this class of problems in Prolog with native backtracking than anything else.

Wikipedia page also list some scientific papers on Mastermind/Bulls and Cows code breaking algorithms. I find them really interesting, indeed. But this is about Prolog and backtracking, indeed.

The code

:- use_module(library(lists)).
:- dynamic query/3.

mastermind(Code) :-
 cleanup, guess(Code), check(Code), announce.

guess(Code) :-
 Code = [_X1, _X2, _X3, _X4],
 selects(Code, [1,2,3,4,5,6,7,8,9]).

check(Guess) :-
 \+ inconsistent(Guess),
 ask(Guess).

inconsistent(Guess) :-
 query(OldGuess, Bulls, Cows),
 \+ bulls_and_cows_match(OldGuess, Guess, Bulls, Cows).

bulls_and_cows_match(OldGuess, Guess, Bulls, Cows):-
 exact_matches(OldGuess, Guess, N1),
 N1 =:= Bulls,
 common_members(OldGuess, Guess, N2),
 Cows =:= N2-Bulls.

ask(Guess) :-
 repeat,
 format('How many bulls and cows in ~p?~n', [Guess]),
 read((Bulls, Cows)),
 sensible(Bulls, Cows), !,
 assert(query(Guess, Bulls, Cows)),
 Bulls =:= 4.

sensible(Bulls, Cows) :-
 integer(Bulls),
 integer(Cows),
 Bulls + Cows =< 4.


%%  Helpers
exact_matches(Xs, Ys, N) :-
 exact_matches(Xs, Ys, 0, N).
exact_matches([X|Xs], [Y|Ys], K, N) :-
 (   X = Y ->
 K1 is K + 1
 ;   
 K1 is K),
 exact_matches(Xs, Ys, K1, N).
exact_matches([], [], N, N).

common_members(Xs, Ys, N) :-
 common_members(Xs, Ys, 0, N).
common_members([X|Xs], Ys, K, N) :-
 (   member(X, Ys) ->
 K1 is K+1
 ;   
 K1 is K),
 common_members(Xs, Ys, K1, N).
common_members([], _Ys, N, N).

cleanup :-
 retractall(query(_,_,_)), !.
cleanup.

announce :-
 size_of(X, query(X, _A, _B), N),
 format('Found the answer after ~d queries.~n', [N]).
%%  Utilities
selects([X|Xs], Ys) :-
 select(X, Ys, Ys1),
 selects(Xs, Ys1).
selects([], _Ys).

size_of(X, G, N) :-
 findall(X, G, Xs),
 length(Xs, N).

Notes

[0] Most of the type when you say "any" or "everyone" you are wrong. This applies to me as well.

Quicksort in Continuation Passing Style

Quicksort is ugly. I hate quicksort. Still everyone praises quicksort...
... and Hoare did worse things. Such as Hoare logic. I had to manually verify some short programs using Hoare logic and sometimes I still wake up screaming at night after dreaming pages of Hoare triples.

Well, this is a problem of mine. Back to quicksort... among the elementary sorting algorithms it is one of the more difficult to understand. But it is rather efficient despite its worse case N^2 running time. Moreover, quicksort can be implemented in constant space (well, almost... you still have double recursive calls which means log n, if you consider the stack).

That is why (the idea that quicksort modifies an array in place) some believe functional implementations of quicksort are not quicksort. And I'm not going to argue. I don't care, in fact. Here my concern are the double recursive calls. Normally you could not tail call optimize such a thing (pseudo code from wikipedia):

procedure quicksort(array, left, right)
     if right > left
         select a pivot index //(e.g. pivotIndex := left+(right-left)/2)
         pivotNewIndex := partition(array, left, right, pivotIndex)
         quicksort(array, left, pivotNewIndex - 1)
         quicksort(array, pivotNewIndex + 1, right)

Luckily for us, we can use continuation passing style to trick this into tail call optimizable. Code in continuation passing style is always tail recursive.

Append:

(define cp-append 
  (lambda (lst1 lst2 k)
    (cond ((null? lst1) (k lst2))
          (else (cp-append (cdr lst1) lst2 
                           (lambda (rest)
                             (k (cons (car lst1) rest))))))))

The continuation function for the partition function shall take two parameters.
The first one "accumulates" less than items, the second one greater than items.

(define cp-partition
  (lambda (lst p? k)
    (letrec ([cpp 
              (lambda (lst k)
                (cond
                  ((null? lst) (k '() '()))
                  ((p? (car lst)) 
                   (cpp (cdr lst)
                        (lambda (p-true p-false)
                          (k (cons (car lst) p-true)
                             p-false))))
                  (else
                   (cpp (cdr lst)
                        (lambda (p-true p-false)
                          (k p-true
                             (cons (car lst) p-false)))))))])
      (cpp lst k))))

And eventually, his majesty the quicksort:

(define quicksort
  (lambda  (lst less?)
    (letrec 
        ([qs
          (lambda (lst k)
            (cond
              ((null? lst) (k '()))
              (else
               (let ([pivot (car lst)]
                     [rest (cdr lst)])
                 (cp-partition 
                  rest
                  (lambda (x) (less? x pivot))
                  (lambda (less-than greater-than)
                    (qs greater-than
                        (lambda (sorted-gt)
                          (qs less-than
                              (lambda (sorted-lt)
                                (cp-append
                                 sorted-lt
                                 (cons pivot sorted-gt) k)))))
      (qs lst (lambda (v) v)))))

Although the testing based on random data is a Very Bad Idea, this was the easiest way to rough up my code.

(define (random-list max length)
  (letrec ([rl (lambda (length)
                 (cond ((= length 0) '())
                       (else (cons (random max)
                                   (rl (- length 1))))))])
    (rl length)))

(define (test-quicksort)
  (let ([tests-per-length 50]
        [random-top-integer 1000]
        [list-lengths '(0 1 10 11 25 40 64 128)])
    (for-each 
     (lambda (length)
       (do ([i tests-per-length (- i 1)])
         ((zero? i))
         (let* ([the-list (random-list random-top-integer length)]
                [lt-sorted-list (sort the-list <)]
                [lt-qsorted-list (quicksort the-list <)]
                [gt-sorted-list (sort the-list >)]
                [gt-qsorted-list (quicksort the-list >)])
           (when (not (equal? lt-sorted-list lt-qsorted-list))
             (printf "~a[<]:~n~a~n~a~n~n" the-list
                     lt-sorted-list lt-qsorted-list))
           (when (not (equal? gt-sorted-list gt-qsorted-list))
             (printf "~a[>]:~n~a~n~a~n~n" the-list
                     gt-sorted-list gt-qsorted-list)))))
     list-lengths)))

I tried to avoid racket specific constructs, but I'm not sure that one or two slipped in the testing code.

BTW, here a version with named-let:

(define quicksort
  (lambda  (lst less?) 
    (let qs ([lst lst] [k (lambda (v) v)])
      (cond 
        ((null? lst) (k '()))
        (else
         (let ([pivot (car lst)]
               [rest (cdr lst)])
           (cp-partition 
            rest 
            (lambda (x) (less? x pivot))
            (lambda (less-than greater-than)
              (qs greater-than
                  (lambda (sorted-gt)
                    (qs less-than
                        (lambda (sorted-lt)
                          (cp-append 
                           sorted-lt
                           (cons pivot sorted-gt) k)))))))))))))

Seems I already wrote on Quicksort...

Reverse in continuation passing style

A simple reverse in continuation passing style...

(define cp-reverse
  (lambda (lst)
    (letrec ([cpr (lambda (lst k)
                 (cond 
                   ((null? lst) (k '()))
                   (else 
                    (cpr (cdr lst)
                         (lambda (v)
                           (cons (car lst) (k v)))))))])
      (cpr lst (lambda (v) v)))))

This is a rather classical example, indeed. Performance wise it's much slower than the reverse builtin in PLT-Scheme/Racket, still it's a lot faster than even more classical trivial implementations such as:

(define (sl-reverse lst)
  (cond
    ((null? lst) '())
    (else (append (sl-reverse (cdr lst)) (list (car lst))))))

In fact the example relies on TCO modulo cons.

In order to test the whole thing in racket I used this snippet:

(define (print-times min max step)
  (for ([m (in-range min max step)])
    (let ([lst (for/list ([i (in-range m)]) i)])
      (time (reverse lst))
      (time (cp-reverse lst))
      (time (sl-reverse lst)))))

> (print-times 5000 10000 1000)
cpu time: 0 real time: 10 gc time: 0
cpu time: 5 real time: 61 gc time: 0
cpu time: 1320 real time: 2088 gc time: 1099
cpu time: 1 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 463 real time: 493 gc time: 185
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 21 gc time: 0
cpu time: 888 real time: 926 gc time: 505
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 2729 real time: 2766 gc time: 2235
cpu time: 0 real time: 0 gc time: 0
cpu time: 2 real time: 2 gc time: 0
cpu time: 2157 real time: 2227 gc time: 1522

Prolog Homoiconicity

Although when talking about homoiconicity the first language that springs into mind is Lisp (or a Lisp dialect), Prolog is a completely homoiconic language. In Prolog everything is a term. Variables, atoms, numbers are terms. And everything else is a compound term: e.g., foo(a, b) is a term. Lists are the main data structure of Prolog, and a list is a term as well. In fact a Prolog list is i) the empty list []; ii) a term '.'(a, b), where a is a term and b is a list or a variable. We say that a compound term foo(x, y) has functor foo and arity 2. Clauses (the prolog equivalent of "functions") are represented as terms whose main functor is :-, their head is a prolog term and their body is a prolog term as well. Moreover, the read predicate reads from file (or standard input) some prolog predicates. E.g., this simple Prolog program reads a Prolog program into memory (and the program is represented as a list of prolog terms):

read_all([Predicate|T]) :-
	read(Predicate),
	Predicate \== end_of_file, !,
	read_all(T).
read_all([]).

read_file(File, L) :-
	see(File), read_all(L), seen.

If we call read_file to read "read_file.pl" (spaces added by me):

?- read_file('read_all.pl', L).
L = [(read_all([_A|_B]):-read(_A),_A\==end_of_file,!,read_all(_B)),
     read_all([]),
     (read_file(_C,_D):-see(_C),read_all(_D),seen)] ? y

The display predicate some prolog interpreters provide gives us more insight on internal representation of terms. We call it on just one rule in order not to clutter the output with list representations:

?- read_file('read_all.pl', [H|_]), display(H).
:-(read_all(.(_932,_952)),,(read(_932),,(\==(_932,end_of_file),,(!,read_all(_952)))))

And here on the full program (notice... lists are "consed" with the '.' functor):

?- read_file('read_all.pl', L), display(L).
.(:-(read_all(.(_900,_920)),,(read(_900),,(\==(_900,end_of_file),,(!,read_all(_920))))),.(read_all([]),.(:-(read_file(_1410,_1430),,(see(_1410),,(read_all(_1430),seen))),[])))

Indeed, infix operators have been placed in prefix form like every other predicate (indeed, they are not special, just a parsing trick). Another "useful" predicate (not standard) is portray_clause/1, in order to do some "pretty-printing":

?- read_file('read_all.pl', [H|_]), portray_clause(H).
read_all([A|B]) :-
        read(A),
        A\==end_of_file, !,
        read_all(B).

The assert family of predicates can “store” into the Prolog database facts (this is very common, in fact, memoization is often implemented this way) and rules (this is done less frequently – and there may be a slight efficiency penality [CHECK]). Thus we can manipulate terms (indeed that is what Prolog is about) and load them as programs. Notice that I showed the read predicate only to show that “standard” Prolog programs are represented that way, but it is not necessary at all to use programs saved in files.

4 ?- assert((foo(X) :- bar(X), \+ baz(X))).
true.

5 ?- assert(bar(1)), assert(bar(2)), assert(baz(2)).
true.

6 ?- foo(X).
X = 1 .

A matter of homoiconicity

Somewhere around the late sixties the term “homoiconicity” has been introduced in the computer science community. In fact, the term was older and dates to the 1960, at least according to Wikipedia. Strangely enough, I did not find traces of the term homoiconic or homoiconicity in McIllroy [1]. I was not unable to recover the full text of the paper on TRAC [2]. However, widespread use of the term is due to McKay (along for the very idea of object oriented programming and a good deal of criticism on Lisp – perhaps I will look for some opinions of famous lispers on Smalltalk to make things even) in his Ph.D. dissertation.

The basic idea is simple: program is data. That is to say, the program is represented in the very same format as data. Thus, a program can manipulate programs (and even itself) in the same ways it uses for data. This is great and is the foundation for great and funny meta-programming.

Indeed, references on TRAC should make clear that a structured representation of programs is not needed. TRAC manipulated strings and programs where represented as strings. On the other hand, Lisp manipulates lists and a program is a list. It is quite rare in a discussion on programming languages with a lisper that he does not use the term “homoiconic” somewhere in the discussion, usually before becoming condescending (a proof of this is being developed actively – no trolls have been harmed during the experimentations).

What I find extremely interesting is that this great property was simply obvious in theoretical models. Universal Turing Machines and primitive functions need an enumeration of programs (functions, respectively) in order to manipulate such objects. If such enumeration was not possible, most computer science would not have been created.

The von Neumann architecture also relies heavily on instructions being represented as numbers and stored along with data. It’s a bit of a pity that this properties have not been naturally ported to programming languages (except from Lisp and some others).

Indeed, we all agree that homoiconicity is a great property in programming languages. In fact, I often find frustrating complete lack of it (e.g., Java is completely not homoiconic, since its main data structure is the Object but Java programs are not even near to being objects – ok, you can always call the compiler get an AST… but this is not what the whole thing is about). Other languages have limited support for it.

In Python functions and classes (and objects) are available when compiling a module. The whole decorator concept, for example, relies on the fact that functions are objects and can be passed as such at compile time. Very powerful meta-programming techniques in Python rely on “program” manipulation, where programs are represented as classes and functions (and not syntactically, like in Lisp). This makes some kind of manipulation very hard (without resorting to byte-code manipulation – and then the same objection with the java compiler/AST thing applies – or to basic string manipulation, which I would not consider as a symptom of homoiconicity, since strings are not “the main data” in Python). However, I would not rule Python out of the bunch of homoiconic languages, either. Perhaps “partially homoiconic” applies? Or perhaps do we need better built in tools to manipulate classes and functions in Python to qualify for the full homoiconic(tm) certification from old lisp hackers[3]?

References

1. McIlroy, M. D. 1960. Macro instruction extensions of compiler languages. Commun. ACM 3, 4 (Apr. 1960), 214-220. DOI
2. MOOERS, C.N. TRAC, a text handling language. Proc. ACM 20th Nat. Conf. Cleveland, Aug. 1965, pp. 229-246.
3. Not meant to be offensive… perhaps old could be replaced with ancient?

Missionaries, Cannibals and Prolog

Apparently, many generations of computer scientists have been concerned with the problem of letting cannibals and missionaries crossing a river with the very same boat.

Before them, logicians were looking for a way to have married couples doing the very same thing with slightly different inherent problems.

Centuries ago, the problem was that no woman should be with another man without her husband being present (this is now called a threesome). However, since women now are emancipated and nobody cares if a woman is with another man (with the possible exception of her own husband, especially when there are no football matches on TV), the cannibal problem seems more interesting.

It is widely accepted that if missionaries outnumber cannibals, they convert the cannibals. Since we believe in freedom of cult, no cannibal shall be converted. Someone may be familiar with another version of this problem, since once having people converted was considering a good thing, while having missionaries eaten was bad.

However, recently cannibals became vegans and until Churches will develop soy-missionaries the problem is how to let cannibals retain their own religion.

Basically, this is the job for a Prolog interpreter. Though humans solved this problem long ago, a human can only solve the problem for small numbers of cannibals and missionary (and though we hope both populations remain small in number, cannibals can always mate and missionaries can convert new people).

This is a short Prolog program that given an initial state (all cannibals and all missionaries on the same side of the river) and the desired final state (all cannibals and missionaries on the other side of the river), computes the strategy our poor bootman has to pursue in order to carry over the whole lot of people.

initial_state(mc, mc(left, bank(3,3), bank(0,0))).
final_state(mc(right, bank(0,0), bank(3,3))).

Above we say that the initial state has the boat on the left, three cannibals and three missionaries are on the left bank and no one is on the other one. The final state encodes what we have already said.

Now we have to describe possible moves:

move(mc(left, L, _R), Boat) :-
    choose_passengers(L, Boat).

move(mc(right, _L, R), Boat) :-
    choose_passengers(R, Boat).

choose_passengers(bank(C, _M), boat(2, 0)) :- 
    C > 1.
choose_passengers(bank(_C, M), boat(0, 2)) :- 
    M > 1.
choose_passengers(bank(C, M), boat(1, 1))  :- 
    C > 0, M  > 0.
choose_passengers(bank(C, _M), boat(1, 0)) :- 
    C > 0.
choose_passengers(bank(_C, M), boat(0, 1)) :- 
    M > 0.

Basically, when the boat is on the left bank, we choose passengers from the left bank. When the boat is on the right bank, we choose passengers from the right bank. We can only take 2 people on the boat. That means that, provided there is enough people on the bank, we can only carry 2 cannibals, 2 missionaries, 1 cannibal, 1 missionary or 1 cannibal and 1 missionary. Since the boatman is usually agnostic, the cannibal aboard with one missionary is not going to be converted.

The Prolog system choses one of the possible moves and proceeds. If the move is wrong, it back-tracks and tries another solution. Until the number of choices is small, it is rather efficient.

The predicates that describe how the system changes when one move is performed are:

update(mc(B, L, R), Boat, mc(B1, L1, R1)) :-
    update_boat(B, B1),
    update_banks(Boat, B, L, R, L1, R1).

update_boat(left, right).
update_boat(right, left).

update_banks(alone, _B, L, R, L, R).
update_banks(boat(C, M), left, 
             bank(LC, LM), bank(RC, RM), 
             bank(LC1, LM1), bank(RC1, RM1)) :-
    LM1 is LM - M,
    RM1 is RM + M,
    LC1 is LC - C,
    RC1 is RC + C.

update_banks(boat(C, M), right,
             bank(LC, LM), bank(RC, RM), 
             bank(LC1, LM1), bank(RC1, RM1)) :-
    LM1 is LM + M,
    RM1 is RM - M,
    LC1 is LC + C,
    RC1 is RC - C.

Eventually, we have to tell legal and illegal configurations apart. Basically, if in the bank we leave there are more missionaries than cannibals, we are breaking the law. If not, everything is fine (since the boatman works for free, so he does not have to pay taxes).

legal(mc(left, _L, R)) :-
    \+ illegal(R).

legal(mc(right, L, _R)) :-
    \+ illegal(L).

illegal(bank(C, M)) :-
    M > C.

The solution algorithm is trivial:

solve_dfs(State, _History, []) :-
    final_state(State).

solve_dfs(State, History, [Move|Moves]) :-
    move(State, Move),
    update(State, Move, State1),
    legal(State1),
    \+ member(State1, History),

solve_dfs(State1, [State1|History], Moves).

print_moves([]).
print_moves([M|Ms]) :-
    writeln(M),
    print_moves(Ms).

go :-
    initial_state(mc, State),
    solve_dfs(State, [State], Moves),
    print_moves(Moves).

We generate new moves and check if the updated state would be legal and if we did not get in the same state before (if it happens we are looping, the boatman becomes hungry and eats whoever is on his boat -- that’s the main reason why he does not travel with the empty boat).

The full source is here:

Using template programming for efficiency reasons

Suppose we want to write a

unsigned int pow(unsigned int n, unsigned int exp) 

function which computes the power of a given number.

A C implementation is rather trivial:

unsigned int
traditional_pow(unsigned int n, unsigned int exp) {

        unsigned int value = 1;

        for(unsigned int i = 0; i < exp; ++i) {

                value *= n;

        }

        return value;
}

Basically we could write the very same thing in C++. We could also perform some minor optimizations in the code in order to make it look more efficient. However, compilers are quite good in optimizing code. Indeed, they are better than humans.

Nonetheless, that function contains jumps. Notice that even though the exp parameter is known at compile time (which is a pretty common use-case), there is no way for the compiler to kill jumps short of doing a pretty expensive and thorough inter-procedural analysis. Which is not performed by gcc even using -O3.

The only result is having traditional_pow inlined in main. This is rather unsatisfactory: branching is among the more costly operations in modern CPU's.

We could try a recursive implementation:

unsigned int
traditional_rec_pow(
        unsigned int n,
        unsigned int exp,
        unsigned int acc) {
        switch(exp) {
                case 0: return 1;
                case 1: return acc;
                default:
                return traditional_rec_pow(n, exp-1, acc*n);
        }
}

unsigned int
traditional_rec_pow(unsigned int n, unsigned int exp) {
        return traditional_rec_pow(n, exp, n);
}

Here we are using an accumulator (a standard functional programmer's trick) in order to make the function tail recursive. With mild optimizations turned on, code generated for traditional_rec_pow looks like a less optimized version of traditional_pow (tail recursion is eliminated, though). Full optimizations yield a 74 lines long version of the function, where some special cases have been optimized.

We are very far from the intuitive idea of full optimization of pow if exp is known at compile time. We think that the compiler should be able to produce the very same code it would for the expression:
n * n * n * n * n * n

in case exp==5.

I promise you: we can do that.
I wrote the recursive functional version as an introduction to a templatic variant. The idea is that if exp is known at compile time, it can become a template parameter.

The structure remains similar, with template specialization used instead of explicit switch/if. This is even more readable for a functional programmer!

template<unsigned int exp> inline unsigned int
pow(unsigned int n, unsigned int acc) {

        return pow<exp-1>(n, acc*n);

}

template<> inline unsigned int
pow<1>(unsigned int n, unsigned int acc) {
        return acc;
}

template<> inline unsigned int
pow<0>(unsigned int n, unsigned int acc) {
        return 1;
}

template<unsigned int exp> unsigned int
pow(unsigned int n) {
        return pow<exp>(n, n);
}

Note that we give special cases for exp==1 and exp==0. They are needed because otherwise compilation would not terminate (well, it terminates with an error for implementation reasons).

Here some computation is implicitly performed at compile time. Suppose in the body of the main we call

pow<3>(3);

With no optimizations, the compiler generates some functions. There is the pow<1> specialization (which basically returns acc). Acc is the second parameter and according to OS X intel conventions that is 12(%ebp), while the return value is in %eax:

.globl __Z3powILj1EEjjj
                .weak_definition __Z3powILj1EEjjj
        __Z3powILj1EEjjj:
        LFB13:
                pushl        %ebp
        LCFI0:
                movl        %esp, %ebp
        LCFI1:
                subl        $8, %esp
        LCFI2:
                movl        12(%ebp), %eax
                leave
                ret
        LFE13:
                .align 1

For each exp value greater than one a function is generated. Each of this functions calls the one "before":

.globl __Z3powILj2EEjjj
                .weak_definition __Z3powILj2EEjjj
        __Z3powILj2EEjjj:
        LFB19:
                pushl        %ebp
        LCFI3:
                movl        %esp, %ebp
        LCFI4:
                subl        $24, %esp
        LCFI5:
                movl        12(%ebp), %eax
                imull        8(%ebp), %eax
                movl        %eax, 4(%esp)
                movl        8(%ebp), %eax
                movl        %eax, (%esp)
                call        __Z3powILj1EEjjj
                leave
                ret
        LFE19:
                .align 1
        .globl __Z3powILj3EEjjj
                .weak_definition __Z3powILj3EEjjj
        __Z3powILj3EEjjj:
        LFB18:
                pushl        %ebp
        LCFI6:
                movl        %esp, %ebp
        LCFI7:
                subl        $24, %esp
        LCFI8:
                movl        12(%ebp), %eax
                imull        8(%ebp), %eax
                movl        %eax, 4(%esp)
                movl        8(%ebp), %eax
                movl        %eax, (%esp)
                call        __Z3powILj2EEjjj
                leave
                ret
        LFE18:
                .align 1

Notice that __Z3powILj3EEjjj(pow<3>) calls __Z3powILj2EEjjj(pow<2>), which calls __Z3powILj1EEjjj(pow<1>). A part from this, most instructions deal with the stack (in order to create and destroy the current function stack frame) and multiply the first parameter for the second one, passing the result to the subsequent call.

Notice that no function contains conditional operations, tests or jumps a part from the call to the subsequent function in the chain. This is the kind of things optimizers shine on.

Indeed, even -O does the right thing. All the functions are inlined and the generated code is (not considering stack operations):

movl        8(%ebp), %eax
movl        %eax, %edx
imull        %eax, %edx
imull        %edx, %eax

Wow! This is how we would have written by hand. Notice that if we have multiple pow<n> calls, specialized ( and optimized code) is generated for each variant. For example this is for pow<11>

.globl __Z3powILj11EEjj
                .weak_definition __Z3powILj11EEjj
        __Z3powILj11EEjj:
        LFB17:
                pushl        %ebp
        LCFI0:
                movl        %esp, %ebp
        LCFI1:
                movl        8(%ebp), %eax
                movl        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %eax, %edx
                imull        %edx, %eax
                leave
                ret