When I was at Santa Clara University there was this class on formal
systems that all students were required to take. It covered predicate
calculus, lambda calculus, and computational theory. For most of us,
this class was hell. American students are notorious for scoring theory
and this class was no different. There was much wailing and gnashing of
teeth, followed by a near revolt. All the students really wanted was
vocational training in the latest language de jour.
Nonetheless, I took the challenge and was frustrated that I had no
tools to try out all these new concepts other Tarski's world. There was
nothing for lambda calculus. But then a search on the internet turned
up this thing called ML. I was hooked, but there was no way to do
commercial work with it. No one I worked with even knew what ML was let
alone lambda calculus. All I got from them were blank stares.
So 6 years passed and then along came F#. Being based on the .Net
platform, I thought; why not give it a go again? Even if none of my
peers share my interest, at least they can still use what I create.
To get started, I took the Concurrent Life sample application from
the distribution (thank you to whoever wrote it) and put a C# face on
it just to make sure I could build a GUI in C#. Then I set out to build
a Prisoner's Dilemma application modeled on the concurrent life just to
reinforce what I learned.
I soon realized that I was struggling with the new language even
after having programmed ML/Haskell many years past. The thousands of
lines of C# code I had written had set down grooves in my mind like an
old LP. There must be millions of groove heads out there, so I thought
I should help my fellow programmers get their arms around this thing
called F#.
The application has four layers:
- C# User Interface
- F# Controller Class
- F# Engine Class
- F# Core Logic
The core logic contains the functions for managing the grid and
cells. The engine is the state machine that runs in a background thread
doing the work. The controller class runs in the user interface thread
and gives the user interface a class based interface and uses friendly
types to make the C# code simpler.
Core Logic
The core logic resides in a module with an interface. Don't confuse
interfaces for modules with interfaces in C#. In F# they are called
signatures and they reside in a separate file, in our case
prisoners.fsi. The implementation of the interface resides in the file
prisoners.fs.
Note: If you are using Visual Studio to write F# using the Add
In, you must make sure that the .fsi file is closer to the top of the
project than the fs file so that it is compiled first. If you get them
out of order, simply edit the .fsharpp file with Notepad and move the
.fsi file above the .fs file.
The Prisoners Interface
The module begins with a module statement followed by type
statements and value statements. Let's walk through some of the
statements.
module Prisoners
type point = int * int
type points = point list
type strategy = Cooperate | Defect
type behavior =
{
i: strategy;
c: strategy;
d: strategy
}
type behaviors = behavior list
type payoff = (strategy * strategy) -> (int * int)
type cellData =
{
coordinate : point;
value : behavior
}
type grid
The first type is a point:
type point = int * int
This defines a tuple of two integers. The * is a separator between
types. In many texts a tuple is shown as <3, 4>. When you use a
tuple, you always have two numbers, you access them individually as
will be discussed below, but they are inseparable, because they are a
type.
type points = point list
The type points is a list of points; type is a keyword, and list is
a keyword; points is the name of the type, and point is the type
defined above.
F# does not require that you specify types, because the language
supports type inference. This means it can figure out the type at
compile time.
Note: If you are a C# programmer, this is going to drive you
nuts. However, you will eventually realize that this allows you to
write code that can operate on more than one type. The closest thing I
can think of to this in C# is generics. But with generics even though
you can write a class that operates on different types safely, you have
to give the type when you write the code. With F#, the compiler figures
it out.
type strategy = Cooperate | Defect
The strategy type is an enumeration. Like enumerations in C#, a
value can only have the value of one of the choices, in this case
Cooperate or Defect.
type behavior =
{
i: strategy;
c: strategy;
d: strategy
}
type behaviors = behavior list
The type behavior is a record. Records allow you to obtain values in
the record by a name. For example, this record has three items (i, c,
d) of type strategy. I is for the initial strategy, c is the strategy
used if your opponent cooperates on the previous move of the game, and
d is the strategy used if your opponent defects on the previous move of
the game.
type payoff = (strategy * strategy) -> (int * int)
The payoff type is a signature of a function. You can think of this as something like a delegate in C#.
Payoff takes two arguments of type strategy, and it returns two
integers. More specifically, it takes the two arguments as a tuple and
returns two integers as a tuple. You can make functions without the
bracket on the incoming parameters and then there are ways to write
code such that you only apply the function to one argument, then pass
that result around and then apply the final argument later. This is
quite power, but you might find it unnerving at first.
type cellData =
{
coordinate : point;
value : behavior
}
type grid
The final types are the definition of cellData which is a record
with a point and behavior, and the type grid. In the implementation,
grid will have parts. However, they are not defined in the signature to
prevent client code from mucking with the insides of the grid. The
signature defines what the world outside the module can see.
The Prisoners Implementation
Here is the whole of the implementation. I will cover each section
one by one below, so if you feel lost, you can skip to the explanation
afterwards and then come back to the whole code when you have a better
feel for what is going one.
module Prisoners
open List
type point = int * int
type points = point list
type strategy = Cooperate | Defect
type behavior =
{ i: strategy;
c: strategy;
d: strategy }
type behaviors = behavior list
type payoff = (strategy * strategy) -> (int * int)
type cellData =
{
coordinate : point;
value : behavior
}
let alwaysDefect = { i=Defect; c=Defect; d=Defect }
let suspiciousDoormat = { i=Defect; c=Defect; d=Cooperate }
let suspiciousTitForTat = { i=Defect; c=Cooperate; d=Defect }
let suspiciousQuaker = { i=Defect; c=Cooperate; d=Cooperate }
let deceptiveDefector = { i=Cooperate; c=Defect; d=Defect }
let gullibleDoormat = { i=Cooperate; c=Defect; d=Cooperate }
let titForTat = { i=Cooperate; c=Cooperate; d=Defect }
let quaker = { i=Cooperate; c=Cooperate; d=Cooperate }
let behaviors = [| alwaysDefect; suspiciousDoormat; suspiciousTitForTat;
suspiciousQuaker; deceptiveDefector; gullibleDoormat; titForTat; quaker |]
let hobbes (a,b) =
match (a,b) with
(Cooperate, Cooperate) -> (3, 3)
| (Cooperate, Defect) -> (0, 5)
| (Defect, Cooperate) -> (5, 0)
| (Defect, Defect) -> (1, 1)
let chicken (a,b) =
match (a,b) with
(Cooperate, Cooperate) -> (3, 3)
| (Cooperate, Defect) -> (1, 5)
| (Defect, Cooperate) -> (5, 1)
| (Defect, Defect) -> (0, 0)
let stag (a,b) =
match (a,b) with
(Cooperate, Cooperate) -> (5, 5)
| (Cooperate, Defect) -> (0, 3)
| (Defect, Cooperate) -> (3, 0)
| (Defect, Defect) -> (1, 1)
let prev size i = if i = 0 then size-1 else i-1
let next size i = if i = size-1 then 0 else i+1
let neighbours size (i,j) =
[ (prev size i,prev size j); (prev size i,j); (prev size i,next size j);
(i, prev size
j);
(i, next size j);
(next size i,prev size j); (next size i,j); (next size i,next size j)]
type cell =
{ x: int;
y: int;
mutable neighbours: cell array;
mutable score: int;
mutable plan : behavior;
mutable first : bool;
mutable last : strategy;
mutable temp : strategy }
type grid =
{ size: int;
mutable pay: payoff;
cells: cell array array;
mutable changed: cellData list }
let changePay grid pay =
grid.pay <- pay;
grid
let newEmptyGame = { size=0; cells = [| |]; changed = []; pay=hobbes}
let getCell grid (x,y) = grid.cells.(x).(y)
let makeGrid size payoff =
let dummyCell = { x=0; y=0;
neighbours=[| |]; score=0; plan=alwaysDefect; first=true;
last=Cooperate; temp=Cooperate } in
let grid =
{ size = size;
cells = Array.create_matrix size size dummyCell; changed=[]; pay=payoff } in
for i = 0 to size - 1 do
for j = 0 to size - 1 do
grid.cells.(i).(j) <- { x=i; y=j; neighbours=[| |];
score=0; plan=alwaysDefect; first=true; last=Cooperate; temp=Cooperate }
done;
done;
for i = 0 to size - 1 do
for j = 0 to size - 1 do
grid.cells.(i).(j).neighbours <- Array.of_list (map (getCell grid) (neighbours size (i,j)))
done;
done;
grid
let resetGrid grid =
grid.changed <- [];
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
(getCell grid (i,j)).score <- 0
done;
done
let augment grid cellCoordinates behaviors =
resetGrid grid;
begin
let cellBehaviors = List.combine cellCoordinates behaviors in
iter (fun (point, behavior) ->
let c = getCell grid point in
c.plan <- behavior;
grid.changed <- { coordinate=(c.x, c.y); value=c.plan }::grid.changed
) cellBehaviors
end;
grid.changed
let randomGenerator size =
let gen = new System.Random() in
let acc = ref [] in
for i = 0 to size-1 do
for j = 0 to size-1 do
acc:=behaviors.(System.Convert.ToInt32(gen.NextDouble() * 7.0))::(!acc);
done;
done;
Array.of_list !acc
let newRandomGame size payoff =
let grid = makeGrid size payoff in
let plans = randomGenerator size in
let index = ref 0 in
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let c = (getCell grid (i,j)) in
c.plan <- plans.(!index);
index := !index + 1;
grid.changed <- { coordinate=(i, j); value=c.plan }::grid.changed
done;
done;
grid, grid.changed
let cellPayoff (grid,a,b) =
if a.first then
begin
a.first <- false;
a.temp <- a.plan.i;
grid.pay (a.plan.i, b.plan.i)
end
else
let aBehavior = if b.last = Cooperate then a.plan.c else a.plan.d in
let bBehavior = if a.last = Cooperate then b.plan.c else b.plan.d in
begin
a.temp <- aBehavior;
grid.pay (aBehavior, bBehavior)
end
let step grid =
resetGrid grid;
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
let nbs = me.neighbours in
for k = 0 to 7 do
let nb = nbs.(k)in
me.score <- me.score + fst (cellPayoff (grid, me, nb))
done;
done;
done;
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
me.last <- me.temp
done;
done;
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
let nbs = me.neighbours in
let max = ref (-1, -1) in
let score = ref me.score in
for k = 0 to 7 do
let nb = nbs.(k)in
if nb.score > !score then
begin
score := nb.score;
max := (nb.x, nb.y)
end
done;
if fst !max >= 0 then
let c = (getCell grid !max) in
me.plan <- c.plan;
grid.changed <- { coordinate = (i,j); value = me.plan }::grid.changed
done;
done;
grid.changed
Let's disect the code bit by bit:
module Prisoners
open List
type point = int * int
type points = point list
type strategy = Cooperate | Defect
type behavior =
{ i: strategy;
c: strategy;
d: strategy }
type behaviors = behavior list
type payoff = (strategy * strategy) -> (int * int)
type cellData =
{
coordinate : point;
value : behavior
}
We open with a module statement that matches the interface file.
Then we have an open statement so we can use the List module without
having to prefix each use. This is similar to a using statement in C#.
When then define most of the types in the interface. Grid will be defined later.
let alwaysDefect = { i=Defect; c=Defect; d=Defect }
let suspiciousDoormat = { i=Defect; c=Defect; d=Cooperate }
let suspiciousTitForTat = { i=Defect; c=Cooperate; d=Defect }
let suspiciousQuaker = { i=Defect; c=Cooperate; d=Cooperate }
let deceptiveDefector = { i=Cooperate; c=Defect; d=Defect }
let gullibleDoormat = { i=Cooperate; c=Defect; d=Cooperate }
let titForTat = { i=Cooperate; c=Cooperate; d=Defect }
let quaker = { i=Cooperate; c=Cooperate; d=Cooperate }
let behaviors = [| alwaysDefect; suspiciousDoormat; suspiciousTitForTat;
suspiciousQuaker; deceptiveDefector; gullibleDoormat; titForTat; quaker |]
We have defined a record for each strategy. We begin with a let to
tell the compiler we are defining a record, give it a name, and then
set its value. All of these records are of type behavior. Each value is
prefixed with the i/c/d from the type definition. The compiler
automatically figures out that these definitions are the behavior type.
We then create and array called behaviors. Arrays are specified
using [| |]. When you see [ ] in the code, these are lists. Arrays are
mutable, meaning you can modify their value. Lists are immutable. You
can make new lists from existing lists, but you can not modify a list.
Arrays are used for the imperative style of programming, and lists are
used for functional style of programming.
let hobbes (a,b) =
match (a,b) with
(Cooperate, Cooperate) -> (3, 3)
| (Cooperate, Defect) -> (0, 5)
| (Defect, Cooperate) -> (5, 0)
| (Defect, Defect) -> (1, 1)
let chicken (a,b) =
match (a,b) with
(Cooperate, Cooperate) -> (3, 3)
| (Cooperate, Defect) -> (1, 5)
| (Defect, Cooperate) -> (5, 1)
| (Defect, Defect) -> (0, 0)
let stag (a,b) =
match (a,b) with
(Cooperate, Cooperate) -> (5, 5)
| (Cooperate, Defect) -> (0, 3)
| (Defect, Cooperate) -> (3, 0)
| (Defect, Defect) -> (1, 1)
There are three payoffs functions. These functions pass in two
strategies and return a tuple with the score. The score tuple has two
values; the left value is the score for the left strategy, and the
right for the right. For example, the Hobbes strategy says that if both
behaviors are cooperate, then each gets 3 points. If they both defect,
they each get 1.
The method uses pattern matching. Pattern matching
is a bit like a switch in C#, except there are more sophisticated
matching techniques not covered here. When the incoming values match
the parenthesized values, the values to the right of the -> are the
result value.
let prev size i = if i = 0 then size-1 else i-1
let next size i = if i = size-1 then 0 else i+1
let neighbours size (i,j) =
[ (prev size i,prev size j); (prev size i,j); (prev size i,next size j);
(i, prev size
j);
(i, next size j);
(next size i,prev size j); (next size i,j); (next size i,next size j)]
type cell =
{ x: int;
y: int;
mutable neighbours: cell array;
mutable score: int;
mutable plan : behavior;
mutable first : bool;
mutable last : strategy;
mutable temp : strategy }
type grid =
{ size: int;
mutable pay: payoff;
cells: cell array array;
mutable changed: cellData list }
We now have some definitions that set up the core types. The cell
type holds the values for each square on the playing field. The cell
has an x/y coordinate. These are values and are immutable. There are
mutable values for neighbors (the cells on all 8 squares around the
cell), the score (for one round of play), the current behavior (which
will change if the neighbours get more points), a Boolean that is true
if this is the initial play, the last strategy used, and a temporary
strategy used for the algorithm that updates cells.
The grid type
has the size of the playing field, the payoff function that was defined
above, the cells, and a list of changed cells. The payoff contains a
function. This is like using a reference to a delegate in C#. It allows
the user to change the payoff by setting a different payoff scheme. The
arrays is immutable, but remember, the contents of an array are
mutable. The change data is a list which is not mutable, but the list
as a whole is, which means the list can be replaced with a new list.
Let’s look at how pay would be changed:
let changePay grid pay =
grid.pay <- pay;
grid
Change pay takes a grid and payoff arguments and then sets the grids
pay field to the payoff, then gives the same grid as a result. The
syntax for setting a mutable value is:
field <- value
The <- operator means to assign the memory that the field references to the value, just like = does in C#.
let newEmptyGame = { size=0; cells = [| |]; changed = []; pay=hobbes}
This
defines a function that creates and empty game and gives a grid as a
result. Actually, it constructs a grid of size 0, with and empty array
of cells, and an empty list of changes. Notice that the array is
initialized with [| |] and the list with [ ]/
let getCell grid (x,y) = grid.cells.(x).(y)
It is quite common to access each cell in the grid, so here is a
function that takes a grid and a tuple of an x/y coordinate and results
in a cell. We access arrays with dot and parenthesis. Notice we also
use dotting to access fields in the grid type.
let makeGrid size payoff =
let
dummyCell = { x=0; y=0; neighbours=[| |]; score=0; plan=alwaysDefect;
first=true; last=Cooperate; temp=Cooperate } in
// First make all the cells
let grid =
{ size = size;
cells = Array.create_matrix size size dummyCell; changed=[]; pay=payoff } in
for i = 0 to size - 1 do
for j = 0 to size - 1 do
grid.cells.(i).(j) <- { x=i; y=j; neighbours=[| |];
score=0; plan=alwaysDefect; first=true; last=Cooperate; temp=Cooperate }
done;
done;
for i = 0 to size - 1 do
for j = 0 to size - 1 do
grid.cells.(i).(j).neighbours <- Array.of_list (map (getCell grid) (neighbours size (i,j)))
done;
done;
grid
Now we are getting closer to the heart of things. makeGrid takes a
size and payoff record and makes a grid. Look at the initial structure:
let ... in
let ... in
for ... to ... do
done
We are writing imperative code here, and the nested let/in
statements will ensure that the definitions are evaluated in the order
they are written. Functional code does not control order of evaluation,
because it does not matter. But imperative code (code with side
effects), it matters. So you have to pay close attention and make sure
that your code is written in a way that controls order of evaluation
when it matters.
In this case the first statement makes a dummyCell, and the second
one makes a grid using the dummy cell. Because the second let statement
is in the first statement, when the second is evaluated, it is assured
that the first let is evaluated first.
If you use a definition like:
let ...
and ... in
all the definitions are simultaneous and the order of evaluation is
not specified. For pure functional code, this does not matter because
there are no side effects of the code because we are dealing with
values and there is no state modification, but to do this with
imperative code will cause unpredictable results in many cases.
for i = 0 to size - 1 do
for j = 0 to size - 1 do
grid.cells.(i).(j).neighbours <- Array.of_list (map (getCell grid) (neighbours size (i,j)))
done;
Here is something new. We are looping through the cells by an i/j
coordinate in the grid and changing the value of neighbours using some
unusual operations with Array and List. The neighbours function
evaluates to a list. The map function is really List.map. We can use
map directly because of the open List statement at the top of the
module file. The map function says to apply the first argument to each
element in the second argument and then return a new list. The second
argument of course is a list. Let's break this down more.
(neighbours size (i,j))
This statement says evaluate neighbours with size and the tuple (i,j), which evaluates to a list.
(getCell grid)
This statement says evaluate getCell with a grid, however the
definition of grid also includes a tuple (i,j). Just what is going on
here? Well, functions can be partially evaluated. Since the second
argument was not given, then the result is a function that requires the
tuple (i,j) to complete evaluation. For the C# programmers, I know what
you are thinking; yuck. But wait, map applies this function to each
element in the list created by neighbours, which evaluates to a list of
(i,j) tuples, just what the new function requires to evaluate. Partial
evaluation combined with map allowed us to make these functions work
together with ease. The final statement:
Array.of_list
turns that list into an array so it can set the cell's neighbors.
The map function is doing something functional, and the assignment of
the array is doing something imperative. The Array.of_list is bridging
the gap between functional and imperative programming.
Let's fast forward a bit because I think you can now figure out some of this.
let cellPayoff (grid,a,b) =
if a.first then
begin
a.first <- false;
a.temp <- a.plan.i;
grid.pay (a.plan.i, b.plan.i)
end
else
let aBehavior = if b.last = Cooperate then a.plan.c else a.plan.d in
let bBehavior = if a.last = Cooperate then b.plan.c else b.plan.d in
begin
a.temp <- aBehavior;
grid.pay (aBehavior, bBehavior)
end
This function performs the payoff calculation. The conditional
determines if this is the first play of the game, and if so uses the i:
of the behavior record. The second part of the conditional does the
real work. It compares the current strategy of the cell with the past
strategy of an opponent and calculates the pay off. Notice this line:
grid.pay (aBehavior, bBehavior)
grid.pay is a function, sort of like a delegate reference in C#, and
it is evaluated by passing a tuple of behaviors. The pay field is
mutable, so this allows us to change the definition of pay dynamically
at run time. You will see later that the user can determine the payoff
structure in the GUI and this is the mutable field that is changed.
let step grid =
resetGrid grid;
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
let nbs = me.neighbours in
for k = 0 to 7 do
let nb = nbs.(k)in
me.score <- me.score + fst (cellPayoff (grid, me, nb))
done;
done;
done;
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
me.last <- me.temp
done;
done;
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
let nbs = me.neighbours in
let max = ref (-1, -1) in
let score = ref me.score in
for k = 0 to 7 do
let nb = nbs.(k)in
if nb.score > !score then
begin
score := nb.score;
max := (nb.x, nb.y)
end
done;
if fst !max >= 0 then
let c = (getCell grid !max) in
me.plan <- c.plan;
grid.changed <- { coordinate = (i,j); value = me.plan }::grid.changed
done;
done;
grid.changed
We are now down the final function which evaluates one step in the
game. This will be called in a loop to make the game progress. The form
of the definition is:
let ... in
... ;
... ;
... ;
...
which is implicitly a sequence of statements that are guaranteed to
evaluate in the order given. Let's take each item one by one.
resetGrid grid;
This resets the score of each cell by setting it to zero.
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
let nbs = me.neighbours in
for k = 0 to 7 do
let nb = nbs.(k)in
me.score <- me.score + fst (cellPayoff (grid, me, nb))
done;
done;
This loop gets each cell one by one and then gets the neighbour and
calculates the payoff. The cellPayoff function takes a grid, the
current cell, and the neighbour cell, and returns a tuple. The fst
function gets the first integer in the tuple. You can get the second
tuple with snd.
We then set the score in the current cell using the <- operate which assigns a mutable value.
for i = 0 to grid.size - 1 do
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
me.last <- me.temp
done;
done;
Now we loop through each cell and set the temp value to last. Temp
was set during payoff calculation. The reason for the two step process
is the payoff calculation knows what behavior was used (i, c, or d) and
saves it. But, we can't use it until all scoring is done, because last
is used when comparing our behavior to our neighbours past behavior.
for j = 0 to grid.size - 1 do
let me = (getCell grid (i,j)) in
let nbs = me.neighbours in
let max = ref (-1, -1) in
let score = ref me.score in
for k = 0 to 7 do
let nb = nbs.(k)in
if nb.score > !score then
begin
score := nb.score;
max := (nb.x, nb.y)
end
done;
if fst !max >= 0 then
let c = (getCell grid !max) in
me.plan <- c.plan;
grid.changed <- { coordinate = (i,j); value = me.plan }::grid.changed
done;
done;
The last loop looks for the largest neighbour score and switches to
that strategy. A couple of things to note. We are using a reference
value.
let score = ref me.score in
Reference values are mutable. You refer to their value by placing a ! in front of its name and you assign with :=.
score := nb.score;
...
if fst !max >= 0 then
The last piece is:
grid.changed
which returns the list of points and behaviors that changed. These will eventually go to the GUI for screen update.
The Engine Implementation
The engine is a statemachine running in a background thread. It
recieves signals from the client and notifies the client about changes
in its state.
module Engine
module Array = Microsoft.FSharp.Compatibility.CompatArray
open System.Threading
type IEngineControl =
interface
abstract Start: unit -> unit;
abstract NewStrategiesReady: AutoResetEvent;
abstract NewPayoffReady: AutoResetEvent;
abstract RunSignal: AutoResetEvent;
abstract ExitSignal: AutoResetEvent;
abstract StopSignal: AutoResetEvent;
abstract StepSignal: AutoResetEvent;
abstract ResetSignal: AutoResetEvent
end
back from the engine.
type IEngineCallbacks =
interface
abstract NotifyUpdates: Prisoners.cellData list -> unit
abstract NotifyFinishedEarly: unit -> unit
abstract CollectStrategies: unit -> Prisoners.points * Prisoners.behaviors
abstract CollectPayoff: unit -> Prisoners.payoff
end
type 'a state = ('a -> unit)
let PeekForOne (xs : (AutoResetEvent * 'a state) list)
(otherwise : 'a state)
(s : 'a) =
let waithandles = Array.of_list (List.map (fun x -> (fst x :> WaitHandle)) xs) in
let actions = Array.of_list (List.map snd xs) in
let i = WaitHandle.WaitAny(waithandles,0,false) in
if i = WaitHandle.WaitTimeout then
otherwise s
else
actions.(i) s
let WaitForOne (xs : (AutoResetEvent * 'a state) list)
(s : 'a) =
let waithandles = Array.of_list (List.map (fun x -> (fst x :> WaitHandle)) xs) in
let actions = Array.of_list (List.map snd xs) in
let i = WaitHandle.WaitAny(waithandles) in
actions.(i) s
let mkEngine (size:int) (callbacks : #IEngineCallbacks) =
/// These are the events used to control the engine
let exitSignal = new AutoResetEvent(false) in
let runSignal = new AutoResetEvent(false) in
let stopSignal = new AutoResetEvent(false) in
let stepSignal = new AutoResetEvent(false) in
let resetSignal = new AutoResetEvent(false) in
let newStrategiesReadySignal = new AutoResetEvent(false) in
let newPayoffReadySignal = new AutoResetEvent(false) in
let pay = ref Prisoners.hobbes in
let OneStep(s) =
let data = Prisoners.step(s) in
callbacks.NotifyUpdates(data);
s, (data <> []) in
let ResetGame(s) =
let s,changed = Prisoners.newRandomGame size !pay in
callbacks.NotifyUpdates(changed);
s in
let CollectStrategies(s) =
let userPoints, userBehavior = callbacks.CollectStrategies() in
let data = Prisoners.augment s userPoints userBehavior in
callbacks.NotifyUpdates(data);
s in
let CollectPayoff(s) =
let p = callbacks.CollectPayoff() in
let s = Prisoners.changePay s p in
pay := p;
s in
let rec StartRun(s) =
let s = ResetGame(s) in
Running(s)
and StartPause(s) =
let s = ResetGame(s) in
Paused(s)
and Running(s) =
PeekForOne
[ (stopSignal, Paused);
(stepSignal, Running);
(runSignal, Running);
(resetSignal, StartRun);
(newStrategiesReadySignal, CollectStrategiesAndRun);
(newPayoffReadySignal, CollectPayoffAndRun);
(exitSignal, Finish) ]
StepRun // otherwise go to this state
s
and CollectStrategiesAndRun(s) =
let s = CollectStrategies(s) in
Running(s)
and CollectPayoffAndRun(s) =
let s = CollectPayoff(s) in
Running(s)
and StepRun(s) =
let s,cont = OneStep(s) in
if cont then SleepThenRun(s)
else FinishEarly(s)
and SleepThenRun(s) =
ignore(Thread.Sleep(20));
Running(s)
and Paused(s) =
WaitForOne
[ (stopSignal, Paused);
(stepSignal, StepPause);
(runSignal, Running);
(resetSignal, StartPause);
(newStrategiesReadySignal, CollectStrategiesAndPause);
(newPayoffReadySignal, CollectPayoffAndPause);
(exitSignal,Finish) ]
s
and CollectStrategiesAndPause(s) =
let s = CollectStrategies(s) in
Paused(s)
and CollectPayoffAndPause(s) =
let s = CollectPayoff(s) in
Paused(s)
and StepPause(s) =
let s,cont = OneStep(s) in
if cont then Paused(s)
else FinishEarly(s)
and FinishEarly(s) =
callbacks.NotifyFinishedEarly();
Paused(s)
and Finish(s) = () in
let start() = StartRun(Prisoners.newEmptyGame) in
{ new IEngineControl
with get_RunSignal() = runSignal;
and get_StopSignal() = stopSignal;
and get_ExitSignal() = exitSignal;
and get_StepSignal() = stepSignal;
and get_ResetSignal() = resetSignal;
and Start() = start();
and get_NewStrategiesReady() = newStrategiesReadySignal;
and get_NewPayoffReady() = newPayoffReadySignal; }
Let's first work through the interfaces that define the interaction. The first interface is for controlling the engine.
type IEngineControl =
interface
abstract Start: unit -> unit;
abstract NewStrategiesReady: AutoResetEvent;
abstract NewPayoffReady: AutoResetEvent;
abstract RunSignal: AutoResetEvent;
abstract ExitSignal: AutoResetEvent;
abstract StopSignal: AutoResetEvent;
abstract StepSignal: AutoResetEvent;
abstract ResetSignal: AutoResetEvent
end
This interface defines a set of events that will be sent to the
engine thread. Start will start the engines operation.
NewStrategiesReady and NewPayoffReady tell the engine to ask the client
for information and apply it. All the other signals should be obvious
in their meaning.
type IEngineCallbacks =
interface
abstract NotifyUpdates: Prisoners.cellData list -> unit
abstract NotifyFinishedEarly: unit -> unit
abstract CollectStrategies: unit -> Prisoners.points * Prisoners.behaviors
abstract CollectPayoff: unit -> Prisoners.payoff
end
The callback interface is implemented by a controller and passed to
the engine. NotifyUpdates sends the controller a list of cell update
infomation. NotifyFinishedEarly tells the controller the game is over.
The collect functions ask for information after the controller notifies
the engine there is information to collect.
type 'a state = ('a -> unit)
Now we encounter something very different: type variables. In this
declaration the name of the type is state. The type variables are to
the left of the name and must have a preceding apostrphe, in this case
'a. The type variable 'a represents some type that will be determined
by the compile based on its use. Type variables allows you to write
functions and types that are type independent.
For example, map is defined as:
type ('a, 'b) map = ('a -> 'b) -> 'a list -> 'b list
Which says we have a new type called map that defines a relationship
between a function and a list and produces a list, where two types 'a
and 'b participate. So we have 'a and 'b listed right after type and
used in the definition after the =. The definition says given a
function that takes 'a and returns 'b, and a list of 'a, produce a list
of 'b. 'a and 'b can be anything.
type 'a state = ('a -> unit)
So back to our state. It says that state is any function that takes
an 'a and produces a unit, which is nothing. We are going to use this
later on to build the state machine, so just hold on.
let PeekForOne (xs : (AutoResetEvent * 'a state) list)
(otherwise : 'a state)
(s : 'a) =
let waithandles = Array.of_list (List.map (fun x -> (fst x :> WaitHandle)) xs) in
let actions = Array.of_list (List.map snd xs) in
let i = WaitHandle.WaitAny(waithandles,0,false) in
if i = WaitHandle.WaitTimeout then
otherwise s
else
actions.(i) s
let WaitForOne (xs : (AutoResetEvent * 'a state) list)
(s : 'a) =
let waithandles = Array.of_list (List.map (fun x -> (fst x :> WaitHandle)) xs) in
let actions = Array.of_list (List.map snd xs) in
let i = WaitHandle.WaitAny(waithandles) in
actions.(i) s
These two functions are our first use of state. Both take a list of
event/state tuples. The event/state tuple represents an event to wait
for, and a state/function to go/call to when the event is processed.
PeekForOne has a timeout, so it also takes an otherwise state. Both
functions also take a grid, which is what is passed around the state
machine when going from state to state.
Now let's take a look at the state machine:
let makeEngine (size:int) (callbacks : #IEngineCallbacks) =
let exitSignal = new AutoResetEvent(false) in
let runSignal = new AutoResetEvent(false) in
let stopSignal = new AutoResetEvent(false) in
let stepSignal = new AutoResetEvent(false) in
let resetSignal = new AutoResetEvent(false) in
let newStrategiesReadySignal = new AutoResetEvent(false) in
let newPayoffReadySignal = new AutoResetEvent(false) in
let pay = ref Prisoners.hobbes in
let OneStep(s) =
let data = Prisoners.step(s) in
callbacks.NotifyUpdates(data);
s, (data <> []) in
let ResetGame(s) =
let s,changed = Prisoners.newRandomGame size !pay in
callbacks.NotifyUpdates(changed);
s in
let CollectStrategies(s) =
let userPoints, userBehavior = callbacks.CollectStrategies() in
let data = Prisoners.augment s userPoints userBehavior in
callbacks.NotifyUpdates(data);
s in
let CollectPayoff(s) =
let p = callbacks.CollectPayoff() in
let s = Prisoners.changePay s p in
pay := p;
s in
let rec StartRun(s) =
let s = ResetGame(s) in
Running(s)
and StartPause(s) =
let s = ResetGame(s) in
Paused(s)
and Running(s) =
PeekForOne
[ (stopSignal, Paused);
(stepSignal, Running);
(runSignal, Running);
(resetSignal, StartRun);
(newStrategiesReadySignal, CollectStrategiesAndRun);
(newPayoffReadySignal, CollectPayoffAndRun);
(exitSignal, Finish) ]
StepRun // otherwise go to this state
s
and CollectStrategiesAndRun(s) =
let s = CollectStrategies(s) in
Running(s)
and CollectPayoffAndRun(s) =
let s = CollectPayoff(s) in
Running(s)
and StepRun(s) =
let s,cont = OneStep(s) in
if cont then SleepThenRun(s)
else FinishEarly(s)
and SleepThenRun(s) =
ignore(Thread.Sleep(20));
Running(s)
and Paused(s) =
WaitForOne
[ (stopSignal, Paused);
(stepSignal, StepPause);
(runSignal, Running);
(resetSignal, StartPause);
(newStrategiesReadySignal, CollectStrategiesAndPause);
(newPayoffReadySignal, CollectPayoffAndPause);
(exitSignal,Finish) ]
s
and CollectStrategiesAndPause(s) =
let s = CollectStrategies(s) in
Paused(s)
and CollectPayoffAndPause(s) =
let s = CollectPayoff(s) in
Paused(s)
and StepPause(s) =
let s,cont = OneStep(s) in
if cont then Paused(s)
else FinishEarly(s)
and FinishEarly(s) =
callbacks.NotifyFinishedEarly();
Paused(s)
and Finish(s) = () in
let start() = StartRun(Prisoners.newEmptyGame) in
of a engine automata
{ new IEngineControl
with get_RunSignal() = runSignal;
and get_StopSignal() = stopSignal;
and get_ExitSignal() = exitSignal;
and get_StepSignal() = stepSignal;
and get_ResetSignal() = resetSignal;
and Start() = start();
and get_NewStrategiesReady() = newStrategiesReadySignal;
and get_NewPayoffReady() = newPayoffReadySignal; }
The makeEngine function defines the statemachine.
let makeEngine (size:int) (callbacks : #IEngineCallbacks) =
let exitSignal = new AutoResetEvent(false) in
let runSignal = new AutoResetEvent(false) in
let stopSignal = new AutoResetEvent(false) in
let stepSignal = new AutoResetEvent(false) in
let resetSignal = new AutoResetEvent(false) in
let newStrategiesReadySignal = new AutoResetEvent(false) in
let newPayoffReadySignal = new AutoResetEvent(false) in
let pay = ref Prisoners.hobbes in
The makeEngine function takes a size and a callback reference. It
then defines a set of signals that will recieve events from the
controllers, followed by a reference to the payoff type.
let OneStep(s) =
let data = Prisoners.step(s) in
callbacks.NotifyUpdates(data);
s, (data <> []) in
let ResetGame(s) =
let s,changed = Prisoners.newRandomGame size !pay in
callbacks.NotifyUpdates(changed);
s in
let CollectStrategies(s) =
let userPoints, userBehavior = callbacks.CollectStrategies() in
let data = Prisoners.augment s userPoints userBehavior in
callbacks.NotifyUpdates(data);
s in
let CollectPayoff(s) =
let p = callbacks.CollectPayoff() in
let s = Prisoners.changePay s p in
pay := p;
s in
We then have some utility functions for the state machine to call.
The first three functions perform some action and then make a call to
callbacks. This is how the state machine will communicate with the
controller.
let rec StartRun(s) =
let s = ResetGame(s) in
Running(s)
and StartPause(s) =
let s = ResetGame(s) in
Paused(s)
and Running(s) =
PeekForOne
[ (stopSignal, Paused);
(stepSignal, Running);
(runSignal, Running);
(resetSignal, StartRun);
(newStrategiesReadySignal, CollectStrategiesAndRun);
(newPayoffReadySignal, CollectPayoffAndRun);
(exitSignal, Finish) ]
StepRun // otherwise go to this state
s
and CollectStrategiesAndRun(s) =
let s = CollectStrategies(s) in
Running(s)
and CollectPayoffAndRun(s) =
let s = CollectPayoff(s) in
Running(s)
and StepRun(s) =
let s,cont = OneStep(s) in
if cont then SleepThenRun(s)
else FinishEarly(s)
and SleepThenRun(s) =
ignore(Thread.Sleep(20));
Running(s)
and Paused(s) =
WaitForOne
[ (stopSignal, Paused);
(stepSignal, StepPause);
(runSignal, Running);
(resetSignal, StartPause);
(newStrategiesReadySignal, CollectStrategiesAndPause);
(newPayoffReadySignal, CollectPayoffAndPause);
(exitSignal,Finish) ]
s
and CollectStrategiesAndPause(s) =
let s = CollectStrategies(s) in
Paused(s)
and CollectPayoffAndPause(s) =
let s = CollectPayoff(s) in
Paused(s)
and StepPause(s) =
let s,cont = OneStep(s) in
if cont then Paused(s)
else FinishEarly(s)
and FinishEarly(s) =
callbacks.NotifyFinishedEarly();
Paused(s)
and Finish(s) = () in
Now we have the state machine itself. Notice the defintion begins:
let rec
The rec means the definition is recursive; that these functions can
all call each other. Each function performs an action and then calls
another function. Each function acts as a state.
and Running(s) =
PeekForOne
[ (stopSignal, Paused);
(stepSignal, Running);
(runSignal, Running);
(resetSignal, StartRun);
(newStrategiesReadySignal, CollectStrategiesAndRun);
(newPayoffReadySignal, CollectPayoffAndRun);
(exitSignal, Finish) ]
StepRun // otherwise go to this state
s
The controller interacts with the state machine by sending signals.
The state machine calls Peek or WaitForOne, which halts execution until
a signal is sent. These functions take a list of signals and functions,
and the functions are states in the state machine. This means the
controller controls what the next state the machine changes to.
let start() = StartRun(Prisoners.newEmptyGame) in
{ new IEngineControl
with get_RunSignal() = runSignal;
and get_StopSignal() = stopSignal;
and get_ExitSignal() = exitSignal;
and get_StepSignal() = stepSignal;
and get_ResetSignal() = resetSignal;
and Start() = start();
and get_NewStrategiesReady() = newStrategiesReadySignal;
and get_NewPayoffReady() = newPayoffReadySignal; }
We provide a start function to start the state machine, and define
the IEngineControl interface implementation. The controller will call
makeEngine and then call start() to get the engine going.
The Controller Implementation
The controller is a class that is intended for use by C#. It creates
the engine, fires off a thread to run the engine, and then waits for
calls from the GUI.
module EngineControl
module Array = Microsoft.FSharp.Compatibility.CompatArray
open System.Threading
open Prisoners
open Engine
type ScreenPoint =
class
val x : int
val y : int
val b : Prisoners.behavior
new (x, y, b) as this = { x=x; y=y; b=b }
member this.X = this.x
member this.Y = this.y
member this.Behavior = this.b
end
type payoff = Hobbes | Chicken | Stag
calls from us.
type IScreenCallbacks =
interface
abstract FinishedEarly : unit -> unit;
abstract NotifyUpdates : ScreenPoint array -> unit;
abstract CollectStrategies : unit -> ScreenPoint array;
abstract CollectPayoff: unit -> payoff
end
type PrisonersEngineControl =
class
val mutable size : int
val engine : IEngineControl
val thread : Thread
val callback : IScreenCallbacks
new (size, callback) as this = {
size=size;
engine = makeEngine size
{ new IEngineCallbacks
with NotifyUpdates(data) = this.engineNotifyUpdates (data);
and NotifyFinishedEarly() = this.engineFinishedEarly();
and CollectStrategies() = this.engineCollectStrategies()
and CollectPayoff() = this.engineCollectPayoff()
};
thread = new Thread(fun () -> this.engine.Start()); callback =
callback
}
then this.thread.IsBackground <- true;
this.thread.Priority <- ThreadPriority.Lowest
member this.engineFinishedEarly () = this.callback.FinishedEarly()
member this.engineNotifyUpdates (data) =
this.callback.NotifyUpdates(Array.of_list (List.map (fun (d : cellData)
-> new ScreenPoint(fst d.coordinate, snd d.coordinate, d.value))
data))
member this.engineCollectStrategies() =
let userInput = this.callback.CollectStrategies() in
List.map (fun (p : ScreenPoint) -> (p.X, p.Y)) (List.of_array
(userInput)),
List.map (fun (p : ScreenPoint) -> p.Behavior) (List.of_array
(userInput))
member this.engineCollectPayoff() =
let userInput = this.callback.CollectPayoff() in
match userInput with
(Hobbes) -> Prisoners.hobbes
| (Chicken) -> Prisoners.chicken
| (Stag) -> Prisoners.stag
member this.Size = this.size
member this.Start() = this.thread.Start();
member this.StrategiesReady() = this.engine.NewStrategiesReady.Set()
member this.PayoffReady() = this.engine.NewPayoffReady.Set()
member this.Run() = this.engine.RunSignal.Set()
member this.Exit() = this.engine.ExitSignal.Set()
member this.Stop() = this.engine.StopSignal.Set()
member this.Step() = this.engine.StepSignal.Set()
member this.Reset() = this.engine.ResetSignal.Set()
end
We begin with a class that is used to pass point data back and forth
with. ScreenPoint contains a coordinate and behavior. When the
controller send points to the GUI for screen update, this class is
used. When the GUI sends points to the controller to change behaviors,
this class is also used.
type ScreenPoint =
class
val x : int
val y : int
val b : Prisoners.behavior
new (x, y, b) as this = { x=x; y=y; b=b }
member this.X = this.x
member this.Y = this.y
member this.Behavior = this.b
end
Notice that there are internal values x and y, and members. Members
act like getter properties. There is also a constructor called new.
type payoff = Hobbes | Chicken | Stag
type IScreenCallbacks =
interface
abstract FinishedEarly : unit -> unit;
abstract NotifyUpdates : ScreenPoint array -> unit;
abstract CollectStrategies : unit -> ScreenPoint array;
abstract CollectPayoff: unit -> payoff
end
There is an interface for the C# code to implement to take calls
from the client. Notice that there is a payoff type that is an enum. We
also use that point class. The basic idea is to avoid tuples and lists
so that the C# code is more natural. If we used tuples, then the C#
programmer would have to write more code to decode them.
type PrisonersEngineControl =
class
val mutable size : int
val engine : IEngineControl
val thread : Thread
val callback : IScreenCallbacks
The final piece is the class the C# GUI will instance and call to
run the game. It defines 4 values: size, a engine control interface for
talking to the engine, a thread to run the engine in, and callbacks for
C#.
new (size, callback) as this = {
size=size;
engine = makeEngine size
{ new IEngineCallbacks
with NotifyUpdates(data) = this.engineNotifyUpdates (data);
and NotifyFinishedEarly() = this.engineFinishedEarly();
and CollectStrategies() = this.engineCollectStrategies()
and CollectPayoff() = this.engineCollectPayoff()
};
thread = new Thread(fun () -> this.engine.Start()); callback =
callback
}
then this.thread.IsBackground <- true;
this.thread.Priority <- ThreadPriority.Lowest
The constructor takes a size and callback from C#. It then calls
makeEngine and passes an implementation of IEngineCallbacks that binds
members of this class to the interface. It then creates the thread and
sets it to background, passing the engine.Start() function to the
thread. The thread class will get created here, but will not run yet.
member this.engineFinishedEarly () = this.callback.FinishedEarly()
member this.engineNotifyUpdates (data) =
this.callback.NotifyUpdates(Array.of_list (List.map (fun (d : cellData)
-> new ScreenPoint(fst d.coordinate, snd d.coordinate, d.value))
data))
member this.engineCollectStrategies() =
let userInput = this.callback.CollectStrategies() in
List.map (fun (p : ScreenPoint) -> (p.X, p.Y)) (List.of_array
(userInput)),
List.map (fun (p : ScreenPoint) -> p.Behavior) (List.of_array
(userInput))
member this.engineCollectPayoff() =
let userInput = this.callback.CollectPayoff() in
match userInput with
(Hobbes) -> Prisoners.hobbes
| (Chicken) -> Prisoners.chicken
| (Stag) -> Prisoners.stag
The callback functions call the GUI callbacks and then return the
information to the engine. This code translates from ScreenPoint class
which was designed to make life good for C# land, and change them to
data types used by the engine. For example, engineCollectStrategies
convers from ScreenPoint to tuples.
member this.StrategiesReady() = this.engine.NewStrategiesReady.Set()
member this.PayoffReady() = this.engine.NewPayoffReady.Set()
member this.Run() = this.engine.RunSignal.Set()
member this.Exit() = this.engine.ExitSignal.Set()
member this.Stop() = this.engine.StopSignal.Set()
member this.Step() = this.engine.StepSignal.Set()
member this.Reset() = this.engine.ResetSignal.Set()
Finally, we have member functions that fire the signals to the engine. And most importantly:
member this.Start() = this.thread.Start();
the member function that starts the engine by starting the thread.
Implementing the GUI
The GUI is implemented in C#. There is a pixel grid and menu bar.
Here is a snapshot after dropping a large Tit For Tat blue square in
the middle of the game and watching what happens:
I will not go through all the GUI code, but just some snippets. You can down load the source to get all the details.
public partial class PrisonersDilemmaApp : Form, EngineControl.IScreenCallbacks
{
private const int size = 128;
private EngineControl.PrisonersEngineControl control;
...
private void LoadForm(object sender, EventArgs e)
{
RunMenuItem.Enabled = false;
StepMenuItem.Enabled = false;
control = new EngineControl.PrisonersEngineControl(size, this);
bitmap = new Bitmap(size, size, PixelFormat.Format24bppRgb);
control.Start();
}
When the form loads, it enables the proper menus, and creates an
engine control with the size. It also passes itself, because it
implements the screen callbacks. This allows the GUI to make calls on
control and get calls back via the callbacks. It also creates a bit map
that will be displayed in the user interface.
public void NotifyUpdates(EngineControl.ScreenPoint[] points)
{
lock (bitmap)
{
UpdatePixels(points);
}
this.Invoke(new DoUpdateDelegate(DoUpdate));
}
private delegate void DoUpdateDelegate();
private void DoUpdate()
{
this.Invalidate();
}
private void UpdatePixels(EngineControl.ScreenPoint[] points)
{
foreach (EngineControl.ScreenPoint point in points)
{
bitmap.SetPixel(point.X, point.Y, GetColor(point.Behavior));
}
}
Here is one of the callbacks NotifyUpdates. The controller calls
this with a list of points that require updating. The callback first
takes a lock on the bit map to make sure we are never painting while
the bit map is being updated. A private update is called that updates
the bit mape. Then, we then use Invoke because the calling thread is
from the engine and is not the GUI thread. If this were not done, we
would get occasional strange GUI behavior or an exception. The invoke
calls Invalidate to force a repaint.
private void FormPaint(object sender, PaintEventArgs e)
{
lock (bitmap)
{
Rectangle region = new Rectangle(0, 0, size, size);
Rectangle cliprect = this.ClientRectangle;
e.Graphics.DrawImage(bitmap, cliprect, region, GraphicsUnit.Pixel);
}
}
Paint takes a lock on bit map so the GUI thread that called can not
copy the bit map while the engine is updating it. It then copies the
bit map to the screen, stretching the bit map to fit.
The remainder of the code manages colors and menus, and sends user input to the controller. See the source code for the details.
Wrapping Up
F# is a powerful language, but for C# programmers, it is a challenge
to learn. My suggestion is to first learn to use F# as an imperative
language and write code that is called from C# like this example and
master the syntax. Once you are over the syntax hurdle and have some
confidence, you need to move into some functional programming. The
functional style is where the real value is. If all you want is
imperative code, you might as well stick with C#. The imperative style
in F# gives you the bridge to the functional code. You could go
straight for functional programming, and by all means do so if you
desire, but I think the transition is easier if you walk the imperative
path through F# first so you get a handle on the type system and syntax
structure first, before dealing with the change in paradigm and problem
solving style that must follow.
I hope walking you though this example helped give you a feel for F#
and gives you the confidence you can tackle it. The road is a bit
bumpy, the the rewards are worth it.
Good Luck!