Overview
This repository contains the material for Introduction to Functional Game Programming with Scala, held at LambdaConf 2014 in Boulder, Colorado.
This README file contains a walkthrough for the workshop, as well as the following source code:
- In the
src
directory, you'll find a skeleton for a functional game that uses Scalaz and Monocle. This application is intended as the basis for the final set of exercises in the workshop. - In
snippets.txt
, you'll find a collection of snippets developed over the course of the workshop. You should be able to run this file from the command-line using thescala
process.
Introduction
Welcome to Introduction to Functional Game Programming with Scala! You're going to learn purely-functional programming by writing a fun little game.
Games are some of the most stateful applications in existence!
In fact, many games are really full-fledged simulations. Almost every piece of data changes at every iteration!
Can you really use pure functional programming to write games? The answer is yes, and this workshop is here to show you how.
We're going to focus on writing a text-based RPG (or adventure game, if you like). This way, you won't need to create or animate graphics, and you can focus on the essence of handling state in a functional way.
Ready? Good, let's begin!
The Game Loop
At the center of every game is something called a game loop. The game loop handles input and updates the state of the game.
In an imperative style, we could write a game loop using a while
loop:
var executing = true
while (executing) {
executing = handleInput()
updateGameWorld()
}
Since we're only focusing on text-based RPG, we can flesh this out a bit more.
Try dumping the following code into an empty file, and executing the file with scala
:
var executing = true
while (executing) {
val input = readLine()
if (input == "quit") executing = false
// Here's where we'd update the game world.... now just print out what they typed:
println("So, you want to " + input + ", do you?")
}
This while
loop prints out your commands until you enter the command "quit", at which point it stops executing.
What's the purely-functional alternative to loops? Recursion, of course!
Let's rewrite the game loop using a self-recursive function:
def loop(): Unit = {
val input = readLine()
if (input == "quit") return;
println("So, you want to " + input + ", do you?")
loop()
}
loop()
Note: Unbounded self-recursion on the JVM will overflow the stack, but there's a robust way to work around this called trampolining, which basically involves stuffing steps of the recursion into data structures, and using an "interpreter" to execute the recursion step-by-step.
This is a good start, but the above game loop is far from purely-functional. Neither readLine()
or println()
are pure functions (deterministic functions of their input), which in a larger context, makes it harder to reason about code.
How can we make this game loop more functional and easier to understand?
There are lots of ways to do this, but the abstraction that's going to help you most as a beginning functional programmer is called a monad.
Bet you guessed that, didn't you?
Exercises
- Write your own game loop using recursion. Hopefully, it's more interesting than the provided game loop!
- Add the
scala.annotation.@tailrec
annotation to your loop to see if Scala can compile it to awhile
loop. The compiler will give you an error if your function is not tail-recursive.
Monads
As you've probably heard, monads are a "functional design pattern" that come up a lot when you're writing purely-functional code.
There's a good reason for their ubiquity: monads encapsulate the essence of sequential computation.
In C, statements are executed one after another. Do this, then do that.
In purely-functional programming, there are no "statements". Instead, there are just declarations (which you can think of as rewrite rules) and expressions, which yield values.
In the purely-functional context, "do this, then do that" can be represented nicely using monads.
Monads have two functions that obey some laws:
- A
point
method to "lift" an ordinary value into the monad. For example, for theList
monad,point
is the singleton constructor_ :: Nil
. It lifts an individual value of typeA
into a list of typeList[A]
. For theOption
monad,point
is the constructorSome.apply()
, which lifts an individual value of typeA
into an option of typeOption[A]
. - A
bind
method to produce the next computation from the value of the current computation (calledflatMap
in Scala). For theList
monad, this is just the methodList.flatMap(f: A => List[B]): List[B]
, and it callsf
on every element to obtain lists of a different type, then merges all those lists into one list.
The bind
/ flatMap
function encodes sequential computation, and you can see this fact just by looking at the type signature:
def flatMap[A, B](value: M[A])(f: A => M[B]): M[B]
The first parameter is the monad. In Scala, if the flatMap
method were defined on the monad itself (like it is for Option
and List
), then you wouldn't pass it explicitly, but I've included it in the type signature for clarity.
The second parameter is a function that takes a value of type A
.
From looking at the type signature, you know that in order for flatMap
to call the function you pass, flatMap
first has to produce a value of type A
.
Since flatMap
works for all types (it's polymorphic in type parameter A
), it can't just produce a value of type A
out of thin air!
Instead, to get a value of type A
, flatMap
first has to "evaluate" M[A]
(where the meaning of "evaluate" depends entirely on the monad). Thus, M[A]
represents a computation that might yield a value of type A
.
This is the essence of sequential computation: flatMap
is prevented by its type signature from calling the function f
before it first produces an A
!
Monads make it easy to handle state, effects, and lots of other things in a purely-functional way. Next, we'll take a look at effectful monads to show how that's done.
Exercises
sealed trait Errorful[+A] {
def flatMap[B](f: A => Errorful[B]): Errorful[B] = ???
def map[B](f: A => B): Errorful[B] = flatMap(f andThen (Continue.apply _))
}
case class Error(message: String) extends Errorful[Nothing]
case class Continue[+A](value: A) extends Errorful[A]
- Given the above code, implement the method
flatMap
. Can you call the functionf
without first having a value of typeA
? - Scala's
for
notation just compiles down to sequences offlatMap
andmap
. Write afor
comprehension that uses theErrorful
monad you just wrote.
Effectful Monads
For some monads M[A]
, you can extract the A
out of M[A]
(for a List
, you can perform the extraction with List.head
, though it's unsafe because the list might be empty).
If you can't write an extraction function for some monad in a purely-functional way, then the monad is called effectful.
Effectful monads can do anything from printing to the screen to launching nuclear missiles!
In Haskell, the mother of all effectful monads is called IO
, and writing code in the IO
monad is very similar to writing code in Java or C or any other imperative language.
The IO monad is basically a giant data structure that describes what effects to perform. You can create, compose, manipulate, and pass these IO
values around in a purely-functional way, and nothing effectful happens until when and if you call the impure extraction function.
In Scala, we can write our own IO monad in just a few lines of code:
class IO[A] private (run0: => A) {
def run = run0
def flatMap[B](f: A => IO[B]): IO[B] = IO(f(run).run)
def map[B](f: A => B): IO[B] = flatMap(a => IO(f(a)))
}
object IO {
def apply[A](v: => A): IO[A] = new IO(v)
}
Note: This definition of the
IO
monad will blow the stack for deeply recursive code, but we'll eventually switch to Scalaz, which has a trampolined implementation that won't blow the stack.
Notice how the constructor for IO
simply captures the effect in a call-by-name parameter, so it isn't actually evaluated, it's just stored as data inside the IO
class.
We can use IO
to wrap ordinary Scala functions like readLine()
and println()
to make them purely-functional:
def getLine: IO[String] = IO(readLine())
def putStrLn(v: String): IO[Unit] = IO(println(v))
We can then compose IO
actions together using flatMap
or map
, or using Scala's for
notation:
val rez: IO[Unit] = for {
line <- getLine
_ <- putStrLn("You wrote: " + line)
} yield Unit
Note: The underscore in the notation
_ <- putStrLn(...)
just means we don't care about the value ofUnit
that will be produced byputStrLn
(what would we do with it?).
As you can tell from this implementation, creating an expression of IO[Unit]
doesn't actually perform any effects — you need to call run
to do that and extract the final value:
rez.run
Although every Scala application using IO
will have to call run
at some point to interact with the outside world, you can always push that out to the main
function of your application, so that 99.9999% of your application code is purely-functional.
We now have enough tools to write a purely-functional game loop!
Exercises
- Using the IO monad built in this section, write a simple program that asks the user for his or her name, then prints out, "Hello, [name]". Don't cheat and print out the text literal "[name]", either! :-)
- Try to add a conditional, so that if the name string is empty, the program spits out, "You must have a name!" Hint: If you get stuck, try using
map
andflatMap
instead of Scala'sfor
notation.
The Super Simple, Pure FP Game Loop
Here's the full game loop, including the dependency on IO
and all helpers:
class IO[A] private (run0: => A) {
def run = run0
def flatMap[B](f: A => IO[B]): IO[B] = IO(f(run).run)
def map[B](f: A => B): IO[B] = flatMap(a => IO(f(a)))
}
object IO {
def apply[A](v: => A): IO[A] = new IO(v)
}
def getLine: IO[String] = IO(readLine())
def putStrLn(v: String): IO[Unit] = IO(println(v))
def gameLoop: IO[Unit] = for {
input <- getLine
_ <- putStrLn("So, you want to " + input + ", do you?")
_ <- if (input == "quit") IO(Unit) else gameLoop
} yield Unit
gameLoop.run
This version of the game loop looks a lot like the non-FP version — but except for gameLoop.run
at the end, this code is purely-functional.
We're off to a good start, but our game is dead boring! To solve that, we're going to have to talk game state.
Exercises
- Sketch out a game by creating a Scala file with a
main
function that calls therun
method of theIO
action representing the entire game. - In addition to a game loop, add entrance and exit messages to your game (e.g. "Welcome to SimpleRPG v1.0!" and "Goodbye!").
Game State
To make our game interesting, we need to add non-player characters (NPCs), a model of the geography of the game world, a model of the player character, and a way to move around the game world and perform other activities.
Every command the user enters into the game has the potential to modify NPCs, the geography, items in the game world, or player attributes.
If you think that sounds like a lot of state, you're right!
There are many approaches to handling all this state in a purely-functional way, including functional reactive programming and event-oriented programming.
The one we're going to look at involves the State monad.
Note: The
State
monad is not always the most elegant tool for the job. But it's a good fallback when other techniques don't pan out, so it's a good tool to learn first.
The State Monad
The essence of the State monad is very simple: it's a function that takes the old state and produces the new state, together with some value.
To orient you, take a look at the following hypothetical function pop
, which "pops" the head off a queue (represented as a List
):
def pop[A](queue: List[A]): (List[A], A) = (queue.tail, queue.head)
This function takes the old state (List[A]'), and returns both the new state (
List[A]), together with a value representing the head of the queue (
A`), bundled in a tuple.
That's basically all there is to the State
monad.
For a given type of state (call it S
), we can define the State
monad as follows:
case class State[S, A](run: S => (S, A)) {
def flatMap[B](g: A => State[S, B]): State[S, B] = State { (s0: S) =>
val (s1, a) = run(s0)
g(a).run(s1)
}
def map[B](f: A => B): State[S, B] = flatMap(a => State.point(f(a)))
}
object State {
def point[S, A](v: A): State[S, A] = State(run = s => (s, v))
}
Notice how in the definition of flatMap
, the state is threaded through both state functions. So the final state you get has been "modified" by two functions in sequence.
To see how we can use State
, let's invent a simple GameState
:
case class PlayerState(health: Int)
case class GameState(player: PlayerState)
We can now write a little helper function to update the player's health and return�the new health value:
def updateHealth(delta: Int): State[GameState, Int] = State { (s: GameState) =>
val newHealth = s.player.health + delta
(s.copy(player = s.player.copy(newHealth)), newHealth)
}
Let's use this helper function to inflict some serious damage on the player:
val stateWithNewHealth: State[GameState, Int] = for {
_ <- updateHealth(-10)
newHealth <- updateHealth(-100)
} yield newHealth
The result is a State
action. If we want to perform the action, we have to "run" the State
. How do we do that?
Remember, State
is just a function from one state to another state and some value. So to "run" State
, all we have to do is pass it an initial game state:
val stateWithNewHealth: State[GameState, Int] = for {
_ <- updateHealth(-10)
newHealth <- updateHealth(-100)
} yield newHealth
stateWithNewHealth.run(GameState(PlayerState(health = 100)))
If you print out the final health, you'll find it's -10. Yep, we succeeded in killing off our player!
Exercises
- Flesh out
GameState
more by adding aGameMap
and anx: Int
andy: Int
location. Define theGameMap
as a rectangular grid, where each cell can contain things like a name, description, list of characters, list of items, etc. - Add a few helper functions that return
State
actions. For example, one helper could update the player's position by moving in some direction.
The Stateful Game Loop
We've written two separate pieces of a game: the game loop, and some miscellaneous code for updating game state.
We used monads to solve both problems, so we have some code written with the IO
monad, and other code written with the State
monad.
If you try to combine the code, you'll find you get type errors:
for {
input <- readLine
newHealth <- if (input == "fight") updateHealth(-10) else State.point(-1)
} yield newHealth
The reason why you get these type errors will be clearer if you explicitly write out flatMap
and all the type signatures.
If we think of IO
as representing the effect of IO, and State
as representing the "effect" of updating state, then what we really want is a way to combine them both together into a single monad that captures both effects.
This way, we can both perform IO and update state in the same game loop.
It turns out that for theoretical reasons, we can't just take any two monads M1
and M2
and combine them into another monad M3
. It's not possible!
However, there are a number of ways to combine monadic effects, ranging from Free
monads to monad zippers and views to monad coproducts (and lots more!).
The particular approach we're going to look at involves monad transformers.
Note: Like the
State
monad, monad transformers are ubiquitous, well-studied, well-supported, and do a very respectable job of composing effects.
Monad Transformers
A monad transformer is a special version of a monad that can stack its own effects on those of another monad. If you stack a monad transformer on another monad, the result forms a monad, which combines the effects of both monads together.
Not all monads have monad transformers. For example, the IO
monad doesn't have a transformer version.
Fortunately, we're in luck: while IO
doesn't come in a transformer flavor, the State
monad does!
It's convention to suffix monad transformers with the letter 'T', which of course is short for "transformer".
Before we can write a StateT
, we first have to be more precise about what a monad is, because StateT
can only be stacked on something that is a monad.
To do that, we can write a simple little trait called Monad
:
trait Monad[M[_]] {
def point[A](a: => A): M[A]
def flatMap[A, B](ma: M[A])(f: A => M[B]): M[B]
def map[A, B](ma: M[A])(f: A => B): M[B] = flatMap(ma)(a => point[B](f(a)))
}
If some type is a monad, for example, List
or Option
, then you can write an implementation of this trait for that type. Here are the implementations for Option
and IO
:
implicit val OptionMonad = new Monad[Option] {
def point[A](a: => A): Option[A] = Some(a)
def flatMap[A, B](ma: Option[A])(f: A => Option[B]): Option[B] = ma.flatMap(f)
}
implicit val IOMonad = new Monad[IO] {
def point[A](a: => A): IO[A] = IO(a)
def flatMap[A, B](ma: IO[A])(f: A => IO[B]): IO[B] = ma.flatMap(f)
}
Now we're all ready to write the monad transformer version of State
:
case class StateT[M[_], S, A](run: S => M[(S, A)]) {
def flatMap[B](g: A => StateT[M, S, B])(implicit M: Monad[M]): StateT[M, S, B] = StateT { (s0: S) =>
M.flatMap(run(s0)) {
case (s1, a) => g(a).run(s1)
}
}
def map[B](f: A => B)(implicit M: Monad[M]): StateT[M, S, B] = flatMap(a => StateT.point(f(a)))
}
object StateT {
def point[M[_], S, A](v: A)(implicit M: Monad[M]): StateT[M, S, A] = StateT(run = s => M.point((s, v)))
}
Notice how the implementations of flatMap
and map
require that M
be a monad by passing along an implicit Monad
trait for that type.
We use the methods of M
's monad to implement the monad for StateT
.
In the case of our game, we need the state transformer to stack on IO
. We can define a type synonym called Game
which describes the resulting monad:
type Game[A] = StateT[IO, GameState, A]
We now have a monad, aliased Game
above, which allows us to both perform IO and update state!
But before we write a new game loop that combines state with IO, we need to tackle one more subject: monadic lifting.
Exercises
- Just like
State
has a monad transformer variant, so also doesOption
. Writemap
andflatMap
for the type,case class OptionT[M[_], A](run: M[A])
. - Use the
OptionT
you just wrote to define a new monad that combines the nullability effect ofOption
with theIO
effect.
Monadic Lifting
Using our new Game
monad, it's very easy to access and modify state. Here's the new updateHealth
function written for the Game
monad:
def updateHealth(delta: Int): Game[Int] = StateT[IO, GameState, Int] { (s: GameState) =>
val newHealth = s.player.health + delta
IO((s.copy(player = s.player.copy(health = newHealth)), newHealth))
}
The only difference is that we have to wrap the return of the state function in IO
, because StateT
is stacked on IO
.
Fortunately, it's easy to write a helper function that does this wrapping for us:
def state[A](f: GameState => (GameState, A)): Game[A] = StateT[IO, GameState, A](s => IO(f(s)))
This helper function makes it possible to define updateHealth
in a way that looks just like the old definition:
def updateHealth(delta: Int): Game[Int] = state[Int] { (s: GameState) =>
val newHealth = s.player.health + delta
(s.copy(player = s.player.copy(health = newHealth)), newHealth)
}
What if we want to perform some IO in our game monad? The naive attempt will fail with type errors:
for {
input <- readLine
health <- updateHealth(100)
} yield health
The code won't compile because readLine
is still in the IO
monad, not the Game
monad.
Remember, Game
is StateT
stacked on top of IO
. To execute an IO
action inside Game
, then we need some way of "lifting" that IO
action into Game
.
We know what the type signature should look like:
def liftIO[A](io: IO[A]): Game[A] = ???
How about the implementation? Turns out to be simple:
def liftIO[A](io: IO[A]): Game[A] = StateT[IO, GameState, A](s => io.map(a => (s, a)))
We just pass along the original state unmodified (since an IO
action won't affect the game state), bundled with the value computed by the IO
action.
How can we use this new function? Simply like so:
for {
input <- liftIO(getLine)
health <- updateHealth(100)
} yield health
And there we have it! Two monadic effects combined into one monad.
We can now both perform IO and update state from the same game loop!
Since we're only using two IO functions, it makes sense to define versions of them for the Game
monad, as follows:
def getLineG: Game[String] = liftIO(getLine)
def putStrLnG(v: String): Game[Unit] = liftIO(putStrLn(v))
Now we can define a non-trivial game loop that allows user input to change the game world:
def gameLoop: Game[Unit] = for {
_ <- putStrLnG("What would you like to do?")
input <- getLineG
_ <- putStrLnG("So, you want to " + input + ", do you?")
_ <- if (input == "fight") for {
newHealth <- updateHealth(-10)
_ <- putStrLnG("Your new health is: " + newHealth)
_ <- gameLoop
} yield Unit
else if (input == "quit") liftIO(IO(Unit))
else for {
_ <- putStrLnG("I'm sorry, I don't understand your command.")
_ <- gameLoop
} yield Unit
} yield Unit
gameLoop.run(GameState(PlayerState(100))).run
Pretty cool, huh? At this point, we're literally one step away from having all the tools necessary to write a clean, purely-functional game.
That one step involves making updating state simple, composable, and very powerful, in a way you can't match with procedural programming.
Exercises
- Modify the previously introduced game loop to tell the user if and when they die (i.e. their health goes below 0). If the player dies, exit the game.
- Add the player location to the game state (if you haven't already), and allow the player to go north, east, west, and south (printing out the new location each time).
Lenses
There's some ugly boilerplate hidden in the updateHealth
function, which you probably had to recreate if you completed the exercises in the last section:
(s.copy(player = s.player.copy(newHealth)), newHealth)
Notice how to update the health, we have to copy the game state, and copy the player state, and then combine them together.
For just updating the player health, this isn't too awful. But it gets progressively worse as you dig deeper and deeper into GameState
and have to update more and more data.
Fortunately, FP has an answer, and it's called lenses.
A Simple Lens
A lens is a combination of a functional getter and a functional setter. Together, they give you a way of manipulating a subset of data inside a data structure (which I'll sloppily call a field).
For a data type S
, and "field" type A
, a simple lens can be defined as follows:
case class Lens[S, A](get: S => A, set: (S, A) => S)
The getter takes an instance of the data type, and returns the field value. The setter takes both an instance of the data type, and the new value, and returns a new instance of the data type.
Here's how we would define a Lens
for the health
field of PlayerState
:
val health = Lens[PlayerState, Int](_.health, (s, a) => s.copy(a))
And here's another lens for the player
field of GameState
val player = Lens[GameState, PlayerState](_.player, (s, a) => s.copy(a))
Using the lens is really simple:
val oldPlayer = PlayerState(100)
val health = health.get(oldPlayer)
val newPlayer = health.set(oldPlayer, health + 200)
They great thing about lenses is that they compose in lots of useful ways. For example, we can define a new method |->
on lens that allows you to dig deeper into a structure:
case class Lens[S, A](get: S => A, set: (S, A) => S) {
def |-> [B](that: Lens[A, B]): Lens[S, B] = Lens(
get = that.get compose get,
set = (s, b) => set(s, that.set(get(s), b))
)
}
This method allows us to combine the previously defined player
and health
lens into another lens that can dig into the player
field of a GameState
, dig further into the health
field of the PlayerState
, and get or set the value of health
!
Here's how we define the composite lens:
player |-> health
That's just as simple as player.health
!
Look at how simple and clean our updateHealth
function becomes:
def updateHealth(delta: Int): Game[Int] = state[Int] { (s: GameState) =>
val newHealth = (player |-> health).get(s) + delta
(player |-> health).set(s, newHealth) -> newHealth
}
We can further generalize this approach by creating a helper function that's aware of lenses and our Game
monad:
def update[A](lens: Lens[GameState, A])(f: A => A): Game[A] = state[A] { (s: GameState) =>
val newValue = f(lens.get(s))
lens.set(s, newValue) -> newValue
}
Now updating health, or any other field regardless of how deeply nested it is, becomes as simple as follows:
def updateHealth(delta: Int): Game[Int] = update(player |-> health)(_ + delta)
That's powerful (at this point, we don't even need the helper function), and it just scratches the surface of what these abstractions are capable of.
We have all the tools we need to build a purely-functional game. So let's put them to use!
Exercises
- Write a generic
get
function whose signature isdef get[A](lens: Lens[GameState, A]): Game[A]
. - Define lenses for whatever other data you have in your
GameState
(as well as for all substructures thereof).
Tying it all Together
You now have a choice: you can take the code you've built up to this point (you have been completing the exercises, right?), or you can jump ship and use the code in the src
directory.
The code in the src
repository builds on the material presented thus far (for example, adding basic command parsing so you don't have to worry about that), and uses the Scalaz and Monocle libraries for super-powered versions of some of the classes built here (Monad
, StateT
, IO
AKA Task
, Lens
, etc.).
You can launch the existing game very simply for testing:
31 introgame % sbt 2014-04-15 21:23:29 John ttys002
Detected sbt version 0.13.0
Starting sbt: invoke with -help for other options
Using /Users/John/.sbt/0.13.0 as sbt dir, -sbt-dir to override.
[info] Loading project definition from /Users/John/Documents/github/lambdaconf/introgame/project
[info] Set current project to introfp (in build file:/Users/John/Documents/github/lambdaconf/introgame/)
[info] Defining */*:console::traceLevel, */*:consoleProject::traceLevel and 2 others.
[info] The new values will be used by no settings or tasks.
[info] Run `last` for details.
[info] Reapplying settings...
[info] Set current project to introfp (in build file:/Users/John/Documents/github/lambdaconf/introgame/)
> run
[info] Compiling 1 Scala source to /Users/John/Documents/github/lambdaconf/introgame/target/scala-2.10/classes...
[warn] there were 1 deprecation warning(s); re-run with -deprecation for details
[warn] one warning found
[info] Running introgame.Main
What would you like to do now?
Now let's get to work building that game!
Exercises
- Give the player the ability to pick up and put down items in any location (e.g. "pick up rusty sword", "drop rusty sword").
- Add an
NPC
class that models a non-player character. ExtendCell
to hold a list ofNPC
s. - Classify
NPC
s as "friendly" or "hostile" (you can be more elaborate but this is the bare minimum). If the player looks around, describe friendly and hostileNPC
s differently. - Allow the player to "fight" NPCs, exchanging damage in a deterministic (i.e. non-random) fashion.
- Allow items to modify the attributes of characters (player or non-player) as well as modify the outcome of a fight.
- BONUS - HARD: Add a deterministic random effect so you can incorporate randomness into fights. Note: You can do this by sticking the state information in
GameState
, or you can add aRandomT
monad transformer in the stack (or if you want even more of a challenge, you can add a free algebra describing randomness, and use a coproduct functor to combine that with the existing IO free algebra). - BONUS - HARDER: Generate events for all actions that happen, whether to player, the environment, an item, or a NPC, and store these events somewhere for later reference. Refactor the game so that player commands generate events, which in turn might generate other events, etc., and produce state updates through monoid actions. You will find it much easier to encode game logic using this approach.