Using games to Improve API Design Skills

$Revision: 1.1.1.1 $

Introduction

During the year 2006, Jaroslav Tulach and Tim Boudreau were invited to present at OOPSLA 2006 conference. There were two possible topics to talk about:

How to design an API to stand the test of time
Whole day seminar about NetBeans

The content of the first talk was more or less fixed. It had already been presented at JavaOne 2005 as well as JavaOne 2006 and the changes were likely to be just cosmetic. More interesting was the content of the other seminar. Indeed it could contain some talk about writing plugins for NetBeans, but a very tempting possibility would be to teach people how to write an API. In fact do a little API Fest.

Overview

The API Fest shall take a form of contest and shall teach participants especially about the evolution problems related to writing an API. People will be given a simple task to write API for, their work will be evaluated and then they will get modified task to improve the API. This sequence can be repeated multiple times. After that, their results will be evaluated. However instead of having a jury to select the nicest solution, the evaluation will be done by the contest participants themselves. Everyone will get access to all solutions and the goal will be to find evolution problem in the solutions done by others - e.g. to write a test that works for previous version of an API, but does not work in the next one. Points will be assigned for holes found in solutions provided by others as well as for writing own API in a bullet proof way.

July 2006

The world's premiere, the first run of the API Fest happened in middle of July 2006 and was played by NetBeans core team. The goal was to practise the API design skills and also to check whether such kind of contest is at all possible. If this contest was about to be repeated with the OOPSLA 2006 participants, there was a strong need to practise the contests, the rules and find out what works and what does not. The best practise is likely to be gained on professionals who spend most of their working days by designing APIs and that is why it was really excelent that the members of the NetBeans core team decided to participate in a pilot version of the API Fest.

The contest started on Wednesday, Jul 12, 2006 at 2pm CET. Participants met in a meeting room and get access to skeleton NetBeans project with a text of usecases describing what needs to be done. Then they worked for an hour and send the diff of their changes back to Jaroslav Tulach.

On Thursday Jul 13, 2006 at 2pm CET the participants met again and get a set of new, additional usecases. They worked for another hour to implement them and send the resulting diff to Jaroslav Tulach again.

On Friday Jul 14, 2006 an email was sent by JaroslavTulach describing how to get all sources from all participants and the part of the competition where the goal was to break API written by others. Participants were supposed to write a test showing an evolution problem in API produced by others. The set of such tests was supposed to be sent to Jaroslav Tulach by Sunday, Jul 16, 2006.

Results were announced on Monday, Jul 17, 2006. Everyone who found a hole in an API written by other contest participant got 1 point, those who created a bulletproof API, not hacked by anyone else got 5 points as a reward of successful defense.

So much for the overview of the whole API Fest. Let's now provide a detailed description of the course of the action.

Day 1

The world's first API Fest started on Wednesday Jul 13, 2006 with a simple task: Write an API that will allow construction and evaluation of boolean circuits. The participants got project template that contained empty Circuit.java as a suggested source file to put the API into and a test file CircuitTest.java containing the three tasks that the API should fullfil. The goal was to create the API and then write implementation for the the three empty test cases, so they run and pass against the API.

The reason why the initial quest of the API Fest was the API for boolean circuits (get more info at wikipedia topics about Truth table and Taugology) was the fact that the whole circuit is in fact just a net of connected circuit elements for NOT, AND and OR operations plus some input elements:

negation - has one input and one output and changes 0 on input to on output 1 and 1 to 0
and - has two inputs and one output. The output is 1 only if both inputs are 1, otherwise it is 0
or - has two inputs and one output. The output is 1 always, except in the case when both inputs are 0

As a result the API for it is relatively small and can be written in an hour or so, yet it is non-trivial as in most versions of the API it allows products of the API to be consumed by the API again, which creates an interesting self reference. Evolving such reference can then lead to very nice problems with backward compatibility. However that is the future, it is preliminary to talk about that at this point. More interesting is the description of the initial tasks as it was given in the CircuitTest.java:

