mercredi 4 juillet 2018

Type Driven Development pattern: Small types


TLDR; Small types in type driven development facilitates composability much like small objects do in OO. By small types I mean few constructors and little data in each.

One of my first experiences in Idris was to try to implement a FizzBuzz where the types would be so strong that they'd ensure  the code could only be correctly implemented.

FizzBuzz is a game where the input is a number between 1 and 100. The output is a string, "Fizz" if the number is divisible by 3. "Buzz" if the number is divisible by 5. "FizzBuzz" if it is both divisible by 3 and 5 and just the number otherwise. eg counting from 1

1, 2, fizz, 4, buzz, fizz, 7, 8, fizz, buzz, ...

My first implemention enforces the correctness by taking as arguments proofs that the given number is either divisible by 3 or a proof that it is not divisible. That way can call the constructor Fizz if and only if you can provide proof of division by 3 and a proof of non division by 5.



So just by defining a type FizzBuzz and the signatures of the constructors of this type we have no possibility of making a mistake in the implementation. Nice! Here's are the types and signature of methods.



IF you're curious about the implementation it's here

Besides being a major challenge, for me, in mastering dependent types and understanding that types can act as proofs, it actually worked out quite OK. Certainly it does not allow for incorrect code, so it was a successful experience. Sure it is a bit of verbose and contains a bit of pseudo-duplication.

But not extensible
Now there's an extension to FizzBuzz, namely Bang. Bang is the word for every multiple of 7, for instance given the number 21 we should return FizzBang. Now without Bang there are 4 possible results, Fizz, Buzz, FizzBuzz and the number. Now here's where things become interesting because with Bang there are 8, so the problem of verbosity and pseudo-duplication gets a lot worse. Clearly the first solution isn't very extensible

A better solution
A different approach is to decompose the type FizzBuzz into smaller orthogonal types. Lets consider the type Fizz (either a IsFizz or a Not IsFizz), the type Buzz, then FizzBuzz can be modeled as a tuple (pair) of Fizz an Buzz (the full code).



If we add the functionality of Bang then all we have to do is create a new type Bang, and a new composed type a 3-tuple of Fizz, Buzz and Bang. We don't have to break the existing type FizzBuzz nor the former function, we could possibly even keep the former method, a good example of the open-closed principle. Open-closed-principle with dependently typed code!

Possibly we'd fear that by making the types less closed we'd be able to code an incorrect solution to fizzbuzz. But that's still not possible.

Learnings
Keeping types small in the sense that they contain little data (few arguments) and have few constructors, favours reuse through composition. It might seem obvious in hindsight, but I discovered this much in the same way that I discovered the use of small objects in OO.

Some people say that strongly typed languages like Idris doesn't allow for extension, that they'd be closed by design. What I learned from this experience is that while that certainly applies to a type and functions on existing types, we can still compose types in new ways. Given of course that our types are small enough.

jeudi 17 mai 2018

Bug generator: Non constrained construction


A bug generator is a style of code that is likely to contain bugs or produce bugs in the future as the code is extended by making them more likely. This is of course an anti-pattern. There are corresponding Prevention Patterns, basically less error-prone alternatives. Now that the term is defined, lets dive into today's bug generator, namely non constrained construction.


Non constrained construction means that it is possible to construct an invalid object. Examples are 1) mandatory parameters are set after construction using a setter 2) No validations in the constructor, for instance instantiating a PhoneNumber using any string. 3) Several parameters of the same type in the constructor. Inversion of the order parameters becomes likely. Example the constructor takes 3 strings


Bug: Object created without mandatory parameter
Some instance variables are added with setters. There is no guarantee that every user of the object thought of setting at least the mandatory ones. One single instantiation without the mandatory parameter suffice to create a bug, that takes the form of null pointer exceptions or a reference to undefined (JS) at  runtime. It can also take the expression of inconsistent behaviour if the depending code handles null as a special flag (see Null-Flag bug-generator). Alternatively it complexifies all the client code with checks to see if the parameter has been set. Remember those if (object != null) { .. } blocks?

Prevention pattern: All mandatory parameters in constructor
It is extraordinary easy to prevent this type of bug, simply by enforcing all mandatory parameters in the constructor(s). 

If there are several combinations of parameters we can use  several constructors or for languages that allows only one constructor we can use static factory methods, that enumerate the valid ways instantiating an object. e.g.

    
private constructor(mainCourse, starter?, dessert?) {...}

public static withoutDessert(mainCourse, starter) {
return new Menu(mainCourse, starter)
}

public static withoutStarter(mainCourse, dessert) {
 return new Menu(mainCourse, null, dessert)
}

Bug: Object contains invalid data
We might instantiate a phone number assuming that we always feed a string containing the country code country code. So when we try to call this number we get a failure or we call someone in another country. Likewise we might accept some IBAN number without validating the key. Later when we post it to some webservice that does validation, then we need to report an error to the user in an asynchronous way like sending an email, sms etc. Handling bad data late is always more costly than just rejecting it on input.

Prevention pattern: assertions in the constructor
Do validations in the constructor. You can mostly get away with throwing an error and only catching it at the top level, like a generic error handler, a very common pattern in the world of REST services is to map Error objects to HTTP status codes via a generic handler.

The reason we prefer doing the validations in the constructor rather than doing them before construction is because it  guarantees that the validation is made.

Bug: Constructor parameters are switched

