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.

Clojure: writing tail recursive functions without using recur

Once upon a time, in the land of the Clojure, there was a brilliant student who enquired the nature of things and he for that he was greatly loved and appreciated by his teachers, for he was brilliant and asked about the nature of things and they could explain him the world. He learned about macros and first order functions and actors and software transactional memory and he was happy. But then he began to focus on the nature of recur and he felt that something was amiss and the way trampolines and functions interact made him wonder.

During a short holiday he was in Schemeland, and he saw that they did not use recur. They named the functions and called them with their name in tail position and that was the way they did. And he felt it was good. So he asked his Master:

"Why can the schemers call the functions in tail position and their stacks never end?"

And the Master told him that it was because their soil is fertile, while the land of the Clojure is just an oasis in the wastes of Javaland.

"We are lucky," he added, "for our land still gives us food spontaneously and the air does not drives us mad. And our spring is natural and not a framework. And if you do not like recur, you can always map, for or loop. Higher order functions and macros can help you to hide what you do not like, for you are the master of your own language."

For a while the student was content, still he had a recurring thought: functions can do everything and in Church he did not find recur but only functions. And so he learned Y. But Y is a demanding beast, for it requires functions to be defined awkwardly. And the student wanted to simply write:

(defn factorial [n acc]
  (if (= n 0)
    acc
    (factorial (- n 1) (* n acc))))

His Master saw him troubled and in pain, and one day a big application they were creating exploded with a StackOverflowError and he knew that unless the student was cured he could not be writing code with the others. So one evening, he told his student that if he really wanted to learn the secrets to make tail-call recursive functions run with constant stack usage, he shall go to the Land of Snakes, where they eat only Spam and Eggs, to look for some wise men and have them teach the secrets of creating tail recursion at language level. And he warned the student that the travel was dangerous.

The young student was frightened, because the Land of Snake is far away and he was barely aware of the perils that lurked in the shadow. However, his resolve was strong and he packed his things, an editor and few jars to survive the wastes of Javaland, and ventured forth. He travelled through the dull wastes where everything is private or protected and he has to ask things to do things for him. But as most people grew up in the land of Clojure, he knew that objects are but closure in disguise and he new how to bind them to his will with the power of the dot form.

After three days and three nights he eventually reached the Mines of Ruby and where massive gates blocked his way. He spoke the words as his master instructed (password: mellon), but the gate remained closed, for someone monkey-patched it and the door now spoke english, but the student did not know it and with failure in his heart he left the place, because he was trained in the ways of Lambda and could not cope with such a stateful abomination.

After months of wandering, he eventually reached Schemeland, where he at least could tail recur without recur. He spent another month drowning his pain into first class continuations and losing hope to ever come back to the land of Clojure, until one day he overhead the men telling tales at the tavern about a pythonista adventuring to Schemeland. The student sought the pythonista and eventually he found him and he asked him about the secrets of recursion and the pythonista showed him code and the student was happy because he knew classes are another word for closures and he was a master of closures. But he also understood that state was the missing element and he was saddened, because he also knew that state is treacherous.

Nonetheless, he felt he had come to far to be stopped by the formal purity of stateless programming and he eventually wrote the code. Little is known of what happened afterwards. Some claim he finally found his way to the lend of the Snake, after having extendedly monkey-wrenched the monkey patcher, other say that he went back to the Land of the Clojure.

I, your humble narrator, do not know the truth. I tried nonetheless to follow the student's step and implement myself the function that makes tail recursive calls without using recur. Ugly it is, and is indeed but an illusion, for recur lies inside the implementation. Still, it does the trick:

(defrec factorial [n acc] 
  (if (= n 0) 
    acc 
    (factorial (- n 1) (* n acc))))

And here the code:

(defn uuid [] (str (java.util.UUID/randomUUID))) 
 
(defn tail-recursive [f] 
  (let [state (ref {:func f :first-call true :continue (uuid)})] 
    (fn [& args] 
      (let [cont (:continue @state)] 
        (if (:first-call @state) 
          (let [fnc (:func @state)] 
            (dosync 
              (alter state assoc :first-call false)) 
            (try 
              (loop [targs args] 
                (let [result (apply fnc targs)] 
                  (if (= result cont) 
                    (recur (:args @state)) 
                    result))) 
              (finally 
                (dosync (alter state assoc :first-call true))))) 
          (dosync 
            (alter state assoc :args args) 
            cont))))))

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.

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.

