Bottoms

In Haskell, every type has at least one value – ⊥. The empty type is not actually empty – it has ⊥ in it, sum types contain the sum of the two types plus one extra element – ⊥, etc.

But we don’t always need to do this. The ⊥ value of a type has one important feature, it’s the least defined value in the type. So let’s investigate the four primitive types:

Empty – as this type has no values, there’s obviously no least defined one, so we definitely need to add an extra value.
() – this type has only one value, so that value clearly is the least defined. Thus (⊥ :: ()) can be defined safely to be ().
Sum types – any value we chose in (A + B) must carry a tag to determine which of type A or B it’s in, and so cannot be the least defined value – if we chose a value in A, it carries enough information to say it’s not in B, and vice-versa. Thus for sum types, we must add an extra ⊥.
Product types – assuming that we have bottom values in types A and B, we can define ⊥ for (A × B) as being (⊥ :: A, ⊥ :: B).

One can clearly make at least two choices here, either the choice Haskell makes – add bottom values everywhere, or add bottom values only where they are needed. One could argue convincingly that what Haskell does is very consistent and predictable, but interestingly, the other choice has some nice results.

The functor laws demand that fmap id x = x. A special case of this is that fmap id ⊥ = ⊥. Lets look at this for pairs – that means that fmap id undefined = undefined, but this isn’t as lazy as we could be – we’d like to be able to return a tuple straight away, without looking at any of the tuple we’re given.

If however we chose to only add a bottom value to a type when needed, then bottom for tuples really is (⊥, ⊥), and we’re able to define fmap for tuples as fmap f x = (fst x, f $ snd x) and not break the Functor laws.

Any more comments about this are appreciated. What other consequences does this decision have?

Dependancies are Bad

This entry’s going to be relatively short. I wanted to point out something that I find very odd.

In the software industry, we strive to eliminate code-duplication. Duplicated code is duplicated effort, duplicated errors, and duplicated complexity. Yet I hear the same thing cropping up over and over again in many different projects – “I’m not going to use xyz, because it adds an extra dependancy”.

Are dependancies so bad that we can’t stand to see just one extra one in the aid of reducing code duplication?

My feeling is that the reason that people don’t want to do this is that the dependancies are often pretty heavy weight things. What they’re really complaining about is that “xyz” covers too much, and that they only want to use a small part of it.

In the interests of increasing code reuse then, I’d like to suggest to everyone one simple task. Release packages, release many packages, release small packages. Small packages are great, because people won’t see them as great monolithic blocks that they don’t want to depend on. Bottom line: if a package can be split into two in a reasonable way, do it! Oh, and one more thing: for the love of god, do it in an open way!

How you should(n’t) use Monad

I’m often surprised by the fact that many people see monads as the be all and end all of Haskell’s abstraction techniques. Beginners often struggle over them thinking that they’re something incredibly important and complex. In reality though, monads are neither important, nor complex, and that’s what I aim to show with this little tutorial about what other abstraction techniques you can use, and when they’re appropriate.

First things first – IO

The reason a lot of people come across monads is that they want to get on with interacting with the outside world – they want to do I/O. I’m going to get this out of the way quickly. In Haskell, IO is kept in a carefully constrained box, because unconstrained it violates referential transparency (that is, you can get multiple answers from the same call to the same function depending on what the user happens to type/how they wibble the mouse/etc). You can recognise functions in this box by their type signature – they involve a type that looks like this: IO something.

Here’s a few examples:

-- Call this, and you get back a Char,
-- carefully wrapped up in an IO type.
getChar :: IO Char
-- This one doesn't have an interesting result,
-- only a unit value wrapped up in an IO type.
putStrLn :: String -> IO () 

These can be stuck together with the handy do notation:

main = do
  putStrLn "What is your name?"
  name <- getLine
  putStrLn ("Your name is " ++ name)

There, that’s that out of the way – we can do IO now, and we didn’t need to understand anything nasty or complex.

Some Abstraction techniques – Dealing with values in boxes

