16 Dec 2014
I stumbled across this great programming site last week called CodinGame. It’s basically a site full of fun programming challenges ranging from AI to maths to data structures.
One of the best things about the site is that it supports a whole bunch of languages including C++11, Scala, Java, Python and C# to name a few. This is brilliant as it allows you to implement solutions to the same problem in different languages and see which is fastest, shortest, simplest, etc. It also poses an added challenge of picking the right language for the problem.
I’m seriously toying of the idea of introducing it at work - perhaps picking a challenge a week and then getting the team together to discuss their implementations.
The only downside is that it’s pretty addictive…
01 Dec 2014
For a while now I have been tempted by the dark art that is functional programming. It’s high order functions and powerful one liners hold a certain allure for me and last year I even started playing around with Haskell.
I wasn’t ready.
This year I’ve decided to give FP another crack and have even bought myself a book - “Functional Programming in Scala” (this is an excellent intro to FP and although the examples are in Scala it focuses on teaching core FP principles) and took a Coursera course, of the same title, which turned out to be a great accompaniment to the book. So that’s how you know I’m serious.
I wanted to learn FP for a few reasons - firstly: I like learning random new things, secondly: everyone is banging on about it and thirdly: I wanted to see if it could improve my C++.
The Good…
Here are some of my favourite aspects of FP:
- Everything is immutable and pure (well almost otherwise it would useless).
- State is explicitly modeled.
- Almost all programs can be modeled using a selection of higher order functions such as map, fold, etc.
- Functions are not understudies to classes and can be composed, chained, passed around - brilliant.
- Generic programming is simple and achievable with little boiler plate code.
- Pattern matching.
- Lazy evaluation: No boilerplate for caching the results of expressions! Don’t pay for what you don’t use!
One of the most impressive aspects of Scala is that you can build almost every language construct from first principles - you can create your own booleans and ints and even create your own if, then, else statements. Completely useless but really shows the power of the language.
The Bad…
Things I didn’t like so much:
- Apparently FP programmers like single letter parameter names (because everything is so generic and based on maths notation). I couldn’t bring myself to do this.
- And…that’s pretty much it.
In truth because I was using Scala (which is a hybrid OOP/FP language) it was much easier to incorporate state at the edges of my program than it would have been using a pure FP language like Haskell (and state is pretty important - put it this way I’m glad my bank is interested in the state of my account).
One of the issues I had with Scala was trying to determine when to use FP and when to use OOP. Usually I ended up with case classes acting as simple structs holding a collection of data. My big dirty secret is that sometimes I would even use an imperative for loop (what’s the harm in a wee ++i) in place of for comprehension on a range.
And the C++
Unfortunately there is little scope for me using Scala in my day job so I had to salvage what I could and bring that across to C++ - this wasn’t as much as I’d hoped. I’ve always thought of C++ as multi-paradigm (and it is) but even C++11 struggles to do proper FP - you have to pick and choose your battles.
One of the cornerstones of FP is immutability and Scala has a whole bunch of immutable data structures. Updating the contents of a data structure produces a copy of it, and because this happens all the time in Scala, and because the structures are immutable; sometimes a copy isn’t even made. Seriously, if you want a substring of a longer string you basically get a reference to part of the original string - it’s never going to change. The compiler is set up to perform these kind of optimisations - C++ isn’t. If we made a copy of vector, array or map every time we updated an element then we’d be in trouble (imagine creating a new texture every time you updated a texel!).
C++11 has introduced anonymous lambda functions which really help with the functional style and several higher order functions such as std::transform(i.e. map), std::accumulate(i.e. reduce), etc. but could really do with some more convenience functions for, among other things, composing functions i.e.
def compose[A, B, C](f : B => C, g : A => B) : A => C = {
a => f(g(a))
}
Also (and I’m by no means the first to mention this) C++ is in desperate need of a D-lang style “pure” keyword that prevents any non-local state from being modified.
That being said there’s always learning to be had:
- Stop making unnecessary setters! I do it all the time - “Oh here is a getter without its partner. Must be lonely. Stick a wee setter in there. Job done. Now how do I make this thread safe…?”.
- Sometimes a copy is good. Although it’s usually too expensive to copy a data structure on every modification perhaps it makes sense to batch modifications together and then make a single copy updated with all changes. This pairs up nicely with the data oriented approach of “where there’s one, there’s many” and actually FP and DOD make good bedfellows.
- Higher order functions are useful. I should make more use of std::algorithm to make my code more generic and less verbose (although the lambda syntax in C++ is still a little verbose compared to Scala i.e
data.map(x => x + 2) vs std::transform(data.begin(), data.end(), newData.begin(), [](auto x){return x + 2;});)
- Model state explicitly. It’s much easier to reason about data and state (not to mention multi-thread it) if it is visible and explicit and covered in warnings and alarms rather than encapsulated in an object that you have no idea is thread safe or not. Concurrency isn’t that hard is access to state is carefully managed.
- Void functions are (usually) stateful functions. This is so blindingly obvious but I had never really considered it to be the case. Reducing the number of void methods or functions will reduce the amount of hidden state and side-effects in your application.
Heading over to the dark side
I’d really like to take on a project using a FP language and hopefully I’ll get a chance in the course of my work to experiment more with FP. If anyone else is interested in learning FP I’d really recommend approaching it without any OO prejudices and learning it from the ground up. Embrace its strange syntax, higher order functions and immutability - don’t fight against it and try and enforce an imperative style. Accept that creating and managing state should be a chore - this will help you mimimise it. Don’t be put off because it is different. Different isn’t bad it’s just different.
I’ve already started learning about functional reactive programming (again via Coursera) so there is a good chance my next blog post will be about that.
P.S.
I’ve also attached my first effort at a functional program and my revised effort based on the huge lambasting I got on “CodeReview” (cheers guys).
05 Mar 2014
It’s going to be an interesting year at Tag Games as we are planning on open-sourcing some of our in-house tech (hopefully I’ll be able to go into more detail in the next few months). I’m both really excited, and slightly apprehensive, at the thought; as a great deal of the code and the architecture is mine and this will be the first time that I’ve had any code of real worth available for external criticism (or external love).
So far the process has made me look at my code in a completely different way, re-evaluating every design decision I’ve ever made in case I have to justify it to some guru hacker. It’s also really strange thinking of the code as the product rather than the means. The best thing so far is being able to learn Git on company time!
As part of open-sourcing we will be looking to actively engage with a good core community that will help drive the direction of the technology as well as make use of it. The community aspect is what concerns me most as it is vital and difficult to encourage and sustain a vibrant and contributing body of developers. However it shames me to admit that I have never contributed to an open-source project and expecting developers to contribute to mine is perhaps slightly hypocritical. So I have decided to do something about that and starting next week will be looking to regularly contribute to an open-source project (that gives me the weekend to actually decide which one). This will a) allow me to no longer be a hypocrite, b) give me something to actually blog about rather than the usual pish and c) provide a good opportunity to sabotage the opposition.
Hopefully this will give me a good insight into how an open-source community works and will help me develop a thick-skin as I suspect I’ll need it over the next year!
29 Oct 2013
I often read that as a programmer you often have to approach problems from a different perspective in order to find the most elegant solution. Well I was made to look a right idiot the other day when I was arguing a new feature was going to increase the scope of the project; only to find out it wouldn’t. Worst of all it was a designer that came up with the solution!
The game we are working on has many complex systems built from components. In the game components control the generation of resources, the trading and transporting of resources and the consumption of resources. One of the main system loops involves a farm growing crops over a period of time and employees are dispatched to fetch these resources periodically. Each farm is a field in which the crops are grown and people collect the crops from the farm. Effectively the crops are a single resource.
The designers wanted to add a system in which the player could grow and harvest trees instead of crops.
Me: “Brilliant; we already have a system for that. We will just create a new farm type that grows tree crops. Pop on a producer controller and a fetch controller - job’s a good ‘un”.
Designer: “Yeah, yeah something like that. Except that trees can grow anywhere across the map and employees must visit each tree, in turn, to obtain the wood, and once the wood is obtained the tree takes time to regenerate, and the trees aren’t really owned by the farm because employees can gather from any tree. But other than that it’s just like a farm”
Me: “So…nothing like a farm. This will require a whole separate system in which field and farms are separated, in which employees work their way through every crop in a field. Each crop must have its own state to manage individual regrowth. Is it really worth all the extra time?”
Designer: “Hmmmmm…”
Designer: “Why not just make each tree a farm?”
Me: “Excuse me a minute… stabs pen through eye”
19 Sep 2013
I stumbled across this blog post the other day describing a new programming language called “Glow” and thought the premise behind the language design was really interesting. Unlike most programming languages that have a consistent set of rules, “Glow” consists of two major programming paradigms. The two rule sets revolve around, what the author describes as, “big programming” and “small programming”. At a high-level i.e. objects, systems, components, etc, you want a strict rule set: explicitly specified types, immutability, no side-effects; but at a low-level i.e. functions, tasks, etc, you want the flexibility of dynamic types and to keep the code minimal by inferring types rather than explicitly specifying them.
A two paradigm solution to application design could be really beneficial as it better describes the approach taken when planning and designing code. The “Glow” language enforces this via a “piping” system which controls data flow, access and mutability. Going forward with my programming language I wonder how I could integrate some of these concepts.
I plan on investigating further to see if any similar languages exist and whether users find they reduce code complexity, bugs and side-effects. Also I wonder what other coding complexities could be reduced by hybrid languages