Elegant Object-oriented Software Design via Interactive, Evolutionary Computation

The abstract of this paper from the ArXiv had me concerned:

Design is fundamental to software development but can be demanding to perform. Thus to assist the software designer, evolutionary computing is being increasingly applied using machine-based, quantitative fitness functions to evolve software designs. However, in nature, elegance and symmetry play a crucial role in the reproductive fitness of various organisms. In addition, subjective evaluation has also been exploited in Interactive Evolutionary Computation (IEC). Therefore to investigate the role of elegance and symmetry in software design, four novel elegance measures are proposed based on the evenness of distribution of design elements. In controlled experiments in a dynamic interactive evolutionary computation environment, designers are presented with visualizations of object-oriented software designs, which they rank according to a subjective assessment of elegance. For three out of the four elegance measures proposed, it is found that a significant correlation exists between elegance values and reward elicited. These three elegance measures assess the evenness of distribution of (a) attributes and methods among classes, (b) external couples between classes, and (c) the ratio of attributes to methods. It is concluded that symmetrical elegance is in some way significant in software design, and that this can be exploited in dynamic, multi-objective interactive evolutionary computation to produce elegant software designs.

The “design” of a software system is, to me, a part of the social science aspect of software engineering. Does the design make it easy for me to work out how the software functions? Can I see what I need to change to fix some problem? If I don’t fix this problem, can you also see what you’d need to change? Does working with this design cause an emotional response?

With this mindset, it’s hard to understand how an objective metric of software design can be formulated. Without that understanding, it’s impossible to see any value in letting a software system design another software system that human developers are going to work on. In fact, it seems entirely back to front: the design is (to me) the part that needs a combination of experience, insight and serendipity to create. If a computer can then automatically fill some of the details in a way that saves time and reduces error, that would be useful. Doing it the other way around means human programmers become blue-collar subordinates to the (literal) software architect.

So, I didn’t exactly jump into the rest of this paper with an open mind, which I recognised was a problem I needed to deal with so I ploughed on anyway. I started by reading “A Survey on Search-based Software Design”, along with some of the other references, with a view to working out just what it was that these researchers are trying to automate. In the event, this post took a couple of weeks to write at my usual “whenever I get a chance” rate—there was a lot to understand.

What’s Going On?

The idea is that certain principles in object-oriented design can be assigned a quantitative value: a “score”, if you will. So you could score a design on how tightly-coupled the classes are, on how many responsibilities each class has, and on other features. You can also decide that a good design would aim to lower or increase particular scores; for example that looser coupling and fewer responsibilities are “better”. You could decide that some designs are just “stillborn”, and no matter how well they do on some metrics you’re never going to use them: a circular reference, or a class with no responsibilities, might instantly be discarded.

Now imagine deriving some initial design for your software, for example from a collection of use cases. (You may be wondering how, and that’s a good question: if your initial guess at the design is derived automatically from the use cases, then the use cases themselves need to be pretty precise, complete and unambiguous. In other words, they need to be written in a computer programming language.[*]) You score that design according to the criteria you defined, then make some “mutations” (which, in the case of evolutionary software design, means applying design patterns from a catalogue). The mutations that score better, you keep, combining them and mutating them further. Eventually you should have a collection of design candidates that are all much better than the initial guess.

[*]As a thought experiment, take the use-case diagram for a cinema booking system used as one of the inputs for this paper’s methods. Try designing a software system to implement these use cases; every time you have a question that isn’t answered by the diagram, make a note but _don’t assume an answer_. How many questions do you end up with? Are you happy using a design in which these questions are unanswered? My guess is you’ll be OK to leave some of them, designing the software to be flexible to different answers. But some will cause more problems unless they’re addressed.

Is This Useful?

I don’t feel like I got over the bias that I went into this post with: that the point of software design is to communicate something about that software among the various people who will be working on it. Computer-generated design is like computer-generated prose, when viewed from that perspective: uncannily close, but no substitute for the real thing.