We often deal with values that are hidden inside other types. For example, we use lists, to hide values in, we use Maybes etc. What would be nice, is if we could apply a function to the values hiding in those boxes. Early in learning Haskell I’m sure you will have met a function that can do this for lists: map. This can be generalised though: Enter the Functor. Functors can do one thing, and one thing only, they can apply a function to a value inside an outer construction. They do this with the function fmap (or Functor map). Lets look at some examples:

For Lists, fmap is simply map:

> fmap (+1) [1,2,3,4]
[2,3,4,5]

For Maybe values fmap lets us apply a function to the value inside a just:

> fmap (+1) (Just 1)
Just 2
> fmap (+1) Nothing
Nothing

For Tuples, fmap lets us apply a function to the second half of the tuple (if we import an extra module that defines it):

> import Control.Applicative
> fmap (+1) (1,2)
(1,3)

We can use fmap to target a function into several layers of boxes by composing applications:

> (fmap . fmap) (+1) [(1,2), (3,4)]
[(1,3),(3,5)]

Here, the first fmap pushes (fmap (+1)) inside the list, and the second fmap pushes (+1) inside the tuples.

Putting things in boxes

All that isn’t very useful if we can’t actually put something in a box in the first place. This is where the pure function comes in handy. This function lets us wrap anything we like in a box.

> pure 1 :: [Int]
[1]
> pure 1 :: Maybe Int
Just 1
> pure 1 :: Either String Int
Right 1

In Haskell, the pure function is in the Applicative class (you’ll need to import Control.Applicative). The Applicative class does some other interesting things as we’ll see in a minute. Because of this it would be nice if pure were separated into its own little class all on its own, but unfortunately that isn’t the way it is in Haskell (at the moment at least).

Boxes everywhere

So, we’ve seen how to put something in a box, and we’ve seen how to apply a function to a value in a box, but what if our function is in a box too? At this point, the Applicative class really comes into its own. The (<*>) function from Applicative lets us apply boxes to each other as long as they have the right types of values inside.

> (Just (+1)) <*> (Just 1)
Just 2
> [(+1), (*2), (^3)] <*> [1,2,3]
[2,3,4,2,4,6,1,8,27]

That second result is not entirely clear – what’s going on? Well, the (<*>) function has applied each function to each argument in turn, and bundled up all the results in one list. (+1) gets applied to each argument, generating the results 2,3 and 4; (*2) gets applied to each argument, generating the results 2,4 and 6; and finally (^3) gets applied to each argument, generating the results 1,8 and 27.

An important note: All Applicatives are also Functors. You can implement fmap for any Applicative like this:

fmap f a = (pure f) <*> a

Applicative in fact does this for you, but calls the function (<$>).

Functions that produce boxes

When we have functions that produce values that are hidden inside boxes, we have a problem. Each time we apply the function we get an additional layer of boxes, this isn’t particularly pretty, nor composable. This is where monads come in. Monads add a single function called join, which is used to flatten out the layers of boxes:

> join (Just (Just 2))
Just 2
> join [[1],[2],[3,4,5]]
[1,2,3,4,5]

The join function lets us compose our box-producing functions more easily. We now fmap our box producing function over values in a box. This results in a 2-layer set of boxes. We can then use join to squash that back down again. This pattern is so useful that we call it “bind” or (=<<).

f =<< a = join (f <$> a)

Some people like to define this the other way round:

a >>= f = join (f <$> a)

This allows a very imperative style of programming where we ask the language to take the result of one computation, push it through a function, take the results, push them through another function, etc.

As with Applicatives and Functors, all Monads are Applicatives. We can define the (<*>) function using only bits of a Monad and the pure function:

f <*> a = f >>= (\fv -> a >>= (pure . fv))

We can see here a common pattern with monadic programming. We bind a function returning a monadic value into a lambda. Haskell provides a syntactic sugar for doing this called do notation:

f <*> a = do
  fv <- f
  av <- a
  pure (fv av)

We can now see clearly that IO in Haskell is not using any magic at all to introduce an imperative concept to a functional language, instead the IO type is simply a monad. Remember, this means that it’s a functor and an applicative too, so we can use <$> and <*> wherever we please in IO code to apply functions to IO values.

Why you don’t always want to go for Monads

