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.

Good and not so good reasons to learn Java (or any other language)

The first thing to consider is there is really not such a thing like a reason not to learn a programming language. Or better, there is only one reason: lack of time. Learning a language is a tricky business[0]. Learning to use a whole platform is way trickier.

Please notice that some of the reasons presented here are general enough to be applied to any programming language (especially the bad reasons to learn a language). Others are specific of Java (especially the reasons to learn it).

Also keep in mind that the good reasons to learn Java will be presented in another post because this one is becoming far to long to be readable in the few minutes I feel entitled to ask you, dear reader. So believe me... you probably should learn Java. Still, not for the reasons I list here.

Not so good reasons to learn Java

It is widespread

You may be lead to think that since Java is a very widespread language, it is easier to find jobs if you know it. In the case of Java there is the question that I am convinced that it is not a bad thing to know Java and that can have pleasant effect on finding jobs (more on that later), still I would not consider it a good reason to learn Java.

Learning a widespread language means more jobs and more applicants. What really matters is the ratio between jobs demand and offer. And usually for very widespread languages it is not always very high. Skilled, experienced and "famous" developers do not care much. The others should.


It is object oriented

This and the variant "it is more object oriented" are clearly wrong reasons. There is plenty of good object oriented languages. And it is rather hard to decide which is more object oriented (lacking function looks more like a wrong design decision than a clue of being more object oriented).

Besides, I'm not even sure that being more object oriented is good (or bad for what matters). Well... not sure that being object oriented is inherently good either. Maybe in ten years the dominant paradigm will be another. Maybe in two. Three years ago "functional programming" was murmured in closed circles and outsiders trembled in fear at its very sound.

No, joking. Most people thought that "functional" meant having functions (and possibly no objects) and thought about C or Pascal. They did not know it was about not having crappy functions. Yeah, more than that, of course, but that's a start.

It is a good functional language

Just checking if you were reading carefully...
That is a bad reason because it is not true!

It is fast/slow

Oh, come on! Java implementations are decently fast, faster than most other language implementations out there and usually slower than implementations of languages such as C, C++, Fortran. Still, for some specific things it may be nearly as fast or faster. Sometimes it is not only CPU efficiency that matters.

It is good for concurrency

The "classic" Java threading model sucks. It's old. Nowadays other ways of doing concurrency are better (more efficient, easier to use).

Such more efficient easier to use methods are built-in in languages such as Clojure (or Scala, or Erlang). Still, Java is probably the most supported platform in the world. Such concurrency models are not inside the language, but you may have them using libraries.

Sometimes this is a real PITA (language support is a great thing, because the syntax is closer to the semantics).

Moreover having the "older" concurrency model visible may be a problem with the newer stuff. And some other libraries and frameworks may just assume you want to do things the old way.

It is good for the web

Ok... most people do not even know how widespread is Java on the web. In fact, it is. But is it really good? I do not really think so. There is lots of good stuff in Java world for the web, of course. The point is that there is also for other platforms. Here Rails and Django spring to mind.

Moreover, there is loads of extremely cool stuff coming from the functional world. Erlang and Haskell have some terrific platforms. Scala and Clojure also have some extremely interesting stuff and can leverage mature Java stuff but make it really easier to use.

Grails (web framwork) may seem on the same wavelength, still I think there is a very important difference. First, I don't like Groovy at all. In fact Groovy very author says that he would not have created it if he knew Scala. And of course since I do not like Groovy, I do not see why I should be using Grails, which, as far as I know, does not offer killer features over Rails or Django.

Scala and Clojure are different. They are not just "easier" than Java. They teach a different way of thinking and approaching development. And of couse, they are great for the web also.

I already know it a bit

This is quite an interesting point. Why, if you know a language a little, shouldn't you learn it well? This essentially makes it clear the difference between a not so good reason to learn something and a reason not to learn it.

The point is simple: if you are interested in learning Java (for the good reasons), do it. But from knowing a language "a bit" and knowing it "well" there is quite the same distance that from not knowing it and knowing it well. So don't do it because you think your prior experience may be extremely relevant.

There are languages which are just easier to master (where easier means that to learn them from scratch it takes less time that to become as proficient in Java as you would learning those languages -- yeah, Python, Ruby, [1]...)

Besides, I feel that the second step in Java is rather hard. I think that Java is very easy to learn for experienced developers (it is not a joke). The very first step in Java is relatively easy (a part from lots of useless crap like having to declare a class to put there a static main method and overly complicated streams). The step just after that, the one that takes you from writing elementary useless programs to writing elementary useful programs is quite harder, since lots of useful stuff in Java requires to understand OO principles quite well to be used without too many surprises.

So, you may have learnt Java at the college. Still, if you to hack something and "grow" there are languages that let you do it faster (Python or Ruby).

I have to

This is the worse possible reason because I don't see the spark in it. You have to. You probably are an experienced developers that got bored to death reading this post, you did not know Java and you have to learn it. Maybe your boss wants you to do some Java.

I'm sorry for you. Java is not easy to learn (especially to learn it at the point you can work with it). Mostly because everybody has been doing Java in the last fifteen years. Smart people and dumb people.

As a consequence there are truly spectacular pieces of software it is a pleasure to work with and worthless pieces of over-engineered crap. I truly hope that you are going to work with the great stuff.