What you could get from a technique like this are proposals for improvement on designs: indeed one branch (or clade, perhaps) of research in which genetic algorithms are applied to software design is in refactoring. One can imagine future UML tools (or IDEs) offering suggestions at the architecture level, just as current IDEs can offer suggestions for individual lines or methods.

That’s basically what this paper is driving at: the “interactive” part of Interactive Evolutionary Computation. Human participants created the first versions of the designs, and qualitatively evaluated the later iterations (which were both produced and also evaluated by the software). Ultimately, software designers were called upon to reward the “better” designs and to decide when to stop the iteration: i.e. they chose whether to accept the “suggestions” made by the evolutionary algorithm.

So is this technique a step on the way to having that tool? Looking at table 4, you might think that the software did create better designs than the humans in two thirds of cases. Such is the danger of bold typeface. Look again at the standard deviations. Unfortunately, discussing the results with a tame statistician, we couldn’t agree that the analysis in the paper shows the significant results the authors claim. As an example, it’s not clear that pairing any two metrics actually makes sense, or that just because one measurement comes out consistently lower overall it’s a better indicator of “elegance” than another (which might vary more between designs: something we’re not told here).

The authors are on clearer footing when evaluating the relationship between the rewards given and the metrics: ignoring the software algorithm completely, do people consistently think of some particular property of a software design as indicative of elegance? While they’ve only got 7 participants (who, assuming you know the group, can probably be de-anonymised based on the information presented…just saying), and it’s risky to draw general conclusions from such a small number of people[*], there are early indications here of consistency.

[*]particularly as they’re all in academia, and probably all in the same institution.

On Scientific Computing

Or: Not everyone works the way you work

Currently doing the rounds on Twitter is a paper from the ArXiV called Best Practices for Scientific Computing—a paper with 13 authors and 6 pages,including a page-long collection of references. Here’s the abstract:

Scientists spend an increasing amount of time building and using software. However, most scientists are never taught how to do this efficiently. As a result, many are unaware of tools and practices that would allow them to write more reliable and maintainable code with less effort. We describe a set of best practices for scientific software development that have solid foundations in research and experience, and that improve scientists’ productivity and the reliability of their software.

Let me start with an anecdote. It’s 2004, and I’ve just started working as a systems manager in a university computing lab. My job is partly to maintain the computers in the lab, partly to teach programming and numerical computing to Physics undergraduates, and partly to write software that will assist in said teaching. As part of this work I started using version control, both for my source code and for some of the configuration files in /etc on the servers. A more experienced colleague saw me doing this and told me that I was just generating work for myself, that this wasn’t necessary for the small things I was maintaining.

Move on now to 2010, and I’m working in a big scientific facility in the UK. Using software and a lot of computers, we’ve got something that used to take an entire PhD to finish down to somewhere between one and eight hours. I’m on the software team, and yes we’re using version control to track changes to the software and to understand what version is released. Well, kindof, anyway. The “core” is in version control, but one of its main features is to provide a scripting environment and DSL in which scientists at the “lab benches”, if you will, can write up scripts that automate their experiments. These scripts are not (necessarily) version-controlled. Worse, the source code is deployed to the experimental stations so someone who discovers a bug in the core can fix it locally without the change being tracked in version control.

So, a group does an experiment at this facility, and produces some interesting results. You try to replicate this later, and you get different results. Could be software-related, right? All you need to do is to use the same software that the original group used…unfortunately, you can’t. It’s gone.

That’s an example of how scientists failing to use the tools from software development could be compromising their science. There’s a lot of snake oil in the software field, both from people wanting you to use their tools/methodologies because you’ll pay them for it, and from people who have decided that “their” way of working is correct and that any other way is incorrect. You need to be able to cut through all of that nonsense to find out how particular tools or techniques impact the actual work you’re trying to achieve. Current philosophy of science places a high value on reproducibility and auditing. Version control supports that, so it would be beneficial for programmers working in science to use version control.

But version control is only one of the 10 recommendation sections in this paper (another is about using the computer to record history, something that I’ll assume is covered well by the above discussion). That leaves eight other sections, which each contain numbered pronouncements about how scientists should write software.

Were you surprised?