For instance our menu from above takes strings mainCourse, starter and dessert as parameters. It is very easy to switch the order

Prevention pattern: Type parameters 
Introduce distinct types for each parameter i.e. MainCourse, Starter and Dessert. This makes it impossible. While this might seem a bit clunky in some mainstream languages it's also a step towards the removal of primitives which adresses another problem, namely the bug generator Primitive Obsession.

Prevention pattern: pass a map/dictionnary or use a parameter object or yet a builder
if each parameter has a name that is visible in the code we reduce the chance of a bug. It is harder to put something in front of the wrong name, like

    { dessert: 'pizza royale', mainCourse: 'chocolat mousse'} 

than it is to make a mistake of order. You might recognize the concept of Connascence of name vs position

Bug: Object not fully initialized before use
Let's imagine an object where we have to call an initialisation method after instantiation like the well known init(). The code gives no guarantee that this will always be done For instance forgot to call init(). The effect of this bug is not dramatic as  in most cases it'll just confuse the developer for a long time as to why the app doesn't work correctly. It rarely slips into production, just slows down the development.

Prevention pattern: call init() in the constructor
Whenever possible.

Prevention pattern: use a factory method
So that the fragile sequence is only in one place. Or refactor so that you pass the result of the init() method to the constructor. i.e the init() method becomes static and/or is moved away from the class all together. e.g.

public constructor(resultOfInit) {}

Prevention pattern: when two objects references each other
When there's a cyclic dependency between two objects, this can be eliminated on the type level by interfaces but the runtime dependency might remain. Then one must be instantiated before the other. We have at least two options for solving this. 1) It might be possible to extract a third object on which the two others depend on, thus eliminating the cyclic dependency, but more often 2) we make this more explicit, like Spring's @PostConstruct. The benefit is that it becomes easy to find all such objects.

There's no particular conclusion to make. It documents the problems and a range of alternative solutions. 

Credits to Peter Kofler whith whom we detailed the bugs and prevention patterns


mardi 1 mai 2018

Bug Generator: Use of indices

Let me just start by stating what I mean by a Bug Generator. It's a style of code that is likely to contain bugs or produce bugs in the future as the code is extended. This is of course an anti-pattern. There are corresponding Prevention Patterns, basically less error-prone alternatives. That being said, let's dive into the Bug Generator Use-of-indices.


Use of indexed access is low level, off-by-one errors are very common. Also index out of bounds can happen. Usually we can simply avoid this by using higher level constructs such as for-each-loops and higher-order functions such as map and filter.


Bug: Off-by-one errors

We access the data by some index. The problem can range from some simple error in a loop construct. For instance we use <= instead of < in loop. To harder-to-spot errors like passing the index to some function and using the index while modifying it by a -1 or +1. 
A basic example of this. Say we need to find the first cat in a list of animals. The bug will only occur when there is no cat in the collection

Bug: Index-out-of-bounds 

Variation of the above bug. This is off-by-one where we actually step outside the array.

Prevention pattern: use lambdas and higher-order-functions

higher order functions like map, filter, some/first, etc have already implemented the looping and we just have to provide a function that the higher order function will use on each element.

Prevention pattern: for-each-loop

If we really must use imperative style

Prevention pattern: link the structure length to the index calculation

E.g. modulo on length. An example would be picking cards from a deck. Lets assume that whenever we get to the end of the deck we're supposed to start from the beginning. A naïve implementation would be to

Prevention pattern: Wrap the array and index in a class (they are nearer).

This is particularly useful when the same calculation is done in several places. Whenever we have a class it is easy to find the code we need to manipulate the date inside. Another advantage is that the behaviour becomes easily testable when isolated in a class.
It'd be very easy and natural (i.e. likely) that we'd test getNextCard both by calling it many times in a row and with large values of someStep.

This solution is related to the Bug generator Primitive-Obsession that will probably be described in the future.

Credits to CodeCop (Peter Kofler) with whom I've worked a lot to explore the concept of Bug Generators. We sketched out this pattern together.

dimanche 15 avril 2018

Bug pattern - Hidden testable code

When there's a bug it is very likely the existing design contributed to it's existence. This suggests that there are corresponding design anti-patterns, patterns of code that are latent bugs

This time lets look at the pattern Hidden testable code

Hidden testable code

By Loveteamin [CC BY-SA 3.0 (https://creativecommons.org/licenses/by-sa/3.0)], from Wikimedia Commons

Problem: Easily testable code is hidden inside hard to test code. For this reason the code is either not tested or the tests are not as thourough as would be needed.

Schematically it looks like this


Solution: It is very very cheap to fix this. Just an Extract Method automatic refactoring in order to extract a Pure Function that can be extremely easily tested.



Recently I came across an example of this bug generator pattern. It had a first bug that was fixed and tests weren't added because it was considered too costly to add tests for it. However the idea of testing an extracted function was not even considered. Two weeks later it became clear that this piece of code contained a second similar bug. The code had some very extensive transformation logic between two calls to a web service and two calls to the persistence layer. Below is a shortened version of it. The problems were both errors in the pure transformation logic.



Once extracted and thoroughly tested the logic can be both refactored and extended with confidence. Bugs will have a much harder time hiding in this kind of light.




The idea that we can cleanse the system from most of the bugs is called BugsZero. You can learn more about it here, and by various talks by Arlo Belshee, available on youtube.