Still I consider a "bad reason" to learn a language, because you are probably not going to enjoy the learning process. If you were, you would have used a different sentece... like "I want to".
And perhaps the thing would have been "My boss gives me the opportunity to increase my professional assets learning this new technology, Java".

It was easier to download/find a book/my cousin knows it.

One of the most popular reasons people pick up a language is because they find it installed on their system. That is not usually the case for Java, in the sense that usually the JDK is not installed, even if the VM is. Variants of this argument are a friend proficient in the language or, more frequently, availability of books at the local bookstores. This kind of arguments usually apply for complete programming beginners or people who had prior experience that has not been refreshed for years (e.g., old Basic programmers).

It is true that it is easy to find manuals for Java. The point is that not every manual is a good starting point. Specifically, this kind of user really needs a manual targeted at a true beginner. Unfortunately, that is the category of books where more craps piles. First beginners usually do not really understand if the manual they are using is crap.

If their learning process is too slow (supposed that they see it) they usually blame: (i) programming in general, (ii) the language or, worse (iii) themselves. Well, the language may have its faults (especially in the case of Java, still C++ is worse for a beginner), but it is important to understand that the culprit is usually the manual.

The funny thing is that the people who know how to tell apart a good manual from a bad one are usually the ones that do not really need an introductory book, are probably not going to buy it and more often than not are not enquired about a good manual. So unless their cousin is actually a skilled programmer, beginners are really risking buying a bad manual. And please, notice that even skilled programmers are susceptible to a similar argument: if you are interested in a new language and you read a terrible manual you may build a wrong opinion on the language (and perhaps you are not interested in spending another 40 gold coins to convince you that the language is really bad).

So please: read reviews on Amazon (or similar site -- notice that I'm not going to suggest to buy from Amazon, even if I often do and I am an associate -- here I'm just saying that the amount of reviews on books on Amazon -- com -- is usually large enough to make an idea). Find people that are experts and have teaching experience: their reviews are probably the one to base the judgment upon. Then buy the book from whatever source you want.

So do not buy a Java book because you can find books on Java and not on Clojure[2]/Python/Ruby/Whatever[3]. Choose the language (this is hard), choose the book (this is easier), buy, read it, study it, code code code.


---

0. I kind of found out that for people really convinced that learning a language is easy one or more of the following apply:
   
   1. have an unmotivatedly high opinion of their knowledge of the languages they claim to have learned
   2. have a very inclusive definition of "learning" a language (e.g., writing hello world in it)
   3. only know and learn very similar languages (really, if you know C++ it's gonna be relatively easy to pick up Java, if you know Scheme probably Clojure is not going to be a big deal, etc.)
   4. and tend to write "blurb" in every language they know (so for example they write Python as if it was C++ -- and usually are very surprised when things go badly)
   Of course there is also a lucky minority for which learning languages is very easy.
1. It is funny that I am suggesting to learn only "object oriented dynamic" languages such as Python or Ruby. I understand that many advocates of functional programming may disagree. But I somewhat think that while some kind of people greatly benefit from learning a functional language as the first language they truly master, many others are just not fit for functional programming because it is too abstract and working imperatively may be easier for them. As a consequence, languages such as Python or Ruby may naturally lead you towards functional programming if it is the kind of stuff you like, but are still usable if you are not that kind of person. I have seen things...
   And yes... if you are the kind of person that likes functional programming, you will get into functional programming sooner or later. This is just a bit later. 
2. Notice Clojure here...
3. Whatever is not a language. Still, it would be a great name for a language. Maybe not.

Scheme Rant, but a bright future lies ahead!

Is this the best moment for scheme ever? First of all, I have to admit that although I quite studied the language in the last years, I'm a bit outside the spirit of the community. My impressions basically come from some discussions I have with more experienced schemer friends and reading stuff on the web.

I have often wrote about my difficulties with finding a satisfactory scheme environment. Essentially problems boil down to two things:

1. I have very high expectations for programming environment (batteries included, etc.)
2. I have very high expectations on Lisps, probably because every lisper I met spent a great deal of his non-programming time saying how lisp did this and that 30 years ago. So I expect to do it now, to do it fast and to do it well.

The issue with the first point is that I'm mostly used to programming environments which are mostly unique. Python is just Python. I use the very same interpreter everywhere, I know what it does, which features are supported and which ones are not. Same thing for Clojure or Erlang and nowadays mostly true for Haskell. I avoided the issue with C/C++ being rigorously adherent to the standards or to very minor gcc extensions (and by the way, I'm always using gcc).

On the other hand in Scheme there are many implementations and there is not a clear winner. There are implementations which are "worse" than others, but among the good ones it is hard to choose.

The problem is especially significant because I somewhat got into a period of transition between R5RS and R6RS (which are two standards). I somewhat lived something like that with C++, but at least back then there was clear consensus that pre-standard C++ was unarguably worse than post-standard C++.

Essentially, R6RS came out in the mid 2007 and I started learning Scheme not much afterwards. Moreover (here discussions with my friend kick in) a large part of the Scheme community did not like the standard, feeling that the new language was too large (plus strictly speaking it should lack a REPL).