As we’ve seen, Monad sits atop a set of classes proudly the most powerful of all, but that doesn’t mean we want to use it all the time. As we’ve seen, Monad gives us a very imperative feel to our code – it reveals an order that isn’t necessarily there. Do notation particularly seems to suggest (in our example above) that we should first take the value out of f, then take the value out of a, and then apply the two. In reality, this order is not there, the Haskell runtime is free to evaluate these in any order it likes. This can make such language constructs dangerous. Firstly, we’re functional programmers because we like describing what things “are”, not what steps you should take to produce them. Secondly, the steps we seem to give here, are not the ones that the run time will really take in the end.

Lets look at an example of when we really shouldn’t use Monads. We have excellent Parser combinators in the Parsec library. These let us define small parsers, and stick them together using the Monadic interface. Lets define a small parser to parse an Int that may or may not be in a string:

parseInt = do
  ds <- many1 digit
  pure $ read ds

parseMaybe p =
      (do n <- p
          pure (Just n))
  <|> (pure Nothing)

We are expressing an ordering that we don’t intend to – first we accept at least one digit into ds, then we read them and rewrap them in a parser. In parseMaybe first we parse something, and take the value out into n, then we wrap it in Just, and give it back.

This isn’t clear. Why couldn’t we just describe the grammar? Why do we have to specify an order? Lets patch parsec to provide an Applicative instance:

instance Applicative (GenParser a st) where
  (<*>) = ap
  pure = return

Note that I’m using a shorter version of the definition of (<*>) in a monad using the ap function. Now we may use the applicative functor interface:

parseInt = read <$> many1 digit

parseMaybe p = (Just <$> p) <|> (pure Nothing)

Not only are these definitions shorter, but we can quickly and easily see their meanings – an integer is many digits, with read applied to get them into a form we can use in Haskell.

Lets look at a more complex example:

data Record = R { firstCol, secondCol :: Maybe Int }
              deriving (Show)

parseRecord = do
  col1 <- parseMaybe parseInt
  char ','
  col2 <- parseMaybe parseInt
  char '\n'
  pure (R col1 col2)

Again, we’re specifying an order we don’t want to see. Lets look at this in applicative style:

parseRecord =
  R <$> (parseMaybe parseInt <* char ',')
    <*> (parseMaybe parseInt <* char '\n')

Note the use of the (<*) function – this simply takes the value from the left hand parser, and passes it up, ignoring the value returned by the right hand parser. We can now see that parseRecord constructs a record from two maybe Ints, separated with a comma. We haven’t introduced any orderings that we don’t need to, and we’ve even condensed our code a little.

Conclusions

We’ve seen the hierarchy of classes in Haskell in all its glory, rather than focusing unduly on the Monad, we’ve seen that the Monad interface, while powerful, is not always desirable. Hopefully we’ve seen that a lot of our monadic code can be cleaned up to use the Applicative (or maybe even Functor) interface instead.

Between Applicative and Monad

Last night in #haskell, there was some interesting discussion going on, in which we discovered a class of data structures that seems to fit in between Applicative and Monad. A foreword though: Most of the credit for this article should go to Brent Yorgey, Cale Gibbard, Peaker and Tristan Seligmann – the article is the product of a discussion with them last night in which they did most of the work.

Why doesn’t Applicative cut the mustard

One of the major drawbacks of Applicative is that you can’t make choices without evaluating too much. If we attempt to use liftA3 if', we find that we evaluate both branches, no matter what we get back from our predicate.

So just use Monad, right?

Well no, bind/join give us too much power, they let us make choices between an infinite number of functions, we only want the ability to make a choice between a finite number of branches.

We can define this class then:

class Applicative b => Branchy b where
  ifB :: b Bool -> b a -> b a -> b a

We can add a pair of laws to this that force this to really be an if like operation, and to make sure that we get lazyness properly:

ifB (pure True ) x y = x
ifB (pure False) x y = y

These laws though may not be complete in getting us to a useful class. Cale has suggested this additional law to get us closer, but holes in the laws are a definite place to do some work hashing this out.

f <*> ifB b x y = ifB b (f <*> x) (f <*> y)

