Teaching Programming to People. It’s easy, right?

I was doing a literature search for a different subject (which will appear soon), and found a couple of articles related to teaching programming. I don’t know if you remember when you learnt programming, but you probably found it hard. I’ve had some experience of teaching programming: specifically, teaching C to undergraduates. Said undergraduates, as it happens, weren’t on a computing course (they studied Physics), and only turned up to the few classes they had a year because attendance was mandatory. The lectures, which weren’t compulsory, had fewer students showing up.

Teaching Python to Undergraduates

When I took the course, we were taught a Pascal variant on NeXTSTEP. I have some evidence that Algol had been the first programming language taught on the course; probably on an HLH Orion minicomputer. While Pascal was developed in part as a vehicle to teach structured programming concepts, the academics in the computing course at my department were already starting to see it as a toy language with no practical utility. Such justification was used to look for a different language to teach. As you can infer from the previous paragraph, we settled on C: but not before a test where interested students (myself included) who had, for the most part, already taken the Pascal course. The experiences with Python were written up in a Masters’ thesis by Michael Williams, the student who had converted the (Pascal-based, of course) teaching materials to Python.

Like Wirth, when Guido van Rossum designed Python he had teaching in mind; though knowing the criticisms of Pascal he also made it extensible so that it could be used as a “real” language. This extensibility was put to use in the Python experiment at Oxford, giving students the numpy module which they used mainly for its matrix datatype (an important facility in Physics).

What the report shows is that it’s possible to teach someone enough Python to get onto problems with numerical computation in a day; although clearly this is also true of Pascal and C. One interesting observation is the benefit of enforced layout (Python’s meaningful indentation) to both the students, who reported that they did not find it difficult to indent a program correctly; and to the teachers, who found that because students were coerced into laying out their code consistently, it was easier to read and understand the intention of code.

An interesting open question is whether that means enforced indentation leads to more efficient code reviews in general, not just in an expert/neophyte relationship. Many developers using languages that don’t enforce layout choose to add the enforcement themselves. Whether this is an issue at all when modern IDEs can lay out code automatically (assuming developers with enough experience of the IDE to use that feature) also needs answering.

The conclusion of this study was that Python is appropriate as a teaching language for Oxford’s Physics course, though clearly it was not adopted and C was favoured. Why was this? As this decision was made after the report was produced, it doesn’t say, and my own recollection is hazy. I recall the “not for real world use” lobby was involved, that it was also possible to teach C in the time involved, and that while many people wanted to teach Java this was overruled due to a desire to avoid OO. The spurned Java crowd preferred C for its Java-like syntax.

Wait, C?

The next part of this story wasn’t published, but I’ll cover it anyway just for completeness. The year after this Python study, the teaching course did an A/B test where half of the first year course was taught Python, and half C. Whatever conclusions were drawn from this test, C won out so either there was no significant difference in that type of course or the “real worldness” of C was thought to be greater than that of Python. I remember both being given as justifications, but don’t know whether either or both were retrofitted.

Whatever the cause, teaching C was sufficiently not bad that the course is still based on the language.

Going back to that Java decision. How good is Java as a teaching language?

Analyses of Student Programming Errors In Java Programming Courses

I’m going to use the results of this paper to argue that Java is not good as a teaching language.

Programming errors can be categorized as syntax, semantic and logic. A syntax error is an error due to incorrect grammar. Syntax errors are often detected by a program called a compiler, if the language is a compiled language such as Java. A semantic error is an error due to misuse of a programming concept, despite correct syntactic structure. Semantic errors are caught when the program code is compiled. A logic error occurs when the program does not solve the problem that the programmer meant for it to solve.

[Notice that the study is only investigating errors: it’s not completely obvious but “bugs” aren’t included. The author’s only reporting on things that are either compiler or runtime errors in Java-land, like typos and indices out of bounds.]

Categorization of errors of the present study into syntax, semantic, runtime and logic revealed that syntax errors made up 94.1%, semantic errors 4.7% and logic
errors 1.2%.

In the ideal world, a programming course teaches students the principles of programming and how to combine these to solve some computational problem. In learning these things, you expect people to make semantic and logic errors: they don’t yet know how these things work. Syntax errors, on the other hand, are the compiler’s way of saying “meh, you know what you meant but I couldn’t be bothered to work it out”, or “I require you to jump through some hoops and you didn’t”.