After reading Dybvig's 4th edition Scheme book I found that mostly I like the new stuff. However, for some unfathomable reason I sticked with Gambit, which does not implement it. So, while I like the idea that Scheme was a little language which you use to build your language, I missed lots of R6RS features which just make to much sense for me (as an "application/library" programmer, instead than a "language programmer"). That, and the fact that if you want to toy with a new language, you do not want to re-implement merge-sort (unless you are are explicitly choosing that example to learn the language).

So there were lots of incomprehensions between me and the my scheme learning process. But I'm afraid that lots of non schemer may be feeling the very same stuff about it (and perhaps jump to clojure, which fixes that issues by default).

Some time later, the other scheme implementation I used became another language (and I'm looking forward to read the new No Starch Press book about it). So the more "batteries included" tool I knew in scheme, ceased to be scheme.

I think things would have been easier if I just picked up an R6RS implementation and stick with it. However, things went differently. Not that I do not like Racket, still I find ackward to code in Racket when I want to grok Scheme and code written in Racket is so often not very portable to other schemes (and that is why Racket is Racket). I'm not complaining about Racket: I think they did the right thing.

However, nowadays the Racket book is scheduled. And there is going to be a new standard R7RS. And they decided to define a "small" and a "big" language. And I really do believe this is wonderful because it would make clear exactly what to expect from either language also to newbies. Moreover, perhaps some of the more reasonable improvements with less reaching implication which R6RS will be added to the small language as well. E.g., how to define libraries and generic information about what to expect from the "platform". Or maybe "values" related stuff.

So, in essence, I think in the future it will be a great time to learn scheme. Maybe I will have the courage (and the time) to re-learn it from scratch and fix all my miscomprehensions which came from the way I originally learned the language.

Does Perl suck? (and something about this Quorum Language)

The short story is that a group of researchers created yet another language. And I see nothing wrong with that. Most people sooner or later implement their own language (or wish to); researchers just do it more often. These languages usually have specific goals and some of them become widespread programming languages. Other remain academic toys. This particular language was created to be intuitive and easy to use. And the researcher meant to make it intuitive and easy with usability studies. I will comment on the idea later.

Fact is, that they put out a paper which compared their Quorum language with Perl and another language they designed to be bad. And they claim that the accuracy rates of their users were similar for Perl and Randomo (the bad language) and worse than Quorum.

Does Perl suck?

The question is that the story became very popular because of this: because they claim to have scientifically proved that Perl sucks. And such pieces of news have huge diffusion. The essence here is that I do not think that the results are so very relevant: they used only the easy part of Perl. As a consequence, I think that many other languages would have scored similarly. And think about it... if the easy part of Perl is hard for novices... what about the hard one?

As far as I can tell, the thing is mostly a syntactical issue. I haven't found papers on the full semantics of Quorum. From the examples in the paper, it looks like the illegitimate child of Ada and Ruby. I'm sure that I'm missing something, but it is mostly a matter of substituitions like:

for -> repeat [ which other major language had a repeat statement? ]
float -> number [*very* clear, especially before explaining the noobs how much different are floating point numbers from real numbers]

I don't consider it particularly readable. On the contrary to me something like:

  if d > e then
    return d
  end
  else then
  return e
  end
  

looks like a walking syntax error. I think I would take lot of time to convince me that it is proper english. I'm not a native speaker, but to me:

  if something is true, then do this, else do that
  

sounds quite more convincing than:

  if something is true, then do this, else then do that
  

All considered, it seems to me that they are optimizing the easy part of learning. The syntax is an issue in the first like 2-3 months of programming. After that the problems become semantic and theoretic. Computer Science is hard. It is not the syntax of the programming language you first learn to program with that makes it easier.

To me, it looks like they would use sponge rubber balls to make rugby less violent, completely ignoring the full contact issue.

Besides, I believe that most people who have serious issues with the syntax of todays' programming languages would also have problems with the semantics and with calculus and lambda calculus and whatever hard stuff is taught in the courses. Moreover, hiding the complexity is not always a good thing.

In a computer we can't represent a real number. We know that. At a given point in our curriculum, we also know exactly why. However, usually the odd behavior of floating point number strikes. Odd in the sense that people usually expect them to behave like real numbers. They do not.

A popular surprise is in Python when they use the console to make operations. In older Python versions, a number was printed just how it was in memory.

>>> 1.1
  1.1000000000000001

and guess what... this is extremely surprising for noobies (and in Python 2.7 the algorithm changed so that the printed number tries to be more 'intuitive' and in the case just prints 1.1). The fact is that 1.1 cannot be represented in memory (as a floating point number) and an approximation is used. This is quite hard stuff.

Pretending that floating point numbers are not floating point numbers is going to lead to disaster as soon as things get rough. So, I while I think there are far easier languages to learn to program with than Perl (Python, Ruby, Scheme) I don't think that Quorum is such a huge advantage past the "very very noob - why this does not compile if(foo); {...} else; {...}" part. And that is not the part to optimize.

And what about quorum?

Unfortunately enough, I do not know very much about usability. So I really cannot comment their methods. However, I think that I can say a couple of things from the point of view of language design. The first thing is that most languages that I think are worth learning and using have some very complex stuff and that stuff is what makes the language powerful. With powerful here I mean that it gets the job done quicker, with less line of code and, why not, shapes the programmer's mind in good ways, giving him insight.

Remove this advanced stuff and you have only dumb ugly languages. Such languages would not make you or your programs better. Remove first order functions and macros from Lisp or Clojure and you are just coding Pascal.

And I'm not exactly sure that "usability" can be applied to programming language design. Some argue that since most "experts" disagree on which features should be added to a programming language (and agree that having them all is a bad thing), such studies are needed to determine how to build the one and "true" language. And I have to say that I disagree.

Democracy plainly does not work in technical issues. Noob programmers are plainly not entitled to discuss about advanced language features that they have not yet the experience to understand and which solve problems they have not yet encountered. So called "professional" (i would say business) programmers do not care about the programming language, be it Java or Cobol. They probably would not have advanced features either, because they may thing such features would slow their juniors down. They mostly care about powerful libraries: the discussion is not at the language level, but at an architectural level. They don't do algorithms, they have to make complex under-documented systems interact and work correctly.

So we have just people who "love" programming languages. People who have a strong opinion on how a programming language should be. And guess what? We disagree. Some of us prefer Ruby to Python. Someone else thinks they are the same and that Haskell is the best.

The simple decision of creating an object oriented imperative language is a very strong assumption. I could not rationally say that object oriented is easier than functional programming. Not even if I thought it. And you can't ask noobs if they prefer functional languages (which they do not know what they are), nor you can ask business programmers (which probably dislike them). And if you ask to object zealots, they will answer that FP is just harder.... however, if you ask to functional programmers, they will say that FP languages are easier.

There are lots of design issues which are too bloody architectural to be decided with statistics.

Regarding the Quorum language itself... I strolled through the library files. And what? I changed my initial opinion... its more something between VisualBasic and Java. It has generics. Which are one of the things which are bloody harder to understand in Java (especially if you throw in extends, ? and company). And if you don't, you have a type-system that cannot express some perfectly useful stuff.

It has packages and includes (they are just called 'use'). The nice thing is that Java without an IDE is a PITA partly because of the redundancy of the interaction between classpath/packages and directory structure. And as far as I can tell that stuff is still there. Not sure that being strongly typed makes things easier for the noobs too.

Well, good luck then... my first impression is that it is basically Java without some nice stuff and a visual basic-ish syntax. On the other hand the compiler code looks very well written (still... writing compilers in Haskell/scheme is just so much easier than doing that in Java)... but really: in 2011, with everybody re-discovering the merits of functional programming (Clojure/Land of Lisp/Learn yourself Haskell/Racket/.../C# being more functional than ever/Erlang)... do we need yet another object oriented language?

On monads and a poor old (dead) greek geek

After immensely enjoying the LYHFFP book, I immediately started playing with Haskell a bit. Since lately I have been implementing sieves in different languages, I found that the Sieve of Eratosthenes was an excellent candidate. In fact, there are quite a few Haskell versions out there (and almost all of them are faster than the version I'm going to write, but this is about an enlightenment process, not an algorithm implementation).

Bits of unrequested and useless background thoroughly mixed with rantings and out of place sarcasm

I also had to reconsider some of my assumptions: I was familiar with Turner's "version" of the sieve and O'Neill's article, which was basically about Turner's version not being a real implementation of the sieve and about not everybody noticing that for like 30 years (and teaching that to student as a good algorithm). I found this story extremely amusing, in the sense that sometimes functional programmers are quite a bit too full of themselves and how cool is their language and overlook simple things.

Turner's algorithm essentially was this:

primesT = 2 : sieve [3,5..]  where
  sieve (p:xs) = p : sieve [x | x<-xs, rem x p /= 0]

And essentially here the point is that to me it does not really look like a sieve, but like a trial division algorithm. Quite amusingly I found a lengthy discussion about that here. The good part is that they rather easily (if you read Haskell as you drink water) derive optimized versions of this algorithm which have decent algorithmic performance and then take some lines in trying to convince us that the code above should not be called naive (which I do not intend as an insult, but as a mere consideration) and that should be regarded as a "specification".

Now I quite understand that declarative languages are excellent tools to write definitions of mathematical stuff (and Haskell is especially good at this), but as far as I know the context in which the one-liner was presented is that of an algorithm, not of a specification.

Essentially this unrequested bit of background is just to retaliate against the world for me not being able to come up with a really fast implementation. Basically the optimized version of Turner's algorithm is quite faster than my monadic versions. Which is fine, as my goal was to get some insight on monads, which I think I did. More on this here.

On the author's unmistakably twisted mind


So... back to our business. I struggled a lot to use Data.Array.ST to implement the sieve. Essentially the point is that I find the monadic do notation quite less clear than the pure functional notation with >>= and >>. This is probably a symptom my brain having been corrupted by maths and myself turning in a soulless robot in human form. Nevertheless, I finished the task but I was so ashamed I buries the code under piles of new git commits.

Essentially, I found mixing and matching different monads (like lists) excruciatingly confusing in do notation. Notice, that was just *my* problem, but I just had to struggle with the types, write outer helper functions to check their type and so on. Basically I was resorting to try and error and much shame will rain on me for that. So I threw away the code and started writing it simply using >>= and >>. Now everything kind of made sense. To me it looked like a dual of CPS, which is something I'm familiar with. The essential point is that the resulting code was:

1. Hopefully correct.
2. Written in one go, essentially easily
3. Rather unreadable

So the resulting code is:

Essentially for (3) I decided it was time to use some do notation. Perhaps things could be improved. What I came out with is a rather slow implementation, but I am rather satisfied. I think it is extremely readable: it retains a very imperative flavor (which is good in the sense that the original algorithm was quite imperative) and I believe could be written and understood even by people not overly familiar with Haskell. It almost has a pseudo-code like quality, wasn't it for some syntactical gimmicks like "$ \idx ->".


Somewhere in the rewrite process I left out the small optimizations regarding running to sqrt(lastPrime) instead of just to lastPrime, but this is not really the point. Still... I'm quite happy because I feel I now have a better grasp of some powerful Haskell concepts.

However, I feel like Clojure macros are greatly missed. Moreover, I found really easier to understand the correspondingly "difficult" concepts of Clojure or Scheme (a part from call/cc which kind of eludes me, think I have to do some explicitly tailored exercises sooner or later).

I also feel like continuously jumping from language to language could lead to problems in the long run, in the sense that if I want to use some language in the real world I probably need more experience with that particular language, otherwise I will just stick with Python because even when sub-optimal I'm so much more skilled in the python platform than in other platforms.

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

Clojure Macros: Wanted and Unwanted Symbol Capture

Introduction

No language is perfect. Most languages do not even come close. Some give the programmer the tools to bridge the gap between his idea of perfection and the actual language. Most of these tools are under the "meta-programming" umbrella, and macros are probably the more powerful.

Macros are dangerous tools, indeed. Most articles, books and posts on macros mention somewhere not to abuse macro usage, because they make the programs less clear (TODO: mention somewhere not to abuse macro usage; DONE).

One of the trickiest part is avoiding unwanted symbol capture. Here the the Lisp world divides: some think that symbol capture should be syntactically banned (or something like that), some believe that it is the programme's task to avoid unwanted symbol capture (with the underlying assumption that wanted symbol capture is fine).

I’m not usually happy when a feature is designed not to let me do something; well, quite depending from that something, indeed. I’m not at all concerned with higher level languages not letting me hacking directly with memory; but as far as I can tell, that is more a question of “language model” than of “designing a language not to let me do something”. In fact, Hoyte goes a long way in motivating that symbol capture is not a bug, but a feature.

I believe he is right. I do not find it hard to find situations where I want symbol capture to occur. Of course, in his book, he gives plenty of examples about that; but that’s not the point. I am limiting this to the context of clojure.

Clojure

First, clojure has a nice feature to make it easier to avoid unwanted symbol capture without actually forbidding that. I’m talking about placing a # at the end of an identifier to gensym a new symbol. This is nice to have, nice to use, nice to understand and solves brilliantly the common cases.

But the point is wanted symbol capture. In Clojure we have an interesting example: when creating a gen-class, the methods take an additional explicit parameter “this” (a-la Python, %s/this/self/gi). Like in Python, this is a conventional name, and could be called in any way; still, since Java has an implicit this reference to the current object, it is nice to maintain the convention.

This is a typical example when we explicitly introduce names. It is easy to understand, easy to write and that’s it. There is no capture involved, as we are simply using a function parameter. On the other hand, code in the proxy macro refers to the proxy being created with “this”.

It can’t be changed (as far as I know) since it is injected by the macro. In fact this is wanted symbol capture. The authors want to capture the symbol “this” in the client code and give it meaning. Looking at the code of proxy, it is rather explict.

Both approaches have their advantages: explicit this is easier to understand. Knowledge about how functions work is sufficient to read (and write the code). On the other hand, the proxy macro requires us to know something more: in fact it is a true “new” piece of language. If we did not know that proxy “magically” injects this, we could not understand/write the code. Probably we would say that the code is wrong as “this” should not be bound to anything there.

On the other hand, auto-this in proxies somewhat reduces code clutter. I have not a distinct opinion whether it is a good thing or if I’d prefer explicit this. Perhaps I’d prefer uniformity: that is to say, explicit this everywhere or implicit this everywhere. Though, that part of clojure is under active design and development.

Back to my macro abuses

This post started because of a macro I wrote. The first version is “clean” as it does not capture anything.

(defmacro let-attributes* [this state-method attrs & body]
    `(let [{:keys ~attrs} @(. ~this  ~state-method)] ~@body))

which would be used as:

(defn exp [this foo]
  (let-attributes* this state [bar baz]
    (println bar baz foo)))

Essentially it just wraps let+keys to provide a slightly terser syntax (in fact, I find it boring to use .state all the time; I have to say that it is one of the parts of clojure I like less). However, it is still rather verbose. I have to manually specify things I would rather not; in fact, in my code this is always called this and state is always called state, as I did not find a better name.

So I wrote a second version of the macro. A version that is not clean.

(defmacro let-attributes [attrs & body]
   (apply list 'let-attributes* 'this 'state attrs body))

And the usage would be just:

(defn exp [this foo]
  (let-attributes [bar baz]
    (println bar baz foo)))

In fact, is very dirty as it depends from the context where is expanded (which makes it different from the proxy macro). It assumes that “this” is bound to an object with a .state method. But is faster to write.

Here we can also spot the other problem with macros. I believe that every clojure developer is tempted to write his own macros. Macros that may solve similar purposes, but are inherently different. Code using such macros looks different at a different level than code which just uses different libraries and functions.

This is essentially the problem with fiddling with the language itself, which is what happens when we are writing a macro. Basically every time we write and use a macro, we are developing (inc clojure).

Amazon associates

"Let Over Lambda" (Doug Hoyte)

Technorati Tags: Clojure, Lisp, Programming

call/cc! I yield! Bah, lazy-seq.

Modifications

1. 03-01-2011: an additional scheme variant has been added.
2. 03-02-2011: minor modifications

Imperative Iterators

The archetypal implementation of imperative iterators are Java's subclasses of the Iterator interface. Everyone who has ever implemented an Iterator should acknowledge the pain that is to explicitly maintain state between calls. The essential problem is that the state has to be explicitly maintained. In particular there are two different concepts of state: the iterator "low level" state and the iteration state. In the iterator we have to save "what we have done" and explicitly do so.

Then every time next() or hasNext() are called, we have to do some more computation, save our internal state and return the control explicitly to our caller. This is the implementation of a Javish iterator in clojure to pre-order visit a tree like structure.

I decided to use Clojure instead of Java because the example structure was easier to write, the example could be just run in a REPL, i prefer Clojure to Java and other irrelevant details. However, that is essentially the way iterators are written in object oriented languages (included nice ones, like Python) or languages that have to interoperate with OO languages.

The principal issues is that the "value returning" logic has to be mingled with the iterator bookkeeping logic; I believe that this (although more versatile) is far more complicated that simply adding all the values in a (flat) structure and returning the structure. The reason why this is not the dominant approach is that it is less flexible and less efficient. We also notice that iterators can be infinite.

Ah, if you like OO mumbo-jumbo, this is of course the Iterator pattern.

Yield Statement

In this section we briefly examine Python yield statement. The corresponding yield expression (which essentially allows limited coroutines) is not considered here. If a Python function contains the yield keyword, its semantic changes.

The yield statement may only be used inside functions. A function that contains a yield statement is called a generator function.

[...]

When a generator function is called, the actual arguments are bound to function-local formal argument names in the usual way, but no code in the body of the function is executed. Instead a generator-iterator object is returned; this conforms to the iterator protocol[6], so in particular can be used in for-loops in a natural way.

[...]

Each time the .next() method of a generator-iterator is invoked, the code in the body of the generator-function is executed until a yield or return statement (see below) is encountered, or until the end of the body is reached.

If a yield statement is encountered, the state of the function is frozen, and the value of expression_list is returned to .next()'s caller. By "frozen" we mean that all local state is retained, including the current bindings of local variables, the instruction pointer, and the internal evaluation stack: enough information is saved so that the next time .next() is invoked, the function can proceed exactly as if the yield statement were just another external call.

Essentially instead of using the structure of the previous example, we could have written:

The idea is that when yield is encountered the generator "returns" the value and when next() is subsequently invoked, it resumes execution from that spot. Essentially it is a neat syntactical facility that "saves" somewhere the continuation of the computation in order to be ready to resume from that point.

call/cc

Ok. I said it. Continuation. That is. When the goal is to experiment with control, scheme comes to mind. This is our representation of the tree:

Now I provide an easy example for doing the preorder "functionally". The idea is to provide a function taking a callback function that is called on each element of the tree when is visited. The function also returns the return values of the callback function (in reverse order); anyway, use display as a callback function and we have our familiar example:

Here we did not use continuations. In the following example, I use continuations to save the state of the computation where to resume (after the yield) and to jump out (simulating python yield statement) with another continuation. I think this code should be written more clearly; I'm no expert with continuations (I usually find them too general), so suggestions are welcome.

When generator is called, it returns a function that every time that is called returns the successive element. It behaves like an almost like an iterator and has the structure of Python generator functions. Boilerplate code could be avoided using a macro. Essentially, lines 2-6 are boilerplate and similarly are lines 11-13 and 18. The difference with a "java like" iterator is that when there is no way to test if there is a "next" element (no hasNext method, closures are objects with just one method! ;)) and it returns null forever. So the implicit protocol is "do not put null objects in the tree" and if you get null, then you are done. Other strategies could be used, e.g., instead of returning the value, a list containing the value is returned; empty list means that the iteration completed; list containing an empty list meant that the tree contained a null valued node.

We could have used continuation passing style and that would perhaps have been more similar (even though far more complex to understand and write) than the corresponding Clojure way to do it.

In the comments a different scheme continuation based solution has been suggested by Marco. It is far more elegant than my original solution, but is structurally different from the Python code of the sections above. In fact, it does not use an explicit stack to manage the tree traversal (as both the Python version and my scheme version do), but relies on more recursive calls, essentially using the implicit call stack.

What about lazy-seq?

Essentially we specified that iterators are needed because they are efficient and more general. Indeed in languages such as Python, generators are an easier way to write iterators. What about Clojure? The example at the very beginning is not the way things should be done in Clojure. On the other hand the iterator in scheme would be a good API for Clojure as well. In fact it is the very same pattern that we have with map (Haskell programmers here may want to extend the discussion on "mapping" on different algebraic types, such as Trees, and not only Lists).

Imperative iterators are just a design pattern. Call/cc is a feature so powerful you can use it build almost every other control abstraction. Yield can be used to implement coroutines (which could also be implemented with call/cc). And what about lazy-seq? Lazy-seq is nothing like that. Many Lisp books show a simple example where macros are used to implement lazy evaluation (or at least list lazy evaluation, which is what matters most). lazy-seq basically does that. The difference is that other Lisps are usually not built around the idea of lazy sequences the way clojure is.

Consequently, most libraries and APIs do not work (or do not play well) with lazy evaluation. They could be made to work, but it is simply outside Common Lisp pragmatics, and there is not anything wrong with that.

But back to lazy-seq... why it is here? Consider the code below.

I want to point out the structure of the tree-seq-aux function. Indeed, the function is not recursive. It simply return a lazy-seq. The second parameter of the cons cell we put in the lazy-seq, is another call to tree-seq-aux. However, this is not recursion: when lazy-seq is evaluated, we already returned from the previous call.

But thing are even more interesting than this. That cons cell is somewhat similar to the iterator we saw at the very beginning. Its car (first) is the current value. It is "next". And what is its cdr (rest)? Suppose that our iterator was not stateful. Suppose instead that calling next() returns both the current value and another iterator which will provide the successive values. Well... basically it is our cons cell.

Pair<Value, ConstIterator<Value>> v = it.next();

That is essentially our cons cell. But in fact we somehow have the same pattern we had in the continuation based example. We "save" what to do next (akin to the jump continuation) in the cdr of the cons cell; however, we do not have to evaluate it right now because of the lazy-eval. As I already said, if we used continuation passing style, we would have placed the recursive call which we put in the lazy-seq cons cdr in the explicit continuation.

The advantage is that it is easier to write, easier to understand, easier to use. Unfortunately is much more specific and powerful. But I don't mind practical tools, when they have the elegance lazy-seq has.

Technorati Tags: Clojure, Lisp,Scheme, Python, Programming

Clojure: generating sentences given a grammar (part 1)

Introduction

The idea of this post is writing a simple sentence generator based on a given (context free) grammar. The idea and the program come from PAIP.

However, this is essentially only a starting point to present some philosophical differences of programming languages and to show how Clojure is every bit as versatile as Common Lisp (on this kind of problems) and perhaps some new built-in features make it an even more interesting choice for this problem.

Description of the problem

The problem here is simple: generate sentences in a small subset of english. Small is an overstatement; perhaps diminutive is more appropriate. At the cost of looking snob, I believe that many mainstream programmers may already be cowling in fear or, if skilled enough, they are looking for a library doing the task.

There is nothing wrong with the library approach. Moreover, it is probably the right choice for a "real" project, because it is certainly more versatile than the few lines we are going to write, more tested [well, actually not, as our piece of code is just a very close translation of some 25 years old program or so ]. Perhaps, more efficient.

Now suppose we are not meant to use external libraries. Unrealistic as it may be, consider that we want to learn something beside a new bunch of API's. Or maybe we just want a lightweight solution. Different approaches are favored for different programming languages.

I jump the stage in which the programmer writes a program specifically translating the example grammar. I believe it is clear from the specs that we want to generate sentences for every grammar with some prerequisites. As a consequence, we have just to represent the grammar in some format, read it, understand it and generate the sentences.

This is essentially a language interpretation problem: we have a "program" written in a given language (the grammar) and we want to interpret it (and generate the sentence). The language is not turing-complete, of course [ as we have decided that it should be a CFG, and consequently out interpreter machine needs not to be a turing machine ]. I read somewhere (which I mistakenly believed to be the Unix Programming Environment) that the authors strongly advised to transform generic problems into language interpretation problems. The idea is that this way it is easier to think at a higher level of abstraction (the one given by the interpreted language, not C); efficiency is probably not an issue either, as a specific domain language is likely to be more efficient than a general purpose interpreted language.

An example grammar is:

Sentence : Noun-Phrase + Verb-Phrase
Noun-Phrase : Article + Noun
Verb-Phrase : Verb + Noun-Phrase
Article : the, a, ...
Noun : man, ball, woman, table, ...
Verb : hit, took, saw, liked, ...

Implementation details

The question is how to represent the grammar. I believe that most Java programmers here are already mentally checking the API's of their favourite XML parser. Although in Clojure there are more appropriate data structures, I chose to represent it as a list of lists, as with the Lisp tradition. This has the advantage that examples prepared for PAIP program can be directly used without modification. Moreover, the size of the grammar is modest enough not to make it an issue. Besides, switching from lists to vectors does not lead to changes in the code.

I belive that here we can spot a very evident cultural difference. In the Java/OOP world the problem is two-fold. First we have to translate the grammar in data structures manipulable by Java, then we have to actually interpret them. The first part is essentially the task of a parser: for XML there are many parsers (but the syntax becomes very clumsy, IMHO); on the other hand it is possible to use parser generators such as Yacc or Antlr. The second part is also considered a serious issue: in fact in GOF's Design Patterns the Interpreter pattern exactly deals with these kind of problem. Their suggestion is to create a class for every terminal and non terminal. Please notice that we are not talking about the terminals and non terminals of the grammar (such as Sentence or Noun Phrase) but about the terminals and non terminals of the language in which we express the grammar (such as Rule, Alternative, Head and things like that).

It is interesting to notice how both problems in Lisp are non-problems. Lists and atoms provide a nice representation for the grammar itself:

(def *simple-grammar*
'((sentence -> (noun-phrase verb-phrase))
(noun-phrase -> (Article Noun))
(verb-phrase -> (Verb noun-phrase))
(Article -> the a)
(Noun -> ball man woman table)
(Verb -> hit took saw liked)))

The parser problem is completely solved. And the interpreter pattern just becomes some list processing. Less fancy for sure, far easier nonetheless. It is just list processing. Nothing more, nothing less.

This is essentially a straightforward translation of the original common-lisp variant. However, does the job. You can also experiment with different grammars.

Morale

Notice that here the key was not lisp homoiconicity. It is a feature which has not been used. A similar approach could have been used also in C (though grammars would have been impossible to share, unless a specific file based representation was developed). Here the key was just thinking in terms of a DSL.

This is not obvious. Some times ago I developed a toy Prolog program which generates imprecations and similar stuff. Unfortunately enough, this example did not immediately come to my mind. Instead I assumed that Prolog ease of development would be (alone) a time safer. It was not. Using the full language power to generate sentences proved to be far more complex than switching to a simple grammar representation + a bunch of procedures.

Future work

Right now, I'm trying to adapt the generate-all to Clojure. Indeed, although the straightforward translation actually works, it is not lazy, and consequently cannot be used with grammars generating an infinite language.

Books & Amazon associates

"Paradigms of Artificial Intelligence Programming: Case Studies in Common Lisp" (Peter Norvig)

"Unix Programming Environment (Prentice-Hall Software Series)" (Brian W. Kernighan, Rob Pike)

Technorati Tags: Clojure, Lisp, Programming

Clojure: on the perversion of condp

Yesterday, I discussed here some issues with removing too many parentheses. Today I especially deal with the awful perversion of condp. Apparently, removing parentheses from Lisp is a common pattern in modern Lisps. Arc seems to have taken the very same route, even though somewhat more extreme (e.g., let binds just one variable -- no parentheses needed --, with binds more than one and essentially uses clojure's let syntax). Anyway, back to condp... condp takes a binary predicate, an expression, and a set of clauses. Essentially instead of yesterday's example:

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

we could have written:

(condp = (class x) String :string Integer :integer)

The first thing it is that, in my opinion, it may be rather easy to mistake the first pair (which semantically is the binary predicate and the expression) with the successive conditions. The second issue is that condp can have an odd number of arguments: the last one is the default. Now consider the pathological example

(condp
  = (str x)
  (str String) (str y)
  (str Integer) (str z)
  (str k))

And suppose that for some unfathomable reason is written like:

(condp =
  (str x) (str String)
  (str y) (str Integer)
  (str z) (str k))

Ok... it is your mistake if you just don't format thing properly, but such a bug is much harder to spot than it should be. I understand that this example is extremely contrived. The problem is that having to resort on basically enumerating arguments to understand what is their function (that is to say if they are in an even position they have a function, if they are not they have another, and if there is actually a last argument things are even different). Things could be worse? They are worse. I forgot to mention that condp clauses have both a binary form and a ternary form. In fact a clause instead of :

value expression

can be

value :>> unary-function

The first thing to notice is that enumerating arguments becomes even messier, and a special syntax is to be introduced. Counting becomes messier because you have to remember if you got an even or an odd number of ternary clauses, which changes the meaning of being in an odd or in an even position. If we grouped things with parentheses, then it would be just a minor issue. Once you are familiar with ternary clauses, you won't be surprised that

((fn [x] (condp = (keyword x) :a :>> :b :>> :<<)) :a)

evaluates to nil. I believe that this is an example of how some good features in a programming language conjure to create very counter-intuitive behaviour (I'm a big fan of the principle of least surprise). Why? If we did not know of the ternary argument, one would thing that if (keyword x) is :a or :b then we get :>>, otherwise, we get :<<. This would be straightforward. Unfortunately[0], we do have the ternary clauses. Ok, but this does not happen. :>> is magic. You cannot (easily) have a condp returning :>> [which is something I think would be perfectly legitimate, and in case you have to resort to an expression which evaluates to :>>, like (keyword ">>")]. I love magic in programming languages, but the magic leaning towards abstraction. The kind of magic which makes complex things easy, not the kind of magic which essentially introduces a special case for something of dubious value. So, back to the expression... :a equals to :a, so that condition is chosen. But :>> is magic. Consequently :>> is not returned. Rather (:b :a) is evaluated. But remember, a keyword may be used to test inclusion; this is a nice programming language feature in many situation, but here it plays awfully bad with the other parts. So we are basically asking... is :b in :a? And the answer is nil. By the way, this does the right thing:

((fn [x] (condp = (keyword x) :a (keyword ">>") :b (keyword ">>") :<<)) :a)

If you are wondering whether parentheses would have fixe the issue... yes they would.

((fn [x] (condp = (keyword x) (:a :>> :b) (:>> :<<))) :a)

is clearly and immediately distinguishable from:

((fn [x] (condp = (keyword x) (:a :>>) (:b :>>) (default :<<))) :a)

Notes

0. It is not that I don't like the idea behind ternary clauses: I just believe that they should be in a separate conditional form. And if you just don't need a function for some of the clauses, clojure has an extremely neat syntax and you can just write #(do % val) or (fn [_] val); I believe that the latter is clearer.

Clojure, Programming, Lisp, Common Lisp, Scheme