Archive for the ‘All’ Category

I first discovered the Visitors pattern from reading the original design patterns book, sometime in the last century when, having jumped into computer science, I was busy hoovering up everything I could about programming. After reading the chapter on visitors, it made no sense to me then and I had no real cause to go near them again until I started working on Tawny-OWL (http://www.russet.org.uk/blog/2989). This library includes a renderer which takes a set of OWL API OWLObjects and turns them into Clojure data structures. Originally, I added this simply to generate documentation, but since then it’s grown to have rather a life of its own. In Java, this would be be implemented with a visitor. In Clojure, I implemented this with multimethods which is often used as a replacement for the visitor pattern but I am now far from convinced that this was a good decision, after the performance of my code collapsed massively. In this article, I describe the problems with multimethods, and some alternatives. For each of these, I use a small example, and bench mark them; you can follow my code on https://github.com/phillord/visitor-benchmark. The results are, perhaps, a little surprising. This should be of relevance to anyone addressing the same problem in Clojure.


Visitors and the OWL API

The purpose of a Visitor is to crawl over a set of objects, identified by their type, typically representing an abstract syntax tree, although it can be used for other purposes. It enables the implementation of many different types of behaviour over the tree without having to extend each of the types. This works by having a Visitor which implements one method for each object type. It works well, unless you add a new type, in which case there are a lot of Visitors to re-write. This is one reason that they are found mainly around abstract syntax trees. They tend not to change very much which is a prerequesite for visitors.

The OWL API (1303.0213) is a library which represents the OWL language (http://www.w3.org/TR/owl2-overview/) — a mechanism for representing an area of knowledge using logical statements, or an ontology (http://ontogenesis.knowledgeblog.org/66). It’s a fairly complex API and implements several visitor patterns; it’s main visitor — the OWLObjectVisitor has so many methods I ended up using Clojure and reflection to count them all — 98 is the answer!


Tawny-OWL

Now, Tawny-OWL (http://www.russet.org.uk/blog/2989) wraps the OWL API to provide an evaluative, R-like environment for building ontologies, built using Clojure, which provides the ability to abstract away from the actual axioms; you can build functions which build axioms, examples of which can be seen in the karyotype ontology (https://github.com/jaydchan/tawny-karyotype) (1305.3758).

While abstractions are generally nice, it also hides the underlying axioms; so I built tawny.render which takes OWL API objects and turns them into Clojure forms, originally as a mechanism for documentation, although since I wrote it, it has taken on a life of its own.

In Java, the renderer would just have used the Visitor pattern. In Tawny-OWL, I initially implemented this using multimethods. These have quite commonly been put forward as a replacement for the visitor pattern (http://www.fatvat.co.uk/2009/01/multi-methods-in-clojure.html), so it seemed a reasonable suggestion and it worked well for me, until a new version of the OWL API was released. Suddenly the performance of my test suite crashed catastrophically. Consider, these results: from 40 seconds to 4 minutes.

git clone git@github.com:phillord/tawny-owl.git
git checkout 5870a9

time lein with-profile 3.4.10 test
real    0m45.186s

time lein with-profile 3.5.0 test
real    4m26.070s

The OWL API test suites speed up slightly between the two versions, so it seemed unlikely to be an implementation mistake. I also noticed that most of the time was in the rendering tests — which include one substantial rendering task.

Thanks to git bisect, I tracked the problem down to a single commit 2bb6a0. If you look through the entire log (it’s long, and I did!) the surprising thing is this; there are precisely no implementation changes. All that this commit does is add a (large number) of interfaces to the existing model. Why on earth would this cause a massive drop in performance?


Visitors Revisited

There is one subtlety about the visitor pattern that is not obvious at first sight. If we have a visitor interface like so:

class Visitor{
    public void visit(A a);
    public void visit(B b);
    public void visit(C c);
    public void visit(D d);
}

At some point, we have to decide which method to actually call. With the visitor pattern it is the entity that accepts the visitor that makes this decision, because it is this entity that calls visit. Consider this code:

class Dimpl implements D{
    public accept( Visitor v ){
        v.visit(this);
    }
}

In Java, which method to dispatch to is made on the basis of the compile time, static type of the object. Now, the Dimpl class knows it’s own type at compile time, hence we dispatch to the correct Visitor method, even though the class which makes calls the accept method does not know the underlying type of the Dimpl object. Effectively, we pass off part of the computation to the compile time type system.

Clojure cannot do this. Multimethod calls have to check the runtime type of the object to be visited at runtime against the range of possibilities. By introducing a large number of interfaces, it appears the OWL API had increased the search space over which the multimethod isa? call had to crawl. I’ll try and show here that between the two versions of the OWL API, benchmarking isa? call has got significantly slower. This is not enough to explain in performance drop of my tests, although refactoring the multimethod to reduce the number of isa? does actually address the issue, so it really does seem to be the problem.

In the rest of this article, I will consider several different alternatives, benchmarking them and comparing them for performance. Microbenchmarking of this form is hard to do. In this article, I use a combination of the excellent criterium, clojure.core/time supplemented with some macro-benchmarking — running the Tawny-OWL tests. I consider that none of these tests are definitive, and will discuss their advantages and disadvantages as I go. All results are reported to 2 significant figures. Ultimately, my aim with this article is to improve the Tawny-OWL performance, but I hope that the results are clean enough that they are relevant to other environments also.


Set up

The rest of the code for this post is available at https://github.com/phillord/visitor-benchmark. The code in this article is a point in time, and will not be updated if I change the visitor benchmark. This project can be cloned and tested using lein with-profile production run. I will not describe all of the plumbing that makes this work here.

First, however, we define a benchmark command. Using Criterium (http:///github.com/hugoduncan/criterium) directly is a little painful, so I define a small macro which allows me to switch between bench, quick-bench and time. My version of bench also prints out the form so I can see what is happening.

(def bench-form
  ;;'clojure.core/time
  ;;'criterium.core/quick-bench
  'criterium.core/bench
  )

(defmacro bench [form]
  `(do
     (println "Benching:" (quote ~form))
     (~bench-form ~form)))

Establishing a base line

First we establish a base line; how long does it take to invoke a function that does nothing at all. While it varies from machine to machine, on my desktop it takes around 10ns.

(defn f [])

(visitor.benchmark.bench/bench (f)

Some objects to work with

I have choosen to use the OWL API and Tawny-OWL to generate my objects, although my belief is that this analysis should be good for any API. I already had a lot of the code for this analysis, the OWL API uses visitors and it is big. Finally, the change between 3.4.10 and 3.5.0 that I describe earlier is a useful test. We generate three objects to use.

(defontology ont)

(defclass AClass)
(defoproperty AProperty)
(def ASome (first  (owl-some AProperty AClass)))

Multimethods

To test multimethods first, I used the following code, which creates a two method multimethod operating on class. After this, I also tried adding many more methods to the multimethod and calling it again.

(defmulti multi class)

(defmethod multi org.semanticweb.owlapi.model.OWLClass [e])
(defmethod multi org.semanticweb.owlapi.model.OWLObjectProperty [e])

(defn multi-on-class []
  (bench (multi AClass)))

(defn multi-on-property []
  (bench (multi AProperty)))

Now using criterium.core/bench gives the following results, both before and after adding extra methods. The basic conclusion here is that, it makes no difference at all: the multimethod is unaffected by the change in number of method and, critically, there is no difference at all between OWL-API 3.4.10 and 3.5.0. Poor evidence for the theory that the multimethod is responsible for the performance drop.

OWL API
Class
Property
Big Class
Big Property
3.4.10
61ns
61ns
66ns
65ns
3.5.0
62ns
57ns
60ns
63ns

Poking through the Clojure java code finds this possible issue — the method lookup appears to be cached. dispatchVal here is the value returned by the dispatch function.

private IFn findAndCacheBestMethod(Object dispatchVal)

Testing with clojure.core/time rather confirms this. Consider the results in this table. The first thing to notice is that change in unit — we have moved from nanoseconds to milliseconds. Just for comparision our base test of an empty function reports “Elapsed time: 0.026253 msecs” or around 26μs for a simple invocation — three orders slower than criterium suggests and 5 orders faster than our multimethod invocation. Now, none of these differences are entirely believable, but what is interesting is difference of between 5 and 20 fold between the two versions of the OWL API. Of course, clojure.core/time is potentially risky because of start up time and so forth but, because this should affect the test against 3.4.10 and 3.5.0 equally; it also will also remove the effect of caching in findAndCacheBestMethod single it only runs once.

OWL API
Class
Property
Big Class
Big Property
3.4.10
220ms
140ms
80ms
88ms
3.5.0
860ms
1400ms
450ms
1400ms

Trying to pull apart this appart a little further, let’s test the isa? method more directly, which we test with following benchmarks one of which succeeds and one of which fails.

(bench (isa? (class AClass)
              org.semanticweb.owlapi.model.OWLClass))
(bench (isa? (class AClass)
              org.semanticweb.owlapi.model.OWLObjectProperty)))

First, comparison with criterium.core/bench which shows a massive difference between success and failure (note the change in unit); the reason for this should be obvious — if isa? succeeds it short-circuits; if it fails, it must test all superclasses and the various hierarchies that Clojure adds.

OWL API
Succeeds
Fails
3.4.10
76ns
40μs
3.5.0
76ns
33μs

Using the simpler, clojure.core/time shows the same thing as well as a difference between 3.4.10 and 3.5.0.

OWL API
Succeeds
Fails
3.4.10
30μs
1.4ms
3.5.0
40μs
3.8ms

This distinction is important here. If it fails, then the isa? method is really very, very slow. 3.5.0 is slower, although not that much slower, at least according to clojure.core/time.

I am still not entirely satisified with these results. They do appear to show that multimethods can be pretty slow, and they do show a difference between 3.4.10 and 3.5.0. However, the various caching that multimethods perform should help — even though the OWL API has add many new interfaces, we are still only talking about tens of interfaces.


Implementing a Visitor with a Visitor

The most obvious way to implement a visitor pattern is to, er, implement the visitor. To achieve this in a vaguely friendly way in Clojure, we need to use reify — we cannot use proxy as it cannot overload on type which is the whole point of the visitor pattern.

We can achieve this simply with the following code:

(defn ontology-visitor []
  (reify org.semanticweb.owlapi.model.OWLObjectVisitor
    (^void visit [this
                  ^org.semanticweb.owlapi.model.OWLOntology o]
      (println "v ontology" o))))

(defontology ont)
(.visit (ontology-visitor) ont)

This works fine, but there is a problem. By default, the visitor pattern returns nothing — it works by side effect. In general, and specifically in the OWL API the visit method returns void. This is not at all useful as a replacement for multimethods in a recursive descent renderer. To work around this problem, I add some extra glue in terms of an atom which we change by side effect during visiting and then dereference to provide a return value.

(defn visit-entity [entity]
  (let [r (atom nil)]
    (.visit
     (reify org.semanticweb.owlapi.model.OWLObjectVisitor
       (^void visit [this
                     ^org.semanticweb.owlapi.model.OWLOntology o]
         (reset! r
                 (str "visit o" o)))

       (^void visit [this
                     ^org.semanticweb.owlapi.model.OWLClass c]
         (reset! r
                 (str "visit class" c))))
     entity)
    @r))

(visit-entity ont)

(defclass A)
(visit-entity A)

And how does it perform. Well, badly, is the answer: around 25μs for each method invocation (using bench) which is 1000x slower than our base line.

Of course, one obvious complaint with this implementation is that it involves creation of an atom, resetting that atom and so forth; actually, I have tested that as well, but for the purpose of this article, I test this simpler version.

(defn new-object-visitor []
  (reify org.semanticweb.owlapi.model.OWLObjectVisitor
    (^void visit [this
                  ^org.semanticweb.owlapi.model.OWLObjectProperty o])
    (^void visit [this
                  ^org.semanticweb.owlapi.model.OWLClass c])))

This gives a base line score of about 7ns. In short, the creation of a new object is not the problem. In the examples above, I use type hinting, but actually this makes no difference to performance. The fundamental problem here is that our reified object is dispatching on type using runtime checks and reflection.


A big Cond

Another possible option would be to replace the multimethod with a big cond form. I will not show the full code for this as it’s rather long, but an example of part of it looks like this:

(defn- as-form-int
  "Render one of the main OWLEntities as one of the main functions
in tawny."
  [c options]
  (condp
      (fn [entity-type ^OWLEntity entity]
        (= entity-type (.getEntityType entity)))
      c
    EntityType/CLASS
    (as-form-int-OWLClass c options)
    EntityType/OBJECT_PROPERTY
    (as-form-int-OWLObjectProperty c options)
    EntityType/DATA_PROPERTY
    (as-form-int-OWLDataProperty c options)
    EntityType/ANNOTATION_PROPERTY
    (as-form-int-OWLAnnotationProperty c options)
    EntityType/NAMED_INDIVIDUAL
    (as-form-int-OWLNamedIndividual c options)
    EntityType/DATATYPE
    (as-form-int-OWLDatatype c options)))

Here, we have use a cond to dispatch on the EntityType. The individual methods for the multimethod have been renamed using a rather clunky naming scheme. I do not have individual benchmarks for form of test, but looked at overall it does solve the problem. lein test runs in around 10s and there is no difference between the OWL API 3.4.10 and 3.5.0. In short, it solves the problem.

Unfortunately, the solution comes at a significant cost. Firstly and perhaps most trivially the code looks terrible. The solution also is very specific to the OWL API — without the getEntityType method this fails. In fact, getEntityType does not make all the distinctions we need; I also needed another couple of methods (getClassExpressionType and getDataRangeType) and still needed to fallback to instance? at points.

A different solution would be to just use instance? calls.

(defn small [e]
  (cond
   (instance? org.semanticweb.owlapi.model.OWLClass e)
   true
   (instance? org.semanticweb.owlapi.model.OWLObjectProperty e)
   true))

This behaves as expected under benchmarking. The code shown above with only two instance of calls bench marks at 5ns; however, when expanded to perform all the instance of calls I need, performance drops to 230ns.

I have also tried a few other tricks for optimising type based look up, including replacing the cond with a map lookup. Details are available in my test code. Suffice to say, I did not achieve a solution which was performant.


Protocols

A final solution would be to use protocols. The idea here is that OWL Objects would know how to render themselves. I have not yet tested this within the context of the OWL API, and have only benchmarks. Consider this code:

(extend-type org.semanticweb.owlapi.model.OWLClass
  Render
  (render[this]))

A bench check of this shows highly performant invocation at around 10ns. The use of time is less happy, however, with a 0.2ms invocation (compared to 0.005ms baseline). I suspect that there is some caching happening at the protocol layer also. I would like to find the time to check protocols further, with a full implementation in the context of tawny.render. Unfortunately, this is quite a bit of (very boring!) code to rewrite.


Adapting the multimethod

The actual solution that I used was different to all of these, simply because it was the first acceptable solution that I found which solved the problem of very long test run. My approach to solving this problem was to address the isa? calls through memoization, using the fact that I know which classes the multimethod dispatches on.

The code for this just affects the dispatch method; we call isa? once and only once for each concrete class of object that we have. The full diff is available here.

(defn lookup
  "Returns the class of the OWLEntity of which this is a subclass."
  [c]
  (first
   (filter
    (fn fn-lookup [parent]
      (isa? c parent))
    (list org.semanticweb.owlapi.model.OWLClass
          org.semanticweb.owlapi.model.OWLObjectProperty
          org.semanticweb.owlapi.model.OWLNamedIndividual
          org.semanticweb.owlapi.model.OWLDataProperty
          org.semanticweb.owlapi.model.OWLAnnotationProperty
          org.semanticweb.owlapi.model.OWLDatatype))))

(def m-lookup (memoize lookup))

(defmulti multi (fn [c]
                  (m-lookup
                   (class c))))

My results here are a little surprising. The speed of the dispatch seems to slow down using my benchmarking (data not shown). Fortunately, I tried running my test cases BEFORE I did this bench marking, because the results overall are excellent.

git  checkout 2fab56

time lein with-profile 3.4.10 test
real    0m7.875s
user    0m9.547s
sys     0m0.661s

time lein with-profile 3.5.0 test
real    0m7.950s
user    0m9.641s
sys     0m0.696s

As you can see, this memoized version achieves two things. Firstly, it is faster than the original by five fold. But critically, the difference between 3.4.10 and 3.5.0 has gone. For the 3.5.0 version of the OWL API this memoization is 30 fold faster.

Of course, this solution is not ideal. The multimethod is not really doing anything now. We have closed it rather than left it open. It is doing a completely pointless isa? check when all we need is an = check, and it is still doing linear time dispatch when it should be constant. Moreover, I wonder what why this form of memoization is working when the multimethod implementation itself is cached. None the less it works well enough that I am happy with it for the moment.


Conclusions

In this article, I have investigated the visitor pattern and its implementation in Clojure. Multimethods do work, and do produce a nice code base, but they do not perform that well. As my example shows, they are potentially also sensitive to changes in the class structure of dependencies. In short, the runtime decisions of multimethods are not really a good replacement for the compile decisions of the Visitor.

Benchmarking is very difficult under the best of circumstances. Criteriums use of multiple runs brings some statistics to bear on the task, but also produces very poor results for memoized or cached functions if the real-world task defeats this caching. In this article, I have chosen a combination of simple test cases, bench and time but also my test cases from tawny.owl, against two different versions of the OWL API. Clearly the latter is not simple and there are many other variables which could be producing these results. However, what these tests lack in cleanliness, they gain in that they are a real world problem. Although I have tested them in this environment as well as I am able, this lack of cleanliness leaves the possibility that I have just misunderstood the cause.

I would like to test protocols in this environment also. They may be a good solution and appear to run quickly, but I have only tested against benchmark; as we have seen benchmarks are not necessarily clean.

Ultimately, I feel that we need proper “dispatch on type” support in Clojure. Multimethods are much more generic even if they are generally used in this way. I would like to be able to dispatch on more than one argument, have type hints taken care of for me, and most importantly, I would like them to be highly performant. I have managed to achieve some of this by modifying the dispatch method, but I think that this is a more generic problem and should be solved properly. As it stands, I would argue that multimethods are not a good replacement for the visitor pattern.


Acknowledgements

Thanks to Keith Flanagan for a proof read. Mistakes are my own!

Bibliography

I was entertained to see the recent publication of a new paper on the definition of function (10.1186/2041-1480-5-27). I met one of the authors at a meeting a few years back in Durham, and had a very nice discussion about my own contribution to this definition which I published previously (1309.5984).

I do not want to discuss the paper in full, which is a nice paper and worth a read. I do however want to comment more specifically about the parts that explicitly and implicitly address my own paper.

At the start of the paper, the authors discuss the criteria for their definition which includes this:

Avoidance of epiphenomenalism: Functions should be determined by current performance of its bearer, not mainly by causally inert historical facts like its (evolutionary or cultural) history or a mere ascription by its producers, users, or observers

I found this a fairly strange criteria; it’s not clear to me why historical facts are inert; especially in biology the evolutionary history of an organism is surely one of the most important features. Originally, this criteria comes from another paper by Artiga who says:

We want to find out what is the lung’s function, we would probably look at what lungs actually do in our body. We would see that they enable respiration, so we would conclude that this is their function. Why they came to be here seems completely irrelevant for function attribution.

Obviously, this means “most peoples” bodies rather than just one, given that lungs do (somewhat) different things in different people. But, I do not think that why they came to be here is irrelevant, at least not if we wish to distinguish with a role. My fingers are currently engaged in typing, but few people would describe this as a function (although most would say that precise and controlled manipulation of the world is). Or to make a more extreme position, after Robert Hoehndorf, the heart actually does produce loud thumping noises. Surely not a function?

I am also slightly disappointed that what I think is one of the key points of my own function paper has been missed from their list of criteria. In it, I say:

I consider whether these definitions are applicable; for a given set of entities how do we decide whether we have a function (of either subclass) or a role.

Given a definition, I should be able to produce at least one practical test that I can use to determine whether that definition holds; I think that this notion of applicability needs to be more widely considered.

Now, my actual definition of biological function was:

A biological function is a realizable entity that inheres in a continuant which is realized in an activity, and where the homologous structure(s) of individuals of closely related and the same species bear this same biological function.

The language has been chosen to mirror BFO since it was in this context that the paper was addressed; I think it could be simplified and made more readable, but I was constrained by the language of BFO. Now, the first criticism on my definition is on technical grounds namely:

Lord claims that his definition is recursive rather than circular, despite the occurrence of the word “function” in the definiens.

My use of this form of definition was, of course, deliberate and partly provocative; perhaps, it is something that I should not have done, since it has muddied the water somewhat as this comment shows. In fact, it is very easy to work around this criticism by simply removing the recursion:

A biological function is a …. same species bear this same realizable entity.

The technical criticism has now gone. But I do not like the definition as much because “the same realizable entity” would in fact be a biological function. I think we avoid recursive definitions because they can be circular, but this is like avoiding recursive function calls because they may not terminate. And that is a shame, because, as with recursive function calls, I think this form of definition can be quite succinct. Consider:

A spouse is a person who is married to their spouse.

or:

A brother is a man with the same parents as their brother.

If we unwind the recursion, then we get

A brother is a man with the same parents as another man.

Again, we are hiding that reality that both men in this definition are brothers.

Of course, some recursive definitions might actually be circular, and that is less good. But if the applicability of a function is also considered then this issue goes away. I can determine if some one is a spouse or a brother given these definitions, so I see no problem.

A second criticism comes from my statment that:

Hence he concludes that among the instances of realizables that are realizables for the same type of process can be both roles and functions depending on the species the realizable’s bearer belongs to. This presents a problem for the distinction between functions and roles.

I do not think that this is a problem at all, because I say quite clearly that we can distinguish between roles and functions, but that we do this for the individual role or function not at a class level:

My definition distinguishes between the two based on the nature of the relationship to the independent continuant in which they inhere. I suggest that it is very hard to make the distinction at the class level[…]. For an individual continuant bearing a realizable entity, this distinction appears to be much more straightforward.

In otherwords, “for walking on” is either a role or a function. But in human hands it is a role, while for chimps it is a function. I see no reason why the distinction at the level of the individual should be considered to be less relavant than at the class, nor why this should be problematic. Actually, it reduces the need for duplication between the role and function hierarchies; while tools like Tawny-OWL (1303.0213) may ease the maintainence of duplication, avoiding altogether still seems sensible.

The final criticism is, I think, the least worrisome. The authors say:

Had evolution stopped after the first species, according to Lord’s definition, there would not have been any biological function at all.

The slightly flippant but none the less entirely valid argument to this is, “but it didn’t”. We could equally argue against a definition of human as having two hands on the basis that they might have evolved a third.

More importantly, though, in most definitions of life the ability to adapt or evolve is part of the definition. Without this, we have a chemical process. So, without evolution, we have no life. Given this, we can rewrite the last statement as:

Had life stopped after the first species, there would not have been any biological function at all.

Which is an entirely true statement; that it drops so nicely out of my definition for biological function is a strength of my definition and not a weakness.

I feel that my definition is still a good one. Rereading my function paper now the argument still seems coherent, and the examples clear. Although I put an entire section on applicability into the function, I do rather regret that I did not introduce it as a general criteria for all ontology definitions explicitly; that this criteria has been missed is surely my fault and not the readers. Perhaps I should have spent more time on that, than on my recursive definition which was not critical to the paper.

At the same time, the fact that discussions on definitions are still going on, for a term that biologists have been using for many years again leads me back to the conclusion that the definitions of such generic terms are not nearly as important as some make out. So long as they are useful, biologists will carry on describing things as functions if it fits their ad-hoc, informal definitions that have been developed over time within a community. I cannot help but think that this is a good thing.

Bibliography

I’ve noted in the past some of the strange beliefs about DOIs (http://www.russet.org.uk/blog/1849). One of these is that DOIs provide some magic archiving capability (http://www.russet.org.uk/blog/2360). The other is the strange one that “DOIs make things citable”. This was one of the selling points for Figshare, for instance.

I’m interested to see that now GitHub have now joined the party (http://github.com/blog/1840-improving-github-for-science), and again using the justification that “DOIs make things citable”. I am lost in attempting to understand this.

First, GitHub have stable URIs for repositories. It’s in their business interests to keep these and if they change them they will break every single repository that has checked things out using the URI.

Second, if I have a github URI I actually know that I have a link to a repository, and it is fairly clear that I can clone from this repository. With a DOIs I do not. Paper, datacite item, git repo, it is not possible to tell.

Third, with a github URI I have a URI that I compare against other URIs and work out whether it is the same or different. If I have a DOI, I now have two identifiers, the DOI and the URI both of which identify the same thing. Surely, this makes the situation worse, and not better.

Am I being a little cynical in wondering why some publishers require them? Do they, perhaps have a vested interest in making things more invouluted and not just using standard web technology (http://www.russet.org.uk/blog/2248)?

It seems to me like a clear case of DOIs are magical fairy dust. We sprinkle them on a github repository and now it is better, when actually we have made the situation worse.

The only justification that we have is “DOIs make it citable”. Is there a better one? Answers on a post-card please.


Update

I totally missed a post by Carl Boettiger which makes some of the same points (http://www.carlboettiger.info/2013/06/03/DOI-citable.html).

On the general issue of metadata, a DOI will give some harvestable metadata from the DOI, although Greycite can give much of the same metadata direct from GitHub (see for instance here). Having GitHub fix their metadata would seem to me to have been an easier win. And, of course, github URIs can be used to clone from and extract all the repository metadata using, well, git.

Bibliography

I’ve been programming in Clojure for well over a year now; originally, I heard about it care of Sam Aaron, an old PhD student of ours who gave a fun lunch time talk; I rarely go to these (although I probably should). Indirectly, Tawny-OWL came out of this one, so it is good that I went.

During the time that I have used Clojure, I have come to know it fairly well, and appreciate many of it’s finer points; these are not the same as many people, I realise; for me, the Java integration is simple, effective and very important, as Tawny-OWL is essentially a wrapper over a Java library. Meanwhile, a lot of the nice concurrency features are a matter of indifference to me, again for the same reason.

But like any language there are some problems, or at least thing that don’t work for me. On the off-chance it is useful to anyone else, here is my list of Clojure gotchas.


Lazy Lists

This is quite a common one, of course, which hits most Clojure beginners. We write something like:

(def x (map (fn [x] (println "hello") x) (range 1 100)))

and then wonder why nothing prints out. Or, the alternative problem, write something like (range) and find the REPL hangs. The latter is, I think, a poorly performing REPL; infinity might be more principled a point at which to stop than an arbitrarily choosen value but it’s not useful.

Of course, once you have got past this point, it’s not so bad, but laziness can still take you unawares, especially when I was using Clojure just to drive a JVM library. This subtle bug from tawny.render which is, essentially, one big recursive descent renderer, demonstrates the problem. Consider, this code:

(concat
  [:fact]
  (form [:fact fact])
  (form [:factnot factnot]))

Looks fine, but I need to pass options and a lookup cache around and had done this with a number of dynamic vars. The cache, it turns out, would not have been working for this form (although it was for others), but I never noticed this. However, the options broke the code more cleanly. concat is, of course, lazy, and was happening outside the binding form which defines the dynamic vars.

Now, I know dynamic vars and laziness don’t mix. In the end, I have added an additional parameter to all the functions in my renderer using the awesome power of lisp (i.e. I wrote a dodgy search and replace function in Emacs). And the cache now invalidates itself using a better technique than before. But I didn’t want laziness, I just got it by chance. In Clojure, it’s always there, wanted or not. Or, rather, it’s always sometimes there, because Clojure is only partly lazy.


Lisp-1 vs Lisp-2

Well, this argument is as old as the hills. Clojure is a lisp-1, so it has a single namespace for variables and functions, while Common Lisp and Emacs-Lisp are a lisp-2, so have one namespace for each.

I’ve had fun with single namespaces before — I used to teach Javascript to new programmers and it produces wierd and wonderful bugs that can be hard to track down. Still, I am too old and wize for that. If only!

During Tawny-OWL, I found accidental capture of functions produced some strange artifacts. Consider, for example, this code.

(defn my-get[x map]
   (get x map))

Everything works fine here, of course, right up till the point that you get bored of typing map and change it to m:

(defn my-get[x m]
   (get x map))

Now things break in strange ways. map is now the (global) function and not the parameter. There are many ways around this, of course. I could not have done (use 'clojure.core) earlier and just imported the functions I use; except that I did use map elsewhere. I could namespace everything (try and find some examples of Clojure code with namespace qualfied or aliased clojure.core functions).

In my case, exactly this problem hit me when I renamed parameters called ontology to o. I thought the compiler would pick up my errors but no, because I had an ontology function. This situation is made worse by my next gotcha which is:


Everything is a function

Consider this entirely pointless piece of code which makes lisp post-fix.

(defmacro do-do [x afn]
    `(do ~(afn x)))

We can use this macro like so:

(do-do 1 inc)

Now, if you know only a little about lisp, you might expect this to return 2. If you are more experienced, then you might think that this is a strange thing to do, because the call to (inc 1) happens at macro-expansion time, and why would you want to do that? If you are more experienced still, you will think, well actually inc is not evaluated so it is actually a symbol, and the whole thing is going to crash.

Actually, it returns nil. The reason for this is that lots of things in Clojure are functions that you wouldn’t expect, and symbol is one of these. So, actually, ('inc 1) returns nil. Because symbols are functions which lookup the occurance of the symbol in the collection that follows.

Now this has advantages, of course, namely that you can use a symbol to look up a key in a collection. So, for example:

('bob {'bob 1})

Returns 1. Of course, this is nice, but how many times do you actually want to do this? And when you do, would (get {'bob 1} 'bob) really be so hard? I can see the justification for (:bob {:bob 1}) but for symbols I am really not convinced, unless I am missing some other critical advantage.


Future, what’s a Future

So, your working along happily in your single threaded application, and then you write this:

(def x 1)
(def y (ref 2))

(+ @x y)

Now, in this small example, the error is easy to find; we should have derefed y and not x. And what is the error that we get from this?

ClassCastException java.lang.Long cannot be cast to
    java.util.concurrent.Future
    clojure.core/deref-future (core.clj:2108).

But I have not used a future. I have never used a future. I do not even know what a future is (although, I may, of course do so in the future). The reason for this strange error message can be seen from the code for deref (which the @ reader macro uses. Since, integers do not implement IDeref we treat them as a Future, which then causes the cast exception.

(defn deref
  {:added "1.0"
   :static true}
  ([ref] (if (instance? clojure.lang.IDeref ref)
           (.deref ^clojure.lang.IDeref ref)
           (deref-future ref)))
  ([ref timeout-ms timeout-val]
     (if (instance? clojure.lang.IBlockingDeref ref)
       (.deref ^clojure.lang.IBlockingDeref ref timeout-ms timeout-val)
       (deref-future ref timeout-ms timeout-val))))

This one is easy to solve. Deref should check instance? Future on the value if IDeref fails, and crash with a better error message. One instance? check is well worth the effort.


Backtick really is for macros only

The backtick notation is found in many lisps, and this includes Clojure. It is primary use is in macros because it lets you build up forms programmatically, but have them look like normal typed in forms. Compare these two:

(defmacro inc2 [x]
  `(+ ~x 2))

(defmacro inc2 [x]
   (list + x 2))

In many lisps, though, the backtick is just a list creation macro, that happens to be mostly used for macros. In clojure, it’s been hard coded for macros. Consider:

(let [x 'john]
  `(~x paul george ringo))

You might expect this to just return a list of four symbols (which it does), but the symbols are not what you might expect.

(john user/paul user/george user/ringo)

The symbols paul, george and ringo get namespace qualified in the return value even though they are not in the original form. Now, of course, there is a good reason for this; it helps to prevent us from accidental capture of symbols. All symbols should be qualified or gensym’d.

But consider this:

(deftype bob []
     java.lang.Runnable
   (run [this]
      (println "Hello")))

Now, I know this is a silly example, because bob is just implementing Runnable, and any function would do this, but Runnable is nice and simple. This is still quite a lot of typing, so, perhaps we should macro this.

(defmacro defrunnable[name body]
  `(deftype ~name []
      java.lang.Runnable
     (run [this]
       ~body)))

Unfortunately, this is actually wrong because the symbols run and this get namespace qualified, so we end up with user/run and user/this. The correct way to achieve this is this:

(defmacro defrunnable[name body]
  `(deftype ~name []
      java.lang.Runnable
     (~'run [~'this]
       ~body)))

Now, this version is anaphoric and introduces this, so perhaps it is not ideal, but run although it looks like a funtion is not one — it’s a lexical symbol that Clojure translates to the method name.


Whitespace

In Clojure , is whitespace. Effectively, it is used to make code pretty but has no meaning other than that. Those coming from other Lisps will sooner or later do something like this:

(defmacro defrunnable[name body]
  `(deftype ,name []
      java.lang.Runnable
     (,'run [,'this]
       ,body)))

This nearly always results in a strange error message somewhere down the line which is not easy to debug. The point is that other lisps use , to mean “unquote” for which Clojure uses ~. Not really Clojure’s fault this one, I guess. But irritating none the less.


Running in Java

One of the most unfortunate things about Clojure is that it’s hosted on the JVM. Of course, this is also the reason that I am using it, so I guess it makes no sense to complain, except when writing a article of “gotchas”. But being hosted on the JVM means Clojure inherits some of the strangeness of the JVM.

While writing Protege-NREPL, I had to struggle with the an OSGi and Clojure’s dynamic ClassLoader both of which do sort of the same thing, but sort of differently. It’s while getting this to work that I found that Clojure uses the context class loader.

In the end, I found that I needed this code to get anything working:

private final ClassLoader cl = new DynamicClassLoader(this.getClass().getClassLoader());
Thread.currentThread().setContextClassLoader(cl);

No one understand what the context class loader is, nor what it is for. There again, no one understands class loaders, so this is perhaps not a surprise.


Two times

Clojure uses what is effectively a two-pass compilation step. I say effectively, because apparently it doesn’t but the practical upshot is that you have to declare things before you use them. This is just a pain.

A related problem is that Clojure dislikes circular namespace dependencies. With Tawny-OWL, this means that the main namespace is not really in the order that I want it. And it was a big problem for the reasoner namespace. The problem is that the reasoner namespace has to know about the owl.clj namespace; but, also, the reasoner namespace has to know when an ontology is removed (so that any reasoners can be dropped). The obvious solution which is to have the owl.clj call reasoner.clj doesn’t work because we now have a circular dependency.

In the end, I solved this by implementing a hook system like Emacs. Now owl.clj just runs a hook. Probably, I should reimplement this directly with watches, but they were alpha at the time.


Goodbye Cons

One of the big wins for Clojure is built over abstractions, so that cons cell which is the core of most lisps is gone. Instead of this, we have ISeq which is an interface and looks like this:

Object first();

ISeq next();

ISeq more();

ISeq cons(Object o);

The problem is that it really does look like this; I mean, this is a cut-and-paste from the code. Aside these method declarations, that’s is. Nothing at all in the way of documentation.

Worse the entire API for Clojure consists of two classes, with the rest being considered “implementation detail”.

Strictly, therefore, Clojure is built over abstractions, but users of Clojure have no access to extend these abstractions themselves, unless they use implementation detail. Which, of course, they do; to access the heart of the language you have to. Given this reality, some documentation would be nice!


Conclusions

Clojure is a nice language, but in some parts it is still a little immature; some of these gotchas will disappear in time. The error message about Future’s is trivial to fix, for instance. Some of them already can be avoided with libraries: for example, the backtick issue can be avoided using an alternative implementation. Others, will I think, stick. Symbols will remain functions I suspect. The last issue, that of a public API, must be fixed if Clojure is to mature.

One gotcha I don’t mention is the lack of a type-system. There are many times when programming Clojure when I have created a bug that a type-system would have picked up instantly. This must, however, be set against those times when you stare at the screen in depression trying to work out why a perfectly innocuous piece of code will not compile. In the end, it’s often easier to debug running code, than it is to fix a broken type error. Both forms of problem are something you learn to live with, depending on your choice of language.

I am please to announce the second full release of Tawny-OWL, my library for fully programmatic development of OWL ontologies. Tawny-OWL now has a fairly large feature set and is becoming a rich development environment.

Perhaps the biggest single change in this release in terms of code base is the least immediately obvious from the user perspective. Previously a large part of the code base was using Java reflection and therefore quite slow. I have now type-hinted all the namespaces meaning that tawny should never reflect. The practical upshot of this is that Tawny runs faster; in the most extreme case, tawny.render is about 5x faster.

The most difficult change for me has be the regularisation of :subclass and :subproperty keywords. The reasons behind this have been described in great detail previously (http://www.russet.org.uk/blog/2985). This was not an easy change to make as it breaks the syntax significantly; I should have made the change before Tawny 1.0, but I didn’t. I am hopefully that there will not be similar changes in future.

The roadmap for Tawny 1.2 is relatively simple; currently there is no good way to search over an ontology and to extract classes fulfilling certain requirements (short of direct invocation of the OWL API). I now have a simple implementation of search facilities operating over OWL using a combination of core.logic and tawny.query; hardening and extending this will be the next logical (ahem!) step.

Bibliography

Before commit eb2f0e04, I used to have this function in tawny.owl.

(defbdontfn
  add-subclass
  {:doc "Adds one or more subclass to name in ontology."
   :arglists '([name & subclass] [ontology name & subclass])}
  [o name subclass]
  (add-axiom o
             (.getOWLSubClassOfAxiom
              (owl-data-factory)
              (ensure-class o name)
              (ensure-class o subclass))))

The idea is, as the name suggests to add a subclass relationship to the ontology; on the face of it, everything looks fine. However, a closer look at the OWL API raises a question:

getOWLSubClassOfAxiom(OWLClassExpression subClass, OWLClassExpression superClass)

The subclass parameter in Clojure maps to the superClass parameter in Java. The subclass in Clojure is actually the superclass.

If we compare the property equivalent in Tawny, things seem more regular:

(defbdontfn add-superproperty
  "Adds all items in superpropertylist to property as
a superproperty."
  [o property superproperty]
  (add-axiom o
             (.getOWLSubObjectPropertyOfAxiom
              (owl-data-factory)
              (ensure-object-property o property)
              (ensure-object-property o superproperty))))

and the equivalent Java:

getOWLSubObjectPropertyOfAxiom(OWLObjectPropertyExpression subProperty,
                               OWLObjectPropertyExpression superProperty)

The names of the parameters are now the same way around in Clojure and Java. So, have I made a mistake in Tawny with subclass handling? Actually, no, because we get strangeness at a different point with properties; consider the object-property-handlers which map between frames and the functions which implement them:

(def ^{:private true} object-property-handlers
  {
   :domain add-domain
   :range add-range
   :inverse add-inverse
   :subproperty add-superproperty
   :characteristic add-characteristics
   :subpropertychain add-subpropertychain
   :disjoint add-disjoint-property
   :equivalent add-equivalent-property
   :annotation add-annotation
   :label add-label
   :comment add-comment})

So, the :subproperty: frame is implemented with the add-superproperty function. As might be expected, :subclass is implemented with add-subclass

Even without this oddness, the problem can be seen when considering just the add-* functions. Consider, add-label:

(defbmontfn add-label
  "Add labels to the named entities."
  [o named-entity label]
  (add-annotation
   o
   named-entity
   [(tawny.owl/label label)]))

The semantics of this are that the third argument, label, is added to the second, named-entity as a label. It is slightly more complex than this; the b in defbmontfn means broadcast — add-label is actually variadic and flattens meaning that any number of labels can be added.

With add-subclass the semantics are reversed; the second argument becomes a subclass of the third (or, again, because of broadcasting, the third or subsequent arguments). And add-subclass is inconsistent here — all of the other add-* have the same semantics as add-label.

So, clearly, both add-subclass and the :subproperty frame have problems, and are not consistent with the rest of the API. Two important parts of Tawny-OWL have been implemented backward. How did this happen?


Investigating Manchester Syntax

We can investigate this further, by considering another inconsistency with Tawny. Considering the object-property-handlers above, we can see that while :subproperty is implemented with add-superproperty, :subpropertychain is implemented with add-subpropertychain.

The slot names in Tawny come (nearly) directly from Manchester syntax; so, let us compare Manchester syntax with the functional syntax for sub-properties and sub-property chains, using the OWL Primer. In Manchester syntax:

ObjectProperty: hasFather
   SubPropertyOf: hasParent

In functional syntax:

SubObjectPropertyOf(
   :hasFather
   :hasParent
)

Compare this to the equivalent declaration for subproperty chain.

ObjectProperty: hasGrandparent
   SubPropertyChain: hasParent o hasParent

Or in functional syntax:

SubObjectPropertyOf(
   ObjectPropertyChain( :hasParent :hasParent )
   :hasGrandparent
 )

The filler for SubPropertyChain: comes first, while for SubProperty: is comes second.

This suggests that the SubPropertyOf: and SubPropertyChain: frames are back-to-front from each other (this is the values of the slots appear in different orders in the two syntaxes). So, with the former, SubPropertyOf: I am stating that the entity (hasFather) is related to the filler (hasParent) and that the filler (hasParent) is the super property. With the latter, SubPropertyChain: I am stating that the entity (hasGrandparent) is related to the filler (hasParent o hasParent) and that the filler (hasParent o hasParent) is the sub property.

So, the two appear to be inconsistent with each other. So, let’s consider a further analysis of the other slots. Consider, for example:

A
  Annotations: rdfs:label B

which means B is an annotation of A.

A
 EquivalentTo: B

means B is equivalent to A (or, in this case, that A is equivalent to B as equivalance is symmetrical).

A
  Domain: B

means B is a domain of A

A
  Type: B

means B is a type of A.

All of these are consistent with each other: the filler (B) has a relationship to the entity (A) which is defined by the slot (type), with the caveat that the EquivalentTo relationship is symmetric.

Now

A
  SubClassOf: B
A
  SubPropertyOf: B

are backward: the entity (A) has a relationship to the filler (B) defined by the slot (SubClassOf:, SubPropertyOf:) – it’s why the Of preposition has been added. It is not possible to add the same preposition to the other slots; although it is possible to add has to the beginning. So, for example, the natural language semantics of these statements preserves their OMN meaning:

A HasAnnotation: B
A HasType: B
A HasKey: B

Of these, only the latter is actually OMN. The only other slots with prepositions are EquivalentTo and SameAs — you could change these to has as well.

A HasEquivalent: B
A HasSame: B

This probably reduces the readability over all, but it does at least maintain the semantics. It is for this reason that I say SubClassOf: is backward; to be consistent, it should be Super:

So

A Super: B

means B is a superclass of A. Now, we could add the has preposition to the start, while preserving the natural language semantics.

A HasSuper: B

Everything that I have said here is also true of SubPropertyOf: which behaves in the same way as SubClassOf: (i.e. backwards wrt to most slots).

Going back to the very early question, SubPropertyChain: (note, not SubPropertyChainOf:) is the same way around as most slots and the opposite way around from SubPropertyOf:

A SubPropertyChain: B o B

could be replaced with

A HasSubPropertyChain: B o B

In summary, for Manchester syntax SubClassOf: and SubPropertyOf: frames are backward with respect to all the other frames.


The Implications for Tawny

Unfortunately, the situation in Tawny-OWL was slightly worse than for Manchester syntax. While writing an early version of the karyotype ontology (1305.3758) by hand, I found typing too hard so removed the prepositions (:subclass and not :subclassof). Combined with the lack of CamelCase, this seemed a cleaner syntax. But it has exacerbated the issues described here.

Although, I have become aware of this problem before the release of the first full version of Tawny, I decided that consistency with Manchester syntax was worth the hassle. My recent experiments with literate ontologies (http://www.russet.org.uk/blog/2979), however have made me realise that I could not leave the situation as it is. One key feature of Tawny is that it (normally) forces declaration of entities before use which avoids simple spelling mistakes common when writing Manchester syntax by hand. However, only having access to a :subclass slot means that ontologies must be declared from the top of the inheritance hierarchy downward. For a literate ontology, this restriction seems unnecessary, and places an unfortunate emphasis on the upper ontology. I would like also to be able to build from the bottom up.

Neither having the semantics of add-subclass backward, nor the :subproperty add-superclass solution work well as it stands, and extending this to a :superclass slot would make the situation worse. In short, the only sensible fix was to diverge from OWL Manchester syntax, and deprecate the use of :subclass and :subproperty. At the same time, I decided to remove some extra typing. Therefore, :subclass has become :super (shortening and reversing the natural language semantics, retaining the logical semantics), and the new slot :sub has been added. Likewise, :subproperty has become :super and a new slot :sub introduced for properties also. As well as avoiding extra typing, removing the suffix has meant that I can leave :subclass and :subproperty in place but deprecated; the alternative of just reversing their semantics seemed unfortunate. Only the semantics of add-subclass has been broken, being reversed.

The inconsistency with Manchester syntax is currently a little painful, especially as the :subclass slot has been around since the early days of Tawny (http://www.russet.org.uk/blog/2214). The advantage, however, is that I have a simple rule to remember: A :s B means “A has :s B” or equivalently, “B is :s of A“. For this reason, and because it paves the way for richer literate ontologies, I feel that this is a good change.

Bibliography