You don’t want syntax errors when you’re teaching programming. You want people to struggle with the problems, not the environment in which those problems are presented. Imagine failing a student because they pushed the door to the exam room when it was supposed to be pulled: that’s a syntax error. One of the roles of a demonstrator in a computing course is to be the magic compiler pixie, fixing syntax errors so the students can get back on track.

OK, so not Java. What else is out there?

C++

The Oxford Physics investigation didn’t publish any results on the difficulty of teaching C. Thankfully, the Other Place is more forthcoming. Tim Love, author of Tim Love’s Cricket for the Dragon 32 and teacher of C++ to Engineering undergraduates blogged about difficulties encountered defining functions in C++. There’s no frequency information here, just representative problems. While most of the problems are semantic rather than syntactic, with some logic problems too, we can’t really compare these with the Java analysis above anyway.

The sorts of problems described in this blog post are largely the kind of problems you want, or at least don’t mind, people experiencing while you’re teaching them programming: as long as they get past them, and understand the difference between what they were trying and what eventually worked.

In that context, comments like this are worrying:

I left one such student to read the documentation for a few minutes, but when I returned to him he was none the wiser. The Arrays section of the doc might be sub-optimal, but it can’t be that bad – it’s much the same as last year’s.

So the teacher knows that the course might have problems, but not what they are or how to correct them despite seeing the failure modes in first person. This is not isolated: the Oxford course linked above has not changed substantially since the version I wrote (which added all the Finder & Xcode stuff).

So, we know something about the problems encountered by students of programming. Do we know anything about how they try to solve those problems?

An analysis of patterns of debugging among novice computer science students

We’ve already seen that students didn’t think to use the interactive interpreter feature of Python when the course handbook stopped telling them about it. In this paper, Ahmadzadeh et al modified the Java compiler to collect analytics about errors encountered by students on their course (the methodology looks very similar to the other Java paper, above). An interesting statistic noticed in §3.1, a statistical analysis of compiler errors:

It can be seen from this table that the error that is most common amongst all the subjects is failing to define a variable before it is used. This was almost always the highest frequency error when teaching a range of different concepts.

It’s possible that you could avoid 30-50% of the problems discovered in this study by using a language that doesn’t require explicit declaration of variables. Would the errors then be replaced by something else? Maybe.

In section 4, the authors note that there’s a distinction between being able to debug effectively and being able to program well: most people who are good at debugging are also good programmers, but a minority of good programmers are good at debugging. Of course this is measuring a class of neophytes so it’s possible that this gap eventually closes, but more work would need to be done to demonstrate or disprove that.

I notice that the students in this test are (at least, initially) fixing problems introduced into a program by someone else. Is that skill related to fixing problems in your own code? Might you be more frustrated if you think you’ve finished an assignment only to find there’s a problem you don’t understand in it? Does debugging someone else’s program support the educational goal? This paper suggests that the skills are in fact different, which is why “good” programmers can be “bad” debuggers: they understand programming, but not the problem solved by someone else’s code. They also suggest that “bad” programmers who do well at fixing bugs do it because they understand the aim of the program, and can reason about what the software should be doing. Perhaps being good at fixing bugs means more understanding of specifications than of code—traditionally the outlook of the tester (who is called on to find bugs but rarely to fix them).

Conclusions and Questions

There’s a surprising amount of data out there on the problems faced by students being taught programming—some of it leads directly to actionable conclusions, or at least testable hypotheses. Despite that, some courses look no different from courses I taught in 2004-2006 nor indeed any different from a course I took in 2000-2001.

Judicious selection of language could help students avoid some of the “syntactic” problems in programming, by choosing languages with less ceremony. Whether such a change would lead to students learning faster, enjoying the topic more, or just bumping up against a different set of syntax errors needs to be tested. But can we extrapolate from this? Are environments that are good for student programmers good for novices in general, including inexperienced professionals? Can this be taken further? Could we conclude that some languages waste time for all programmers, or that becoming expert in programming just means learning to cope with your environment’s idiosyncrasies?

And what should we make of this result that being good at programming and debugging do not go together? Should a programming course aim to develop both skills, or should specialisation be noticed and encouraged early? [Is there indeed a degree in software testing offered at any university?]

But, perhaps most urgently, why are so many different groups approaching this problem independently? Physics and Engineering academics are not experts at teaching computing, and as we’ve seen science code is not necessarily the best code. Could someone aggregate these results from various courses and produce the killer course in undergraduate computing?

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.