So then, do we actually have something useful here? For that, we would have to find two things – an Applicative which is not a Branchy (to show that we’ve not just reinvented applicatives), and a Branchy that’s not a Monad. Well, clearly Const a is not a Branchy, a Const a Bool does not actually contain a Bool with which to decide which branch to take. And, here’s the useful Branchy that’s not a monad:

instance Branchy ZipList where
  ifB (ZipList ps) (ZipList xs) (ZipList ys) 
      = ZipList $ zipWith3 if' ps xs ys

Using Either instead

Andrea Vezzosi commented this morning that the interface would be rather nicer if rather than using ifB, we used eitherB :: b (Either c d) -> b (c -> e) -> b (d -> e) -> b e. While each can be implemented in terms of the other, eitherB allows for a little more efficiency. The following implementation of eitherB evaluates the either twice:

eitherB fe fl fr = ifB (isLeft       <$> fe)
                       ((.fromLeft)  <$> fl) 
                       ((.fromRight) <$> fr) <*> fe

This version of the class also makes the connection with ArrowChoice rather clearer.

I’d really appreciate everyone’s comments on this topic.

Simulating n-bodies and functional programming

The n-bodies problem

There’s been some activity in the #haskell IRC channel recently towards coming up with a better solution to the n-bodies problem.  In this problem, you’re given a set of bodies, and are asked to simulate Newtonian gravity on them.  Most of the solutions I’ve seen go past have involved some sort of crazy state monad based stuff, reading from and writing to STUArrays and other imperative ideas.  So, I thought I’d try and solve the problem using a pure functional style instead.

Reactive

I’ve recently been playing with Reactive a lot, initially for my work, but also just because it’s so damned cool.  Reactive is a library for Haskell that lets you describe time varying values in a purely functional way.  That is, out goes the concept of state, and in comes the concept of describing exactly what is going on.

Back to n-bodies

In order to simulate newtonian physics, we need the bodies’ mass,the positions of the bodies, and the velocities of the bodies:

data Body = Body { mass     :: Double
                 , position :: Point3  Double
                 , velocity :: Vector3 Double
                 }

That was pretty straight forward, lets get down to the core of the problem – simulating gravity:

accelBetween :: Body -> Body -> Vector3 Double
accelBetween p1 p2 =
  (mass p2 *^ vecBetween) / ((mag vecBetween) ^ 3)
  where
    vecBetween = position p2 ^-^ position p1

computeAccels :: Body -> [Body] -> Vector3 Double
computeAccels p = sum . map (accelBetween p)

Well, that was surprisingly easy!  The accelBetween function describes the newtonian gravity equation just as the maths does, and summing up the acceleration due to all the other planets in the system is fairly straightforward.

What we’ve not seen yet though, is any of that lovely functional reactive programming I was talking about.  We know now how to compute the acceleration affecting any one body at any one time, but what we want to know is the acceleration affecting a body at *any* time.  To do this, we’re going to need to move from doing computations on Bodys, to instead doing computation on Behaviors of Bodys.

bodyAccels :: [Behaviour Body] -> [Behaviour (Vector3 Double)]
bodyAccels ps = withOthers (liftA2 computeAccels) ps

withOthers :: (a -> [a] -> b) -> [a] -> [b]
withOthers f xs =
  withOthers' f [] xs
  where
    withOthers' _ _  []       = []
    withOthers' f os (x : xs) = f x (os ++ xs) : withOthers' f (x : os) xs

The withOthers function here is just like map, but it passes in all the other values in the list in a second argument to the function.

So then, bodyAccels computes a continuous acceleration function for all the bodies in the system.  For each body, it runs the computeAccels function, giving it all other bodies in the system as its second argument.  Crucially, liftA2 allows us to do this in the Behavior Applicative, so we are no longer computing it on rigid, static bodies, but instead, on all the positions and velocities the bodies in the system will ever have (isn’t lazyness great!).

Finally, we can get from these accelerations down to the velocities, and then positions of the bodies using integration on the acceleration:

bodyVel :: Body -> Behaviour (Vector3 Double) -> Behaviour (Vector3 Double)
bodyVel p acc = (velocity p ^+^) <$> integral dt acc