I expect, if you write software in the commercial sector, you wouldn’t find any of their suggestions contentious: examples include naming things meaningfully, using a consistent convention for names and layout, don’t repeat yourself, and so on. I included this paper here to start discussion of an important point.

What goes on in commercial software engineering is not the be-all and end-all of software development. Scientific software has been around for as long as there have been computers to run software on, and indeed not only is some really old software still in use but the people who wrote it are still around and maintaining it. In the aforementioned university lab, one of my tasks was to help a professor who’d been using his home-grown FORTRAN FITS manipulation routines for at least two decades. Every system he’d used it on—most recently PowerPC, MIPS and Alpha workstations—had been big-endian and he didn’t know why it gave the wrong results when used on our new Intel Mac. His postdocs and PhD students were using the same code—in the same FORTRAN language, which he’d either taught them or given them a book on. And then of course when they moved to a different institution they’d take that code and that understanding of code with them.

I imagine that many professional programmers are not surprised by the validity of (m)any of the statements made in this paper, but by the necessity of stating them. No, not everyone uses version control, or thinks that agile is the best thing ever, or uses consistent naming conventions throughout a source file. Indeed in my experience of scientific programming, use of a symbolic debugger wasn’t If you consider all of these problems to be “solved” then you’re really only looking at a limited part of the world of software development. It’s not just scientific computing that doesn’t match that worldview; what about all the people out there for whom programming is a bunch of Excel formulae and maybe the odd VBA macro pasted from a website?

In both commercial and scientific software development, understanding and behaviour is spread by sharing knowledge from masters to apprentices. I think that the reason there’s such a big difference in practice could be due to the longer generations in scientific software. That 20+-year-old FITS code still works, why change it? And those 20+-year-old practices that created the FITS code, well they still work too, don’t they?

Which of these things actually matters?

Based on my own experience I’d assert that all of them are important things for scientific programmers to know about. I’ve argued, hopefully convincingly, that version control has an important part to play in the scientific process: numerical analysis is a key part of many experiments and like the rest of the method it should be available for inspection and repetition. Science is also a collaborative activity, so it makes sense that some of the recommendations would be about collaboration: document the purpose of the code instead of its mechanics, write programs for people.

Could I justify those assertions with figures? Probably not. Is that important? Well, actually it probably is. Of the researchers I’ve worked with (bear in mind this has always been in Physics), even many who are heavily invested in computational methods see programming (rightly) as a means to an end, and aren’t likely to try new-to-them techniques in programming just for the sake of programming. Despite any rational economic benefit, they’d rather stick with what they know and focus on getting new results without any surprises.

If you want to say “it’s better to work this way” or “you’ll get results quicker like this”, to a bunch of physicists, you have to show them data to prove it. A paper like the one I’m discussing here will likely be read, if it:

  1. gets published
  2. said publication happens in a relevant journal
  3. said publication is picked up and circulated in enough news sources that researchers who don’t read the publishing journal get wind

On the other hand, it’s likely that the article’s tone will ensure that it only preaches to the converted. Nothing in the paper says “this is actually better”, just “professional programmers do these things”. Exercises like Software Carpentry are likely to only appeal to people who already have an interest in bettering their own programming abilities. As I said, most researchers I know don’t: they want to publish, and programming is a necessary—albeit complex—tool helping them to achieve that.

Why is this suddenly an issue?

It isn’t. A very quick search for errors in scientific computing yielded papers published across the last two decades, and I could probably find more. The abstracts for these (I did say it was a very quick search) include some pining for the use of skills from software engineering, or a closer focus by software engineering researchers on scientific computing projects.

What can be done about it?

That’s a very good question. If we knew what to do to improve the quality of any software production effort, there’d be a lot more good software in the world :). If the techniques from commercial software really would help make scientific software better, why wait for the scientists to apply them? Plenty of scientific software is open source, so in the case of things like analysis tools and automatic tests, sufficiently motivated individuals could just apply those things then demonstrate to the project maintainers how much of a difference they’ve made. Sure, there will be problems: I once worked on some software that could only be successfully executed if there was a particle accelerator connected to your workstation. But the first thing I did was to make a virtual particle accelerator – demonstrating how much easier it was to make progress if you could do it away from the experiment.