Create a circuit to evaluate x1 and x2 and then verify that its result is false for input (false, true) and it is true for input (true, true).
Create a circuit to evaluate (x1 and x2) or x3 and then verify that its result is false for input (false, true, false) and it is true for input (false, false, true).
Create a circuit to evaluate (x1 or not(x1)) and then verify that its result is true for all values of x1.

The API Fest One participants did really good job and most of them managed to create their APIs after an hour work. Most of the solutions were pretty inspiring and overall of very high quality.

Try it yourself! Download the project template at apifest1-day1.zip. Follow the instructions in CircuitTest.java and write the API for the boolean circuit yourself! Btw. this is your last chance to do it without knowing anything about the work done by others. The rest of the document is going to describe their thinking, achievements, mistakes and reading it before trying own solution gives you significant competitive advantage.

However some of the solutions also revieled certain problems. Not in the solution itself, but more in the description and specification of the problem and the initial tasks.

Problem of Non-Public API Classes

At least two solutions forgot to make an important API class public (for example here). This mistake was not noticed at this stage of the API Fest, however in later stages of the competition caused a lot of troubles and harms. The reason why this was possible was the fact that the test class CircuitTest.java and the suggested APIs class Circuit.java were in the same package. As a result they could use package private and protected methods for calling each other and nobody noticed until it was too late.

The lesson to learn is that next time someone runs API Fest like this, the API class and test class shall be in different packages. Then the usage of the non-API methods and fields gets discovered immediatelly by the compiler.

The Immutability Problem

NetBeans core developers are pretty well trained in not exposing more than is needed and as a result a lot of the solutions were written pretty minimalisticaly. They did satisfy the given goals, however just the goals and nothing else. As a result, some of the solutions were not boolean circut at all! Those solutions satisfied all the explicitly given tasks, so one could do the computations with AND, OR and NOT elements, but to run the same computation with different input values, one had to create new boolean circut each time! See for example inputandoperation or alwayscreatenewcircuit .

The root cause of this problem lays in different understanding of the problem between the participants in the API Fest. The person who designed the task just could not imagine someone would write a circut that does not allow multiple evaluation with different input values. Some participants shared this knowledge (like the pinbasedsolution ), some participants did not. This can happen. Some people faced the circut problematic before and understood its complexity and what it is good for, for others this was completely new and they just do what was required, nothing more.

There is a clear simple advice: Always make sure you explain the problem domain clearly, so every participant understands the problem and solves the same quest. However this is obviously not very useful advice. As experience shows, regardless of how much one tries, there are always going to be problems like this. They can be minimized, however they cannot be prevented.

That is why the appropriate structural solution to this problem seems to be to be ready to insert new round of the competition, say day 1 and half and clearly specify the additional requirements that the API needs to fullfil (e.g. be able to run more computations on the same circuit) and give participants a time to get along each other. Of course this means that those who get it right during the first round, have nothing to do. However the alignment seems to be more important than such pauses, because for next quests, it is important that every API is in similar starting position.

Problem of Missing Implementation

There was one very creative and interesting solution created to solve the boolean circuit problem. It was based on parsing, see sources of the parsingsolution . The point was in specifying the logical formula as a string in form of x1 AND NOT(x1), parsing it into a representation of the circuit and then allowing repetitive evaluations with different variables.

This was pretty nice and flexible solution. It was excelentlly documented (unlike the other ones), however it had one problem - it had no implementation. No surprise! Writing expression parser in an hour is not very easy task and even googling for some existing implementation may not achievable in one hour. As a result this solution could not advance to next round.

It seems necessary to explain the participants explicitly and clearly that this is an API Fest obsessed by evolution problems and functional compatibility between different versions of one API. It is also necessary to repeat that API is everything one can depend on, including an implementation. So the whole point of the API Fest is to write a functional API. Its versions are then going to be compared against each other. That is why the correct implementation of the API is necessary, while the javadoc is pretty much useless.

Problem of Possible Incorrect Results

The last observed problem after day1, was that some implementations were incorrect, or at least allowed misuse of the API. For example the stackbasedsolution required a value of each variable to be specified on input as many times as it was used. As a result evaluation of x1 OR NOT(x1) which is a taugology could sometimes yield false, if the input of the API was not consistent.