I’m sure you can imagine what the bodyPos function looks like.  You may wonder what the dt in here is talking about.  This is an unfortunate effect of not being able to mathematically integrate arbitrary functions.  Instead, we must use euler integration, and that requires us to provide times at which to take samples.  The dt argument is an event which ticks reasonably fast, and progresses our simulation:

dt :: Event ()
dt = atTimes [0,0.01..]

So, now we are able to combine all our efforts together, and solve the whole n-bodies problem:

nbodies :: [Body] -> [Behaviour Body]
nbodies ps = pbs
             where
               pbs = Body <$> (mass <$> ps) <*> pps <*> pvs
               pps = zipWith bodyPos ps pvs
               pvs = zipWith bodyVel ps pas
               pas = bodyAccels pbs

Conclusions

A lot of assumptions are made about how we must write programs.  Often, even beautiful mathematical problems end up described as horrible state-full masses of code that obscure what it is we’re trying to compute.  I’ve presented a solution to the  n-bodies problem using the Reactive library to get a handle on time in a purely functional setting, it turned out that this was rather beautiful!

Full code for my solution can be found below.

Continue reading

Copyright and EULAs

Prelude

I had intended this blog to be programming based, not copyright rant based, so I’m going to keep this entry short.  Rest assured, I will post something programming orientated soon, I just need the posts to percolate through my brain.

“That EULA is invalid, I’m not breaking the law”

This is a sentence I’ve heard many times now.  It’s often used to justify pirating a particular piece of software.  This entry is going to be based around showing why this is such a bogus argument.

What is Copyright

I’m going to discuss copyright in the western world here. There are several countries that I’m sure deviate from what I’m going to say in many interesting ways. It’s also important to note here that I am not a lawyer, and I may well be talking out of my ass, but that’s not going to stop me ranting :P.

Copyright is a right granted to the person who produces a work (and sometimes also to the subject). It allows them to decide how, and where that work is copied. They may chose to not allow anyone to ever copy the work, they may chose to give it away freely, or they may chose any in between.

They may chose their in between stage by issuing licenses to people. The license stipulates exactly who can copy a work, when, how, how often etc. I remind you, that the person giving the license owns the copyright on the work, and can chose to hand it out in any way shape or form they like – most countries will ban illegal contracts though, so there are some restrictions.

Illegal Contracts, and Invalid licenses

When a contract stipulates illegal terms, it may be ruled by a court that the contract is invalid. This is the bandwagon that I am referring to above. People will commonly claim “this license would be found invalid in a court, so I can copy freely”. But wait! Remember, the copyright holder still owns all the distribution rights. Your license to copy the work being invalid does not automatically make the work public domain. No, instead, all it means is that you now don’t have any claim what so ever to copy the work! Without that piece of paper saying “you may copy this work”, you may not copy it.

Conclusion

Don’t try to argue that your EULA is invalid! It’s counter productive, all you’re doing is reinforcing the fact that you have no right to copy the item. If you don’t like the terms of the EULA, approach whoever owns the copyright, and ask them for a different license.

Why the GPL is not free

Introduction

The Free Software Foundation [FSF1] touts the GPL[GNU1] as an all singing, all dancing defender of your freedoms. We are told that the GPL is at the heart of defending four freedoms:

  1. The freedom to run the program, for any purpose (freedom 0).
  2. The freedom to study how the program works, and adapt it to your needs (freedom 1). Access to the source code is a precondition for this.
  3. The freedom to redistribute copies so you can help your neighbor (freedom 2).
  4. The freedom to improve the program, and release your improvements (and modified versions in general) to the public, so that the whole community benefits (freedom 3). Access to the source code is a precondition for this.

[GNU2]

I assert though that the GPL does not give us freedom, merely different restrictions.  I even assert that it does not give us all of the freedoms listed above.  In this post, I will argue that the GPL is inherently flawed when it comes to freeing software.

What did I write?

Allow me to take a detour before we begin.  I would like to investigate a related topic that is at the core of my argument, and that is the question of exactly what code you wrote.  Let us imagine a typical scenario – you are the author of a free, open source library.  The purpose of your library does not particularly matter, so lets say it encrypts widgets.  You pour your heart and soul into your library, and it becomes stable and fully featured.  This diagram represents the project as it stands:

You are proud of your project

You are proud of your project

So lets now suppose that a third party takes your code, and builds upon it.  We might represent this as such:

A large addition to your project

A small addition to your project

A large, and a small addition to your project

What’s important to realise here is that the amount of code you have written has not changed.  Even if the addition that the 3rd party writes simply wraps your library with a pretty GUI, the amount of code you have written has neither grown, nor shrunk.

What you license

Okay, so now let’s ask the question.  What relevance did that have?  Well, it helped clarify exactly what you are licensing when you attach the GPL to your code.  You are licensing your code, and only your code.  And yet, the GPL makes a restriction on the license for the derivative work.  Noting here, that the derivative work is wholy someone else’s work.

The most common argument I hear pushing the GPL is that with a weaker license (say, BSD[BSD1]), a third party can take your code, extend it, and close it.  So let’s think about what that means.  In order to close your code, they would have to have taken it, removed all open sources for it, and then rereleased it in a closed form.  But that doesn’t make any sense.  You’re still distributing your source code under a free and open source license, so how have they closed it?  They haven’t – your code has remained open source.  So then, what have they closed?  Well the answer is, their code, and only their code is closed source, and that’s fine – it’s their right to license their code in any way they like.

So the conclusion then, is that a company can come along, and take libWidgetCrypt and produce a thin wrapper around it, and start making an enormous profit by selling the result at $10,000.  Yes, that’s possible, but it’s also a rather unlikely scenario.  If all they’ve done is write a thin wrapper, then you, or someone else in the open source community is perfectly capable of making such a thin wrapper in no time at all.  Then all you need do is undercut them by $10,000, and a good chunk of freedom.

The more likely scenario though, is that a company may come along and take libWidgetCrypt and produce a large amount of other code that just happens to use your library at its core.  Then said company will sell their code, and their extensions for a large sum of money, and they are perfectly entitled to do so.  It is after all, their code.

Believe it or not, this scenario is even one which is beneficial to you.  Said company, is likely to find bugs in libWidgetCrypt, and fix them.  From my experience of such things happening, they more often than not, contribute their changes back to you when they make such fixes to your library, even though they’re not required to!  Yes it happens that they patch it and run with the patch, but again – they wrote the patch, they’re entitled to do that!

Where the GPL fails

I’ve now gone into detail a lot on exactly what you are licensing when you apply a GPL license to your code, but I haven’t looked at what I claimed I would show at the start of the blog.  I haven’t told you why the GPL is not a free license.  To do that, I’m going to concentrate on the last freedom that it claims to offer – “The freedom to improve the program, and release your improvements (and modified versions in general) to the public, so that the whole community benefits (freedom 3).”  Suppose that I am a company, and I am building a product to release.  I would like to use your library in my program, I would even like to improve your library, and release the improvements to the public so that the whole community benefits.  Unfortunately, at the end of the day, I need to ship a product, so I’d like to keep the core of my project closed source.  Unfortunately, the GPL outlaws this kind of interaction.

So, we have a good citizen, a company that wants to release their patches to your library back to the community, and yet, the GPL is banning them from doing so!  It is not giving them freedom at all!  Instead, the GPL is a different set of restrictions.

It may be that you personally find the set of restrictions that the GPL offers more morally palatable than traditional closed source licenses, but it is not a free license.  It does not grant freedom, it grants different restrictions.

Conclusions

The GPL is not a free license, in that it restricts freedoms to only people it deems to be morally acceptable.  Often, there are people who do not fall inside this morally acceptable box, yet do really have good intentions.  Thus, the GPL is too restrictive for many projects.  Instead, it’s often a good idea to use a truly FOSS license, like for example the BSD license.  Doing so, will not make you vulnerable to companies magically making your code closed source, as you will continue to distribute it.  It may be that they will close a small addition to your code and attempt to sell it for vast amounts of money.  However, in that situation, you can just release the same minor change, and give it away totally freely too.

References:

[BSD1] http://www.opensource.org/licenses/bsd-license.php
[FSF1] http://www.fsf.org
[GNU1] http://www.gnu.org/copyleft/gpl.html
[GNU2] http://www.gnu.org/philosophy/free-sw.html