Mike's corner of the web.

Archive: Software design

GraphJoiner: Implementing GraphQL with joins

Thursday 27 October 2016 20:23

I've had the chance to play around with GraphQL recently, and so far have found it all quite pleasant. Compared to fixed REST endpoints, being able to describe the data you need has resulted in less churn in the API. It also allows descriptions of the data needed to be co-located with the components actually using the data, making the code easier to understand and change.

However, most implementations of GraphQL libraries require some batching logic to behave efficiently. For instance, consider the request:

{
    books(genre: "comedy") {
        title
        author {
            name
        }
    }
}

A naive GraphQL implementation would issue one SQL query to get the list of all books in the comedy genre, and then N queries to get the author of each book (where N is the number of books returned by the first query).

The standard solution I've seen is to batch together requests. In node.js this is reasonably straightforward using promises and the event loop: don't start fulfiling the promise for each author until other requests in the same tick in the event loop have run, at which point you can fulfil those promises in bulk. The downside? This is trickier to implement in other languages that aren't built around an event loop.

Another issue with the standard implementation is performance. Normally, you define a resolver that gets executed on each field. In our example, the resolver for books and author would issue a request to get data from the database, but most resolvers just read a field: for instance, the resolver for title can just read the title field from the book that we got back from the database. The problem? If some resolvers can return asynchronous results, then you always need to handle the possibility of an asynchronous result. When dealing with larger responses, this can mean most of the time is spent in the overhead in invoking resolvers.

As an alternative, I suggest that you can get the data you want in three steps. First, get all of the books in the comedy genre with the requested scalar fields (i.e. their titles), along with their author IDs. Next, get all of the authors of books in the comedy genre with the requested scalar fields (i.e. their names), along with their IDs. Finally, using the IDs that we've fetched, join the authors onto the books.

In other words: rather than calling resolve for every field in the response, and batching together requests, I suggest that you can execute intermediate queries for each non-trivial field in the request, and then join the results together. As proof that the idea is at least somewhat workable, I've created a library called GraphJoiner, available as node-graphjoiner for node.js and python-graphjoiner for Python. When a response contains arrays with hundreds or thousands of results, I've found not having to call resolvers on every response field has massively reduced execution time (it was previously the majority of time spent handling the request, far exceeding the time to actually execute the SQL query). Hopefully someone else finds it useful!

Topics: Software design

Power à la Carte: fine-grained control of power in programming languages

Monday 28 March 2016 11:05

Proposal: general purpose programming languages should provide fine-grained control of the power that a particular module can use. "Power" includes language features, or what modules it is allowed to depend on, whether built into the language, from another package, or within the same codebase.

Suppose I'm writing some code to calculate how much tax someone should pay in a given year. I might want to forbid the use of floating point arithmetic in any of these calculations, but this isn't possible in most languages. In this proposal, I can declare what domain a module belongs to. For each domain, I can then declare what language features it's allowed to use. In this case, I'd be able to declare code as belonging to the "tax calculation" domain, and ensure that that domain cannot use floating point.

Take mutability as another example. I find most code I write is easier to reason about if it doesn't use mutability, but there are a small set of problems that I find are best expressed with mutable code, either for clarity or performance. By choosing exactly when mutability is permitted, I can still use mutability when needed without introducing its complexity into the rest of my codebase. Provided that the code doesn't mutate its arguments nor global state, the rest of the code doesn't need to know that mutability is being used: the contract of the functions can still be pure.

For each domain, I can also declare what other domains that domain is allowed to access. This allows enforcement of separation of concerns i.e. we can ensure that domains aren't intertwined when they shouldn't be. For instance, how tax is calculated shouldn't depend on personal details of an individual, such as their name. This also allows us to see what domains are used without having to read and understand the code of a module.

As another example, suppose I'm writing code to calculate the trajectory of a spacecraft. If I represent values such as distance or speed as integers, then it's possible to do something nonsensical like adding together two distances that use different units, or add together a distance and a speed. Within the domain of the trajectory calculation, I could represent these values with specialised data types preventing the incorrect use of these types. At some point, I may wish to unwrap these values, say to print them, but I can enforce that such unwrapping never happens during calculations. I'll also need to create these wrapped values in the first place, but I can declare and ensure that this value creation only occurs at well-defined boundaries, such as when reading sensors, and never directly within the calculation code.

In other words: the "mechanics" domain uses the "integer arithmetic" domain in its implementation, but that fact is private to the "mechanics" domain. In the "trajectory" domain, I explicitly declare that I can use values from the "mechanics" domain (such as adding together distances or dividing a distance by a time to get a speed), but that doesn't allow me to get their underlying integer representation nor create them from integers. In the "sensor" domain, I explicitly declare that I can create these values, meaning I can read the raw integers from some hardware, and turn them into their appropriate data types.

In the previous example, we saw how we wanted the fact that the "mechanics" domain uses the "integer arithmetic" domain to be private, but there are times when we don't want to allow this hiding. For instance, it's useful to definitively know whether a piece of code might write to disk, even if the write doesn't happen directly in that code.

I might also want to be able to enforce separation of concerns at a much higher level. Being able to enforce this separation is one of the cited benefits of a microservice architecture: it would be nice to be able to get this benefit without having to build a distributed system.

I believe part of the potential benefit of this is from going through the process of declaring what other domains a domain can access. It's often extremely easy to pull in another dependency or to rely on another part of our code without thinking about whether that makes conceptual sense. This is still possible in the system I describe, but by making the programmer be explicit, they are prompted to stop and think. I've made many bad decisions because I didn't even realise I was making a decision.