This brings me onto another option: scientific computing teams can employ commercial developers. I’ve seen it happen, I’ve seen it work and I’ve seen it fail. The ways in which it work include sharing of knowledge from both disciplines, discussing and improving practices. The ways in which it fails come down to frustration on both sides: scientific programmers feel that refactoring is change for change’s sake, perhaps, and software engineers think that not using their favourite practices is the realm of cowboys. That means that for a cross-discipline software team to work, it needs good leadership: the team needs to be designed to appreciate the different skills and viewpoints brought by the different members. And now we’ve gone fully out of the realm of science into management techniques.

Representativeness in Software Engineering Research

The first paragraph describes the context of this post in relation to the blog on which it originally appeared, not blog.securemacprogramming.com.

For this post, I wanted to go a little bit meta. One focus of this blog will be on whether results from academic software engineering are applicable to the work I do as a commercial software developer, so it was hard to pass up this Microsoft Research paper on representativeness of research.

In a nutshell, the problem is this: imagine that you read some study that shows, for example, that schedule slippage on a software project is significantly lessened if developers are given two digestive biscuits and a cup of tea at 4pm on working days. The study examined the breaktime habits of developers on 500 open source projects. This sounds quite convincing. If this thing with the tea and biscuits is true across five hundred projects, it must be applicable to my project, right?

That doesn’t follow. There are many reasons why it might not follow: the study may be biased. The analysis may be wrong. The biscuit thing may be significant but not the root cause of success. The authors may have selected projects that would demonstrate the biscuit outcome. Projects that had initially signed up but got delayed might have dropped out. This paper evaluates one cause of bias: the projects used in the study aren’t representative of the project you’re doing.

It’s a fallacy to assume that just because a study has a large sample size, its results can be generalised to the population. This only applies in the case that the sample represents an even slice of the population. Imagine a world in which all software projects are either written in Java or LISP. Now it doesn’t matter whether I select 10 projects or 10,000 projects: a sample of LISP practices will not necessarily tell us anything about how to conduct a Java project.

Conversely a study that investigates both Java and LISP projects can—in this restricted universe, and with the usual “all other things being equal” caveat—tell us something generally about software projects independent of language. However, choice of language is only one dimension in which software can be measured: the size, activity, number of developers, licence and other factors can all be relevant. Therefore the possible phase space of important factors can be multidimensional.

In this paper the authors develop a framework, based on work in medicine and other fields, for measuring and maximising representativeness of a sample by appropriate selection of projects along the dimensions of the problem space. They apply the framework to recent research.

What they discovered, tabulated in Table II of the paper, is that while a very small, carefully-selected sample can be surprisingly representative (50 out of ~20k projects represented ~15% of their problem space), the ~200 projects they could find analysed in recent research only scored around 9% on their representativeness metric. However in certain dimensions the studies were highly representative, many covering 100% of the phase space in specific dimensions.

Conclusions

A fact that jumped out at me, because of the field I work in, is that there are 245 Objective-C projects in the universe studied by this paper (the projects indexed on Ohloh) and that not one of these is covered by any of the studies they analysed. That could mean that my own back yard is ripe for the picking: that there are interesting results to be determined by analysing Objective-C projects and comparing those results with received wisdom.

In the discussion section, the authors point out that just because a study is not general, does not mean it is not useful. You may not be able to generalise a result gleaned from analysing (say) Java developer tools to all software development, but if what you’re interested in is Java developer tools then that is not a problem.

What this paper gives us, then, is not necessarily a tool that commercial developers can run out and use. It gives us some important quantitative context on evaluating the research that we do read. And, should we want to analyse our own work and investigate hypotheses about factors affecting our projects, it gives us a framework to understand just how representative those analyses would be.

Garbage-collected Objective-C

When was a garbage collector added to Objective-C? If you follow Apple’s work with the language, you might be inclined to believe that it was in 2008 when AutoZone was added as part of Objective-C 2.0 (the AutoZone collector has since been deprecated by Apple, and I’m not sure whether anyone else ever adopted it).