Again, this solution satisfied all the quests for the API and as such it was accepted for next round. However it is different and as the starting line for next round should have been same for all solution, the appropriate action should have been to insert the day 1 and half round and request that the API was fixed and reported such inconsistency in input as a misuse and a problem in the usage of the API.

Solutions for Day 1

The APIs for representation of boolean circuit created during API Fest day 1 can be split into various groups. The most common group is a classic example of defensive NetBeans never expose more than you want. Althrough there are little differences, solutions like alwayscreatenewcircuit, elementbasedsolution, inputandoperation, pinbasedsolution and partially also stackbasedsolution do not expose constructors and use factory methods, make classes that shall not be subclassed final and for mutual communication use package private methods.

Exceptional in its implementation is the parsingsolution . However it does not contain the actual implementation as it would be hard to write expression parser during one hour. The slight mistake here is the fact that the Circuit class is not final, which would very likely bite the author in next round.

A special attention should be paid to the subclassingsolution as it does not solve the problem on the level of data structures like other solutions, but instead on meta-data structures - e.g. models of data structures. While other solutions have instances that represent the actual elements in the circuit, instances in this solution represent type of elements and in fact there are just three predefined - AND, OR, NOT. Indeed this is a little trick as it requires subclassing and does not allow composition, but it is an example of a little bit unexpected meta approach to solve the problem. It is not suprising that this solution was written by our meta modeling (MOF, UML, MDR) expert.

Day 2

Requirements imposed on every API change over its life time and the API Fest boolean circuit is not an exception. Quite opposite. The API Fest is here to boost the speed of changes to the limit. That is why the main goal of the day to is to absorb some significant change to the requirements and do it in a compatible way - e.g. in a way that all usages of the API from day 1 still continue to work. To simulate that, all the participants got a new test class with new quests and had to modify their APIs to continue to work for old quests and also work for the new one.

However due to the different style of the solution, first thing to do was to get all the APIs to the same starting possition. As mentioned in the list of the problems of Day 1, there were two major problems in some of the implementations:

In some cases the boolean circuit could not be reused multiple times. This was requested to be fixed during the Day 2 quests.
Some APIs allowed an improper use of the circuit, that allowed to evalute a circuit representing a taugology to false. It was also requested to fix this during Day 2 work.

In ideal world these two quests, that just aligned the competitors to the same starting line, would have been done isolated, without knowing the major quest of the Day 2, however as we had just two days for the coding period of the API Fest, this work had to be done all at once, with all its drawbacks - e.g. some participants had really hard time to fix their design from day 1 and also implement the newly required feature. Especially due to the fact that the feature was quite hard. Its main request was to turn the boolean circuit into probability circuit - e.g. something that instead of booleans computes on real values from range 0.0 to 1.0 represented by doubles.

This means that whereever a boolean was used to represent input or output values, one can now use any double number from >= 0 and <= 1. Still, to support backward compatibility, the operations with booleans have to be kept available and continue to work. In fact False shall be treated as 0 and True as 1.

The basic elements have to be modified to work on doubles in the following way:

negation - neg(x) = 1 - x, this is correct extension as neg(false)=neg(0)=1-0=1=true
and - and(x,y) = x * y, again this is fine as and(true,true)=1*1=true and also and(false,true)=0*1=0=false
or - or(x,y) = 1 - (1 - x) * (1 - y) and this is also ok as or(false,false) = 1 - (1 - 0) * (1 - 0) = 1 - 1 = 0 = false and for example or(true,false) = 1 - (1 - 1) * (1 - 0) = 1 - 0 * 1 = 1 = true

To prevent cheating by creating completely new API without any connection to the previous one, which is by definition the most compatible evolution possible, it was requested that the new API has to support single creation of a circuit that can later be fed with double inputs and subsequently with boolean inputs. Moreover it should have been stated that regardless of the way how to circuit was constructed, it can create the same instance of object that existed during day 1 and can be operated and evaluated using the APIs existing then. This would completely prevent the case of writing completely independent APIs.