Some of this separation of domains is already possible: although I can't restrict access to language features, I have some control over what other modules each module can access: for instance, by using separate jars in Java, or assemblies in .NET. However, these are quite coarse and heavyweight: it's hard to use them to express the level of fine-grained control that I've described. The other downside is that by requiring a dependency, you normally end up being able to access its transitive dependencies: again, something that's often undesirable as previously described.

Using something like algebraic effect systems is probably more complex than necessary. The use of a language feature or domain could be modelled as an effect, but tracking this on an expression granularity is probably unhelpful: instead, tracking it by module is both simpler and more appropriate.

In fact, something like Java's annotations, C#'s attributes or Python's decorators are probably sufficient to express what domain each module resides in. You'd then need to separately define what power each domain has, which could be written in a comparatively simple declaration language. I suspect the difficulty comes not in implementing such a checker, but in working out how to use effectively, particularly what granularity is appropriate.

Topics: Software design, Language design

Nope: a statically-typed subset of Python that compiles to JS and C#

Sunday 22 March 2015 15:55

Nope is a statically-typed subset of Python that uses comments as type annotations. For instance, here's the definition of a Fibonacci function:

#:: int -> int
def fib(n):
    seq = [0, 1]
    for i in range(2, n + 1):
        seq.append(seq[i - 1] + seq[i - 2])
    
    return seq[n]

print(fib(10))

And here's a generic identity function:

#:: T => T -> T
def identity(value):
    return value

Since the types are just comments, any Nope program is directly executable as a Python program without any extra dependencies.

Having written your program with type annotations, you can now compile it to some horrible-looking JavaScript or C# and run it:

$ python3 fib.py
55
$ nope compile fib.py --backend=dotnet --output-dir=/tmp/fib
$ /tmp/fib/fib.exe
55
$ nope compile fib.py --backend=node --output-dir=/tmp/fib
$ node /tmp/fib/fib.js
55

Why?

A little while ago, I wrote mammoth.js, a library for converting Word documents to HTML. Since some people found it useful, I ported it to Python. Both implementations are extremely similar, and don't heavily exploit the dynamic features of either language. Therefore, a third port, even to a statically-typed language such as C# or Java, is likely to end up looking extremely similar.

This led to the question: if I annotated the Python implementation with appropriate types, could I use it to generate vaguely sensible C# or Java code? Nope is an experiment to find out the answer.

Should I use it?

This project is primarily an experiment and a bit of fun. Feel free to have a play around, but I'd strongly suggest not using it for anything remotely practical. Not that you'd be able to anyway: many essential features are still missing, while existing features are likely to change. The type-checking is sufficiently advanced to allow partial type-checking of the Python port of Mammoth.

I discuss a few alternatives a little later on, and explain how Nope differs. In particular, there are a number of existing type checkers for Python, the most prominent being mypy.

Examples

Simple functions

Functions must have a preceding comment as a type annotation.

#:: int -> int
def triple(value):
    return value * 3
Functions with optional and named arguments

Optional arguments are indicated with a leading question mark, and must have a default value of None. For instance:

#:: name: str, ?salutation: str -> str
def greeting(name, salutation=None):
    if salutation is None:
        salutation = "Hello"
    
    print(greeting + " " + name)

print(greeting("Alice"))
print(greeting("Bob", salutation="Hi"))