With a slightly wider knowledge of the language’s history, you can push this date back a bit. The GNUstep project—a Free Software reimplementation of Apple’s (formerly NeXT’s) APIs—has been using the Boehm–Demers–Weiser collector for a while. How long? I can’t tell exactly, but a keyword search in the project’s version control logs makes me think that most of the work to support it was done by one person in mid-2002:

r13976 | nico | 2002-06-26 15:34:16 +0100 (Wed, 26 Jun 2002) | 3 lines

Do not add -lobjc_gc -lgc flags when compiling with gc=yes – should now
be added automatically by gnustep-make


r13971 | nico | 2002-06-25 18:28:56 +0100 (Tue, 25 Jun 2002) | 2 lines

Tidyup for gc=yes with old compilers


r13970 | nico | 2002-06-25 18:23:05 +0100 (Tue, 25 Jun 2002) | 2 lines

Tidied code to compile with gc=yes and older compilers


r13969 | nico | 2002-06-25 13:36:11 +0100 (Tue, 25 Jun 2002) | 3 lines

Tidied some indentation; a couple of insignificant changes to have it compile
under gc


r13968 | nico | 2002-06-25 13:15:04 +0100 (Tue, 25 Jun 2002) | 2 lines

Tidied code which wouldn’t compile with gc=yes and gcc < 3.x


r13967 | nico | 2002-06-25 13:13:19 +0100 (Tue, 25 Jun 2002) | 2 lines

Tidied code which was not compiling with the garbage collector


r13966 | nico | 2002-06-25 13:12:17 +0100 (Tue, 25 Jun 2002) | 2 lines

Tidied code which was not compiling with gc=yes

That was, until fairly recently, the earliest example I knew about. Then I discovered a conference talk by Paulo Ferreira:

Reclaiming storage in an object oriented platform supporting extended C++ and Objective-C applications

This is a paper presented at “1991 International Workshop on Object Orientation in Operating Systems”. 1991. That is—obviously—11 years before GNUstep’s GC work and 17 years before Apple released AutoZone.

Comandos

The context in which this work was being done is a platform called Comandos. I’d never heard of that before—and I thought I knew Objective-C!

Judging from the report linked above, Comandos is a platform for distributed and parallel object-oriented software, based on UNIX but supporting multiple variants. The fact that it was created in 1986 means that both the languages supported—Objective-C and C++—were new at the time. Indeed the project was contemporary with the development of NeXTSTEP, which was publicly released to developers in 1988.

The 1994 summary report doesn’t mention Objective-C: just C++, Eiffel and a bespoke language called Guide. It’s possible that the platform supported ObjC simply because they used gcc which picked up ObjC support during the life of Comandos; however this seems unlikely as there would be significant work in making Objective-C objects work with their platform’s distributed messaging interface and persistence subsystem.

Why ObjC should be one of two languages mentioned (along with C++) in the 1991 paper on garbage collection, but zero of three mentioned (C++, Eiffel, Guide) in 1994 will have to remain a mystery for now. Looking into the references for Ferreira’s paper, I can find one mention of Objective-C as the inspiration for their own, custom C-based message dispatch system, but no indication that they actually used Objective-C.

The Garbage Collector

I’m not really an expert at garbage collectors. In fact, I have no idea what I’m doing. I appreciate them when they’re around, and leak or crash things occasionally when they’re not.

To my uneducated eye, the description of the Ferreira 1991 garbage collector and Apple’s description of their collector (no link I’m afraid, it was session 940 at WWDC 2008) look quite different. AutoZone is conservative (like B-W-D) and only works on Objective-C objects. Ferreira’s collector operates, like B-W-D, on any memory block including new C++ instances and C heap allocations. Apple’s collector is supposed to avoid blocking wherever it can, a constraint not mentioned in the Ferreira paper.

All of Comandos, GNUstep and Cocoa (Apple’s Objective-C framework) have systems for distributed objects that complicate collection: does some remote process have a handle on memory in my address space? The proxy system used by Cocoa and GNUstep make it easy to answer this question. Comandos used a different technique, where objects local to a process were “volatile” and objects shared between processes were “persistent”. Persistent objects were subject to a different lifecycle management process, so the Ferreira GC didn’t interact with them.