Additinally there was another quest, which would again be better left for API Fest day 3, 4, etc. But due to the lack of time, had to be done at the same day. As the circuits with doubles are more rich than plain boolean circuits, there is additional requirement to allow any user of your API to write its own "element" type. E.g. the quest says that now the API shall not allow only composition of elements, but also allow others to write own plugins for the circuit elements. The individual tasks were:

First of all create a circuit which will evaluate expression (X1 and X2) or not(x1). Hold the circuit in some variable.
- Feed this circuit with x1=true, x2=false, assert result is false
- Feed the same circuit with x1=false, x2=true, assert result is true
- Feed the same circuit with x1=0.0, x2=1.0, assert result is 1.0
- Feed the same circuit with x1=0.5, x2=0.5, assert result is 0.625
- Feed the same circuit with x1=0.0, x2=2.0, make sure it throws an exception
Ensure that one variable cannot be filled with two different values. Create a circuit for x1 and x1. Make sure that for any usage of your API that would not lead to x1 * x1 result, an exception is thrown. For example if there was a way to feed the circuit with two different values 0.3 and 0.5 an exception is thrown indicating that this is improper use of the circuit.
Write your own element type called "gte" that will have two inputs and one output. The output value will be 1 if x1 >= x2 and 0 otherwise. Create circuit for following expression: (x1 and not(x1)) gte x1:
- Feed the circuit with 0.5 and verify the result is 0
- Feed the same circuit with 1 and verify the result is 0
- Feed the same circuit with 0 and verify the result is 1

Now is the right time to try the quest yourself! Get the RealTest.java put it into your project from Day 1 and rewrite your API to satisfy the individual tasks. Do it now or it will be to late as the best approach to solve the problems is about to be revieled soon!

Basically there are two ways to solve the problem. Either one tries to enhance the existing interfaces and classes in the API to accommodate operations on probability circuits or one writes the API from scratch and provides a bridge that allows conversion of the boolean circuit and the probability circuit from one to the another. So one can construct its circuit once and then evaluate it with booleans and doubles later. As all the solutions from Day 1 properly expected some kind of evolution, all participants chosen to enhance their interfaces and nobody decided to write a bridge. This was very likely good choice as creating proper bridge seems to be significantly more work.

I Want to Fix My Mistakes Problem

In contrary to the Day 1 there were no misunderstanding of the description of quests. However a syndrom this is not nice and needs to be fixed appeared in some cases. Some participants realized that their solution from previous day was not in fact absolutely correct and wanted to fix it. However fixing something always creates a risk of incompatible change and that is why it is necessary to explain to such persons that the API Fest is just a contest about compatibility, not a beauty and that a fixing something ugly is not necessarily. That the goal is to evolve and keep compatibility.

Solutions for Day 2

Slight problems with the implementation were faced by those who either did not allow multiple execution on the same circuit or those that allowed inconsistent evaluations. They had more work to do. So solutions alwayscreatenewcircuit, inputandoperation, stackbasedsolution had to fix themselves first and only later proceed with new tasks.

Then however the major task, I mean the extension of the circuit capabilities to double values from range 0.0 to 1.0 started. The participants used one of two approaches to make such extensions. Either they anticipated during day 1 that extensions will be needed and made the class responsible for the computation non-subclassable during the first day, and as a result they could add new method to it to perform the operations on doubles. This was the case of alwayscreatenewcircuit, elementbasedsolution , inputandoperation , pinbasedsolution and welltestedsolution . All of these could use the benefits of having non-subclassable class that can easily be enhanced with new methods during evolution without breaking existing clients.

The other solutions, namely subclassingsolution and stackbasedsolution decided to represent the circuit element as a subclassable class and as such they could not compatibly enhance their classes and needed to add new classes to represent circuit with enhanced capabilities. That is why the stackbasedsolution introduced Circuit2 and the subclassingsolution FuzzyCircuit .

Both of these approaches are possible, yet both can be dangerous. The danger of new interfaces is that the user will find it hard to use, particulary to decide when to use the simple interface and when the enhanced. Also one can mess up return types of methods and types of fields. On the other hand, enhancing existing non-subclassable class with a new method is nicer for clients, yet it can be dangerous due to uncertain cooperation between the new and old methods. One has to be very careful to do this right.