Note that the type of salutation changes as it is reassigned in a branch of the if-else statement. It is initially of type str | none, which is the union of the formal argument type and none (since it's optional). After the if-else statement, it is of the narrower type str, which allows it to be safely used in the string concatenation.

Variables

Most of the time, Nope can infer a suitable type for variables. However, there are occasions where an explicit type is required, such as when inferring the type of empty lists. In these cases, an explicit type can be specified in a similar manner to functions:

#:: list[int]
x = []
Classes

When annotating the self argument of a method, you can use the explicit name of the class:

class Greeter(object):
    #:: Greeter, str -> str
    def hello(self, name):
        return "Hello " + name

For convenience, Nope also introduces Self into the scope of the class, which can be used instead of referring to the containing class directly:

class Greeter(object):
    #:: Self, str -> str
    def hello(self, name):
        return "Hello " + name

As with local variables, instance variables assigned in __init__ can have type annotations, but will often be fine using the inferred type:

class Greeter(object):
    #:: Self, str -> none
    def __init__(self, salutation):
        self._salutation = salutation

    #:: Self, str -> str
    def hello(self, name):
        return self._salutation + " " + name

Generic classes are also supported, although the exact syntax might change:

#:generic T
class Result(object):
    #:: Self, T, list[str] -> none
    def __init__(self, value, messages):
        self.value = value
        self.messages = messages
Code transformations

To preserve some of the advantages of working in a dynamic langauge, Nope supports code transformations: given the AST of a module, a transformation returns an AST that should be used for type-checking and code generation. So long as the transformation and the original runtime behaviour are consistent, this allows you to use code such as collections.namedtuple:

import collections

User = collections.namedtuple("User", [
    #:: str
    "username",
    #:: str
    "password",
])

The current implementation is a bit of a hack, but the ultimate goal is to let a user specify transformations to apply to their code. Ideally, this would allow Python libraries such as SQLAlchemy to be supported in a type-safe manner.

And the rest

Nope also supports while and for loops, try statements, raise statements, destructuring assignment and plenty more. However, I've left them out of this post since they look the same as they do in Python. The only difference is that Nope will detect when inappropriate types are used, such as when trying to raise a value that isn't an exception.

I've started using Nope on a branch of Mammoth. Only some modules are currently being type-checked by Mammoth, such as html_generation.

If you're feeling brave, Nope has a set of execution tests that check and compile sample programs. It's the not the greatest codebase in the world with many unhanded or improperly handled cases, but feel free to read the tests if you want to dive in and see exactly what Nope supports. At the moment, Nope compiles to Python (which means just copying the files verbatim), JavaScript and C# with varying degrees of feature-completeness. The C# implementation in particular has huge scope for optimisation (since it currently relies heavily on (ab)using dynamic), but should already be fast enough for many uses.

Type system

Nope ends up with a few different kinds of type in its type system. It would be nice to be able combine some of these, but for the time being I've preferred to avoid introducing extra complexity into existing types. At the moment, Nope supports:

  • Ordinary classes, made by using class in the usual way. Since inheritance is not yet supported, a type T is a subclass of itself and no other ordinary classes.
  • Function types, such as:
    • int, str -> str (Requires two positional arguments of type int and str respectively, and returns a str.)
    • int, x: int, ?y: str -> int (Has two required arguments, the second of which can be passed by the name x. Has an optional third argument called y.)
  • Structural types. For instance, we might define a structural type HasLength with the attribute __len__ of type -> int (takes no arguments, returns an integer). Any type with an appropriately typed attribute __len__ would be a subtype of HasLength. Currently not definable by users, but should be.
  • Generic types. Nope currently supports generic functions, generic classes and generic structural types. For instance, the generic structural type Iterable has a single formal type parameter, T, and an attribute __iter__ of type -> Iterator[T], where Iterator is also a generic structural type.
  • Type unions. For instance, a variable of type int | str could hold an int or a str at runtime.

What about IronPython or Jython?

Both IronPython and Jython aim to be Python implementations, rather than implementing a restricted subset. This allows them to run plenty of Python code with little to no modification.

Nope differs in that it aims to allow the generation of code without any additional runtime dependencies. Since the code is statically typed, it should also allow better integration with the platform, such as auto-complete or Intellisense in IDEs such as Visual Studio, Eclipse and IntelliJ.

What about mypy?

mypy is an excellent project that can type check Python code. If you want a project that you can practically use, then mypy is by far more appropriate. There are other type checkers that also use Python annotations to specify types, such as obiwan.

At this point, Nope differs in two main regards. Firstly, Nope's scope is slightly different in that I'm aiming to compile to other languages.

The second main difference is that Nope aims to have zero runtime dependencies. Since mypy uses Python annotations to add type information, programs written using mypy have mypy as a runtime dependency. This also allows some meta-programming with somewhat consistent type annotations, as shown in the collections.namedtuple from earlier:

import collections

User = collections.namedtuple("User", [
    #:: str
    "username",
    #:: str
    "password",
])

What next?

I'm only working on Nope in my spare time, so progress is a little slow. The aim is to get a C# version of Mammoth working by using Nope in the next few months. Although there might not be feature parity to begin with, I'd be delighted if I got far enough to get the core program working.

If, in a surprising turn of events, this turns out to work, I'd be interested to add effects to the type system. Koka is the most notable example I know of such a system, although I'll happily admit to being some unknowledgeable in this area. Thoughts welcome!

Topics: Software design, Language design

Code smears: code smells that spread across your codebase

Monday 5 January 2015 21:34

The term "code smells" gives us a handy shorthand for signs that our code might not be especially clean. In my experience, the worst sort of code smell are "code smears": those smells that tend to spread their badness across your codebase, which also makes them more difficult to fix as time goes on. For instance, suppose a function has too many arguments, making it difficult to see the purpose of each argument. That code smell isn't confined to the function definition: it's going to appear every time that the function is called.

Code smells tell us that there's probably room for improvement. Ideally, we'd avoid all code smells, but there often comes a point where our time is better spent elsewhere. Yet not all code smells are created equal. Some code smells can be fixed later with little or no impact on the rest of the codebase: for instance, if I take an extremely long function and break it up into smaller functions that compose together nicely, nobody who calls the function needs to be aware that anything has changed.

On the other hand, some code smells tend to make their presence felt across a codebase: for instance, if a function takes four boolean arguments, this leads to somewhat mysterious function calls such as update(true, false, true, true). Fixing this requires changing everywhere that calls that function. This task can range from tedious, if the function is called in many places, to impossible, if third parties are calling into our code. As time goes on, it's likely that there will be more callers of the our function, and so more work to clean it up. I'd suggest that this second group of code smells is more severe than the first, and therefore deserves the more severe name of code smears.

As a further incentive to avoid code smears moreso than code smells, I've found that code smears are often quicker and easier to fix so long as you do so as soon as they appear. Splitting up a long method can be time-consuming and difficult. Giving a function a better name or grouping together related arguments into a single object can often be accomplished in a couple of minutes provided that the function is only used in one or two places under your control.

Sometimes, it's a good trade-off not to fix a code smell. It's rarely a good trade-off to leave behind a code smear.

Topics: Software design

The Dangerous Allure of Code Reuse

Tuesday 20 May 2014 20:42

Back when I was learning to code, one of the ideas that kept cropping up was the idea of code reuse. If one of the main benefits of functions is the ability to reuse a bit of code, doesn't it follow that we should have future code reuse in mind when writing functions? My experience says: nope. It's this thinking that leads me to create functions with six Boolean arguments, or to create functions with complex, deeply nested switching logic. By following principles such as "Don't repeat yourself" (DRY) and "You ain't gonna need it" (YAGNI), and creating short functions that operate at a single level of abstraction, I find that useful functions pop out without consciously thinking about code reuse.

If I try to write a function with code reuse in mind, it becomes tempting to write features that might be useful. In other words, it encourages the opposite of YAGNI (you ain't gonna need it). Far better to have a tightly focused function that does exactly what I need, no more nor less. Sometimes that function will already exist exactly as we need it. Great! Use it.

But what if there's an existing function that's similar, but would require some changes for our required functionality? Should I create a new function or should I modify the existing function? It's tempting to tweak the existing function in the name of code reuse, but I'd suggest that we should err on the side of creating new functions.

One of my guiding principles is also one of the main benefits of functions: abstraction. Imagine that there's already a function that does exactly what you need. What would it be called? What concept does it represent? Now take a look at the existing function. Are they the same concept? If the concepts are related but distinct, that suggests they belong in different functions. If it happens that they have similar implementations, then you'll find the same consideration happening recursively: is this sub-concept in my new function actually the same sub-concept in the existing function? And so on. Although you might have created a new function, it might not actually lead to much new code if it shares many of the same underlying concepts.

I try to write short functions that operate at a single level of abstraction. The result is that I write plenty of short functions that only get used in one place, at least initially. Such functions might end up getting used in other places, but they weren't really designed with reuse in mind: instead, the foremost consideration was whether that function represented a coherent abstraction of a concept.

This isn't to say that I completely ignore code reuse when writing functions. Sometimes, when weighing up different design choices that are similarly elegant for my current use-case, I'll pick a design based on which one is likely to be best suited to usages that I anticipate in the future. However, I won't add anything specifically for code reuse: I've still chosen a design which does only what I need, but is also amenable to anticipated future change. If that future change never happens, then the function still makes sense and doesn't have extra unused functionality.

To summarise: I try to avoid crowbarring in functionality to existing functions just because it's similar. Separate concepts should go in separate functions, even if they share underlying concepts. Better to have two coherent, small, simple concepts than a larger but ill-defined concept. Code reuse is a good thing, but it's not something that I actively design for.

Footnote: for brevity, I've only talked about functions in this post, but it applies equally to classes and other such constructs for the same reasons.

Topics: Software design

External code quality and libification

Tuesday 26 February 2013 20:11

If you ask a programmer to list symptoms of low code quality, they could probably produce a long list: deeply nested conditionals and loops, long methods, overly terse variable names. Most of these code smells tend to focus on the implementation of the code. They're about internal code quality.

External code quality instead asks you to consider the programmer that has to call your code. When trying to judge how easily somebody else can you use your code, you might ask yourself:

  • Do the class and method names describe what the caller wants to accomplish?
  • How many times must we call into your code to complete a single, discrete task?
  • Does your code have minimal dependencies on other parts of your codebase and external libraries?

As an example, consider this snippet of Java to write an XML document to an OutputStream:

import org.w3c.dom.*;
import java.io.*;
import javax.xml.transform.*;
import javax.xml.transform.dom.*;
import javax.xml.transform.stream.*;

private static final void writeDoc(Document document, OutputStream output)
        throws IOException {
    try {
        Transformer transformer =
            TransformerFactory.newInstance().newTransformer();
        transformer.setOutputProperty(
            OutputKeys.DOCTYPE_SYSTEM,
            document.getDoctype().getSystemId()
        );
        transformer.transform(new DOMSource(document), new StreamResult(output));
    } catch (TransformerException e) {
        throw new AssertionError(e); // Can't happen!
    }
}

While there are probably good reasons for all of those methods, and there are cases where having a high level of control is valuable, this isn't a good API for our user that just wants to write out their XML document to an output stream.

  • Do the class and method names describe what they want to accomplish? We want to write out our XML document, and instead we're talking about TransformerFactory and OutputKeys.DOCTYPE_SYSTEM.
  • How many times must we call into your code to complete a single, discrete task? Writing out an XML document seems simple, but we have to create an instance of a transformer factory, then ask it for a transformer, set the output property (whatever that is), wrap up our document and output stream, before we can finally use the transformer to write out our document.
  • Does your code have minimal dependencies on other parts of your codebase and external libraries? The code above actually does quite well here, since that snippet should work on a normal installation of Java.

So, why is it valuable to distinguish between internal and external code quality? The effect of low internal code quality is contained within a small scope (by definition!). I'm certainly not advocating one letter names for all local variables, but cleaning up that code is comparatively straightforward compared to improving an API. The effects of low external code quality tend to pervade your entire system. If you change the signature of a method, you now have to change every use of that method.

When writing code, we often trade off code quality against speed of execution. Even when writing good quality code, we're not going to spend weeks refactoring to make it perfect. I'm suggesting that we should be spending more time worrying about the external quality of our code. Internal quality is important, but it's not as important.

A good measure of whether a piece of your code has minimal dependencies is to try "libifying" it: turn it into an independent library. If the code you write frequently depends on large parts of the entire system, then it probably depends on too much. Once you've split out your code into a separate library, there's a good chance that external code quality will improve. For starters, once you've pulled out that code, you're unlikely to accidentally introduce new dependencies that aren't really required. Beyond that: when you've written a bad API deep within the internals of your large system, it's easy to ignore. If you've split it out into a library, it's much harder to ignore whether your library makes it hard or easy to do what it says on the tin.

Decomposing your code into libraries has plenty of advantages, such as code reuse and being able to test components independently. But I have a hypothesis that aggressively libifying your code will leave you with a much higher quality of code in the long run.

Topics: Software development, Software design

Test reuse

Monday 18 February 2013 10:38

Code reuse is often discussed, but what about test reuse? I don't just mean reusing common code between tests -- I mean running exactly the same tests against different code. Imagine you're writing a number of different implementations of the same interface. If you write a suite of tests against the interface, any one of your implementations should be able to make the tests pass. Taking the idea even further, I've found that you can reuse the same tests whenever you're exposing the same functionality through different methods, whether as a library, an HTTP API, or a command line interface.

As an example, suppose you want to start up a virtual machine from some Python code. We could use QEMU, a command line application on Linux that lets you start up virtual machines. Invoking QEMU directly is a bit ugly, so we wrap it up in a class. As an example of usage, here's what a single test case might look like:

def can_run_commands_on_machine():
    provider = QemuProvider()
    with provider.start("ubuntu-precise-amd64") as machine:
        shell = machine.shell()
        result = shell.run(["echo", "Hello there"])
        assert_equal("Hello there\n", result.output)

We create an instance of QemuProvider, use the start method to start a virtual machine, and then run a command on the virtual machine, and check the output. However, other than the original construction of the virtual machine provider, there's nothing in the test that relies on QEMU specifically. So, we could rewrite the test to accept provider as an argument to make it implementation agnostic:

def can_run_commands_on_machine(provider):
    with provider.start("ubuntu-precise-amd64") as machine:
        shell = machine.shell()
        result = shell.run(["echo", "Hello there"])
        assert_equal("Hello there\n", result.output)

If we decided to implement a virtual machine provider using a different technology, for instance by writing the class VirtualBoxProvider, then we can reuse exactly the same test case. Not only does this save us from duplicating the test code, it means that we have a degree of confidence that each implementation can be used in the same way.

If other people are implementing your interface, you could provide the same suite of tests so they can run it against their own implementation. This can give them some confidence that they've implemented your interface correctly.

What about when you're implementing somebody else's interface? Writing your own set of implementation-agnostic tests and running it existing implementations is a great way to check that you've understood the interface. You can then use the same tests against your code to make sure your own implementation is correct.

We can take the idea of test reuse a step further by testing user interfaces with the same suites of tests that we use to implement the underlying library. Using our virtual machine example, suppose we write a command line interface (CLI) to let people start virtual machines manually. We could test the CLI by writing a separate suite of tests. Alternatively, we could write an adaptor that invokes our own application to implement the provider interface:

class CliProvider(object):
    def start(self, image_name):
        output = subprocess.check_output([
            _APPLICATION_NAME, "start", image_name
        ])
        
        return CliMachine(_parse_output(output))

Now, we can make sure that our command-line interface behaves correctly using the same suite of tests that we used to test the underlying code. If our interface is just a thin layer on top of the underlying code, then writing such an adaptor is often reasonably straightforward.

I often find writing clear and clean UI tests is hard. Keeping a clean separation between the intent of the test and the implementation is often tricky, and it takes discipline to stop the implementation details from leaking out. Reusing tests in this way forces you to hide those details behind the common interface.

If you're using nose in Python to write your tests, then I've put the code I've been using to do this in a separate library called nose-set-tests.

Topics: Testing, Software design, Python

The importance of extremes

Tuesday 18 December 2012 21:01

When exploring unfamiliar ideas, the best approach is often to take them to the extreme. For instance, suppose you're trying to follow the principle "tell, don't ask". I've often found it tricky to know where to draw the line, but as an exercise, try writing your code without a single getter or setter. This may seem ludicrous, but by throwing pragmatism completely out the window, you're forced to move outside your comfort zone. While some the code might be awful, some of it might present ideas in a new way.

As an example, suppose I have two coordinates which represent the top-left and bottom-right corners of a rectangle, and I want to iterate through every integer coordinate in that rectangle. My first thought might be:

def find_coordinates_in_rectangle(top_left, bottom_right):
    for x in range(top_left.x - 1, bottom_right.x + 2):
        for y in range(top_left.y - 1, bottom_right.y + 2):
            yield Coordinate(x, y)

Normally, I might be perfectly happy with this code (although there is a bit of duplication!) But if we've forbidden getters or setters, then we can't retrieve the x and y values from each coordinate. Instead, we can write something like:

def find_coordinates_in_rectangle(top_left, bottom_right):
    return top_left.all_coordinates_in_rectangle_to(bottom_right)

The method name needs a bit more thought, but the important difference is that we've moved some of the knowledge of our coordinate system into the actual coordinate class. Whether or not this turns out to be a good idea, it's food for thought that we might not have come across without such a severe constraint as "no getters or setters".

Topics: Software design

Polymorphism and reimplementing integers

Tuesday 18 December 2012 20:39

While taking part in the Global Day of Coderetreat, one of the sessions had us implementing Conway's Game of Life without using any "if" statements to force us to use polymorphism instead. Anything that was an "if" in spirit, such as a switch statement or storing functions in a dictionary, was also forbidden. For most of the code, this was fairly straightforward, but the interesting problem was the code that decided whether a cell lived or died based on how many neighbours it had:

if numberOfNeighbours in [2, 3]:
    return CellState.LIVE
else:
    return CellState.DEAD

Polymorphism allows different code to be executed depending on the type of a value. In this particular case, we need to execute different code depending on which value we have. It follows that each number has to have a different type so we can give it different behaviour:

class Zero(object):
    def increment(self):
        return One()
        
    def live_cell_next_generation():
        return CellState.DEAD
        
class One(object):
    def increment(self):
        return Two()
        
    def live_cell_next_generation():
        return CellState.DEAD
        
class Two(object):
    def increment(self):
        return Three()
        
    def live_cell_next_generation():
        return CellState.LIVE
        
class Three(object):
    def increment(self):
        return FourOrMore()
        
    def live_cell_next_generation():
        return CellState.LIVE

class FourOrMore(object):
    def increment(self):
        return FourOrMore()
        
    def live_cell_next_generation():
        return CellState.DEAD

In the code that counts the number of neighbours, we use our new number system by starting with Zero and incrementing when we find a neighbour. To choose the next state of the cell, rather than inspecting the number of neighbours, we ask the number of neighbours for the next state directly:

numberOfNeighbours.live_cell_next_generation()

And now we have no "if"s! It's possible to move the logic for choosing the next cell out of the number classes, for instance using the visitor pattern, which might feel a bit more natural. I suspect that reimplementing the natural numbers is still going to feel about the same amount of crazy though.

Topics: Software design

Modularity through HTTP

Monday 10 December 2012 10:41

As programmers, we spend quite a lot of effort in pursuit of some notion of modularity. We hope that this allows us to solve problems more easily by splitting them up, as well as then letting us reuse parts of the code in other applications. Plenty of attempts have been made to get closer to this ideal, object-orientation perhaps being the most obvious example, yet one of the most successful approaches to modularity is almost accidental: the web.

Modularity makes our code easier to reason about by allowing us to take our large problem, split it into small parts, and solve those small parts without having to worry about the whole. Programming languages give us plenty of ways to do this, functions and classes among them. So far, so good. But modularity has some other benefits that we’d like to be able to take advantage of. If I’ve written an independent module, say to send out e-mails to my customers, I’d like to be able to reuse that module in another application. And by creating DLLs or JARs or your platform’s package container of choice, you can do just that – provided your new application is on the same platform. Want to use a Java library from C#? Well, good luck – it might be possible, but it’s not going to be smooth sailing.

What’s more, just because the library exists, it doesn’t mean it’s going to be a pleasant experience. If nobody can understand the interface to your code, nobody’s going to use it. Let’s say we want to write out an XML document to an output stream in Java. You’d imagine this would be a simple one-liner. You’d be wrong:

import org.w3c.dom.*;
import java.io.*;
import javax.xml.transform.*;
import javax.xml.transform.dom.*;
import javax.xml.transform.stream.*;

private static final void writeDoc(Document doc, OutputStream out) 
        throws IOException{
    try {
        Transformer t = TransformerFactory.newInstance().newTransformer();
        t.setOutputProperty(
            OutputKeys.DOCTYPE_SYSTEM, doc.getDoctype().getSystemId());
        t.transform(new DOMSource(doc), new StreamResult(out));
    } catch(TransformerException e) {
       throw new AssertionError(e); // Can't happen!
    }
}

The result is that most of the code we write is just a variation on a theme. Odds are, somebody else has written the code before. Despite our best efforts, we’ve fallen a little short.

However, the web brings us a little closer to the ideal. If I want to send e-mails to my customers, I could write my own e-mail sending library. More likely, I’d use an existing one for my language. But even then, I probably wouldn’t have some niceties like A/B testing or DKIM signing. Instead, I could just fire some HTTP at MailChimp, and get a whole slew of features without getting anywhere near the code that implements them.

The web is inherently language agnostic. So long as your language can send and receive text over HTTP, and probably parse some JSON, you’re about as well-equipped as everybody else. Instead of building libraries for a specific language, you can build a service that can be used from virtually every language.

The text-based nature of HTTP also helps to limit on the complexity of the API. As SOAP will attest, you can still make a horrible mess using HTTP, but that horrible mess is plain to see. Complex data structures are tedious to marshal to and from text, providing a strong incentive to keep things simple. Spotting the complexities in a class hierarchy is often not as easy.

HTTP doesn’t solve every problem – using it inside an inner loop that’s executed thousands of times per second probably isn’t such a good idea. What’s more, this approach might introduce some new problems. For instance, if we’re combining existing applications using HTTP for communication, we often need to add a thin shim to each application. For instance, you might need to write a small plugin in PHP if you want to integrate WordPress into your system. Now, instead of a system written in one language, you’ve got to maintain a system with several distinct languages and platforms.

Even then, we should strive to avoid reimplementing the same old thing. As programmers, we consistently underestimate the cost of building a system, not to mention ongoing maintenance. By integrating existing applications, even if they’re in an unfamiliar languages, we save ourselves those development and maintenance costs, as well as being able to pick the best solution for our problem. Thanks to the web, HTTP is often the easiest way to get there.

In case you recognised the topic, an edited version of this post was used as the Simple-Talk editorial a few months ago.

Topics: Software development, Software design

Coupling classes to interfaces

Sunday 23 October 2011 09:49

Over on the 8th Light blog, Steven Degutis discusses the advantages of Go's approach to interfaces. Specifically, Go allows you to have a class implement an interface without explicitly mentioning the interface so long as it has methods with the right names and type signatures. He likes the idea you can write an interface, and have an existing class implement that interface without modification. I find the idea that a class can implement an interface just by the coincidence of having methods with matching names and type signatures to be terrifying.

To re-use Steven's example:

    type Predator interface {
        chasePrey(Prey) bool
        eatPrey(Prey)
    }
   
    type Lion struct{}
   
    func (self Lion) chasePrey(p Prey) bool {
        // ...
    }
   
    func (self Lion) eatPrey(p Prey) {
        // ...
    }

Since Lion has the methods chasePrey and eatPrey with the correct type signature, it implements the interface Predator, yet the interface Predator is never mentioned in the definition of Lion. This is considered a Good Thing: to quote Steven:

But alas, in Java, the class itself must know ahead of time all the names of the interfaces it wants to conform to. This is an unfortunate form of temporal coupling.

[…]

Go doesn't care that, 5 years ago, Lion never specified which interfaces it implements, it just cares that it has the methods this interface needs, and rightly so.

I think it's a terrifying idea that my class could suddenly start implementing new interfaces that I'd never considered when writing the class. When I define an interface in Java, it has more meaning than just the name and type signature of each method. An interface is also a contract for the behaviour of the implementation of those methods, which can't be verified by names and types alone. I want to explicitly specify the interfaces that a class implements, as a declaration in the code that says “I understand what behaviour sub-types of the interface should have, and I've done my best to make sure that this class implements that behaviour”. To me, this is much more useful than knowing the type of a class is compatible with an interface.

Now, I'm not saying that Go has got it wrong. I think Go's interfaces provide weaker contracts in exchange for greater flexibility, but which is better depends on your programming style and preferences.

Topics: Software design

Sharing JavaScript between the browser and the server

Saturday 22 October 2011 09:20

When talking about node.js, I usually hear people give two reasons why they love it. The first is that it uses an event-driven model for concurrency, rather than using threads and blocking function calls. The second is that node.js allows you to use the same language, JavaScript, on both the browser and the server. You can then share logic that might otherwise be duplicated, such as validation of user input. Yet people often dismiss the latter point, saying that when they do web development, the amount of logic that ends up being duplicated is neglible, since the code on the browser and on the server address different concerns.

My question is: have we got this the wrong way round? Does code on the browser and server tend to address separate concerns precisely because sharing logic between them is hard? Once we start using the same language on both sides, we might start to see new ideas that this brings to the table. With modern web applications, we see more and more code that we might have previously expected to see on the server being brought into the browser. If we can easily move code between the browser and server, then we start to have an enourmous amount of flexibility: we can easily change our minds about where some particular code should be executed both when building our application, and at run-time.

Topics: JavaScript, Software design

Writing maintainable code

Tuesday 27 September 2011 20:14

I heartily endorse this fine article on writing maintainable code. What do you mean I'm biased because I wrote it?

Topics: Software design, Software development, Testing

Design Minimalism or the Dinosaur Snaggletooth

Tuesday 7 December 2010 00:00

While looking for a templating language for node.js, I came across an article On Design Minimalism, which gels well with my view that reusable code is all about small components that do as little as possible to get the job done, rather than frameworks that do everything you can think of.

Topics: Software design

Naming Functional/Procedural Functions

Thursday 9 September 2010 14:15

It was recently pointed out to me (unfortunately, I can't remember where) that a good way to distinguish functional and procedural versions of similar functions is to use adjectives for the functional version and verbs for the procedural version.

For instance, consider functions that sort a list. The functional version would be called sorted, and returns a sorted copy of the list:

some_list = [2, 0, 1]
sorted_list = sorted(some_list)
# some_list == [2, 0, 1], sorted_list == [0, 1, 2]

On the other hand, the procedural function would be called sort, and modifies the list in-place:

some_list = [2, 0, 1]
sort(some_list)
# some_list == [0, 1, 2]

This is probably obvious to everybody else, but I'd never really thought it too much before.

Topics: Software design

Object orientation without classes

Saturday 9 January 2010 21:47

So, in the last post, I decided that object orientation was about a couple of key concepts: encapsulation and polymorphism. Revisiting our NameGenerator example, we had this code in Java:

public class NameGenerator {
    private final FirstNameGenerator firstNameGenerator;
    private final LastNameGenerator lastNameGenerator;
    
    public NameGenerator(FirstNameGenerator firstNameGenerator,
                         LastNameGenerator lastNameGenerator) {
        this.firstNameGenerator = firstNameGenerator;
        this.lastNameGenerator = lastNameGenerator;
    }

    public String generateName() {
        return firstNameGenerator.generate() + " " + lastNameGenerator.generate();
    }
}

However, there's an awful lot of duplication here -- in the fields and constructor, we mention a first name generator no less than six times. There's also another form of duplication present -- this constructor is identical to every other constructor I write in Java in that all it does is assign arguments to fields. After all, doing work in the constructor is a bad idea. In an ideal world, we might decide a more succinct syntax for our class would be:

public class NameGenerator(FirstNameGenerator firstNameGenerator,
                           LastNameGenerator lastNameGenerator) {
    public String generateName() {
        return firstNameGenerator.generate() + " " + lastNameGenerator.generate();
    }
}

Now, the constructor arguments are parameters for the class itself. This is functionally equivalent to the example above, while cutting down on the duplication we saw. Incidentally, Scala users will be familiar with this style of constructing objects.

The example is still in a statically typed language -- so what happens if we remove the static typing?

public class NameGenerator(firstNameGenerator, lastNameGenerator) {
    public generateName() {
        return firstNameGenerator.generate() + " " + lastNameGenerator.generate();
    }
}

I'm not sure this has really helped readability or clarity. Certainly, we haven't gotten the same gains that we got by changing from a Java constructor to using class parameters. However, if we inspect our dynamically typed example closely, we might notice that there's very little that distinguishes it from a couple of function definitions. This leads us to write code that looks something like this:

function nameGenerator(firstNameGenerator, lastNameGenerator) {
    return {
        generateName: function() {
            return firstNameGenerator.generate() + " " + lastNameGenerator.generate();
        }
    };
}

In a few simple transformations, we've moved from Java to Javascript. Instead of a class, we have a function that takes a couple of generators. This function returns a new object with a single field called generateName. It just so happens that this field is a function, which uses the two generators to generate a full name. So, to give an example usage of the class:

// Assume we already have first and last name generators
var generator = nameGenerator(firstNameGenerator, lastNameGenerator);
var name = generator.generateName();

Hopefully this is enough to persuade you that we don't need classes in order to capture what we mean by object orientation. Indeed, there are only really two language features that we've used here. The first is the object, which allows us to group together the various parts of some idea (although in this case, we only have a single field).

The second feature is functions. But just having functions is not enough -- there are many languages that have functions where this wouldn't be possible to write. To be more specific we need to have first class functions, so that we can assign a function to a field as easily as we would assign a number or a string to a field. It also helps to have anonymous functions so that we can create functions easily, in the same way that Javascript's object literal notation makes it straightforward to build objects. The other piece of the puzzle is closures. Although firstNameGenerator and lastNameGenerator were not defined in the function assigned to generateName, they can still access these values since Javascript supports closures. This means that the references to the generators are still valid even after the function nameGenerator has returned.

This raises the question of what features you actually need in a language, and what features you can implement by composing other features. Another example might be namespaces. Many languages have namespaces explicitly built into the language, but by using layers of objects, you can easily build namespaces in Javascript despite the lack of explicit support for namespaces in the language. For instance, if were writing real Javascript code, we should put our nameGenerator method into the proper namespace, rather than in the global namespace:

ZWOBBLE = ZWOBBLE || {};
ZWOBBLE.names = ZWOBBLE.names || {};

ZWOBBLE.names.nameGenerator = function(firstNameGenerator, lastNameGenerator) {
    ...
}

We can easily write a function to replace this first couple of lines, so we have:

ZWOBBLE.define("ZWOBBLE.names");

ZWOBBLE.names.nameGenerator = function(firstNameGenerator, lastNameGenerator) {
    ...
}

Again, I hope this enough to convince that there's no need in Javascript for explicit support for namespaces. I could go on, but my broader point is that by giving a language a few basic, but powerful, constructs, one can build on top of them to reach the same features that are explicitly supported in other languages.

Incidentally, I've recently read a couple of articles on object orientation that I found interesting. The first distinguishes between abstract data types and objects, while the second makes the case for tail calls in object orientation languages.

Topics: Software design

Object orientation, inheritance and the template pattern (oh my!)

Monday 30 November 2009 19:43

Recently, I've been discussing with a variety of people the merits of various styles of programming. One person's complaint about object orientated programming is that it leads to huge hierarchies of code, where you constantly have to move up and down the class hierarchy to find out what's going on. I've encountered such code on plenty of occasions, but I disagree that it's a problem with object orientation. Instead, I believe it's a problem with inheritance.

Of course, this all depends on what we mean by object orientation. So, let's take a simple example in Java. In this case, we're going to make a class that generates names.

public class NameGenerator {
    public String generateName() {
        return generateFirstName() + " " + generateLastName();
    }
    
    protected String generateFirstName() {
        // Generate a random first name
        ...
    }
    
    protected String generateLastName() {
        // Generate a random last name
        ...
    }
}

So, NameGenerator will generate names using the default implementations of generateFirstName and generateLastName. If we want to change the behaviour of the class, say so that we only generate male names, we can override the generateFirstName method to only generate male names. This is known as the template pattern, the idea being that by putting the overall algorithm in one method that delegates to other methods, we avoid code duplication while still allowing different behaviours in different subclasses.

However, in my experience, the template pattern is a terrible way to write code. In some piece of code, if we see that the NameGenerator is being used, we might take a quick look at the class to see how it behaves. Unfortunately, the fact that subclasses may be overriding some methods to change behaviour isn't immediately obvious. This can make debugging difficult, since we start seeing behaviour we don't expect according to the class definition we have right in front of us. This becomes especially confusing if one of the methods affects control flow, for instance if we use one of the protected methods in a conditional, such as an if statement.

Testing also becomes more difficult. When we subclass NameGenerator, what methods should we be testing? We could always test the public method, but then we'll be testing the same code over and over again. We could test just the protected methods, but then we aren't testing the public method fully since it's behaviour changes depending on the protected methods. Only testing the public method if we think its behaviour will have changed is error-prone and brittle to changes made in behaviour in NameGenerator.

The solution is to use composition rather than inheritance. In this case, the first step is to pull out the two protected methods into two interfaces. The first interface will generate first names, and the second interface will generate last names. We then use dependency injection to get a hold of some implementation of these classes. This means that, rather than creating classes themselves, we have them passed in via the constructor. So, our NameGenerator now looks like this:

public class NameGenerator {
    private final FirstNameGenerator firstNameGenerator;
    private final LastNameGenerator lastNameGenerator;
    
    public NameGenerator(FirstNameGenerator firstNameGenerator,
                         LastNameGenerator lastNameGenerator) {
        this.firstNameGenerator = firstNameGenerator;
        this.lastNameGenerator = lastNameGenerator;
    }

    public String generateName() {
        return firstNameGenerator.generate() + " " + lastNameGenerator.generate();
    }
}

Now we've made the dependencies on the generation of first and last names clear and explicit. We've also made the class easier to test, since we can just pass in mocks or stubs into the constructor. This also encourages having a number of smaller classes interacting, rather than a few enormous classes. The code is also more modular, allowing it be reused more easily. For instance, if there's somewhere in the code where we just want to generate first names, we now have an interface FirstNameGenerator that we can use straight away.

For more on dependency injection, Misko Hevery has a good blog post on the subject, as well as a tech talk on dependency injection.

Notice how the new version of our code is completely devoid of inheritance. That's not to say that we have a completely flat class hierarchy -- we need implementations of FirstNameGenerator and LastNameGenerator, but it's important to keep inheritance and implementation distinct. Despite the lack of inheritance, I believe that this is still an example of object orientated programming in action. So, if not inheritance, what characterises object orientation?

I would first suggest encapsulation -- in this case, we don't care how the first and last name generators work, we just call their methods to get a result out. In this way, we can concentrate on one small part of the program at a time.

This doesn't tell the whole story though. If we didn't allow any subtyping, or rather polymorphism, then our example would not be able to use different implementations of FirstNameGenerator. By having polymorphism, we allow different implementations to be used so that we can use the same algorithm without rewriting it.

So, there we have my view of object orientation -- composition of small objects using encapsulation and polymorphism, while avoiding inheritance and, in particular, the template pattern.

Topics: Software design, Testing