Teaching Javascript and other languages (Scheme, Python, Clojure, ...).

Recently, I started working more and more with Javascript, and it happened outside the browser with node.js.

So far so good, I love node.js and I will consider it as a strong alternative to twisted. I think that the language has some extremely interesting features which I would like to see in Java as well. I'm probably biased: after all, I'm cold towards inheritance to say the least. In fact, I'm quite used to doing encapsulation with closures in scheme, and the fact that in Javascript I can just return objects of functions solves the classical problem of having to return a single function[0].

So I was thinking about a discussion I had with some friends from the Europython (and Python Italia) organization group. Someone made a point about using Javascript as a teaching language. The idea has its merits: Javascript is everywhere. A browser and and editor is enough to get started with programming. Moreover, the language is quite nice: many interesting programming techniques can be taught in Javascript (and more easily than, say, C++).

Then I considered what I learned in "Javascript: The Good Parts". The subset of Javascript I'm using is roughly the one suggested in the book. And that is nice. I'm basically leaving out the bad parts. However, a student probably would meet those parts soon enough and probably would not have the wisdom to avoid the bad parts (some of them are "easier" in the short term and discipline is something often newbies lack).

Moreover, it would be naive to assume that Javascript would be "well" taught. Many languages are taught badly (and students are often not very receptive of good suggestions).

Somewhat, it reminds me of pre-standard C: the language itself had many nice features [as a domain specific language to manipulate von Neumann machines at rather high level], however, there were plenty of rough edges (I'm thinking about C Traps & Pitfals: nowadays, many suggestions are granted, but back then it wasn't really that common).

Scheme (Racket)

All considered, other languages need something to be installed. Racket/scheme ranks pretty high as a teaching languages. SICP is an excellent book and Racket offers an easy to install/easy to use (easy to debug/easy to *) environment. The language is small and orthogonal and has features and abstraction which are hard to find outside the Lisp world. However, some concepts need some mathematical understanding: probably it is ok to assume such maturity at university level, but not before. Moreover, everything which could be of interest (GUI, threads, web, whatever) is just bundled.

Python

Python on the other hand is easier to start with. The mathematical maturity needed is lower, the language is probably easier. The abstraction level is good and there are lots of interesting functionality in the standard library. IDLE is a decent basic IDE and it is probably easier to find open source projects to which contribute. I just love Python, so I may be biased. Moreover, Python is easy to use to script the system (both Unix and Windows) and I believe that using a language to automate common operations is a great way to increase programming skills [useful programs are just more fun]. Ruby essentially has the same merits and problems of Python.

Clojure