Anyway all participants in the Day 2 of API Fest seemed to satisfy the requirements, fulfil all the given tasks:

alwayscreatenewcircuit 's RealTest.java
inputandoperation 's RealTest.java
elementbasedsolution 's RealTest.java
subclassingsolution 's RealTest.java
pinbasedsolution 's RealTest.java
stackbasedsolution 's RealTest.java
welltestedsolution 's RealTest.java

and their solutions advanced to the final, competitive round.

Day 3 - The Judgment Day

So far all participants had played on their own field. And to be honest one has to admit that they played pretty well, but now the time has come to value the work done by others.

Of course, this API Fest is in some way a competition. However this is not a competition about beauty, like an iceskating one. Worlds like "to like", "to love" and "to hate" should have and hopefully have no meaning. There is no jurry to decide which API is the best. Now it is the turn for all participants to find out evolution holes in APIs written by others. Get a point for every broken API. Get five points if your APIs stays unbroken. Whatever happens the destiny is in your hands, in hands of you, the participants.

Download the ZIP file with all sources and search for a compatibility problem.

How to write a test proving there is an incompatibility problem? You can use NetBeans module with a project template . Download it, install it to NetBeans and create new compatibility testing projects. You can also just copy the sample infrastructure project from apifest1/day3-intermezzo/jtulach/against-pinbasedsolution/, after downloading all the sources.

At the end of day please submit a diff or a ZIP of sources that you put in yourname/against-nameofapi. Each of these folders shall have a build.xml ant file that will demonstrate the evolution problem. The more problems you find, the more points you will get.

The project I have prepared contains "project.properties" file. Modify it! Change the name of the api you want to work against, change the relative location (if wrong). Then you shall have code completion, and also compile, run, test actions shall work fine from inside NetBeans. Of course, as usual in NetBeans, the sample infrastructure is fully based on Ant, so you can also use it directly from a command line. Just execute the right build.xml.

The build.xml compiles your test file against some API from day1 and makes sure that your test succeeds against the implementation from day1. Then it runs the same test against implementation of day2. If the test run fails, the script succeeds as you have found an incompatibility. This shall discover binary and functional incompatibilities. Additionally the API is also compiled against the day2 API and if the compilation fails, the test also succeeds, as you have probably found a source incompatibility.

Now something about the rules for finding incompatibilities. First thing to say is that they are hard to describe, as there are obviously pretty good hackers that can invent many ways how to workaround the rules. So the general principle is: The less tricks you use to show an incompatibility, the better. If there are two solutions that show an incompatibility in the same API, the one that uses less tricks will win. Now what it means a trick? During runtime it definitely includes java.security.Permission. The less permissions you need to run your code the better. For example do not even try to use ReflectionPermission, that would indeed show incompatibility in every solution. Do not use Class.forName(...), that would be too easy, as very likely every API added some new class in day2. Class.getName() is also pretty wild trick, but it might be be allowed in some situations. Also notice that you may use new threads, but starting new thread requires a permission, so if there are two solution that show an incompatibility and one is using more threads and second does not, guess which one is going to be preferred... Please do not use wildcard imports in sources. import something.* it a as language construct that can break compilation against any API which added new class, so please do import fully qualified names. As you can see the range of tricks is probably unlimited, so remember the general principle: less tricks is better.

Wanna try hacking yourself? There is nothing easier, just download the solutions and sample testing project template (here), and try to find an evolution problem!

Conclusions

The Day 3 started on Friday afternoon and ended on Sunday. Maybe this was one of the reasons why very few people decided to participate in this round. The other reason may include problems in understanding how to use the testing infrastructure and also the fact that looking at others code may be a bit tedious and boring.

Thanks god we have Petr Nejedly. He not only wrote a solution that seems unbreakable, but also managed to break all other APIs. Sometimes he used unfair methods like getClass().getSuperclass() and getClass().getName(), but still being able to find an evolution problem in each API, really deserves an applause. No suprise that Petr won the API Fest One.

