A lot of popular applications were written in Lua. Josh treats Lua as a functional language and makes some sparks fly.
If you write code in mainstream programming languages, you might never have heard of Lua. But I bet you've heard of Angry Birds, Wikipedia, or World of Warcraft. So what made their developers use Lua in those mainstream products? Perhaps it's because Lua is lightweight, cross-platform, embeds and extends well, performs well, has a small memory footprint, and a shallow learning curve. I'd like to believe some are attracted to Lua because it supports different paradigms and includes some pretty sweet functional programming capabilities.
First-Class and Higher-Order Functions
Saying functions are 'first-class' just implies there's nothing special about them, so they can be treated like any other value. A 'higher-order' function does at least one of two things: it either takes other functions as arguments, or it returns functions. These are important capabilities in functional languages, but they are missing or a bit funky in many mainstream languages.
Suppose we have a handy list of cats. We can use Lua's 'table' concept, a swiss-army style collection that behaves like both an array and a hash:
A function that collects the names of all of our cats would look like this:
Lua uses 1-based indexes, which are easy to think about but can be easy to get wrong.
We could write a very similar breedsOf(cats) function, but we'd have to repeat the logic for iterating over the collection of things. We'd also use 'special-purpose' language syntax twice (for...in). Higher-order functions give us a uniform way of combining functions to reduce duplication:
Via this sort of reuse, functional programs tend to consist of lots of very small things.
Recursive functions eventually call themselves, like this:
Easy to follow, but executing this function for some values of n will result in a stack overflow error. That's because on each successive invocation of factorial(n - 1), the machine must retain a reference to the previous iteration on its stack. The stack is finite, so it eventually runs out of space and the program explodes:
Lua 5.0 added 'proper tail calls,' a sort of functional goto that makes it possible to structure a recursive function such that it never runs out of stack space:
Can you spot the difference? For a Lua function to benefit from tail call optimization its return value needs to call a function (often itself) and do nothing else. Expressions are allowed to appear in the arguments, as in return factorialUntil(n - 1, n * answer) because function arguments are evaluated immediately. But expressions such as return n * factorial(n - 1) cannot be optimized because the * is the last operation, instead of the recursive function call.
We had to define our own map() earlier, which we'll use again in a minute. Let's define a few more functional primitives that we can arrange into bigger and better things:
I should point out that all of these are relatively slow, because they copy elements between Lua tables. We can guarantee immutability of these tables, so we could avoid copying and simply manipulate 'pointers' into a limited set of underlying tables. That's what proper functional languages like Haskell do by default. But I want to focus on functional semantics rather than performance, so we'll keep things simple.
We're ready to tackle an actual problem that a typical Lua hacker might face. Lua is often used as a scripting language for games. These days games often include particle systems that generate organic-looking graphical effects. I've always wanted to build a particle emitter, so today I'm going to start a fire, functional style!
A functional particle system wouldn't retain mutable state, so it might be a function that accepts state (particles) as an argument and produces new state (new particles).
But before I can start writing my particle system, I need something capable of drawing. I was without my computer this weekend, so that gave me an excuse to use Codea, a cute little iPad Lua development environment with a drawing API.
The Codea runtime calls a draw() function in your code, once per frame. After drawing each particle, I'll mutate the flame to acquire a new state of the flame as a whole. This bit is necessarily imperative, so let's keep it short and sweet:
As we shall see, f = f.next() is in fact the only example of mutable state we'll need.
Next, a drawing 'adapter' renders each particle as an ellipse in Codea's drawing API:
So, what exactly is a 'flame'? In my model, a flame comprises of many particles, each of which 'evolves' over time to make a new flame:
Each particle changes style over time, taking a step function describing how it changes style over time:
I've used one object-oriented detail here, by keeping state (or style) close to behavior that manipulates that state (the next function). But since I'm keeping clear of mutable state, I don't think the pure functional police can bust me.
My model describes a step in the evolution of the whole flame in three parts:
Particles are generated at a point in time, then they repeatedly mutate until they die. Given a set of particles, we 'prune' any dead particles, 'mutate' each remaining particle, and 'generate' new particles to keep the flame alive. Each operation produces a new set of particles, the state of the flame as a whole:
Before we can generate particles, we have to describe what it means to be a particle in a flame. I'm sure there are established models for this, but I have a vague mental image of how I want my fire to look, so I'm going to make an approximation based on my fuzzy knowledge. In my eyes, flames seem to consist of upwardly moving particles that also move smoothly from side to side, change color, get smaller, and gradually disappear. So my spark particle is this somewhat random looking transformation of position, color, and size over time:
What are all these magic numbers? What's this 'seed' thing? These are just some dials I came up with to tweak the 'personality' of each spark and to give the overall flame a varied-but-consistent feel. The sparks I was fiddling with? Oh yes, those were generated by this last piece of my functional puzzle:
Several more particles and lots more knob twiddling later (omitted for brevity) and the outcome is something like the smooth flame animation I was daydreaming of:
The individual frames don't do it justice, so you'll have to imagine the upwardly, side-to-side movement and color progression as each particle burns and fades into nothingness. Or you can grab the code from github and fiddle with it in Codea or elsewhere.
Twiddle those knobs again, tweak the magic numbers, add different kinds of particles, and you'll generate a completely different effect. As it stands, this is about right for some jazzy looking torches in my new dungeon adventure game!
Josh Chisholm is a co-founder of Featurist, a software development consultancy based in London. He started programming because he wanted to write games. After over a decade of serious programming, he's just getting back to where his fun began. His first commercial game will hit a device near you, any day now. He occasionally tweets as @joshski but he regularly plays with code at github.com/featurist.