• Download source - 9.5 KB
• Download sample - 14 KB

 

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!!!