What was Wrong with subclassingsolution and stackbasedsolution?

The author of the subclassingsolution thought that the biggest problem is the fact that he made the AND, OR and NOT constants non-final, however he was wrong. The biggest problem of this API was that one class, the Circuit was used as two types of API - as the API that people call as well as the API that people subclass and implement. This indeed is a basic design problem that just asks for troubles. The evolution using FuzzyCircuit was in fact the correct one, just one has to remember that changing type of a field, parameters or return type of a method is not binary compatible in Java. The classfile format includes not just the name of the field, but also its type and if it is changed, the application classes compiled independently may not link together. As a result the herein written test compiles against both versions, but if compiled against version from Day 1 and run against version of Day 2 it produces NoFieldFoundError and fails.

Similar problem happened to the author of stackbasedsolution that changed the return type of one method and as such a test similar to previous one caused NoMethodFoundError.

What was Wrong with inputandoperation?

The inputandoperation was very well designed solution, which was nearly unbreakable. Except one case: the Circuit was not final and because during Day 2 new method has been added to it, it was easy to break it using a test like this.

The lesson to take here is to not forget to add private constructor and/or final keyword to most of the classes exposed in the APIs. Otherwise the clients of the API can do pretty wild things while using it, like subclassing classes not intended for being subclassed.

What was Wrong with alwayscreatenewcircuit and welltestedsolution?

In short - nothing. Petr managed to break both of these APIs, but only by using unfair tricks. Once he exploited a rename of implementation class and then a change in hierarchy of superclasses . None of this is an aspect that sane people consider an API contract. More likely everyone is going to agree that these are implementation details. True. However it is still good to keep in mind that even changes like this can be observed from outside code (even without using any special Permissions) and the code can get broken.

A thing to note is that because both authors of these APIs were in hurry, as they needed to do additional rewrites during Day 2 including repeatable evaluation on the same circuit, they solved the problem of allowing clients to write their own circuit elements by making the Circuit class subclassable. As a result the class has started to play two roles, being part of APIs that clients call as well as those that clients implement. That is why these two solutions would have pretty hard time with future evolution. For example just a request to add an unique ID to each circuit element could lead to possible evolution problems much the same as in case of inputandoperation. Much better approach is to add additional interface and factory method as done by the pinbasedsolution's createGate . This approach fulfils the same functionality, but clearly separates the contract for callers to the API from the contract for the implementors of the API.

What was Wrong with elementbasedsolution?

The elementbasedsolution seemed unbreakable at first sight, but still Petr managed to find a sequence of calls and put them in a test that thrown NullPointerException when run on Day 2 solution and worked correctly on Day 1 version. The point to make is that in spite that the API was evolved in source compatible and binary compatible way, it was not retained its functional compatibility. There was just one sequence of calls that could produce different result in different versions.

The lesson to learn is that any change to an API can introduce unwanted side effects. Regardless of how much careful review is done, there can always be corner cases that remain unnoticed and can exhibit incompatibilities between different version of the API.

Summary

Running the API Fest with NetBeans core team was funny and entertaining. Althrough it did not seems so, two plus one judgement rounds were enough to select the winner. Still it would be more pleasant if there could be more rounds and they could take longer time.

The main objective of the API Fest is evolution of the API and backward compatibility and indeed these are not the only properties of well written and maintained API. Ability to design the API correctly, make it easy to understand for the audience that will use it, document it, etc. is not practised and important in API Fest style of competition at all. Still compatibility and evolution is an important part of the API design, and API Fest game seems to practice these skills very well.

API Fest One turned into pretty successful event. It would be shame if this was the last one. The amount of various APIs to practice evolution on is unlimited and there is also many other evolution paths to enrich the game on the boolean circuit. Imagine new quests like support for multiple outputs, cyclic circuits, a way to analyse structure of unknown circuits, etc.

The API Fest game seems to be promissing learning and training technique for those who design an API to be consumed by others, for students that need to learn about backward compatibility, and anyone who just has not lost a sense for interesting games and wants to learn while being entertained.

Have a comment? Send a note to nbdev@netbeans.org!