As an aside, Apple’s garbage collector also needed to provide a “mixed mode”—support for code that could be loaded into either a garbage-collected or manually managed process.

Conclusions

Memory management is hard. Making programmers do it themselves leads to all sorts of problems. Doing it automatically is also hard, and many different approaches have been tried over the last few decades. Interestingly, Apple has (for the moment) settled on a “none of the above” approach, using a compiler-inserted reference counting system based on the manual ownership tracking previously implemented by the frameworks.

What interests me most about this paper on Objective-C garbage collection is not so much its technical content (which it’s actually rather light on, containing only conversational overviews of the algorithms and no information about results), but the fact that it existed at all and I, as someone who considers himself an experienced Objective-C programmer, did not know anything about it or its project.

That’s why I started this blog [Ed: referring to the blog these posts are imported from] by discussing it. A necessary prerequisite to deciding whether the literature has something useful to tell us is knowing about its existence. I’m really surprised that it took so long for me to find out about something that’s almost directly related to my everyday work. Mind you, maybe I shouldn’t feel too bad: the author of AutoZone told me he hadn’t heard of it, either.

Programming Literate Manifesto

Late last year, I decided to set up a second blog, focusing on exploring the world of academic literature relevant to our work as people who make software. The tone and content was very different to what I usually write here. I’ve now decided that while it’s interesting to explore this material, it was a mistake to try creating a second identity for this. I want to write about it, this is where I write, it belongs here. There are currently only a few posts at the other blog, so I’m going to import them all. If you’ve already read them or this content doesn’t interest you, filter the “academia” category.

This first one set the stall for the remaining posts. One thing made clear in the manifesto was that I wanted to encourage discussion: I’m not convinced blog comments are the place for that so comments remain off for the time being.

Programming Literate Manifesto

This blog is written by what you might call a “practising software engineer”, working in the field of mobile software. I’m hoping for a few things from the articles here, which fall into three main categories:

  • introduce more of “the primary literature” to people at the software coal face. Explore the applicability of research material to what we’re doing. Bring some more critical appraisal to the field. Invite discussion from working programmers about the relevance of the articles discussed.
  • get input from academics about related work, whether the analyses here are balanced, and how the researchers see the applicability of the work covered here to current practice. Welcome academics to the discussions on the articles – in other words to make this blog part of the interface between research and practice.
  • find out about some interesting work and have fun writing about it.

Sources

Papers and articles in this blog have to come from where I can find them, obviously. Largely that’s going to mean using the following resources:

Where the articles I cover are available online I’ll be linking to them, preferring free downloads over paywalled sites. Yes, IEEE, I’m looking at you.

Sandbox

I don’t know how easy it is to be truly dispassionate when writing, so it makes sense to lay out my stall. Hopefully that means intrinsic biases can be uncovered.

In my opinion, “software engineering” is the social science that describes how people involved in making software work and communicate with each other—and to some extent how they communicate to the computers too, at least so far as the created software and source code are tools that enable collaboration and are also the result of such.

That makes it quite a wide discipline (perhaps actually an interface discipline, or multiple disciplines looking for an interface). There’s some sociology and ethnography involved in identifying and describing the culture or cultures of software teams and communities. There’s the management science side, attempting to define “success” at various activities related to making software, trying to discover how to measure for and maximise such success. Questions exist over whether programming is best taught as an academic or vocational discipline, so education science is also on-topic. Then there’s the usability/HCI side related to the tools we use, and the mathematics and computer science that go into the building of those tools.

Just because a field is not a “hard” science, does not mean that useful results cannot be derived. It means that you have to be quite analytical about how someone else’s results apply to your circumstances, perhaps. That’s not to dismiss evidence-based software engineering out of hand, but to say that any result that is said to apply to all of software engineering in general needs to be peered at quite closely.

About the name

It’s quite simply a pun on Donald Knuth’s Literate Programming.