Introduction
This is a two state Turing machine written in fsharp inspired by
Langton' Ant pattern, I'm glad to share my work and walk you through the sample,
and discuss about the fsharp language constructs
Background
There were three rules and are as simple as this,
The ant makes one move at a time, on moving flips the color of the tile.
While moving from White tile, moves to its right.
While moving from Black tile, move to its left.<o:p>
Black and white screen wasn’t exciting and I’ve changed my mind at the
last moment, and tiles are replaced with flowers, therefore the ant with a bug.
(You know what? you have this bug in your ‘Clip Board’, It took me hours to
locate it.)
Foreword:
I’ve been practicing fsharp for a while, and this work is to
engage myself this weekend, further this post discusses the language constructs
utilized than the work itself. Please feel free to correct me on any ‘beginners’
mistakes’ I may have here.
Fun Begins here
I would like to take you through a classic ‘Hello world’ C Sharp
example and compare it with fsharp version of it to show you why fsharp is fun
and how fsharp makes the difference.
|
// fsharp
<o:p>
open
System<o:p>
let
msg = "Hello World!"<o:p>
Console.WriteLine
msg<o:p>
|
// CSharp
<o:p>
using
System;<o:p>
namespace
HelloWorld<o:p>
{<o:p>
class Program<o:p>
{<o:p>
private static String msg = "Hello World!";<o:p>
static void Main(string[] args)<o:p>
{<o:p>
Console.WriteLine(msg);<o:p>
}<o:p>
}
<o:p>
}<o:p>
|
You know the difference and it doesn’t need any explanation,
programming has never been this easier and cleaner.
Using let:
First and important thing to learn in fsharp is the ‘let’ bindings.
Keyword ‘let’ is used to bind a value or an object to an identifier, and
therefore the reference is available for access all over the program. Same
identifier can be used within a child block and is available within the current
context and out scopes the identifier from the parent context.
|
> let index =
0;;<o:p>
val index : int = 0
<o:p>
|
All the code presented here are written and manipulated within fsharp
Interactive window (FSI) you could think of this as interactive window in
vs2010, and the end of any block must be terminated with ‘;;’ for the FSI to
evaluate the value of the block, however it is not necessary to terminate a
statement or a line with ‘;’ in fsharp.
Note there is no type specified in index declaration and FSI infers index
as a value and of type int. and by default every identifier in fsharp is
immutable meaning - once binded the value cannot be changed. If a value is
assigned to an immutable identifier compiler will throw an error, and that’s why
it wasn’t called a variable.
|
> index <-
5;;<o:p>
index <-
5;;<o:p>
^^^^^^^^^^<o:p>
stdin(3,1): error FS0027: This value is not
mutable
<o:p>
|
In most cases of our day today programming we have variables and objects
changing their state. To modify the value of an identifier it must be explicitly
marked as mutable, and the compiler will be happy to assign a value for mutable
identifier.
|
> let mutable pointer
= 0;;<o:p>
val mutable pointer :
int = 0<o:p>
|
To bind a value equality (=) operator has to be used, and use assignment
operator ( <- ) to assign a value to an identifier.
|
> let mutable pointer
= 0<o:p>
pointer <- 5<o:p>
val mutable pointer :
int = 5<o:p>
|
Functions:
Function declaration is same as of identifiers, and they take arguments
to operate on. fsharp supports partial application of functions and function
currying; therefore partial functions can be used as first class arguments. This
is more powerful way to write better code and be productive. Let’s declare a
simple function that takes an input ‘x’ and increment the value by one.
|
> let increment x = x
+ 1;;<o:p>
val increment : int -
> int<o:p>
|
Did you see that? The type of the argument and the return type are
mentioned nowhere. Compiler infers the type of argument as integer, how is it
done? The answer would be that the function body adds 1 an integer to x, so the
probability of x being an integer is more so it marks the type of x as integer.
By default the last statement of a block or a function is evaluated to be the
value of the block and its type as the return type. Since our function body
evaluates to an integer and is the last line of the block so the return type is
an integer.
Let’s make a difference to the code and see how the types are
inferred,
|
> let increment x = x
+ 1.0;;<o:p>
val increment : float -
> float<o:p>
|
Now the function body adds a floating point number to x, so does the type
of the argument and return type is a floating point number. FSI’s notion of
increment is that it takes a float and results (->) in a float (float ->
float).
Given that let’s see how partial application is possible. Here is a
function that takes two arguments multiplies them and returns the result.
|
> let multiply x y =
x * y;;<o:p>
val multiply
: int -> int -> int<o:p>
|
Let’s take a closure look at the FSI’s notion of multiply function, it
takes a function (int -> int) as an argument and results in an integer,
(int -> int) -> int
And it is safe to do the following, multiply function is partially
applied with 2 and is available as double, Does it makes sense?
|
> let double =
multiply 2;;<o:p>
val double : (int ->
int)<o:p>
> double 5;;<o:p>
val it : int = 10<o:p>
|
Our case simple it just takes a tile, changes its state and returns
nothing. Note the argument type is explicitly specified within parens, and if no
parens were used it marks the return type of the function.
|
> let flipTile
(tile:Tile) = tile.State <- State.Black;;<o:p>
val flipTile : Tile -
> unit<o:p>
|
Pattern matching is a powerful way to do decision making, controlling the
execution flow and do much more than that. There are different ways to match
different types, but for our need it is the simplest.
The current state of a tile is known and have to predict the next move,
We will discuss about the types later in this post, for now think of the State
and Move as Enum.
|
> let getNextMove
(currentState:State) =<o:p>
match
currentState with<o:p>
|
White -> Right<o:p>
| _
-> Left;;<o:p>
val getNextMove : State
-> Move<o:p>
|
It is more like if then else / case statement in our case, if it matches
State.White then returns Move.Right or else Move.Left but remember there is much
more.
There is a different way of doing this which makes our life easier. Note
the FSI’s notion remains the same.
|
> let getNextMove =
function<o:p>
|
White -> Right<o:p>
| _
-> Left;;<o:p>
val getNextMove : State
-> Move<o:p>
|
Arrays:
Fsharp has other different data structures like List and Sequences (Seq).
Each one of them is powerful in their own way, for instance Seq can be used to
create an infinite length sequence and literally process it with least memory,
Seq is lazy loaded and at any moment the current element in the iterate is
alive.
Array was preferred for this work just because the tiles can be accessed
with an index as a handle. We can construct a simple int array by specifying the
elements within ‘[| |]’ symbols.
|
> let nums = [| 1; 2;
3; 4; 5; |];;<o:p>
val nums : int [] = [|1;
2; 3; 4; 5|]<o:p>
|
There are other ways of initialization as well, here is a few
|
> let nums = [|
1..1..10|];;<o:p>
val nums : int [] = [|1;
2; 3; 4; 5; 6; 7; 8; 9; 10|]<o:p>
<o:p>
> let nums = [|
2..2..20|];;<o:p>
val nums : int [] = [|2;
4; 6; 8; 10; 12; 14; 16; 18; 20|]<o:p>
|
Finally here is how the tiles are initialized,
|
> let tiles =
Array.init 3 (fun i -> new Tile(i));;<o:p>
val tiles : Tile [] =
[|FSI_0004+Tile; FSI_0004+Tile; FSI_0004+Tile|]<o:p>
|
Array.init takes the count of items to be generated and a
generator function to create the items.
Types:
Fsharp is all about types and type inference; if you are reading this
post then you must be interested in Type Providers as well, and I recommend you
watch Daniel Spiewak’s talk on
Principles of Type
Inference
Let me make it short about type definitions here.
Following is the syntax for one of the many ways to create a type and the
following uses an explicit constructor with a property and a method.
type typename (param:type) =
let mutable member = something
member alias.MemberName
with get() = value
and set(value) = member <- value
member alias.MethodName() = [some function]
|
type Tile (i:int) =<o:p>
let mutable state =
White<o:p>
member x.State<o:p>
with get() = state<o:p>
and set(value) = state
<- value<o:p>
member x.Reset() =<o:p>
x.State <- White<o:p>
><o:p>
type Tile =<o:p>
class<o:p>
new :
i:int -> Tile<o:p>
member Reset : unit -> unit<o:p>
member State : State<o:p>
member State : State with set<o:p>
end<o:p>
|
Inheritance:
As said earlier Fsharp supports oops concepts. Types can inherit from
other types and override its member, and it can be done with ‘inherits’ and
‘override’ keywords respectively.
For this work the UI is built with WPF and any changes in property has to
be notified to the UI. We have a type that implements the notification mechanism
‘ObservableObject’ and our Tile type will inherit from it.
|
type Tile (i:int) =<o:p>
inherit
ObservableObject()<o:p>
<o:p>
let mutable state =
White<o:p>
member x.State<o:p>
with get() = state<o:p>
and set(value) = state
<- value ; x.Notify x "State"<o:p>
member x.Reset() =<o:p>
x.State <- White<o:p>
><o:p>
type Tile =<o:p>
class<o:p>
inherit ObservableObject<o:p>
new :
i:int -> Tile<o:p>
member Reset : unit -> unit<o:p>
member State : State<o:p>
member State : State with set<o:p>
end<o:p>
|
Events and Interfaces:
There is no relation or intention to put events and Interfaces together,
but the ObservableObject mentioned in previous code block makes use of both of
them and therefore can be used as a single example. Interface implementation is
similar to the member and method definitions in a type, and the syntax is,
interface IInterfaceName with
member x.InterfaceMember = someValue
meber x.InterfaceMethod() = somFunction
Events are implemented in three steps, first is to define the event
signature, second is to publish the event on the other hand exposing the event
to the outer world to hook it and the final step is to trigger the event when
needed.
|
type
ObservableObject () =<o:p>
let propertyChangedEvent = new Event<_,_>()<o:p>
interface INotifyPropertyChanged with<o:p>
member x.PropertyChanged =
propertyChangedEvent.Publish<o:p>
member x.Notify s n = propertyChangedEvent.Trigger (s,
PropertyChangedEventArgs n)<o:p>
><o:p>
type
ObservableObject =<o:p>
class<o:p>
interface System.ComponentModel.INotifyPropertyChanged<o:p>
new : unit -> ObservableObject<o:p>
member Notify : s:'a -> n:string -> unit<o:p>
end<o:p>
|
That’s it and you can now experience the bug’s moves.
Hosting a Window:
The UI is presented with WPF window, and the flowers and bugs are
template and updated with triggers based on the state of the tile, and is
assumed the readers has enough knowledge on WPF. Here is how the Window is
hosted from fsharp.
Add a xml file from solution explorer, and update the extension
to be .Xaml
Mark the file as a resource and paste the xaml content to the
file.
|
let main =<o:p>
let
app = Application()<o:p>
let
window = Application.LoadComponent(new<o:p>
Uri
("TheForgottonAnt;component/MainWindow.xaml",
System.UriKind.Relative)) :?> Window<o:p>
app.Run window |> ignore<o:p>
[<STAThread>]<o:p>
main<o:p>
|
<o:p>
<o:p>
<o:p>HaPpY Coding!!!