About Clojure, basically it depends on Clojure Box. Without it, setting up a (free) easy to use environment is not as easy (I have seen newbies finding hard to make differences between the OS specific command prompt (cmd.exe or bash) and a REPL -- in python, I'm not talking about clojure --). That is the kind of ease of use we must reach (something like racket or IDLE) and the only way to get it with clojure is clojure box. Still it is a somewhat more complex -- though more powerful -- environment. The other problem I found about teaching Clojure is that it is hard to do without some prior knowledge of Java and also the official documentation is somewhat not very newbie friendly -- lack of examples are a [pun intended] clear example of that --.

On the other hand, it has all the advantages of scheme (a part that the language is somewhat bigger) with some further merits (IMHO swing >> wx, easy stuff to use from the Java world). The dependency from Java leads me to think that Clojure is more an excellent second language to "teach programming" to people exposed only to Java (and probably to the "bad parts of Java"). In this case requiring prior knowledge of Java is not a weakness but a point of strength.

----

[0] ok, there are other solutions in scheme, still I quite like to return {function: function, functionB: functionB}

Is state really bad?

Prologue

Actually this post was being written in March, when some facts referred in the body of the article actually happened. I am resuming the post today, after months of extensive (and rather unbloggable) work.

Intro

Stateful programming is somewhat the default strategy in the industry nowadays and it has been in the last 60 years. If we consider the 10 more widespread languages in the tiobe index (a statistic is worth another), they are all imperative languages strongly based on stateful programming. This month Lisp is has enormously improved (Land of Lisp anyone?), but even if we would consider Common Lisp and Scheme together, it would not go in the first 10 positions (even if just for a few points).

The Haskell case

In fact, in the last years we have witness an increase of interest in functional languages. As far as I remember, about 5 years ago there was a lot of hype about Haskell (which was in its 30's or something like that). It was related, as far as I remember, in a famous user-friendly linux distro having written some tools in Haskell and in the Darcs project. Darcs has almost disappeared with Git (Perl+C) and Mercurial/Bazaar (Python, Python+C) sharing the market of distributed versioning tools.

The case is rather interesting: Darcs was built with a very strong "theory" behind, the algebra of patches. The problem is that the merge process is still exponential in the worse case and that it is rather buggy. It is interesting that the software is both slow and bug ridden. It is tempting to infer something about Haskell, at least to counter the hypothesis that pure functional programming makes it relatively easy to write bug-free programs. Perhaps this should be taken into account the next time someone looks down on setf. Well, I do like Haskell, just not as much as I love Lisp.

The last thing I would like to mention is that I like the idea to insulate imperative code from functional/algorithmic code (but this is something I suggest with every language). However being forced to do that is not necessarily a good idea. In fact, it makes Haskell quite harder to pick up and has the paradoxical effect that if you are a developer good enough to code in Haskell, you probably already know how to separate side-effected code from side-effect free code. Besides, although I like purity (to some extent), I'm not sure whether state monads should be considered stateless. I mean, a state monad implements state in a nice functional construct, mathematically sound and pure. In fact they are almost seen as an executable transaltion of the declarative semantics of a stateful program. Consequently, I'm not sure whether frequent use of state monads is really an improvement over carefully used stateful programming.

In other words, although I admit my limited experience of Haskell in real world projects, I believe that if we think functionally the code is going to be clear (but it will be as clear in Haskell as in Lisp). On the other hand, if we think in a heavily stateful way, our code may be less clear in Lisp and quite messy in Haskell, where we would implement our (wrong) thinking having state monads pop out everywhere. Feel free to correct me, possibly with real experience and examples.

Erlang and Clojure

Erlang is different from Haskell in that functional stateless programming is required for practical purposes. In order to allow shared-nothing process based architecture (and the actor model), state is essentially banned. Of course, there are solutions which bring back state (ETS, DTS, plus various libraries such as mnesia). It is worth noting that this kind of state is generally different from usual imperative state.

In imperative languages everything is stateful by default. On the other hand, in this case, we basically have only "db like" solutions. This does not encourage real stateful programming, and in fact, usual Erlang programs are pretty much state free. The essential different is that they are not side-effect free.

Being state free and side effect free are two very different things. Having no side effects is pure functional programming. And is extremely hard to do. In fact, it would not even made sense in a programming language built around the idea of passing messages between processes. If you send a message, you are not side-effect free anymore.

Somewhat in the same sense, Clojure is stateless but not side effect free. Most clojure coding is performed without explicit state change and there are a few explicit ways to deal with state. This is done in transactional way, so that essentially state change is allowed if explicitly required. State change should not mingled with stuff which has effect outside the clojure process. You can "unset" a variable and recover the old value, but you cannot unsend a message.

At the moment I feel that I can easily tolerate (and like) the kind of state change insulation provided by clojure and the pragmatics of avoiding side-effected stuff for as long as possible typical of all functional languages. On the other hand, I find really hard to accept absolute stateless-ness.

Lisp and Languages with FOFs

On the other hand of the spectrum of "functional languages" we have Common Lisp and the various freedom languages where functions are first order objects (Python, Ruby, ...), with Scheme leaning a bit more towards the functional side. Technically speaking Python is not even a functional language. Surely it is not stateless (but Lisp is neither). In fact, in Python recursion is frowned in favor of iteration (but iteration is often built around generators, which are an user-friendly/dumbed-down[0] instance of anamorphism -- unfold --, which is strongly functionally flavored). On the other hand, some call Ruby the Matz-Lisp.
In these languages there is no explicit restriction towards stateful programming. This means that usual algorithms and way of thinking are easy to implement (especially in Lisp, both very functional and very stateful algorithms are easy to implement). On the other hand, restriction of state change is left to the sense of the programmer (which not always is a good thing, but I don't really like languages which tell me exactly what to do... they just have to make the better way obvious -- I'm not Dutch, sorry --).
To be sincere, there are just things that are so much easier in stateful programming than in stateless programming. And for other stuff the converse applies. Consequently, the language should not force me too much towards one style or the other. Moreover, stateless-only languages tend to be harder to pick up for beginners (on the other hand Python and Ruby are extremely easy to start with and I believe that scheme is a wonderful first language for computer scientists). Eventually, stuff like GUIs are really hard to implement in fully stateless settings (clojure essentially relies on Java underlying classes, and I actually have never used Erlang for guis -- not that I am a strong GUI developer --).

On performance

One of the consequences is that lots of algorithms, data structures and ideas are just developed with stateful programming in mind. This is the reason books suck as Okasaki's Purely Functional Data Structures have been written: just to bridge the gap between mainstream stateful programming and functional reasoning.

Unfortunately many algorithms have been created with imperative languages in mind, and the data structures supporting the algorithms strongly reflect the imperative setting. Implementing such algorithms in functional settings is usually inefficient to say the least. Much theory (and not only the practice) is built around state change. The Art of Computer Programming uses a pseudo assembly language which essentially manipulates a Von Neumann machine.

Something as easy as "modify an array" may be a source of inefficiency in many languages. E.g., clojure provides transients just to make it easier to express such operations. On the other hand functional languages have usually some troubles in providing a data structure that is immutable, offers O(1) random element access and allows element modifications without copying the whole data structure.

Books

"Purely Functional Data Structures" (Chris Okasaki)

"Art of Computer Programming, The, Volumes 1-3 Boxed Set (3rd Edition) (Vol 1-3)" (Donald E. Knuth)

Notes

[0] depends on whether you are a python or a scheme programmer: python programmers usually say user-friendly

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

Clojure: great exploratory programming

One of the major drawbacks of Java development is the almost complete lack of a REPL. All my favourite languages have a REPL, and I have to say that I've grown completely accustomed to it. I almost can't do without. The possibility to explore new libraries step by step, perhaps with some features common on IDEs (and some more, as it's runtime), is invaluable.

It is hard to understand how the lack of a REPL cripples the learning process of the language (in the first place) and of libraries without having extensively used a REPL. Java somehow compensate this with extensive IDE support; it is possible to write many small programs to try the libraries. However, it is a poor substitute for a true REPL. Java has some third party REPLs, but I did not feel at ease with them. Rather, I resorted on unit testing (which has the added benefit of documenting what you are doing).

Recently, I found out that clojure is an excellent candidate to do the kind of exploratory programming Java is not good at. Essentially, I find it easier to try the libraries with clojure than with Java. My usual setup is Emacs + swank. The close integration between the buffer and the REPL, means that I'm free to try wrapper functions in the REPL (most Java APIs are quite over-engineered) then move them to the editor and use them to build further abstractions.

For example, here I just wrapped the API to build ER and BA random graphs. It is quick to use in the REPL and then I can easily study the generated graphs directly in the REPL. Notice that this is different from both using unit testing and small programs; in both situations, should I want to run further functions on a graph, I would have to save it to disk and reload it, because a successive run on the program would yield a different graph.

This is another example:

Here I created a bunch of functions to visually present a graph. Essentially I can easily use the macro to experiment with different layouts (that is to say the algorithm placing the nodes. Notice that once again, running things step by step, means that I can try new things on the same graph and compare them.

And these were added at the end to check some standard metrics:

I have to admit that I somewhat missed Common Lisp loop, for the latter.

Technorati Tags: Clojure, Java, Programming,Lisp,Common Lisp

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

Is laziness tiring? (part 1)

Introduction

A part from the obvious pun, I effectively consider laziness tiring. Let me explain: I'm quite used to lazy languages, I've used Haskell for some time, and I use effectively Python lazy features extensively. Moreover, it has been a while I use clojure as well.

Laziness is an extremely powerful conceptual abstraction: it is like having an optimizing compiler tailored at not perusing your sequences, so that you can write code in a natural way. I would definitely want some form of laziness (especially sequence based laziness) in every language high level enough that it does not hurt.

Moreover, lazy sequences do not have many of the usual drawbacks of default lazyness. First, you somehow have to explicitly require it; when not required is there but it does not hurt either (e.g., map). It does not play extremely well with side-effects, but in clojure the language is designed to limit the scope of expressions with side effect.

However, I decided to understand more fully how lazyness works in clojure.

lazy-seq and cons

This is a simple code I wrote to test multiple functions on a given collection and see how they fare.

Essentially benchmark is a macro taking a vector of functions. It builds code fragments which call the desired function on the list and prints the time needed. We use a slow-computation function which sleeps for 500 ms. This way is easy to count calls to slow-computation.

One of the more interesting examples I found is this one:

Here the list is a completely lazy list of three elements. The results are expected: list?, seq?, identity do not do anything with their argument, which is not evaluated (by the way list? is false, seq? is true). first has to evaluate the first element (which is expected), empty evaluates the first element to see if there is such an element. seq should return nil for empty sequences, and as a consequence has to evaluate the first element.

rest also evaluates the first element, but not the successive. I'm not sure if it would be possible to return the cdr of the list without evaluating the car; probably not with clojure lazyness model. next is worse: it evaluates the first element (like rest), but then calls seq on the result, and that leads to the execution of another element.

lazy-seq and list

This example is slightly different, but is trivial, indeed. There is just one lazy seq: the contained list has to be evaluated altogether for every function that needs at least one element.

lazy-seq and concat

The following example, started to surprise me.

As far as I could tell, concat should return a lazy sequence over the lists. It is probably my misunderstanding, but I thought that identity, seq, first, list? and empty? should evaluate one or no elements. I decided to write more benchmark functions.

The results are here:

However, when running the first example the perceived time was akin to the second: simply the evaluation was not timed because it was done (at least) when binding in the let form. Then I got the illumination. Laziness is a bitch: the point here is that it is list that is not lazy. By the way, why should it be. So it does not matter what I do: the time is already spent when I get into concat. I understand that this is trivial: however, I find strange having tp reason about "when things happen" the point of laziness being "not reasoning about when things happen".

Anyway, using lazy-seq, things work as expected:

But what about a "warn on eager", which alerts when something that should be lazy is instead eager?

Technorati Tags:Clojure, Lisp, Programming

'(leiningen slime Emacs) are the way.

Leiningen seems to be really the easiest way to create a clojure developing environment.

Up to now, I worked mainly with IntelliJ + LaClojure. The rest of the project is Java (so having IntelliJ is a huge plus) and is very "project oriented" stuff. In fact, it is not even possible to think about individual scripts or so, things are meant to work in an environment and the environment needs to be started beforehand. As a consequence, a solution which does not work well "one file at a time" is not a big issue right now.

Although LaClojure plugin is very good, I feel more at home with Emacs. Not that I'm been an assiduous Emacs user (I use and used pretty much everything), it is just that Emacs has been optimized in last "don't even know how many years" to work with Lisp. Emacs indentation is beautiful and all. Moreover, leiningen should be a good choice even for my main project.

As a consequence, I decided to test leiningen with smaller projects.  I started a one file project as an example. The first step was just lein new'ing, then I had to manually add the :dev-dependencies [[swank-clojure "1.2.1"]].

$ lein deps

Then it is just a matter of lein swank and the server is there, waiting for my Emacs to connect. I had already installed slime (and swank) for my common lisp development. I installed swank clojure and set some configuration variables in my emacs configuration:

 
(require 'clojure-mode)
(add-to-list 'load-path
             "~/.emacs.d/swank-clojure/src/emacs")

(setq swank-clojure-jar-path "/usr/local/Cellar/clojure/1.2.0/clojure.jar"
      swank-clojure-extra-classpaths (list
                                      "~/.emacs.d/swank-clojure/src/main/clojure"
                                      "/usr/local/Cellar/clojure-contrib/1.2.0/clojure-contrib.jar"))

and that is the rest of the slime related configuration

(eval-after-load "slime" 
  '(progn (slime-setup '(slime-repl))))


(setq load-path 
      (cons "~/.emacs.d/slime" load-path))
(cond
 ((macosx-p)
  (setq inferior-lisp-program "/usr/local/bin/sbcl --noinform"))
 ((win-p)
  (setq inferior-lisp-program "C:/Program Files/Steel Bank Common Lisp/1.0.37/sbcl.exe --noinform")))

; (slime-setup)
(require 'slime)
(require 'slime-autoloads)
(add-hook 'slime-repl-mode-hook 'split-window-vertically)

I think that I should improve the configuration, as it is still sub-optimal. However, with M-x slime I just run a new sbcl slime server, with sbcl client. Then I can use it just to hack with common lisp. On the other hand, M-x slime-connect asks me which server to connect. With default values, if I already run lein swank in my project, it connects to that one (but ports and servers are completely configurable).

At that point I have a familiar lisp developing environment. I can easily compile and load with C-c C-k, reload every function with C-M-x and everything that is standard in slime.

It seems that functions in src/projectname/core.clj can be used directly when they are loaded with C-M-k, but not with C-c C-k. However, I find more useful to do the latter most of the times. Moreover, I believe that files outside src do not load directly in user. Besides, I prefer not to. As a consequence I switch namespace in slime.

(in-ns 'org.enrico_franchi.paip.simplegrammar.grammar)

I believe that this should make clojure.core functions not accessible; however, I have the habit of importing the "core" libraries (at least, I did that in common lisp packages, as recommended). Consequently my namespace declaration is, for example:

(ns org.enrico_franchi.paip.simplegrammar.grammar
  (:use
   clojure.core
   clojure.contrib.combinatorics))

And slime is in my namespace, so I can use the functions as I want (user is not modified) and I can also call clojure.core and whatever I need.

Technorati Tags: Clojure, Lisp, Programming, Leiningen

Clojure: mdef macro

I don't believe this macro is particularly useful. In principle, this macro should not have been written at all. If fails the very first questions we should ask ourselves before writing a macro, that is to say the macro is not necessary. If you really need a macro to specify multiple special variables, you are probably getting the design wrong.

However, it is easy enough to demonstrate some basic techniques. In particular, the idea is how we quote/unquote in nested ways. Most basic examples on macros show how ~ unquotes a symbol. In fact ~/unquote is more general: it "reverts" to standard clojure evaluation.

Code in an unquote is just regularly executed at compile time. A particular case is when we write ~foo it is equivalent to (unquote foo) where foo is just a symbol which is evaluated to its value as it is the rule with Clojure. The do form is quasiquoted, then we ~@ the list built with the loop.

Inside the loop, we use ` once again: we could have built the list without using "templating", just using regular clojure operations [(list 'def ...)]. In fact, it is entirely possible to build macros without using ` and ~ and simply "building" the s-expressions representing the code. It is usually believed that code written this way is less clear.

Of course, the macro could have been written in a more compact way. However, I think that this way is rather readable and shows clearly the point I intended to make.

Technorati Tags: Clojure, Lisp, Programming, Macros

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

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

Macro or not to macro?

Today I was wondering about the code I commented about some days ago. I essentially created a function to transform an array of objects I got in input to something more easy to deal with, that is to say an hash-map. Since most of those parameters needed to become properties of the object receiving them, I considered that I could just write a function to avoid repetitive code.

The function approach is useful and it solves my problem. I need a dictionary, I get a dictionary. However, what I am doing is essentially akin to binding/destructuring. I only have to rely on the information on the left side of the binding, as the right side completely lacks such information. Moreover, in some situation it is nice to directly access the "fields". I definitely decided that it was time for a macro.

Notice, I'm quite against macro abuse. I've already abused many nice programming features as soon as I learned them. Consequently I know I can resist this time. But this is definitely too nice not to use a macro. My first attempt was this:



It essentially retains the same structure of the function, but is a macro. It is slightly more robust because it makes clear what happens when the array is too short (the variables are nil) or when it is too long (variables are ignored). It stresses that what matters is just the keys parameter, while the defaults only help. In particular it is clear that having keys in the defaults that are not among keys is completely useless. Consequently, order in defaults is plainly irrelevant and plain dictionaries (instead of array-map's) can be used.

However, when I started substituting the code in the project, I felt that the code did not look particularly nicer. I immediately started thinking to a new solution. An afterthought is that my typical use-case (get a dictionary to merge with .state) is not easily covered.

In "Artificial Intelligence Programming: Case Studies in Common Lisp" some suggestions regarding macros are given at the very beginning of the book. Norvig explains that writing a macro is a four-step process:

1. Decide if the macro is really necessary.
2. Write down the syntax of the macro
3. Figure out what the macro should expand to
4. Use defmacro to implement the syntax/expansion correspondence

I felt like the syntax of the macro was not carefully designed. The advise given in the book (a part of not writing them) is to follow established Lisp conventions for macro syntax whenever possible. In this case, the idea was to follow clojure conventions. In particular, clojure has structural unbinding. Using the {:keys [...], :or {}, :as options} I just have all the features I need.

I considered that in order to read the other macro a programmer needed either to look at the implementation or to the documentation. On the other hand, following clojure conventions, the meaning of the code would be apparent to everybody knowing about clojure destructuring.



That is an example on how to use the macro. And now, the macro itself!



Not perfect, but it does its job.

Clojure, Macros, Metaprogramming, Programming