Pretty image
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.

You probably know some JavaScript. Although Lua has quite a different heritage, it shares many design ideas with JavaScript and feels similar. Syntactically, Lua is a bit less spiky:

 function hello() {
  say("Hi there, I'm JavaScript");
 }
 function hello()
  say "Howdy, I'm Lua"
 end

Just like JavaScript, Lua owes a lot to Scheme, a Lisp dialect. But because both JavaScript and Lua appear closer to Java and C, you wouldn't immediately recognize the Lisp underpinning either of them. Look beyond the syntax and Lua has some features that make it great for using functional techniques as part of a multi-paradigm approach.

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:

 local cats = {
  { name = "meg", breed = "persian" },
  { name = "mog", breed = "siamese" }
 }

A function that collects the names of all of our cats would look like this:

 function namesOf (things)
  local names = {}
  for index, thing in pairs(things) do
  names[index] = thing.name
  end
  return names
 end
 print(namesOf(cats)[1]) --> meg
 print(namesOf(cats)[2]) --> mog

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:

 function map (things, fn)
  local mapped = {}
  for index, thing in pairs(things) do
  mapped[index] = fn(thing)
  end
  return mapped
 end
 function namesOf (things)
  return map(things, function(thing)
  return thing.name
  end)
 end
 function breedsOf (things)
  return map(things, function(thing)
  return thing.breed
  end)
 end
 print(namesOf(cats)[1]) --> meg
 print(breedsOf(cats)[2]) --> siamese

Via this sort of reuse, functional programs tend to consist of lots of very small things.

Recursion

Recursive functions eventually call themselves, like this:

 function factorial (n)
  if n == 0 then
  return 1
  else
  return n * factorial(n - 1)
  end
 end
 print(factorial(5)) --> 120

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:

 print(factorial(-1))
 lua: factorial.lua:5: stack overflow
 stack traceback:
  factorial.lua:5: in function 'factorial'
  factorial.lua:5: in function 'factorial'
  ...

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:

 function factorial (n)
  return factorialUntil(n, 1)
 end
 function factorialUntil (n, answer)
  if n == 0 then
  return answer
  else
  return factorialUntil(n - 1, n * answer)
  end
 end
 print(factorial(-1)) --> Loops forever, but doesn't crash

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.

Functional Primitives

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:

 function each (things, fn)
  for i, thing in ipairs(things) do
  fn(thing)
  end
 end
 function filter (things, fn)
  local filtered = {}
  each(things, function(thing)
  if fn(thing) then
  table.insert(filtered, thing)
  end
  end)
  return filtered
 end
 function cons (things, ...)
  local all = {}
  each({...}, function(t)
  table.insert(all, t)
  end)
  each(things, function(t)
  table.insert(all, t)
  end)
  return all
 end

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.

Functional Flames

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:

 f = flame({}, 0)
 function draw()
  each(f.particles, function(p)
  drawParticle(p.style)
  end)
  f = f.next()
 end

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:

 function drawParticle(style)
  fill(style.red, style.green, style.blue, style.alpha)
  ellipse(style.x, style.y, style.radius, style.radius)
 end

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:

 function flame(particles, t)
  local newParticles = evolve(particles, t)
  return {
  particles = newParticles,
  next = function()
  return flame(newParticles, t + 1)
  end
  }
 end

Each particle changes style over time, taking a step function describing how it changes style over time:

 function particle(step, style, t)
  local newStyle = step(style, t)
  return {
  style = newStyle,
  next = function()
  return particle(step, newStyle, t + 1)
  end
  }
 end

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:

 function evolve(particles, t)
  return generate(mutate(prune(particles)), t)
 end

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:

 function mutate(particles)
  return map(particles, function(p)
  return p.next()
  end)
 end
 function prune(particles)
  return filter(particles, function(p)
  return p.style.alpha > 0
  end)
 end

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:

 function spark(style, t)
  return {
  x = style.x - math.sin(t * 0.5),
  y = style.y + 1,
  red = style.red + (math.sin(t * style.seed) * 40),
  green = style.green + (math.sin(t * style.seed) * 33),
  blue = style.blue,
  alpha = (style.alpha - 5 * style.seed) * 0.97,
  seed = style.seed,
  radius = 5 - t * 0.03
  }
 end

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:

 function generate(particles, t)
  return cons(particles,
  particle(spark, {
  x = 0,
  y = 0,
  red = 255,
  green = 40,
  blue = 10,
  alpha = 220,
  seed = 0.3
  }, 0),
  particle(spark, {
  x = 1,
  y = 2,
  red = 220,
  green = 30,
  blue = 10,
  alpha = 180,
  seed = 0.5
  }, 1)
  -- snip: lots more spark particles!
  )
 )

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:

sparks.jpg

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.

Send the author your feedback or discuss the article in the magazine forum.